Recordamos que tal como se lo definio en la Seccion [definicion=000020de=000020orden=000020parcial], una relacion binaria sobre un conjunto es llamada un orden parcial sobre si se cumplen las siguientes condiciones:
(1) es reflexiva, i. e. para todo ,
(2) es antisimetrica, i. e. para todo , si y , entonces
(3) es transitiva, i. e. para todo , si y , entonces .
(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 donde es un conjunto no vacio cualquiera y es un orden parcial sobre . Dado un poset , el conjunto sera llamado el universo de . Algunos ejemplos:
(E1) es un poset, donde es el orden usual de los numeros relales
(E2) es un poset
(E3) es un poset, donde
(E4) es un poset
(E5) es un poset, donde
(E6) es un poset, cualesquiera sea el conjunto no vacio
Usaremos la siguiente
Convencion notacional 1 Si hemos denotado con a cierto orden parcial sobre un conjunto , entonces
Denotaremos con a la relacion binaria y . Es decir que y . Cuando se de diremos que es menor que o que es mayor que (respecto de )
Denotaremos con a la relacion binaria Cuando se de diremos que es cubierto por o que cubre a (respecto de ).
El mismo tipo de convencion notacional se hara cuando denotemos con (o , etc) a un orden parcial sobre . Es decir tendremos dos relaciones binarias nuevas tacitamente definidas, a saber:
Dado un poset , con un conjunto finito, podemos realizar un diagrama llamado diagrama de Hasse, siguiendo las siguientes instrucciones:
(1) Asociar en forma inyectiva, a cada un punto del plano
(2) Trazar un segmento de recta uniendo los puntos y , cada vez que
(3) Realizar lo indicado en los puntos (1) y (2) en tal forma que
(i) Si , entonces esta por debajo de
(ii) Si un punto 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, sucedera si y solo si o hay una sucesion de segmentos ascendentes desde hasta .
Algunos ejemplos:
Sea un poset. Diremos que es un elemento maximal de si no existe un tal que . Diremos que es un elemento maximo de si , para todo . En forma analoga se definen los conceptos de elemento minimal y minimo. Algunos ejemplos:
(E1) Sea el orden usual de los numeros reales. El poset no tiene elemento maximo ni minimo. Tampoco tiene elementos maximales ni minimales.
(E2) El poset no tiene elemento maximo. es un elemento minimo de . El unico elemento minimal de es . Los elementos y son los unicos maximales de .
(E3) es un elemento maximo de del poset . Tambien es un elemento minimo de .
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 y , respectivamente. Tambien diremos que tiene un (resp. ) para expresar que tiene un elemento maximo (resp. minimo). Notese tambien que todo elemento maximo (resp. minimo) de es un elemento maximal (resp. minimal) de (por que?).
Sea un poset. Dado , diremos que un elemento es cota superior de en cuando , para todo . Notese que todo elemento de es cota superior de en . Un elemento sera llamado supremo de en cuando se den las siguientes dos propiedades
(1) es a cota superior de en
(2) Para cada , si es una cota superior de en , entonces .
Algunos ejemplos:
(E1) Consideremos el poset , donde es el orden usual de los numeros reales. Notese que ningun elemento de es cota superior de en . O sea que ningun elemento de es supremo de en . Sea Es facil ver que es supremo de en .
(E2) Consideremos el poset , donde . Sean . Es facil ver que es supremo de en .
Como lo muestra el ejemplo (E1) no siempre existe un supremo de en . Ademas notese que en caso de existir es unico, es decir, si es supremo de en y es supremo de en , entonces (por que?). Esto nos permite hablar de EL supremo de en , cuando exista. Denotaremos con al supremo de en , en caso de que exista. A veces para hacer mas dinamicos los enunciados en lugar de escribir es supremo de en escribiremos o .
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 es un elemento minimo de . Esto es porque todo elemento de es cota superior de en .
Daremos otro ejemplo muy importante pero antes un poco de matematica basica. Recordemos que dados decimos que es multiplo de cuando divide a . Ademas, por definicion, el minimo comun multiplo de e es el menor elemento del conjunto es multiplo de y de . El minimo comun multiplo de e se denota con . Una propiedad importante es la siguiente:
(*) Si es multiplo de y de , entonces , es decir no solo es menor o igual a cada multiplo comun de e , sino que divide a cada multiplo comun de e
Un ejemplo importante de existencia de supremos es el siguiente:
(E3) Consideremos el poset , donde . Dados , se tiene que es el supremo de en . Es claro que es cota superior de en . 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 (*)?
Sea un poset. Dado , diremos que un elemento es cota inferior de en , cuando , para cada . Notese que todo elemento de es cota inferior de en . Un elemento sera llamado infimo de en cuando se den las siguientes dos propiedades
(1) es a cota inferior de en
(2) Para cada , si es una cota inferior de en , entonces .
Algunos ejemplos:
(E1) Consideremos el poset , donde es el orden usual de los numeros reales. Notese que ningun elemento de es cota inferior de en . O sea que ningun elemento de es infimo de en . Sea Es facil ver que es infimo de en . Notar que .
(E2) Consideremos el poset , donde . Sean . Es facil ver que es infimo de en .
Como lo muestra el ejemplo (E1) no siempre existe un infimo de en . Ademas notese que en caso de existir es unico, es decir, si es infimo de en y es infimo de en , entonces (por que?). Esto nos permite hablar de EL infimo de en , cuando exista. Denotaremos con al infimo de en , en caso de que exista. A veces para hacer mas dinamicos los enunciados en lugar de escribir es infimo de en escribiremos o .
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 es un elemento maximo de .
Daremos otro ejemplo muy importante pero antes un poco de matematica basica. Recordemos que dados , por definicion, el maximo comun divisor de e es el mayor elemento del conjunto y . El maximo comun divisor de e se denota con . Una propiedad importante es la siguiente:
(**) Si y , entonces , es decir no solo es mayor o igual a cada divisor comun de e , sino que es divisible por cada divisor comun de e
Un ejemplo importante de existencia de infimos es el siguiente:
(E3) Consideremos el poset , donde . Dados , se tiene que es el infimo de en . Es claro que es cota inferior de en . 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 (**)?
Sean y posets. Una funcion sera llamada un homomorfismo de en si para todo se cumple que implica . Escribiremos para expresar que es un homomorfismo de en . Algunos ejemplos:
(E1) dada por es un homomorfismo de en
(E2) Sea y sea un poset cualquiera. Entonces cualquier funcion es un homomorfismo de en (glup!)
(E3) Consideremos el poset , donde y el poset , donde . Entonces dada por es un homomorfismo de en
Una funcion sera llamada un isomorfismo de en si es biyectiva, es un homomorfismo de en y es un homomorfismo de en . Escribiremos cuando exista un isomorfismo de en y en tal caso diremos que y son isomorfos. Cabe observar que un homomorfismo biyectivo no necesariamente es un isomorfismo como lo muestra el siguiente ejemplo.
- Consideremos los posets y . Es facil ver que , dada por y es un homomorfismo de en . Dejamos al lector chequear que no es un homomorfismo de en .
Notacion: Dada una funcion y , denotaremos con al conjunto
El siguiente lema aporta evidencia al hecho de que los isomorfismos preservan todas las propiedades matematicas.
5.1. Sean y posets. Supongamos es un isomorfismo de en .
(a) Para , tenemos que si y solo si .
(b) Para cada , se tiene que es maximo (resp. minimo) de si y solo si es maximo (resp. minimo) de .
(c) Para cada , se tiene que es maximal (resp. minimal) en si y solo si es maximal (resp. minimal) en .
(d) Para , tenemos que si y solo si .
(e) Para cada y cada , se tiene que es cota superior (resp. inferior) de si y solo si es cota superior (resp. inferior) de .
(f) Para cada , se tiene que existe si y solo si existe y en el caso de que existan tales elementos se tiene que .
(g) Para , tenemos que si y solo si
(h) Para , tenemos que si y solo si
Proof. (b) Sea un elemento fijo. Supongamos es maximo de . Probaremos que es maximo de . Sea un elemento fijo pero arbitrario de . Probaremos que . Sea tal que (tal existe ya que es suryectiva). Ya que es maximo de tenemos que . Ya que es un homomorfismo tenemos que por lo cual ya que . Ya que era arbitrario hemos probado que para cada , lo cual por definicion nos dice que es maximo de .
Supongamos ahora que es maximo de . Probaremos que es maximo de . Sea un elemento fijo pero arbitrario de . Probaremos que . Ya que es maximo de tenemos que . Ya que es un homomorfismo tenemos que , por lo cual . Ya que era arbitrario hemos probado que para cada , lo cual por definicion nos dice que es maximo de .
Ya que era fijo pero arbitrario hemos probado que cualquiera sea , se tiene que es maximo de si y solo si es maximo de .
(e) Supongamos que es cota superior de . Veamos que entonces es cota superior de . Sea . Sea tal que . Ya que , tenemos que . Supongamos ahora que es cota superior de y veamos que entonces es cota superior de . Sea . Ya que , tenemos que .
(f) Supongamos existe . Veamos entonces que es el supremo de . Por (e) es cota superior de . Supongamos es cota superior de . Entonces es cota superior de , por lo cual , produciendo . En forma analoga se ve que si existe , entonces es el supremo de .
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:
- Si es una funcion y , entonces , para algun
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 esta en la imagen de una funcion , entonces escriba al elemento en la forma , donde denota algun elemento fijo del dominio de tal que .
Muchas veces tener presente dicha regla es la diferencia a que a uno le salga o no una prueba determinada.