2 Relaciones
Definición 2.1 (Relacion binaria de dos conjuntos).
Sean y dos conjuntos no vacios. Una relacion binaria entre y es un subconjunto .
Definición 2.2 (Relacion binaria en un conjunto).
Sea un conjunto no vacio. Una relacion binaria en es ub subconjunto .
Sea una relacion entre dos conjuntos y . Si decimos que a esta relacionado con b por y escribimos:
Ejemplo.
.
Una relacion es o . El producto cartesiano o tambien son relaciones.
Observación.
Como tiene elementos, puedo encontrar relaciones distintas (porque tiene 64 subconjuntos distintos).
Definición 2.3 (Dominio, imagen).
Sea una relacion binaria entre dos conjuntos y . Se definen
-
Dominio de como
-
Imagen o rango de como
Definición 2.4.
Sea una relacion binaria entre dos conjuntos y . Sean y . Se definen:
-
Imagen inversa de por como
-
Imagen o imagen directa de por como
Observación.
Ejemplo.
Sean , , , .
-
-
- Funcion.
En total habia relaciones entre y .
Ejemplo.
Sean , .
-
-
-
-
-
-
Definición 2.5.
Sean y dos enunciados. La notacion
se lee “ implica ”.
El unico caso en el que es falsa es cuando sucede y no sucede . Esta situacion supone un contraejemplo a la implicacion.
La notacion
se lee “ si y solo si ” o “ es equivalente a ” y quiere decir que y simultaneamente. Es falsa si sucede una de las dos afirmaciones y no la otra.
Definición 2.6.
Sean un conjunto no vacio y una relacion binaria en . Decimos que cumple la propiedad
-
Reflexiva si
-
Simetrica si
-
Antisimetrica si
También se puede formular: -
Transitiva si
Definición 2.7.
Sean un conjunto no vacio y una relacion binaria en . Decimos que es una relacion de
-
Equivalencia si cumple las propiedades reflexiva, simetrica y transitiva.
-
Orden si cumple las propiedades reflexiva, antisimetrica y transitiva.
-
Orden total si es de orden y ademas
Ejemplo.
Sea . Para cada una de las siguientes relaciones en , estudia si cumplen las propiedades reflexiva, simetrica, antisimetrica y transitiva. Tambien si son de equivalencia, orden y orden total.
-
-
-
-
-
-
-
-
-
-
Solucion:
-
No es reflexiva porque (contraejemplo). Por tanto no es de equivalencia ni de orden y, por tanto, no es de orden total.
Tampoco es simetrica porque pero . es antisimetrica porque se cumple la definicion. Por ultimo, no es transitiva porque y pero .
-
no es reflexiva (contraejemplo: ). Luego no es de equivalencia, orden ni orden total.
No es simetrica porque pero . Tampoco es antisimetrica porque . Por ultimo, no es simetrica porque y pero .
-
.
No es reflexiva. Contraejemplo: . No es simetrica porque pero . No es antisimetrica porque y y . No es transitiva porque y pero .
-
.
Es reflexiva porque se cumple la definicion (todos los elementos de estan relacionados consigo mismos). Es simetrica (se cumple la definicion). No es antisimetrica: y . Es transitiva.
Es una relacion de equivalencia.
-
.
No es reflexiva, . Es simetrica porque se cumple la definicion (no hay ningun contraejemplo). Tambien es antisimetrica y transitiva por la misma razon.
-
.
Es reflexiva ya que todos los elementos estan relacionados consigo mismos. Es simetrica y antisimetrica (). Tambien es transitiva, ya que no hay ningun contraejemplo ( solo puede pasar si ).
es una relacion de equivalencia y de orden. No es de orden total porque y .
-
.
Es reflexiva porque estan los pares de (es decir, ). Es simetrica porque en los pares que he añadido no he metido contraejemplos. No es antisimetrica; un contraejemplo es . Es transitiva pues no se pueden encontrar contraejemplos.
es de equivalencia. No es de orden y, por tanto, tampoco de orden total.
-
No es reflexiva. No es simetrica ( y ). Es antisimetrica porque no hay contraejemplos. Es transitiva.
Vamos a ver que es antisimetrica y transitiva solo con la definicion. Supongamos que es el alfabeto español. y es la misma relacion.
Si va antes que , va antes que , entonces va antes que . Luego si es transitiva.
Si va antes que () entonces no va antes que , luego . Entonces es antisimetrica.
-
.
Es reflexiva porque estan todos los pares de . No es simetrica porque pero .
Es antisimetrica: vamos a usar la definicion . va antes o es igual que y va antes o es igual que . La unica opcion es . Por tanto es antisimetrica.
Si va antes o es igual a y va antes o es igual a entonces va antes o es igual a . Luego si es transitiva.
es de orden. Tambien es de orden total porque todos los elementos estan relacionados.
-
Es reflexiva porque estan todos los pares de . No es simetrica porque pero . Es antisimetrica. Es transitiva porque no se han añadido contraejemplos.
es una relacion de orden. No es total ().
Ejemplo.
Dados , .
Tambien se puede definir .
Esta relacion es reflexiva: es del mismo color que . Tambien es simetrica: si (x es del mismo color que y), entonces (y es del mismo color que x). Por ultimo, es transitiva: si es del mismo color que , es del mismo color que , entonces es del mismo color que
Luego es de equivalencia. Una relacion de equivalencia genera una particion. A los elementos de la particion se les llama “clases de equivalencia”. En este caso, hay 3 clases de equivalencia: la de los bolis rojos, la de los bolis negros y la de los bolis azules:
, y son representantes de clase (elegidos de forma arbitraria).
El conjunto cociente va a ser el conjunto formado por las clases de equivalencia .
Definición 2.8 (Clase de equivalencia).
Sea una relacion de equivalencia en un conjunto y sea . Llamamos clase de equivalencia de por la relacion al conjunto de todos los elementos de que estan relacionados con . Simbolicamente:
Si, por contexto, esta claro que solo podemos estar hablando de clases respecto de la relacion , omitiremos el subindice y escribiremos . Tambien se puede escribir .
Definición 2.9 (Conjunto cociente).
Sea una relacion de equivalencia en un conjunto . Llamamos conjunto cociente de bajo la relacion al conjunto formado por todas las clases de equivalencia de la relacion. Simbolicamente:
Ejemplo.
.
.
.
.
Hay una unica clase de equivalencia. El cociente es .
Otra relacion de equivalencia es .
En este caso, . El conjunto cociente esta formado por 4 elementos:
. En este caso, hay 2 clases:
y .
El conjunto cociente es .
Otro ejemplo es , siendo la relacion de igualdad. Se puede demostrar que es una relacion de equivalencia.
Las clases de equivalencia son y . El conjunto cociente es .
Proposición 2.1.
Sean una relacion de equivalencia en un conjunto y . Se cumple:
-
.
-
.
Demostración.
Sean .
-
Si :
Tenemos que demostrar que . Para ello, vamos a ver un doble contenido de conjuntos.
Vamos a ver que .
y .
Sea . Como y es simetrica (por ser una relacion de equivalencia), tenemos que . Como y , por ser transitiva, tengo que .
Sea .
Como y es transitiva, .
-
Si :
Tenemos que demostrar que . Por reduccion al absurdo, supongamos que .
Sin embargo, y . Como y es transitiva entonces . Hemos llegado a una contradiccion porque partimos de que .
Por tanto, .
∎
Definición 2.10 (Conjuntos disjuntos).
Sean y dos conjuntos. Decimos que son disjuntos si .
Definición 2.11 (Partición).
Sea un conjunto. Decimos que una coleccion de subconjuntos de constituye una particion de si se cumplen las dos condiciones siguientes:
-
Son disjuntos dos a dos: dos conjuntos diferentes cualesquiera de la coleccion son disjuntos.
-
Recubren : la union de todos ellos es .
Teorema 2.1.
Sea una relacion de equivalencia en un conjunto . Entonces las clases de equivalencia de constituyen una particion de .
Demostración.
En la proposicion 3 hemos demostrado que las clases de equivalencia son disjuntas dos a dos.
Veamos que las clases recubren .
Dado se cumple que por ser reflexiva que .
Luego todo elemento pertenece a una clase de equivalencia. ∎
Ejemplo.
.
Una particion es: .
Defino como: .
Entonces . Dentro de cada conjunto de la particion he relacionado sus elementos de todas las formas posibles.
Teorema 2.2.
Supongamos que tenemos una particion de un conjunto . Definimos una relacion en de la siguiente forma:
Entonces la relacion es de equivalencia.
Ademas, las clases de equivalencia de coinciden con los subconjuntos de la particion.
Demostración.
Vamos a demostrar que es de equivalencia.
-
es reflexiva?
Dado , como la particion recubre existe un conjunto de la particion al que pertenece. Luego y estan en el mismo conjunto de la particion .
-
es simetrica?
y estan en el mismo conjunto de la particion .
Por tanto, es simetrica.
-
es transitiva?
y estan en el mismo conjunto de la particion y y c estan en el mismo conjunto de la particion. Por lo tanto, y estan en el mismo conjunto y .
Las clases de son los conjuntos de la particion por construccion.
Luego es el conjunto de la particion al que pertenece. ∎
Ejemplo.
Cuantas relaciones de equivalencia se pueden definir sobre un conjunto de 4 elementos?
Demostración.
Es lo mismo que contar cuantas particiones diferentes se pueden hacer de un conjunto de 4 elementos. Cuento por numero de “trozos”.
-
Con un subconjunto. Solo hay una particion que es tomar todo el conjunto.
-
Con 2 trozos. En total, hay 7 trozos (3 con 2 trozos iguales, 4 con un trozo de 1 elemento y otro de 3).
-
Con 3 trozos. Los trozos deben ser 2 de 1 elemento y otro de 2. Hay 6 distintas.
-
Con 4 trozos hay una unica forma.
Hay relaciones de equivalencia distintas en . Ver: Numeros de Bell. ∎
Ejemplo.
Dos relaciones de equivalencia importantes:
-
Construccion de los racionales.
-
Enteros modulo 2.
Demostración.
-
Los numeros racionales como cociente.
Si defino los racionales como :
En el conjunto de fracciones vamos a definir una relacion tal que
Vamos a demostrar que es de equivalencia.
-
•
reflexiva: se cumple
-
•
Simetrica:
-
•
Transitiva:
,
Debemos llegar a que
Como d es un denominador, implica que y puedo dividir ambos enteros entre .
Luego la relacion es de equivalencia. Como son las clases?
Por ejemplo:
.
Quien es ?
Luego en este cociente .
Obs: .
-
•
-
Enteros modulo 2.
. Dados , es par. Es decir, tal que () ( congruente con modulo 2).
Veamos si esta relacion es de equivalencia:
-
•
Reflexiva:
Si porque
-
•
Simetrica:
Si tal que .
-
•
Transitiva:
.
Sumando . Por tanto .
Hemos visto que la congruencia modulo 2 es una relacion de equivalencia.
Ejemplos de enteros relacionados: , , .
Clases de equivalencia:
Luego hay 2 clases y .
-
•
∎
Definición 2.12 (Orden parcial).
Decimos que una relacion es de orden parcial si es de orden pero no es de orden total.
Ejemplo.
-
Relacion “menor o igual” en (orden total).
-
Relacion “contenido o igual” en siendo un conjunto (orden parcial si , orden total si o ).
Definición 2.13.
Sean y conjuntos no vacios. Una relacion -aria entre es un subconjunto .