5.1 Conjuntos parcialmente ordenados

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

  1. (1) es reflexiva, i. e. para todo aP, aa

  2. (2) es antisimetrica, i. e. para todo a,bP, si ab y ba, entonces a=b.

  3. (3) es transitiva, i. e. para todo a,b,cP, si ab y bc, entonces ac.

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

Un conjunto parcialmente ordenado o poset es un par (P,) donde P es un conjunto no vacio cualquiera y es un orden parcial sobre P. Dado un poset (P,), el conjunto P sera llamado el universo de (P,). Algunos ejemplos:

  1. (E1) (R,) es un poset, donde es el orden usual de los numeros relales

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

  3. (E3) (P(ω),) es un poset, donde ={(S,T)P(ω)2:ST}

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

  5. (E5) (N,) es un poset, donde ={(n,m)N2:nm}

  6. (E6) (A,{(a,b):a=b}) es un poset, cualesquiera sea el conjunto no vacio A

Usaremos la siguiente

  1. Convencion notacional 1 Si hemos denotado con a cierto orden parcial sobre un conjunto A, entonces

    1. Denotaremos con < a la relacion binaria {(a,b)A2:ab y ab}. Es decir que <={(a,b)A2:ab y ab}. Cuando se de a<b diremos que a es menor que b o que b es mayor que a (respecto de )

    2. Denotaremos con a la relacion binaria {(a,b)A2:a<b y no existe z tal que a<z<b} Cuando se de ab diremos que a es cubierto por b o que b cubre a a (respecto de ).

El mismo tipo de convencion notacional se hara cuando denotemos con (o ~, etc) a un orden parcial sobre A. Es decir tendremos dos relaciones binarias nuevas tacitamente definidas, a saber: <={(a,b)A2:ab y ab}={(a,b)A2:a<b yno existe z tal que a<z<b}

5.1.1 Diagramas de Hasse

Dado un poset (P,), con P un conjunto finito, podemos realizar un diagrama llamado diagrama de Hasse, siguiendo las siguientes instrucciones:

  1. (1) Asociar en forma inyectiva, a cada a P un punto pa del plano

  2. (2) Trazar un segmento de recta uniendo los puntos pa y pb, cada vez que ab

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

    1. (i) Si ab, entonces pa esta por debajo de pb

    2. (ii) Si un punto pa ocurre en un segmento del diagrama entonces lo hace en alguno de sus extremos.

La relacion de orden puede ser facilmente obtenida a partir del diagrama, a saber, ab sucedera si y solo si pa=pb o hay una sucesion de segmentos ascendentes desde pa hasta pb.

Algunos ejemplos:

5.1.2 Elementos maximales, maximos, minimales y minimos

Sea (P,) un poset. Diremos que aP es un elemento maximal de (P,) si no existe un bP tal que a<b. Diremos que aP es un elemento maximo de (P,) si ba, para todo bP. En forma analoga se definen los conceptos de elemento minimal y minimo. Algunos ejemplos:

  1. (E1) Sea el orden usual de los numeros reales. El poset (R,) no tiene elemento maximo ni minimo. Tampoco tiene elementos maximales ni minimales.

  2. (E2) El poset P=({1,2,3},{(1,2),(1,3),(1,1),(2,2),(3,3)}) no tiene elemento maximo. 1 es un elemento minimo de P. El unico elemento minimal de P es 1. Los elementos 2 y 3 son los unicos maximales de P.

  3. (E3) 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,) tiene un 1 (resp. 0) para expresar que (P,) tiene un elemento maximo (resp. minimo). Notese tambien que todo elemento maximo (resp. minimo) de (P,) es un elemento maximal (resp. minimal) de (P,) (por que?).

5.1.3 Supremos

Sea (P,) un poset. Dado SP, diremos que un elemento aP es cota superior de S en (P,) cuando ba, para todo bS. Notese que todo elemento de P es cota superior de en (P,). Un elemento aP sera llamado supremo de S en (P,) cuando se den las siguientes dos propiedades

  1. (1) a es a cota superior de S en (P,)

  2. (2) Para cada bP, si b es una cota superior de S en (P,), entonces ab.

Algunos ejemplos:

  1. (E1) Consideremos el poset (R,), donde es el orden usual de los numeros reales. Notese que ningun elemento de R es cota superior de ω en (R,). O sea que ningun elemento de R es supremo de ω en (R,). Sea S={1/n:nN}={1,1/2,1/3,...} Es facil ver que 0 es supremo de S en (R,).

  2. (E2) Consideremos el poset (P(ω),), donde ={(A,B)P(ω)2:AB}. Sean A,BP(ω). Es facil ver que AB es supremo de {A,B} en (P(ω),).

Como lo muestra el ejemplo (E1) no siempre existe un supremo de S en (P,). Ademas notese que en caso de existir es unico, es decir, si a es supremo de S en (P,) y a es supremo de S en (P,), entonces a=a (por que?). Esto nos permite hablar de EL supremo de S en (P,), cuando exista. Denotaremos con sup(S) al supremo de S en (P,), en caso de que exista. A veces para hacer mas dinamicos los enunciados en lugar de escribir z es supremo de S en (P,) 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 en (P,) es un elemento minimo de (P,). Esto es porque todo elemento de P es cota superior de en (P,).

Daremos otro ejemplo muy importante pero antes un poco de matematica basica. Recordemos que dados x,yN 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 {zN: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. (*) 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. (E3) Consideremos el poset (N,D), donde D={(x,y)N2:x|y}. Dados x,yN, se tiene que mcm(x,y) es el supremo de {x,y} en (N,D). Es claro que mcm(x,y) es cota superior de {x,y} en (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,) un poset. Dado SP, diremos que un elemento aP es cota inferior de S en (P,), cuando ab, para cada bS. Notese que todo elemento de P es cota inferior de en (P,). Un elemento aP sera llamado infimo de S en (P,) cuando se den las siguientes dos propiedades

  1. (1) a es a cota inferior de S en (P,)

  2. (2) Para cada bP, si b es una cota inferior de S en (P,), entonces ba.

Algunos ejemplos:

  1. (E1) Consideremos el poset (R,), donde es el orden usual de los numeros reales. Notese que ningun elemento de R es cota inferior de Z en (R,). O sea que ningun elemento de R es infimo de Z en (R,). Sea S={1/n:nN}={1,1/2,1/3,...} Es facil ver que 0 es infimo de S en (R,). Notar que infSS.

  2. (E2) Consideremos el poset (P(ω),), donde ={(A,B)P(ω)2:AB}. Sean A,BP(ω). Es facil ver que AB es infimo de {A,B} en (P(ω),).

Como lo muestra el ejemplo (E1) no siempre existe un infimo de S en (P,). Ademas notese que en caso de existir es unico, es decir, si a es infimo de S en (P,) y a es infimo de S en (P,), entonces a=a (por que?). Esto nos permite hablar de EL infimo de S en (P,), cuando exista. Denotaremos con inf(S) al infimo de S en (P,), en caso de que exista. A veces para hacer mas dinamicos los enunciados en lugar de escribir z es infimo de S en (P,) 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 en (P,) es un elemento maximo de (P,).

Daremos otro ejemplo muy importante pero antes un poco de matematica basica. Recordemos que dados x,yN, por definicion, el maximo comun divisor de x e y es el mayor elemento del conjunto {zN: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. (**) 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. (E3) Consideremos el poset (N,D), donde D={(x,y)N2:x|y}. Dados x,yN, se tiene que mcd(x,y) es el infimo de {x,y} en (N,D). Es claro que mcd(x,y) es cota inferior de {x,y} en (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,) y (P,) posets. Una funcion F:PP sera llamada un homomorfismo de (P,) en (P,) si para todo x,yP se cumple que xy implica F(x)F(y). Escribiremos F:(P,)(P,) para expresar que F es un homomorfismo de (P,) en (P,). Algunos ejemplos:

  1. (E1) F:RR dada por F(r)=3.r es un homomorfismo de (R,) en (R,)

  2. (E2) Sea ={(n,m)ω:n=m} y sea (P,) un poset cualquiera. Entonces cualquier funcion F:ωP es un homomorfismo de (ω,) en (P,) (glup!)

  3. (E3) Consideremos el poset (P(ω),), donde ={(A,B)P(ω)2:AB} y el poset (P({1,2,3,4}),), donde ={(A,B)P({1,2,3,4})2:AB}. Entonces F:P(ω)P(1,2,3,4) dada por F(A)=A{1,2,3,4} es un homomorfismo de (P(ω),) en (P({1,2,3,4}),)

Una funcion F:PP sera llamada un isomorfismo de (P,) en (P,) si F es biyectiva, F es un homomorfismo de (P,) en (P,) y F1 es un homomorfismo de (P,) en (P,). Escribiremos (P,)(P,) cuando exista un isomorfismo de (P,) en (P,) y en tal caso diremos que (P,) y (P,) son isomorfos. Cabe observar que un homomorfismo biyectivo no necesariamente es un isomorfismo como lo muestra el siguiente ejemplo.

  1. - Consideremos los posets P=({1,2},{(1,1),(2,2)}) y Q=({1,2},{(1,1),(2,2),(1,2)}). Es facil ver que F:{1,2}{1,2}, dada por F(1)=1 y F(2)=2 es un homomorfismo de P en Q. Dejamos al lector chequear que F1 no es un homomorfismo de Q en P.

  2. Notacion: Dada una funcion F:AB y SA, denotaremos con F(S) al conjunto {F(a):aS}

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

5.1. Sean (P,) y (P,) posets. Supongamos F es un isomorfismo de (P,) en (P,).

  1. (a) Para x,yP, tenemos que x<y si y solo si F(x)<F(y).

  2. (b) Para cada xP, se tiene que x es maximo (resp. minimo) de (P,) si y solo si F(x) es maximo (resp. minimo) de (P,).

  3. (c) Para cada xP, se tiene que x es maximal (resp. minimal) en (P,) si y solo si F(x) es maximal (resp. minimal) en (P,).

  4. (d) Para x,yP, tenemos que xy si y solo si F(x)F(y).

  5. (e) Para cada SP y cada aP, se tiene que a es cota superior (resp. inferior) de S si y solo si F(a) es cota superior (resp. inferior) de F(S).

  6. (f) Para cada SP, se tiene que existe sup(S) si y solo si existe sup(F(S)) y en el caso de que existan tales elementos se tiene que F(sup(S))=sup(F(S)).

  7. (g) Para x,y,zP, tenemos que z=sup{x,y} si y solo si F(z)=sup{F(x),F(y)}

  8. (h) Para x,y,zP, tenemos que z=inf{x,y} si y solo si F(z)=inf{F(x),F(y)}

Proof. (b) Sea aP un elemento fijo. Supongamos aP es maximo de (P,). Probaremos que F(a) es maximo de (P,). Sea b un elemento fijo pero arbitrario de P. Probaremos que bF(a). Sea dP tal que F(d)=b (tal d existe ya que F es suryectiva). Ya que a es maximo de (P,) tenemos que da. Ya que F es un homomorfismo tenemos que F(d)F(a) por lo cual bF(a) ya que F(d)=b. Ya que b era arbitrario hemos probado que xF(a) para cada xP, lo cual por definicion nos dice que F(a) es maximo de (P,).

Supongamos ahora que F(a) es maximo de (P,). Probaremos que a es maximo de (P,). Sea b un elemento fijo pero arbitrario de P. Probaremos que ba. Ya que F(a) es maximo de (P,) tenemos que F(b)F(a). Ya que F1 es un homomorfismo tenemos que F1(F(b))F1(F(a)), por lo cual ba. Ya que b era arbitrario hemos probado que xa para cada xP, lo cual por definicion nos dice que a es maximo de (P,).

Ya que a era fijo pero arbitrario hemos probado que cualquiera sea xP, se tiene que x es maximo de (P,) si y solo si F(x) es maximo de (P,).

(e) Supongamos que a es cota superior de S. Veamos que entonces F(a) es cota superior de F(S). Sea xF(S). Sea sS tal que x=F(s). Ya que sa, tenemos que x=F(s)F(a). Supongamos ahora que F(a) es cota superior de F(S) y veamos que entonces a es cota superior de S. Sea sS. Ya que F(s)F(a), tenemos que s=F1(F(s))F1(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 F1(b) es cota superior de S, por lo cual sup(S)F1(b), produciendo F(sup(S))b. En forma analoga se ve que si existe sup(F(S)), entonces F1(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. - Si F es una funcion y bIm(F), entonces b=F(d), para algun dDF

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 tal que F(a)=b.

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