La simetría cubre el casillero que falta

El enunciado, textual: «Sea

$$\tau =(\{\mathrm{ce},\mathrm{un}\},\{\mathrm{FU}\},\{V\},\{(\mathrm{FU},2),(V,1)\})$$

y sea $\Sigma$ formado por las siguientes sentencias elementales puras de tipo $\tau$:

$$\forall x\forall y(V(x)\to (\mathrm{FU}(x,y)=\mathrm{ce}))$$ $$\forall x\forall y(\neg V(y)\to (\mathrm{FU}(x,y)=\mathrm{un}))$$ $$\forall x\forall y(\mathrm{FU}(x,y)=\mathrm{FU}(y,x))$$

De una prueba elemental de

$$\forall x\forall y((\mathrm{FU}(x,y)=\mathrm{ce})\vee (\mathrm{FU}(x,y)=\mathrm{un}))$$

en $(\Sigma ,\tau )$». Es el mismo enunciado que el Ejercicio 18 de la Guía 8, pág. 25.

01 · Antes de probar: qué dice cada axioma

Una prueba elemental en $(\Sigma ,\tau )$ parte de una estructura $A=(A,i)$ de tipo $\tau$, fija pero arbitraria, de la que sólo se sabe que satisface los tres axiomas: un modelo de la teoría. Trae dos elementos con nombre, $i(\mathrm{ce})$ e $i(\mathrm{un})$, una operación binaria $i(\mathrm{FU})$ y un subconjunto $i(V)$ del universo.

Conviene pensar a $\mathrm{FU}$ como una tabla: la fila es el primer argumento, la columna el segundo. Leídos así, los axiomas dicen:

• El primero: la fila de un elemento que está en $V$ está llena de $\mathrm{ce}$. Mira el primer argumento.
• El segundo: la columna de un elemento que no está en $V$ está llena de $\mathrm{un}$. Mira el segundo argumento.
• El tercero: la tabla es simétrica respecto de la diagonal.

Lo que hay que probar es que cada casillero de la tabla tiene $\mathrm{ce}$ o $\mathrm{un}$. Y la pregunta que ordena todo es qué casillero no está en ninguna de las filas del primero ni en ninguna de las columnas del segundo. Es el de fila fuera de $V$ y columna dentro de $V$: ahí los dos primeros axiomas no dicen nada.

02 · Lo que hay a mano

Los tres axiomas y nada más. De la lógica, lo que vale en cualquier estructura: un elemento está en $V$ o no está, sin tercera posibilidad, así que se puede dividir en casos según $V(a)$ y $\neg V(a)$; de una implicación y su antecedente sale el consecuente; dos igualdades se encadenan; y de una de las dos partes de una disyunción sale la disyunción entera.

Eso último parece poco, y es lo que cierra cada caso. La meta es una disyunción, pero en cada caso se prueba algo más fuerte, una de sus dos partes, y la disyunción viene gratis.

03 · La mariposa: el casillero que nadie mira

Fijá $a$ y $b$, y preguntá en qué casillero cae $\mathrm{FU}(a,b)$. Según $a$ y $b$ estén o no en $V$, hay tres situaciones, y las dos primeras se pisan:

• $V(a)$, cualquier $b$: el primer axioma da $\mathrm{FU}(a,b)=\mathrm{ce}$.
• $\neg V(b)$, cualquier $a$: el segundo da $\mathrm{FU}(a,b)=\mathrm{un}$.
• $\neg V(a)$ y $V(b)$: ninguno de los dos. Es el casillero que falta.

El tercer axioma lo resuelve dándolo vuelta. $\mathrm{FU}(a,b)=\mathrm{FU}(b,a)$, y $\mathrm{FU}(b,a)$ está en la fila de $b$, que está en $V$: el primer axioma, con los argumentos cambiados, da $\mathrm{FU}(b,a)=\mathrm{ce}$. La simetría lleva el casillero que nadie mira a uno que sí está cubierto.

Para escribirlo no hacen falta cuatro casos: alcanza con partir según $V(a)$. Si vale, el primer axioma resuelve de frente. Si no vale, $a$ tiene que pasar a ser el segundo argumento para que el segundo axioma lo vea: tomando $x$ como $b$ e $y$ como $a$, da $\mathrm{FU}(b,a)=\mathrm{un}$ sin preguntar nada sobre $b$. Y el tercer axioma devuelve $\mathrm{FU}(a,b)=\mathrm{un}$.

La tentación es usar el segundo axioma de frente, tomando $x$ como $a$ e $y$ como $b$. Eso pide $\neg V(b)$, que no se tiene, y obliga a abrir un subcaso según $V(b)$. En el subcaso $V(b)$ vuelve a hacer falta la simetría. Por donde se lo mire, el tercer axioma se usa una vez.

Abajo, una estructura de tipo $\tau$ sobre tres elementos, con su tabla a mano. Arranca con $V$ vacío, donde no hay ningún casillero sin cubrir. Prendé $V$ en algún elemento y mirá qué casilleros quedan para el tercer axioma.

Con el tercer axioma apagado, un valor raro en un casillero azul deja una estructura que cumple los dos primeros y donde la sentencia es falsa. El más chico tiene dos elementos: $V=\{1\}$, $i(\mathrm{ce})=i(\mathrm{un})=1$, todos los casilleros en $1$ salvo $\mathrm{FU}(2,1)=2$. Con el tercer axioma prendido, ese mismo valor rompe la simetría, porque $\mathrm{FU}(1,2)$ está en la fila de $1$ y vale $\mathrm{ce}$. Ésa es exactamente la línea de la prueba donde entra la conmutatividad.

Y el widget deja ver algo que la prueba no pide. Con $V$ ni vacío ni todo el universo, hay un casillero en la fila de un elemento de $V$ y la columna de uno que no está: el primer axioma le pide $\mathrm{ce}$ y el segundo $\mathrm{un}$. Sólo se arregla si $i(\mathrm{ce})=i(\mathrm{un})$. Nada obliga a interpretar dos nombres distintos con elementos distintos, y en este caso la teoría obliga a lo contrario.

04 · El escarabajo

Como lo pide la Guía 8 para una prueba elemental en una teoría, en el formato de sus ejemplos de las págs. 24 y 25: renglones numerados, cada uno justificado en una frase.

Prueba. Sea $A=(A,i)$ una estructura de tipo $\tau$ que satisface $\Sigma$, fija pero arbitraria. Sean $a,b\in A$ fijos pero arbitrarios. O bien $V(a)$, o bien $\neg V(a)$; dividimos en esos dos casos.

Caso 1: $V(a)$.

Caso 2: $\neg V(a)$.

Los dos casos agotan las posibilidades y en los dos vale la disyunción, así que

$$(\mathrm{FU}(a,b)=\mathrm{ce})\vee (\mathrm{FU}(a,b)=\mathrm{un})$$

Como $a$ y $b$ eran fijos pero arbitrarios, vale $\forall x\forall y((\mathrm{FU}(x,y)=\mathrm{ce})\vee (\mathrm{FU}(x,y)=\mathrm{un}))$. ∎

La línea que vale la nota es la 4: el segundo axioma instanciado con los argumentos cruzados. Es la que pone a $a$ donde el axioma lo puede ver, y la 6 deshace el cruce.

05 · Si la piden como prueba formal

La lista pide una prueba elemental, y la de arriba es lo que se entrega. En el formato formal del apunte, con su lista cerrada de justificaciones y sus bloques de hipótesis —explicado en otro ensayo—, la división por casos es DIVISIONPORCASOS, que cita tres líneas: la disyunción y las dos implicaciones. Y hay un detalle que el escarabajo elemental esconde: «$V(a)$ o $\neg V(a)$» no es un axioma lógico. Entre los nueve esquemas del apunte no está el tercero excluido, así que hay que fabricarlo, y se fabrica en cuatro líneas.

La línea 4 usa la tercera forma de DISJUNCIONINTRODUCCION, la que pasa de $(\neg \phi \to \psi )$ a $(\phi \vee \psi )$: con $\phi$ igual a $V(a)$ y $\psi$ igual a $\neg V(a)$, la implicación trivial de la línea 3 se vuelve el tercero excluido. Las dos generalizaciones del final son legales porque $a$ y $b$ no salieron de ninguna ELECCION y los tres bloques ya cerraron.

Las disyunciones se usan de dos maneras, y conviene no confundirlas. Acá se producen: cada caso consigue una parte y la introduce. En Si no sale ninguna flecha, entra una se consumen: hay una disyunción probada y la negación de una de sus partes, y DISJUNCIONELIMINACION deja la otra.

06 · Lo medido

Recorriendo todas las estructuras de tipo $\tau$ sobre dos elementos —256, contando cada elección de $V$, de $i(\mathrm{ce})$, de $i(\mathrm{un})$ y de la tabla— hay 12 modelos, y en los 12 la sentencia vale. Sobre tres elementos son 1 417 176 estructuras, 36 modelos y ninguna falla.

Cada axioma hace falta. Sin el tercero, sobre tres elementos hay 180 estructuras que cumplen los dos primeros, y en 144 la sentencia es falsa. Sin el segundo, 7380 cumplen el primero y el tercero, y en 6786 falla. Sin el primero, la misma cuenta: 7380 y 6786.

Y la teoría dice bastante más que la sentencia. En los 36 modelos de tres elementos, $i(\mathrm{FU})$ es constante, y en los 18 donde $V$ no es ni vacío ni todo el universo, $i(\mathrm{ce})=i(\mathrm{un})$. No es un accidente de los tamaños chicos. Si $V$ es todo el universo, el primer axioma llena la tabla de $\mathrm{ce}$. Si es vacío, el segundo la llena de $\mathrm{un}$. Y si hay un $p$ en $V$ y un $q$ fuera, $\mathrm{FU}(p,q)$ vale $\mathrm{ce}$ y $\mathrm{un}$ a la vez, así que son el mismo elemento y la tabla entera vale eso. La sentencia del ejercicio, «toma a lo sumo dos valores», es más débil que lo que de verdad pasa: toma uno.

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

Dibujar los axiomas como pedazos de una tabla. Cuando los axiomas condicionan argumentos distintos, la pregunta útil es qué casillero no cubre ninguno. Ahí está el caso difícil, y ahí entra el axioma que parecía de relleno.

Instanciar con los argumentos cruzados. Un axioma universal se puede tomar con cualquier término en cualquier variable. Si el dato está en la primera coordenada y el axioma lo pide en la segunda, se lo instancia al revés y después se usa la simetría.

Una meta disyuntiva se cierra con una de sus partes. En cada caso se prueba algo más fuerte que la disyunción y se la introduce.

Lo que hace perder puntos. Dividir en casos que no agotan, por ejemplo «$V(a)$ y $V(b)$» contra «ninguno de los dos». Usar el segundo axioma de frente en el caso $\neg V(a)$, que pide un dato sobre $b$ que no se tiene. Olvidarse del tercer axioma y cerrar el caso 2 con «análogamente». Y suponer que $\mathrm{ce}$ y $\mathrm{un}$ son distintos: no está en $\Sigma$, y en muchos modelos son el mismo elemento.

Para tener a mano

1. El primer axioma llena filas de elementos de $V$; el segundo, columnas de elementos fuera de $V$. Queda sin cubrir fila fuera de $V$ por columna dentro.
2. El tercero da vuelta ese casillero y lo manda a uno cubierto.
3. Un solo corte alcanza: según $V(a)$. En el caso $\neg V(a)$, segundo axioma con $x$ como $b$ e $y$ como $a$, y después simetría.
4. Cada caso prueba una parte de la disyunción y la introduce.
5. En el formato formal, el tercero excluido no es axioma lógico: se arma con un bloque trivial y DISJUNCIONINTRODUCCION.