Sea un conjunto. Por una relacion binaria sobre entenderemos un subconjunto de . Algunos ejemplos:
(E1) Sea . Entonces es una relacion binaria sobre .
(E2) Sea divide a . Entonces es una relacion binaria sobre .
(E3) Sea . Entonces es una relacion binaria sobre
(E4) es una relacion binaria sobre , cualesquiera sea el conjunto .
(E5) Sea o . Entonces es una relacion binaria sobre
Notese que si es una relacion binaria sobre y entonces es una relacion binaria sobre . Por ejemplo las relaciones dadas en los ejemplos (E1), (E2), (E4) y (E5) tambien son relaciones binarias sobre . Sin envargo si es una relacion binaria sobre y entonces no necesariamente sera una relacion binaria sobre (por que?).
Como es usual, cuando sea una relacion binaria sobre un conjunto , algunas veces escribiremos en lugar de .
Hay algunas propiedades que pueden tener o no las relaciones binarias sobre un conjunto , las cuales son muy importantes en matematica. Algunas de estas son:
Reflexividad , cualesquiera sea
Transitividad y implica , cualesquiera sean
Simetria implica , cualesquiera sean
Antisimetria y implica , cualesquiera sean
Cuando cumpla la primer propiedad diremos que es reflexiva, con respecto a . Analogamente diremos que es transitiva, simetrica o antisimetrica, con respecto a , cuando se den, respectivamente las otras propiedades. Notese que estas propiedades dependen del conjunto , por ejemplo si tomamos entonces es una relacion binaria sobre y tambien es una relacion binaria sobre , pero es relexiva con respecto a y no lo es con respecto a ya que no pertenece a . Sin envargo es transitiva con respecto a y tambien lo es con respecto a .
Una relacion binaria sobre un conjunto sera llamada un orden parcial sobre si es reflexiva, transitiva y antisimetrica respecto de . Algunos ejemplos:
(E1) Sea . Entonces es un orden parcial sobre , llamado el orden usual de
(E2) Sea . Entonces es un orden parcial sobre
(E3) Sea . Entonces es un orden parcial sobre
(E4) Sea . Entonces es un orden parcial sobre .
(E5) Sea . Entonces es un orden parcial sobre .
(E6) es un orden parcial sobre , cualesquira sea el conjunto
(E7) Sea . Es facil ver que es un orden parcial sobre
Notese que las relaciones dadas en (E1) y (E4) son distintas, ademas la relacion dada en (E4) no es un orden parcial sobre (por que?).
Muchas veces denotaremos con a una relacion binaria que sea un orden parcial. Esto hace mas intuitiva nuestra escritura pero siempre hay que tener en cuenta que en estos casos esta denotando cierto conjunto de pares ordenados previamente definido.
Usaremos la siguiente
Convencion notacional 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 )
Algunos ejemplos:
(E1) Si y , entonces
(E2) Si y , entonces y . En particular tenemos que , pero no se da que .
(E3) Si y , entonces y sii hay un tal que
Sea un conjunto cualquiera. Por un orden total sobre entenderemos un orden parcial sobre el cual cumpla:
(C) o , cualesquiera sean
Supongamos es finito no vacio y es un orden total sobre . La propiedad (C) nos permite probar que para cada conjunto no vacio , hay un elemento el cual cumple para cada . Por supuesto, es unico (por que?) y habitualmente es llamado el menor elemento de , ya que es menor que todo otro elemento de .
Si es finito no vacio y es un orden total sobre , podemos definir recursivamente una funcion de la siguiente manera:
- menor elemento de
- Si , entonces
- menor elemento de
Como es habitual, es llamado el -esimo elemento de .
Muchas veces para dar un orden total sobre un conjunto finito , daremos simplemente sus elementos en forma creciente ya que esto determina el orden por completo. Por ejemplo si , el orden total dado por es la relacion .
Un concepto importante relativo a los ordenes totales es el de sucesor. Si es un orden total sobre y , diremos que es el sucesor de cuando se de que y , para cada tal que , i.e., es el menor elemento del conjunto tal que . No siempre existe el sucesor de un elemento. Por ejemplo si es el orden usual de , entonces ningun elemento tiene sucesor (justifique).
Dado un orden parcial sobre un conjunto finito podemos realizar un diagrama de , 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 de su diagrama, a saber, sucedera si y solo si o hay una sucesion de segmentos ascendentes desde hasta .
Ejemplos:
Sea un conjunto cualquiera. Por una relacion de equivalencia sobre entenderemos una relacion binaria sobre la cual es reflexiva, transitiva y simetrica, con respecto a , es decir, la cual cumple:
Reflexividad , cualesquiera sea
Transitividad y implica , cualesquiera sean
Simetria implica , cualesquiera sean
Algunos ejemplos:
(E1) Sea . Entonces es una relacion de equivalencia sobre
(E2) Dada una funcion , el nucleo de , i.e. es una relacion de equivalencia sobre .
(E3) Sea . Entonces es una relacion de equivalencia sobre
(E4) Sea . Entonces es una relacion de equivalencia sobre
(E5) Sea es finito. Entonces es una relacion de equivalencia sobre
(E7) Sea . Entonces es una relacion de equivalencia sobre .
(E8) Sea es multiplo de . Entonces es una relacion de equivalencia sobre .
Dada una relacion de equivalencia sobre y , definimos: El conjunto sera llamado la clase de equivalencia de , con respecto a . Ejemplos:
(E1) Si , entonces , cualesquier sea
(E2) Si , entonces y
(E3) Si es multiplo de , entonces es par, es impar y en general notese que es par si es par y es impar si es impar. Es decir que hay solo dos clases de equivalencia con respecto a
Algunas propiedades basicas son:
1.4. Sea una relacion de equivalencia sobre . Sean .
(1)
(2) si y solo si . Es decir que implica
(3) o
Proof. (1) es muy facil.
(2) Supongamos . Veremos que . Supongamos . Entonces . Como , tenemos que , por lo cual hemos probado que y , lo cual implica que . O sea que , lo cual nos dice que . Esto prueba que . Similarmente se prueba que , con lo cual se tiene que .
Reciprocamente, si , entonces ya que . Pero esto nos dice que .
(3) Supongamos que no es vacio, es decir hay un . Entonces es facil ver que . Pero entonces por (2) tenemos que .
Denotaremos con al conjunto . Llamaremos a el cociente de por . Ejemplos:
(E1) Si , entonces
(E2) Si , entonces
(E3) Si es multiplo de , ya vimos que es par es impar
Si es una relacion de equivalencia sobre , definamos la funcion por , para cada . La funcion es llamada la proyeccion canonica (respecto de ).
1.5. Sea una relacion de equivalencia sobre . Entonces . Es decir que es inyectiva sii
Dado un conjunto por una particion de entenderemos un conjunto tal que:
- Cada elemento de es un subconjunto no vacio de
- Si y , entonces
- , para algun
La ultima condicion dice simplemente que la union de todos los elementos de debe ser . Ejemplos:
(E1) Si , entonces
es una particion de
(E2) es una particion de
(E3) es una particion de
Una observacion importante es que si es una particion de , entonces para cada hay un unico tal que (por que?). O sea que podemos hablar de EL elemento de que contiene a .
Dada una particion de un conjunto podemos definir una relacion binaria asociada a de la siguiente manera:
1.6. Sea un conjunto cualquiera. Entonces:
(1) Sea una particion de . Entonces es una relacion de equivalencia sobre .
(2) Sea una relacion de equivalencia sobre . Entonces es una particion de .
Proof. (1). Es facil ver que es reflexiva y simetrica. Veamos que es transitiva. Supongamos que y . O sea que hay tales que y . Ya que y tienen un elemento en comun, debera suceder que . Pero entonces tenemos que , lo cual nos dice que .
(2). Sigue facilmente del Lema 1.4.
El siguiente teorema da una correspondencia natural entre relaciones de equivalencia sobre y particiones de .
1.1. Sea un conjunto cualquiera. Sean Entonces las funciones: son biyecciones una inversa de la otra.
Proof. Notese que por el Lema 1.3 basta con probar:
(1) , cualesquiera sea la particion de
(2) , cualesquiera sea la relacion de equivalencia sobre
Prueba de (1). Primero veamos que . Sea , veremos que . Sea el unico elemento de que contiene a . Es facil ver de la definicion de que por lo cual . Veamos ahora que . Sea . Sea . Es facil ver de la definicion de que por lo cual .
Prueba de (2). Primero veamos que . Supongamos . Entonces , para algun . Es claro que entonces . Veamos ahora que . Supongamos que . Entonces , lo cual nos dice que .
El teorema anterior muestra que a nivel de informacion es lo mismo tener una relacion de equivalencia sobre que tener una particion de . Esto es muy util ya que muchas veces es mas facil especificar una relacion de equivalencia via su particion asociada. Por ejemplo si hablamos de la relacion de equivalencia sobre dada por la particion nos estaremos refiriendo a , es decir a la relacion:
Supongamos es una relacion de equivalencia sobre y supongamos definimos una funcion de la siguiente manera: A priori puede pareser que esta definicion es natural y que no esconde ninguna posible complicacion. Pero veamos que pueden surgir problemas dependiendo de como es . Supongamos que es tal que . Entonces tendriamos que , lo cual nos diria obviamente que . Pero y , por lo cual deberia suceder que sea igual a . El problema aqui es que la ecuacion no esta definiendo en forma correcta o inhambigua una funcion ya que el supuesto valor de la funcion en una clase de equivalencia dada depende de que representante de la clase usamos para denotarla. Si usamos el 2 la ecuacion nos dice que entonces debe valer 4 y si usamos el 6 la ecuacion nos dice que debe valer 36. Claramente no estamos definiendo una funcion.
Para dar un ejemplo mas concreto de este fenomeno de ambiguedad, supongamos y definimos una funcion de la siguiente manera: Como ya vimos es par es impar, por lo cual facilmente se puede llegar a que la ecuacion no define correctamente una funcion. Por ejemplo, si llamamos a la clase es par tenemos que la ecuacion nos diria que y que tambien .
Sin envargo hay muchos casos en los cuales este tipo de definiciones son inhambiguas y desde luego muy importantes en el algebra moderna. Como un primer ejemplo tenemos el siguiente lema el cual es una de las ideas fundamentales del algebra moderna.
1.7. Si , entonces la ecuacion define en forma inhambigua una funcion la cual es inyectiva. Si es suryectiva, entonces lo es y por lo tanto es una biyeccion.
Proof. Que la ecuacion define sin ambiguedad una funcion es obvio ya que si , entonces por definicion de debera suceder que . Dejamos al lector la prueba de que es inyectiva. Es obvio que y tienen la misma imagen por lo cual si es suryectiva, lo sera.