Cinco elementos con dos variables

El enunciado, textual: «De una sentencia elemental pura de reticulados acotados la cual sea verdadera en un reticulado acotado $(L,s,i,0,1)$ si y solo si el reticulado acotado $(\{1,3,5,15,30\},\mathrm{mcm},\mathrm{mcd},1,30)$ es isomorfo a un subreticulado acotado de $(L,s,i,0,1)$». Es el Ejercicio 8 de la Guía 7. Se entrega una sentencia y la justificación de que dice exactamente eso, en las dos direcciones.

01 · Antes de escribir: qué se pide de verdad

El lenguaje. Los términos de reticulados acotados son las variables, los nombres de elementos fijos, los numerales $0$ y $1$, y $(tsr)$, $(tir)$. La única fórmula atómica es $(t=r)$: el $\le$ no existe acá. Pura quiere decir sin nombres de elementos fijos; el $0$ y el $1$ sí se pueden usar, porque son símbolos del tipo. Y sentencia quiere decir sin variables libres: el valor de verdad lo decide el reticulado solo.

El reticulado del enunciado. Antes de usarlo hay que ver que es uno: que $\{1,3,5,15,30\}$ sea cerrado bajo $\mathrm{mcm}$ y $\mathrm{mcd}$. Lo es: los pares que no están uno debajo del otro son sólo el 3 y el 5, con $\mathrm{mcm}(3,5)=15$ y $\mathrm{mcd}(3,5)=1$; todos los demás pares son comparables por divisibilidad y su $\mathrm{mcm}$ y su $\mathrm{mcd}$ son uno de los dos. El orden es la divisibilidad: un rombo $1,3,5,15$ con una antena, el 30, encima del 15. El mínimo es 1 y el máximo 30.

«Subreticulado acotado». La Guía 5 pide cuatro cosas para que $(S,s^{\prime },i^{\prime },0^{\prime },1^{\prime })$ sea subreticulado acotado de $(L,s,i,0,1)$: $S\subseteq L$, $S$ cerrado bajo $s$ e $i$, las operaciones restringidas, y $0^{\prime }=0$ y $1^{\prime }=1$. Esa última es la trampa del ejercicio. Un rombo con antena que cuelga de un elemento que no es el $0$ de $L$ no cuenta, aunque como reticulado sea igual al del enunciado.

02 · Las herramientas

Los axiomas de reticulado acotado: las siete identidades de reticulado terna, con los nombres de la Guía 4 —(I1) $xsx=x$ y $xix=x$; (I2) $xsy=ysx$; (I3) $xiy=yix$; (I4) y (I5) las asociativas; (I6) $xs(xiy)=x$; (I7) $xi(xsy)=x$— más las dos de la Guía 5:

(I8) $0sx=x$ y (I9) $xs1=1$, para cada $x\in L$.

Las dos hablan de $s$. Las versiones con $i$ son teoremas, y como se van a usar, la regla de la cátedra obliga a probarlas acá:

• (T1) $0ix=0$. Por (I7) tomando $x$ como $0$ e $y$ como $x$, $0i(0sx)=0$; y por (I8), $0sx=x$. Reemplazando, $0ix=0$.
• (T2) $xi1=x$. Por (I7) tomando $y$ como $1$, $xi(xs1)=x$; y por (I9), $xs1=1$. Reemplazando, $xi1=x$.

Y la definición de isomorfismo de la Guía 5: un homomorfismo $F$ —que preserva $s$, $i$, $0$ y $1$— biyectivo y cuya inversa también es homomorfismo.

03 · La mariposa: qué hay que nombrar

Primera pregunta: ¿cuántos elementos hay que nombrar? El camino largo es nombrar los cinco con cinco variables, pedir que sean distintos de a pares —diez desigualdades— y copiar las dos tablas, veinticinco casillas cada una. Sale una sentencia correcta y enorme. Pero dos de los cinco ya tienen nombre: el subreticulado tiene el mismo $0$ y el mismo $1$ que $L$, y un isomorfismo manda mínimo en mínimo y máximo en máximo, así que la imagen del 1 es el $0$ y la del 30 es el $1$. Y el 15 es $\mathrm{mcm}(3,5)$: su imagen es $xsy$, no hace falta otra variable. Quedan dos: $x$, la imagen del 3, e $y$, la del 5.

Segunda pregunta: ¿qué casillas de la tabla dicen algo? Casi ninguna. Que $xs(xsy)=xsy$ o que $xi(xsy)=x$ salen de los axiomas en cualquier reticulado; pedirlas no agrega nada. Las únicas casillas que no son gratis son las del par 3, 5: $\mathrm{mcd}(3,5)=1$, que se vuelve $xiy=0$, y $\mathrm{mcm}(3,5)=15$, que ya está usado para nombrar al 15.

Tercera pregunta: ¿cuáles de las diez distinciones hay que pedir? Ésta es la que decide el largo. Con $xiy=0$ adentro, casi todas salen solas: si $x$ fuera igual a $y$, $xiy$ sería $x$, que entonces sería $0$; si $x$ fuera $1$, $xiy$ sería $y$; y así. Hay que pedir $x\ne 0$ e $y\ne 0$, que no se deducen de nada. Y queda una sola más: que $xsy$ no sea el $1$. Sin ella, $0$, $x$, $y$, $xsy$, $1$ pueden ser cuatro elementos y no cinco: es el rombo sin la antena.

Las cuatro cláusulas juntas: $x\ne 0$, $y\ne 0$, $xiy=0$ y $xsy\ne 1$. El widget deja prenderlas y apagarlas y mirar en qué reticulado cada versión dice algo falso.

Sin la antena, el rombo la hace verdadera: su 2 y su 3 son distintos de $0$ y tienen ínfimo $0$, pero su supremo es el $1$ y no queda lugar para el 30. Con «incomparables» en lugar de «ínfimo $0$», el que tiene una cola abajo la hace verdadera aunque el rombo que contiene cuelgue de un elemento que no es el $0$. Y sin $x\ne 0$ ni $y\ne 0$, cualquier reticulado con un elemento en el medio sirve: $x$ e $y$ en $0$.

Medido sobre todos los reticulados acotados de hasta ocho elementos, salvo isomorfismo —1, 1, 1, 2, 5, 15, 53 y 222, que son las cantidades conocidas—, la sentencia de cuatro cláusulas evaluada elemento por elemento coincide en los 300 con la búsqueda directa de un isomorfismo, hecha sin fórmulas. El del enunciado entra en 165 de ellos. Sin la antena la sentencia se equivoca en 56; con «incomparables» en lugar de «ínfimo $0$», en 49, y el primero aparece con seis elementos: es el de la cola abajo.

Trescientos acuerdos no son una prueba: es la advertencia del final de decilo con una fórmula, y un reticulado de nueve elementos podría romperla. Lo que la cierra para todo reticulado acotado es el argumento de la sección siguiente.

04 · El escarabajo: la sentencia y por qué dice lo pedido

La sentencia.

Con las abreviaturas de la lista: $x\ne 0$ es $\neg (x=0)$, y los paréntesis de las conjunciones se omiten porque no hay ambigüedad. Es elemental de reticulados acotados —usa $s$, $i$, $0$, $1$ y $=$—, es pura y no tiene variables libres. Sea $(L,s,i,0,1)$ un reticulado acotado.

Si hay un isomorfismo, $\phi$ es verdadera. Sea $G$ un isomorfismo de $(\{1,3,5,15,30\},\mathrm{mcm},\mathrm{mcd},1,30)$ en un subreticulado acotado $(S,s^{\prime },i^{\prime },0,1)$ de $L$; por definición de subreticulado acotado, su mínimo y su máximo son el $0$ y el $1$ de $L$, y $s^{\prime }$, $i^{\prime }$ son las restricciones de $s$ e $i$. Como $G$ es homomorfismo, $G(1)=0$ y $G(30)=1$. Tomemos $x$ como $G(3)$ e $y$ como $G(5)$.

• $G(3)\ne 0$: si no, $G(3)=G(1)$, y como $G$ es inyectiva, $3=1$. Igual $G(5)\ne 0$.
• $G(3)iG(5)=G(\mathrm{mcd}(3,5))=G(1)=0$, porque $G$ preserva el ínfimo e $i^{\prime }$ es la restricción de $i$.
• $G(3)sG(5)=G(\mathrm{mcm}(3,5))=G(15)$, y $G(15)\ne G(30)=1$ porque $G$ es inyectiva.

Las cuatro cláusulas son verdaderas con esa asignación, así que $\phi$ es verdadera en $L$.

Si $\phi$ es verdadera, hay un isomorfismo. Sean $a,b\in L$ testigos del $\exists x\exists y$: $a\ne 0$, $b\ne 0$, $aib=0$ y $asb\ne 1$. Llamemos $c=asb$ y $S=\{0,a,b,c,1\}$.

Paso 1: los cinco son distintos. Los diez pares, uno por uno:

• $a\ne 0$, $b\ne 0$ y $c\ne 1$ son hipótesis.
• $a\ne b$: si $a=b$, por (I1) $aib=aia=a$, y entonces $a=0$.
• $a\ne 1$: si $a=1$, por (I3) y (T2) $aib=1ib=bi1=b$, y entonces $b=0$. Igual $b\ne 1$, con (T2) directo: $ai1=a$.
• $c\ne 0$: si $asb=0$, por (I7) $a=ai(asb)=ai0$, y por (I3) y (T1) $ai0=0ia=0$.
• $c\ne a$: si $asb=a$, por (I7) y (I2) $b=bi(bsa)=bi(asb)=bia$, y por (I3) $bia=aib=0$.
• $c\ne b$: si $asb=b$, por (I7) $a=ai(asb)=aib=0$.
• $0\ne 1$: si $0=1$, por (T2), (I3) y (T1) $a=ai1=ai0=0ia=0$.

Paso 2: $S$ es cerrado. Tiene al $0$ y al $1$. Para cualquier $k\in S$: $0sk=k$ por (I8), $0ik=0$ por (T1), $ks1=1$ por (I9), $ki1=k$ por (T2), y $ksk=kik=k$ por (I1); los órdenes inversos salen por (I2) e (I3). Quedan los cruces entre $a$, $b$, $c$:

• $asb=c$ por definición y $aib=0$ por hipótesis.
• $asc=as(asb)=(asa)sb=asb=c$, por (I4) e (I1); $aic=ai(asb)=a$, por (I7).
• $bsc=bs(bsa)=(bsb)sa=bsa=c$, por (I2), (I4) e (I1); $bic=bi(bsa)=b$, por (I2) e (I7).

Todo cae en $S$, así que $(S,s|S\times S,i|S\times S,0,1)$ es un subreticulado acotado de $L$.

Paso 3: el isomorfismo. Sea $F(1)=0$, $F(3)=a$, $F(5)=b$, $F(15)=c$, $F(30)=1$. Es biyectiva por el Paso 1. Manda 1 en $0$ y 30 en $1$. Y preserva $s$ e $i$: los pares $(3,5)$, $(3,15)$ y $(5,15)$ son los del Paso 2 —$\mathrm{mcm}(3,15)=15$ y $asc=c$, $\mathrm{mcd}(3,15)=3$ y $aic=a$, y así—; los pares con el 1 o el 30 son las cuentas con $0$ y $1$ del Paso 2, y los de un elemento consigo mismo, (I1). Su inversa también preserva: si $p=F(u)$ y $q=F(v)$, entonces $F^{\text{−1}}(psq)=F^{\text{−1}}(F(\mathrm{mcm}(u,v)))=\mathrm{mcm}(u,v)$, y lo mismo con $i$ y $\mathrm{mcd}$. Luego $F$ es un isomorfismo entre el reticulado del enunciado y un subreticulado acotado de $L$. ∎

05 · Lo que se lleva a otros ejercicios

Lo que el lenguaje ya nombra, no se cuantifica. El $0$ y el $1$ son términos; un elemento que es supremo o ínfimo de otros dos es un término. Cada cosa que se puede escribir como término es una variable menos y un puñado de desigualdades menos. Es lo opuesto al Ejercicio 7, donde el lenguaje de posets no tiene operaciones y cada supremo hay que nombrarlo con un cuantificador.

Lo que hace perder puntos. Escribir $\le$ dentro de la sentencia: no es un símbolo de este tipo. Olvidar la antena. Pedir «incomparables» en vez de «ínfimo $0$», que olvida que el subreticulado tiene que tener el mismo $0$. Usar $0ix=0$ o $xi1=x$ sin probarlos, que es justo lo que la regla de la cátedra prohíbe. Y escribir la vuelta como «se ve en el dibujo»: en la vuelta $L$ es un reticulado acotado cualquiera, y lo único que se sabe de $a$ y $b$ son las cuatro cláusulas.

Para tener a mano

1. Subreticulado acotado: mismo $0$ y mismo $1$. Por eso la imagen del 1 es el $0$ y la del 30 es el $1$.
2. De cinco elementos se nombran dos: $x$ e $y$. El 15 es $xsy$.
3. $\phi =\exists x\exists y(x\ne 0\wedge y\ne 0\wedge xiy=0\wedge xsy\ne 1)$.
4. Las diez distinciones salen de las cuatro cláusulas; sólo $xsy\ne 1$, la antena, hay que pedirla.
5. $0ix=0$ y $xi1=x$ son teoremas: si se usan, se prueban, por (I7) con (I8) y con (I9).