Con un átomo debajo de todo, sólo 0 y 1 tienen complemento

El enunciado, textual: «Sea

$$\tau =(\{0,1,\mathrm{mono}\},\{s,i\},\{\le \},\{(s,2),(i,2),(\le ,2)\})$$

y sea $\Sigma$ formado por los axiomas de la teoría elemental de reticulados cuaterna junto con los axiomas:

$$\forall x\le (x,1)$$ $$\forall x\le (0,x)$$ $$\neg (\mathrm{mono}=0)$$ $$\forall x(\neg (x=0)\to \le (\mathrm{mono},x))$$

(a) Diga en forma hablada o mediante un grafico que son "esencialmente" los modelos de $(\Sigma ,\tau )$. (b) De una prueba elemental de

$$\forall x(\exists z(i(x,z)=0\wedge s(x,z)=1)\to (x=0\vee x=1))$$

en $(\Sigma ,\tau )$». Es el mismo armado que el Ejercicio 24, con un axioma sobre la constante nueva que pide mucho más. Se nota en los dos incisos: el dibujo de los modelos se vuelve rígido, y la prueba ya no abre casos sobre lo que está debajo sino sobre lo que está arriba.

01 · Antes de resolver: qué dice la sentencia del (b)

Tres nombres de constante. El tipo trae 0, 1 y mono, y un modelo elige qué elemento nombra cada uno. Que 0 nombre el mínimo y 1 el máximo lo dicen dos axiomas, no los nombres. Y nada impide que dos nombres nombren el mismo elemento: mono y 1 pueden coincidir.

El antecedente es «tener complemento». Que exista un $z$ con $i(x,z)=0$ y $s(x,z)=1$ es, palabra por palabra, que $z$ sea un complemento de $x$. La sentencia dice entonces que los únicos elementos con complemento son $0$ y $1$. Leída así, antes de escribir nada, ya se sabe qué se va a probar y se puede ir a buscar el dibujo que lo explica.

Lo que hay que entregar. El (a) es castellano sobre los modelos, en el sentido de la Guía 8: un modelo $(A,i)$ es, a nivel de información, la 7-upla $(A,i(s),i(i),i(\le ),i(0),i(1),i(\mathrm{mono}))$, y hay que decir cuáles aparecen. Para no cruzar la $i$ de la interpretación con el ínfimo, de acá en adelante se dice «$\mathrm{mono}$ nombra a $b$». El (b) es una prueba elemental en $(\Sigma ,\tau )$: un modelo fijo pero arbitrario, y sólo se citan sentencias de $\Sigma$. Se escribe $x\le y$ por $\le (x,y)$, como permite la lista, y el supremo y el ínfimo quedan prefijos, como en el enunciado.

La trampa del existencial. Está en el antecedente, así que en la prueba se lo usa: se le pone nombre a un complemento que existe. Ese nombre es un testigo, no un elemento arbitrario, y sobre él no se generaliza.

02 · Las herramientas

De los siete axiomas de reticulados cuaterna, la prueba del (b) usa cinco:

• A≤R, reflexiva: $\forall xx\le x$.
• A≤A, antisimétrica: $\forall x\forall y((x\le y\wedge y\le x)\to x=y)$.
• AsesC, el supremo es cota superior: $\forall x\forall y(x\le s(x,y)\wedge y\le s(x,y))$.
• As≤C, el supremo está debajo de toda cota superior: $\forall x\forall y\forall z((x\le z\wedge y\le z)\to s(x,y)\le z)$.
• Ai≥C, el ínfimo está encima de toda cota inferior: $\forall x\forall y\forall z((z\le x\wedge z\le y)\to z\le i(x,y))$.

Y los cuatro nuevos, numerados en el orden del enunciado:

• Σ₁: $\forall xx\le 1$. Lo que se llama $1$ está arriba de todo.
• Σ₂: $\forall x0\le x$. Lo que se llama $0$ está debajo de todo.
• Σ₃: $\neg (\mathrm{mono}=0)$.
• Σ₄: $\forall x(\neg (x=0)\to \mathrm{mono}\le x)$. $\mathrm{mono}$ está debajo de todo lo que no es $0$.

03 · (a) Qué son, esencialmente, los modelos

Sentencia por sentencia. Los siete de reticulado cuaterna dicen, por el teorema de la Guía 6 que los caracteriza, que $A$ es un reticulado con $s$ e $i$ como supremo e ínfimo. Σ₁ y Σ₂ dicen que es acotado, con $1$ en el máximo y $0$ en el mínimo. Y Σ₃ con Σ₄ dicen algo de $\mathrm{mono}$ que tiene nombre: $\mathrm{mono}$ tapa al $0$, o sea que está estrictamente arriba de él y debajo de todo lo que está estrictamente arriba de él.

La cuenta es corta. Por Σ₂, $0\le \mathrm{mono}$, y por Σ₃ son distintos: $0<\mathrm{mono}$. Si $0<c$, entonces $c$ no es $0$ y Σ₄ da $\mathrm{mono}\le c$. Al revés, si $0$ es el mínimo y $\mathrm{mono}$ lo tapa, todo $x$ distinto de $0$ cumple $0<x$ y por eso $\mathrm{mono}\le x$: Σ₄ vale. Tapar es más que cubrir: $\mathrm{mono}$ es un átomo, y es el único.

La forma del dibujo. Sacándole el $0$ al modelo queda $L^{\prime }=A\setminus \{0\}$, y eso es un reticulado acotado por derecho propio:

• No es vacío: tiene a mono, por Σ₃.
• Es cerrado por supremos: si $x$ e $y$ no son $0$ y $s(x,y)=0$, de $x\le s(x,y)$ saldría $x\le 0$, y $x=0$.
• Es cerrado por ínfimos: si $x$ e $y$ no son $0$, $\mathrm{mono}$ está debajo de los dos y por eso debajo de $i(x,y)$; si $i(x,y)$ fuera $0$, $\mathrm{mono}$ sería $0$.
• Tiene a $1$: si fuera $1=0$, todo elemento estaría debajo de $0$, el reticulado tendría un solo punto y $\mathrm{mono}$ sería $0$.

Su mínimo es mono y su máximo es 1. Y la vuelta también vale: a cualquier reticulado acotado se le puede pegar un elemento nuevo debajo de todo, los supremos y los ínfimos de adentro no cambian, y lo que queda es un modelo, con 0 en el elemento nuevo, mono en el mínimo viejo y 1 en el máximo.

La respuesta del (a): los modelos de $(\Sigma ,\tau )$ son, esencialmente, los reticulados acotados a los que se les pegó un cero nuevo por debajo. En un dibujo: el $0$ abajo, una sola arista que sube hasta $\mathrm{mono}$, y de $\mathrm{mono}$ para arriba, hasta el $1$, un reticulado acotado cualquiera. Todo camino que sube desde el $0$ pasa por $\mathrm{mono}$.

El más chico es la cadena de dos, y ahí mono y 1 nombran el mismo elemento: el reticulado de arriba tiene un solo punto. Es el único modelo de hasta siete elementos donde pasa eso.

Contado sobre los 78 reticulados de hasta siete elementos, con cada una de las 22 208 maneras de interpretar $0$, $1$ y $\mathrm{mono}$: evaluando las once sentencias de $\Sigma$ con la definición de verdad, son modelo exactamente las interpretaciones con $0$ en el mínimo, $1$ en el máximo y $\mathrm{mono}$ tapando al $0$. Y la descripción de arriba se puede poner a prueba con un número: si un modelo de $n$ elementos es un reticulado acotado de $n-1$ con un cero pegado, tiene que haber tantos modelos de $n$ elementos como reticulados de $n-1$.

Las dos columnas de modelos salen de evaluar $\Sigma$ en reticulados de $n$ elementos; las otras dos, de contar reticulados de $n-1$, sin ninguna constante. Coinciden fila por fila. El factor $n$ de la última es elegir cuál de los $n$ elementos del universo es el cero pegado.

En el rombo no hay lugar para $\mathrm{mono}$: en $b$ no queda debajo de $c$, en $c$ no queda debajo de $b$, y más arriba tampoco. Ningún reticulado con dos átomos tiene modelos. Y ahí $b$ y $c$ son complemento uno del otro, así que la sentencia del (b) falla. En el rombo con un cuello, el lugar es uno solo, $b$, y entonces los únicos elementos con complemento son $a$ y $e$: el $0$ y el $1$. Lo mismo en el diamante con un cuello, que sin el cuello tenía cada uno de sus tres átomos con dos complementos.

04 · (b) La mariposa: dos no nulos se cruzan en mono

El dibujo lo dice todo. Si $a$ no es $0$ y su complemento $c$ tampoco, los dos están arriba de $\mathrm{mono}$. Entonces $\mathrm{mono}$ es cota inferior de los dos, queda debajo de $i(a,c)$, y ese ínfimo no puede ser $0$. Un complemento de algo no nulo tiene que ser el $0$. Y si $c=0$, $s(a,0)$ es $a$, que tendría que ser $1$.

De atrás para adelante. La conclusión es $a=0\vee a=1$, y ningún axioma la entrega hecha. Lo natural es partir en dos casos: o $a=0$, y no hay nada que hacer, o no, y entonces la meta es $a=1$. Una igualdad entre elementos sale de A≤A, así que hacen falta $a\le 1$ y $1\le a$. La primera es gratis, porque $1=s(a,c)$ y AsesC da $a\le s(a,c)$. La segunda es $s(a,c)\le a$, y As≤C la parte en $a\le a$ y $c\le a$. Esa última es la difícil, y sale si $c=0$: se la pide Σ₂.

Y $c=0$ sale por el absurdo, con el dibujo de arriba: si $c$ no fuera $0$, Σ₄ pone a $\mathrm{mono}$ debajo de $a$ y de $c$, Ai≥C lo pone debajo de $i(a,c)$, que es $0$, y con Σ₂ y antisimetría $\mathrm{mono}$ sería $0$, contra Σ₃.

Hay un detalle que conviene notar antes de escribir: $a\le 1$ sale de AsesC, no de Σ₁. Con eso, la prueba entera no usa que $1$ sea el máximo.

05 · El escarabajo: la prueba escrita

Prueba. Sea $𝐀=(A,i)$ un modelo de $(\Sigma ,\tau )$ fijo pero arbitrario. Sea $a\in A$ fijo pero arbitrario, y supongamos

$$\exists z(i(a,z)=0\wedge s(a,z)=1)$$

Sea $c$ un elemento tal que $i(a,c)=0$ y $s(a,c)=1$; el nombre $c$ es nuevo. Queremos probar $a=0\vee a=1$, y separamos dos casos, que agotan las posibilidades: $a=0$ o $\neg (a=0)$.

Caso $a=0$. Vale $a=0\vee a=1$.

Caso $\neg (a=0)$. Paso 1: $c=0$. Supongamos, para llegar a un absurdo, que $\neg (c=0)$. El axioma Σ₄, tomando $x$ como $a$, nos dice que $\neg (a=0)\to \mathrm{mono}\le a$; como $\neg (a=0)$, obtenemos $\mathrm{mono}\le a$. El axioma Σ₄, tomando $x$ como $c$, nos dice que $\neg (c=0)\to \mathrm{mono}\le c$; como $\neg (c=0)$, obtenemos $\mathrm{mono}\le c$. El axioma Ai≥C, tomando $x$ como $a$, $y$ como $c$ y $z$ como $\mathrm{mono}$, nos dice que $(\mathrm{mono}\le a\wedge \mathrm{mono}\le c)\to \mathrm{mono}\le i(a,c)$, con lo cual $\mathrm{mono}\le i(a,c)$; como $i(a,c)=0$, resulta $\mathrm{mono}\le 0$. El axioma Σ₂, tomando $x$ como $\mathrm{mono}$, nos dice que $0\le \mathrm{mono}$. El axioma A≤A, tomando $x$ como $\mathrm{mono}$ e $y$ como $0$, nos dice que $(\mathrm{mono}\le 0\wedge 0\le \mathrm{mono})\to \mathrm{mono}=0$, con lo cual $\mathrm{mono}=0$, que contradice el axioma Σ₃. Luego $c=0$.

Paso 2: $1\le a$. El axioma A≤R, tomando $x$ como $a$, nos dice que $a\le a$. El axioma Σ₂, tomando $x$ como $a$, nos dice que $0\le a$, y como $c=0$, $c\le a$. El axioma As≤C, tomando $x$ como $a$, $y$ como $c$ y $z$ como $a$, nos dice que $(a\le a\wedge c\le a)\to s(a,c)\le a$, con lo cual $s(a,c)\le a$; como $s(a,c)=1$, resulta $1\le a$.

Paso 3: $a\le 1$ y $a=1$. El axioma AsesC, tomando $x$ como $a$ e $y$ como $c$, nos dice que $a\le s(a,c)$ y $c\le s(a,c)$; del primer conjunto y $s(a,c)=1$, $a\le 1$. El axioma A≤A, tomando $x$ como $a$ e $y$ como $1$, nos dice que $(a\le 1\wedge 1\le a)\to a=1$, con lo cual $a=1$, y vale $a=0\vee a=1$.

Cierre. En los dos casos vale $a=0\vee a=1$. Esa conclusión no menciona a $c$, así que vale a partir de la sola hipótesis $\exists z(i(a,z)=0\wedge s(a,z)=1)$, y tenemos la implicación. Como $a$ era fijo pero arbitrario, generalizando concluimos

$$\forall x(\exists z(i(x,z)=0\wedge s(x,z)=1)\to (x=0\vee x=1))$$

como queríamos. ∎

06 · Qué axiomas hicieron falta

La prueba cita A≤R, A≤A, AsesC, As≤C, Ai≥C, Σ₂, Σ₃ y Σ₄. No cita Σ₁: que $1$ sea el máximo no se usa. Cualquier elemento que se llame $1$ sirve, porque lo único que se necesita de él es que sea un supremo, $s(a,c)$, y eso lo trae la hipótesis.

Contrastado contra los 78 reticulados de hasta siete elementos y las 22 208 interpretaciones de las tres constantes, sacando un axioma nuevo por vez y dejando los otros tres:

Sin Σ₄, el ejemplo más chico es el rombo con $\mathrm{mono}$ en $b$: $b$ y $c$ se complementan. Sin Σ₃, $\mathrm{mono}$ puede nombrar al $0$ y Σ₄ no exige nada: el rombo otra vez. Sin Σ₂, el $0$ puede nombrar al cuello: en el rombo con un cuello, con $0$ en $b$, $\mathrm{mono}$ en $a$ y $1$ en $e$, $i(c,d)$ es lo que se llama $0$ y $s(c,d)$ lo que se llama $1$. Se puede armar en la simulación de arriba.

07 · Lo que se lleva a otros ejercicios

Cubrir y tapar, en una teoría. El Ejercicio 24 pide que la constante no tenga nada en el medio por debajo; éste, que esté debajo de todo lo que no es 0. Es la diferencia entre cubrir y tapar, y en los modelos es enorme: allá, arriba del átomo puede haber cualquier cosa y puede haber otros átomos; acá, el dibujo entero cuelga de mono. La sentencia que se prueba cambia en consecuencia: allá era sobre lo que está debajo de ato, acá sobre dos elementos que están arriba de mono.

Para probar que algo no tiene complemento, mirá el ínfimo. Dos elementos con una cota inferior común distinta de 0 no se pueden complementar. Es la misma idea que dice que en una cadena sólo los extremos tienen complemento.

Lo que hace perder puntos. Usar en el (b) que «$\mathrm{mono}$ es el único átomo» o «el reticulado es un cero pegado a otro»: es la descripción del (a), castellano sobre los modelos, no sentencias de $\Sigma$. Usar $s(a,0)=a$ sin probarlo: es un resultado de la guía, y la regla de la cátedra pide enunciarlo y probarlo por separado; arriba se esquiva probando sólo la desigualdad que hace falta. Generalizar sobre el testigo $c$. Y en el (a), olvidarse de que $\mathrm{mono}$ puede ser $1$, o decir que los modelos son «los reticulados con un único átomo» sin pedir que el átomo esté debajo de todo: en un reticulado infinito eso no alcanza.

Para tener a mano

1. El antecedente $\exists z(i(x,z)=0\wedge s(x,z)=1)$ es «$x$ tiene complemento». La sentencia dice que sólo $0$ y $1$ lo tienen.
2. Los modelos son, esencialmente, un reticulado acotado cualquiera con un cero nuevo pegado abajo; mono es su mínimo, tapa al 0 y es el único átomo.
3. Hay tantos modelos de $n$ elementos como reticulados de $n-1$: medido hasta siete.
4. La prueba: casos sobre $a=0$; si no, $c=0$ por el absurdo con Σ₄ y Ai≥C, y $a=1$ con As≤C, AsesC y antisimetría.
5. Σ₁ no se usa: $a\le 1$ sale de que $1$ es el supremo $s(a,c)$.