5.1 Conjuntos parcialmente ordenados

Recordamos que tal como se lo definio en la Seccion [definicion de orden parcial], una relacion binaria \(\leq\) sobre un conjunto \(P\) es llamada un orden parcial sobre \(P\) si se cumplen las siguientes condiciones:

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

2. adhocprefix(2)adhocsufix \(\leq\) es antisimetrica, i. e. para todo \(a,b\in P\), si \(a\leq b\) y \(b\leq a\), entonces \(a=b.\)

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

(recomendamos antes de leer este tema, leer la Seccion [definicion de orden parcial], para familiarizarse con la notacion y las propiedades basicas de los ordenes parciales).

Un conjunto parcialmente ordenado o poset es un par \((P,\leq)\) donde \(P\) es un conjunto no vacio cualquiera y \(\leq\) es un orden parcial sobre \(P\). Dado un poset \((P,\leq)\), el conjunto \(P\) sera 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 numeros relales

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):a=b\})\) es un poset, cualesquiera sea el conjunto no vacio \(A\)

Usaremos la siguiente

1. adhocprefixConvencion notacional 1adhocsufix Si hemos denotado con \(\leq\) a cierto orden parcial sobre un conjunto \(A\), entonces

   1. Denotaremos con \(<\) a la relacion 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 de \(a<b\) diremos que \(a\) es menor que \(b\) o que \(b\) es mayor que \(a\) (respecto de \(\leq\))

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

El mismo tipo de convencion notacional se hara cuando denotemos con \(\leq^{\prime}\) (o \(\tilde{\leq}\), etc) a un orden parcial sobre \(A\). Es decir tendremos dos relaciones binarias nuevas tacitamente definidas, a saber: \[\begin{aligned} & \mathrm{<}^{\prime}=\{(a,b)\in A^{2}:a\leq^{\prime}b\text{ y }a\neq b\}\\ & \mathrm{\prec}^{\prime}=\{(a,b)\in A^{2}:a<^{\prime}b\text{ y no existe }z\text{ tal que }a<^{\prime}z<^{\prime}b\} \end{aligned}\]

5.1.1 Diagramas de Hasse

Dado un poset \((P,\leq)\), con \(P\) un conjunto finito, podemos realizar un diagrama llamado diagrama de Hasse, 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 relacion de orden \(\leq\) puede ser facilmente obtenida a partir del diagrama, a saber, \(a\leq b\) sucedera si y solo si \(p_{a}=p_{b}\) o hay una sucesion de segmentos ascendentes desde \(p_{a}\) hasta \(p_{b}\).

Algunos ejemplos:

5.1.2 Elementos maximales, maximos, minimales y minimos

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 maximo de \((P,\leq)\) si \(b\leq a\), para todo \(b\in P\). En forma analoga se definen los conceptos de elemento minimal y minimo. Algunos ejemplos:

1. adhocprefix(E1)adhocsufix Sea \(\leq\) el orden usual de los numeros reales. El poset \((\mathbf{R},\leq)\) no tiene elemento maximo ni minimo. 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 maximo. \(1\) es un elemento minimo de \(\mathbf{P}\). El unico elemento minimal de \(\mathbf{P}\) es \(1\). Los elementos \(2\) y \(3\) son los unicos maximales de \(\mathbf{P}\).

3. adhocprefix(E3)adhocsufix \(1\) es un elemento maximo de del poset \((\{1\},\{(1,1)\})\). Tambien \(1\) es un elemento minimo de \((\{1\},\{(1,1)\})\).

Como lo muestra el ejemplo (E3), no siempre hay elementos maximales o maximos en un poset. Ademas un poset tiene a lo sumo un maximo y un minimo (por que?), los cuales en caso de existir algunas veces seran denotados con \(1\) y \(0\), respectivamente. Tambien diremos que \((P,\leq)\) tiene un \(1\) (resp. \(0\)) para expresar que \((P,\leq)\) tiene un elemento maximo (resp. minimo). Notese tambien que todo elemento maximo (resp. minimo) de \((P,\leq)\) es un elemento maximal (resp. minimal) de \((P,\leq)\) (por que?).

5.1.3 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\). Notese que todo elemento de \(P\) es cota superior de \(\emptyset\) en \((P,\leq)\). Un elemento \(a\in P\) sera 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 Consideremos el poset \((\mathbf{R},\leq)\), donde \(\leq\) es el orden usual de los numeros reales. Notese que ningun elemento de \(\mathbf{R}\) es cota superior de \(\omega\) en \((\mathbf{R},\leq)\). O sea que ningun elemento de \(\mathbf{R}\) es supremo de \(\omega\) en \((\mathbf{R},\leq)\). Sea \[\begin{aligned} S & =\{-1/n:n\in\mathbf{N}\}\\ & =\{-1,-1/2,-1/3,...\} \end{aligned}\] Es facil ver que \(0\) es supremo de \(S\) en \((\mathbf{R},\leq)\).

2. adhocprefix(E2)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 facil ver que \(A\cup B\) es supremo de \(\{A,B\}\) en \((\mathcal{P}(\omega),\leq)\).

Como lo muestra el ejemplo (E1) no siempre existe un supremo de \(S\) en \((P,\leq)\). Ademas notese que en caso de existir es unico, 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 dinamicos los enunciados en lugar de escribir \(z\) es supremo de \(S\) en \((P,\leq)\) escribiremos \(z=\sup(S)\) o \(\sup(S)=z\).

Notese que (E1) nos muestra que no siempre el supremo de un conjunto pertenece al conjunto. Notese ademas que, en caso de existir, el supremo del conjunto \(\emptyset\) en \((P,\leq)\) es un elemento minimo 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 matematica basica. Recordemos que dados \(x,y\in\mathbf{N}\) decimos que \(x\) es multiplo de \(y\) cuando \(y\) divide a \(x\). Ademas, por definicion, el minimo comun multiplo de \(x\) e \(y\) es el menor elemento del conjunto \(\{z\in\mathbf{N}:z\) es multiplo de \(x\) y de \(y\}\). El minimo comun multiplo de \(x\) e \(y\) se denota con \(mcm(x,y)\). Una propiedad importante es la siguiente:

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

Un ejemplo importante de existencia de supremos es el siguiente:

1. adhocprefix(E3)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)\). Ademas la propiedad (*) nos asegura que la propiedad (2) de la definicion de supremo se cumple. Por que no es obvio que se cumpla (2) de la definicion de supremo? Por que es necesario aplicar la propiedad (*)?

5.1.4 Infimos

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\). Notese que todo elemento de \(P\) es cota inferior de \(\emptyset\) en \((P,\leq)\). Un elemento \(a\in P\) sera llamado infimo 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 Consideremos el poset \((\mathbf{R},\leq)\), donde \(\leq\) es el orden usual de los numeros reales. Notese que ningun elemento de \(\mathbf{R}\) es cota inferior de \(\mathbf{Z}\) en \((\mathbf{R},\leq)\). O sea que ningun elemento de \(\mathbf{R}\) es infimo de \(\mathbf{Z}\) en \((\mathbf{R},\leq)\). Sea \[\begin{aligned} S & =\{1/n:n\in\mathbf{N}\}\\ & =\{1,1/2,1/3,...\} \end{aligned}\] Es facil ver que \(0\) es infimo de \(S\) en \((\mathbf{R},\leq)\). Notar que \(\inf S\notin S\).

2. adhocprefix(E2)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 facil ver que \(A\cap B\) es infimo de \(\{A,B\}\) en \((\mathcal{P}(\omega),\leq)\).

Como lo muestra el ejemplo (E1) no siempre existe un infimo de \(S\) en \((P,\leq)\). Ademas notese que en caso de existir es unico, es decir, si \(a\) es infimo de \(S\) en \((P,\leq)\) y \(a^{\prime}\) es infimo de \(S\) en \((P,\leq)\), entonces \(a=a^{\prime}\) (por que?). Esto nos permite hablar de EL infimo de \(S\) en \((P,\leq)\), cuando exista. Denotaremos con \(\inf(S)\) al infimo de \(S\) en \((P,\leq)\), en caso de que exista. A veces para hacer mas dinamicos los enunciados en lugar de escribir \(z\) es infimo de \(S\) en \((P,\leq)\) escribiremos \(z=\inf(S)\) o \(\inf(S)=z\).

Notese que (E1) nos muestra que no siempre el infimo de un conjunto pertenece al conjunto. Notese ademas que en caso de existir el infimo del conjunto \(\emptyset\) en \((P,\leq)\) es un elemento maximo de \((P,\leq)\).

Daremos otro ejemplo muy importante pero antes un poco de matematica basica. Recordemos que dados \(x,y\in\mathbf{N}\), por definicion, el maximo comun divisor de \(x\) e \(y\) es el mayor elemento del conjunto \(\{z\in\mathbf{N}:z|x\) y \(z|y\}\). El maximo comun 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 comun de \(x\) e \(y\), sino que \(mcd(x,y)\) es divisible por cada divisor comun de \(x\) e \(y\)

Un ejemplo importante de existencia de infimos es el siguiente:

1. adhocprefix(E3)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 infimo de \(\{x,y\}\) en \((\mathbf{N},D)\). Es claro que \(mcd(x,y)\) es cota inferior de \(\{x,y\}\) en \((\mathbf{N},D)\). Ademas la propiedad (**) nos asegura que la propiedad (2) de la definicion de infimo se cumple. Por que no es obvio que se cumpla (2) de la definicion de infimo? Por que es necesario aplicar la propiedad (**)?

5.1.5 Homomorfismos de posets

Sean \((P,\leq)\) y \((P^{\prime},\leq^{\prime})\) posets. Una funcion \(F:P\rightarrow P^{\prime}\) sera 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 funcion \(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 funcion \(F:P\rightarrow P^{\prime}\) sera 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 facil 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}\).

2. adhocprefixNotacion:adhocsufix Dada una funcion \(F:A\rightarrow B\) y \(S\subseteq A\), denotaremos con \(F(S)\) al conjunto \(\{F(a):a\in S\}\)

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

Proof. (b) Sea \(a\in P\) un elemento fijo. Supongamos \(a\in P\) es maximo de \((P,\leq)\). Probaremos que \(F(a)\) es maximo 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 maximo 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 definicion nos dice que \(F(a)\) es maximo de \((P^{\prime},\leq^{\prime})\).

Supongamos ahora que \(F(a)\) es maximo de \((P^{\prime},\leq^{\prime})\). Probaremos que \(a\) es maximo de \((P,\leq)\). Sea \(b\) un elemento fijo pero arbitrario de \(P\). Probaremos que \(b\leq a\). Ya que \(F(a)\) es maximo 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 definicion nos dice que \(a\) es maximo de \((P,\leq)\).

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

(e) 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\).

(f) Supongamos existe \(\sup(S)\). Veamos entonces que \(F(\sup(S))\) es el supremo de \(F(S)\). Por (e) \(F(\sup(S))\) es cota superior de \(F(S)\). Supongamos \(b\) es cota superior de \(F(S)\). Entonces \(F^{-1}(b)\) es cota superior de \(S\), por lo cual \(\sup(S)\leq F^{-1}(b)\), produciendo \(F(\sup(S))\leq^{\prime}b\). En forma analoga se ve que si existe \(\sup(F(S))\), entonces \(F^{-1}(\sup(F(S)))\) es el supremo de \(S\).

Las pruebas faltantes son dejadas como ejercicio.  

Notese que (d) nos garantiza que si dos posets finitos son isomorfos, entonces pueden representarse con el mismo diagrama de Hasse.

En la prueba de (b) del lema anterior se uso tacitamente la siguiente propiedad que es obvia pero clave en la demostracion:

1. adhocprefix-adhocsufix Si \(F\) es una funcion y \(b\in\operatorname{Im}(F)\), entonces \(b=F(d)\), para algun \(d\in D_{F}\)

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

Regla Pertenecer a la Imagen

Si ud en el desarrollo de una prueba conoce que un elemento \(b\) esta en la imagen de una funcion \(F\), entonces escriba al elemento \(b\) en la forma \(F(a)\), donde \(a\) denota algun elemento fijo del dominio de \(F\)

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