De Morgan sale por unicidad

El enunciado, textual: «De una prueba elemental de reticulados complementados de la sentencia elemental pura

$${\mathrm{Dis}}_1\to \forall x\forall y(c(xiy)=c(x)sc(y))$$

Puede usar como teoremas a las sentencias:

$${\mathrm{Dis}}_1\to \forall x\forall u\forall v((xsu=1\wedge xiu=0\wedge xsv=1\wedge xiv=0)\to u=v)$$ $$({\mathrm{Dis}}_1\to {\mathrm{Dis}}_2)$$

». Con Dis1 y Dis2 las dos distributivas de la lista: $\forall x\forall y\forall z(xi(ysz)=(xiy)s(xiz))$ y $\forall x\forall y\forall z(xs(yiz)=(xsy)i(xsz))$. Es una de las leyes de De Morgan, el ítem (1) del Teorema 12 de la Guía 5, y el Ejercicio 23 (b) de la Guía 7.

01 · Antes de probar: lo que la consigna regala y lo que no

El tipo es el de reticulados complementados, como en el Ejercicio 14: se escribe con $s$, $i$, $c$, $0$, $1$ y la igualdad, sin $\le$. La regla general de la cátedra pide enunciar y probar todo resultado de una guía que se use. Éste es el único ejercicio de la lista que autoriza, por escrito, dos teoremas sin prueba. Conviene ponerles nombre:

• La unicidad, la primera: con Dis1, dos complementos del mismo elemento son iguales. Es la sentencia del Ejercicio 13 y el Lema 10 de la Guía 5.
• $({\mathrm{Dis}}_1\to {\mathrm{Dis}}_2)$, la segunda: la distributiva de la lista trae la otra. Es la de Una distributiva te da la otra, y la recíproca del Ejercicio 12.

Y hay que leer igual de bien lo que no regala. No autoriza el Ejercicio 14, aunque sería el atajo natural: «$c(a)sc(b)$ es complemento de $aib$, luego es $c(aib)$». No hace falta, porque $c(aib)$ es complemento de $aib$ por I10 e I11, y entonces la unicidad compara dos complementos. Tampoco autoriza $0ix=0$, que la prueba necesita y no es axioma: va con su prueba antepuesta.

La unicidad está enunciada en reticulados acotados. Igual se puede usar acá: es una sentencia que sólo habla de $s$, $i$, $0$ y $1$, y todo reticulado complementado cumple los axiomas de acotado.

02 · La mariposa: no calcular ningún complemento

Calcular $c(aib)$ no se puede: $c$ es un dato de la estructura y ningún axioma dice cuánto vale en un ínfimo. Lo que sí se sabe de $c(aib)$ es que cumple dos ecuaciones con $aib$. La idea es mostrar que $c(a)sc(b)$ también las cumple, y dejar que la unicidad diga que son el mismo.

Con $w=c(a)sc(b)$, quedan dos metas:

$$(aib)sw=1(aib)iw=0$$

La del supremo. Hay un supremo de algo con un ínfimo, $ws(aib)$. Para abrirlo hay que meter el supremo adentro del ínfimo, y eso es Dis2, no Dis1: $ws(aib)=(wsa)i(wsb)$. Cada factor da $1$, porque $wsa$ contiene $asc(a)$, que es $1$ por I10, y algo en supremo con $1$ es $1$ por I9. Queda $1i1=1$.

La del ínfimo. Ahora es un ínfimo de un supremo, $(aib)i(c(a)sc(b))$, y eso sí lo abre Dis1: $((aib)ic(a))s((aib)ic(b))$. Cada sumando contiene $aic(a)$ o $bic(b)$, que es $0$ por I11, y algo en ínfimo con $0$ es $0$. Queda $0s0=0$.

Ahí está para qué viene el segundo teorema: la meta del supremo pide Dis2, y la hipótesis es Dis1. Sin la autorización habría que anteponer la prueba de $({\mathrm{Dis}}_1\to {\mathrm{Dis}}_2)$ entera, o hacer esa misma cuenta en el medio con la instancia que hace falta.

Cómo se usa un teorema que es una implicación. Los dos teoremas tienen Dis1 adelante, y la prueba ya supuso Dis1. Se usan en dos pasos, cada uno simple y obvio. Primero se separa el consecuente: «como suponemos Dis1 y vale $({\mathrm{Dis}}_1\to {\mathrm{Dis}}_2)$, vale Dis2». Después, si el consecuente es universal, se instancia diciendo con qué: la unicidad, tomando $x$ como $aib$, $u$ como $c(a)sc(b)$ y $v$ como $c(aib)$. Las cuatro ecuaciones de su antecedente son las dos metas de arriba y las dos de I10 e I11 en $aib$.

En el diamante De Morgan vale con dos de las ocho operaciones $c$: las que mandan los tres átomos en ronda, $c(p)=q$, $c(q)=r$, $c(r)=p$, o la ronda al revés. Con las otras seis falla, y siempre igual: dos átomos van al mismo complemento, por ejemplo $c(p)=c(q)=r$, y entonces $c(piq)=c(0)=1$ pero $c(p)sc(q)=r$. Ése es el contraejemplo: un reticulado complementado, no distributivo, con una $c$ donde la sentencia falla. La pieza que se cae es la ecuación del supremo, $0sr=r\ne 1$: el lugar donde la prueba usó Dis2.

Y cada pieza de la prueba que usa distributividad se puede caer por separado. Contado sobre los complementados no distributivos de hasta siete elementos, con todas sus $c$ y todos los pares ordenados: de 12 054 fallas, en 8878 se cae la ecuación del supremo (el paso de Dis2), en 2484 la del ínfimo (el de Dis1), y en 692 las dos ecuaciones valen pero $c(aib)$ y $c(a)sc(b)$ son dos complementos distintos: se cae la unicidad. El hexágono muestra la última; el pentágono con un átomo más, la del ínfimo.

El pentágono es la trampa al buscar contraejemplo. No es distributivo y sin embargo De Morgan vale en él con sus dos operaciones $c$, en los 25 pares. De los 26 complementados no distributivos de hasta siete elementos, en 8 vale con toda $c$. La sentencia dice que la distributividad alcanza, no que haga falta: el contraejemplo hay que buscarlo, y el primero que se prueba puede no servir.

03 · El escarabajo: la prueba escrita

Los dos teoremas autorizados se citan sin prueba, diciendo que la consigna los autoriza. $0ix=0$ va con la suya. Los axiomas, con los nombres de las guías: I1 idempotencia, I2 e I3 conmutatividad, I4 e I5 asociatividad, I6 e I7 absorción, I8 $\forall x(0sx=x)$, I9 $\forall x(xs1=1)$, I10 $\forall x(xsc(x)=1)$ e I11 $\forall x(xic(x)=0)$.

Teorema T2: $\forall x(0ix=0)$.

Prueba de T2. Sea $t\in L$ fijo pero arbitrario. El axioma I7, $\forall x\forall y(xi(xsy)=x)$, tomando $x$ como $0$ e $y$ como $t$, nos dice que $0i(0st)=0$. El axioma I8, tomando $x$ como $t$, nos dice que $0st=t$. Reemplazando, $0it=0$. Como $t$ era fijo pero arbitrario, vale $\forall x(0ix=0)$. ∎

Prueba. Supongamos Dis1. Como la consigna autoriza a usar como teorema $({\mathrm{Dis}}_1\to {\mathrm{Dis}}_2)$, vale también Dis2, es decir $\forall x\forall y\forall z(xs(yiz)=(xsy)i(xsz))$. Sean $a,b\in L$ elementos fijos pero arbitrarios.

Primera ecuación: $(aib)s(c(a)sc(b))=1$.

• El axioma I2, tomando $x$ como $aib$ e $y$ como $c(a)sc(b)$, nos dice que $(aib)s(c(a)sc(b))=(c(a)sc(b))s(aib)$.
• Dis2, tomando $x$ como $c(a)sc(b)$, $y$ como $a$ y $z$ como $b$, nos dice que$$(c(a)sc(b))s(aib)=((c(a)sc(b))sa)i((c(a)sc(b))sb)$$
• El primer factor. El axioma I2, tomando $x$ como $c(a)sc(b)$ e $y$ como $a$, nos dice que $(c(a)sc(b))sa=as(c(a)sc(b))$. El axioma I4, tomando $x$ como $a$, $y$ como $c(a)$ y $z$ como $c(b)$, nos dice que $(asc(a))sc(b)=as(c(a)sc(b))$. El axioma I10, tomando $x$ como $a$, nos dice que $asc(a)=1$, así que el factor es $1sc(b)$. El axioma I2, tomando $x$ como $1$ e $y$ como $c(b)$, nos dice que $1sc(b)=c(b)s1$, y el axioma I9, tomando $x$ como $c(b)$, que $c(b)s1=1$. O sea $(c(a)sc(b))sa=1$.
• El segundo factor. El axioma I4, tomando $x$ como $c(a)$, $y$ como $c(b)$ y $z$ como $b$, nos dice que $(c(a)sc(b))sb=c(a)s(c(b)sb)$. El axioma I2, tomando $x$ como $c(b)$ e $y$ como $b$, nos dice que $c(b)sb=bsc(b)$, y el axioma I10, tomando $x$ como $b$, que $bsc(b)=1$. Así que el factor es $c(a)s1$, y el axioma I9, tomando $x$ como $c(a)$, nos dice que $c(a)s1=1$. O sea $(c(a)sc(b))sb=1$.
• Reemplazando los dos factores, $(aib)s(c(a)sc(b))=1i1$, y el axioma I1, tomando $x$ como $1$, nos dice que $1i1=1$. Luego $(aib)s(c(a)sc(b))=1$.

Segunda ecuación: $(aib)i(c(a)sc(b))=0$.

• Dis1, tomando $x$ como $aib$, $y$ como $c(a)$ y $z$ como $c(b)$, nos dice que$$(aib)i(c(a)sc(b))=((aib)ic(a))s((aib)ic(b))$$
• El primer sumando. El axioma I3, tomando $x$ como $a$ e $y$ como $b$, nos dice que $aib=bia$, así que $(aib)ic(a)=(bia)ic(a)$. El axioma I5, tomando $x$ como $b$, $y$ como $a$ y $z$ como $c(a)$, nos dice que $(bia)ic(a)=bi(aic(a))$. El axioma I11, tomando $x$ como $a$, nos dice que $aic(a)=0$, así que el sumando es $bi0$. El axioma I3, tomando $x$ como $b$ e $y$ como $0$, nos dice que $bi0=0ib$, y el teorema T2, tomando $x$ como $b$, que $0ib=0$. O sea $(aib)ic(a)=0$.
• El segundo sumando. El axioma I5, tomando $x$ como $a$, $y$ como $b$ y $z$ como $c(b)$, nos dice que $(aib)ic(b)=ai(bic(b))$. El axioma I11, tomando $x$ como $b$, nos dice que $bic(b)=0$, así que el sumando es $ai0$. El axioma I3, tomando $x$ como $a$ e $y$ como $0$, nos dice que $ai0=0ia$, y el teorema T2, tomando $x$ como $a$, que $0ia=0$. O sea $(aib)ic(b)=0$.
• Reemplazando los dos sumandos, $(aib)i(c(a)sc(b))=0s0$, y el axioma I1, tomando $x$ como $0$, nos dice que $0s0=0$. Luego $(aib)i(c(a)sc(b))=0$.

Cierre por unicidad. Los axiomas I10 e I11, tomando $x$ como $aib$, nos dicen que $(aib)sc(aib)=1$ y $(aib)ic(aib)=0$. La consigna autoriza a usar como teorema la unicidad,

$${\mathrm{Dis}}_1\to \forall x\forall u\forall v((xsu=1\wedge xiu=0\wedge xsv=1\wedge xiv=0)\to u=v)$$

y como suponemos Dis1, vale su consecuente. Tomando $x$ como $aib$, $u$ como $c(a)sc(b)$ y $v$ como $c(aib)$, su antecedente es la conjunción de las dos ecuaciones probadas y las dos que acabamos de obtener de I10 e I11, así que obtenemos $c(a)sc(b)=c(aib)$, o sea $c(aib)=c(a)sc(b)$. Como $a$ y $b$ eran fijos pero arbitrarios, vale $\forall x\forall y(c(xiy)=c(x)sc(y))$, y como todo se dedujo suponiendo Dis1, queda probada la sentencia del enunciado. ∎

04 · Lo que se lleva y lo que hace perder puntos

La estrategia es de toda la familia. Para probar $t=c(r)$ no se calcula: se verifican $rst=1$ y $rit=0$ y se cierra con la unicidad contra $c(r)$. Así sale la otra De Morgan, $c(xsy)=c(x)ic(y)$, con la misma estrategia, y $c(c(x))=x$, donde la cuenta es todavía más corta: I10 e I11 en $x$, conmutadas, dicen que $x$ es complemento de $c(x)$. En otro ejercicio la unicidad no viene regalada: hay que enunciarla y probarla, como en el Ejercicio 14.

Lo que hace perder puntos. Usar el Ejercicio 14, o cualquier otro teorema que no sean los dos autorizados, sin probarlo; en particular $0ix=0$. Abrir la ecuación del supremo con Dis1, que no tiene la forma: es un ínfimo afuera de un supremo, y ahí hay un supremo afuera de un ínfimo. Usar la unicidad sin decir con qué se instancia $x$, $u$ y $v$, o sin mostrar las cuatro ecuaciones del antecedente: las dos de $c(aib)$ también se escriben. Y despachar el segundo factor o el segundo sumando con «análogamente».

Para tener a mano

1. Es la única de la lista con teoremas autorizados: la unicidad del Ejercicio 13 y $({\mathrm{Dis}}_1\to {\mathrm{Dis}}_2)$. El Ejercicio 14 y $0ix=0$ no lo están.
2. No se calcula $c(aib)$: se muestra que $c(a)sc(b)$ es complemento de $aib$ y se cierra por unicidad con $v$ igual a $c(aib)$.
3. La ecuación del supremo se abre con Dis2; la del ínfimo, con Dis1.
4. Un teorema con Dis1 adelante se usa en dos pasos: separar el consecuente, porque Dis1 está supuesta, e instanciarlo diciendo con qué.
5. Contraejemplo: el diamante con $c(p)=c(q)=r$ da $c(piq)=1$ y $c(p)sc(q)=r$.
6. El pentágono no sirve: De Morgan vale ahí con sus dos $c$, aunque no sea distributivo.