Reticulado par, terna y cuaterna

La cátedra define reticulado tres veces. La Guía 3 lo da como un orden en el que todo par tiene supremo e ínfimo. La Guía 4, como dos operaciones que cumplen siete identidades, sin ningún orden a la vista. La Guía 6, como las dos cosas juntas, atadas por siete axiomas. Las tres guardan la misma información, y el teorema de Dedekind es el que lo garantiza. Lo que cambia de una a otra es qué se da, qué hay que verificar y qué se puede escribir en una prueba.

01 · Las tres definiciones

Reticulado par (Guía 3). Un poset $(P,\le )$ tal que, para todo $a,b\in P$, existen $\sup (\{a,b\})$ e $\inf (\{a,b\})$. Lo único que se da es la relación. Las operaciones vienen después, definidas a partir de ella: $asb=\sup (\{a,b\})$ y $aib=\inf (\{a,b\})$.

Reticulado terna (Guía 4). Una terna $(L,s,i)$ con $L$ no vacío y $s$, $i$ dos operaciones binarias sobre $L$ que cumplen, cualesquiera sean $x,y,z\in L$:

• (I1) $xsx=x=xix$
• (I2) $xsy=ysx$ y (I3) $xiy=yix$
• (I4) $(xsy)sz=xs(ysz)$ y (I5) $(xiy)iz=xi(yiz)$
• (I6) $xs(xiy)=x$ y (I7) $xi(xsy)=x$

Idempotencia, conmutatividad, asociatividad y absorción, cada una para las dos operaciones. Son siete con la numeración de la Guía 4 y ocho sentencias cuando se escriben como axiomas elementales. Ninguna menciona un orden: lo que se da son dos tablas.

Reticulado cuaterna (Guía 6). Una 4-upla $(L,s,i,\le )$ con $L$ no vacío, $s$ e $i$ operaciones binarias y $\le$ una relación binaria sobre $L$, que cumple los siete axiomas elementales:

• A≤R $\forall x(x\le x)$
• A≤T $\forall x\forall y\forall z((x\le y\wedge y\le z)\to x\le z)$
• A≤A $\forall x\forall y((x\le y\wedge y\le x)\to x=y)$
• AsesC $\forall x\forall y(x\le xsy\wedge y\le xsy)$
• As≤C $\forall x\forall y\forall z((x\le z\wedge y\le z)\to xsy\le z)$
• AiesC $\forall x\forall y(xiy\le x\wedge xiy\le y)$
• Ai≥C $\forall x\forall y\forall z((z\le x\wedge z\le y)\to z\le xiy)$

Los tres primeros dicen que $\le$ es un orden parcial. AsesC dice que $xsy$ es cota superior de $\{x,y\}$, y As≤C que está debajo de cualquier otra: juntos, que $xsy=\sup (\{x,y\})$. Los dos últimos dicen lo mismo de $i$ y el ínfimo. Acá se da todo: el orden y las dos tablas, y lo que se verifica es que encajen.

02 · De par a terna: la dirección gratis

Si $(L,\le )$ es un reticulado par, la terna $(L,s,i)$ con $s$ e $i$ el supremo y el ínfimo es un reticulado terna. Las siete identidades son lemas de la Guía 3, probados desde la definición de supremo y de ínfimo: la idempotencia y la conmutatividad son el Lema 1, la asociatividad el Lema 4 y las absorciones el Lema 3. No hay nada que construir, porque el orden ya está y las operaciones salen de él.

Lo mismo para la cuaterna: $(L,s,i,\le )$ cumple los siete axiomas, porque los tres primeros son la hipótesis de poset y los otros cuatro son la definición de supremo y de ínfimo partida en dos mitades cada una.

El paso que no es gratis es el de antes: que $(L,\le )$ sea un reticulado par. Ahí es donde un orden puede fallar, y cuando falla no es porque una tabla dé un valor equivocado, sino porque hay una celda que no se puede llenar.

03 · De terna a par: el teorema de Dedekind

La otra dirección es el teorema. Dada una terna $(L,s,i)$ que cumple las siete identidades, se define

$$x\le y⟺xsy=y$$

y el Teorema 1 de la Guía 4 dice que $\le$ es un orden parcial, que $xsy=\sup (\{x,y\})$ y que $xiy=\inf (\{x,y\})$. La prueba es una cadena de pasos cortos, y conviene tenerla entera con la identidad que usa cada uno.

Paso 1: es reflexiva. $xsx=x$ es I1, y eso es $x\le x$.

Paso 2: es antisimétrica. Si $xsy=y$ y $ysx=x$, entonces $x=ysx=xsy=y$, con I2 en el medio.

Paso 3: es transitiva. Si $xsy=y$ y $ysz=z$, entonces $xsz=xs(ysz)=(xsy)sz=ysz=z$, con I4 en el segundo igual.

Paso 4: $xsy$ es cota superior. Hay que ver $xs(xsy)=xsy$ y $ys(xsy)=xsy$. La primera: $xs(xsy)=(xsx)sy=xsy$, por I4 y I1. La segunda: $ys(xsy)=ys(ysx)=(ysy)sx=ysx=xsy$, por I2, I4, I1 e I2.

Paso 5: es la menor. Si $xsz=z$ y $ysz=z$, entonces $(xsy)sz=xs(ysz)=xsz=z$, por I4.

Paso 6: el orden también se lee en $i$. Para el ínfimo, la Guía 4 prueba primero que $u\le v$ si y sólo si $uiv=u$. Si $usv=v$, entonces $uiv=ui(usv)=u$ por I7. Y si $uiv=u$, entonces

$$usv=(uiv)sv=vs(uiv)=vs(viu)=v$$

por I2, I3 e I6. Esta vuelta es la única que usa la absorción del supremo.

Paso 7: $xiy$ es el ínfimo. Con el paso 6, es el paso 4 y el 5 dados vuelta: $(xiy)ix=xi(xiy)=(xix)iy=xiy$ por I3, I5 e I1; $(xiy)iy=xi(yiy)=xiy$ por I5 e I1; y si $zix=z$ y $ziy=z$, $zi(xiy)=(zix)iy=ziy=z$ por I5.

Las siete aparecen. Qué papel juega cada una —cuáles construyen el orden y cuáles atan $i$ a ese mismo orden— es la tesis de Cuando las siete identidades se cumplen, aparece un orden.

Es lo mismo. Las dos construcciones se deshacen una a la otra. Del par a la terna y de vuelta al par se recupera el mismo orden, porque en un reticulado par $x\le y$ si y sólo si $xsy=y$ (Lema 2 de la Guía 3). De la terna al par y de vuelta a la terna se recuperan las mismas tablas, porque el supremo del orden de Dedekind es $s$ (paso 5). Por eso hay una biyección entre reticulados par y reticulados terna sobre un mismo conjunto, que es el Ejercicio 3 de la Guía 4.

Contado por enumeración sobre los conjuntos de uno a cinco elementos: las ternas que cumplen las siete son 1, 2, 6, 36 y 380, y los reticulados par sobre el mismo conjunto son 1, 2, 6, 36 y 380. En cada una de esas 425 ternas el orden de Dedekind es un orden parcial con $s$ e $i$ como supremo e ínfimo, la ida y vuelta devuelve las mismas tablas, y no hay dos ternas con el mismo orden. El 6 es la respuesta del Ejercicio 4 de la Guía 4: sobre $\{1,2,3\}$ las únicas ternas son las seis cadenas.

04 · La cuaterna: las dos cosas, y que encajen

El Ejercicio 1 de la Guía 6 pide probar que $(L,s,i,\le )$ es un reticulado cuaterna si y sólo si $(L,s,i)$ es un reticulado terna y $\le$ es su orden asociado. La guía insiste en que eso es un teorema y no la definición. Una dirección: los siete axiomas hacen de $\le$ un orden con $s$ e $i$ como supremo e ínfimo, así que $(L,\le )$ es un reticulado par, $(L,s,i)$ es su terna, y por el Lema 2 de la Guía 3 $x\le y$ si y sólo si $xsy=y$. La otra: si la terna lo es y $\le$ es su orden, Dedekind da los siete.

Lo que la cuaterna agrega es la posibilidad de que los datos no encajen. Una relación y dos operaciones dadas por separado pueden ser, cada una por su lado, impecables, y la 4-upla igual no ser un reticulado. El Ejercicio 2 de la Guía 6 lo muestra con $(\mathbb{N},\mathrm{máx},\mathrm{mín},|)$: el orden es la divisibilidad, que con mcm y mcd es un reticulado; $(\mathbb{N},\mathrm{máx},\mathrm{mín})$ es una terna; pero las operaciones son las del orden usual y no las de la divisibilidad. Con $x=2$ e $y=3$, $\mathrm{máx}(2,3)=3$ y $2$ no divide a $3$: falla AsesC. Falla también AiesC, y sobreviven los otros cinco: A≤R, A≤T, A≤A, As≤C y Ai≥C, porque el máximo de dos números que dividen a $z$ es uno de ellos y también divide a $z$.

El caso extremo es $(ℝ,+,·,\le )$, la otra mitad del mismo ejercicio. Sobreviven sólo los tres del orden: AsesC falla con $x=1$, $y=-1$; As≤C con $x=y=z=1$; AiesC con $x=y=2$; y Ai≥C con $x=y=z=1/2$.

Y contado: sobre $\{0,1,2\}$ hay 512 relaciones binarias y 19 683 operaciones binarias, así que las 4-uplas son 512 por 19 683 al cuadrado, casi doscientos mil millones. Las que cumplen los siete axiomas son seis, y las seis son una terna con su orden asociado: las mismas seis cadenas de antes.

Las dos estructuras sobre los divisores de 6 con otras operaciones son el mismo fenómeno. Con máximo y mínimo, la terna es una cadena —su orden de Dedekind es $1<2<3<6$— y la relación dada es el rombo de la divisibilidad: dos órdenes distintos, y por eso caen AsesC y AiesC. Con las operaciones dadas vuelta, la terna sigue siendo terna (es el Ejercicio 5 de la Guía 4), pero su orden es la divisibilidad al revés. En los dos casos el par y la terna pasan, y la cuaterna no. El poset de seis elementos es el caso contrario: el orden de Dedekind de $s$ coincide con $\le$, pero $a$ y $b$ no tienen supremo, y entonces la terna tampoco puede ser terna: lo que se le cae es la asociatividad.

05 · Una terna a la que le falta una identidad

Sobre $\{0,1,2\}$, tomá $xsy=x$ —el supremo devuelve siempre el primero— y como $i$ el mínimo. Es la cuarta estructura del widget. Cumple seis de las siete: $s$ es idempotente, y es asociativa porque los dos lados de I4 dan $x$; las dos absorciones valen porque $xs(xiy)=x$ por cómo está definida $s$, y $xi(xsy)=xix=x$. Lo único que falla es I2: $0s1=0$ pero $1s0=1$.

Lo que se rompe es el paso 6. Las dos lecturas del orden dejan de coincidir. Leído en $s$, $xsy=y$ sólo pasa cuando $x=y$, así que el orden de Dedekind es la anticadena: un orden parcial, pero ningún par de elementos distintos tiene supremo. Leído en $i$, $xiy=x$ da la cadena $0<1<2$. En términos de sentencias: la de la Guía 7,

$$\eta =\forall x\forall y(xsy=y\to xiy=x)$$

sigue valiendo, porque su prueba usa sólo I7. Pero la recíproca, la del Ejercicio 19 de esa guía, $\forall x\forall y(xiy=x\to xsy=y)$, falla con $x=0$, $y=1$: $0i1=0$ y $0s1=0\ne 1$. Es la que en la prueba del paso 6 necesitaba I2.

No es un caso aislado. Sobre $\{0,1,2\}$, entre todos los pares de operaciones, los que fallan exactamente una de las ocho sentencias son: 42 que fallan sólo la conmutatividad de $s$, 42 sólo la de $i$, 6 sólo I6 y 6 sólo I7. Ninguno falla sólo una mitad de I1, y ninguno sólo una asociatividad. Lo de I1 no depende del tamaño: sus dos mitades se deducen de las absorciones, y la cuenta está en aparece un orden, junto con el caso de máximo y máximo común divisor, que es el que falla sólo I7.

06 · Qué cambia al escribir una prueba

Si las tres guardan la misma información, ¿para qué tres? Porque cada una se escribe con símbolos distintos, y en una prueba elemental sólo se puede citar lo que el tipo trae como axioma. Lo que en una definición es un axioma, en otra es un teorema que hay que probar.

Una desigualdad. Que $x$ está debajo de $xsy$. En cuaterna es un renglón: la primera mitad de AsesC, tomando $x$ como $a$ e $y$ como $b$. En terna no se puede ni escribir, porque el lenguaje de las ternas no tiene $\le$. La Guía 7 propone escribir $tsu=u$ en lugar de $t\le u$, y entonces la sentencia es $\forall x\forall y(xs(xsy)=xsy)$, que no es un axioma y hay que probar:

Es el paso 4 del teorema de Dedekind escrito como escarabajo. El Ejercicio 21 de la Guía 7 pide exactamente eso para cuatro sentencias: las traducciones de la antisimetría, la transitividad, AsesC y As≤C. En terna, todo lo que se use del orden hay que reconstruirlo desde las identidades.

Una igualdad. Que $xsy=ysx$. En terna es un renglón: es I2. En cuaterna es la prueba de la sentencia $\rho$ de la Guía 6: AsesC instanciado dos veces, As≤C dos veces para tener las dos desigualdades, y A≤A para juntarlas. La guía la deja con un «en forma análoga» y avisa que así no es elemental; escrita entera cita cinco instancias de axioma.

Una existencia. El reticulado par no es uno de los tipos de la Guía 7: su lenguaje sería el de los posets, que no tiene símbolo para el supremo. Que todo par tenga supremo e ínfimo se dice con un $\exists$:

$$\forall x\forall y\exists z(x\le z\wedge y\le z\wedge \forall w((x\le w\wedge y\le w)\to z\le w))$$

y su gemela con las desigualdades dadas vuelta para el ínfimo. Evaluadas sobre todos los posets de hasta cuatro elementos —1, 3, 19 y 219—, la conjunción de las dos es verdadera exactamente en los reticulados: 1, 2, 6 y 36. Cada vez que una prueba en ese lenguaje necesita el supremo de dos elementos, tiene que sacarlo de ese $\exists$ y ponerle nombre. Es lo que pide la lista del parcial cuando busca una sentencia de posets para «reticulado par distributivo».

Por eso conviene tener las tres a mano y elegir según lo que hay que probar. Las desigualdades se piensan y se prueban en cuaterna, donde las tres reglas de la Guía 3 son axiomas. Las igualdades entre operaciones, como las distributivas, son naturales en terna. Las existencias son del lenguaje de los posets. Lo que no se puede es mezclar: una prueba escrita para un tipo deja de serlo en otro aunque la sentencia se lea igual en los dos, y eso es la misma prueba, otro tipo.

Para tener a mano

1. Par: un poset $(P,\le )$ con $\sup (\{a,b\})$ e $\inf (\{a,b\})$ para todo par. Se da un orden.
2. Terna: $(L,s,i)$ con I1 a I7: idempotencia, conmutatividad, asociatividad y absorción. Se dan dos operaciones; en la Guía 7 son ocho sentencias.
3. Cuaterna: $(L,s,i,\le )$ con A≤R, A≤T, A≤A, AsesC, As≤C, AiesC y Ai≥C. Se dan las dos cosas y tienen que encajar.
4. De par a terna: $s$ e $i$ son el supremo y el ínfimo, y las siete salen de los lemas de la Guía 3.
5. De terna a par (Dedekind): $x\le y$ sii $xsy=y$, que es lo mismo que $xiy=x$. La equivalencia entre las dos lecturas usa I2, I3, I6 e I7.
6. Las dos construcciones se deshacen una a la otra: sobre 1 a 5 elementos hay 1, 2, 6, 36 y 380 de cada lado.
7. Cuaterna es terna más su orden asociado (Guía 6, Ejercicio 1). Un par y una terna correctos por separado pueden no encajar: $(\mathbb{N},\mathrm{máx},\mathrm{mín},|)$ falla AsesC y AiesC.
8. Lo que en una es axioma, en otra es teorema: $x\le xsy$ es AsesC en cuaterna y una prueba en terna; $xsy=ysx$ es I2 en terna y una prueba en cuaterna.