El 5 y el 7 no se distinguen

El enunciado, textual: «Sea $\tau =(\{\mathrm{iz}\},\varnothing ,\{{\mathrm{me}}^2\},a)$. Sea $𝐀$ dado por $A=\{2,5,7,70,140,280\}$, ${\mathrm{me}}^{𝐀}=\{(i,j):i\mid j\text{ y }i\ne j\}$ y ${\mathrm{iz}}^{𝐀}=2$. Para cada elemento definible de una formula que lo defina (no es necesario demostrar que las fórmulas propuestas funcionan). Use el criterio NoDefinible para justificar cuales no son definibles.» Es el Ejercicio 18 de la Guía 11.

01 · Qué pide, en criollo

El tipo tiene un nombre de constante, $\mathrm{iz}$, ningún nombre de función y un nombre de relación binaria, $\mathrm{me}$. La estructura interpreta $\mathrm{me}$ como «divide estrictamente» sobre seis números, e $\mathrm{iz}$ como el 2. Escrita entera, la relación son doce pares:

$${\mathrm{me}}^{𝐀}=\{(2,70),(2,140),(2,280),(5,70),(5,140),(5,280),(7,70),(7,140),(7,280),(70,140),(70,280),(140,280)\}$$

O sea: 2, 5 y 7 dividen a 70, 140 y 280; 70 divide a 140 y a 280; 140 divide a 280. A 2, 5 y 7 no los divide estrictamente nadie de $A$, y 280 no divide estrictamente a nadie.

Que un elemento sea definible quiere decir que hay una fórmula con a lo sumo $x_1$ libre que él cumple y ningún otro cumple. Una fórmula así es una descripción tan precisa que un solo elemento encaja. Por ejemplo, $\forall x_2\neg \mathrm{me}(x_1,x_2)$ dice «$x_1$ no divide estrictamente a nadie». Mirándola elemento por elemento: 2, 5, 7, 70 y 140 dividen estrictamente a 280, así que no la cumplen; 280 sí. Esa fórmula define a 280.

El ejercicio tiene dos mitades. Para los definibles, dar la fórmula. Para los otros, probar que no hay ninguna, y eso no se hace probando fórmulas: «no encontré» no prueba nada. Se hace con un isomorfismo. Y antes de buscar nada conviene mirar a 5 y 7: nadie los divide, dividen a los mismos tres números, ninguno divide al otro y ninguno es el que nombra $\mathrm{iz}$. Cualquier cosa que se diga del 5 con $\mathrm{me}$ e $\mathrm{iz}$ vale igual para el 7. Esa es la intuición, y NoDefinible la convierte en prueba.

02 · Las herramientas

Elemento definible (Guía 11, p. 4). Sea $𝐀$ un modelo de tipo $\tau$. Un elemento $a$ de $A$ es definible en $𝐀$ si hay una fórmula $\phi {=}_d\phi (v)$ tal que $𝐀\models \phi [a]$ y, para cada $b\in A-\{a\}$, $𝐀⊭\phi [b]$. Se dice entonces que $\phi$ define a $a$ en $𝐀$. Declarar $\phi {=}_d\phi (v)$ pide que las variables libres de $\phi$ estén entre $v$; acá $v$ es siempre $x_1$, y $𝐀\models \phi [a]$ se lee «$\phi$ es verdadera cuando $x_1$ vale $a$».

Homomorfismo e isomorfismo (Guía 10, p. 11–12). Una función $F:A\to B$ es un homomorfismo de $𝐀$ en $𝐁$ si

• (1) $F(c^{𝐀})=c^{𝐁}$, para todo $c\in 𝒞$;
• (2) $F({\mathrm{f}}^{𝐀}(a_1,\dots ,a_n))={\mathrm{f}}^{𝐁}(F(a_1),\dots ,F(a_n))$, para cada $\mathrm{f}\in {ℱ}_n$ y $a_1,\dots ,a_n\in A$;
• (3) $(a_1,\dots ,a_n)\in r^{𝐀}$ implica $(F(a_1),\dots ,F(a_n))\in r^{𝐁}$, para todo $r\in {ℛ}_n$ y $a_1,\dots ,a_n\in A$.

Un isomorfismo es un homomorfismo biyectivo cuya inversa también es un homomorfismo. Acá $𝐁$ es el mismo $𝐀$: se buscan isomorfismos de $𝐀$ en $𝐀$, que son las maneras de mover los elementos sin que $\mathrm{iz}$ ni $\mathrm{me}$ lo noten.

El criterio NoDefinible (Guía 11, p. 7). Si $𝐀$ es un modelo de tipo $\tau$ y $a\in A$ es tal que $F(a)\ne a$ para algún isomorfismo $F:𝐀\to 𝐀$, entonces $a$ no es definible en $𝐀$. La consigna manda usarlo, así que se enuncia y se aplica sin probarlo. Por qué es correcto —es el Ejercicio 36 de la guía— está en Elementos definibles.

03 · La mariposa: describir por lo que distingue

Para cada elemento se busca un rasgo que tenga él y ningún otro. Con este tipo hay tres clases de rasgos: a quién divide, quién lo divide, y si es el que nombra $\mathrm{iz}$. Cada intento se controla igual: se recorre $A$ y se mira quién lo cumple.

El 2 tiene nombre. Es lo más barato: $(x_1\equiv \mathrm{iz})$, «$x_1$ es el que nombra $\mathrm{iz}$». Lo cumple el 2, porque ${\mathrm{iz}}^{𝐀}=2$, y nadie más.

El 280 está arriba de todo. $\forall x_2\neg \mathrm{me}(x_1,x_2)$, «$x_1$ no divide estrictamente a nadie». Los otros cinco dividen estrictamente a 280.

El 140 divide a uno solo. «$x_1$ divide estrictamente a alguien, y a uno solo»:

$$(\exists x_2\mathrm{me}(x_1,x_2)\wedge \forall x_2\forall x_3((\mathrm{me}(x_1,x_2)\wedge \mathrm{me}(x_1,x_3))\to (x_2\equiv x_3)))$$

La primera mitad deja afuera al 280. La segunda es la manera de decir «a lo sumo uno» sin un símbolo para eso: si $x_1$ divide a $x_2$ y a $x_3$, son el mismo. El 140 divide sólo a 280; el 70 divide a 140 y a 280; 2, 5 y 7 dividen a tres.

El 70 tiene una cadena de dos pasos encima. «2 divide estrictamente a $x_1$, y arriba de $x_1$ hay una cadena de dos pasos»:

$$(\mathrm{me}(\mathrm{iz},x_1)\wedge \exists x_2\exists x_3(\mathrm{me}(x_1,x_2)\wedge \mathrm{me}(x_2,x_3)))$$

$\mathrm{me}(\mathrm{iz},x_1)$ deja a 70, 140 y 280. De esos, sólo el 70 tiene dos pasos encima: $70\mid 140\mid 280$. El 140 tiene uno, el 280 ninguno. La constante, de paso, no hacía falta: «alguien divide estrictamente a $x_1$» descarta igual a 2, 5 y 7, y $(\exists x_2\exists x_3(\mathrm{me}(x_1,x_2)\wedge \mathrm{me}(x_2,x_3))\wedge \exists x_2\mathrm{me}(x_2,x_1))$ también define al 70.

El 5 y el 7 no se dejan separar. «Nadie lo divide estrictamente», $\neg \exists x_2\mathrm{me}(x_2,x_1)$, lo cumplen 2, 5 y 7. Agregando «y no es $\mathrm{iz}$» queda $\{5,7\}$. «Divide estrictamente a tres distintos» vuelve a dar $\{2,5,7\}$. Cada intento se lleva a los dos juntos, y no es mala suerte.

04 · El cambio que no se nota

Lo que hace que 5 y 7 vayan siempre juntos es que cambiarlos entre sí es un isomorfismo. Sea $F$ la función que manda 5 a 7, 7 a 5 y deja fijo todo lo demás. Mueve sólo a dos elementos que tienen exactamente las mismas relaciones con todo el resto: los dos dividen a 70, 140 y 280, a ninguno lo divide nadie, ninguno divide al otro, y ninguno es ${\mathrm{iz}}^{𝐀}$. Un par de ${\mathrm{me}}^{𝐀}$ pasa por $F$ a otro par de ${\mathrm{me}}^{𝐀}$, y la constante queda donde estaba.

¿Cómo se encuentra ese $F$ sin probar al azar? Un isomorfismo de $𝐀$ en $𝐀$ tiene que dejar fijo a 2, por la condición (1). Y tiene que conservar todo lo que se puede decir con una fórmula: manda el único que no divide a nadie al único que no divide a nadie, el único que divide a uno solo al que divide a uno solo, y así. Las fórmulas de arriba atan a 2, 70, 140 y 280; el único movimiento que queda es entre 5 y 7. De las $6!=720$ biyecciones de $A$ en $A$, son isomorfismos exactamente dos: la identidad y ésta.

Abajo está la estructura con su diagrama de divisibilidad. Cada fórmula ilumina a los que la cumplen, y $F$ se arma elemento por elemento: se ve qué condición falla y con qué testigo.

Cambiar 2 con 5 falla ya en la condición (1): $F({\mathrm{iz}}^{𝐀})=F(2)=5$, y ${\mathrm{iz}}^{𝐀}=2$. Cambiar 5 con 70 falla en la (3) con el par $(2,70)$: $\mathrm{me}(2,70)$ vale y $\mathrm{me}(F(2),F(70))=\mathrm{me}(2,5)$ no. Cada transposición que toca a 2, 70, 140 o 280 falla en alguna; la única que pasa las tres es la de 5 con 7.

05 · El escarabajo: la respuesta escrita

Los definibles: 2, 70, 140 y 280. Cada uno, con su fórmula y la razón en una línea:

• $(x_1\equiv \mathrm{iz})$ define a 2: «$x_1$ es el que nombra $\mathrm{iz}$», y ${\mathrm{iz}}^{𝐀}=2$.
• $\forall x_2\neg \mathrm{me}(x_1,x_2)$ define a 280: «$x_1$ no divide estrictamente a nadie»; todos los demás dividen estrictamente a 280.
• $(\exists x_2\mathrm{me}(x_1,x_2)\wedge \forall x_2\forall x_3((\mathrm{me}(x_1,x_2)\wedge \mathrm{me}(x_1,x_3))\to (x_2\equiv x_3)))$ define a 140: «$x_1$ divide estrictamente a alguien, y a uno solo»; 140 divide sólo a 280, 70 divide a dos, 2, 5 y 7 a tres, 280 a ninguno.
• $(\mathrm{me}(\mathrm{iz},x_1)\wedge \exists x_2\exists x_3(\mathrm{me}(x_1,x_2)\wedge \mathrm{me}(x_2,x_3)))$ define a 70: «2 divide estrictamente a $x_1$ y encima de $x_1$ hay una cadena de dos pasos»; de 70, 140 y 280, sólo 70 tiene $70\mid 140\mid 280$.

Los no definibles: 5 y 7. Sea $F:A\to A$ dada por $F(5)=7$, $F(7)=5$ y $F(a)=a$ para $a\in \{2,70,140,280\}$. Veamos que $F$ es un isomorfismo de $𝐀$ en $𝐀$.

• $F$ es biyectiva y $F\circ F$ es la identidad de $A$, así que $F^{-1}=F$.
• Condición (1). La única constante es $\mathrm{iz}$, y $F({\mathrm{iz}}^{𝐀})=F(2)=2={\mathrm{iz}}^{𝐀}$.
• Condición (2). $\tau$ no tiene nombres de función: no hay nada que verificar.
• Condición (3). Sea $(a,b)\in {\mathrm{me}}^{𝐀}$. Ningún elemento de $A$ divide estrictamente a 2, a 5 ni a 7, así que $b\in \{70,140,280\}$ y $F(b)=b$. Si $a\notin \{5,7\}$, $(F(a),F(b))=(a,b)\in {\mathrm{me}}^{𝐀}$. Si $a=5$, $(F(a),F(b))=(7,b)$, y $(7,b)\in {\mathrm{me}}^{𝐀}$ porque 7 divide a 70, a 140 y a 280 y es distinto de los tres. Si $a=7$, $(F(a),F(b))=(5,b)$, que está en ${\mathrm{me}}^{𝐀}$ por lo mismo con 5.
• Entonces $F$ es un homomorfismo de $𝐀$ en $𝐀$, y como $F^{-1}=F$, la inversa también lo es. $F$ es un isomorfismo.

Como $F(5)=7\ne 5$, por el criterio NoDefinible 5 no es definible en $𝐀$. Como $F(7)=5\ne 7$, por el mismo criterio 7 no es definible en $𝐀$. Los elementos definibles son exactamente 2, 70, 140 y 280.

06 · Lo que hace perder puntos

Decir «5 y 7 no son definibles porque no se les encuentra fórmula». No es una prueba. Lo que prueba es el isomorfismo, con sus tres condiciones verificadas.

Olvidar la condición (1). Una permutación que mueve al 2 no es un isomorfismo, por más que respete $\mathrm{me}$. Sin la constante la cuenta cambia: con $\tau =(\varnothing ,\varnothing ,\{{\mathrm{me}}^2\},a)$ hay seis isomorfismos, que permutan 2, 5 y 7 de todas las maneras, y ninguno de los tres es definible. La constante es lo único que separa al 2.

Verificar (3) sólo para F. Con relaciones, un homomorfismo biyectivo puede no ser isomorfismo: hace falta que la inversa también preserve $\mathrm{me}$. Acá es gratis porque $F^{-1}=F$, pero hay que decirlo.

Escribir «∃!» o «el único». No son símbolos del lenguaje. «A uno solo» se escribe con $\forall x_2\forall x_3((\mathrm{me}(x_1,x_2)\wedge \mathrm{me}(x_1,x_3))\to (x_2\equiv x_3))$.

Dejar otra variable libre. $\mathrm{me}(x_1,x_2)$ no es una fórmula $\phi {=}_d\phi (x_1)$: su verdad depende de cuánto valga $x_2$. Toda variable que no sea $x_1$ tiene que quedar cuantificada.

Lo mismo, sin constantes y con todo definible, es el Ejercicio 19; una simetría que el dibujo sugiere y que no es isomorfismo, el Ejercicio 20. Que un isomorfismo no cambia ninguna verdad, que es lo que sostiene a NoDefinible, es el Ejercicio 29.

Para tener a mano

1. Definir es describir: una fórmula con sólo $x_1$ libre que cumpla él y nadie más. Se controla recorriendo $A$.
2. 2 por su nombre, 280 por no dividir a nadie, 140 por dividir a uno solo, 70 por la cadena de dos pasos que tiene encima.
3. 5 y 7 no: cambiarlos es un isomorfismo. (1) deja fijo a 2; (2) no hay funciones; (3) un par $(5,b)$ va a $(7,b)$, que también está; la inversa es $F$ misma.
4. No definible se prueba con un isomorfismo que lo mueve, nunca con «no encontré fórmula».