5.5 Reticulados complementados

Sea \((L,\mathsf{s},\mathsf{i},0,1)\) un reticulado acotado. Dado \(a\in L\), diremos que \(a\) es complementado cuando exista un elemento \(b\in L\) (llamado complemento de a) tal que: \[\begin{aligned} a\;\mathsf{s\;}b & =1\\ a\;\mathsf{i\;}b & =0 \end{aligned}\] Notese que dicho elemento \(b\) puede no ser unico, es decir \(a\) puede tener varios complementos. Recordemos que una operacion unaria sobre un conjunto \(L\) es por definicion una funcion de \(L\) en \(L\). Muchas veces si \(s\) denota una operacion unaria, entonces escribiremos \(x^{s}\) en lugar de \(s(x)\). Por un reticulado complementado entederemos una \(6\)-upla \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) tal que \((L,\mathsf{s},\mathsf{i},0,1)\) es un reticulado acotado y \(^{c}\) es una operacion unaria sobre \(L\) tal que

  1. adhocprefix(I10)adhocsufix \(x\mathsf{\;s\;}x^{c}=1\), para cada \(x\in L\)

  2. adhocprefix(I11)adhocsufix \(x\mathsf{\;i\;}x^{c}=0\), para cada \(x\in L\)

Dado un reticulado acotado \((L,\mathsf{s},\mathsf{i},0,1)\) puede haber mas de una operacion unaria \(g\) tal que \((L,\mathsf{s},\mathsf{i},g,0,1)\) resulte un reticulado complementado. Intente dar un ejemplo en el cual \(L\) tenga 5 elementos.

Reflexion Informatica

Notese que si tenemos un reticulado par \((L,\leq)\) en el cual hay un maximo \(1\) y un minimo \(0\) y ademas tenemos una funcion \(g:L\rightarrow L\) tal que \[\begin{aligned} \sup\{x,g(x)\} & =1\\ \inf\{x,g(x)\} & =0 \end{aligned}\] para cada \(x\in L\), entonces podemos definir \[\begin{array}{rcl} \mathsf{s}:L^{2} & \rightarrow & L\\ (a,b) & \rightarrow & \sup(\{a,b\}) \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rcl} \mathsf{i}:L^{2} & \rightarrow & L\\ (a,b) & \rightarrow & \inf(\{a,b\}) \end{array}\] y se obtiene que \((L,\mathsf{s},\mathsf{i},g,0,1)\) es un reticulado complementado. Ademas todo reticulado complementado se obtiene de esta forma (por que?). O sea que a nivel de informacion, tener un reticulado par con \(0\) y \(1\) junto con una operacion unaria que da complementos, es exactamente lo mismo que tener un reticulado complementado.

El orden asociado a un reticulado complementado

Dado un reticulado complementado \((L,\mathsf{s},\mathsf{i},^{c},0,1)\), llamaremos a \(\mathrm{\leq}=\{(x,y):x\;\mathsf{s}\;y=y\}\) el orden parcial asociado a \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) y \((L\leq)\) sera llamado el poset asociado a \((L,\mathsf{s},\mathsf{i},^{c},0,1)\). Notese que tambien tenemos que \(\mathrm{\leq}=\{(x,y):x\;\mathsf{i}\;y=x\}\) (¿por que?).

Convencion notacional

Muchos conceptos definidos para posets, reticulados terna o reticulados acotados, pueden aplicarse cuando tenemos un reticulado complementado \((L,\mathsf{s},\mathsf{i},^{c},0,1)\). Por ejemplo, si decimos que en \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) el elemento \(a\) es cubierto por \(b\), esto significara que en el poset \((L,\leq)\) el elemento \(a\) es cubierto por \(b\). Si decimos que en \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) se da que el supremo de un conjunto \(S\) es \(a\), nos estaremos refiriendo a que en su poset asociado \((L,\leq)\) se da que el supremo de \(S\) es \(a\). Si decimos que \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) es distributivo nos estaremos refiriendo a que \((L,\mathsf{s},\mathsf{i})\) lo es. Si decimos que en \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) el elemento \(a\) es un complemento del elemento \(b\), nos estaremos refiriendo a que esto sucede en \((L,\mathsf{s},\mathsf{i},0,1)\). Aqui es importante notar que por el hecho de saber que \(a\) sea un complemento de \(b\) en \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) no podemos inferir que \(a=b^{c}\).

5.5.1 Subreticulados complementados

Dados reticulados complementados \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) y \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},^{c^{\prime}},0^{\prime},1^{\prime})\) diremos que \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) es un subreticulado complementado de \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},^{c^{\prime}},0^{\prime},1^{\prime})\) si se dan las siguientes condiciones

  1. adhocprefix(1)adhocsufix \(L\subseteq L^{\prime}\)

  2. adhocprefix(2)adhocsufix \(L\) es cerrado bajo las operaciones \(\mathsf{s}^{\prime}\), \(\mathsf{i}^{\prime}\) y \(^{c^{\prime}}\)

  3. adhocprefix(3)adhocsufix \(0=0^{\prime}\) y \(1=1^{\prime}\)

  4. adhocprefix(4)adhocsufix \(\mathsf{s}=\mathsf{s}^{\prime}\)\(|\)\(_{L\times L}\), \(\mathsf{i}=\mathsf{i}^{\prime}\)\(|\)\(_{L\times L}\) y \(^{c}=\ ^{c^{\prime}}\)\(|\)\(_{L}\)

Sea \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) un reticulado complementado. Un conjunto \(S\subseteq L\) es llamado subuniverso de \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) si \(0,1\in S\) y ademas \(S\) es cerrado bajo las operaciones \(\mathsf{s}\), \(\mathsf{i}\) y \(^{c}\). Es importante notar que si bien los conceptos de subreticulado complementado y subuniverso estan muy relacionados, se trata de conceptos diferentes ya que los subreticulados complementados de \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) son reticulados complementados, es decir \(6\)-uplas y los subuniversos de \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) son conjuntos, por lo cual no son \(6\)-uplas.

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

5.5.2 Homomorfismos de reticulados complementados

Sean \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) y \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},^{c^{\prime}},0^{\prime},1^{\prime})\) reticulados complementados. Una funcion \(F:L\rightarrow L^{\prime}\) sera llamada un homomorfismo de \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},^{c^{\prime}},0^{\prime},1^{\prime})\) si para todo \(x,y\in L\) se cumple que \[\begin{aligned} F(x\mathsf{\;s\;}y) & =F(x)\;\mathsf{s}^{\prime}\ F(y)\\ F(x\mathsf{\;i\;}y) & =F(x)\;\mathsf{i}^{\prime}\ F(y)\\ F(x^{c}) & =F(x)^{c^{\prime}}\\ F(0) & =0^{\prime}\\ F(1) & =1^{\prime} \end{aligned}\] Un homomorfismo de \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},^{c^{\prime}},0^{\prime},1^{\prime})\) sera llamado isomorfismo cuando sea biyectivo y su inversa sea un homomorfismo. Como es usual usaremos el simbolo \(\cong\) para denotar la relacion de isomorfismo. Escribiremos "Sea \(F:(L,\mathsf{s},\mathsf{i},^{c},0,1)\rightarrow(L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},^{c^{\prime}},0^{\prime},1^{\prime})\) un homomorfismo" para expresar que \(F\) es un homomorfismo de \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},^{c^{\prime}},0^{\prime},1^{\prime})\). No hay que confundirse al leer esta notacion y pensar que \(F\) es una funcion cuyo dominio es \((L,\mathsf{s},\mathsf{i},^{c},0,1)\), lo cual por otra parte no tiene sentido ya que el dominio de una funcion nunca puede ser una \(6\)-upla!

5.20. Si \(F:(L,\mathsf{s},\mathsf{i},^{c},0,1)\rightarrow(L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},^{c^{\prime}},0^{\prime},1^{\prime})\) un homomorfismo biyectivo, entonces \(F\) es un isomorfismo

Proof. Es dejada al lector.  


5.21. Si \(F:(L,\mathsf{s},\mathsf{i},^{c},0,1)\rightarrow(L^{\prime},\mathsf{s}^{\prime}\),\(\mathsf{i}^{\prime},^{c^{\prime}},0^{\prime},1^{\prime})\) es un homomorfismo, entonces \(I_{F}\) es un subuniverso de \((L^{\prime},\mathsf{s}^{\prime}\),\(\mathsf{i}^{\prime},^{c^{\prime}},0^{\prime},1^{\prime})\). Es decir que \(F\) es tambien un homomorfismo de \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) en \((I_{F},\mathsf{s}^{\prime}\)\(|\)\(_{I_{F}\times I_{F}},\mathsf{i}^{\prime}\)\(|\)\(_{I_{F}\times I_{F}},^{c^{\prime}},0^{\prime},1^{\prime})\)

Proof. Es dejada al lector.  


5.5.3 Congruencias de reticulados complementados

Sea \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) un reticulado complementado. Una congruencia sobre \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) sera una relacion de equivalencia sobre \(L\) la cual cumpla:

  1. adhocprefix(1)adhocsufix \(\theta\) es una congruencia sobre \((L,\mathsf{s},\mathsf{i},0,1)\)

  2. adhocprefix(2)adhocsufix \(x/\theta=y/\theta\) implica \(x^{c}/\theta=y^{c}/\theta\)

Las condiciones anteriores nos permiten definir sobre \(L/\theta\) dos operaciones binarias \(\mathsf{\tilde{s}}\) e \(\mathsf{\tilde{\imath}}\), y una operacion unaria \(^{\tilde{c}}\) de la siguiente manera: \[\begin{aligned} x/\theta\mathsf{\;\tilde{s}\;}y/\theta & =(x\mathsf{\;s\;}y)/\theta\\ x/\theta\mathsf{\;\tilde{\imath}\;}y/\theta & =(x\mathsf{\;i\;}y)/\theta\\ (x/\theta)^{\tilde{c}} & =x^{c}/\theta \end{aligned}\] La \(6\)-upla \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}},^{\tilde{c}},0/\theta,1/\theta)\) es llamada el cociente de \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) sobre \(\theta\) y la denotaremos con \((L,\mathsf{s},\mathsf{i},^{c},0,1)/\theta\). Tal como era de esperar tenemos entonces

5.22. Sea \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) un reticulado complementado y sea \(\theta\) una congruencia sobre \((L,\mathsf{s},\mathsf{i},^{c},0,1)\).

  1. adhocprefix(a)adhocsufix \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}},^{\tilde{c}},0/\theta,1/\theta)\) es un reticulado complementado.

  2. adhocprefix(b)adhocsufix \(\pi_{\theta}\) es un homomorfismo de \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) en \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}},^{\tilde{c}},0/\theta,1/\theta)\) cuyo nucleo es \(\theta\).

Proof. (a) Por un lema anterior ya sabemos que \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}},0/\theta,1/\theta)\) es un reticulado acotado. Es decir que solo nos falta ver que \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}},^{\tilde{c}},0/\theta,1/\theta)\) sarisface las identidades (I10) y (I11). Veamos por ejemplo que satisface la (I10). Sea \(x/\theta\) un elemento cualquiera de \(L/\theta\). Ya que \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) satisface la (I10), tenemos que \(x\mathsf{\;s\;}x^{c}=1\). O sea que \((x\mathsf{\;s\;}x^{c})/\theta=1/\theta\) y por lo tanto \(x/\theta\mathsf{\;\tilde{s}\;}x^{c}/\theta=1/\theta\). Pero por definicion de \(^{\tilde{c}}\) tenemos que \((x/\theta)^{\tilde{c}}=x^{c}/\theta\), lo cual nos dice que \(x/\theta\mathsf{\;\tilde{s}\;}(x/\theta)^{\tilde{c}}=1/\theta\). Dejamos al lector ver que \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}},^{\tilde{c}},0/\theta,1/\theta)\) sarisface la identidad (I11)

(b) Por el Lema 5.18 tenemos que \(\pi_{\theta}\) es un homomorfismo de \((L,\mathsf{s},\mathsf{i},0,1)\) en \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}},0/\theta,1/\theta)\) cuyo nucleo es \(\theta\). Notese que por definicion de \(^{\tilde{c}}\) tenemos que \(x^{c}/\theta=(x/\theta)^{\tilde{c}}\), es decir \(\pi_{\theta}(x^{c})=(\pi_{\theta}(x))^{\tilde{c}}\), cualquiera sea \(x\in L\)  


5.23. Si \(F:(L,\mathsf{s},\mathsf{i},^{c},0,1)\rightarrow(L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},^{c^{\prime}},0^{\prime},1^{\prime})\) es un homomorfismo de reticulados complementados, entonces \(\ker F\) es una congruencia sobre \((L,\mathsf{s},\mathsf{i},^{c},0,1)\)

Proof. Ya que \(F\) es un homomorfismo de \((L,\mathsf{s},\mathsf{i},0,1)\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},0^{\prime},1^{\prime})\) tenemos que por un lema anterior \(\ker F\) es una congruencia sobre \((L,\mathsf{s},\mathsf{i},0,1)\). Es decir que solo falta probar que para todos \(x,y\in L\), se tiene que \(x/\ker F=y/\ker F\) implica \(x^{c}/\ker F=y^{c}/\ker F\), lo cual es dejado al lector