5.2 Reticulados par

El concepto de reticulado puede ser abordado en dos formas distintas, una geometrica, via posets, la cual daremos ahora y la otra algebraica, via estructuras algebraicas definidas ecuacionalmente, la cual daremos en la seccion siguiente. Como veremos mas adelante ambas definiciones son equivalentes.

Por un reticulado par entenderemos un poset $(P,\le )$ el cual cumple que para todo $a,b\in P$, existen (en $(P,\le )$) $sup\left(\right\{a,b\left\}\right)$ e $inf\left(\right\{a,b\left\}\right)$. Algunos ejemplos:

1. (E1) El poset $(N,D)$ es un reticulado par ($D=\left\{\right(x,y)\in N^2:x|y\}$) ya que dados $x,y\in N$, hemos visto que $mcd(x,y)$ y $mcm(x,y)$ son infimo y supremo del conjunto $\{x,y\}$ en $(N,D)$

2. (E2) El poset $\left(P\right(\omega ),\le )$ es un reticulado par ($\le =\left\{\right(A,B)\in P(\omega {)}^2:A\subseteq B\}$) ya que dados $A,B\in P\left(\omega \right)$, hemos visto que $A\cap B$ y $A\cup B$ son infimo y supremo del conjunto $\{A,B\}$ en $\left(P\right(\omega ),\le )$

Recordemos que dado un conjunto $A$, por una operacion binaria sobre $A$ entenderemos una funcion cuyo dominio es $A^2$ y cuya imagen esta contenida en $A$. En un reticulado par $(P,\le )$ tenemos dos operaciones binarias naturalmente definidas: $$\begin{array}{ccc}s:P^2& \to & P\\ (a,b)& \to & sup\left(\right\{a,b\left\}\right)\end{array}\begin{array}{ccc}i:P^2& \to & P\\ (a,b)& \to & inf\left(\right\{a,b\left\}\right)\end{array}$$ Escribiremos $asb$ en lugar de $s(a,b)$ y $aib$ en lugar de $i(a,b)$.

A continuacion nos dedicaremos a probar varias propiedades agradables que se cumplen en un reticulado par. Recomendamos al lector que en algunos casos practique encontrando pruebas perfectas. Esto lo entrenara en su capacidad de ser un matematico maduro, la cual sera crucial a la hora de hacer logica ya que la logica estudia (modeliza) matematicamente el funcionar de un matematico y sera muy practico que cada uno cuente con un matematico maduro en su propia mente.

Proof. Prueba perfecta de (1). Sean $a,b\in L$, fijos. Por definicion de $s$ tenemos que $a$ $s$ $b=sup\left(\right\{a,b\left\}\right)$. O sea que por definicion de supremo de un conjunto tenemos que $a$ $s$ $b$ es cota superior del conjunto $\{a,b\}$ en $(L\le )$. O sea que $a\le a$ $s$ $b$. Ya que $a,b$ eran arbitrarios, hemos probado que vale (1).  

Prueba perfecta de (3). Sea $a\in L$, fijo. Por definicion de $s$ tenemos que $a$ $s$ $a=sup\left(\right\{a,a\left\}\right)=sup\left(\right\{a\left\}\right)$. O sea que debemos probar que $a=sup\left(\right\{a\left\}\right)$. Es claro que $a$ es cota superior de $\left\{a\right\}$. Ademas es claro que si $z$ es cota superior de $\left\{a\right\}$, entonces $z\ge a$. O sea que por definicion de supremo de un conjunto tenemos que $a=sup\left(\right\{a\left\}\right)$. O sea que hemos probado que $asa=a$. Ya que $a$ era arbitrario, hemos probado que vale (3).

Dejamos al lector completar la prueba.

Proof. Ejercicio  

Las siguientes dos propiedades son conocidas como leyes de absorcion (por que?)

Proof. (1). Sean $a,b\in L$, fijos. Por definicion de $i$ debemos probar que $sup\left(\right\{a,aib\left\}\right)=a$. O sea debemos probar que $a$ es la menor cota superior de $\{a,aib\}$. Por un lema anterior tenemos que $aib\le a$ y obviamente se da $a\le a$, lo cual nos dice que $a$ es cota superior de $\{a,aib\}$. Es claro que es menor o igual que cualquier otra cota superior. O sea que hemos probado que $as\left(aib\right)=a$, lo cual ya que $a,b$ eran elementos arbitrarios nos dice que vale (1).  

(2) es dejada al lector.

Antes de seguir dando propiedades basicas de los reticulados par daremos tres reglas que seran de suma utilidad para encontrar pruebas. Dejamos al lector justificar matematicamente la validez de dichas reglas.

Regla Igualdad en Posets

Si ud esta intentando probar que en un poset $(P,\le )$ dos elementos $x,y$ son iguales, desdoble su tarea en las dos tareas siguientes:

1. - Probar que $x\le y$

2. - Probar que $y\le x$

Regla Superar un Supremo

Si ud esta intentando probar que en un reticulado par $(L,\le )$ se da que $z\ge xsy$, desdoble su tarea en las dos tareas siguientes:

1. - Probar que $z\ge x$

2. - Probar que $z\ge y$

Regla Ser Menor o Igual que un Infimo

Si ud esta intentando probar que en un reticulado par $(L,\le )$ se da que $z\le xiy$, desdoble su tarea en las dos tareas siguientes:

1. - Probar que $z\le x$

2. - Probar que $z\le y$

Ambas operaciones $s$ e $i$ son asociativas, es decir:

Proof. (1) Sean $a,b,c\in L$, fijos. Usaremos la regla Igualdad en Posets. Primero probaremos $\left(asb\right)sc\le as\left(bsc\right)$. Para esto usaremos la regla Superar un Supremo. Es decir que debemos probar que $$\begin{array}{cc}\left(asb\right)& \le as\left(bsc\right)\\ c& \le as\left(bsc\right)\end{array}$$ Para la primer desigualdad usaremos tambien la regla Superar un Supremo, por lo cual deberemos probar $$\begin{array}{cc}a& \le as\left(bsc\right)\\ b& \le as\left(bsc\right)\end{array}$$ O sea que en suma debemos probar las siguientes desigualdades $$\begin{array}{cc}a& \le as\left(bsc\right)\\ b& \le as\left(bsc\right)\\ c& \le as\left(bsc\right)\end{array}$$ La primera es directa de un lema anterior, y para la segunda notese que el mismo lema nos dice que $$b\le \left(bsc\right)\text{y}\left(bsc\right)\le as\left(bsc\right)$$ por lo cual solo resta usar que $\le$ es transitiva. La tercera es completamente analoga a la segunda.

En forma similar se prueba que $as\left(bsc\right)\le \left(asb\right)sc$. Es decir que por la regla Igualdad en Posets tenemos que $as\left(bsc\right)=\left(asb\right)sc$. Ya que $a,b,c$ eran elementos arbitrarios hemos probado que vale (1).

(2) es dejada como ejercicio.  

El siguiente lema prueba que en un reticulado par las operaciones $s$ e $i$ preservan el orden.

Proof. (1) Sean $a,b,c,d\in L$, elementos fijos. Supongamos que $a\le c$ e $b\le d$. Probaremos que entonces $asb\le csd$. Por la regla Superar un Supremo basta con probar que $$\begin{array}{cc}a& \le csd\\ b& \le csd\end{array}$$ Para ver que $a\le csd$ notese que $a\le c$ (por hipotesis) y $c\le csd$, por lo cual podemos usar que $\le$ es transitiva. La desigualdad $b\le csd$ se prueba en forma similar. O sea que hemos probado que $$a\le c\text{y}b\le d\text{implica}asb\le csd$$ Ya que $a,b,c,d$ eran elementos arbitrarios hemos probado que vale (1).

(2) es dejada al lector  

Proof. Sean $a,b,c\in L$, elementos fijos. Por la regla Superar un Supremo, basta con probar que $$\begin{array}{cc}aib& \le ai\left(bsc\right)\\ aic& \le ai\left(bsc\right)\end{array}$$ Pero estas dos desigualdades pueden ser facilmente probadas aplicando (2) del lema anterior. O sea que $\left(aib\right)s\left(aic\right)\le ai\left(bsc\right)$, de lo cual se deduce nuestro lema ya que $a,b,c$ eran elementos arbitrarios.  

Iterar supremos (resp. infimos) da supremos (resp. infimos), es decir:

Proof. Por induccion en $n$. Claramente el resultado vale para $n=2$. Supongamos vale para $n$ y veamos entonces que vale para $n+1$. Sean $a_1,...,a_{n+1}\in L$, fijos. Por hipotesis inductiva tenemos que

1. (1) $(...(a_{1}s{a}_2)s...)s{a}_n=sup\left(\right\{a_1,...,a_n\left\}\right)$

Veamos entonces que

1. (2) $\left(\right(...\left(a_{1}s{a}_2\right)s...\left)s{a}_n\right)s{a}_{n+1}=sup\left(\right\{a_1,...,a_{n+1}\left\}\right)$

Usando (1), es facil ver que $\left(\right(...\left(a_{1}s{a}_2\right)s...\left)s{a}_n\right)s{a}_{n+1}$ es cota superior de $\{a_1,...,a_{n+1}\}$. Supongamos que $z$ es otra cota superior. Ya que $z$ es tambien cota superior del conjunto $\{a_1,...,a_n\}$, por (1) tenemos que $$(...(a_{1}s{a}_2)s...)s{a}_n\le z$$ Pero entonces ya que $a_{n+1}\le z$, tenemos que $$\left(\right(...\left(a_{1}s{a}_2\right)s...\left)s{a}_n\right)s{a}_{n+1}\le z$$ con lo cual hemos probado (2). Ya que $a_1,...,a_{n+1}\in L$ eran elementos arbitrarios, hemos probado que vale el enunciado del lema para $n+1$.  

Dado que la distribucion de parentesis en una expresion de la forma $$(...(x_{1}s{x}_2)s...)s{x}_n$$ es irrelevante (ya que$s$es asociativa), en general suprimiremos los parentesis.

Una regla que hemos usado constantemente es la siguiente:

Regla Igualar un Supremo

1. Si ud esta intentando probar que en un poset $(P,\le )$ se da que $x=sup\left(S\right)$, desdoble su tarea en las dos tareas siguientes:

   1. - Probar que $x$ es cota superior de $S$

   2. - Probar que si $z$ es una cota superior de $S$, entonces $x\le z$

Concluimos la seccion con una regla que es una de las mas usadas por los matematicos:

Regla del Director de Cine Generoso

1. Si ud esta en el medio de una prueba y puede introducir un nuevo actor, hagalo!

Obviamente esta regla necesita explicacion. La cosa es asi, muchas veces en el desarrollo de una demostracion probamos que existe al menos un objeto con cierta propiedad $P.$ Por supuesto que en general puede haber varios objetos con dicha propiedad $P.$ Entonces la Regla del Director de Cine Generoso nos dice que introduzcamos un nuevo objeto en nuestro discurso diciendo “sea $a$ un elemento fijo tal que cumple $P$”. Este nuevo actor $a$ muchas veces nos ayuda a seguir con la demostracion. Cabe destacar que la Regla Pertenecer a la Imagen dada al final de la seccion anterior es un caso particular de la Regla del Director de Cine Generoso (por que?)

Las seis reglas consideradas estan muy vinculadas al concepto de inteligencia artificial ya que si quisieramos hacer un probador automatico del tipo de teoremas hechos en esta seccion, claramente estas reglas le darian una alternativa de busqueda que podria (y de hecho en muchos casos lo hace) dar el camino adecuado para obtener la prueba de un enunciado dado.