Lo que se deshace no junta a dos

El enunciado, textual: «Sea

$$\tau =(\varnothing ,\{\mathrm{Op}\},\varnothing ,\{(\mathrm{Op},1)\})$$

y sea

$$T=(\{\forall x(\mathrm{Op}(\mathrm{Op}(x))=x)\},\tau )$$

De pruebas elementales en $T$ de las siguientes sentencias elementales de tipo $\tau$:

(a) $\forall x\forall y(\neg (x=y)\to \neg (\mathrm{Op}(x)=\mathrm{Op}(y)))$

(b) $\forall x\exists y(\mathrm{Op}(y)=x)$»

Es el mismo enunciado que el Ejercicio 16 de la Guía 8, pág. 25.

01 · Antes de probar: qué pide cada inciso

Una prueba elemental en $T$ parte de una estructura $A=(A,i)$ de tipo $\tau$, fija pero arbitraria, de la que lo único que se sabe es que hace verdadero el axioma: es un modelo de la teoría. La estructura trae un universo no vacío y una función $i(\mathrm{Op})$ de $A$ en $A$. El axioma dice que esa función, aplicada dos veces, vuelve al punto de partida.

Traducidos, los dos incisos son dos propiedades de $i(\mathrm{Op})$ que se conocen por su nombre. El (a) es la inyectividad, escrita con negaciones: elementos distintos tienen imágenes distintas. El (b) es la sobreyectividad: todo elemento es imagen de alguno. Juntas dicen que $i(\mathrm{Op})$ es una biyección, y el axioma agrega que es su propia inversa.

La trampa está en el (a), y es leerlo al revés. La sentencia $\forall x\forall y(x=y\to \mathrm{Op}(x)=\mathrm{Op}(y))$ vale en cualquier estructura de tipo $\tau$, con o sin axioma: dice que $i(\mathrm{Op})$ es una función, que a entradas iguales da salidas iguales. La que pide el ejercicio es la otra dirección: salidas iguales sólo con entradas iguales. Ésa no vale en toda estructura, y el axioma es lo único que la sostiene.

02 · Lo que hay a mano

De la teoría, un solo axioma, y nada más:

$$\forall x(\mathrm{Op}(\mathrm{Op}(x))=x)$$

De la lógica, lo que vale en cualquier estructura y por eso no hay que enunciar ni probar aparte: una igualdad se da vuelta, dos igualdades se encadenan, y de $u=v$ se pasa a $\mathrm{Op}(u)=\mathrm{Op}(v)$, aplicando $\mathrm{Op}$ a los dos miembros. Esto último es lo que la trampa de arriba confundía con el ejercicio. Acá es una herramienta, y es la que hace el trabajo.

Para el (a) hace falta, además, una envoltura. La meta termina en una negación, y una negación no se construye: se prueba que lo contrario lleva a un absurdo. La otra salida es el contrarrecíproco, que cambia la meta por $\mathrm{Op}(a)=\mathrm{Op}(b)\to a=b$. Las dos llevan adentro la misma cuenta.

03 · La mariposa: volver por el mismo camino

Conviene dibujar $i(\mathrm{Op})$ como flechas: de cada punto sale exactamente una, la que lo lleva a su imagen. El axioma dice que si seguís la flecha dos veces, volvés adonde estabas. O sea: la flecha que sale de $\mathrm{Op}(a)$ vuelve a $a$.

Ahora suponé que dos puntos distintos, $a$ y $b$, caen en el mismo $c$. De $c$ sale una sola flecha. Por el axioma, tiene que volver a $a$, porque $a$ llegó a $c$; y tiene que volver a $b$, porque $b$ también llegó. Una flecha, dos destinos: no se puede, salvo que $a$ y $b$ sean el mismo. Ésa es toda la prueba, y en ecuaciones son cuatro renglones:

$$\mathrm{Op}(a)=\mathrm{Op}(b)\Rightarrow \mathrm{Op}(\mathrm{Op}(a))=\mathrm{Op}(\mathrm{Op}(b))\Rightarrow a=b$$

El primer paso es aplicar $\mathrm{Op}$ a los dos lados. El segundo, leer cada lado con el axioma: $\mathrm{Op}(\mathrm{Op}(a))$ es $a$ y $\mathrm{Op}(\mathrm{Op}(b))$ es $b$.

De atrás para adelante sale lo mismo. La meta, con $a$ y $b$ fijos, es $\neg (a=b)\to \neg (\mathrm{Op}(a)=\mathrm{Op}(b))$. Se supone el antecedente, $\neg (a=b)$, y la conclusión es una negación: se supone $\mathrm{Op}(a)=\mathrm{Op}(b)$ y se busca un absurdo. La cuenta de arriba da $a=b$, que choca con lo supuesto. Para el escarabajo conviene el absurdo y no el contrarrecíproco, porque es lo que se traduce directo al formato formal: en la lista de justificaciones hay ABSURDO y no hay una regla de contrarrecíproco.

Abajo, $i(\mathrm{Op})$ sobre cuatro puntos, a mano. Arranca cumpliendo el axioma. Intentá juntar dos puntos en el mismo destino sin romperlo.

Cada vez que dos flechas llegan al mismo punto, el axioma falla en uno de los dos que chocaron: la flecha que sale del punto de llegada vuelve a uno solo. Se puede contar: sobre cuatro puntos hay 256 maneras de elegir $i(\mathrm{Op})$, y en ellas aparecen 384 pares de puntos distintos que chocan. En los 384 el axioma falla en al menos uno de los dos. No hay excepción, que es lo que la prueba asegura para cualquier universo.

04 · El escarabajo del (a)

Como lo pide la Guía 8 para una prueba elemental en una teoría: renglones numerados, y cada uno justificado en una frase. Así están escritos los ejemplos de la guía, en las págs. 24 y 25.

Prueba. Sea $A=(A,i)$ una estructura de tipo $\tau$ que satisface el axioma de $T$, fija pero arbitraria. Sean $a,b\in A$ fijos pero arbitrarios, y supongamos $\neg (a=b)$. Queremos probar $\neg (\mathrm{Op}(a)=\mathrm{Op}(b))$. Supongamos, para llegar a un absurdo, que

La línea 5 contradice lo supuesto, $\neg (a=b)$. Luego $\neg (\mathrm{Op}(a)=\mathrm{Op}(b))$, y quedó probado

$$\neg (a=b)\to \neg (\mathrm{Op}(a)=\mathrm{Op}(b))$$

Como $a$ y $b$ eran fijos pero arbitrarios, vale $\forall x\forall y(\neg (x=y)\to \neg (\mathrm{Op}(x)=\mathrm{Op}(y)))$. ∎

Las dos instanciaciones del axioma van escritas, una por renglón, aunque digan lo mismo con otra letra. Y la línea 5 nombra de dónde sale cada eslabón: la 3 hay que leerla al revés, $a=\mathrm{Op}(\mathrm{Op}(a))$, para que la cadena arranque en $a$.

05 · El (b): el testigo se escribe

El (b) tiene su propio ensayo, que recorre la mariposa con calma: por qué el testigo es $\mathrm{Op}(a)$ y no $a$, y por qué alcanza con instanciar el axioma en el término correcto. Acá va la prueba elemental, para que el ejercicio quede entero.

Prueba. Sea $A=(A,i)$ una estructura de tipo $\tau$ que satisface el axioma de $T$, fija pero arbitraria, y sea $a\in A$ fijo pero arbitrario.

Como $a$ era fijo pero arbitrario, vale $\forall x\exists y(\mathrm{Op}(y)=x)$. ∎

Los dos incisos son independientes: ninguno usa al otro. Sobre un universo finito se sabe que una función inyectiva es sobreyectiva, pero ese resultado no sirve acá por dos razones: la estructura puede ser infinita, y si se lo usara habría que enunciarlo y probarlo por separado.

06 · Si la piden como prueba formal

La lista pide una prueba elemental, y la de la sección 04 es lo que se entrega. Pero el (a) vale como práctica del formato formal del apunte, con su lista cerrada de justificaciones y sus bloques de hipótesis, explicado en otro ensayo. Las mismas ideas, renglón por renglón:

Dos diferencias con el escarabajo elemental. «Aplicar $\mathrm{Op}$ a los dos miembros» no está en la lista: lo que hay es REEMPLAZO, que cambia una ocurrencia de $\mathrm{Op}(a)$ por $\mathrm{Op}(b)$ adentro de la línea 4. Por eso la línea 6 ya sale con $a$ a la derecha, y la cadena es más corta. Y el absurdo pide su forma exacta: ABSURDO pasa de $(\phi \to (\psi \wedge \neg \psi ))$ a $\neg \phi$, así que la contradicción se arma con una conjunción y el bloque se cierra antes de usarla.

Las dos generalizaciones son legales: $a$ y $b$ nacieron como constantes arbitrarias, ninguna salió de una ELECCION, y cuando se generaliza ya no hay ninguna hipótesis abierta que las mencione.

07 · Lo medido

Sobre cuatro puntos hay 256 funciones posibles. Cumplen el axioma 10, y en las 10 valen el (a) y el (b). Al revés no: hay 24 funciones inyectivas, y 14 de ellas no cumplen el axioma. Un ciclo de tres puntos, $1\to 2\to 3\to 1$, es inyectivo y sobreyectivo, y aplicado dos veces no vuelve. El axioma es más fuerte que lo que se prueba con él. Sobre cinco puntos, la misma cuenta da 3125 funciones, 26 que cumplen el axioma, 120 inyectivas y 94 inyectivas que no lo cumplen.

La teoría tiene modelos, así que no se está probando nada a partir de axiomas contradictorios: cualquier conjunto no vacío con la identidad, los enteros con $\mathrm{Op}(n)=-n$, o el modelo con el que arranca el widget.

08 · Lo que se lleva y lo que hace perder puntos

Aplicar la operación a los dos lados. Es el paso que convierte una hipótesis sobre imágenes en una afirmación sobre los elementos, cuando el axioma deshace la operación. La misma jugada sirve cada vez que un axioma tiene la forma de una ecuación que «vuelve».

Una negación se prueba suponiendo lo contrario. Con $\neg$ en la conclusión, la mariposa puede pensar por contrarrecíproco, pero el escarabajo formal va por absurdo.

Lo que hace perder puntos. Probar la dirección trivial del (a), la que no usa el axioma. Escribir «como $\mathrm{Op}$ es una involución, es biyectiva»: es un resultado, y la regla de la cátedra obliga a enunciarlo y probarlo por separado, que es exactamente lo que pide el ejercicio. Instanciar el axioma una vez y despachar la otra con «análogamente». Y en el (b), dar a $a$ como testigo: sólo sirve si $\mathrm{Op}(a)=a$, y el axioma no lo garantiza.

Para tener a mano

1. (a) es la inyectividad de $i(\mathrm{Op})$, (b) la sobreyectividad. La dirección $x=y\to \mathrm{Op}(x)=\mathrm{Op}(y)$ es gratis y no es la que se pide.
2. La mariposa del (a): de $c$ sale una sola flecha, y el axioma la manda de vuelta a cada punto que llegó a $c$.
3. Cuatro renglones: suponer $\mathrm{Op}(a)=\mathrm{Op}(b)$, aplicar $\mathrm{Op}$ a los dos lados, instanciar el axioma en $a$ y en $b$, encadenar hasta $a=b$.
4. La envoltura del (a) es un absurdo adentro de una implicación. En el formato formal: dos bloques, REEMPLAZO en lugar de «aplicar $\mathrm{Op}$», y ABSURDO sobre una conjunción.
5. El testigo del (b) es $\mathrm{Op}(a)$, y sale del axioma instanciado en $a$.