f y g no son intercambiables

El enunciado, textual: «Sea $\tau =(\varnothing ,\{{\mathrm{f}}^1,{\mathrm{g}}^1\},\varnothing ,a)$, y sea $𝐀$ el modelo de $\tau$ con universo $A=\{1,2,3,4\}$ y donde las interpretaciones de $\mathrm{f}$ y $\mathrm{g}$ están dadas por el siguiente diagrama. […] 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 19 de la Guía 11.

El diagrama tiene el 1 abajo, el 2 a la izquierda, el 3 a la derecha y el 4 arriba. Una flecha rotulada $\mathrm{f}$ de $a$ a $b$ dice ${\mathrm{f}}^{𝐀}(a)=b$. Del 1 sale una flecha $\mathrm{f}$ al 2 y una $\mathrm{g}$ al 3; del 2 y del 3 salen flechas $\mathrm{f},\mathrm{g}$ al 4; y el 4 tiene un rulo $\mathrm{f},\mathrm{g}$ sobre sí mismo. Como tabla:

01 · Qué pide, en criollo

El dibujo es simétrico: si se lo refleja de izquierda a derecha, el 2 y el 3 cambian de lugar y todo lo demás queda igual. La tentación es concluir que el 2 y el 3 no se distinguen, como el 5 y el 7 del Ejercicio 18, y que no son definibles. Pero el reflejo no deja las flechas iguales: la flecha del 1 al 2 es $\mathrm{f}$, y su reflejo, del 1 al 3, es $\mathrm{g}$. El espejo cambia $\mathrm{f}$ por $\mathrm{g}$, y un isomorfismo no puede cambiar nombres: tiene que respetar $\mathrm{f}$ como $\mathrm{f}$ y $\mathrm{g}$ como $\mathrm{g}$.

Así que la pregunta es la de siempre: qué tiene cada elemento que no tengan los otros. Con funciones, los rasgos son adónde va cada uno y quién llega a él. Por ejemplo, $(\mathrm{f}(x_1)\equiv x_1)$ dice «$\mathrm{f}$ deja a $x_1$ en su lugar»: $\mathrm{f}(1)=2$, $\mathrm{f}(2)=4$, $\mathrm{f}(3)=4$ y $\mathrm{f}(4)=4$, así que la cumple sólo el 4.

02 · Las herramientas

Elemento definible (Guía 11, p. 4). $a\in A$ es definible en $𝐀$ si hay $\phi {=}_d\phi (v)$ con $𝐀\models \phi [a]$ y $𝐀⊭\phi [b]$ para cada $b\in A-\{a\}$. Acá $v$ es $x_1$: la fórmula tiene a lo sumo $x_1$ libre, y la cumple $a$ y nadie más.

Homomorfismo e isomorfismo (Guía 10, p. 11–12). $F:A\to B$ es un homomorfismo si respeta las constantes (1), conmuta con las funciones (2) y preserva las relaciones (3); un isomorfismo es un homomorfismo biyectivo cuya inversa también lo es. Este $\tau$ no tiene constantes ni relaciones, así que de las tres condiciones sólo habla la (2), y con $𝐁=𝐀$ dice: para cada $a\in A$,

$$F({\mathrm{f}}^{𝐀}(a))={\mathrm{f}}^{𝐀}(F(a))\text{ y }F({\mathrm{g}}^{𝐀}(a))={\mathrm{g}}^{𝐀}(F(a))$$

En el dibujo: si hay una flecha $\mathrm{f}$ de $a$ a $b$, tiene que haber una flecha $\mathrm{f}$ de $F(a)$ a $F(b)$, y lo mismo con $\mathrm{g}$. Las flechas se mueven con su rótulo.

El criterio NoDefinible (Guía 11, p. 7). Si $F(a)\ne a$ para algún isomorfismo $F:𝐀\to 𝐀$, entonces $a$ no es definible en $𝐀$. La consigna manda usarlo; por qué es correcto está en Elementos definibles.

03 · La mariposa: quién llega a cada uno

El 4 es el punto fijo. $(\mathrm{f}(x_1)\equiv x_1)$: «$\mathrm{f}$ deja a $x_1$ en su lugar». Al 4 lo manda a sí mismo, a los demás los mueve.

Al 1 no llega nadie. Ninguna flecha entra al 1: no es $\mathrm{f}$ de nadie ni $\mathrm{g}$ de nadie.

$$(\neg \exists x_2(\mathrm{f}(x_2)\equiv x_1)\wedge \neg \exists x_2(\mathrm{g}(x_2)\equiv x_1))$$

«No hay ningún $x_2$ con $\mathrm{f}(x_2)=x_1$, ni ningún $x_2$ con $\mathrm{g}(x_2)=x_1$». Al 2 llega $\mathrm{f}$ desde el 1, al 3 llega $\mathrm{g}$ desde el 1, al 4 llegan las dos. También sirve una más corta, $\neg (\mathrm{f}(x_1)\equiv \mathrm{g}(x_1))$, «$\mathrm{f}$ y $\mathrm{g}$ lo mandan a lugares distintos»: sólo el 1 sale por dos flechas a dos lugares.

Al 2 llega f y no llega g; al 3, al revés. Ésta es la diferencia que el dibujo esconde:

$$(\exists x_2(\mathrm{f}(x_2)\equiv x_1)\wedge \neg \exists x_2(\mathrm{g}(x_2)\equiv x_1))$$ $$(\exists x_2(\mathrm{g}(x_2)\equiv x_1)\wedge \neg \exists x_2(\mathrm{f}(x_2)\equiv x_1))$$

«Está en la imagen de $\mathrm{f}$» sola deja al 2 y al 4, porque al 4 llegan las dos; «y no en la de $\mathrm{g}$» saca al 4. La del 3 es la misma con $\mathrm{f}$ y $\mathrm{g}$ cambiados.

Por qué cambiar 2 con 3 no es isomorfismo. Sea $F$ la función que cambia 2 con 3 y deja fijos 1 y 4. La condición (2) con $\mathrm{f}$ en el 1 pide $F({\mathrm{f}}^{𝐀}(1))={\mathrm{f}}^{𝐀}(F(1))$. A la izquierda, $F({\mathrm{f}}^{𝐀}(1))=F(2)=3$. A la derecha, ${\mathrm{f}}^{𝐀}(F(1))={\mathrm{f}}^{𝐀}(1)=2$. Y $3\ne 2$. En el dibujo: la flecha $\mathrm{f}$ del 1 al 2 tendría que ir a una flecha $\mathrm{f}$ del 1 al 3, y la flecha del 1 al 3 es $\mathrm{g}$. Las fórmulas lo dicen de otro modo: al 2 llega $\mathrm{f}$ y al 3 no, y un isomorfismo no puede llevar un elemento que cumple una fórmula a uno que no la cumple.

Abajo está el diagrama con sus rótulos. Cada fórmula ilumina a los que la cumplen, y $F$ se arma elemento por elemento.

El cambio de 2 con 3 falla con $\mathrm{f}$ en el 1, que es lo primero que se mira. Las otras cinco transposiciones también fallan en la (2): las que tocan al 1 o al 2, con $\mathrm{f}$ en el 1, y la de 3 con 4, con $\mathrm{f}$ en el 2. De las $4!=24$ biyecciones de $A$ en $A$, el único isomorfismo es la identidad.

04 · El escarabajo: la respuesta escrita

Los cuatro elementos son definibles. Cada uno, con su fórmula y la razón en una línea:

• El 4. $(\mathrm{f}(x_1)\equiv x_1)$: «$\mathrm{f}$ deja a $x_1$ en su lugar». ${\mathrm{f}}^{𝐀}(4)=4$, y ${\mathrm{f}}^{𝐀}(1)=2$, ${\mathrm{f}}^{𝐀}(2)={\mathrm{f}}^{𝐀}(3)=4$.
• El 1. $(\neg \exists x_2(\mathrm{f}(x_2)\equiv x_1)\wedge \neg \exists x_2(\mathrm{g}(x_2)\equiv x_1))$: «$x_1$ no es imagen ni de $\mathrm{f}$ ni de $\mathrm{g}$». La imagen de ${\mathrm{f}}^{𝐀}$ es $\{2,4\}$ y la de ${\mathrm{g}}^{𝐀}$ es $\{3,4\}$; el 1 no está en ninguna.
• El 2. $(\exists x_2(\mathrm{f}(x_2)\equiv x_1)\wedge \neg \exists x_2(\mathrm{g}(x_2)\equiv x_1))$: «$x_1$ es imagen de $\mathrm{f}$ y no de $\mathrm{g}$». Está en $\{2,4\}$ y no en $\{3,4\}$ sólo el 2.
• El 3. $(\exists x_2(\mathrm{g}(x_2)\equiv x_1)\wedge \neg \exists x_2(\mathrm{f}(x_2)\equiv x_1))$: «$x_1$ es imagen de $\mathrm{g}$ y no de $\mathrm{f}$». Está en $\{3,4\}$ y no en $\{2,4\}$ sólo el 3.

No hay elementos no definibles. Cada elemento tiene una fórmula que lo define, así que el criterio NoDefinible no tiene a quién descartar. En particular, el cambio de 2 con 3 que sugiere el dibujo no es un isomorfismo: si $F$ cambia 2 con 3 y deja fijos 1 y 4, entonces $F({\mathrm{f}}^{𝐀}(1))=F(2)=3$ y ${\mathrm{f}}^{𝐀}(F(1))={\mathrm{f}}^{𝐀}(1)=2$, y $F$ no cumple la condición (2) de homomorfismo.

No hace falta para la respuesta, pero cierra el cuadro: como un isomorfismo deja fijo a todo elemento definible (el Ejercicio 36 de la guía), y acá lo son los cuatro, la identidad es el único isomorfismo de $𝐀$ en $𝐀$.

05 · Lo que hace perder puntos

Fiarse del dibujo. «El 2 y el 3 son simétricos, así que no son definibles» es falso, y además NoDefinible no se aplica sin un isomorfismo verificado. El reflejo del dibujo cambia $\mathrm{f}$ por $\mathrm{g}$, y eso no es mover elementos: es cambiar el lenguaje.

Nombrar números. $(\mathrm{f}(x_1)\equiv 2)$ no es una fórmula: el tipo no tiene nombres de constante, y 2 no es un término. Al 2 hay que describirlo.

Leer mal la dirección de las flechas. «Llega $\mathrm{f}$» es $\exists x_2(\mathrm{f}(x_2)\equiv x_1)$: $x_1$ es la punta de la flecha, no la cola. $(\mathrm{f}(x_1)\equiv \mathrm{g}(x_1))$, que habla de adónde va $x_1$, lo cumplen 2, 3 y 4.

Verificar la (2) sólo para f, o sólo en algunos puntos. Para afirmar que algo es isomorfismo hay que revisar $\mathrm{f}$ y $\mathrm{g}$ en los cuatro elementos; para afirmar que no lo es alcanza un testigo, y hay que escribirlo con números.

Los otros dos ejercicios del grupo: el Ejercicio 18, donde sí hay un isomorfismo que mueve algo, y el Ejercicio 19, con una relación en lugar de funciones. Sin relaciones, un homomorfismo biyectivo ya es isomorfismo: es el Ejercicio 16.

Para tener a mano

1. 4: punto fijo de $\mathrm{f}$. 1: no le llega nadie. 2: le llega $\mathrm{f}$ y no $\mathrm{g}$. 3: le llega $\mathrm{g}$ y no $\mathrm{f}$.
2. Cambiar 2 con 3 no es isomorfismo: $F(\mathrm{f}(1))=F(2)=3$ pero $\mathrm{f}(F(1))=\mathrm{f}(1)=2$.
3. Un isomorfismo mueve las flechas con su rótulo. El espejo del dibujo cambia $\mathrm{f}$ por $\mathrm{g}$, y eso no vale.
4. Todos definibles: NoDefinible no descarta a nadie, y el único isomorfismo es la identidad.