Dos pruebas elementales, y qué axioma hace la fuerza

Prueba 1 · ningún triángulo

Guía 7, Ejercicio 25 (b): $\forall x \forall y \forall z \neg (r (x, y) \land r (x, z) \land r (y, z))$ .

Un solo axioma alcanza: Aprop, $\forall x \forall y (r (x, y) \to ((R (x) \land \neg R (y)) \lor (\neg R (x) \land R (y))))$ . La cátedra lo escribe como disyunción y no como bicondicional negado — son equivalentes, pero la disyunción es la que abre los dos casos que la prueba usa.

Sean $a$ , $b$ , $c$ ∈ G fijos pero arbitrarios. Supongo por el absurdo que se da $(r (a, b) \land r (a, c) \land r (b, c))$ .

El axioma Aprop nos dice que: $(r (a, b) \to ((R (a) \land \neg R (b)) \lor (\neg R (a) \land R (b))))$ . Ya que se da $r (a, b)$ , obtenemos que se da $(R (a) \land \neg R (b)) \lor (\neg R (a) \land R (b))$ .

El axioma Aprop nos dice que: $(r (a, c) \to ((R (a) \land \neg R (c)) \lor (\neg R (a) \land R (c))))$ . Ya que se da $r (a, c)$ , obtenemos que se da $(R (a) \land \neg R (c)) \lor (\neg R (a) \land R (c))$ .

El axioma Aprop nos dice que: $(r (b, c) \to ((R (b) \land \neg R (c)) \lor (\neg R (b) \land R (c))))$ . Ya que se da $r (b, c)$ , obtenemos que se da $(R (b) \land \neg R (c)) \lor (\neg R (b) \land R (c))$ .

Abrimos dos casos, según la primera disyunción.

Caso 1. Supongamos que se da $(R (a) \land \neg R (b))$ .

Pero ya que se da $R (a)$ , no puede darse $(\neg R (a) \land R (c))$ , por lo cual obtenemos que se da $(R (a) \land \neg R (c))$ .

Pero ya que se da $\neg R (b)$ , no puede darse $(R (b) \land \neg R (c))$ , por lo cual obtenemos que se da $(\neg R (b) \land R (c))$ .

Se da $\neg R (c)$ y se da $R (c)$ , a la vez. Lo cual es una contradicción.

Caso 2. Supongamos que se da $(\neg R (a) \land R (b))$ .

Pero ya que se da $\neg R (a)$ , no puede darse $(R (a) \land \neg R (c))$ , por lo cual obtenemos que se da $(\neg R (a) \land R (c))$ .

Pero ya que se da $R (b)$ , no puede darse $(\neg R (b) \land R (c))$ , por lo cual obtenemos que se da $(R (b) \land \neg R (c))$ .

Se da $R (c)$ y se da $\neg R (c)$ , a la vez. Lo cual es una contradicción.

Ya que $a$ , $b$ , $c$ eran elementos fijos pero arbitrarios, hemos probado que vale $\forall x \forall y \forall z \neg (r (x, y) \land r (x, z) \land r (y, z))$ .

Abajo, la misma prueba: avanzá paso a paso y mirá al triángulo pintarse solo.

Prueba 2 · la mitad de una conmutatividad

Guía 7, pág. 15: $\forall x \forall y (x s y \leq y s x)$ . Es la primera mitad de la prueba de $\forall x \forall y (x s y = y s x)$ que la guía hace entera; la otra mitad es la misma cuenta con los nombres cambiados, y A≤A junta las dos en la igualdad.

Dos axiomas, uno cada uno: AsesC, $\forall x \forall y ((x \leq (x s y)) \land (y \leq (x s y)))$ ; y As≤C, $\forall x \forall y \forall z (((x \leq z) \land (y \leq z)) \to ((x s y) \leq z))$ .

Sean $a$ , $b$ ∈ L fijos pero arbitrarios.

El axioma AsesC nos dice que: $((b \leq (b s a)) \land (a \leq (b s a)))$ .

El axioma As≤C nos dice que: $(((a \leq (b s a)) \land (b \leq (b s a))) \to ((a s b) \leq (b s a)))$ . Ya que se da $((a \leq (b s a)) \land (b \leq (b s a)))$ , obtenemos que se da $((a s b) \leq (b s a))$ .

Ya que $a$ , $b$ eran elementos fijos pero arbitrarios, hemos probado que vale $\forall x \forall y (x s y \leq y s x)$ .

Lo que estas pruebas no dicen

Ninguna de las dos cuentas siguientes está en la guía. Salen de evaluar los axiomas sobre todas las estructuras chicas, que es lo que este sitio puede hacer y un apunte no.

De los tres axiomas de bicoloreado, la Prueba 1 usa uno. Sobre las 4096 estructuras de tres elementos con $r$ arbitraria —no sólo simétrica—, las 98 que cumplen Aprop no tienen ningún triángulo: las 98. No hace falta ni Airr ni Asim.

Y hay algo más: de esas mismas 98, todas cumplen también Airr —si valiera $r (a, a)$ , Aprop pediría $(R (a) \land \neg R (a)) \lor (\neg R (a) \land R (a))$ , que es imposible—, así que Airr es redundante frente a Aprop. Asim no lo es: de esas 98, hay 72 donde Asim falla.

De los siete axiomas de cuaterna, la Prueba 2 usa dos, y los dos hacen falta. Sobre las 19683 operaciones $s$ posibles en un orden total de tres elementos, sólo una cumple AsesC y As≤C a la vez, y ahí la sentencia nunca falla. De las 23 que cumplen AsesC sin As≤C, falla en 12; de las 1943 que cumplen As≤C sin AsesC, falla en 1836.

← Anterior Siguiente → Inicio

Sirve para el Ejercicio 25 de la Guía 7 y para la primera mitad de la prueba de conmutatividad de su página 15. La teoría está en parcial-2/preparacion/apunte-pruebas-elementales.pdf del repo de Lógica, y las resoluciones en parcial-2/soluciones/practico-7-lenguaje-elemental.pdf.