Distributivo, sin s ni i

El enunciado, textual: «De una sentencia elemental pura de posets la cual sea verdadera en un poset $(P,\le )$ si y solo si $(P,\le )$ es un reticulado par cuyo reticulado terna asociado es distributivo». Es el Ejercicio 2 (d) de la Guía 7. Se entrega una sentencia y la justificación de que es verdadera exactamente en esos posets.

01 · Antes de escribir: lo que el lenguaje no tiene

El lenguaje de posets es pobre. Sus términos son las variables y los nombres de elementos fijos, y nada más: no hay operaciones ni constantes. Las fórmulas atómicas son $(t=r)$ y $(t\le r)$. Y la propiedad pedida está escrita con operaciones: «distributivo» es ${\mathrm{Dis}}_1$, $xi(ysz)=(xiy)s(xiz)$. Ese $s$ y ese $i$ no son símbolos de posets; $xsy$ no es un término acá.

La propiedad son dos cosas. Primero, que $(P,\le )$ sea un reticulado par: que todo par tenga supremo e ínfimo. Sólo entonces existe el reticulado terna asociado, con $asb=\sup \{a,b\}$ y $aib=\inf \{a,b\}$. Segundo, que ese reticulado terna cumpla ${\mathrm{Dis}}_1$. La segunda depende de la primera: sin supremos no hay $s$ del que hablar.

Sentencia y pura. Ninguna variable libre, ningún nombre de elemento fijo. El valor de verdad lo decide el poset solo, y tiene que ser «verdadera» en los reticulados distributivos y «falsa» en todos los demás posets: los que no son reticulados y los reticulados que no son distributivos.

02 · Las herramientas

Las definiciones, en el orden en que se usan. Supremo: $u$ es el supremo de $\{a,b\}$ cuando es cota superior —$a\le u$ y $b\le u$— y está debajo de toda otra cota superior. Reticulado par: todo par tiene supremo e ínfimo. Reticulado terna asociado: $(P,s,i)$ con $s$ e $i$ definidas como supremo e ínfimo del par. Distributivo: el reticulado terna cumple ${\mathrm{Dis}}_1$. Y de los axiomas de poset, uno: A≤A, la antisimetría, $\forall x\forall y((x\le y\wedge y\le x)\to x=y)$.

El ladrillo es el Ejercicio 1 (c) de la Guía 7, «existe el supremo de $\{x,y\}$». Conviene escribirlo con el supremo como tercer argumento, para poder hablar de él. Dos atajos de lectura, que no son símbolos del lenguaje:

Con $t$, $r$, $u$ asignados a $a$, $b$, $c$, $\mathrm{Sup}(t,r,u)$ es verdadera si y solo si $c$ es el supremo de $\{a,b\}$: el primer conjunto dice «cota superior» y el segundo «la menor». Cada vez que se usa un atajo, su $w$ ligada lleva un nombre nuevo —$w_1$, $w_2$, …— para que no capture ninguna variable de afuera. Es la misma operación que en decilo con una fórmula: escribir algo cuya columna de verdades coincida con la de la propiedad.

03 · La mariposa: ponerle nombre a cada pedazo

Primera pregunta: ¿cómo se dice «es reticulado par»? Es la definición leída en voz alta: para todo par existe un $z$ que es su supremo y un $u$ que es su ínfimo.

Segunda pregunta: ¿cómo se dice $xi(ysz)=(xiy)s(xiz)$ sin escribir $s$ ni $i$? El término no se puede escribir, pero se puede recorrer. Cada nodo interno de su árbol es un supremo o un ínfimo de dos cosas que ya tienen nombre, y se le pone un nombre nuevo:

Cinco operaciones en ${\mathrm{Dis}}_1$, cinco nombres. La igualdad de los dos lados es $q=v$, que sí es una fórmula de posets.

Tercera pregunta: ¿los nombres van con $\forall$ o con $\exists$? Hay dos caminos, y los dos sirven. Con $\forall$: «para todos $p,q,r,u,v$, si cada uno es lo que su renglón dice, entonces $q=v$».

Y acá está la trampa del ejercicio. Una implicación con el antecedente falso es verdadera. Si en el poset no existe el supremo de $y$ y $z$, ningún $p$ cumple $\mathrm{Sup}(y,z,p)$, el antecedente es falso para todas las asignaciones, y ${\phi }_{\text{dis}}$ pasa sin mirar nada. En la anticadena de dos elementos —dos elementos que no se comparan— ${\phi }_{\text{dis}}$ es verdadera, y la anticadena ni siquiera es un reticulado. Por eso ${\phi }_{\text{dis}}$ sola no alcanza: hace falta ${\phi }_{\text{par}}$ al lado, que garantiza que los cinco nombres existan.

El otro camino es con $\exists$: «para todos $x,y,z$ existen $p,q,r,u,v$ que son lo que dicen sus renglones, y además $q=v$». Ésa no pasa en vacío: si falta un supremo, falta el testigo, y es falsa. Tanto, que ella sola alcanza: con $y$ y $z$ cualesquiera exige el supremo de todo par, y con $x$ e $y$ cualesquiera, el ínfimo. Que el $\forall$ y el $\exists$ digan lo mismo cuando todo existe es porque el supremo, si existe, es uno solo: no hay dos candidatos a $p$ entre los que el $\forall$ y el $\exists$ puedan diferir.

El widget de abajo tiene las dos, cada una sola, y una versión rota a propósito: la que en $\mathrm{Sup}$ e $\mathrm{Inf}$ se olvida del «la menor» y deja sólo la cota.

Lo que el widget muestra en nueve posets vale en todos los chicos. Evaluadas sobre los 405 posets de hasta seis elementos, salvo isomorfismo —1, 2, 5, 16, 63 y 318, las cantidades conocidas—: ${\phi }_{\text{par}}\wedge {\phi }_{\text{dis}}$ y la versión con $\exists$ coinciden con la propiedad en los 405. ${\phi }_{\text{dis}}$ sola se equivoca en 364: es verdadera en casi todo lo que no es reticulado. ${\phi }_{\text{par}}$ sola se equivoca en 12, que son exactamente los reticulados no distributivos de hasta seis elementos, empezando por el diamante y el pentágono. La versión con «cota» en lugar de «supremo» falla ya en la cadena de dos: con $x$, $y$, $z$ todos en el de abajo, $v$ puede ser cualquier cota de $r$ y $u$, también el de arriba, y $q=v$ no tiene por qué valer.

Que coincidan en 405 no es una prueba —un poset de siete elementos podría romperla—. La prueba es la sección siguiente.

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

La sentencia es $\phi =({\phi }_{\text{par}}\wedge {\phi }_{\text{dis}})$, con

donde cada atajo se reemplaza por su expansión, con su $w$ renombrada ($w_1$ a $w_5$ en ${\phi }_{\text{dis}}$). Es elemental de posets: sólo hay $\le$, $=$, nexos y cuantificadores. Es pura, y es una sentencia: todas sus variables están ligadas.

Lema (unicidad). En un poset, si $c$ y $c^{\prime }$ son supremos de $\{a,b\}$, entonces $c=c^{\prime }$. Como $c^{\prime }$ es cota superior y $c$ está debajo de toda cota superior, $c\le c^{\prime }$; por lo mismo con los papeles cambiados, $c^{\prime }\le c$; y por A≤A, tomando $x$ como $c$ e $y$ como $c^{\prime }$, $c=c^{\prime }$. Igual para el ínfimo. Lo que se usa del lema: si $\mathrm{Sup}(t,r,u)$ es verdadera con $t,r,u$ en $a,b,c$, entonces $c$ es el supremo de $\{a,b\}$.

Si $(P,\le )$ es un reticulado par con terna asociado distributivo, $\phi$ es verdadera.

• ${\phi }_{\text{par}}$: sean $a,b\in P$ fijos pero arbitrarios, asignados a $x$ e $y$. Tomando $z$ como $\sup \{a,b\}$, que existe por ser reticulado par, $\mathrm{Sup}(x,y,z)$ es verdadera; tomando $u$ como $\inf \{a,b\}$, también $\mathrm{Inf}(x,y,u)$. Como $a,b$ eran arbitrarios, vale el $\forall x\forall y$.
• ${\phi }_{\text{dis}}$: sean $a,b,c,p_0,q_0,r_0,u_0,v_0\in P$ fijos pero arbitrarios, asignados a $x,y,z,p,q,r,u,v$, y supongamos el antecedente verdadero. Por el lema, $p_0=bsc$, $q_0=ai{p}_0=ai(bsc)$, $r_0=aib$, $u_0=aic$ y $v_0=r_{0}s{u}_0=(aib)s(aic)$. Por ${\mathrm{Dis}}_1$, tomando $x$ como $a$, $y$ como $b$ y $z$ como $c$, $q_0=v_0$: el consecuente. Si el antecedente es falso la implicación vale igual. Como los ocho eran arbitrarios, vale ${\phi }_{\text{dis}}$.

Si $\phi$ es verdadera, $(P,\le )$ es un reticulado par con terna asociado distributivo.

• Reticulado par: sean $a,b$ fijos pero arbitrarios. Por ${\phi }_{\text{par}}$, tomando $x$ como $a$ e $y$ como $b$, hay un $c$ con $\mathrm{Sup}(x,y,z)$ verdadera para $z$ en $c$, o sea $c=\sup \{a,b\}$; y un $d=\inf \{a,b\}$. Existen los dos. Entonces el reticulado terna asociado $(P,s,i)$ está definido.
• Distributivo: sean $a,b,c$ fijos pero arbitrarios. Como $(P,\le )$ es reticulado par, existen $p_0=bsc$, $q_0=ai{p}_0$, $r_0=aib$, $u_0=aic$ y $v_0=r_{0}s{u}_0$, y con $x,y,z,p,q,r,u,v$ asignados a $a,b,c,p_0,q_0,r_0,u_0,v_0$ los cinco conjuntos del antecedente de ${\phi }_{\text{dis}}$ son verdaderos. Instanciando ${\phi }_{\text{dis}}$ en esa asignación, $q_0=v_0$, es decir $ai(bsc)=(aib)s(aic)$. Como $a,b,c$ eran arbitrarios, vale ${\mathrm{Dis}}_1$. ∎

La vuelta usa ${\phi }_{\text{par}}$ dos veces: para que el terna asociado exista, y para que los cinco nombres tengan quién los ocupe. Sin ella, ${\phi }_{\text{dis}}$ se instancia en una asignación que no existe.

05 · Lo que se lleva a otros ejercicios

Un término que el lenguaje no tiene se recorre. Cada nodo interno, una variable y un renglón que la caracteriza. Es lo que hace el Ejercicio 2 (c) de la misma guía con un solo supremo, y lo opuesto de lo que pasa en el Ejercicio 9, donde el lenguaje tiene $s$ e $i$ y un elemento que es supremo de otros dos ni siquiera necesita variable.

Un $\forall$ sobre testigos pide que alguien garantice que existen. Ante cada $\forall$ con un antecedente, la pregunta es qué pasa si el antecedente no se cumple nunca. Si la respuesta es «la sentencia es verdadera y no debería», falta una cláusula de existencia o hay que pasar a $\exists$.

Lo que hace perder puntos. Escribir $xsy$ dentro de la sentencia, que no es un término de posets. Entregar ${\phi }_{\text{dis}}$ sola. Olvidar la segunda mitad de $\mathrm{Sup}$: sin «la menor», $\mathrm{Sup}$ dice «cota superior» y la sentencia falla hasta en una cadena. Reutilizar la misma $w$ en dos atajos anidados, que puede capturar una variable. Y usar la unicidad del supremo sin probarla: es un resultado de guía, y la regla de la cátedra pide enunciarlo y probarlo aparte, como en el lema de arriba.

Para tener a mano

1. El lenguaje de posets no tiene $s$ ni $i$: cada supremo e ínfimo se nombra con una variable y se describe con $\mathrm{Sup}$ o $\mathrm{Inf}$.
2. ${\mathrm{Dis}}_1$ tiene cinco operaciones: cinco nombres $p,q,r,u,v$, y la igualdad es $q=v$.
3. ${\phi }_{\text{dis}}$ sola es verdadera en vacío cuando faltan supremos: en la anticadena de dos, por ejemplo. Va con ${\phi }_{\text{par}}$.
4. Con $\exists$ en lugar de $\forall$ sobre los cinco nombres, la sentencia sola alcanza: exige la existencia.
5. El $\forall$ y el $\exists$ coinciden porque el supremo es único; la unicidad, si se usa, se prueba.