5.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\}\)

5.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).

5.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\)

5.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\}\)

5.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:

5.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?).

5.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 (*)?

5.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 (**)?

5.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.