El átomo no se parte en un supremo

El enunciado, textual: «Sea $\tau =(\{0,\mathrm{ato}\},\{s,i\},\{\le \},\{(s,2),(i,2),(\le ,2)\})$ y sea $\Sigma$ formado por los axiomas de elementales de reticulados cuaterna junto con las sentencias elementales de tipo $\tau$:

$$\forall x\le (0,x)$$ $$\neg (\mathrm{ato}=0)$$ $$\forall x(\le (x,\mathrm{ato})\to (x=0\vee x=\mathrm{ato}))$$

(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\forall y(\mathrm{ato}=s(x,y)\to x=\mathrm{ato}\vee y=\mathrm{ato})$$

en $(\Sigma ,\tau )$». Son dos trabajos de naturaleza distinta. El (a) se contesta en castellano, mirando los modelos desde afuera. El (b) es una prueba elemental, y adentro de ella no se puede citar nada de lo que se dijo en el (a).

01 · Antes de resolver: qué hay en el tipo y qué piden

Dos nombres de constante, y nada más. El tipo trae 0 y ato. Son nombres: un modelo elige qué elemento nombra cada uno. Que el elemento que se llama 0 esté abajo de todo no lo dice el nombre, lo dice el primer axioma de la lista. Y no hay ningún 1: el tipo no tiene cómo hablar de un máximo.

«Esencialmente» tiene un sentido preciso. Es el de la Guía 8: un modelo es un par $(A,i)$, con $i$ la función que interpreta cada símbolo del tipo, y a nivel de información es lo mismo que la 6-upla

$$(A,i(s),i(i),i(\le ),i(0),i(\mathrm{ato}))$$

Contestar el (a) es decir qué 6-uplas aparecen así. Ojo con la letra repetida: en la Guía 8 la $i$ del par es la interpretación, y la $i$ del tipo es el nombre del ínfimo. De acá en adelante, para no cruzarlas, se dice «$\mathrm{ato}$ se interpreta como $b$» en vez de escribir la interpretación.

Lo que hay que entregar en el (b) es una prueba elemental en $(\Sigma ,\tau )$: se parte de un modelo fijo pero arbitrario, del que sólo se sabe que hace verdaderas las sentencias de $\Sigma$, y cada paso cita una de ellas o es una deducción simple. La lista deja escribir $x\le y$ en lugar de $\le (x,y)$, y eso se usa abajo; el supremo queda prefijo, $s(x,y)$, como en el enunciado.

Una errata para no tropezar. «Los axiomas de elementales de reticulados cuaterna» son los siete de la teoría elemental de reticulados cuaterna de la Guía 8, la que tiene a A≤R, A≤T, A≤A, AsesC, As≤C, AiesC y Ai≥C. Con los tres de arriba, $\Sigma$ tiene diez sentencias.

02 · Las herramientas

De los siete axiomas de reticulados cuaterna, la prueba del (b) usa cuatro. Escritos con la abreviatura de la lista para $\le$ y con el supremo prefijo:

• 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)$.

Y las tres sentencias nuevas. La guía no les pone nombre; acá van numeradas en el orden del enunciado:

• Σ₁: $\forall x0\le x$. Lo que se llama $0$ está debajo de todo.
• Σ₂: $\neg (\mathrm{ato}=0)$. Los dos nombres no nombran lo mismo.
• Σ₃: $\forall x(x\le \mathrm{ato}\to (x=0\vee x=\mathrm{ato}))$. Debajo de $\mathrm{ato}$ hay dos cosas como mucho: el $0$ y él mismo.

Una palabra que va a aparecer: un átomo de un reticulado con mínimo es un elemento que cubre al mínimo, o sea que está arriba de él sin nada en el medio.

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

Se lee $\Sigma$ sentencia por sentencia, preguntando qué le exige cada una a un modelo $(A,i)$.

• Los siete de reticulado cuaterna. Por el teorema de la Guía 6 que los caracteriza, dicen que $\le$ se interpreta como un orden parcial sobre $A$ en el que todo par tiene supremo e ínfimo, y que $s$ e $i$ se interpretan como ese supremo y ese ínfimo. O sea: $A$ es un reticulado.
• Σ₁: 0 se interpreta como el mínimo del reticulado.
• Σ₂: ato se interpreta como algo que no es el mínimo.
• Σ₃: lo único que está debajo de ato es el mínimo y ato mismo.

Las tres últimas juntas dicen que $\mathrm{ato}$ es un átomo. Por Σ₁, $0\le \mathrm{ato}$, y por Σ₂ son distintos: $0<\mathrm{ato}$. Si hubiera un $z$ con $0<z<\mathrm{ato}$, Σ₃ diría que $z=0$ o $z=\mathrm{ato}$, y las dos contradicen las desigualdades estrictas. No hay nada en el medio. Y al revés: si $0$ es el mínimo y $\mathrm{ato}$ lo cubre, las tres se cumplen, porque todo $x\le \mathrm{ato}$ cumple $0\le x\le \mathrm{ato}$, y si no fuera ninguna de las dos puntas estaría estrictamente en el medio.

La respuesta del (a): los modelos de $(\Sigma ,\tau )$ son, esencialmente, los reticulados con mínimo en los que se señaló un átomo: las 6-uplas $(L,s,i,\le ,0,\mathrm{ato})$ tales que $(L,s,i,\le )$ es un reticulado cuaterna, $0$ es su mínimo y $\mathrm{ato}$ cubre a $0$. En un dibujo: el mínimo abajo, $\mathrm{ato}$ pegado arriba de él, y del resto, cualquier cosa con tal de que siga siendo reticulado.

Y nada más que eso, que es donde se pierden puntos por decir de más:

• No tiene por qué haber máximo. El tipo no tiene cómo pedirlo. El conjunto $\omega$ con el orden usual, el máximo como supremo y el mínimo como ínfimo, con la constante $0$ nombrando al número cero y $\mathrm{ato}$ nombrando al uno, es un modelo sin elemento más grande. En un modelo finito el máximo aparece siempre, pero por ser finito, no por $\Sigma$.
• ato no tiene por qué ser el único átomo. Σ₃ mira sólo lo que está debajo de ato, no lo que está al lado. En el rombo, ato puede ser cualquiera de los dos del medio, y el otro es otro átomo. En el lenguaje de la Guía 2, ato cubre al mínimo, pero no tiene por qué taparlo.
• No tiene por qué ser distributivo. El diamante, con ato en cualquiera de sus tres átomos, es un modelo. Y sin 1 en el tipo, ni siquiera tiene sentido preguntar por complementos.

Contado sobre todos los reticulados de hasta siete elementos —78, uno por cada forma posible— y con cada una de las 3308 maneras de interpretar $0$ y $\mathrm{ato}$ en ellos: evaluando las diez sentencias de $\Sigma$ con la definición de verdad, las interpretaciones que las hacen verdaderas son exactamente las que ponen $0$ en el mínimo y $\mathrm{ato}$ en un átomo, sin una sola excepción. Los modelos que salen, por tamaño:

Con un elemento no hay modelos, porque Σ₂ pide dos elementos distintos. El más chico es la cadena de dos, con 0 abajo y ato arriba. Y la columna de los modelos le gana a la de los reticulados porque un mismo reticulado da tantos modelos como átomos distintos tenga: de los 77 reticulados con más de un elemento, 52 tienen más de uno.

En el rombo, con $\mathrm{ato}$ arriba de todo, Σ₃ falla porque debajo hay cuatro elementos, y la sentencia del (b) falla con ella: $s(b,c)=d$ y ninguno de los dos es $d$. Bajalo a $b$ o a $c$ y las dos se arreglan juntas. En la cadena hay un solo lugar posible, en el diamante tres, en el pentágono dos —$b$ y $d$— y en la grilla de seis, dos. Y si movés el $0$ fuera del mínimo, Σ₁ se cae con el primer elemento que no queda arriba de él.

Hay un caso que conviene buscar: el pentágono con $\mathrm{ato}$ en $c$. Σ₃ falla —$b\le c$ y $b$ no es ninguna de las dos puntas—, pero la sentencia del (b) vale igual, porque ningún par de elementos distintos de $c$ tiene supremo $c$. La sentencia del (b) es una consecuencia de $\Sigma$, no una definición de sus modelos: vale en todos ellos y también en algunos que no lo son.

04 · (b) La mariposa: debajo de ato hay dos cosas

La sentencia dice que ato no es el supremo de dos elementos distintos de él. Leída con el dibujo del (a), es casi obvia: un supremo queda arriba de lo que junta, y debajo de un átomo no hay casi nada. La mariposa es convertir ese «casi nada» en pasos citables.

De atrás para adelante. La conclusión es una disyunción, $a=\mathrm{ato}\vee b=\mathrm{ato}$. De las diez sentencias de $\Sigma$, la única que entrega una disyunción es Σ₃, y la entrega para algo que está debajo de $\mathrm{ato}$. Así que la pregunta es si $a$ y $b$ están debajo de $\mathrm{ato}$. Lo están: $\mathrm{ato}=s(a,b)$, y un supremo es cota superior. Eso es AsesC.

Los casos. Con Σ₃ aplicado a los dos, cada uno es $0$ o $\mathrm{ato}$. Son cuatro combinaciones, y en tres de ellas alguno es $\mathrm{ato}$, que es lo que se quería. Queda la cuarta: $a=0$ y $b=0$. Ahí $\mathrm{ato}=s(0,0)$, y el supremo de $0$ consigo mismo es $0$, así que $\mathrm{ato}$ sería $0$.

Y acá hay dos salidas. La que se ve primero es decir que eso contradice Σ₂, así que el caso no ocurre. La otra es más barata: si $\mathrm{ato}=0$ y $a=0$, entonces $a=\mathrm{ato}$, que ya es la conclusión. Las dos son correctas. La segunda deja ver algo que la primera esconde: para el (b), Σ₂ no hace falta.

Falta un detalle. Que $s(0,0)=0$ es la idempotencia, y la idempotencia no es uno de los siete axiomas: citarla como resultado de la Guía 6 obliga a enunciarla y probarla aparte. No hace falta entera. Alcanza con $s(0,0)\le 0$, que sale de As≤C con las tres variables en $0$, y con $0\le \mathrm{ato}$, que ya está: es $a\le \mathrm{ato}$ con $a=0$.

05 · El escarabajo: la prueba escrita

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

$$\mathrm{ato}=s(a,b)$$

Queremos probar $a=\mathrm{ato}\vee b=\mathrm{ato}$.

Paso 1: los dos están debajo de $\mathrm{ato}$. El axioma AsesC, tomando $x$ como $a$ e $y$ como $b$, nos dice que $a\le s(a,b)$ y $b\le s(a,b)$. Reemplazando $s(a,b)$ por $\mathrm{ato}$, que es lo que dice el supuesto, obtenemos $a\le \mathrm{ato}$ y $b\le \mathrm{ato}$.

Paso 2: cada uno es $0$ o $\mathrm{ato}$. El axioma Σ₃, tomando $x$ como $a$, nos dice que $a\le \mathrm{ato}\to (a=0\vee a=\mathrm{ato})$; como $a\le \mathrm{ato}$ por el Paso 1, obtenemos $a=0\vee a=\mathrm{ato}$. El axioma Σ₃, tomando $x$ como $b$, nos dice que $b\le \mathrm{ato}\to (b=0\vee b=\mathrm{ato})$; como $b\le \mathrm{ato}$ por el Paso 1, obtenemos $b=0\vee b=\mathrm{ato}$.

Paso 3: los casos. Si $a=\mathrm{ato}$, la conclusión vale. Si $b=\mathrm{ato}$, también. Si no pasa ninguna de las dos cosas, por las dos disyunciones del Paso 2 tiene que ser $a=0$ y $b=0$. Los tres casos agotan todas las posibilidades, y falta sólo el último.

Paso 4: el caso $a=0$ y $b=0$. El axioma A≤R, tomando $x$ como $0$, nos dice que $0\le 0$. El axioma As≤C, tomando $x$, $y$ y $z$ como $0$, nos dice que $(0\le 0\wedge 0\le 0)\to s(0,0)\le 0$, con lo cual $s(0,0)\le 0$. Como $\mathrm{ato}=s(a,b)$ y $a=b=0$, tenemos $\mathrm{ato}=s(0,0)$, y entonces $\mathrm{ato}\le 0$. Por otro lado, el Paso 1 dio $a\le \mathrm{ato}$, y como $a=0$, $0\le \mathrm{ato}$. El axioma A≤A, tomando $x$ como $\mathrm{ato}$ e $y$ como $0$, nos dice que $(\mathrm{ato}\le 0\wedge 0\le \mathrm{ato})\to \mathrm{ato}=0$, con lo cual $\mathrm{ato}=0$. Como $a=0$, resulta $a=\mathrm{ato}$, y la conclusión también vale en este caso.

Cierre. En los tres casos vale $a=\mathrm{ato}\vee b=\mathrm{ato}$, así que vale la implicación $\mathrm{ato}=s(a,b)\to a=\mathrm{ato}\vee b=\mathrm{ato}$. Como $a$ y $b$ eran fijos pero arbitrarios, generalizando concluimos $\forall x\forall y(\mathrm{ato}=s(x,y)\to x=\mathrm{ato}\vee y=\mathrm{ato})$. ∎

Si en el Paso 4 se prefiere la otra salida, se cambia la última oración: $\mathrm{ato}=0$ contradice el axioma Σ₂, así que ese caso no puede darse. Es igual de correcta y cita un axioma más.

06 · Qué axiomas hicieron falta

La prueba de arriba cita A≤R, A≤A, AsesC, As≤C y Σ₃. No cita Σ₁ ni Σ₂. Eso dice que la sentencia del (b) se deduce de los siete axiomas de reticulado y Σ₃ solos, aunque 0 no esté en el mínimo y aunque ato y 0 nombren lo mismo.

Se puede contrastar contra los mismos 78 reticulados de hasta siete elementos y las 3308 interpretaciones de antes. Σ₃ vale en 658 de ellas, y en 500 de esas 658 falla Σ₁ o Σ₂: no son modelos. La sentencia del (b) vale en las 658. En cambio, si se saca Σ₃ y se dejan las otras dos, quedan 422 interpretaciones y la sentencia falla en 95. La más chica es la de la simulación al arrancar: el rombo con ato arriba. El trabajo lo hace Σ₃, y los otros dos axiomas nuevos están para el (a): sin ellos ato no sería un átomo.

07 · Lo que se lleva a otros ejercicios

Leer la teoría antes de describirla. Para el (a) de cualquier ejercicio así, la receta es la misma: los axiomas conocidos se traducen de una («es un reticulado»), y los nuevos se leen uno por uno, preguntando qué le exigen a la interpretación de cada nombre. Después se juntan, y casi siempre dicen una sola cosa con nombre propio: acá, «átomo». En el Ejercicio 25 el mismo método da otra palabra, tapar, y otra forma del dibujo.

Una disyunción en el consecuente de un axioma es un razonamiento por casos esperando. Σ₃ no se usa para deducir una igualdad: se usa para abrir casos que agotan, y el trabajo es cerrar cada uno.

Lo que hace perder puntos. Usar en el (b) que «$\mathrm{ato}$ es un átomo» porque se dijo en el (a): eso es castellano sobre los modelos, no una sentencia de $\Sigma$, y no se cita. Escribir $s(0,0)=0$ sin probarlo: es un resultado de la guía, y la regla de la cátedra pide enunciarlo y probarlo por separado. Despachar el caso de $b$ con «análogamente»: en una prueba elemental, cada instanciación se escribe. Y en el (a), decir «reticulado acotado» o «el único átomo»: las dos son falsas en algún modelo.

Para tener a mano

1. Los modelos son, esencialmente, reticulados con mínimo en los que se señaló un átomo: 0 es el mínimo y ato lo cubre.
2. No hay máximo obligatorio, ato no tiene por qué ser el único átomo, y arriba puede haber cualquier reticulado.
3. La prueba del (b): AsesC pone $a$ y $b$ debajo de $\mathrm{ato}$, Σ₃ abre los casos, y el caso $a=b=0$ se cierra con $s(0,0)\le 0$ y antisimetría.
4. Ese último caso no hace falta descartarlo con Σ₂: si $\mathrm{ato}=0=a$, ya es la conclusión.
5. Medido sobre los reticulados de hasta siete elementos: la sentencia del (b) vale siempre que valga Σ₃, y sin Σ₃ falla en 95 de 422 interpretaciones.