Elementos definibles

Una fórmula con una sola variable libre parte el universo en dos: los elementos que la cumplen y los que no. Un elemento es definible cuando alguna fórmula lo deja solo de su lado. Encontrar esa fórmula es describirlo por algo que tiene él y ningún otro; probar que no existe es otra cosa, y se hace con un isomorfismo que lo mueve.

01 · La definición

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]$. Es decir, $a$ es el único elemento de $A$ que cumple $𝐀\models \phi [a]$. Una fórmula $\phi \in F^{\tau }$ define a $a$ en $𝐀$ si cumple eso.

Dos cosas que la definición dice sin subrayar. La declaración $\phi {=}_d\phi (v)$ pide que las variables libres de $\phi$ estén entre $v$: si quedara otra libre, la verdad de $\phi$ dependería de un valor que nadie fijó. Y $\phi$ puede no tener ninguna libre, pero entonces es una sentencia, la cumplen todos o ninguno, y no define a nadie salvo en un universo de un elemento.

El ejemplo más chico es el Ejercicio 9 de la guía: $\tau =(\{\mathrm{un}\},\varnothing ,\varnothing ,\varnothing )$, $A=\{1,3\}$ y ${\mathrm{un}}^{𝐀}=3$. $(x_1\equiv \mathrm{un})$ la cumple sólo el 3, y $\neg (x_1\equiv \mathrm{un})$ sólo el 1. Los dos son definibles: el 3 por su nombre, y el 1 por no ser el 3.

02 · Cómo se arma la fórmula

Cada fórmula con $x_1$ libre recorta un subconjunto de $A$: los $a$ con $𝐀\models \phi [a]$. La conjunción corta la intersección, la negación el complemento, y los cuantificadores hablan de cómo se relaciona $x_1$ con los demás. Armar una fórmula que define a $a$ es llegar al conjunto $\{a\}$ con esas operaciones. El método, en tres pasos:

• Buscar un rasgo. Algo que $a$ tenga: un nombre de constante que lo nombra, un lugar extremo, a cuántos se relaciona, quién llega a él por una función.
• Ver quién más lo tiene. Se recorre $A$ elemento por elemento.
• Descartar a los intrusos con otro rasgo, unido por $\wedge$. Si un intruso no se deja descartar nunca, sospechar que no se puede: puede haber un isomorfismo que lo cambia con $a$.

Los rasgos que más rinden, con un ejemplo de los ejercicios de la lista:

• Un nombre. $(x_1\equiv \mathrm{iz})$: «$x_1$ es el que nombra $\mathrm{iz}$».
• Un extremo. $\forall x_2\mathrm{rel}(x_1,x_2)$: «$x_1$ se relaciona con todos». $\forall x_2\neg \mathrm{me}(x_1,x_2)$: «con nadie».
• Exactamente uno. No hay símbolo para eso: «a alguno» es $\exists x_2\mathrm{me}(x_1,x_2)$ y «a lo sumo uno» es $\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))$.
• Una cadena. $\exists x_2\exists x_3(\mathrm{me}(x_1,x_2)\wedge \mathrm{me}(x_2,x_3))$: «encima de $x_1$ hay dos pasos».
• Una imagen. $\exists x_2(\mathrm{f}(x_2)\equiv x_1)$: «a $x_1$ llega una flecha $\mathrm{f}$». Y un punto fijo, $(\mathrm{f}(x_1)\equiv x_1)$.

Toda variable que no sea $x_1$ va cuantificada. Y si la relación es reflexiva, lo estricto se escribe: «divide estrictamente» es $(\mathrm{rel}(a,b)\wedge \neg (a\equiv b))$, porque si no $\exists x_2\mathrm{rel}(x_2,x_1)$ la cumplen todos, con $x_2$ igual a $x_1$.

03 · Reusar lo ya armado: el reticulado de la guía

En una estructura grande las fórmulas crecen rápido, y la notación declaratoria permite armar una con otras. La Guía 11 lo muestra en las p. 5–6 sobre un reticulado de dieciséis elementos, con $\tau =(\varnothing ,\{{\mathrm{s}}^2,{\mathrm{i}}^2\},\varnothing ,a)$ y ${\mathrm{s}}^{𝐀}$, ${\mathrm{i}}^{𝐀}$ el supremo y el ínfimo del diagrama. Va abajo, en el widget.

El 15 es el máximo.

$${\phi }_{15}=\forall x_{200}(\mathrm{s}(x_1,x_{200})\equiv x_1)$$

«$x_1$ absorbe a todos con el supremo»: $\mathrm{s}(15,b)=15$ para cada $b$, y sólo el máximo hace eso. Se declara ${\phi }_{15}{=}_d{\phi }_{15}(x_1)$, y entonces ${\phi }_{15}(x_7)=\forall x_{200}(\mathrm{s}(x_7,x_{200})\equiv x_7)$ también define al 15, ahora con $x_7$ libre.

La trampa. ${\phi }_{15}(x_{200})=\forall x_{200}(\mathrm{s}(x_{200},x_{200})\equiv x_{200})$ no define al 15. La $x_{200}$ que entra queda atrapada por el $\forall x_{200}$ que la fórmula usaba de auxiliar, y lo que queda es una sentencia: «todo elemento es su propio supremo con sí mismo», verdadera en $𝐀$. La cumplen los dieciséis.

Cubrir. Para seguir hace falta «$x_1$ es cubierto por $x_2$»: $x_1$ está estrictamente abajo de $x_2$ y no hay nada entre los dos.

$$\mathrm{Cub}=(((\mathrm{s}(x_1,x_2)\equiv x_2)\wedge \neg (x_1\equiv x_2))\wedge \neg \exists x_{300}((((\mathrm{s}(x_1,x_{300})\equiv x_{300})\wedge \neg (x_1\equiv x_{300}))\wedge (\mathrm{s}(x_{300},x_2)\equiv x_2))\wedge \neg (x_{300}\equiv x_2)))$$

$\mathrm{Li}(\mathrm{Cub})=\{x_1,x_2\}$, y se declara $\mathrm{Cub}{=}_d\mathrm{Cub}(x_1,x_2)$. $\mathrm{Cub}(x_3,x_6)$ dice «$x_3$ es cubierto por $x_6$»; con $x_6$ valiendo 10, la cumplen el 8 y el 9. Pero $\mathrm{Cub}(x_3,x_{300})$ no dice «$x_3$ es cubierto por $x_{300}$»: adentro, $x_{300}$ es la variable del $\exists x_{300}$, el último conjunto pasa a ser $\neg (x_{300}\equiv x_{300})$, siempre falso, y la fórmula se reduce a «$x_3$ está estrictamente abajo de $x_{300}$». Con $x_{300}$ valiendo 10 la cumplen los diez elementos del 0 al 9.

El 13 es el único cubierto por el 15 que cubre a dos elementos distintos:

$${\phi }_{13}=(\exists x_{600}({\phi }_{15}(x_{600})\wedge \mathrm{Cub}(x_1,x_{600}))\wedge \exists x_{700}\exists x_{800}((\mathrm{Cub}(x_{700},x_1)\wedge \mathrm{Cub}(x_{800},x_1))\wedge \neg (x_{700}\equiv x_{800})))$$

La primera mitad, «$x_1$ es cubierto por el 15», la cumplen el 13 y el 14. La segunda, «$x_1$ cubre a dos distintos», saca al 14, que sólo cubre al 12. Las auxiliares $x_{600}$, $x_{700}$ y $x_{800}$ son nuevas: no son $x_1$ ni las variables que ${\phi }_{15}$ y $\mathrm{Cub}$ usan adentro, $x_{200}$ y $x_{300}$.

Los consejos de la guía, escritos. El 14 es el otro cubierto por el 15; el 12 es el ínfimo del 13 y el 14; el 11 es el otro cubierto por el 13:

$${\phi }_{14}=(\exists x_{600}({\phi }_{15}(x_{600})\wedge \mathrm{Cub}(x_1,x_{600}))\wedge \neg {\phi }_{13}(x_1))$$ $${\phi }_{12}=\exists x_{900}\exists x_{1000}(({\phi }_{13}(x_{900})\wedge {\phi }_{14}(x_{1000}))\wedge (\mathrm{i}(x_{900},x_{1000})\equiv x_1))$$ $${\phi }_{11}=(\exists x_{1100}({\phi }_{13}(x_{1100})\wedge \mathrm{Cub}(x_1,x_{1100}))\wedge \neg {\phi }_{12}(x_1))$$

Cada una se declara ${=}_d(x_1)$ y se reusa en la siguiente, siempre con una variable que no aparece en la fórmula que se reemplaza: ${\phi }_{13}(x_{900})$ y ${\phi }_{14}(x_{1000})$ cambian $x_1$ por variables que ni ${\phi }_{13}$ ni ${\phi }_{14}$ usan. Escritas enteras son palabras de cientos de símbolos; medidas en la estructura, cada una la cumple su elemento y nadie más.

04 · El criterio NoDefinible

Para probar que un elemento no es definible no sirve probar fórmulas: hay infinitas. La guía da un criterio (p. 7):

NoDefinible. 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 $𝐀$.

Un isomorfismo de $𝐀$ en $𝐀$ es una manera de mover los elementos sin que ningún símbolo del tipo lo note: biyectivo, homomorfismo —respeta constantes, conmuta con funciones, preserva relaciones— y con inversa homomorfismo (Guía 10, p. 11–12). Si uno de esos movimientos lleva $a$ a otro elemento, todo lo que se pueda decir de $a$ se dice igual de ese otro, y ninguna fórmula los separa. En el Ejercicio 18 de la lista, cambiar 5 con 7 es un isomorfismo, y por eso ninguno de los dos es definible.

La guía agrega, sin probarlo, que cuando el universo es finito el criterio es completo: si $a$ no es definible, hay un isomorfismo $F:𝐀\to 𝐀$ con $F(a)\ne a$. Así que en los ejercicios, con universos finitos, todo elemento cae de un lado: o tiene fórmula, o hay un isomorfismo que lo mueve.

05 · Por qué es correcto: el Ejercicio 36

Ejercicio 36 (Guía 11, p. 13). Si $𝐀$ es un modelo de tipo $\tau$ y $a\in A$ es definible en $𝐀$, entonces $F(a)=a$ para cada isomorfismo $F:𝐀\to 𝐀$. Como corolario, el criterio NoDefinible es correcto.

La prueba se apoya en un hecho: un isomorfismo no cambia ninguna verdad. Es el Ejercicio 35 de la guía (el Ejercicio 29 de la lista, con su prueba): si $F:𝐀\to 𝐁$ es un isomorfismo y $\phi {=}_d\phi (v_1,\dots ,v_n)\in F^{\tau }$, entonces

$$𝐀\models \phi [a_1,\dots ,a_n]\text{ sii }𝐁\models \phi [F(a_1),\dots ,F(a_n)]$$

para cada $a_1,\dots ,a_n\in A$.

Prueba. Sea $a\in A$ definible en $𝐀$, y sea $\phi {=}_d\phi (v)$ una fórmula que lo define: $𝐀\models \phi [a]$, y $𝐀⊭\phi [b]$ para cada $b\in A-\{a\}$. Sea $F:𝐀\to 𝐀$ un isomorfismo. Por el Ejercicio 35, con $𝐁=𝐀$, $n=1$ y $a_1=a$, $𝐀\models \phi [a]$ si y sólo si $𝐀\models \phi [F(a)]$. Como $𝐀\models \phi [a]$, se tiene $𝐀\models \phi [F(a)]$. Si fuera $F(a)\ne a$, $F(a)$ sería un elemento de $A-\{a\}$ que cumple $\phi$, contra lo que dice que $\phi$ define a $a$. Luego $F(a)=a$. ∎

Corolario: NoDefinible es correcto. Es la contrarrecíproca. Si $F(a)\ne a$ para algún isomorfismo $F:𝐀\to 𝐀$, entonces no vale «$F(a)=a$ para cada isomorfismo», y por el Ejercicio 36 $a$ no es definible.

Y una consecuencia que ahorra búsquedas: si todos los elementos son definibles, el único isomorfismo de $𝐀$ en $𝐀$ es la identidad. Pasa en los Ejercicios 19 y 20 de la lista.

06 · Los tres de la lista

Contados sobre todas las biyecciones de $A$ en $A$: 720 en el 18, 120 en el 19, 24 en el 20. En el 18, sin la constante $\mathrm{iz}$ habría seis isomorfismos, que permutan 2, 5 y 7, y el 2 tampoco sería definible.

Para tener a mano

1. $\phi$ define a $a$: $\phi {=}_d\phi (v)$, $𝐀\models \phi [a]$ y $𝐀⊭\phi [b]$ para todo $b\ne a$.
2. Se arma por rasgos: uno que $a$ tenga, y otros unidos por $\wedge$ hasta descartar a los intrusos. Toda auxiliar, cuantificada.
3. Al reusar una fórmula declarada, la variable que entra no puede ser una de sus auxiliares: ${\phi }_{15}(x_{200})$ es una sentencia.
4. NoDefinible: un isomorfismo que mueve a $a$ prueba que $a$ no es definible. En universos finitos vale la vuelta.
5. Por qué: un isomorfismo no cambia verdades (Ejercicio 35), así que $F(a)$ cumple lo mismo que $a$, y si sólo $a$ lo cumple, $F(a)=a$.