2.1 Estructuras algebraicas ordenadas

En este capítulo estudiaremos varias clases de estructuras algebraicas en las cuales hay un orden parcial involucrado. Esto tendrá una triple utilidad. Por un lado algunos de los resultados probados sobre álgebras de Boole (por ejemplo el Teorema de Rasiowa y Sikorski) serán utilizados mas adelante para la prueba del Teorema de Completitud de la lógica de primer orden. También, este capítulo servirá para volvernos algebristas maduros (lo mas que se pueda) ya que esto nos será útil a la hora de hacer lógica matemática. La lógica matemática es matemática aplicada al estudio de los matemáticos, su lenguaje y sus métodos de demostración, y que mas cómodo para hacer lógica matemática que contar con un matemático dentro de uno mismo para estudiarlo!

Finalmente cabe destacar que los resultados cubiertos en este capítulo son importantes en si mismos fuera de su vinculación con la lógica y tienen fuertes aplicaciones en otras disciplinas y ramas de la matemática.

2.1.1 Conjuntos parcialmente ordenados

Una relación binaria \(R\) sobre un conjunto \(P\) es llamada un orden parcial sobre \(P\) si se cumplen las siguientes condiciones:

1. adhocprefix(1)adhocsufix \(R\) es reflexiva, i. e. para todo \(a\in P\), \(aRa\)

2. adhocprefix(2)adhocsufix \(R\) es antisimétrica, i. e. para todo \(a,b\in P\), si \(aRb\) y \(bRa\), entonces \(a=b.\)

3. adhocprefix(3)adhocsufix \(R\) es transitiva, i. e. para todo \(a,b,c\in P\), si \(aRb\) y \(bRc\), entonces \(aRc\).

Algunos ejemplos:

1. adhocprefix(E1)adhocsufix Sea \(R=\{(r,t)\in\mathbf{R}^{2}:r\leq t\}\). Entonces \(R\) es un orden parcial sobre \(\mathbf{R}\), llamado el orden usual de \(\mathbf{R}\)

2. adhocprefix(E2)adhocsufix Sea \(R=\{(1,2),(1,3),(1,1),(2,2),(3,3)\}\). Entonces \(R\) es un orden parcial sobre \(\{1,2,3\}\)

3. adhocprefix(E3)adhocsufix Sea \(R=\{(S,T)\in\mathcal{P}(\omega)^{2}:S\subseteq T\}\). Entonces \(R\) es un orden parcial sobre \(\mathcal{P}(\omega)\)

4. adhocprefix(E4)adhocsufix Sea \(R=\{(x,y)\in\omega^{2}:\) \(x\leq y\}\). Entonces \(R\) es un orden parcial sobre \(\omega\).

5. adhocprefix(E5)adhocsufix Sea \(R=\{(1,1)\}\). Entonces \(R\) es un orden parcial sobre \(\{1\}\).

6. adhocprefix(E6)adhocsufix \(\{(a,b)\in A^{2}:a=b\}\) es un orden parcial sobre \(A\), cualesquiera sea el conjunto \(A\)

7. adhocprefix(E7)adhocsufix Sea \(\mathrm{\leq}=\{(n,m)\in\mathbf{N}^{2}:n\mid m\}\). Es fácil ver que \(\leq\) es un orden parcial sobre \(\mathbf{N}\)

Nótese que las relaciones dadas en (E1) y (E4) son distintas, además la relación dada en (E4) no es un orden parcial sobre \(\mathbf{R}\) (por que?).

Muchas veces denotaremos con \(\leq\) a una relación binaria que sea un orden parcial. Esto hace mas intuitiva nuestra escritura pero siempre hay que tener en cuenta que \(\leq\) en estos casos esta denotando cierto conjunto de pares ordenados previamente definido.

Usaremos la siguiente

• Convención Notacional: Si hemos denotado con \(\leq\) a cierto orden parcial sobre un conjunto \(A\), entonces

  • Denotaremos con \(<\) a la relación binaria \(\{(a,b)\in A^{2}:a\leq b\) y \(a\neq b\}\). Es decir que \(\mathrm{<}=\{(a,b)\in A^{2}:a\leq b\) y \(a\neq b\}\). Cuando se dé \(a<b\) diremos que \(a\) es menor que \(b\) o que \(b\) es mayor que \(a\) (respecto de \(\leq\))

  • Denotaremos con \(\prec\) a la relación binaria \[\{(a,b)\in A^{2}:a<b\text{ y no existe }z\text{ tal que }a<z<b\}\] Cuando se dé \(a\prec b\) diremos que \(a\) es cubierto por \(b\) o que \(b\) cubre a \(a\) (respecto de \(\leq\))

Algunos ejemplos:

1. adhocprefix(E1)adhocsufix Si \(A=\mathbf{R}\) y \(\mathrm{\leq}=\{(r,t)\in\mathbf{R}^{2}:r=t\}\), entonces \(\mathrm{<}=\emptyset\)

2. adhocprefix(E2)adhocsufix Si \(A=\{1,2,3,4\}\) y \(\mathrm{\leq}=\{(1,2),(2,3),(1,3),(1,1),(2,2),(3,3),(4,4)\}\), entonces \(\mathrm{<}=\{(1,2),(2,3),(1,3)\}\) y \(\mathrm{\prec}=\{(1,2),(2,3)\}\). En particular tenemos que \(1\prec2\), \(1<3\) pero no se da que \(1\prec3\).

3. adhocprefix(E3)adhocsufix Si \(A=\mathcal{P}(\omega)\) y \(\mathrm{\leq}=\{(S,T)\in\mathcal{P}(\omega)^{2}:S\subseteq T\}\), entonces \(\mathrm{<}=\{(S,T)\in\mathcal{P}(\omega)^{2}:S\subsetneq T\}\) y \(S\prec T\) sii hay un \(n\in T-S\) tal que \(T=S\cup\{n\}\)

2.1.1.1 Ordenes totales sobre un conjunto

Sea \(A\) un conjunto cualquiera. Por un orden total sobre \(A\) entenderemos un orden parcial \(\leq\) sobre \(A\) el cual cumpla:

1. adhocprefix(C)adhocsufix \(a\leq b\) o \(b\leq a\), cualesquiera sean \(a,b\in A\)

Supongamos \(A\) es finito no vacío y \(\leq\) es un orden total sobre \(A\). La propiedad (C) nos permite probar que para cada conjunto no vacío \(S\subseteq A\), hay un elemento \(s\in S\) el cual cumple \(s\leq s^{\prime}\) para cada \(s^{\prime}\in S\). Por supuesto, \(s\) es único (por que?) y habitualmente es llamado el menor elemento de \(S\), ya que es menor que todo otro elemento de \(S\).

Si \(A\) es finito no vacío y \(\leq\) es un orden total sobre \(A\), podemos definir recursivamente una función \(f:\{1,...,\left\vert A\right\vert \}\rightarrow A\) de la siguiente manera:

1. adhocprefix-adhocsufix \(f(1)=\) menor elemento de \(A\)

2. adhocprefix-adhocsufix Si \(i\in\{1,...,\left\vert A\right\vert -1\}\), entonces

   1. adhocprefix-adhocsufix \(f(i+1)=\) menor elemento de \(A-\{f(1),...,f(i)\}\)

Como es habitual, \(f(i)\) es llamado el \(i\)-ésimo elemento de \(A\).

Muchas veces para dar un orden total sobre un conjunto finito \(A\), daremos simplemente sus elementos en forma creciente ya que esto determina el orden por completo. Por ejemplo si \(A=\{1,2,3\}\), el orden total dado por \(2<1<3\) es la relación \(\mathrm{\leq}=\{(2,1),(1,3),(2,3),(1,1),(2,2),(3,3)\}\).

Un concepto importante relativo a los ordenes totales es el de sucesor. Si \(\leq\) es un orden total sobre \(A\) y \(a,b\in A\), diremos que \(b\) es el sucesor de \(a\) cuando se dé que \(a<b\) y \(b\leq c\), para cada \(c\in A\) tal que \(a<c\), i.e., \(b\) es el menor elemento del conjunto \(\{c\in A:\) tal que \(a<c\}\). No siempre existe el sucesor de un elemento. Por ejemplo si \(\leq\) es el orden usual de \(\mathbf{R}\), entonces ningún elemento tiene sucesor (justifique).

2.1.1.2 Conjuntos parcialmente ordenados o posets

Un conjunto parcialmente ordenado o poset es un par \((P,\leq)\) donde \(P\) es un conjunto no vacío cualquiera y \(\leq\) es un orden parcial sobre \(P\). Dado un poset \((P,\leq)\), el conjunto \(P\) será llamado el universo de \((P,\leq)\). Algunos ejemplos:

1. adhocprefix(E1)adhocsufix \((\mathbf{R},\leq)\) es un poset, donde \(\leq\) es el orden usual de los números reales

2. adhocprefix(E2)adhocsufix \((\{1,2,3\},\{(1,2),(1,3),(1,1),(2,2),(3,3)\})\) es un poset

3. adhocprefix(E3)adhocsufix \((\mathcal{P}(\omega),\leq)\) es un poset, donde \(\mathrm{\leq}=\{(S,T)\in\mathcal{P}(\omega)^{2}:S\subseteq T\}\)

4. adhocprefix(E4)adhocsufix \((\{1\},\{(1,1)\}\) es un poset

5. adhocprefix(E5)adhocsufix \((\mathbf{N},\leq)\) es un poset, donde \(\mathrm{\leq}=\{(n,m)\in\mathbf{N}^{2}:n\mid m\}\)

6. adhocprefix(E6)adhocsufix \((A,\{(a,b)\in A^{2}:a=b\})\) es un poset, cualesquiera sea el conjunto no vacío \(A\)

2.1.1.3 Conjuntos totalmente ordenados

Un conjunto totalmente ordenado es un par \((P,\leq)\) donde \(P\) es un conjunto no vacío cualquiera y \(\leq\) es un orden total sobre \(P\). Note que entonces todo conjunto totalmente ordenado es un poset. Algunos ejemplos:

1. adhocprefix(E1)adhocsufix \((\mathbf{R},\leq)\) es un conjunto totalmente ordenado, donde \(\leq\) es el orden usual de los números reales

2. adhocprefix(E2)adhocsufix \((\{1,2,3\},\{(1,2),(2,3),(1,3),(1,1),(2,2),(3,3)\})\) es un un conjunto totalmente ordenado

3. adhocprefix(E3)adhocsufix \((\mathcal{P}(\omega),\leq)\) no es es un conjunto totalmente ordenado, donde \(\mathrm{\leq}=\{(S,T)\in\mathcal{P}(\omega)^{2}:S\subseteq T\}\)

4. adhocprefix(E4)adhocsufix \((\{1\},\{(1,1)\}\) es un conjunto totalmente ordenado

5. adhocprefix(E5)adhocsufix \((\{2^{n}:n\in\mathbf{N}\},\leq)\) es un conjunto totalmente ordenado, donde \(\mathrm{\leq}=\{(n,m)\in\mathbf{N}^{2}:n\mid m\}\)

2.1.1.4 Diagrama de Hasse de un poset

Dado un poset \((P,\leq)\) podemos realizar un diagrama de \((P,\leq)\), llamado diagrama de Hasse de \((P,\leq)\), siguiendo las siguientes instrucciones:

1. adhocprefix(1)adhocsufix Asociar en forma inyectiva, a cada \(a\in\) \(P\) un punto \(p_{a}\) del plano

2. adhocprefix(2)adhocsufix Trazar un segmento de recta uniendo los puntos \(p_{a}\) y \(p_{b}\), cada vez que \(a\prec b\)

3. adhocprefix(3)adhocsufix Realizar lo indicado en los puntos (1) y (2) en tal forma que

   1. adhocprefix(i)adhocsufix Si \(a\prec b\), entonces \(p_{a}\) esta por debajo de \(p_{b}\)

   2. adhocprefix(ii)adhocsufix Si un punto \(p_{a}\) ocurre en un segmento del diagrama entonces lo hace en alguno de sus extremos.

La relación de orden \(\leq\) puede ser fácilmente obtenida de su diagrama, a saber, \(a\leq b\) sucederá si y solo si \(p_{a}=p_{b}\) o hay una sucesión de segmentos ascendentes desde \(p_{a}\) hasta \(p_{b}\).

Ejemplos:

2.1.1.5 Elementos maximales, máximos, minimales y mínimos

Sea \((P,\leq)\) un poset. Diremos que \(a\in P\) es un elemento maximal de \((P,\leq)\) si no existe un \(b\in P\) tal que \(a<b\). Diremos que \(a\in P\) es un elemento máximo de \((P,\leq)\) si \(b\leq a\), para todo \(b\in P\). En forma análoga se definen los conceptos de elemento minimal y mínimo. Algunos ejemplos:

1. adhocprefix(E1)adhocsufix Sea \(\leq\) el orden usual de los números reales. El poset \((\mathbf{R},\leq)\) no tiene elemento máximo ni mínimo. Tampoco tiene elementos maximales ni minimales.

2. adhocprefix(E2)adhocsufix El poset \(\mathbf{P}=(\{1,2,3\},\{(1,2),(1,3),(1,1),(2,2),(3,3)\})\) no tiene elemento máximo. \(1\) es un elemento mínimo de \(\mathbf{P}\). El único elemento minimal de \(\mathbf{P}\) es \(1\). Los elementos \(2\) y \(3\) son los únicos maximales de \(\mathbf{P}\).

3. adhocprefix(E3)adhocsufix \(1\) es un elemento máximo de del poset \((\{1\},\{(1,1)\})\). También \(1\) es un elemento mínimo de \((\{1\},\{(1,1)\})\).

Como lo muestra el ejemplo (E3), no siempre hay elementos maximales o máximos en un poset. Además un poset tiene a lo sumo un máximo y un mínimo (por que?), los cuales en caso de existir algunas veces serán denotados con \(1\) y \(0\), respectivamente. También diremos que \((P,\leq)\) tiene un \(1\) (resp. \(0\)) para expresar que \((P,\leq)\) tiene un elemento máximo (resp. mínimo). Nótese también que todo elemento máximo (resp. mínimo) de \((P,\leq)\) es un elemento maximal (resp. minimal) de \((P,\leq)\) (por que?).

2.1.1.6 Supremos

Sea \((P,\leq)\) un poset. Dado \(S\subseteq P\), diremos que un elemento \(a\in P\) es cota superior de \(S\) en \((P,\leq)\) cuando \(b\leq a\), para todo \(b\in S\). Nótese que todo elemento de \(P\) es cota superior de \(\emptyset\) en \((P,\leq)\). Un elemento \(a\in P\) será llamado supremo de \(S\) en \((P,\leq)\) cuando se den las siguientes dos propiedades

1. adhocprefix(1)adhocsufix \(a\) es a cota superior de \(S\) en \((P,\leq)\)

2. adhocprefix(2)adhocsufix Para cada \(b\in P\), si \(b\) es una cota superior de \(S\) en \((P,\leq)\), entonces \(a\leq b\).

Algunos ejemplos:

1. adhocprefix(E1)adhocsufix Si \(S=\{x,y\}\) y se da que \(x\leq y\), entonces \(y\) es supremo de \(S\) en \((P,\leq)\). Esto es fácil de probar ya que claramente \(y\) es a cota superior de \(S\) en \((P,\leq)\) y además si \(z\) es una cota superior de \(S\) en \((P,\leq)\), obviamente tendremos que \(y\leq z\) ya que \(y\in S\).

2. adhocprefix(E2)adhocsufix Consideremos el poset \((\mathbf{R},\leq)\), donde \(\leq\) es el orden usual de los números reales. Nótese que ningún elemento de \(\mathbf{R}\) es cota superior de \(\omega\) en \((\mathbf{R},\leq)\). O sea que ningún elemento de \(\mathbf{R}\) es supremo de \(\omega\) en \((\mathbf{R},\leq)\). También consideremos el poset \((\{2,5,20,50\},\leq)\), donde \(\mathrm{\leq}=\{(x,y)\in\{2,5,20,50\}^{2}:x\text{ divide a }y\}\) (hacer el diagrama de Hasse). Nótese que el conjunto \(S=\{2,5\}\) tiene solo dos cotas superiores, a saber \(20\) y \(50\). Ya que \(20\nleq50\) y \(50\nleq20\) es fácil ver que ningún elemento es supremo de \(S\) en \((\{2,5,20,50\},\leq)\).

3. adhocprefix(E3)adhocsufix Consideremos el poset \((\mathbf{R},\leq)\), donde \(\leq\) es el orden usual de los números reales. Sea \[\begin{aligned} S & =\{-1/n:n\in\mathbf{N}\}\\ & =\{-1,-1/2,-1/3,...\} \end{aligned}\] Veamos que \(0\) es supremo de \(S\) en \((\mathbf{R},\leq)\). Claramente \(0\) es cota superior de \(S\) en \((\mathbf{R},\leq)\). Además si \(x\in\mathbf{R}\) es negativo, entonces habrá un \(n\in\mathbf{N}\) tal que \(x<-1/n\) (por que?). Pero esto nos dice que entonces toda cota superior de \(S\) en \((\mathbf{R},\leq)\) debe ser mayor o igual a \(0\). O sea que \(0\) es supremo de \(S\) en \((\mathbf{R},\leq)\).

4. adhocprefix(E4)adhocsufix Consideremos el poset \((\mathcal{P}(\omega),\leq)\), donde \(\mathrm{\leq}=\{(A,B)\in\mathcal{P}(\omega)^{2}:A\subseteq B\}\). Sean \(A,B\in\mathcal{P}(\omega)\). Es fácil ver que \(A\cup B\) es supremo de \(\{A,B\}\) en \((\mathcal{P}(\omega),\leq)\)

Como lo muestra el ejemplo (E2) no siempre existe un supremo de \(S\) en \((P,\leq)\). Además nótese que en caso de existir es único, es decir, si \(a\) es supremo de \(S\) en \((P,\leq)\) y \(a^{\prime}\) es supremo de \(S\) en \((P,\leq)\), entonces \(a=a^{\prime}\) (por que?). Esto nos permite hablar de EL supremo de \(S\) en \((P,\leq)\), cuando exista. Denotaremos con \(\sup(S)\) al supremo de \(S\) en \((P,\leq)\), en caso de que exista. A veces para hacer mas dinámicos los enunciados en lugar de escribir \(z\) es supremo de \(S\) en \((P,\leq)\) escribiremos \(z=\sup(S)\) o \(\sup(S)=z\).

Nótese que (E3) nos muestra que no siempre el supremo de un conjunto pertenece al conjunto. Nótese además que, en caso de existir, el supremo del conjunto \(\emptyset\) en \((P,\leq)\) es un elemento mínimo de \((P,\leq)\). Esto es porque todo elemento de \(P\) es cota superior de \(\emptyset\) en \((P,\leq)\).

Daremos otro ejemplo muy importante pero antes un poco de matemática básica. Recordemos que dados \(x,y\in\mathbf{N}\) decimos que \(x\) es múltiplo de \(y\) cuando \(y\) divide a \(x\). Ademas, por definición, el mínimo común múltiplo de \(x\) e \(y\) es el menor elemento del conjunto \(\{z\in\mathbf{N}:z\) es múltiplo de \(x\) y de \(y\}\). El mínimo común múltiplo de \(x\) e \(y\) se denota con \(mcm(x,y)\). Una propiedad importante es la siguiente:

1. adhocprefix(*)adhocsufix Si \(z\) es múltiplo de \(x\) y de \(y\), entonces \(mcm(x,y)|z\), es decir no solo \(mcm(x,y)\) es menor o igual a cada múltiplo común de \(x\) e \(y\), sino que \(mcm(x,y)\) divide a cada múltiplo común de \(x\) e \(y\)

Un ejemplo importante de existencia de supremos es el siguiente:

1. adhocprefix(E5)adhocsufix Consideremos el poset \((\mathbf{N},D)\), donde \(D=\{(x,y)\in\mathbf{N}^{2}:x|y\}\). Dados \(x,y\in\mathbf{N}\), se tiene que \(mcm(x,y)\) es el supremo de \(\{x,y\}\) en \((\mathbf{N},D)\). Es claro que \(mcm(x,y)\) es cota superior de \(\{x,y\}\) en \((\mathbf{N},D)\). Además la propiedad (*) nos asegura que la propiedad (2) de la definición de supremo se cumple. Por que no es obvio que se cumpla (2) de la definición de supremo? Por que es necesario aplicar la propiedad (*)?

2.1.1.7 Ínfimos

Sea \((P,\leq)\) un poset. Dado \(S\subseteq P\), diremos que un elemento \(a\in P\) es cota inferior de \(S\) en \((P,\leq)\), cuando \(a\leq b\), para cada \(b\in S\). Nótese que todo elemento de \(P\) es cota inferior de \(\emptyset\) en \((P,\leq)\). Un elemento \(a\in P\) será llamado ínfimo de \(S\) en \((P,\leq)\) cuando se den las siguientes dos propiedades

1. adhocprefix(1)adhocsufix \(a\) es a cota inferior de \(S\) en \((P,\leq)\)

2. adhocprefix(2)adhocsufix Para cada \(b\in P\), si \(b\) es una cota inferior de \(S\) en \((P,\leq)\), entonces \(b\leq a\).

Algunos ejemplos:

1. adhocprefix(E1)adhocsufix Si \(S=\{x,y\}\) y se da que \(x\leq y\), entonces \(x\) es ínfimo de \(S\) en \((P,\leq)\) (por que?)

2. adhocprefix(E2)adhocsufix Consideremos el poset \((\mathbf{R},\leq)\), donde \(\leq\) es el orden usual de los números reales. Nótese que ningún elemento de \(\mathbf{R}\) es cota inferior de \(\mathbf{Z}\) en \((\mathbf{R},\leq)\). O sea que ningún elemento de \(\mathbf{R}\) es ínfimo de \(\mathbf{Z}\) en \((\mathbf{R},\leq)\). También consideremos el poset \((\{2,5,20,50\},\leq)\), donde \(\mathrm{\leq}=\{(x,y)\in\{2,5,20,50\}^{2}:x\text{ divide a }y\}\) (hacer el diagrama de Hasse). Nótese que el conjunto \(S=\{20,50\}\) tiene solo dos cotas inferiores, a saber \(2\) y \(5\). Ya que \(2\nleq5\) y \(5\nleq2\) es fácil ver que ningún elemento es ínfimo de \(S\) en \((\{2,5,20,50\},\leq)\).

3. adhocprefix(E3)adhocsufix Consideremos el poset \((\mathbf{R},\leq)\), donde \(\leq\) es el orden usual de los números reales. Sea \[\begin{aligned} S & =\{1/n:n\in\mathbf{N}\}\\ & =\{1,1/2,1/3,...\} \end{aligned}\] Es fácil ver que \(0\) es ínfimo de \(S\) en \((\mathbf{R},\leq)\).

4. adhocprefix(E4)adhocsufix Consideremos el poset \((\mathcal{P}(\omega),\leq)\), donde \(\mathrm{\leq}=\{(A,B)\in\mathcal{P}(\omega)^{2}:A\subseteq B\}\). Sean \(A,B\in\mathcal{P}(\omega)\). Es fácil ver que \(A\cap B\) es ínfimo de \(\{A,B\}\) en \((\mathcal{P}(\omega),\leq)\).

Como lo muestra el ejemplo (E2) no siempre existe un ínfimo de \(S\) en \((P,\leq)\). Además nótese que en caso de existir es único, es decir, si \(a\) es ínfimo de \(S\) en \((P,\leq)\) y \(a^{\prime}\) es ínfimo de \(S\) en \((P,\leq)\), entonces \(a=a^{\prime}\) (por que?). Esto nos permite hablar de EL ínfimo de \(S\) en \((P,\leq)\), cuando exista. Denotaremos con \(\inf(S)\) al ínfimo de \(S\) en \((P,\leq)\), en caso de que exista. A veces para hacer mas dinámicos los enunciados en lugar de escribir \(z\) es ínfimo de \(S\) en \((P,\leq)\) escribiremos \(z=\inf(S)\) o \(\inf(S)=z\).

Nótese que (E3) nos muestra que no siempre el ínfimo de un conjunto pertenece al conjunto. Nótese además que en caso de existir el ínfimo del conjunto \(\emptyset\) en \((P,\leq)\) es un elemento máximo de \((P,\leq)\).

Daremos otro ejemplo muy importante pero antes un poco de matemática básica. Recordemos que dados \(x,y\in\mathbf{N}\), por definición, el máximo común divisor de \(x\) e \(y\) es el mayor elemento del conjunto \(\{z\in\mathbf{N}:z|x\) y \(z|y\}\). El máximo común divisor de \(x\) e \(y\) se denota con \(mcd(x,y)\). Una propiedad importante es la siguiente:

1. adhocprefix(**)adhocsufix Si \(z|x\) y \(z|y\), entonces \(z|mcd(x,y)\), es decir no solo \(mcd(x,y)\) es mayor o igual a cada divisor común de \(x\) e \(y\), sino que \(mcd(x,y)\) es divisible por cada divisor común de \(x\) e \(y\)

Un ejemplo importante de existencia de ínfimos es el siguiente:

1. adhocprefix(E5)adhocsufix Consideremos el poset \((\mathbf{N},D)\), donde \(D=\{(x,y)\in\mathbf{N}^{2}:x|y\}\). Dados \(x,y\in\mathbf{N}\), se tiene que \(mcd(x,y)\) es el ínfimo de \(\{x,y\}\) en \((\mathbf{N},D)\). Es claro que \(mcd(x,y)\) es cota inferior de \(\{x,y\}\) en \((\mathbf{N},D)\). Además la propiedad (**) nos asegura que la propiedad (2) de la definición de ínfimo se cumple. Por que no es obvio que se cumpla (2) de la definición de ínfimo? Por que es necesario aplicar la propiedad (**)?

2.1.1.8 Homomorfismos de posets

Sean \((P,\leq)\) y \((P^{\prime},\leq^{\prime})\) posets. Una función \(F:P\rightarrow P^{\prime}\) será llamada un homomorfismo de \((P,\leq)\) en \((P^{\prime},\leq^{\prime})\) si para todo \(x,y\in P\) se cumple que \(x\leq y\) implica \(F(x)\leq^{\prime}F(y)\). Escribiremos \(F:(P,\leq)\rightarrow(P^{\prime},\leq^{\prime})\) para expresar que \(F\) es un homomorfismo de \((P,\leq)\) en \((P^{\prime},\leq^{\prime})\). Algunos ejemplos:

1. adhocprefix(E1)adhocsufix \(F:\mathbf{R}\rightarrow\mathbf{R}\) dada por \(F(r)=3.r\) es un homomorfismo de \((\mathbf{R},\leq)\) en \((\mathbf{R},\leq)\)

2. adhocprefix(E2)adhocsufix Sea \(\mathrm{\leq}=\{(n,m)\in\omega:n=m\}\) y sea \((P^{\prime},\leq^{\prime})\) un poset cualquiera. Entonces cualquier función \(F:\omega\rightarrow P^{\prime}\) es un homomorfismo de \((\omega,\leq)\) en \((P^{\prime},\leq^{\prime})\) (glup!)

3. adhocprefix(E3)adhocsufix Consideremos el poset \((\mathcal{P}(\omega),\leq)\), donde \(\mathrm{\leq}=\{(A,B)\in\mathcal{P}(\omega)^{2}:A\subseteq B\}\) y el poset \((\mathcal{P}(\{1,2,3,4\}),\leq^{\prime})\), donde \(\mathrm{\leq}^{\prime}=\{(A,B)\in\mathcal{P}(\{1,2,3,4\})^{2}:A\subseteq B\}\). Entonces \(F:\mathcal{P}(\omega)\rightarrow\mathcal{P}(1,2,3,4)\) dada por \(F(A)=A\cap\{1,2,3,4\}\) es un homomorfismo de \((\mathcal{P}(\omega),\leq)\) en \((\mathcal{P}(\{1,2,3,4\}),\leq^{\prime})\)

Una función \(F:P\rightarrow P^{\prime}\) será llamada un isomorfismo de \((P,\leq)\) en \((P^{\prime},\leq^{\prime})\) si \(F\) es biyectiva, \(F\) es un homomorfismo de \((P,\leq)\) en \((P^{\prime},\leq^{\prime})\) y \(F^{-1}\) es un homomorfismo de \((P^{\prime},\leq^{\prime})\) en \((P,\leq)\). Escribiremos \((P,\leq)\cong(P^{\prime},\leq^{\prime})\) cuando exista un isomorfismo de \((P,\leq)\) en \((P^{\prime},\leq^{\prime})\) y en tal caso diremos que \((P,\leq)\) y \((P^{\prime},\leq^{\prime})\) son isomorfos. Cabe observar que un homomorfismo biyectivo no necesariamente es un isomorfismo como lo muestra el siguiente ejemplo.

1. adhocprefix-adhocsufix Consideremos los posets \(\mathbf{P}=(\{1,2\},\{(1,1),(2,2)\})\) y \(\mathbf{Q}=(\{1,2\},\{(1,1),(2,2),(1,2)\})\). Es fácil ver que \(F:\{1,2\}\rightarrow\{1,2\}\), dada por \(F(1)=1\) y \(F(2)=2\) es un homomorfismo de \(\mathbf{P}\) en \(\mathbf{Q}\). Dejamos al lector chequear que \(F^{-1}\) no es un homomorfismo de \(\mathbf{Q}\) en \(\mathbf{P}\).

1. Dada una función \(F:A\rightarrow B\) y \(S\subseteq A\), denotaremos con \(F(S)\) al conjunto \(\{F(a):a\in S\}\). Nótese que si \(F\) es biyectiva, entonces \(F^{-1}(F(S))=S\) (ejercicio).

El siguiente lema aporta evidencia al hecho de que los isomorfismos preservan todas las propiedades matemáticas.

Proof. (b) Sea \(a\in P\) un elemento fijo. Supongamos \(a\in P\) es máximo de \((P,\leq)\). Probaremos que \(F(a)\) es máximo de \((P^{\prime},\leq^{\prime})\). Sea \(b\) un elemento fijo pero arbitrario de \(P^{\prime}\). Probaremos que \(b\leq^{\prime}F(a)\). Sea \(d\in P\) tal que \(F(d)=b\) (tal \(d\) existe ya que \(F\) es suryectiva). Ya que \(a\) es máximo de \((P,\leq)\) tenemos que \(d\leq a\). Ya que \(F\) es un homomorfismo tenemos que \(F(d)\leq^{\prime}F(a)\) por lo cual \(b\leq^{\prime}F(a)\) ya que \(F(d)=b\). Ya que \(b\) era arbitrario hemos probado que \(x\leq^{\prime}F(a)\) para cada \(x\in P^{\prime}\), lo cual por definición nos dice que \(F(a)\) es máximo de \((P^{\prime},\leq^{\prime})\).

Supongamos ahora que \(F(a)\) es máximo de \((P^{\prime},\leq^{\prime})\). Probaremos que \(a\) es máximo de \((P,\leq)\). Sea \(b\) un elemento fijo pero arbitrario de \(P\). Probaremos que \(b\leq a\). Ya que \(F(a)\) es máximo de \((P^{\prime},\leq^{\prime})\) tenemos que \(F(b)\leq^{\prime}F(a)\). Ya que \(F^{-1}\) es un homomorfismo tenemos que \(F^{-1}(F(b))\leq F^{-1}(F(a))\), por lo cual \(b\leq a\). Ya que \(b\) era arbitrario hemos probado que \(x\leq a\) para cada \(x\in P\), lo cual por definición nos dice que \(a\) es máximo de \((P,\leq)\).

Ya que \(a\) era fijo pero arbitrario hemos probado que cualquiera sea \(x\in P\), se tiene que \(x\) es máximo de \((P,\leq)\) si y solo si \(F(x)\) es máximo de \((P^{\prime},\leq^{\prime})\).

(d) Supongamos que \(a\) es cota superior de \(S\). Veamos que entonces \(F(a)\) es cota superior de \(F(S)\). Sea \(x\in F(S)\). Sea \(s\in S\) tal que \(x=F(s)\). Ya que \(s\leq a\), tenemos que \(x=F(s)\leq^{\prime}F(a)\). Supongamos ahora que \(F(a)\) es cota superior de \(F(S)\) y veamos que entonces \(a\) es cota superior de \(S\). Sea \(s\in S\). Ya que \(F(s)\leq^{\prime}F(a)\), tenemos que \(s=F^{-1}(F(s))\leq F^{-1}(F(a))=a\).

(e) Probaremos los dos siguientes enunciados los cuales claramente implican la totalidad de lo aseverado por (f):

1. adhocprefix(I)adhocsufix Si existe \(\sup(S)\), entonces \(F(\sup(S))\) es el supremo de \(F(S)\).

2. adhocprefix(II)adhocsufix Si existe \(\sup(F(S))\), entonces existe \(\sup(S)\) y \(F(\sup(S))=\sup(F(S))\).

Prueba de (I). Supongamos que existe \(\sup(S)\). Por (d) \(F(\sup(S))\) es cota superior de \(F(S)\). Falta ver entonces que es la menor cota. Supongamos \(b\) es cota superior de \(F(S)\). Probaremos que \(F(\sup(S))\leq^{\prime}b\). Ya que \(F\) es suryectiva, hay un \(a\in P\) tal que \(b=F(a)\). Entonces (d) nos dice que \(a\) es cota superior de \(S\), por lo cual \(\sup(S)\leq a\). Ya que \(F\) es un homomorfismo tenemos que \(F(\sup(S))\leq^{\prime}F(a)\) y por lo tanto \(F(\sup(S))\leq^{\prime}b\) ya que \(b=F(a)\).

Prueba de (II). Supongamos existe \(\sup(F(S))\). Ya que \(F^{-1}\) es un isomorfismo, por (I) aplicado a este isomorfismo y al subconjunto \(F(S)\) de su dominio, tenemos que:

1. adhocprefix(*)adhocsufix \(F^{-1}(\sup(F(S)))\) es el supremo de \(F^{-1}(F(S))\)

Pero \(F^{-1}(F(S))=S\) o sea que \(F^{-1}(\sup(F(S)))=\sup(S)\) lo cual también nos dice que \(F(\sup(S))=\sup(F(S))\).

Las pruebas faltantes son dejadas como ejercicio. La prueba de (i) esta en video en granlogico.com  

Nótese que (i) nos garantiza que si dos posets finitos son isomorfos, entonces pueden representarse con el mismo diagrama de Hasse.

En la prueba de (b) y también en la de (e) del lema anterior se uso tácitamente la siguiente propiedad que es obvia pero clave en la demostración:

1. adhocprefix-adhocsufix Si \(F\) es una función y \(b\in\mathrm{Im}(F)\), entonces \(b=F(d)\), para algún \(d\in D_{F}\)

Esto da lugar a la siguiente regla la cual es muy útil a la hora de hacer pruebas:

1. adhocprefixRegla Pertenecer a la Imagen:adhocsufix Si Ud en el desarrollo de una prueba conoce que un elemento \(b\) esta en la imagen de una función \(F\), entonces escriba al elemento \(b\) en la forma \(F(a)\), donde \(a\) denota algún elemento fijo del dominio de \(F\)

Muchas veces tener presente esta regla es la diferencia de que a uno le salga o no una prueba determinada.

2.1.2 Reticulados par

El concepto de reticulado puede ser abordado en dos formas distintas, una geométrica, vía posets, la cual daremos ahora y la otra algebraica, vía estructuras algebraicas definidas ecuacionalmente, la cual daremos en la sección siguiente. Como veremos mas adelante ambas definiciones son equivalentes.

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

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

2. adhocprefix(E2)adhocsufix El poset \((\mathcal{P}(\omega),\leq)\) es un reticulado par (\(\mathrm{\leq}=\{(A,B)\in\mathcal{P}(\omega)^{2}:A\subseteq B\}\)) ya que dados \(A,B\in\mathcal{P}(\omega)\), hemos visto que \(A\cap B\) y \(A\cup B\) son ínfimo y supremo del conjunto \(\{A,B\}\) en \((\mathcal{P}(\omega),\leq)\)

Recordemos que dado un conjunto \(A\), por una operación binaria sobre \(A\) entenderemos una función cuyo dominio es \(A^{2}\) y cuya imagen esta contenida en \(A\). En un reticulado par \((P,\leq)\) tenemos dos operaciones binarias naturalmente definidas: \[\begin{array}{rcl} \mathsf{s}:P^{2} & \rightarrow & P\\ (a,b) & \rightarrow & \sup(\{a,b\}) \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rcl} \mathsf{i}:P^{2} & \rightarrow & P\\ (a,b) & \rightarrow & \inf(\{a,b\}) \end{array}\] Escribiremos \(a\mathsf{\;s\;}b\) en lugar de \(\mathsf{s}(a,b)\) y \(a\mathsf{\;i\;}b\) en lugar de \(\mathsf{i}(a,b)\).

A continuación 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 matemático maduro, la cual será crucial a la hora de hacer lógica ya que la lógica estudia (modeliza) matemáticamente el funcionar de un matemático y será muy práctico que cada uno cuente con un matemático maduro en su propia mente.

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

Prueba perfecta de (3). Sea \(a\in L\), fijo. Por definición de \(\mathsf{s}\) tenemos que \(a\) \(\mathsf{s}\) \(a=\sup(\{a,a\})=\sup(\{a\})\). O sea que debemos probar que \(a=\sup(\{a\})\). Es claro que \(a\) es cota superior de \(\{a\}\). Además es claro que si \(z\) es cota superior de \(\{a\}\), entonces \(z\geq a\). O sea que por definición de supremo de un conjunto tenemos que \(a=\sup(\{a\})\). O sea que hemos probado que \(a\mathsf{\;s\;}a=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 absorción (por que?)

Proof. (1). Sean \(a,b\in L\), fijos. Por definición de \(\mathsf{i}\) debemos probar que \(\sup(\{a,a\mathsf{\;i\;}b\})=a\). O sea debemos probar que \(a\) es la menor cota superior de \(\{a,a\mathsf{\;i\;}b\}\). Por un lema anterior tenemos que \(a\mathsf{\;i\;}b\leq a\) y obviamente se da \(a\leq a\), lo cual nos dice que \(a\) es cota superior de \(\{a,a\mathsf{\;i\;}b\}\). Es claro que es menor o igual que cualquier otra cota superior. O sea que hemos probado que \(a\;\mathsf{s}\;(a\mathsf{\;i\;}b)=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 básicas de los reticulados par daremos tres reglas que serán de suma utilidad para encontrar pruebas. Dejamos al lector justificar matemáticamente la validez de dichas reglas.

• Regla Igualdad en Posets: Si Ud esta intentando probar que en un poset \((P,\leq)\) dos elementos \(x,y\) son iguales, desdoble su tarea en las dos tareas siguientes:

  • Probar que \(x\leq y\)

  • Probar que \(y\leq x\)

• Regla Superar un Supremo: Si Ud esta intentando probar que en un reticulado par \((L,\leq)\) se da que \(z\geq x\;\mathsf{s}\;y\), desdoble su tarea en las dos tareas siguientes:

  • Probar que \(z\geq x\)

  • Probar que \(z\geq y\)

• Regla Ser Menor o Igual que un Ínfimo: Si Ud esta intentando probar que en un reticulado par \((L,\leq)\) se da que \(z\leq x\;\mathsf{i}\;y\), desdoble su tarea en las dos tareas siguientes:

  • Probar que \(z\leq x\)

  • Probar que \(z\leq y\)

Ambas operaciones \(\mathsf{s}\) e \(\mathsf{i}\) son asociativas, es decir:

Proof. (1) Sean \(a,b,c\in L\), fijos. Usaremos la regla Igualdad en Posets. Primero probaremos \((a\;\mathsf{s}\;b)\;\mathsf{s}\;c\leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\). Para esto usaremos la regla Superar un Supremo. Es decir que debemos probar que \[\begin{aligned} (a\;\mathsf{s}\;b) & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\\ c & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c) \end{aligned}\] Para la primer desigualdad usaremos también la regla Superar un Supremo, por lo cual deberemos probar \[\begin{aligned} a & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\\ b & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c) \end{aligned}\] O sea que en suma debemos probar las siguientes desigualdades \[\begin{aligned} a & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\\ b & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\\ c & \leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c) \end{aligned}\] La primera es directa de un lema anterior, y para la segunda nótese que el mismo lema nos dice que \[b\leq(b\;\mathsf{s}\;c)\text{ y }(b\;\mathsf{s}\;c)\leq a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\] por lo cual solo resta usar que \(\leq\) es transitiva. La tercera es completamente análoga a la segunda.

En forma similar se prueba que \(a\;\mathsf{s}\;(b\;\mathsf{s}\;c)\leq(a\;\mathsf{s}\;b)\;\mathsf{s}\;c\). Es decir que por la regla Igualdad en Posets tenemos que \(a\;\mathsf{s}\;(b\;\mathsf{s}\;c)=(a\;\mathsf{s}\;b)\;\mathsf{s}\;c\). 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 \(\mathsf{s}\) e \(\mathsf{i}\) preservan el orden.

Proof. (1) Sean \(a,b,c,d\in L\), elementos fijos. Supongamos que \(a\leq c\) e \(b\leq d\). Probaremos que entonces \(a\;\mathsf{s}\ b\leq c\;\mathsf{s}\ d\). Por la regla Superar un Supremo basta con probar que \[\begin{aligned} a & \leq c\;\mathsf{s}\;d\\ b & \leq c\;\mathsf{s}\;d \end{aligned}\] Para ver que \(a\leq c\;\mathsf{s}\;d\) nótese que \(a\leq c\) (por hipótesis) y \(c\leq c\;\mathsf{s}\;d\), por lo cual podemos usar que \(\leq\) es transitiva. La desigualdad \(b\leq c\;\mathsf{s}\;d\) se prueba en forma similar. O sea que hemos probado que \[a\leq c\text{ y }b\leq d\text{ implica }a\;\mathsf{s}\ b\leq c\;\mathsf{s}\ d\] 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{aligned} a\mathsf{\;i\;}b & \leq a\mathsf{\;i\;}(b\;\mathsf{s}\;c)\\ a\mathsf{\;i\;}c & \leq a\mathsf{\;i\;}(b\;\mathsf{s}\;c) \end{aligned}\] Pero estas dos desigualdades pueden ser fácilmente probadas aplicando (2) del lema anterior. O sea que \((a\mathsf{\;i\;}b)\;\mathsf{s}\;(a\mathsf{\;i\;}c)\leq a\mathsf{\;i\;}(b\;\mathsf{s}\;c)\), de lo cual se deduce nuestro lema ya que \(a,b,c\) eran elementos arbitrarios.  

Iterar supremos (resp. ínfimos) da supremos (resp. ínfimos), es decir:

Proof. Haremos sólo el caso del supremo. Lo probaremos usando la Regla de Inducción desde 2. Para cada \(n\geq2\) sea \(\mathrm{Enu}_{n}\) el siguiente enunciado:

1. adhocprefix\(\mathrm{Enu}_{n}\):adhocsufix Sea \((L,\leq)\) un reticulado par y sean \(x_{1},...,x_{n}\in L\). Se tiene que \[\begin{aligned} (...(x_{1}\;\mathsf{s\;}x_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}x_{n} & =\sup(\{x_{1},...,x_{n}\}) \end{aligned}\]

Hagamos entonces lo que nos encomienda la Regla de Inducción desde \(2\).

Prueba de que \(\mathrm{Enu}_{2}\) es verdadero. Por definición de la operación \(\mathsf{s}\).

Prueba de que si \(\mathrm{Enu}_{k}\) es verdadero entonces \(\mathrm{Enu}_{k+1}\) lo es. Supongamos entonces que vale \(\mathrm{Enu}_{k}\). Sea \((L,\leq)\) un reticulado par y sean \(a_{1},...,a_{n+1}\in L\), fijos. Ya que \(\mathrm{Enu}_{k}\) es verdadero tenemos que

1. adhocprefix(1)adhocsufix \((...(a_{1}\;\mathsf{s}\;a_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}a_{n}=\sup(\{a_{1},...,a_{n}\})\)

Veamos entonces que

1. adhocprefix(2)adhocsufix \(((...(a_{1}\;\mathsf{s\;}a_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}a_{n})\;\mathsf{s\;}a_{n+1}=\sup(\{a_{1},...,a_{n+1}\})\)

Usando (1), es fácil ver que \(((...(a_{1}\;\mathsf{s\;}a_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}a_{n})\;\mathsf{s\;}a_{n+1}\) es cota superior de \(\{a_{1},...,a_{n+1}\}\). Supongamos que \(z\) es otra cota superior. Ya que \(z\) es también cota superior del conjunto \(\{a_{1},...,a_{n}\}\), por (1) tenemos que \[(...(a_{1}\;\mathsf{s\;}a_{2})\;\mathsf{s}\;...)\;\mathsf{s\;}a_{n}\leq z\] Pero entonces ya que \(a_{n+1}\leq z\), tenemos que \[((...(a_{1}\;\mathsf{s\;}a_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}a_{n})\;\mathsf{s\;}a_{n+1}\leq z\] con lo cual hemos probado (2). Ya que \(a_{1},...,a_{n+1}\in L\) eran elementos arbitrarios, hemos probado que vale \(\mathrm{Enu}_{n+1}\).  

Dado que la distribución de paréntesis en una expresión de la forma \[(...(x_{1}\;\mathsf{s\;}x_{2})\;\mathsf{s\;}...)\;\mathsf{s\;}x_{n}\] es irrelevante (ya que\(\;\mathsf{s\;}\)es asociativa), en general suprimiremos los paréntesis.

Una regla que hemos usado constantemente es la siguiente:

• Regla Igualar un Supremo: Si Ud esta intentando probar que en un poset \((P,\leq)\) se da que \(x=\sup(S)\), desdoble su tarea en las dos tareas siguientes:

  • Probar que \(x\) es cota superior de \(S\)

  • Probar que si \(z\) es una cota superior de \(S\), entonces \(x\leq z\)

Concluimos la sección con una regla que es una de las mas usadas por los matemáticos:

• Regla del Director de Cine Generoso: Si Ud esta en el medio de una prueba y puede introducir un nuevo actor, hágalo!

Obviamente esta regla necesita explicación. La cosa es así, muchas veces en el desarrollo de una demostración 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 demostración. Cabe destacar que la Regla Pertenecer a la Imagen dada al final de la sección anterior es un caso particular de la Regla del Director de Cine Generoso (por que?). A medida que vayamos haciendo mas pruebas y vayamos madurando como matemáticos iremos entendiendo mas el nombre de esta regla ya que en algún sentido una demostración es una película que parte de un escenario inicial fijo y ficticio (i.e. las hipótesis) y a lo largo de la demostración van sucediendo cosas que nos conducen dentro de esa ficción a un escenario distinto al que teníamos al comienzo (i.e. la conclusión de la demostración). Obviamente el matemático que realiza la demostración es el director de esta “película” ya que es quien decide que cosas van sucediendo a lo largo de la prueba. Por ejemplo en la prueba del Lema 1.7 el escenario inicial es un reticulado par \((L,\leq)\) el cual obviamente es ficticio (i.e. no es uno concreto) aunque lo pensamos como un objeto fijo, concreto (tal como cuando comenzamos a ver una película). Luego se introducen en la escena tres elementos \(a,b,c\) de \(L\) (actores nuevos en la película) y sigue la trama hasta obtener la conclusión de que \((L,\leq)\) cumple que \((x\mathsf{\;i\;}y)\;\mathsf{s}\;(x\mathsf{\;i\;}z)\leq x\mathsf{\;i\;}(y\;\mathsf{s}\;z)\), cualesquiera sean \(x,y,z\in L\) (este es el escenario final de esta corta película).

Las seis reglas consideradas están muy vinculadas al concepto de inteligencia artificial ya que si quisiéramos hacer un probador automático del tipo de teoremas hechos en esta sección, claramente estas reglas le darían una alternativa de búsqueda que podría (y de hecho en muchos casos lo hace) dar el camino adecuado para obtener la prueba de un enunciado dado.

2.1.3 Reticulados terna

De la diversas propiedades de las operaciones \(\mathsf{s}\) e \(\mathsf{i}\) de un reticulado par \((L,\leq)\) distinguiremos las siguientes:

1. adhocprefix(I1)adhocsufix \(x\;\mathsf{s}\;x=x\mathsf{\;i\;}x=x\), cualesquiera sea \(x\in L\)

2. adhocprefix(I2)adhocsufix \(x\mathsf{\;s\;}y=y\;\mathsf{s}\;x\), cualesquiera sean \(x,y\in L\)

3. adhocprefix(I3)adhocsufix \(x\mathsf{\;i\;}y=y\mathsf{\;i\;}x\), cualesquiera sean \(x,y\in L\)

4. adhocprefix(I4)adhocsufix \((x\mathsf{\;s\;}y)\;\mathsf{s}\;z=x\;\mathsf{s}\;(y\;\mathsf{s}\;z)\), cualesquiera sean \(x,y,z\in L\)

5. adhocprefix(I5)adhocsufix \((x\mathsf{\;i\;}y)\mathsf{\;i\;}z=x\mathsf{\;i\;}(y\mathsf{\;i\;}z)\), cualesquiera sean \(x,y,z\in L\)

6. adhocprefix(I6)adhocsufix \(x\;\mathsf{s}\;(x\mathsf{\;i\;}y)=x\), cualesquiera sean \(x,y\in L\)

7. adhocprefix(I7)adhocsufix \(x\mathsf{\;i\;}(x\;\mathsf{s}\;y)=x\), cualesquiera sean \(x,y\in L\)

Podemos abstraernos y pensar que \(\mathsf{s}\) e \(\mathsf{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=\mathbf{R}\) y \[\begin{array}{rcl} \mathsf{s}:\mathbf{R}^{2} & \rightarrow & \mathbf{R}\\ (a,b) & \rightarrow & a+b \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rcl} \mathsf{i}:\mathbf{R}^{2} & \rightarrow & \mathbf{R}\\ (a,b) & \rightarrow & 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}{rcl} \mathsf{s}:\{1,2\}^{2} & \rightarrow & \{1,2\}\\ (1,1) & \rightarrow & 1\\ (1,2) & \rightarrow & 2\\ (2,1) & \rightarrow & 1\\ (2,2) & \rightarrow & 2 \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rcl} \mathsf{i}:\{1,2\}^{2} & \rightarrow & \{1,2\}\\ (1,1) & \rightarrow & 1\\ (1,2) & \rightarrow & 1\\ (2,1) & \rightarrow & 1\\ (2,2) & \rightarrow & 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=\mathbf{N}\) y \[\begin{array}{rcl} \mathsf{s}:\mathbf{N}^{2} & \rightarrow & \mathbf{N}\\ (a,b) & \rightarrow & \max\{a,b\} \end{array}\ \ \ \ \ \ \begin{array}{rcl} \mathsf{i}:\mathbf{N}^{2} & \rightarrow & \mathbf{N}\\ (a,b) & \rightarrow & \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 \(\mathsf{s}\) e \(\mathsf{i}\) son las operaciones supremo e ínfimo dadas por algún orden parcial \(\leq\) sobre \(L\) el cual hace de \((L,\leq)\) un reticulado par, entonces las propiedades (I1),...,(I7) se cumplen y esto es justamente lo probado en la última serie de lemas. El último ejemplo nos permite ver una sutileza. Nótese que en este ejemplo \(\mathsf{s}\) es la operación supremo del reticulado par \((\mathbf{N},\leq)\), donde \(\leq\) es el orden usual de los naturales, e \(\mathsf{i}\) es la operación ínfimo del reticulado par \((\mathbf{N},|)\), donde \(|\) es el orden de la divisibilidad de los naturales. Sin embargo la última propiedad falla y esto se debe a que \(\mathsf{s}\) e \(\mathsf{i}\) son supremo e ínfimo pero respecto de distintos ordenes parciales.

Lo anterior motiva la siguiente definición:

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

Tal como lo vimos recién, 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,\leq)\) el cual sea un reticulado par, entonces la terna \((L,\mathsf{s},\mathsf{i})\), con \(\mathsf{s}\) e \(\mathsf{i}\) definidas como supremo e ínfimo, es un reticulado terna. El siguiente teorema muestra que todo reticulado terna \((L,\mathsf{s},\mathsf{i})\) se obtiene de esta forma.

Proof. Dejamos como ejercicio para el lector probar que \(\leq\) es reflexiva y antisimétrica con respecto a \(L\). Veamos que \(\leq\) es transitiva con respecto a \(L\). Supongamos que \(x\leq y\) e \(y\leq z\). Es decir que por definición de \(\leq\) tenemos que \[\begin{aligned} x\;\mathsf{s}\;y & =y\\ y\;\mathsf{s}\;z & =z \end{aligned}\] Entonces \[x\;\mathsf{s\;}z=x\;\mathsf{s\;}(y\;\mathsf{s\;}z)=(x\;\mathsf{s\;}y)\;\mathsf{s\;}z=y\;\mathsf{s\;}z=z\] por lo cual \(x\leq z\). O sea que ya sabemos que \((L,\leq)\) es un poset. Veamos ahora que \(\sup(\{x,y\})=x\;\mathsf{s\;}y\). Primero debemos ver que \(x\;\mathsf{s\;}y\) es una cota superior del conjunto \(\{x,y\}\), es decir \[\begin{aligned} x & \leq x\;\mathsf{s}\;y\\ y & \leq x\;\mathsf{s}\;y \end{aligned}\] Por la definición de \(\leq\) debemos probar que \[\begin{aligned} x\ \mathsf{s}\;(x\;\mathsf{s}\;y) & =x\;\mathsf{s}\;y\\ y\ \mathsf{s}\;(x\;\mathsf{s}\;y) & =x\;\mathsf{s}\;y \end{aligned}\] Estas igualdades se pueden probar usando (I1), (I2) y (I4). Dejamos al lector hacerlo como ejercicio. Nos falta ver entonces que \(x\;\mathsf{s\;}y\) es menor o igual que cualquier cota superior de \(\{x,y\}\). Supongamos \(x,y\leq z\). Es decir que por definición de \(\leq\) tenemos que \[\begin{aligned} x\;\mathsf{s}\;z & =z\\ y\;\mathsf{s}\;z & =z \end{aligned}\] Pero entonces \[(x\;\mathsf{s\;}y)\;\mathsf{s\;}z=x\;\mathsf{s\;}(y\;\mathsf{s\;}z)=x\;\mathsf{s\;}z=z\] por lo que \(x\;\mathsf{s\;}y\leq z\). Es decir que \(x\;\mathsf{s\;}y\) es la menor cota superior.

Para probar que \(\inf(\{x,y\})=x\mathsf{\;i\;}y\), probaremos que para todo \(u,v\in L\), \[u\leq v\text{ si y solo si }u\mathsf{\;i\;}v=u\] lo cual le permitirá al lector aplicar un razonamiento similar al usado en la prueba de que \(\sup(\{x,y\})=x\;\mathsf{s\;}y\). Supongamos que \(u\leq v\). Por definición tenemos que \(u\;\mathsf{s}\;v=v\). Entonces \[u\mathsf{\;i\;}v=u\mathsf{\;i\;}(u\;\mathsf{s}\;v)\] Pero por (I7) tenemos que \(u\mathsf{\;i\;}(u\;\mathsf{s}\;v)=u\), lo cual implica \(u\mathsf{\;i\;}v=u\). Recíprocamente si \(u\mathsf{\;i\;}v=u\), entonces \[\begin{aligned} u\;\mathsf{s}\;v & =(u\mathsf{\;i\;}v)\;\mathsf{s}\;v\\ & =v\;\mathsf{s}\;(u\mathsf{\;i\;}v)\text{ (por (I2))}\\ & =v\;\mathsf{s}\;(v\mathsf{\;i\;}u)\text{ (por (I3))}\\ & =v\text{ (por (I6))} \end{aligned}\] lo cual nos dice que \(u\leq v\).  

1. adhocprefixEjercicio:adhocsufix Use los resultados anteriores para definir una función \(\mathcal{F}\) de \(\{(L,\leq):(L,\leq)\) es un reticulado par\(\}\) en \(\{(L,\mathsf{s},\mathsf{i}):(L,\mathsf{s},\mathsf{i})\) es un reticulado terna\(\}\) la cual sea biyectiva

Reflexión Informática

Como vimos recién a nivel de información 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 información. Muchas veces esta información es mas fácil de dar dando el poset ya que simplemente podemos dar su diagrama de Hasse y esto en general es una forma económica de dar las operaciones \(\mathsf{s}\) e \(\mathsf{i}\).

Recordemos que algo similar sucedía con los conceptos equivalentes de relación de equivalencia y partición.

El orden asociado a un reticulado terna

Como vimos el Teorema de Dedekind nos dice que un reticulado terna \((L,\mathsf{s},\mathsf{i})\) es un objeto geométrico ya que si definimos \[\mathrm{\leq}=\{(x,y):x\;\mathsf{s}\;y=y\}\] entonces \(\leq\) es un orden parcial sobre \(L\) y las operaciones \(\mathsf{s}\) e \(\mathsf{i}\) resultan ser supremo e ínfimo respecto de este orden parcial. Llamaremos a \(\mathrm{\leq}=\{(x,y):x\;\mathsf{s}\;y=y\}\) el orden parcial asociado a \((L,\mathsf{s},\mathsf{i})\) y a \((L,\leq)\) el poset asociado a \((L,\mathsf{s},\mathsf{i})\). Nótese que también tenemos que \(\mathrm{\leq}=\{(x,y):x\;\mathsf{i}\;y=x\}\) (¿por que?).

Muchos conceptos definidos para posets ahora pueden aplicarse cuando tenemos un reticulado terna \((L,\mathsf{s},\mathsf{i})\). Por ejemplo, si decimos que \((L,\mathsf{s},\mathsf{i})\) tiene elemento máximo, esto significara que el poset \((L,\leq)\) tiene elemento máximo. Otro ejemplo, si decimos que en \((L,\mathsf{s},\mathsf{i})\) 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\). También hablaremos del diagrama de Hasse de \((L,\mathsf{s},\mathsf{i})\) en referencia al diagrama de Hasse de su poset asociado \((L,\leq)\).

Convenciones notacionales

Usaremos las siguientes prácticas convenciones notacionales

• Convención notacional 1: Si \(L\) es un conjunto no vacío cuyos elementos son conjuntos y \(L\) cumple la siguiente condición \[\text{Si }A,B\in L,\text{ entonces }A\cup B,A\cap B\in L\] entonces ciertas veces usaremos \(\cup\) (resp. \(\cap\)) para denotar la operación binaria sobre \(L\) dada por la unión (resp. la intersección). Es decir \(\cup\) e \(\cap\) denotarán las funciones \[\begin{array}{rcl} L^{2} & \rightarrow & L\\ (A,B) & \rightarrow & A\cup B \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rcl} L^{2} & \rightarrow & L\\ (A,B) & \rightarrow & A\cap B \end{array}\]

• Convención notacional 2: Si \(L\) es un conjunto no vacío cuyos elementos son números reales entonces ciertas veces usaremos \(\max\) y \(\min\) para denotar las operaciones binarias sobre \(L\) dadas por \[\begin{array}{rcl} L^{2} & \rightarrow & L\\ (a,b) & \rightarrow & \max(a,b) \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rcl} L^{2} & \rightarrow & L\\ (a,b) & \rightarrow & \min(a,b) \end{array}\]

• Convención notacional 3: Si \(L\) es un conjunto no vacío cuyos elementos son números naturales y \(L\) cumple la siguiente condición \[\text{Si }a,b\in L,\text{ 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}{rcl} L^{2} & \rightarrow & L\\ (a,b) & \rightarrow & mcm(a,b) \end{array}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \begin{array}{rcl} L^{2} & \rightarrow & L\\ (a,b) & \rightarrow & mcd(a,b) \end{array}\]

• Convención notacional 4: Si \(P\) es un conjunto no vacío contenido en \(\omega\), entonces escribiremos \((P,|)\) para denotar al poset \((P,\{(x,y)\in P^{2}:x|y\})\). 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\})\)

En virtud de las convenciones notacionales anteriores nótese que por ejemplo

1. \((\mathbf{R,}\max,\min)\)

2. \(([0,1]\mathbf{,}\max,\min)\)

3. \((\mathcal{P}(\mathbf{N}),\cup,\cap)\)

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

5. \((\mathbf{N},mcm,mcd)\)

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

denotan reticulados terna pero debería quedar claro que en los primeros dos ejemplos \(\max\) denota dos distintas operaciones. Análogamente sucede con \(\min\), \(\cup\), \(\cap\), \(mcm\) y \(mcd\). Similarmente

1. \((\mathbf{N,}|)\)

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

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

4. \((\{A\subseteq\mathbf{N}:A\) es finito\(\},\subseteq)\)

denotan posets pero debería quedar claro que en los primeros dos ejemplos \(|\) denota dos distintos ordenes parciales. Análogamente sucede con \(\subseteq\)

Estas ambigüedades no nos traerán problemas si estamos atentos al contexto.

2.1.3.1 Subreticulados terna

Si \(f\) es una operación \(n\)-aria sobre \(A\) y \(S\subseteq A\), entonces diremos que \(S\) es cerrado bajo \(f\) cuando se dé que \(f(a_{1},...,a_{n})\in S\), cada ves que \(a_{1},...,a_{n}\in S\). Nótese que si \(n=0\), entonces \(S\) es cerrado bajo \(f\) si y solo si \(f(\lozenge)\in S\).

Dados reticulados terna \((L,\mathsf{s},\mathsf{i})\) y \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\) diremos que \((L,\mathsf{s},\mathsf{i})\) es un subreticulado terna de \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\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}\) e \(\mathsf{i}^{\prime}\)

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

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

Es fácil de chequear que si \(S\) es un subuniverso de \((L,\mathsf{s},\mathsf{i})\), entonces \((S,\mathsf{s}\mathrm{\mid}_{S\times S},\mathsf{i}\mathrm{\mid}_{S\times S})\) es un subreticulado terna de \((L,\mathsf{s},\mathsf{i})\) y que todo subreticulado terna de \((L,\mathsf{s},\mathsf{i})\) se obtiene en esta forma. Es decir, hay una biyección entre el conjunto de los subreticulados terna de \((L,\mathsf{s},\mathsf{i})\) y el conjunto de los subuniversos de \((L,\mathsf{s},\mathsf{i})\) (cual es?). Dicho de manera mas rápida: los subuniversos de \((L,\mathsf{s},\mathsf{i})\) son ni mas ni menos que los universos de los subreticulados terna de \((L,\mathsf{s},\mathsf{i})\).

2.1.3.2 Homomorfismos de reticulados terna

Sean \((L,\mathsf{s},\mathsf{i})\) y \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\) reticulados terna. Una función \(F:L\rightarrow L^{\prime}\) será llamada un homomorfismo de \((L,\mathsf{s},\mathsf{i})\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\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). \end{aligned}\] Un homomorfismo de \((L,\mathsf{s},\mathsf{i})\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\) será llamado isomorfismo de \((L,\mathsf{s},\mathsf{i})\) en \((L^{\prime},\mathsf{s}^{\prime}\), \(\mathsf{i}^{\prime}\) \()\) cuando sea biyectivo y su inversa sea también un homomorfismo. Escribiremos \((L,\mathsf{s},\mathsf{i})\cong(L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\) cuando exista un isomorfismo de \((L,\mathsf{s},\mathsf{i})\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\). Escribiremos "Sea \(F:(L,\mathsf{s},\mathsf{i})\rightarrow(L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\) un homomorfismo" para expresar que \(F\) es un homomorfismo de \((L,\mathsf{s},\mathsf{i})\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\). No hay que confundirse al leer esta notación y pensar que \(F\) es una función cuyo dominio es \((L,\mathsf{s},\mathsf{i})\), lo cual por otra parte no tiene sentido ya que el dominio de una función nunca puede ser una \(3\)-upla!

Proof. Solo falta ver que \(F^{-1}\) es un homomorfismo. Sean \(F(x),F(y)\) dos elementos cualesquiera de \(L^{\prime}\). Tenemos que \[F^{-1}(F(x)\;\mathsf{s}^{\prime}\ F(y))=F^{-1}(F(x\mathsf{\;s\;}y))=x\mathsf{\;s\;}y=F^{-1}(F(x))\;\mathsf{s}\ F^{-1}(F(y))\]  

Proof. Ya que \(L\) es no vacío tenemos que \(I_{F}\) también es no vacío. Sean \(a,b\in I_{F}\). Sean \(x,y\in L\) tales que \(F(x)=a\) y \(F(y)=b\). Se tiene que \[\begin{aligned} a\;\mathsf{s}^{\prime}\ b & =F(x)\;\mathsf{s}^{\prime}\ F(y)=F(x\mathsf{\;s\;}y)\in I_{F}\\ a\;\mathsf{i}^{\prime}\ b & =F(x)\;\mathsf{i}^{\prime}\ F(y)=F(x\mathsf{\;i\;}y)\in I_{F} \end{aligned}\] por lo cual \(I_{F}\) es cerrada bajo \(\mathsf{s}^{\prime}\) e \(\mathsf{i}^{\prime}\).  

Proof. Supongamos \(F\) es un isomorfismo de \((L,\mathsf{s},\mathsf{i})\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\). Sean \(x,y\in L\), tales que \(x\leq y\). Tenemos que \(y=x\mathsf{\;s\;}y\) por lo cual \(F(y)=F(x\mathsf{\;s\;}y)=F(x)\mathsf{\;s^{\prime}\;}F(y)\), produciendo \(F(x)\leq^{\prime}F(y)\). En forma similar se puede ver que \(F^{-1}\) es también un homomorfismo de \((L^{\prime},\leq^{\prime})\) en \((L,\leq)\). Si \(F\) es un isomorfismo de \((L,\leq)\) en \((L^{\prime},\leq^{\prime})\), entonces (g) y (h) del Lema 1.1 nos dicen que \(F\) y \(F^{-1}\) son homomorfismos (de reticulados terna terna) por lo cual \(F\) es un isomorfismo de \((L,\mathsf{s},\mathsf{i})\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\).  

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

2.1.3.3 Congruencias de reticulados terna

Sea \((L,\mathsf{s},\mathsf{i})\) un reticulado terna. Una congruencia sobre \((L,\mathsf{s},\mathsf{i})\) será una relación de equivalencia \(\theta\) sobre \(L\) la cual cumpla:

1. adhocprefix(1)adhocsufix \(x\theta x^{\prime}\) y \(y\theta y^{\prime}\) implica \((x\mathsf{\;s\;}y)\theta(x^{\prime}\mathsf{\;s\;}y^{\prime})\) y \((x\mathsf{\;i\;}y)\theta(x^{\prime}\mathsf{\;i\;}y^{\prime})\)

Gracias a esta condición podemos definir en forma inambigua sobre \(L/\theta\) dos operaciones binarias \(\mathsf{\tilde{s}}\) e \(\mathsf{\tilde{\imath}}\), 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 \end{aligned}\] Veamos algunos ejemplos:

1. adhocprefix(E1)adhocsufix Consideremos el reticulado terna \((\{1,2,3,4,5\},\max,\min)\). O sea que aquí \(L=\{1,2,3,4,5\}\), \(\mathsf{s}\) es la operación \(\max\) sobre \(L\) y \(\mathsf{i}\) es la operación \(\min\) sobre \(L\). Sea \(\theta\) la relación de equivalencia sobre \(\{1,2,3,4,5,6\}\) dada por la partición \(\{\{1,2\},\{3\},\{4,5\}\}\). Se puede chequear que \(\theta\) es una congruencia, es decir satisface (1) de arriba. Nótese que \[\begin{aligned} L/\theta & =\{\{1,2\},\{3\},\{4,5\}\}\\ \mathsf{\tilde{s}\;} & =\widetilde{\max}:L/\theta\times L/\theta\rightarrow L/\theta\\ \mathsf{\tilde{\imath}\;} & =\widetilde{\min}:L/\theta\times L/\theta\rightarrow L/\theta \end{aligned}\] Por ejemplo tenemos que \[\{1,2\}\ \widetilde{\max}\ \{3\}=\{3\}\] ya que \(\{1,2\}\ \widetilde{\max}\ \{3\}=1/\theta\ \widetilde{\max}\ 3/\theta=(1\max3)/\theta=3/\theta=\{3\}\) (escribimos \(1\max3\) en lugar de \(\max(1,3)\)). Similarmente tenemos que \[\begin{aligned} \{4,5\}\ \widetilde{\max}\ \{3\} & =\{4,5\}\\ \{1,2\}\ \widetilde{\min}\ \{4,5\} & =\{1,2\} \end{aligned}\]

2. adhocprefix(E2)adhocsufix Consideremos el reticulado terna \((\{1,2,3,6\},mcm,mcd)\) (o sea el rombo) y sea \(\theta\) la relación de equivalencia dada por la partición \(\{\{1,2\},\{3\},\{6\}\}\) (haga un dibujo). Entonces \(\theta\) no es una congruencia sobre \((\{1,2,3,6\},mcm,mcd)\). Esto es ya que si tomamos \[\begin{aligned} x & =1\\ x^{\prime} & =2\\ y & =3\\ y^{\prime} & =3 \end{aligned}\] no se cumple la implicación de (1) de la definición de congruencia.

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

Proof. Veamos que la estructura \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}})\) cumple (I4). Sean \(x/\theta\), \(y/\theta\), \(z/\theta\) elementos cualesquiera de \(L/\theta\). Tenemos que \[\begin{array}{ccl} (x/\theta\mathsf{\;\tilde{s}\;}y/\theta)\;\mathsf{\tilde{s}}\;z/\theta & = & (x\mathsf{\;s\;}y)/\theta\;\mathsf{\tilde{s}}\;z/\theta\\ & = & ((x\mathsf{\;s\;}y)\;\mathsf{s}\;z)/\theta\\ & = & (x\mathsf{\;s\;}(y\;\mathsf{s}\;z))/\theta\\ & = & x/\theta\;\mathsf{\tilde{s}}\;(y\;\mathsf{s}\;z)/\theta\\ & = & x/\theta\mathsf{\;\tilde{s}\;}(y/\theta\;\mathsf{\tilde{s}}\;z/\theta) \end{array}\] En forma similar se puede ver que la estructura \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}})\) cumple el resto de las identidades que definen reticulado terna.  

Denotaremos con \(\tilde{\leq}\) al orden parcial asociado al reticulado terna \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}})\).

Proof. Por definición de \(\tilde{\leq}\) tenemos que \(x/\theta\tilde{\leq}y/\theta\) sii \(y/\theta=x/\theta\mathsf{\;\tilde{s}\;}y/\theta\). Pero \(x/\theta\mathsf{\;\tilde{s}\;}y/\theta=(x\mathsf{\;s\;}y)/\theta\) (por definición de \(\mathsf{\tilde{s}}\)) por lo cual tenemos que \(x/\theta\tilde{\leq}y/\theta\) sii \(y/\theta=(x\mathsf{\;s\;}y)/\theta\).  

Proof. Ya que \(1=x\mathsf{\;s\;}1\), para cada \(x\in L\), tenemos que \(1/\theta=(x\mathsf{\;s\;}1)/\theta\), para cada \(x\in L\), lo cual por el lema anterior nos dice que \(x/\theta\tilde{\leq}1/\theta\), para cada \(x\in L\).  

El siguiente lema nos da una forma natural de encontrar congruencias (i.e. como núcleos de homomorfismos).

Proof. Dejamos al lector ver que \(\ker(F)\) es una relación de equivalencia. Supongamos \(x\ker(F)x^{\prime}\) y \(y\ker(F)y^{\prime}\). Entonces \[F(x\mathsf{\;s\;}y)=F(x)\mathsf{\;s^{\prime}\;}F(y)=F(x^{\prime})\mathsf{\;s^{\prime}\;}F(y^{\prime})=F(x^{\prime}\mathsf{\;s\;}y^{\prime})\] lo cual nos dice que \((x\mathsf{\;s\;}y)\ker(F)(x^{\prime}\mathsf{\;s\;}y^{\prime})\). En forma similar tenemos que \((x\mathsf{\;i\;}y)\ker(F)(x^{\prime}\mathsf{\;i\;}y^{\prime})\).  

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

Proof. Sean \(x,y\in L\). Tenemos que \[\pi_{\theta}(x\mathsf{\;s\;}y)=(x\mathsf{\;s\;}y)/\theta=x/\theta\mathsf{\;\tilde{s}\;}y/\theta=\pi_{\theta}(x)\mathsf{\;\tilde{s}\;}\pi_{\theta}(y)\] por lo cual \(\pi_{\theta}\) preserva la operación supremo. Para la operación ínfimo es similar.  

2.1.4 Reticulados acotados

Por un reticulado acotado entenderemos una \(5\)-upla \((L,\mathsf{s},\mathsf{i},0,1)\), tal que \((L,\mathsf{s},\mathsf{i})\) es un reticulado terna, \(0,1\in L\), y además se cumplen las siguientes identidades

1. adhocprefix(I8)adhocsufix \(0\mathsf{\;s\;}x=x\), para cada \(x\in L\)

2. adhocprefix(I9)adhocsufix \(x\mathsf{\;s\;}1=1\), para cada \(x\in L\).

Por ejemplo \((\{4,56,449\},\max,\min,4,449)\) es un reticulado acotado pero es fácil ver que \((\{4,56,449\},\max,\min,449,56)\) no lo es.

Reflexión Informática

Por supuesto, en virtud de lo desarrollado en la sección sobre reticulados par, se tiene que si \((L,\leq)\) es reticulado par en el cual hay un máximo \(1\) y un mínimo \(0\), entonces si tomamos: \[\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}\] tenemos que \((L,\mathsf{s},\mathsf{i},0,1)\) es un reticulado acotado. Veamos que todo reticulado acotado se obtiene de esta forma. Supongamos \((L,\mathsf{s},\mathsf{i},0,1)\) es un reticulado acotado. Ya que por definición tenemos que entonces \((L,\mathsf{s},\mathsf{i})\) es un reticulado terna, el Teorema de Dedekind nos dice que el orden parcial \(\mathrm{\leq}=\{(x,y):x\;\mathsf{s}\;y=y\}\) hace de \((L,\leq)\) un reticulado par en el cual \[\begin{aligned} \sup(\{x,y\}) & =x\;\mathsf{s}\;y\\ \inf(\{x,y\}) & =x\mathsf{\;i\;}y \end{aligned}\] cualesquiera sean \(x,y\in L\). Además las propiedades (I8) y (I9) nos garantizan que \(0\) y \(1\) son máximo y mínimo de \((L,\leq)\). O sea que a nivel de información, un reticulado par que tiene \(0\) y \(1\) es exactamente lo mismo que un reticulado acotado. O, dicho de otra forma, hay una biyección entre el conjunto de los reticulados pares con \(0\) y \(1\) y el conjunto de los reticulados acotados.

El orden asociado a un reticulado acotado

Dado un reticulado acotado \((L,\mathsf{s},\mathsf{i},0,1)\), llamaremos a \(\mathrm{\leq}=\{(x,y):x\;\mathsf{s}\;y=y\}\) el orden parcial asociado a \((L,\mathsf{s},\mathsf{i},0,1)\) y \((L\leq)\) será llamado el poset asociado a \((L,\mathsf{s},\mathsf{i},0,1)\). Nótese que también tenemos que \(\mathrm{\leq}=\{(x,y):x\;\mathsf{i}\;y=x\}\) (¿por que?).

Muchos conceptos definidos para posets o reticulados terna pueden aplicarse cuando tenemos un reticulado acotado \((L,\mathsf{s},\mathsf{i},0,1)\). Por ejemplo, si decimos que \((L,\mathsf{s},\mathsf{i},0,1)\) es totalmente ordenado, esto significara que el poset \((L,\leq)\) lo es. Si decimos que en \((L,\mathsf{s},\mathsf{i},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},0,1)\) es distributivo nos estaremos refiriendo a que \((L,\mathsf{s},\mathsf{i})\) lo es. También hablaremos del diagrama de Hasse de \((L,\mathsf{s},\mathsf{i},0,1)\) en referencia al diagrama de Hasse de su poset asociado \((L,\leq)\). También hablaremos del diagrama de Hasse de \((L,\mathsf{s},\mathsf{i},0,1)\) en referencia al diagrama de Hasse de su poset asociado \((L,\leq)\).

2.1.4.1 Subreticulados acotados

Dados reticulados acotados \((L,\mathsf{s},\mathsf{i},0,1)\) y \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},0^{\prime},1^{\prime})\) diremos que \((L,\mathsf{s},\mathsf{i},0,1)\) es un subreticulado acotado de \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\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}\) e \(\mathsf{i}^{\prime}\)

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

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

Sea \((L,\mathsf{s},\mathsf{i},0,1)\) un reticulado acotado. Un conjunto \(S\subseteq L\) es llamado subuniverso de \((L,\mathsf{s},\mathsf{i},0,1)\) si \(0,1\in S\) y además \(S\) es cerrado bajo las operaciones \(\mathsf{s}\) e \(\mathsf{i}\). Es importante notar que si bien los conceptos de subreticulado acotado y subuniverso están muy relacionados, se trata de conceptos diferentes ya que los subreticulados acotados de \((L,\mathsf{s},\mathsf{i},0,1)\) son reticulados acotados, es decir \(5\)-uplas y los subuniversos de \((L,\mathsf{s},\mathsf{i},0,1)\) son conjuntos, por lo cual no son \(5\)-uplas.

Es fácil de chequear que si \(S\) es un subuniverso de \((L,\mathsf{s},\mathsf{i},0,1)\), entonces \((S,\mathsf{s}\mathrm{\mid}_{S\times S},\mathsf{i}\mathrm{\mid}_{S\times S},0,1)\) es un subreticulado acotado de \((L,\mathsf{s},\mathsf{i},0,1)\) y que todo subreticulado acotado de \((L,\mathsf{s},\mathsf{i},0,1)\) se obtiene en esta forma. Es decir, hay una biyección entre el conjunto de los subreticulados acotados de \((L,\mathsf{s},\mathsf{i},0,1)\) y el conjunto de los subuniversos de \((L,\mathsf{s},\mathsf{i},0,1)\) (cual es?). Dicho de manera mas rápida: los subuniversos de \((L,\mathsf{s},\mathsf{i},0,1)\) son ni mas ni menos que los universos de los subreticulados acotados de \((L,\mathsf{s},\mathsf{i},0,1)\).

2.1.4.2 Homomorfismos de reticulados acotados

Sean \((L,\mathsf{s},\mathsf{i},0,1)\) y \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},0^{\prime},1^{\prime})\) reticulados acotados. Una función \(F:L\rightarrow L^{\prime}\) será llamada un homomorfismo de \((L,\mathsf{s},\mathsf{i},0,1)\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\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(0) & =0^{\prime}\\ F(1) & =1^{\prime} \end{aligned}\] Un homomorfismo de \((L,\mathsf{s},\mathsf{i},0,1)\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},0^{\prime},1^{\prime})\) será llamado isomorfismo cuando sea biyectivo y su inversa sea también un homomorfismo. Escribiremos \((L,\mathsf{s},\mathsf{i},0,1)\cong(L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},0^{\prime},1^{\prime})\) cuando exista un isomorfismo de \((L,\mathsf{s},\mathsf{i},0,1)\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},0^{\prime},1^{\prime})\). Escribiremos "Sea \(F:(L,\mathsf{s},\mathsf{i},0,1)\rightarrow(L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},0^{\prime},1^{\prime})\) un homomorfismo" para expresar 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})\). No hay que confundirse al leer esta notación y pensar que \(F\) es una función cuyo dominio es \((L,\mathsf{s},\mathsf{i},0,1)\), lo cual por otra parte no tiene sentido ya que el dominio de una función nunca puede ser una \(5\)-upla!

Proof. Similar a la prueba del Lema 1.9.  

Proof. Ya que \(F\) es un homomorfismo de \((L,\mathsf{s},\mathsf{i})\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\) tenemos que \(I_{F}\) es subuniverso de \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\) lo cual ya que \(0^{\prime},1^{\prime}\in I_{F}\) implica que \(I_{F}\) es un subuniverso de \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime},0^{\prime},1^{\prime})\).  

2.1.4.3 Congruencias de reticulados acotados

Sea \((L,\mathsf{s},\mathsf{i},0,1)\) un reticulado acotado. Una congruencia sobre \((L,\mathsf{s},\mathsf{i},0,1)\) será una relación de equivalencia \(\theta\) la cual sea una congruencia sobre \((L,\mathsf{s},\mathsf{i})\). Tenemos definidas sobre \(L/\theta\) dos operaciones binarias \(\mathsf{\tilde{s}}\) e \(\mathsf{\tilde{\imath}}\), 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 \end{aligned}\] La \(5\)-upla \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}},0/\theta,1/\theta)\) es llamada el cociente de \((L,\mathsf{s},\mathsf{i},0,1)\) sobre \(\theta\) y la denotaremos con \((L,\mathsf{s},\mathsf{i},0,1)/\theta\).

Proof. (a) Es fácil ver que \((L/\theta,\mathsf{\tilde{s}},\mathsf{\tilde{\imath}},0/\theta,1/\theta)\) cumple (I1), (I2),...,(I9) dado que \((L,\mathsf{s},\mathsf{i},0,1)\) las cumple.  

(b) Sigue directamente del Lema 1.15

Proof. Ya que \(F\) es un homomorfismo de \((L,\mathsf{s},\mathsf{i})\) en \((L^{\prime},\mathsf{s}^{\prime},\mathsf{i}^{\prime})\) tenemos que por un lema anterior \(\ker(F)\) es una congruencia sobre \((L,\mathsf{s},\mathsf{i})\) lo cual por definición nos dice que \(\ker(F)\) es una congruencia sobre \((L,\mathsf{s},\mathsf{i},0,1)\).  

2.1.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}\] Nótese que dicho elemento \(b\) puede no ser único, es decir \(a\) puede tener varios complementos. Recordemos que una operación unaria sobre un conjunto \(L\) es por definición una función de \(L\) en \(L\). Muchas veces si \(s\) denota una operación unaria, entonces escribiremos \(x^{s}\) en lugar de \(s(x)\). Por un reticulado complementado entenderemos 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 operación 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 operación 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.

Reflexión Informática

Nótese que si tenemos un reticulado par \((L,\leq)\) en el cual hay un máximo \(1\) y un mínimo \(0\) y además tenemos una función \(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. Además todo reticulado complementado se obtiene de esta forma (por que?). O sea que a nivel de información, tener un reticulado par con \(0\) y \(1\) junto con una operación 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)\) será llamado el poset asociado a \((L,\mathsf{s},\mathsf{i},^{c},0,1)\). Nótese que también tenemos que \(\mathrm{\leq}=\{(x,y):x\;\mathsf{i}\;y=x\}\) (¿por que?).

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)\). Aquí 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}\). También hablaremos del diagrama de Hasse de \((L,\mathsf{s},\mathsf{i},^{c},0,1)\) en referencia al diagrama de Hasse de su poset asociado \((L,\leq)\).

2.1.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 además \(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 están 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 fácil 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 biyección 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 rápida: 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)\).

2.1.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 función \(F:L\rightarrow L^{\prime}\) será 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})\) será llamado isomorfismo cuando sea biyectivo y su inversa sea un homomorfismo. Como es usual usaremos el símbolo \(\cong\) para denotar la relación 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 notación y pensar que \(F\) es una función 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 función nunca puede ser una \(6\)-upla!

Proof. Es dejada al lector.  

Proof. Es dejada al lector.  

2.1.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)\) será una relación 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 operación 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

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)\) satisface 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 definición 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)\) satisface la identidad (I11)

(b) Por el Lema 1.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 núcleo es \(\theta\). Nótese que por definición 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\)  

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  

2.1.6 Álgebras de Boole

Un reticulado terna \((L,\mathsf{s},\mathsf{i})\) se llamara distributivo cuando cumpla la siguiente identidad

1. adhocprefix\(Dis_{1}=\)adhocsufix \(x\mathsf{\;i\;}(y\;\mathsf{s}\;z)=(x\mathsf{\;i\;}y)\;\mathsf{s}\;(x\mathsf{\;i\;}z)\), cualesquiera sean \(x,y,z\in L\)

Diremos que un reticulado acotado \((L,\mathsf{s},\mathsf{i},0,1)\) (resp. complementado \((L,\mathsf{s},\mathsf{i},^{c},0,1)\)) es distributivo cuando \((L,\mathsf{s},\mathsf{i})\) lo sea. Consideremos la distributividad dual a \(Dis_{1}\), es decir

1. adhocprefix\(Dis_{2}=\)adhocsufix \(x\;\mathsf{s}\;(y\mathsf{\;i\;}z)=(x\mathsf{\;s\;}y)\mathsf{\;i\;}(x\;\mathsf{s}\;z)\), cualesquiera sean \(x,y,z\in L\)

Proof. Supongamos \((L,\mathsf{s},\mathsf{i})\) satisface \(Dis_{1}\). Sean \(a,b,c\in L\) elementos fijos. Por \(Dis_{1}\) tenemos que \[(a\mathsf{\;s\;}b)\mathsf{\;i\;}(a\;\mathsf{s}\;c)=((a\mathsf{\;s\;}b)\mathsf{\;i\;}a)\;\mathsf{s}\;((a\mathsf{\;s\;}b)\mathsf{\;i\;}c)\] Pero por conmutatividad tenemos que \[((a\mathsf{\;s\;}b)\mathsf{\;i\;}a)\;\mathsf{s}\;((a\mathsf{\;s\;}b)\mathsf{\;i\;}c)=(a\mathsf{\;i\;}(a\mathsf{\;s\;}b))\;\mathsf{s}\;(c\mathsf{\;i\;}(a\mathsf{\;s\;}b))\] Por (I7) tenemos que \(a\mathsf{\;i\;}(a\mathsf{\;s\;}b)=a\) y por \(Dis_{1}\) tenemos que \(c\mathsf{\;i\;}(a\mathsf{\;s\;}b)=(c\mathsf{\;i\;}a)\mathsf{\;s\;}(c\mathsf{\;i\;}b)\) por lo cual \[(a\mathsf{\;i\;}(a\mathsf{\;s\;}b))\;\mathsf{s}\;(c\mathsf{\;i\;}(a\mathsf{\;s\;}b))=a\;\mathsf{s}\;((c\mathsf{\;i\;}a)\mathsf{\;s\;}(c\mathsf{\;i\;}b))\] Por asociatividad tenemos que \[a\;\mathsf{s}\;((c\mathsf{\;i\;}a)\mathsf{\;s\;}(c\mathsf{\;i\;}b))=(a\;\mathsf{s}\;(c\mathsf{\;i\;}a))\mathsf{\;s\;}(c\mathsf{\;i\;}b)\] Pero por conmutatividad tenemos que \[(a\;\mathsf{s}\;(c\mathsf{\;i\;}a))\mathsf{\;s\;}(c\mathsf{\;i\;}b)=(a\;\mathsf{s}\;(a\mathsf{\;i\;}c))\mathsf{\;s\;}(b\mathsf{\;i\;}c)\] Lo cual por (I6) nos dice que \[(a\;\mathsf{s}\;(a\mathsf{\;i\;}c))\mathsf{\;s\;}(b\mathsf{\;i\;}c)=a\mathsf{\;s\;}(b\mathsf{\;i\;}c)\] Por transitividad de la igualdad, las igualdades anteriores nos dicen que \[a\mathsf{\;s\;}(b\mathsf{\;i\;}c)=(a\mathsf{\;s\;}b)\mathsf{\;i\;}(a\;\mathsf{s}\;c)\] Pero \(a,b,c\) eran elementos arbitrarios por lo que hemos probado que vale \(Dis_{2}\).  

1. adhocprefixEjercicio:adhocsufix Use la prueba del lema anterior para hacer un algoritmo el cual tome de entrada un reticulado acotado \((L,\mathsf{s},\mathsf{i},0,1)\) y elementos \(x,y,z\in L\) tales que \(y\neq z\) son complementos de \(x\), y de como salida elementos \(a,b,c\) tales que \(a\mathsf{\;i\;}(b\;\mathsf{s}\;c)\neq(a\mathsf{\;i\;}b)\;\mathsf{s}\;(a\mathsf{\;i\;}c)\)

Por un álgebra de Boole entenderemos un reticulado complementado que es distributivo. Algunos ejemplos:

1. adhocprefix(E1)adhocsufix Dado un conjunto no vacío \(X\), la \(6\)-upla \((\mathcal{P}(X),\cup,\cap,^{c},\emptyset,X)\) es un álgebra de Boole

2. adhocprefix(E2)adhocsufix \((\{1\},\max,\min,\{(1,1)\},1,1)\) es un álgebra de Boole

3. adhocprefix(E3)adhocsufix \((\{0,1\},\max,\min,\{(0,1),(1,0)\},0,1)\) es un álgebra de Boole

4. adhocprefix(E4)adhocsufix \((\{1,2,5,10\},mcm,mcd,c,0,1)\) es un álgebra de Boole, donde \(c(x)=10/x\), para cada \(x\in\{1,2,5,10\}\).

Para probar algunas propiedades fundamentales de un álgebra de Boole necesitaremos el siguiente

Proof. Sean \(a,b,c\in L\) elementos fijos. Supongamos que \[\begin{aligned} a\;\mathsf{s\;}b & =a\;\mathsf{s\;}c=1\\ a\;\mathsf{i\;}b & =a\;\mathsf{i\;}c=0 \end{aligned}\] (es decir \(b\) y \(c\) son ambos complementos de \(a\)). Veremos que entonces \(b=c\). Nótese que \[b=b\;\mathsf{i\;}1=b\;\mathsf{i\;}(a\;\mathsf{s\;}c)=(b\;\mathsf{i\;}a)\;\mathsf{s\;}(b\;\mathsf{i\;}c)=0\;\mathsf{s\;}(b\;\mathsf{i\;}c)=b\;\mathsf{i\;}c\] por lo cual \(b\leq c\). Análogamente se puede probar que \(c\leq b\) por lo cual \(b=c\). Ya que \(a,b,c\) eran elementos cualesquiera de \(L\), hemos probado el lema.  

Una propiedad muy importante que se da en las álgebras de Boole es

Proof. Sean \(a,b\in B\), fijos. Se tiene que \[b=b\;\mathsf{i\;}1=b\mathsf{\;i\mathsf{\;}}(a\mathsf{\;s\mathsf{\;}}a^{c})=(b\;\mathsf{i\;}a)\;\mathsf{s\;}(b\mathsf{\;i\mathsf{\;}}a^{c})\] Ya que \(a\) y \(b\) eran elementos cualesquiera de \(B\), hemos probado el lema.  

Proof. Antes de probar los items recordemos que, por el Teorema de Dedekind, \((B,\leq)\) es un reticulado par en el cual \[\begin{aligned} \sup(\{x,y\}) & =x\;\mathsf{s}\;y\\ \inf(\{x,y\}) & =x\mathsf{\;i\;}y \end{aligned}\] cualesquiera sean \(x,y\in B\).

(1) Es fácil ver que \(a^{c}\;\mathsf{s\;}b^{c}\) es un complemento de \(a\;\mathsf{i\;}b\) (hacer!). Pero ya que \((B,\mathsf{s},\mathsf{i},^{\mathbf{c}},0,1)\) es un reticulado complementado, tenemos que \((a\;\mathsf{i\;}b)^{c}\) es un complemento de \(a\;\mathsf{i\;}b\). El Lema 1.25 aplicado al reticulado acotado \((B,\mathsf{s},\mathsf{i},0,1)\) nos dice que \((a\;\mathsf{i\;}b)^{c}\) y \(a^{c}\;\mathsf{s\;}b^{c}\) deben ser iguales.

(2) y (3) se prueban en forma similar (hacer!)

(4) Supongamos \(a\;\mathsf{i\;}b=0\). Se tiene \[\begin{aligned} b & =(b\;\mathsf{i\;}a)\;\mathsf{s\;}(b\mathsf{\;i\mathsf{\;}}a^{c})\text{ (por lema anterior)}\\ & =(a\;\mathsf{i\;}b)\;\mathsf{s\;}(b\mathsf{\;i\mathsf{\;}}a^{c})\\ & =0\;\mathsf{s\;}(b\mathsf{\;i\mathsf{\;}}a^{c})\\ & =(b\mathsf{\;i\mathsf{\;}}a^{c})\leq a^{c} \end{aligned}\] por lo cual \(b\leq a^{c}\). Supongamos ahora \(b\leq a^{c}\). Ya que \(a\leq a\), el Lema 1.6, aplicado al reticulado par \((B,\leq)\), nos dice que \(a\;\mathsf{i\;}b\leq a\;\mathsf{i\;}a^{c}\). Ya que \(a\;\mathsf{i\;}a^{c}=0\) obtenemos que \(a\;\mathsf{i\;}b=0\).

(5) Supongamos \(a\leq b\). Entonces \(a\;\mathsf{i\;}b=a\), lo cual por (1) nos dice que \(a^{c}\;\mathsf{s\;}b^{c}=a^{c}\) obteniendo que \(b^{c}\leq a^{c}\). La reciproca es dejada al lector (hint: use (3)).  

2.1.7 Teoremas del filtro primo y de Rasiowa Sikorski

Un filtro de un reticulado terna \((L,\mathsf{s},\mathsf{i})\) será un subconjunto \(F\subseteq L\) tal que:

1. adhocprefix(1)adhocsufix \(F\neq\emptyset\)

2. adhocprefix(2)adhocsufix para cada \(x,y\in F\text{ se tiene que }x\;\mathsf{i\;}y\in F\)

3. adhocprefix(3)adhocsufix para cada \(x,y\in L\), si \(x\in F\) y \(x\leq y\text{ entonces }y\in F\)

El nombre "filtro" es inspirado por la propiedad (3) ya que si un filtro o colador atrapa a cierto objeto \(x\), entonces claramente atrapara a todos los objetos mas grandes que \(x\).

Dado un conjunto \(S\subseteq L\), denotemos con \([S)\) el siguiente conjunto \[\{y\in L:y\geq s_{1}\;\mathsf{i\;}...\;\mathsf{i\;}s_{n}\text{, para algunos }s_{1},...,s_{n}\in S\text{, }n\geq1\}\]

Proof. Ya que \(S\subseteq[S)\), tenemos que \([S)\neq\emptyset\). Claramente \([S)\) cumple la propiedad (3). Veamos cumple la (2). Si \(y\geq s_{1}\;\mathsf{i\;}s_{2}\;\mathsf{i\;}...\;\mathsf{i\;}s_{n}\) y \(z\geq t_{1}\;\mathsf{i\;}t_{2}\;\mathsf{i\;}\)...\(\;\mathsf{i\;}t_{m}\), con \(s_{1},s_{2},...,s_{n}\), \(t_{1},t_{2},...,t_{m}\in S\), entonces \[y\;\mathsf{i\;}z\geq s_{1}\;\mathsf{i\;}s_{2}\;\mathsf{i\;}...\;\mathsf{i\;}s_{n}\;\mathsf{i\;}t_{1}\;\mathsf{i\;}t_{2}\;\mathsf{i\;}...\;\mathsf{i\;}t_{m}\] lo cual prueba (2).  

Llamaremos a \([S)\) el filtro generado por \(S\) en \((L,\mathsf{s},\mathsf{i})\). Cuando \(S\) es finito, ya que existe \(\inf(S)\), es claro que \([S)=\{y\in L:y\geq\inf(S)\}\). Cuando \(S\) es infinito y existe \(\inf(S)\), en muchos casos se dará que \([S)=\{y\in L:y\geq\inf(S)\}\) o que \([S)=\{y\in L:y>\inf(S)\}\), pero no necesariamente esto sucederá siempre. Por ejemplo:

1. adhocprefix-adhocsufix Sea \(\mathbf{L}=(\mathcal{P}(\mathbf{N}),\cup,\cap)\) y sea \(S=\{\mathbf{N}-\{n\}:n\in\mathbf{N}\}\). Es fácil ver que \(\inf(S)=\emptyset\) y que \([S)=\{A\in\mathcal{P}(\mathbf{N}):\mathbf{N}-A\) es finito\(\}\) por lo cual no se da que \([S)=\{y\in L:y\geq\inf(S)\}\) o que \([S)=\{y\in L:y>\inf(S)\}\)

En general, si \((L,\mathsf{s},\mathsf{i},0,1)\) es un reticulado acotado, diremos que \(F\) es un filtro de \((L,\mathsf{s},\mathsf{i},0,1)\) cuando \(F\) sea un filtro de \((L,\mathsf{s},\mathsf{i})\). Lo mismo sucederá con el concepto de filtro de un reticulado complementado \((L,\mathsf{s},\mathsf{i},^{c},0,1)\). También hablaremos del filtro generado por \(S\) en \((L,\mathsf{s},\mathsf{i},0,1)\), etc.

Sea \((P,\leq)\) un poset. Un subconjunto \(C\subseteq P\) será llamado una cadena si para cada \(x,y\in C\), se tiene que \(x\leq y\) o \(y\leq x\). Por ejemplo

1. adhocprefix(E1)adhocsufix \(\{1,10,40,600\}\) y \(\{2^{n}:n\in\mathbf{N}\}\) son cadenas del poset \((\mathbf{N},|)\)

2. adhocprefix(E2)adhocsufix \(\{-3,5,2\}\) y el intervalo \([2,3]\) son cadenas del poset \((\mathbf{R},\leq)\). De hecho todo subconjunto de \(\mathbf{R}\) es una cadena de \((\mathbf{R},\leq)\)

3. adhocprefix(E3)adhocsufix \(C=\{[0,n]:n\in\mathbf{N}\}\) es una cadena del poset \((\mathcal{P}(\mathbf{R}),\subseteq)\). Nótese que cada elemento de \(C\) es un conjunto (i.e. un intervalo).

Es importante notar que las cadenas pueden ser infinitas y que dada una cadena infinita \(C\) puede no existir una infinitupla \((c_{1},c_{2},...)\) tal que \(C=\{c_{n}:n\in\mathbf{N}\}\). Este es el caso de la cadena \([0,1]\) del poset \((\mathbf{R},\leq)\), ya que el bien conocido argumento diagonal de Cantor nos dice que no existe una manera de enumerar los elementos del intervalo \([0,1]\). Esto nos obliga a pensar con cierta madurez a las cadenas y no caer en la falacia de pensar que sus elementos forman necesariamente una "filita discreta".

También es importante para entender la prueba del Teorema del Filtro Primo que viene a continuación, imaginar las cadenas de posets que sus elementos son conjuntos y su orden es la inclusión, es decir dichas cadenas serán un conjunto de conjuntos \(C\) con la propiedad que dados dos cualesquiera elementos de \(C\) siempre alguno contiene al otro. Un ejemplo de este tipo de cadenas es dado en (E3). Otro ejemplo:

1. adhocprefix(E4)adhocsufix Sea \(\mathcal{F}=\{F:F\) es un filtro del reticulado terna \((\mathbf{N},mcm,mcd)\}\). Notar que dado \(n\in\mathbf{N}\), el conjunto \(\{x\in\mathbf{N}:n|x\}\) es un filtro de \((\mathbf{N},mcm,mcd)\}\). Ya que \(\mathcal{F}\) es no vacío tenemos que \((\mathcal{F},\subseteq)\) es un poset. Entonces \[C=\{\{x\in\mathbf{N}:n|x\}:n\text{ es potencia de }2\}\] es una cadena de \((\mathcal{F},\subseteq)\).

El siguiente resultado es una herramienta fundamental en el álgebra moderna.

Obviamente en cada poset con universo finito hay al menos un elemento maximal. O sea que el Lema de Zorn es interesante para el caso en que \(P\) es un conjunto infinito. Un argumento para creer en la veracidad del lema podría ser el siguiente razonamiento por el absurdo:

Supongamos que \((P,\leq)\) es un poset en el cual cada cadena tiene al menos una cota superior y supongamos además que no hay elementos maximales en \((P,\leq)\). Tomemos \(x_{0}\in P\) un elemento cualquiera. Ya que \(x_{0}\) no es maximal, hay un \(x_{1}\in P\) tal que \(x_{0}<x_{1}\). Iterando esta idea vemos que debe haber elementos \(x_{2},x_{3},...\) tales que: \[x_{0}<x_{1}<x_{2}<x_{3}<\cdots\] Pero \(\{x_{0},x_{1},x_{2},x_{3},...\}\) es una cadena por lo cual hay al menos una cota superior de ella en \((P,\leq)\). Sea \(y_{0}\) una de tales cotas. Ya que \(y_{0}\) no es maximal, hay un \(y_{1}\) tal que \(y_{0}<y_{1}\). Iterando esta idea vemos que debe haber elementos \(y_{2},y_{3},...\) tales que: \[x_{0}<x_{1}<x_{2}<x_{3}<\cdots<y_{0}<y_{1}<y_{2}<y_{3}<\cdots\] Pero \(\{x_{0},x_{1},x_{2},x_{3},...,y_{0},y_{1},y_{2},y_{3},...\}\) es una cadena por lo cual hay al menos una cota superior de ella en \((P,\leq)\). Esto nos permite seguir agrandando la cadena usando la misma idea usada recién lo cual muestra que tenemos un procedimiento abstracto constructivo que nos permite ir agrandando indefinidamente nuestra cadena. Esto huele a absurdo!

De todas maneras para dar una prueba formal del Lema de Zorn es necesario madurar algunos conceptos para poder escribir en forma precisa el argumento antes descripto. Esto no lo haremos en el apunte.

Un filtro \(F\) de un reticulado terna \((L,\mathsf{s},\mathsf{i})\) será llamado primo cuando se cumplan:

1. adhocprefix(1)adhocsufix \(F\neq L\)

2. adhocprefix(2)adhocsufix para cada \(x,y\in L\), si \(x\;\mathsf{s\;}y\in F\text{ entonces }x\in F\) o \(y\in F\).

Algunos ejemplos:

1. adhocprefix(E1)adhocsufix Todo filtro de \((\mathbf{R},\max,\min)\), distinto de \(\mathbf{R}\), es primo (justificar)

2. adhocprefix(E2)adhocsufix Sea \(B=\{X\subseteq\omega:X\) es finito o \(\omega-X\) es finito\(\}\). Como vimos anteriormente \(B\) es cerrado bajo las operaciones \(\cup\) y \(\cap\). Sea \(P=\{X\subseteq\omega:\omega-X\) es finito\(\}\). Entonces \(P\) es un filtro primo de \((B,\cup,\cap)\).

Proof. Sea \[\mathcal{F}=\{F_{1}:F_{1}\text{ es un filtro, }x_{0}\notin F_{1}\text{ y }F\subseteq F_{1}\}.\] Nótese que \(\mathcal{F}\neq\emptyset\), por lo cual \((\mathcal{F},\subseteq)\) es un poset. Veamos que cada cadena en \((\mathcal{F},\subseteq)\) tiene una cota superior. Sea \(C\) una cadena. Si \(C=\emptyset\), entonces cualquier elemento de \(\mathcal{F}\) es cota de \(C\). Supongamos entonces \(C\neq\emptyset\). Sea \[G=\{x:x\in F_{1}\text{, para algún }F_{1}\in C\}.\] Veamos que \(G\) es un filtro. Es claro que \(G\) es no vacío. Supongamos que \(x,y\in G\). Sean \(F_{1},F_{2}\in\mathcal{F}\) tales que \(x\in F_{1}\) y \(y\in F_{2}\). Si \(F_{1}\subseteq F_{2}\), entonces ya que \(F_{2}\) es un filtro tenemos que \(x\;\mathsf{i\;}y\in F_{2}\subseteq G\). Si \(F_{2}\subseteq F_{1}\), entonces tenemos que \(x\;\mathsf{i\;}y\in F_{1}\subseteq G\). Ya que \(C\) es una cadena, tenemos que siempre \(x\;\mathsf{i\;}y\in G\). En forma análoga se prueba la propiedad restante por lo cual tenemos que \(G\) es un filtro. Además \(x_{0}\notin G\), por lo que \(G\in\mathcal{F}\) es cota superior de \(C\). Por el lema de Zorn, \((\mathcal{F},\subseteq)\) tiene un elemento maximal \(P\). Veamos que \(P\) es un filtro primo. Supongamos \(x\;\mathsf{s\;}y\in P\) y \(x,y\notin P\). Nótese que \([P\cup\{x\})\) es un filtro el cual contiene propiamente a \(P\). Entonces ya que \(P\) es un elemento maximal de \((\mathcal{F},\subseteq)\), tenemos que \(x_{0}\in[P\cup\{x\})\). Análogamente tenemos que \(x_{0}\in[P\cup\{y\})\). Ya que \(x_{0}\in[P\cup\{x\})\), tenemos que hay elementos \(p_{1},...,p_{n}\in P\), tales que \[x_{0}\geq p_{1}\;\mathsf{i\;}...\;\mathsf{i\;}p_{n}\;\mathsf{i\;}x\] (se deja como ejercicio justificar esto). Ya que \(x_{0}\in[P\cup\{y\})\), tenemos que hay elementos \(q_{1},...,q_{m}\in P\), tales que \[x_{0}\geq q_{1}\;\mathsf{i\;}...\;\mathsf{i\;}q_{m}\;\mathsf{i\;}y\] Si llamamos \(p\) al siguiente elemento de \(P\) \[p_{1}\;\mathsf{i\;}...\;\mathsf{i\;}p_{n}\;\mathsf{i\;}q_{1}\;\mathsf{i\;}...\;\mathsf{i\;}q_{m}\] tenemos que \[\begin{aligned} x_{0} & \geq p\;\mathsf{i\;}x\\ x_{0} & \geq p\;\mathsf{i\;}y \end{aligned}\] Se tiene entonces que \(x_{0}\geq(p\;\mathsf{i\;}x)\;\mathsf{s\;}(p\;\mathsf{i\;}y)=p\;\mathsf{i\;}(x\;\mathsf{s\;}y)\in P\), lo cual es absurdo ya que \(x_{0}\notin P\).  

Proof. Nótese que \([S)\neq L\) por lo cual se puede aplicar el Teorema del filtro primo.  

Proof. (1)\(\Rightarrow\)(2). Ya que \(x\;\mathsf{s\;}x^{c}=1\in F\), (2) se cumple si \(F\) es primo.

(2)\(\Rightarrow\)(1). Ya sabemos por hipótesis que \(F\) es un filtro y que \(F\neq B\). Supongamos que \(x\;\mathsf{s\;}y\in F\) y que \(x\not\in F\). Entonces por (2), \(x^{c}\in F\) y por lo tanto tenemos que \[y\geq x^{c}\;\mathsf{i\;}y=(x^{c}\;\mathsf{i\;}x)\;\mathsf{s\;}(x^{c}\;\mathsf{i\;}y)=x^{c}\;\mathsf{i\;}(x\;\mathsf{s\;}y)\in F,\] lo cual dice que \(y\in F\).  

Necesitaremos el siguiente lema.

Proof. Supongamos que para cada \(e\in A\), tengamos que \(b\;\mathsf{i\;}e^{c}=0\). Entonces tenemos que para cada \(e\in A\), \[b=b\;\mathsf{i\;}(e\;\mathsf{s\;}e^{c})=(b\;\mathsf{i\;}e)\;\mathsf{s\;}(b\;\mathsf{i\;}e^{c})=b\;\mathsf{i\;}e,\] lo cual nos dice que \(b\) es cota inferior de \(A\). Pero entonces \(b\leq a\), por lo cual \(b=b\;\mathsf{i\;}a=0\), contradiciendo la hipótesis.  

Es claro que si \(P\) es un filtro primo de un álgebra de Boole \((B,\mathsf{s},\mathsf{i},^{c},0,1)\), entonces cualquiera sea el conjunto finito \(S\) contenido en \(P\), se tiene que \(\inf(S)\in P\). Cuando tomamos un subconjunto \(S\subseteq P\) el cual es infinito, la cosa cambia sustancialmente. Primero cabe destacar que puede suceder que \(S\) no tenga ínfimo en \((B,\mathsf{s},\mathsf{i},^{c},0,1)\). Pero también puede pasar que \(S\) tenga ínfimo pero que \(\inf(S)\) no pertenezca a \(P\). Por ejemplo, si tomamos el álgebra de Boole \((B,\cup,\cap,^{c},\emptyset,\omega)\), donde \[B=\{X\subseteq\omega:X\text{ es finito o }\omega-X\text{ es finito}\}\] podemos observar que \[P=\{X\subseteq\omega:\omega-X\text{ es finito}\}\] es un filtro primo y que \[S=\{\omega-\{n\}:n\in\omega\}\] esta contenido en \(P\) pero \(\inf(S)=\emptyset\) no pertenece a \(P\).

El siguiente teorema será clave en nuestra prueba del Teorema de Completitud de la lógica de primer orden.

Proof. Sean \(a_{j}=\inf(A_{j})\), \(j=1,2,...\). Construiremos inductivamente una infinitupla \((b_{0},b_{1},...)\) de elementos de \(B\) tal que:

1. adhocprefix(1)adhocsufix \(b_{0}=a\)

2. adhocprefix(2)adhocsufix \(b_{0}\;\mathsf{i\;}\)...\(\;\mathsf{i\;}b_{n}\neq0\), para cada \(n\geq0\)

3. adhocprefix(3)adhocsufix \(b_{j}=a_{j}\) o \(b_{j}^{c}\in A_{j}\), para cada \(j\geq1\).

Definamos \(b_{0}=a\). Supongamos ya definimos \(b_{0},...,b_{n}\), veamos como definir \(b_{n+1}\). Si \((b_{0}\;\mathsf{i\;}...\;\mathsf{i\;}b_{n})\;\mathsf{i\;}a_{n+1}\neq0\), entonces definamos \(b_{n+1}=a_{n+1}\). Si \((b_{0}\;\mathsf{i\;}...\;\mathsf{i\;}b_{n})\;\mathsf{i\;}a_{n+1}=0\), entonces por el lema anterior, tenemos que hay un \(e\in A_{n+1}\) tal que \((b_{0}\;\mathsf{i\;}...\;\mathsf{i\;}b_{n})\;\mathsf{i\;}e^{c}\neq0\), lo cual nos permite definir \(b_{n+1}=e^{c}\).

Usando (2) se puede probar que el conjunto \(S=\{b_{0},b_{1},...\}\) satisface la hipótesis del primer corolario del Teorema del filtro primo, por lo cual hay un filtro primo \(P\) tal que \(\{b_{0},b_{1},...\}\subseteq P\). Es claro que \(a\in P\) y es fácil chequear usando (3) que \(P\) satisface la propiedad (b).  

Cerramos la sección con una convención notacional que se usara mas que nada en los ejercicios y la tómbola.

• Convención Notacional: Nótese que hemos definido distintos tipos de estructuras (i.e. posets, reticulados ternas, etc) y en todas ellas su primera coordenada es llamada el universo de dicha estructura. En general usaremos letras mayúsculas en bold para denotar una estructura dada y en tal caso usaremos la convención de que su correspondiente mayúscula en itálica denotará el universo de dicha estructura. Por ejemplo si decimos "sea \(\mathbf{L}\) un reticulado acotado", entonces ya queda implícita la información de que denotaremos con \(L\) al universo de \(\mathbf{L}\). Además debería quedar claro que en tal caso \(\mathbf{L}\) es una 5-upla. También si \(\mathbf{L}^{\prime}\) denota una estructura, \(L^{\prime}\) denotará su universo. Similarmente si \(\mathbf{\tilde{L}}\) denota una estructura, \(\tilde{L}\) denotará su universo, etc. Nótese que entonces, si escribimos "Sea \(F:\mathbf{L}\rightarrow\mathbf{L}^{\prime}\) es un homomorfismo de reticulados complementados", estaremos suponiendo que \(\mathbf{L}\) y \(\mathbf{L}^{\prime}\) son reticulados complementados (i.e. ciertas 6-uplas) y que \(F\) es una función de \(L\) en \(L^{\prime}\) la cual es un homomorfismo de \(\mathbf{L}\) en \(\mathbf{L}^{\prime}\). Aquí hay que tener cuidado ya que \(D_{F}\) es \(L\) y no \(\mathbf{L}\) lo cual seria imposible ya que \(\mathbf{L}\) no es un conjunto! También nótese que si \(\mathbf{L}\) denota un reticulado acotado y \(\theta\) es una congruencia de \(\mathbf{L}\), entonces \(\mathbf{L}/\theta\) denotará el cociente de \(\mathbf{L}\) sobre \(\theta\), a saber cierto reticulado acotado cuyo universo es \(L/\theta\). Es decir que \(Ti(\mathbf{L}/\theta)=5\mathrm{-UPLA}\) y \(Ti(L/\theta)=\mathrm{CONJUNTO}\)

2.1.8 Reticulados cuaterna y su lenguaje elemental

En esta sección introduciremos un nuevo tipo de estructura que llamaremos reticulado cuaterna, pero nuestra intención aquí no será hacer teoremas similares a los hechos con las estructuras ya estudiadas. De hecho ya lo hicimos en detalle tantas veces que el lector no tendría problema si quisiera definir los conceptos de subestructura, subuniverso, homomorfismo, etc para los reticulados cuaterna. Nuestra intención aquí será delimitar en forma intuitiva un lenguaje muy elemental con el cual se pueden enunciar muchas propiedades matemáticas de los reticulados cuaterna y también con el cual se pueden hacer muchas pruebas interesantes sin salirse de dicho lenguaje elemental (a las cuales llamaremos pruebas elementales). Comencemos con la definición matemática de este nuevo tipo de estructura.

Por un reticulado cuaterna entenderemos una \(4\)-upla \((L,\mathsf{s},\mathsf{i},\leq)\) tal que \(L\) es un conjunto no vacío, \(\mathsf{s}\) e \(\mathsf{i}\) son operaciones binarias sobre \(L\), \(\leq\) es una relación binaria sobre \(L\) y se cumplen las siguientes propiedades:

1. adhocprefix(1)adhocsufix \(x\leq x\), cualesquiera sea \(x\in L\)

2. adhocprefix(2)adhocsufix \(x\leq y\text{ y }y\leq z\text{ implican }x\leq z\), cualesquiera sean \(x,y,z\in L\)

3. adhocprefix(3)adhocsufix \(x\leq y\text{ y }y\leq x\text{ implican }x=y\), cualesquiera sean \(x,y\in L\)

4. adhocprefix(4)adhocsufix \(x\leq x\;\mathsf{s}\;y\text{ y }y\leq x\;\mathsf{s}\;y\), cualesquiera sean \(x,y\in L\)

5. adhocprefix(5)adhocsufix \(x\leq z\text{ y }y\leq z\text{ implican }x\;\mathsf{s}\;y\leq z\), cualesquiera sean \(x,y,z\in L\)

6. adhocprefix(6)adhocsufix \(x\;\mathsf{i}\;y\leq x\text{ y }x\;\mathsf{i}\;y\leq y\), cualesquiera sean \(x,y\in L\)

7. adhocprefix(7)adhocsufix \(z\leq x\text{ y }z\leq y\text{ implican }z\leq x\;\mathsf{i}\;y\), cualesquiera sean \(x,y,z\in L\)

Obviamente (1), (2) y (3) nos garantizan que \((L,\leq)\) es un poset. Nótese que (4) nos dice que cualesquiera sean \(x,y\in L\) se tiene que \(x\;\mathsf{s}\;y\) es cota superior del conjunto \(\{x,y\}\). Además (5) nos dice que cualesquiera sean los elementos \(x,y\in L\), se tiene que \(x\;\mathsf{s}\;y\leq z\), cada vez que \(z\) es cota superior del conjunto \(\{x,y\}\). Por supuesto esto nos garantiza que \(x\;\mathsf{s}\;y=\mathrm{sup}(\{x,y\})\), cualesquiera sean \(x,y\in L\). Similarmente (6) y (7) garantizan que \(x\;\mathsf{s}\;y=\inf(\{x,y\})\), cualesquiera sean \(x,y\in L\).

O sea que, en virtud del Teorema de Dedekind y de los resultados sobre reticulados par probados anteriormente, tenemos que un reticulado cuaterna no es ni mas ni menos que una \(4\)-upla \((L,\mathsf{s},\mathsf{i},\leq)\) tal que \((L,\mathsf{s},\mathsf{i})\) es un reticulado terna y \(\leq\) es su orden parcial asociado. Pero debe quedar claro que este último resultado es un teorema y no la definición de reticulado cuaterna.

Algunos ejemplos de reticulados cuaterna:

1. adhocprefix-adhocsufix \((\mathbf{N},mcm,mcd,|)\)

2. adhocprefix-adhocsufix \((\mathbf{R},max,min,\leq)\), donde \(\leq\) es el orden usual de los números reales

3. adhocprefix-adhocsufix \((\{A\subseteq\mathbf{N}:A\) es finito\(\},\cup,\cap,\subseteq)\)

• Convención Notacional: Muchos conceptos definidos para posets o reticulados terna los usaremos referidos a un reticulado cuaterna. Por ejemplo, si decimos que \((L,\mathsf{s},\mathsf{i},\leq)\) es totalmente ordenado, esto significara que el poset \((L,\leq)\) lo es. Si decimos que \((L,\mathsf{s},\mathsf{i},\leq)\) tiene elemento máximo, esto significara que el poset \((L,\leq)\) lo tiene. Si decimos que en \((L,\mathsf{s},\mathsf{i},\leq)\) el elemento \(a\) cubre al elemento \(b\), esto significara que eso sucede en el poset \((L,\leq)\). Otro ejemplo, si decimos que \((L,\mathsf{s},\mathsf{i},\leq)\) es distributivo, nos estaremos refiriendo a que \((L,\mathsf{s},\mathsf{i})\) es distributivo. También hablaremos del diagrama de Hasse de \((L,\mathsf{s},\mathsf{i},\leq)\) en referencia al diagrama de Hasse de su poset asociado \((L,\leq)\).

En lo que sigue comenzaremos a definir en forma intuitiva el lenguaje elemental de los reticulados cuaterna. Lo que debe quedar claro es que no nos interesa dar definiciones matemáticas rigurosas de estos conceptos sino mas bien dejar bien desarrollada nuestra intuición respecto de los mismos.

2.1.8.1 Términos elementales de reticulados cuaterna

Son palabras que se construyen usando símbolos de la siguiente lista

1. adhocprefix-adhocsufix Paréntesis: \((\;\;)\)

2. adhocprefix-adhocsufix Variables: \(x,y,z,w,...\)

3. adhocprefix-adhocsufix Nombres de elementos fijos: \(a,b,c,d,...\)

4. adhocprefix-adhocsufix Los símbolos: \(\mathsf{s}\text{ }\) \(\text{ }\mathsf{i}\)

Intuitivamente hablando son palabras que representan el resultado de aplicar a las variables y a los nombres de elementos fijos las operaciones \(\mathsf{s}\) e \(\mathsf{i}\) cierta cantidad de veces (posiblemente 0 veces). Algunos ejemplos:

1. adhocprefix-adhocsufix \((x\;\mathsf{s\;}y)\)

2. adhocprefix-adhocsufix \(((a\mathsf{\;i\;}y)\;\mathsf{s}\;z)\)

3. adhocprefix-adhocsufix \(((x\mathsf{\;s\;}y)\;\mathsf{s}\;((x\mathsf{\;s\;}y)\;\mathsf{s}\;z))\)

4. adhocprefix-adhocsufix \((x\mathsf{\;i\;}(x\mathsf{\;i\;}(b\mathsf{\;i\;}x)))\)

5. adhocprefix-adhocsufix \(x\)

6. adhocprefix-adhocsufix \(a\)

Es muy importante entender que los términos elementales de reticulados cuaterna son palabras, es decir \(Ti(t)=\mathrm{PALABRA}\), cada vez que \(t\) es un término elemental de reticulado cuaterna. Por ejemplo el término elemental dado en el primer ejemplo arriba es una palabra de longitud 5 (los espacios no cuentan y son para hacerla mas “legible”) el del quinto ejemplo es una palabra de longitud 1 (la letra \(x\)), etc. No precisaremos bien la lista de variables y la de nombres de elementos fijos pero esto no traerá problemas para el manejo intuitivo que haremos del tema.

Las siguientes reglas constructivas nos aproximan razonablemente al concepto de término elemental de reticulado cuaterna (aunque no sean una definición matemática precisa):

1. adhocprefix(1)adhocsufix Cada variable es un término elemental de reticulados cuaterna

2. adhocprefix(2)adhocsufix Cada nombre de elemento fijo es un término elemental de reticulados cuaterna

3. adhocprefix(3)adhocsufix Si \(t\) y \(s\) son términos elementales de reticulados cuaterna, entonces la palabra \((t\;\mathsf{s\;}s)\) es un término elemental de reticulados cuaterna

4. adhocprefix(4)adhocsufix Si \(t\) y \(s\) son términos elementales de reticulados cuaterna, entonces la palabra \((t\;\mathsf{i\;}s)\) es un término elemental de reticulados cuaterna

5. adhocprefix(5)adhocsufix Una palabra es un término elemental de reticulados cuaterna si y solo si se puede construir usando las clausulas anteriores

Debería quedar claro que arriba \((t\;\mathsf{s\;}s)\) denota el resultado de concatenar las 5 siguientes palabras \[(\;\;\;\;\;\;t\;\;\;\;\;\;\;\;\;\mathsf{s\;}\;\;\;\;\;\;\;s\;\;\;\;\;\;\;\;\;)\] es decir que \((t\;\mathsf{s\;}s)\) es una palabra de longitud \(\left|t\right|+\left|s\right|+3\).

Valores que asumen o representan los términos elementales

Para que un término elemental \(t\) represente o asuma un valor debemos tener un reticulado cuaterna concreto y asignarle valores a las variables y a los nombres de elementos fijos que ocurren en \(t\). Algunos ejemplos:

1. adhocprefix-adhocsufix En el reticulado cuaterna \((\mathbf{N},mcm,mcd,|)\), el término elemental \(((x\mathsf{\;i\;}b))\), cuando le asignamos a \(x\) el valor \(200\) y a \(b\) el valor \(300\), asume el valor 100 (ya que \(mcd(200,300)=100\)).

2. adhocprefix-adhocsufix En el reticulado cuaterna \((\mathbf{N},mcm,mcd,|)\), el término elemental \(z\), cuando le asignamos a \(z\) el valor \(200\) asume el valor 200.

3. adhocprefix-adhocsufix En el reticulado cuaterna \((\mathbf{N},mcm,mcd,|)\), el término elemental \(((x\mathsf{\;i\;}y)\;\mathsf{s}\;z)\), cuando le asignamos a \(x\) el valor \(20\) a \(y\) el valor 12 y a \(z\) el valor 100, asume el valor 100 (ya que \(mcm(mcd(20,12),100)=100\)).

4. adhocprefix-adhocsufix En el reticulado cuaterna \((\{A\subseteq\mathbf{N}:A\text{ es finito}\},\cup,\cap,\subseteq)\), el término elemental \(((x\mathsf{\;i\;}y)\mathsf{\;i\;}z)\), cuando le asignamos a \(x\) el valor \(\{1,5,9\}\) a \(y\) el valor \(\{5,6,9,1000\}\) y a \(z\) el valor \(\{9\}\), asume el valor \(\{9\}\) (ya que \((\{1,5,9\}\cap\{5,6,9,1000\})\cap\{9\}=\{9\}\)).

Es muy importante no confundir un término elemental con el valor que asume en un determinado reticulado cuaterna, para alguna asignación de valores a sus variables y nombres de elementos fijos. Por ejemplo los términos elementales \((x\mathsf{\;i\;}y)\) y \((y\mathsf{\;i\;}x)\) son distintos y sin embargo asumen siempre el mismo valor cualquiera sea el reticulado cuaterna que consideremos y cualquiera sea la asignación de valores que tomemos para las variables \(x\) e \(y\).

Términos elementales puros

Un término elemental de reticulados cuaterna será llamado puro cuando en el no ocurran nombres de elementos fijos.

2.1.8.2 fórmulas elementales de reticulados cuaterna

Las fórmulas elementales de reticulados cuaterna son palabras que se construyen usando símbolos de la siguiente lista:

1. adhocprefix-adhocsufix \(\forall\ \exists\;\lnot\;\vee\;\wedge\;\rightarrow\;\leftrightarrow\;(\;)\;=\;\mathsf{s\;}\mathsf{i\;}\leq\)

2. adhocprefix-adhocsufix Variables: \(x,y,z,w,...\)

3. adhocprefix-adhocsufix Nombres de elementos fijos: \(a,b,c,d,...\)

Es decir que, mas allá de que no daremos una definición matemática rigurosa del concepto de fórmula elemental de reticulados cuaterna, es importante entender que son meras palabras, es decir \(Ti(\varphi)=\mathrm{PALABRA}\), cada ves que \(\varphi\) es una fórmula elemental de reticulado cuaterna. Antes de dar una descripción mas completa del concepto, veamos algunos ejemplos concretos:

1. adhocprefix-adhocsufix \((x\leq y)\)

2. adhocprefix-adhocsufix \((x=y)\)

3. adhocprefix-adhocsufix \(((x\;\mathsf{s\;}y)=a)\)

4. adhocprefix-adhocsufix \(((a\;\mathsf{s\;}z)\;\mathsf{i\;}x)=((x\;\mathsf{i\;}y)\;\mathsf{s\;}x))\)

5. adhocprefix-adhocsufix \((((a\leq z)\wedge(x=y))\wedge\lnot(x=y))\)

6. adhocprefix-adhocsufix \(\lnot\exists y((x\;\mathsf{s\;}y=y)\wedge\lnot(x=y))\)

7. adhocprefix-adhocsufix \(\forall x\forall y\forall z(((x\leq y)\wedge(y\leq z))\rightarrow(x\leq z))\)

8. adhocprefix-adhocsufix \(\forall x\exists y((x\;\mathsf{s\;}y)=a)\)

9. adhocprefix-adhocsufix \(\forall x\forall y\forall z\forall w(((x\leq z)\wedge(y\leq w))\rightarrow((x\;\mathsf{s}\ y)\leq(z\;\mathsf{s}\ w)))\)

Como puede notarse es muy común que una fórmula elemental tenga a términos elementales como subpalabras aunque los términos elementales tienen un distinto significado que las fórmulas elementales ya que ellos representan elementos y las fórmulas elementales son palabras que cuando las interpretamos adecuadamente se vuelven verdaderas o falsas. Las siguientes reglas constructivas nos aproximan razonablemente al concepto de fórmula elemental de reticulado cuaterna (aunque no sean una definición matemática precisa):

1. adhocprefix(1)adhocsufix Si \(t\) y \(s\) son términos elementales de reticulados cuaterna, entonces la palabra \((t=s)\) es una fórmula elemental de reticulados cuaterna

2. adhocprefix(2)adhocsufix Si \(t\) y \(s\) son términos elementales de reticulados cuaterna, entonces la palabra \((t\leq s)\) es una fórmula elemental de reticulados cuaterna

3. adhocprefix(3)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados cuaterna, entonces la palabra \((\varphi_{1}\wedge\varphi_{2})\) es una fórmula elemental de reticulados cuaterna

4. adhocprefix(4)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados cuaterna, entonces la palabra \((\varphi_{1}\vee\varphi_{2})\) es una fórmula elemental de reticulados cuaterna

5. adhocprefix(5)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados cuaterna, entonces la palabra \((\varphi_{1}\leftrightarrow\varphi_{2})\) es una fórmula elemental de reticulados cuaterna

6. adhocprefix(6)adhocsufix Si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales de reticulados cuaterna, entonces la palabra \((\varphi_{1}\rightarrow\varphi_{2})\) es una fórmula elemental de reticulados cuaterna

7. adhocprefix(7)adhocsufix Si \(\varphi\) es una fórmula elemental de reticulados cuaterna, entonces la palabra \(\lnot\varphi\) es una fórmula elemental de reticulados cuaterna

8. adhocprefix(8)adhocsufix Si \(\varphi\) es una fórmula elemental de reticulados cuaterna, entonces las palabras \[\forall x\varphi\;\;\;\forall y\varphi\;\;\;\forall z\varphi\;\;\;...\] son fórmulas elementales de reticulados cuaterna

9. adhocprefix(9)adhocsufix Si \(\varphi\) es una fórmula elemental de reticulados cuaterna, entonces las palabras \[\exists x\varphi\;\;\;\exists y\varphi\;\;\;\exists z\varphi\;\;\;...\] son fórmulas elementales de reticulados cuaterna

10. adhocprefix(10)adhocsufix Una palabra es una fórmula elemental de reticulados cuaterna si y solo si se puede construir usando las clausulas anteriores

Debería quedar claro que, por ejemplo, arriba \((\varphi_{1}\wedge\varphi_{2})\) denota el resultado de concatenar las 5 siguientes palabras \[(\;\;\;\;\;\;\varphi_{1}\;\;\;\;\;\;\;\;\;\wedge\;\;\;\;\;\;\;\varphi_{2}\;\;\;\;\;\;\;\;\;)\] es decir que \((\varphi_{1}\wedge\varphi_{2})\) es una palabra de longitud \(\left|\varphi_{1}\right|+\left|\varphi_{2}\right|+3\). Nótese que siempre "cuantificamos por delante", es decir que la palabra \((x\leq a)\forall x\) NO es una fórmula elemental de reticulados cuaterna. Tampoco se cuantificaran los nombres de elementos fijos, es decir solo cuantificamos variables. O sea que \(\forall a(a=x)\) no es una fórmula elemental.

• Observación Importante: Nótese que según los items (7), (8) y (9), cuando “negamos” y cuando “cuantificamos”, no agregamos paréntesis. Solo agregamos paréntesis cuando “nexamos” un par de fórmulas. Esto hay que tenerlo en cuenta para leer las fórmulas. Por ejemplo la fórmula \((\exists z(a\leq z)\wedge(b\leq z))\) debe leerse como la conjunción de las fórmulas \(\exists z(a\leq z)\) y \((b\leq z)\) y no pensarse como una fórmula que dice “\(\exists z\text{ tal que }(a\leq z)\wedge(b\leq z)\)”. Sucede algo similar con la negación. Es decir si \(\varphi_{1}\) y \(\varphi_{2}\) son fórmulas elementales entonces la fórmula elemental \((\lnot\varphi_{1}\wedge\varphi_{2})\) debe leerse como la conjunción de \(\lnot\varphi_{1}\) y \(\varphi_{2}\) y no pensarse como una fórmula que dice “no es verdad que \(\varphi_{1}\wedge\varphi_{2}\)”. O sea, los cuantificadores y la negación tienen precedencia sobre los nexos lógicos.

Fórmulas elementales puras

Una fórmula elemental de reticulados cuaterna será llamada pura cuando en ella no ocurran nombres de elementos fijos. Nótese que en particular los términos que ocurran en una fórmula elemental pura serán también puros.

Valor de verdad de una fórmula elemental

Para que una fórmula elemental se vuelva verdadera o falsa tenemos que tener un reticulado cuaterna concreto \((L,\mathsf{s},\mathsf{i},\leq)\) y además asignar valores concretos de \(L\) a las variables libres y a los nombres de elementos fijos que ocurren en dicha fórmula. También cabe destacar que los cuantificadores siempre ranguean sobre \(L\), es decir \(\forall x\) se interpretara como \(\forall x\in L\) y \(\exists x\) se interpretara como \(\exists x\in L\). Veamos algunos ejemplos concretos:

1. adhocprefix-adhocsufix La fórmula elemental \((x\leq y)\) tiene a las variables \(x\) e \(y\) libres y en el reticulado cuaterna \((\mathbf{N},mcm,mcd,|)\) es verdadera cuando le asignamos a \(x\) el valor \(6\) y a \(y\) el valor \(36\). Esto es ya que interpretamos a \(\leq\) como la relación \(|\) y \(6\text{ divide a }36\)

2. adhocprefix-adhocsufix La fórmula elemental \((((a\;\mathsf{s\;}y)=y)\vee((y\;\mathsf{s\;}a)=a))\) tiene a \(y\) como su única variable libre y en el reticulado cuaterna \((\mathbf{N},mcm,mcd,|)\) es falsa cuando le asignamos a \(a\) el valor \(5\) y a \(y\) el valor \(11\) y verdadera cuando le asignamos a \(a\) el valor \(5\) y a \(y\) el valor \(10\). Esta fórmula es verdadera en el reticulado cuaterna \((\mathbf{N},max,min,\leq)\) para cualquier asignación de valores a \(a\) y a \(y\).

3. adhocprefix-adhocsufix La fórmula elemental \(\exists y((y\leq x)\wedge\lnot(y=x))\) tiene a \(x\) como su única variable libre y en el reticulado cuaterna \((\{A\subseteq\mathbf{N}:A\text{ es finito}\},\cup,\cap,\subseteq)\) es verdadera cuando le asignamos a \(x\) cualquier valor distinto de \(\emptyset\) y es falsa cuando le asignamos a \(x\) el valor \(\emptyset\)

4. adhocprefix-adhocsufix La fórmula elemental \(((\lnot(x=y)\wedge\lnot(x=z))\wedge\lnot(y=z))\) es verdadera en un reticulado cuaterna si y solo si los valores que le asignamos a las variables \(x\), \(y\) y \(z\) son distintos entre si.

Por supuesto, cuando la fórmula elemental es pura, su valor de verdad en un reticulado cuaterna dado solo depende de que valores asignemos a sus variables libres. También es bueno pensar que

1. adhocprefix-adhocsufix La fórmula elemental \(\forall y(x\leq y)\) dice \[x\text{ es un elemento minimo de }(L,\mathsf{s},\mathsf{i},\leq)\] en el sentido que ella será verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo si el valor asignado a \(x\) es un elemento mínimo de \((L,\mathsf{s},\mathsf{i},\leq)\).

2. adhocprefix-adhocsufix La fórmula elemental \(\forall y(y\leq b)\) dice \[b\text{ es un elemento maximo de }(L,\mathsf{s},\mathsf{i},\leq)\] en el sentido que ella será verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo el valor asignado a \(b\) es un elemento máximo de \((L,\mathsf{s},\mathsf{i},\leq)\).

3. adhocprefix-adhocsufix La fórmula elemental \(((x\leq y)\wedge\lnot(y=x))\) dice \(x\) es menor que \(y\) en \((L,\mathsf{s},\mathsf{i},\leq)\)

4. adhocprefix-adhocsufix La fórmula elemental \(\lnot\exists z((x\leq z)\wedge\lnot(z=x))\) dice \(x\) es un elemento maximal de \((L,\mathsf{s},\mathsf{i},\leq)\)

Sentencias elementales

Cuando una fórmula elemental de reticulados cuaterna no tiene variables libres diremos que es una sentencia elemental de reticulados cuaterna. Algunos ejemplos de sentencias elementales de reticulados cuaterna:

1. adhocprefix-adhocsufix \(\forall x(a\leq x)\)

2. adhocprefix-adhocsufix \(\exists x\exists y\lnot(x=y)\)

3. adhocprefix-adhocsufix \(\forall x\forall y((x\leq y)\vee(y\leq x))\)

4. adhocprefix-adhocsufix \(\exists x\exists y((((a\;\mathsf{s\;}x)=(a\;\mathsf{s\;}y))\wedge\lnot(x\leq y))\wedge\lnot(y\leq x))\)

Nótese que una sentencia elemental de reticulados cuaterna será verdadera o falsa en \((L,\mathsf{s},\mathsf{i},\leq)\) dependiendo solo de los valores que tomen los nombres de elementos fijos que ocurren en ella. Y si ella es pura (i.e. no ocurren en ella nombres de elementos fijos), entonces dado un reticulado cuaterna concreto, la sentencia resulta verdadera o falsa. Por ejemplo:

1. adhocprefix-adhocsufix La sentencia elemental \(\forall x(a\leq x)\) es verdadera en el reticulado cuaterna \((\{A\subseteq\mathbf{N}:A\text{ es finito}\},\cup,\cap,\subseteq)\) cuando le asignamos a \(a\) el valor \(\emptyset\) y falsa cuando le asignamos cualquier otro valor de \(\{A\subseteq\mathbf{N}:A\text{ es finito}\}\)

2. adhocprefix-adhocsufix La sentencia elemental pura \(\exists x\exists y\lnot(x=y)\) es verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo si \(L\) tiene al menos dos elementos distintos.

3. adhocprefix-adhocsufix La sentencia elemental pura \(\forall x\forall y((x\leq y)\vee(y\leq x))\) es verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo si el poset \((L,\leq)\) es un conjunto totalmente ordenado

4. adhocprefix-adhocsufix La sentencia elemental \[\exists x\exists y((((a\;\mathsf{s\;}x)=(a\;\mathsf{s\;}y))\wedge\lnot(x\leq y))\wedge\lnot(y\leq x))\] es verdadera en el reticulado cuaterna \((\mathcal{P}(\{0,1,2\}),\cup,\cap,\subseteq)\) cuando le asignamos a \(a\) el valor \(\{0,1\}\) y es falsa cuando le asignamos a \(a\) el valor \(\{0\}\) o el valor \(\emptyset\)

Un poco mas sobre variables libres

Ya que el tema de cuando una variable es libre o no, es bastante delicado, nos explayaremos un poco mas. Primero deberíamos notar que si una variable ocurre varias veces en una fórmula, entonces algunas de aquellas ocurrencias serán libres y otras no. Por ejemplo

1. adhocprefix-adhocsufix En la fórmula \(((x\leq a)\wedge\forall x(b\leq x))\) la primer ocurrencia de \(x\) es libre y las otras dos ocurrencias de \(x\) no son libres

Como es usual a las ocurrencias que no son libres las llamaremos acotadas. O sea que toda ocurrencia de una variable en una fórmula es ya sea libre o acotada. Por ejemplo, en la fórmula \[(((a\;\mathsf{s\;}b)\leq y)\wedge\forall y((z\;\mathsf{s\;}b)\leq y))\] la variable \(y\) ocurre tres veces, la primera ocurrencia es libre y la segunda y tercera son acotadas.

Cuando digamos que \(x\) es una variable libre de una fórmula elemental \(\varphi\) nos estaremos refiriendo a que la variable \(x\) ocurre al menos una ves libremente en \(\varphi\), aunque también puede ocurrir acotadamente en \(\varphi\). Por ejemplo:

1. adhocprefix-adhocsufix \(x\) es una variable libre de la fórmula \(((x\leq a)\wedge\forall x(b\leq x))\) (aunque ocurre acotadamente)

2. adhocprefix-adhocsufix Las variables libres de la fórmula \[(((x\leq z)\vee\exists x\forall y((a\leq x)\wedge(y\leq x)))\rightarrow\forall y(z\leq y))\] son \(x\) y \(z\). Las dos ocurrencias de \(z\) son libres, todas las ocurrencias de \(y\) son acotadas, la primer ocurrencia de \(x\) es libre y las otras tres ocurrencias de \(x\) son acotadas.

Alcance de la ocurrencia de un cuantificador

Un cuantificador será una palabra formada por alguno de los símbolos \[\forall\ \ \ \ \exists\] seguido de una variable. Es decir \[\exists x\ \ \ \forall x\ \ \ \exists y\ \ \ \forall y\ \ \ \exists z\ \ \ \forall z\ \ \ldots\] son los cuantificadores.

Una propiedad importante de las fórmulas elementales es que siempre que un cuantificador ocurra en una fórmula elemental, seguido a dicha ocurrencia ocurrirá una fórmula elemental (la cual además es única). Ejemplos:

1. adhocprefix-adhocsufix En la fórmula \[(((x\leq y)\wedge\forall y\lnot(y=a))\rightarrow\forall y((z\;\mathsf{s\;}y)\leq y))\] seguido a la segunda ocurrencia del cuantificador \(\forall y\) ocurre la fórmula \(((z\;\mathsf{s\;}y)\leq y)\) y seguido a la primer ocurrencia del cuantificador \(\forall y\) ocurre la fórmula \(\lnot(y=a)\).

2. adhocprefix-adhocsufix En la fórmula \[\forall x\forall y((x\leq y)\vee(y\leq x))\] seguido a la única ocurrencia del cuantificador \(\forall y\) ocurre la fórmula \(((x\leq y)\vee(y\leq x))\) y seguido a la única ocurrencia del cuantificador \(\forall x\) ocurre la fórmula \(\forall y((x\leq y)\vee(y\leq x))\)

Llamaremos a esta fórmula elemental única que sigue a la ocurrencia de un cuantificador el alcance de dicha ocurrencia. En los siguientes ejemplos subrayaremos algunos alcances de ocurrencias de cuantificadores.

1. adhocprefix-adhocsufix En la fórmula \[((((x\leq y)\wedge\forall y\underline{\lnot(y=a)})\rightarrow\forall y((z\;\mathsf{i\;}y)\leq y))\vee(x\leq z))\] hemos subrayado el alcance de la primer ocurrencia del cuantificador \(\forall y\).

2. adhocprefix-adhocsufix En la fórmula \[\forall x\underline{\forall y((x\leq y)\vee(y\leq x))}\] hemos subrayado el alcance de la única ocurrencia del cuantificador \(\forall x\).

3. adhocprefix-adhocsufix En la fórmula \[(((x\leq z)\vee\exists x\underline{\forall y((a\leq(x\;\mathsf{i\;}b))\wedge(y\leq x))})\rightarrow\exists x(x\leq(y\;\mathsf{i\;}c)))\] hemos subrayado el alcance de la primer ocurrencia del cuantificador \(\exists x\).

Es importante notar que no tiene sentido hablar a secas del alcance de un cuantificador en una fórmula ya que el mismo cuantificador puede ocurrir varias veces en dicha fórmula y tener distintos alcances cada una de las distintas ocurrencias. Es decir el concepto de alcance es relativo a una ocurrencia de un cuantificador. Por ejemplo

1. adhocprefix-adhocsufix En la fórmula \[((((x\leq y)\wedge\forall y\lnot(y=a))\rightarrow\forall y(z\leq y))\vee(x\leq z))\] el alcance de la primer ocurrencia del cuantificador \(\forall y\) es \(\lnot(y=a)\) y el alcance de la segunda ocurrencia de \(\forall y\) es \((z\leq y)\).

Nótese que una ocurrencia de una variable \(v\) en una fórmula elemental \(\varphi\) será acotada si y solo si ella sucede dentro de una ocurrencia en \(\varphi\) de una fórmula de la forma \(Qv\psi\), con \(Q\in\{\forall,\exists\}\) y \(\psi\) una fórmula elemental.

Además debería quedar claro que el rol jugado por una variable \(v\) en sus ocurrencias acotadas dentro de una ocurrencia en \(\varphi\) de una fórmula de la forma \(Qv\psi\) es "mudo" o "impersonal" en el sentido que podríamos reemplazar dichas ocurrencias de \(v\) por una variable \(w\) que no figure en la fórmula \(\psi\) y el significado de la fórmula resultante seria el mismo que el significado de \(\varphi\). Por ejemplo la fórmula \[\varphi=(\lnot(x=a)\wedge\forall y((x\leq y)\vee(y\leq x)))\] nos "dice" que \(x\) es distinto a \(a\) y que \(x\) es comparable con todo elemento de \(L\); y si reemplazamos cada ocurrencia de \(y\) en el bloque \(\forall y((x\leq y)\vee(y\leq x))\) por la variable \(z\), obtenemos \[(\lnot(x=a)\wedge\forall z((x\leq z)\vee(z\leq x)))\] la cual claramente dice lo mismo acerca de \(x\) y \(a\).

• Aviso Importante: Ya tenemos una intuición bien clara del concepto de fórmula elemental y en esta etapa no nos interesa ser puntillosos en la escritura por lo cual muchas veces para hacer mas dinámica la exposición suprimiremos algunos paréntesis. Algunos ejemplos:

  • En lugar de escribir \(((x\leq y)\wedge(y\leq z))\) escribiremos \(x\leq y\wedge y\leq z\)

  • En lugar de escribir \(((x\leq y)\wedge(y\leq z))\vee(a=b))\) escribiremos \((x\leq y\wedge y\leq z)\vee a=b\)

  • En lugar de escribir \(((a\leq b)\wedge(x\leq y))\wedge(z=c))\) escribiremos \(a\leq b\wedge x\leq y\wedge z=c\)

  • En lugar de escribir \((a\leq(x\;\mathsf{i\;}b))\) escribiremos \(a\leq x\;\mathsf{i\;}b\)

  • En lugar de escribir \(((a\;\mathsf{s\;}x)=(a\;\mathsf{s\;}y))\) escribiremos \(a\;\mathsf{s\;}x=a\;\mathsf{s\;}y\)

Limitaciones del poder expresivo de las fórmulas elementales

Hay muchas propiedades de los reticulados cuaterna que no se pueden “decir” usando sentencias elementales puras. Por ejemplo no hay una sentencia elemental pura de reticulados cuaterna la cual cumpla que es verdadera en un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) si y solo si \(L\) es un conjunto finito. Por supuesto esto lo podemos “decir” de la siguiente manera \[\exists x_{1}\exists x_{2}...\exists x_{n}\forall z((z=x_{1})\vee(z=x_{2})\vee...\vee(z=x_{n}))\] pero aquí el problema es que \(n\) hace referencia a algún natural que puede variar y no podemos reemplazarlo por uno concreto ya que entonces la sentencia solo valdría en los reticulados cuaterna con a lo sumo esa cantidad de elementos. Es decir las fórmulas elementales en general no pueden expresar la existencia de una sucesión finita de elementos, solo la existencia de una cantidad concreta fija de elementos. O sea se puede “decir” existen tres elementos tales que ... o “decir” existen 10 elementos tales que ... pero no se puede “decir” existen \(n\) elementos tales que ... , pensando que \(n\) es algún natural. Una prueba de esta imposibilidad de “decir” con una sentencia elemental que el universo de \((L,\mathsf{s},\mathsf{i},\leq)\) es finito es consecuencia directa del Teorema de Compacidad que veremos mas adelante.

2.1.8.3 Pruebas elementales de reticulados cuaterna

Nótese que las propiedades (1), ... ,(7) que definen reticulado cuaterna pueden ser escritas como sentencias elementales puras de reticulados cuaterna:

1. adhocprefixadhocsufix \(\mathrm{A}_{\leq R}=\forall x(x\leq x)\)

2. adhocprefixadhocsufix \(\mathrm{A}_{\leq T}=\forall x\forall y\forall z((x\leq y\wedge y\leq z)\rightarrow x\leq z)\)

3. adhocprefixadhocsufix \(\mathrm{A}_{\leq A}=\forall x\forall y((x\leq y\wedge y\leq x)\rightarrow x=y)\)

4. adhocprefixadhocsufix \(\mathrm{A}_{\mathsf{s}esC}=\forall x\forall y(x\leq x\;\mathsf{s}\;y\wedge y\leq x\;\mathsf{s}\;y)\)

5. adhocprefixadhocsufix \(\mathrm{A}_{\mathsf{s}\leq C}=\forall x\forall y\forall z((x\leq z\wedge y\leq z)\rightarrow x\;\mathsf{s}\;y\leq z)\)

6. adhocprefixadhocsufix \(\mathrm{A}_{\mathsf{i}esC}=\forall x\forall y(x\;\mathsf{i}\;y\leq x\wedge x\;\mathsf{i}\;y\leq y)\)

7. adhocprefixadhocsufix \(\mathrm{A}_{\mathsf{i}\geq C}=\forall x\forall y\forall z((z\leq x\wedge z\leq y)\rightarrow z\leq x\;\mathsf{i}\;y)\)

Llamaremos a estas sentencias elementales puras los axiomas elementales de reticulados cuaterna. El nombre \(\mathrm{A}_{\leq R}\) hace referencia a que esta sentencia “dice” que la relación \(\leq\) es reflexiva. El nombre \(\mathrm{A}_{\mathsf{s}esC}\) hace referencia a que esta sentencia “dice” que \(x\;\mathsf{s}\;y\) es cota superior del conjunto \(\{x,y\}\). El nombre \(\mathrm{A}_{\mathsf{s}\leq C}\) hace referencia a que esta sentencia “dice” que \(x\;\mathsf{s}\;y\) es menor o igual a cualquier cota superior del conjunto \(\{x,y\}\). Los otros nombres fueron elegidos en forma análoga.

Muchas propiedades que son ciertas en todos los reticulados cuaterna se pueden escribir usando sentencias elementales puras de reticulados cuaterna. Por ejemplo la sentencia elemental pura \(\rho=\forall x\forall y(x\;\mathsf{s}\;y=y\;\mathsf{s}\;x)\) es cierta en cada reticulado cuaterna. Esto nosotros lo sabemos ya que en un reticulado cuaterna los axiomas \(\mathrm{A}_{\mathsf{s}esC}\) y \(\mathrm{A}_{\mathsf{s}\leq C}\) nos garantizan que \(x\;\mathsf{s}\;y=\mathrm{sup}\{x,y\}\) y obviamente \(\mathrm{sup}\{x,y\}=\mathrm{sup}\{y,x\}\). Pero esta prueba o justificación de \(\rho\) usa la expresión \(\mathrm{sup}\{x,y\}\), la cual no forma parte de las fórmulas elementales. Nos interesa dar una prueba muy especial de \(\rho\) en el sentido que se cumplan las siguientes características

1. adhocprefix(1)adhocsufix En la prueba se parte de una estructura \((L,\mathsf{s},\mathsf{i},\leq)\) fija pero arbitraria en el sentido lo único que sabemos de ella es:

   1. adhocprefix-adhocsufix \(L\) es un conjunto no vacío

   2. adhocprefix-adhocsufix \(\mathsf{s}\) e \(\mathsf{i}\) son operaciones binarias sobre \(L\)

   3. adhocprefix-adhocsufix \(\leq\) es una relación binaria sobre \(L\)

   4. adhocprefix-adhocsufix \((L,\mathsf{s},\mathsf{i},\leq)\) satisface los axiomas \(\mathrm{A}_{\leq R}\), \(\mathrm{A}_{\leq A}\), \(\mathrm{A}_{\leq T}\), \(\mathrm{A}_{\mathsf{s}esC}\), \(\mathrm{A}_{\mathsf{s}\leq C}\), \(\mathrm{A}_{\mathsf{i}esC}\) , \(\mathrm{A}_{\mathsf{i}\geq C}\)

   (O sea esta es la única información particular de \((L,\mathsf{s},\mathsf{i},\leq)\) que podemos usar).

2. adhocprefix(2)adhocsufix Las deducciones de la prueba son muy simples y obvias de justificar con mínimas frases en castellano.

3. adhocprefix(3)adhocsufix En la escritura de la prueba lo concerniente a la matemática misma se expresa usando solo sentencias elementales de reticulados cuaterna.

Llamaremos a las pruebas que tengan estas características, pruebas elementales de reticulados cuaterna. Veamos una prueba de \(\rho\) con estas características. Recordemos que en la prueba partiremos de una estructura \((L,\mathsf{s},\mathsf{i},\leq)\) fija de la cual solo sabemos que satisface los axiomas \(\mathrm{A}_{\leq R}\), \(\mathrm{A}_{\leq A}\), \(\mathrm{A}_{\leq T}\), \(\mathrm{A}_{\mathsf{s}esC}\), \(\mathrm{A}_{\mathsf{s}\leq C}\), \(\mathrm{A}_{\mathsf{i}esC}\) , \(\mathrm{A}_{\mathsf{i}\geq C}\).

Proof. Sean \(a,b\in L\) elementos fijos pero arbitrarios. Por el axioma \(\mathrm{A}_{\mathsf{s}esC}\) (instanciado haciendo \(x=b\) y \(y=a\)) tenemos que \[b\leq b\;\mathsf{s}\;a\wedge a\leq b\;\mathsf{s}\;a\] De lo cual sacamos obviamente que \[a\leq b\;\mathsf{s}\;a\wedge b\leq b\;\mathsf{s}\;a\] Además el axioma \(\mathrm{A}_{\mathsf{s}\leq C}\) (instanciado haciendo \(x=a\), \(y=b\) y \(z=b\;\mathsf{s}\;a\)) nos dice que \[\left((a\leq b\;\mathsf{s}\;a\wedge b\leq b\;\mathsf{s}\;a)\rightarrow a\;\mathsf{s}\;b\leq b\;\mathsf{s}\;a\right)\] O sea que de las últimas dos sentencias obtenemos trivialmente que \[a\;\mathsf{s}\;b\leq b\;\mathsf{s}\;a\] En forma análoga se puede probar que \[b\;\mathsf{s}\;a\leq a\;\mathsf{s}\;b\] Lo cual nos dice trivialmente que \[a\;\mathsf{s}\;b\leq b\;\mathsf{s}\;a\wedge b\;\mathsf{s}\;a\leq a\;\mathsf{s}\;b\] Pero el axioma \(\mathrm{A}_{\leq A}\) nos dice que \[(a\;\mathsf{s}\;b\leq b\;\mathsf{s}\;a\wedge b\;\mathsf{s}\;a\leq a\;\mathsf{s}\;b)\rightarrow a\;\mathsf{s}\;b=b\;\mathsf{s}\;a\] De lo cual obviamente obtenemos que \[a\;\mathsf{s}\;b=b\;\mathsf{s}\;a\] Ya que \(a,b\) eran elementos fijos pero arbitrarios, hemos probado que \[\forall x\forall y(x\;\mathsf{s}\;y=y\;\mathsf{s}\;x)\]  

Por supuesto, en la parte de la prueba en la que decimos "En forma análoga se puede probar que \(b\;\mathsf{s}\;a\leq a\;\mathsf{s\;}\)\(b\)" deberíamos poner las lineas que corresponden para obtener realmente la prueba elemental (si no lo hacemos la prueba no es una prueba elemental ya que la justificación “en forma análoga se puede probar ...” no es lo suficientemente simple y obvia).

Muchas de las pruebas dadas en la Sección de Reticulados Par pueden adaptarse naturalmente para ser pruebas elementales de reticulados cuaterna. Para hacer esta adaptación nótese que el axioma \(\mathrm{A}_{\leq A}\) puede ser usado en lugar de aplicar la regla Igualdad en Posets (así lo hicimos en la prueba de recién) y similarmente los axiomas \(\mathrm{A}_{\mathsf{s}\leq C}\) y \(\mathrm{A}_{\mathsf{i}\geq C}\) se pueden usar en lugar de las reglas Superar un Supremo y Ser \(\leq\) que un Ínfimo.

Ahora daremos una prueba elemental de la sentencia elemental pura \(\mu=\forall x\forall y(x\leq y\leftrightarrow x\;\mathsf{s}\;y=y)\). Obviamente sabemos que \(\mu\) es verdadera en cada reticulado cuaterna pero queremos una prueba elemental. Recordemos que en la prueba partiremos de una estructura \((L,\mathsf{s},\mathsf{i},\leq)\) fija de la cual solo sabemos que satisface los axiomas \(\mathrm{A}_{\leq R}\), \(\mathrm{A}_{\leq A}\), \(\mathrm{A}_{\leq T}\), \(\mathrm{A}_{\mathsf{s}esC}\), \(\mathrm{A}_{\mathsf{s}\leq C}\), \(\mathrm{A}_{\mathsf{i}esC}\) , \(\mathrm{A}_{\mathsf{i}\geq C}\) .

Proof. Sean \(a,b\in L\) elementos fijos. Supongamos que \(a\leq b\). Probaremos que \(a\;\mathsf{s}\;b=b\). Por el axioma \(\mathrm{A}_{\mathsf{s}\leq C}\) tenemos que \[\left((a\leq b\wedge b\leq b)\rightarrow a\;\mathsf{s}\;b\leq b\right)\] Pero por el axioma \(\mathrm{A}_{\leq R}\) tenemos que \(b\leq b\) y por hipótesis tenemos que \(a\leq b\) por lo cual \[a\leq b\wedge b\leq b\] Obviamente esto nos dice que \(a\;\mathsf{s\;}\)\(b\leq b\). Además por el axioma \(\mathrm{A}_{\mathsf{s}esC}\) tenemos que \[b\leq a\;\mathsf{s}\;b\] O sea que hemos probado \[a\;\mathsf{s\;}b\leq b\wedge b\leq a\;\mathsf{s\;}b\] Lo cual por el axioma \(\mathrm{A}_{\leq A}\) nos dice que \(a\;\mathsf{s}\;b=b\). Ya que habíamos asumido que \(a\leq b\) en realidad hemos probado que \[a\leq b\rightarrow a\;\mathsf{s}\;b=b\] Supongamos ahora que \(a\;\mathsf{s}\;b=b\). Por el axioma \(\mathrm{A}_{\mathsf{s}esC}\) tenemos que \(a\leq a\;\mathsf{s}\;b\). Ya que \(a\;\mathsf{s}\;b=b\) obtenemos que \(a\leq b\). O sea que realmente hemos probado que \[a\;\mathsf{s}\;b=b\rightarrow a\leq b\] Lo cual por la otra implicación probada nos dice que \[a\leq b\leftrightarrow a\;\mathsf{s}\;b=b\] Ya que \(a,b\) eran elementos fijos pero arbitrarios, hemos probado que \[\forall x\forall y(x\leq y\leftrightarrow x\;\mathsf{s}\;y=y)\]  

• Consejos Importantes: Por favor contengan a su escarabajo interior...

  • Cuando queramos hacer una prueba elemental de alguna sentencia elemental pura es importante no perder nuestro rol de matemáticos y creer que porque debemos realizar la prueba escribiendo las cosas con sentencias elementales debemos dejar de pensar como matemáticos y volvernos escarabajos sintácticos mecánicos que solo usan reglas y van encadenando sentencias elementales sin pensar e imaginar. Es decir, debemos hacer la prueba a lo mariposa pensando, imaginando. Tal como lo venimos haciendo en las guías anteriores pero agregando la consigna de que a la matemática involucrada la escribamos usando sentencias elementales.

  • Una buena manera de hacer una prueba elemental de una sentencia elemental pura \(\varphi\) es primero hacer la prueba matemática sin fijarse demasiado si es elemental o no. Es decir partir de la suposición de que tenemos un reticulado cuaterna \((L,\mathsf{s},\mathsf{i},\leq)\) fijo (pero arbitrario) e intentar (como matemáticos) probar que entonces en \((L,\mathsf{s},\mathsf{i},\leq)\) se cumple \(\varphi\). Una ves que hayamos hecho nuestra prueba como matemáticos, intentar tunearla para que se vuelva una prueba elemental.

  • Es decir debemos ser el mismo matemático de siempre solo que haciendo pruebas de un estilo muy particular.