5.3 Reticulados terna

De la diversas propiedades de las operaciones $s$ e $i$ de un reticulado par $(L,\le )$ distinguiremos las siguientes:

1. (I1) $xsx=xix=x$, cualesquiera sea $x\in L$

2. (I2) $xsy=ysx$, cualesquiera sean $x,y\in L$

3. (I3) $xiy=yix$, cualesquiera sean $x,y\in L$

4. (I4) $\left(xsy\right)sz=xs\left(ysz\right)$, cualesquiera sean $x,y,z\in L$

5. (I5) $\left(xiy\right)iz=xi\left(yiz\right)$, cualesquiera sean $x,y,z\in L$

6. (I6) $xs\left(xiy\right)=x$, cualesquiera sean $x,y\in L$

7. (I7) $xi\left(xsy\right)=x$, cualesquiera sean $x,y\in L$

Podemos abstraernos y pensar que $s$ e $i$ son dos operaciones binarias cualesquiera sobre un conjunto $L$ arbitrario y estudiar cuando se satisfacen y cuando no dichas propiedades. Por ejemplo si tomamos $L=R$ y $$\begin{array}{ccc}s:R^2& \to & R\\ (a,b)& \to & a+b\end{array}\begin{array}{ccc}i:R^2& \to & R\\ (a,b)& \to & a.b\end{array}$$ entonces se cumplen (I2), (I3), (I4) e (I5), pero (I1), (I6) e (I7) no se cumplen. Otro ejemplo, si tomamos $L=\{1,2\}$ y $$\begin{array}{ccc}s:\{1,2{\}}^2& \to & \{1,2\}\\ (1,1)& \to & 1\\ (1,2)& \to & 2\\ (2,1)& \to & 1\\ (2,2)& \to & 2\end{array}\begin{array}{ccc}i:\{1,2{\}}^2& \to & \{1,2\}\\ (1,1)& \to & 1\\ (1,2)& \to & 1\\ (2,1)& \to & 1\\ (2,2)& \to & 1\end{array}$$ entonces se cumplen (I3), (I4) e (I5), pero (I1), (I2), (I6) e (I7) no se cumplen. Un tercer ejemplo, si tomamos $L=N$ y $$\begin{array}{ccc}s:N^2& \to & N\\ (a,b)& \to & max\{a,b\}\end{array}\begin{array}{ccc}i:N^2& \to & N\\ (a,b)& \to & \text{maximo comun divisor de}a\text{y}b\end{array}$$ entonces se cumplen (I1), (I2), (I3), (I4), (I5) e (I6), pero (I7) no se cumple. Por supuesto si $s$ e $i$ son las operaciones supremo e infimo dadas por algun orden parcial $\le$ sobre $L$ el cual hace de $(L,\le )$ un reticulado par, entonces las propedades (I1),...,(I7) se cumplen y esto es justamente lo probado en la ultima serie de lemas. El ultimo ejemplo nos permite ver una sutileza. Notese que en este ejemplo $s$ es la operacion supremo del reticulado par $(N,\le )$, donde $\le$ es el orden usual de los naturales, e $i$ es la operacion infimo del reticulado par $(N,|)$, donde $|$ es el orden de la divisibilidad de los naturales. Sin envargo la ultima propiedad falla y esto se debe a que $s$ e $i$ son supremo e infimo pero respecto de distintos ordenes parciales.

Lo anterior motiva la siguiente definicion:

Por un reticulado terna entenderemos una terna $(L,s,i)$, donde $L$ es un conjunto no vacio y $s$ e $i$ son dos operaciones binarias sobre $L$ para las cuales se cumplen (I1),...,(I7). Si $(L,s,i)$ es un reticulado terna, llamaremos a $L$ el universo de $(L,s,i)$.

Tal como lo vimos recien, las ternas dadas por los tres ejemplos anteriores no son reticulados terna ya que no cumplen alguna de las identidades (I1),...,(I7), y si tomamos un poset $(L,\le )$ el cual sea un reticulado par, entonces la terna $(L,s,i)$, con $s$ e $i$ definidas como supremo e infimo, es un reticulado terna. El siguiente teorema muestra que todo reticulado terna $(L,s,i)$ se obtiene de esta forma.

Proof. Dejamos como ejercicio para el lector probar que $\le$ es reflexiva y antisimetrica con respecto a $L$. Veamos que $\le$ es transitiva con respecto a $L$. Supongamos que $x\le y$ e $y\le z$. Es decir que por definicion de $\le$ tenemos que $$\begin{array}{cc}xsy& =y\\ ysz& =z\end{array}$$ Entonces $$xsz=xs\left(ysz\right)=\left(xsy\right)sz=ysz=z$$ por lo cual $x\le z$. O sea que ya sabemos que $(L,\le )$ es un poset. Veamos ahora que $sup\left(\right\{x,y\left\}\right)=xsy$. Primero debemos ver que $xsy$ es una cota superior del conjunto $\{x,y\}$, es decir $$\begin{array}{cc}x& \le xsy\\ y& \le xsy\end{array}$$ Por la definicion de $\le$ debemos probar que $$\begin{array}{cc}xs\left(xsy\right)& =xsy\\ ys\left(xsy\right)& =xsy\end{array}$$ Estas igualdades se pueden probar usando (I1), (I2) y (I4). Dejamos al lector hacerlo como ejercicio.

Nos falta ver entonces que $xsy$ es menor o igual que cualquier cota superior de $\{x,y\}$. Supongamos $x,y\le z$. Es decir que por definicion de $\le$ tenemos que $$\begin{array}{cc}xsz& =z\\ ysz& =z\end{array}$$ Pero entonces $$\left(xsy\right)sz=xs\left(ysz\right)=xsz=z$$ por lo que $xsy\le z$. Es decir que $xsy$ es la menor cota superior.

Para probar que $inf\left(\right\{x,y\left\}\right)=xiy$, probaremos que para todo $u,v\in L$, $$u\le v\text{si y solo si}uiv=u$$ lo cual le permitira al lector aplicar un razonamiento similar al usado en la prueba de que $sup\left(\right\{x,y\left\}\right)=xsy$. Supongamos que $u\le v$. Por definicion tenemos que $usv=v$. Entonces $$uiv=ui\left(usv\right)$$ Pero por (I7) tenemos que $ui\left(usv\right)=u$, lo cual implica $uiv=u$. Reciprocamente si $uiv=u$, entonces $$\begin{array}{cc}usv& =\left(uiv\right)sv\\ & =vs\left(uiv\right)\text{(por (I2))}\\ & =vs\left(viu\right)\text{(por (I3))}\\ & =v\text{(por (I6))}\end{array}$$ lo cual nos dice que $u\le v$.  

1. Ejercicio: Use los resultados anteriores para definir una funcion $F$ de $\left\{\right(L,\le ):(L,\le )$ es un reticulado par$\}$ en $\left\{\right(L,s,i):(L,s,i)$ es un reticulado terna$\}$ la cual sea biyectiva

Refleccion Informatica

Como vimos recien a nivel de informacion es lo mismo tener un reticulado par que un reticulado terna. Es decir, los dos conceptos pueden considerarse dos formas distintas de presentar la misma informacion. Muchas veces esta informacion es mas facil de dar dando el poset ya que simplemente podemos dar su diagrama de Hasse y esto en general es una forma economica de dar las operaciones $s$ e $i$.

Recordemos que algo similar sucedia con los conceptos equivalentes de relacion de equivalencia y particion.

El orden asociado a un reticulado terna

Como vimos el Teorema de Dedekind nos dice que un reticulado terna $(L,s,i)$ es un objeto geometrico ya que si definimos $$\le =\left\{\right(x,y):xsy=y\}$$ entonces $\le$ es un orden parcial sobre $L$ y las operaciones $s$ e $i$ resultan ser supremo e infimo respecto de este orden parcial. Llamaremos a $\le =\left\{\right(x,y):xsy=y\}$ el orden parcial asociado a $(L,s,i)$ y a $(L,\le )$ el poset asociado a $(L,s,i)$. Notese que tambien tenemos que $\le =\left\{\right(x,y):xiy=x\}$ (¿por que?).

Convencion notacional

Muchos conceptos definidos para posets ahora pueden aplicarse cuando tenemos un reticulado terna $(L,s,i)$. Por ejemplo, si decimos que $(L,s,i)$ tiene elemento maximo, esto significara que el poset $(L,\le )$ tiene elemento maximo. Otro ejemplo, si decimos que en $(L,s,i)$ se da que el supremo de un conjunto $S$ es $a$, nos estaremos refiriendo a que en su poset asociado $(L,\le )$ se da que el supremo de $S$ es $a$.

Convencion notacional

Usaremos las siguientes practicas convenciones notacionales

1. Convencion notacional 1: Si $L$ es un conjunto no vacio cuyos elementos son conjuntos y $L$ cumple la siguiente condicion

   1. - Si $A,B\in L$, entonces $A\cup B,A\cap B\in L$

   entonces ciertas veces usaremos $\cup$ (resp. $\cap$) para denotar la operacion binaria sobre $L$ dada por la union (resp. la interceccion). Es decir $\cup$ e $\cap$ denotaran las funciones $$\begin{array}{ccc}{L}^2& \to & L\\ (A,B)& \to & A\cup B\end{array}\begin{array}{ccc}{L}^2& \to & L\\ (A,B)& \to & A\cap B\end{array}$$

2. Convencion notacional 2: Si $L$ es un conjunto no vacio cuyos elementos son numeros reales entonces ciertas veces usaremos $max$ y $min$ para denotar las operaciones binarias sobre $L$ dadas por $$\begin{array}{ccc}{L}^2& \to & L\\ (a,b)& \to & max(a,b)\end{array}\begin{array}{ccc}{L}^2& \to & L\\ (a,b)& \to & min(a,b)\end{array}$$

3. Convencion notacional 3: Si $L$ es un conjunto no vacio cuyos elementos son numeros naturales y $L$ cumple la siguiente condicion

   1. - Si $a,b\in L$, entonces $mcm(a,b),mcd(a,b)\in L$

   entonces ciertas veces usaremos $mcm$ y $mcd$ para denotar las operaciones binarias sobre $L$ dadas por $$\begin{array}{ccc}{L}^2& \to & L\\ (a,b)& \to & mcm(a,b)\end{array}\begin{array}{ccc}{L}^2& \to & L\\ (a,b)& \to & mcd(a,b)\end{array}$$

4. Convencion notacional 4: Si $P$ es un conjunto no vacio contenido en $N$, entonces escribiremos $(P,|)$ para denotar al poset $(P,\{(x,y)\in P^2:x|y\left\}\right)$. Similarmente si $P$ es un conjunto cuyos elementos son conjuntos, entonces escribiremos $(P,\subseteq )$ para denotar al poset $(P,\{(A,B)\in P^2:A\subseteq B\left\}\right)$

En virtud de las convenciones notacionales anteriores notese que por ejemplo

1. $(R,max,min)$

2. $\left(\right[0,1],max,min)$

3. $\left(P\right(N),\cup ,\cap )$

4. $\left(\right\{A\subseteq N:A$ es finito$\},\cup ,\cap )$

5. $(N,mcm,mcd)$

6. $\left(\right\{1,2,3,6,12\},mcm,mcd)$

denotan reticulados terna pero deberia quedar claro que en los primeros dos ejemplos $max$ denota dos distintas operaciones. Analogamente sucede con $min$, $\cup$, $\cap$, $mcm$ y $mcd$.

Similarmente

1. $\left(N,|\right)$

2. $\left(\right\{1,2,3,6,7\},|)$

3. $\left(\right\{\left\{1\right\},\{1,7\},\{1,2,3\},\{16,99,65\}\},\subseteq )$

4. $\left(\right\{A\subseteq N:A$ es finito$\},\subseteq )$

denotan posets pero deberia quedar claro que en los primeros dos ejemplos $|$ denota dos distintos ordenes parciales. Analogamente sucede con $\subseteq$

Estas ambiguedades no nos traeran problemas si estamos atentos al contexto.

5.3.1 Subreticulados terna

Si $f$ es una operacion $n$-aria sobre $A$ y $S\subseteq A$, entonces diremos que $S$ es cerrado bajo $f$ cuando se de que $f(a_1,...,a_n)\in S$, cada ves que $a_1,...,a_n\in S$. Notese que si $n=0$, entonces $S$ es cerrado bajo $f$ si y solo si $f\left(◊\right)\in S$.

Dados reticulados terna $(L,s,i)$ y $(L^{\prime },s^{\prime },i^{\prime })$ diremos que $(L,s,i)$ es un subreticulado terna de $(L^{\prime },s^{\prime },i^{\prime })$ si se dan las siguientes condiciones

1. (1) $L\subseteq L^{\prime }$

2. (2) $L$ es cerrado bajo las operaciones $s^{\prime }$ e $i^{\prime }$

3. (3) $s=s^{\prime }$$|$${}_{L\times L}$ y $i=i^{\prime }$$|$${}_{L\times L}$

Sea $(L,s,i)$ un reticulado terna. Un conjunto $S\subseteq L$ es llamado subuniverso de $(L,s,i)$ si es no vacio y cerrado bajo las operaciones $s$ e $i$. Es importante notar que si bien los conceptos de subreticulado terna y subuniverso estan muy relacionados, se trata de conceptos diferentes ya que los subreticulados terna de $(L,s,i)$ son reticulados terna, es decir ternas y los subuniversos de $(L,s,i)$ son conjuntos, por lo cual no son ternas.

Es facil de chequear que si $S$ es un subuniverso de $(L,s,i)$, entonces $(S,s{\mid }_{S\times S},i{\mid }_{S\times S})$ es un subreticulado terna de $(L,s,i)$ y que todo subreticulado terna de $(L,s,i)$ se obtiene en esta forma. Es decir, hay una biyeccion entre el conjunto de los subreticulados terna de $(L,s,i)$ y el conjunto de los subuniversos de $(L,s,i)$ (cual es?). Dicho de manera mas rapida: los subuniversos de $(L,s,i)$ son ni mas ni menos que los universos de los subreticulados terna de $(L,s,i)$.

5.3.2 Homomorfismos de reticulados terna

Sean $(L,s,i)$ y $(L^{\prime },s^{\prime },i^{\prime })$ reticulados terna. Una funcion $F:L\to L^{\prime }$ sera llamada un homomorfismo de $(L,s,i)$ en $(L^{\prime },s^{\prime },i^{\prime })$ si para todo $x,y\in L$ se cumple que $$\begin{array}{cc}F\left(xsy\right)& =F\left(x\right)s^{\prime }F\left(y\right)\\ F\left(xiy\right)& =F\left(x\right)i^{\prime }F\left(y\right).\end{array}$$ Un homomorfismo de $(L,s,i)$ en $(L^{\prime },s^{\prime },i^{\prime })$ sera llamado isomorfismo de $(L,s,i)$ en $(L^{\prime },s^{\prime }$, $i^{\prime }$ $)$ cuando sea biyectivo y su inversa sea tambien un homomorfismo. Escribiremos $(L,s,i)\cong (L^{\prime },s^{\prime },i^{\prime })$ cuando exista un isomorfismo de $(L,s,i)$ en $(L^{\prime },s^{\prime },i^{\prime })$. Escribiremos "Sea $F:(L,s,i)\to (L^{\prime },s^{\prime },i^{\prime })$ un homomorfismo" para expresar que $F$ es un homomorfismo de $(L,s,i)$ en $(L^{\prime },s^{\prime },i^{\prime })$. No hay que confundirse al leer esta notacion y pensar que $F$ es una funcion cuyo dominio es $(L,s,i)$, lo cual por otra parte no tiene sentido ya que el dominio de una funcion nunca puede ser una $3$-upla!

Proof. Solo falta ver que $F^{-1}$ es un homomorfismo. Sean $F\left(x\right),F\left(y\right)$ dos elementos cualesquiera de $L^{\prime }$. Tenemos que $$F^{-1}\left(F\right(x\left)s^{\prime }F\right(y\left)\right)=F^{-1}\left(F\right(xsy\left)\right)=xsy=F^{-1}\left(F\right(x\left)\right)s{F}^{-1}\left(F\right(y\left)\right)$$  

Proof. Ya que $L$ es no vacio tenemos que $I_F$ tambien es no vacio. Sean $a,b\in I_F$. Sean $x,y\in L$ tales que $F\left(x\right)=a$ y $F\left(y\right)=b$. Se tiene que $$\begin{array}{cc}a{s}^{\prime }b& =F\left(x\right)s^{\prime }F\left(y\right)=F\left(xsy\right)\in I_F\\ a{i}^{\prime }b& =F\left(x\right)i^{\prime }F\left(y\right)=F\left(xiy\right)\in I_F\end{array}$$ por lo cual $I_F$ es cerrada bajo $s^{\prime }$ e $i^{\prime }$.  

Proof. Supongamos $F$ es un isomorfismo de $(L,s,i)$ en $(L^{\prime },s^{\prime },i^{\prime })$. Sean $x,y\in L$, tales que $x\le y$. Tenemos que $y=xsy$ por lo cual $F\left(y\right)=F\left(xsy\right)=F\left(x\right)s^{\prime }F\left(y\right)$, produciendo $F\left(x\right){\le }^{\prime }F\left(y\right)$. En forma similar se puede ver que $F^{-1}$ es tambien un homomorfismo de $(L^{\prime },{\le }^{\prime })$ en $(L,\le )$. Si $F$ es un isomorfismo de $(L,\le )$ en $(L^{\prime },{\le }^{\prime })$, entonces (g) y (h) del Lema 5.1 nos dicen que $F$ y $F^{-1}$ son homomorfismos (de reticulados terna terna) por lo cual $F$ es un isomorfismo de $(L,s,i)$ en $(L^{\prime },s^{\prime },i^{\prime })$.  

1. Ejercicio: Encontrar dos reticulados terna, $(L,s,i)$ y $(L^{\prime },s^{\prime },i^{\prime })$, tales que haya una función biyectiva de $L$ en $L^{\prime }$ que preserve orden pero no sea homomorfismo de reticulados terna.

5.3.3 Congruencias de reticulados terna

Sea $(L,s,i)$ un reticulado terna. Una congruencia sobre $(L,s,i)$ sera una relacion de equivalencia $\theta$ sobre $L$ la cual cumpla:

1. (1) $x\theta x^{\prime }$ y $y\theta y^{\prime }$ implica $\left(xsy\right)\theta \left(x^{\prime }s{y}^{\prime }\right)$ y $\left(xiy\right)\theta \left(x^{\prime }i{y}^{\prime }\right)$

Gracias a esta condicion podemos definir en forma inambigua sobre $L/\theta$ dos operaciones binarias $\tilde{s}$ e $\tilde{ı}$, de la siguiente manera: $$\begin{array}{cc}x/\theta \tilde{s}y/\theta & =\left(xsy\right)/\theta \\ x/\theta \tilde{ı}y/\theta & =\left(xiy\right)/\theta \end{array}$$

Veamos algunos ejemplos:

1. (E1) Consideremos el reticulado terna $\left(\right\{1,2,3,4,5,6\},max,min)$. O sea que aqui $L=\{1,2,3,4,5,6\}$, $s$ es la operacion $max$ sobre $L$ y $i$ es la operacion $min$ sobre $L$. Sea $\theta$ la relacion de equivalencia sobre $\{1,2,3,4,5,6\}$ dada por la particion $\left\{\right\{1,2\},\{3\},\{4,5\left\}\right\}$. Se puede chequear que $\theta$ es una congruencia, es decir satisface (1) de arriba. Notese que $$\begin{array}{cc}L/\theta & =\left\{\right\{1,2\},\{3\},\{4,5\left\}\right\}\\ \tilde{s}& =\widetilde{max}:L/\theta \times L/\theta \to L/\theta \\ \tilde{ı}& =\widetilde{min}:L/\theta \times L/\theta \to L/\theta \end{array}$$ Por ejemplo tenemos que $$\{1,2\}\widetilde{max}\left\{3\right\}=\left\{3\right\}$$ ya que $\{1,2\}\widetilde{max}\left\{3\right\}=1/\theta \widetilde{max}3/\theta =(1max3)/\theta =3/\theta =\left\{3\right\}$ (escribimos $1max3$ en lugar de $max(1,3)$). Similarmente tenemos que $$\begin{array}{cc}\{4,5\}\widetilde{max}\left\{3\right\}& =\{4,5\}\\ \{1,2\}\widetilde{min}\{4,5\}& =\{1,2\}\end{array}$$

2. (E2) Consideremos el reticulado terna $\left(\right\{1,2,3,6\},mcm,mcd)$ (o sea el rombo) y sea $\theta$ la relacion de equivalencia dada por la particion $\left\{\right\{1,2\},\{3\},\{6\left\}\right\}$ (haga un dibujo). Entonces $\theta$ no es una congruencia sobre $\left(\right\{1,2,3,6\},mcm,mcd)$. Esto es ya que si tomamos $$\begin{array}{cc}x& =1\\ x^{\prime }& =2\\ y& =3\\ y^{\prime }& =3\end{array}$$ no se cumple la implicacion de (1) de la definicion de congruencia.

La terna $(L/\theta ,\tilde{s},\tilde{ı})$ es llamada el cociente de $(L,s,i)$ sobre $\theta$ y la denotaremos con $(L,s,i)/\theta$.

Proof. Veamos que la estructura $(L/\theta ,\tilde{s},\tilde{ı})$ cumple (I4). Sean $x/\theta$, $y/\theta$, $z/\theta$ elementos cualesquiera de $L/\theta$. Tenemos que $$\begin{array}{ccc}\left(x/\theta \tilde{s}y/\theta \right)\tilde{s}z/\theta & =& \left(xsy\right)/\theta \tilde{s}z/\theta \\ & =& \left(\right(xsy\left)sz\right)/\theta \\ & =& \left(xs\right(ysz\left)\right)/\theta \\ & =& x/\theta \tilde{s}\left(ysz\right)/\theta \\ & =& x/\theta \tilde{s}\left(y/\theta \tilde{s}z/\theta \right)\end{array}$$ En forma similar se puede ver que la estructura $(L/\theta ,\tilde{s},\tilde{ı})$ cumple el resto de las identidades que definen reticulado terna.  

Denotaremos con $\tilde{\le }$ al orden parcial asociado al reticulado terna $(L/\theta ,\tilde{s},\tilde{ı})$.

Proof. Por definicion de $\tilde{\le }$ tenemos que $x/\theta \tilde{\le }y/\theta$ sii $y/\theta =x/\theta \tilde{s}y/\theta$. Pero $x/\theta \tilde{s}y/\theta =\left(xsy\right)/\theta$ (por definicion de $\tilde{s}$) por lo cual tenemos que $x/\theta \tilde{\le }y/\theta$ sii $y/\theta =\left(xsy\right)/\theta$.  

Proof. Ya que $1=xs1$, para cada $x\in L$, tenemos que $1/\theta =\left(xs1\right)/\theta$, para cada $x\in L$, lo cual por el lema anterior nos dice que $x/\theta \tilde{\le }1/\theta$, para cada $x\in L$.  

El siguiente lema nos da una forma natural de encontrar congruencias

Proof. Dejamos al lector ver que $\ker F$ es una relacion de equivalencia. Supongamos $x\ker F{x}^{\prime }$ y $y\ker F{y}^{\prime }$. Entonces $$F\left(xsy\right)=F\left(x\right)s^{\prime }F\left(y\right)=F\left(x^{\prime }\right)s^{\prime }F\left(y^{\prime }\right)=F\left(x^{\prime }s{y}^{\prime }\right)$$ lo cual nos dice que $\left(xsy\right)\ker F\left(x^{\prime }s{y}^{\prime }\right)$. En forma similar tenemos que $\left(xiy\right)\ker F\left(x^{\prime }i{y}^{\prime }\right)$.  

Ya vimos que el nucleo de un homomorfismo es una congruencia. El siguiente lema muestra que toda congruencia es el nucleo de un homomorfismo.

Proof. Sean $x,y\in L$. Tenemos que $${\pi }_{\theta }\left(xsy\right)=\left(xsy\right)/\theta =x/\theta \tilde{s}y/\theta ={\pi }_{\theta }\left(x\right)\tilde{s}{\pi }_{\theta }\left(y\right)$$ por lo cual ${\pi }_{\theta }$ preserva la operacion supremo. Para la operacion infimo es similar.