1.7 Relaciones binarias

Sea A un conjunto. Por una relacion binaria sobre A entenderemos un subconjunto de A2. Algunos ejemplos:

1. (E1) Sea R={(1,2),(2,3)}. Entonces R es una relacion binaria sobre N.

2. (E2) Sea R={(x,y)∈ω2: x divide a y}. Entonces R es una relacion binaria sobre ω.

3. (E3) Sea R={(r,t)∈R2:r≤t}. Entonces R es una relacion binaria sobre R

4. (E4) ∅ es una relacion binaria sobre A, cualesquiera sea el conjunto A.

5. (E5) Sea R={(x,y)∈ω2:x<y o y=0}. Entonces R es una relacion binaria sobre ω

Notese que si R es una relacion binaria sobre A y A⊆B entonces R es una relacion binaria sobre B. Por ejemplo las relaciones dadas en los ejemplos (E1), (E2), (E4) y (E5) tambien son relaciones binarias sobre R. Sin envargo si R es una relacion binaria sobre B y A⊆B entonces no necesariamente R sera una relacion binaria sobre A (por que?).

Como es usual, cuando R sea una relacion binaria sobre un conjunto A, algunas veces escribiremos aRb en lugar de (a,b)∈R.

1.7.1 Propiedades notables de relaciones binarias

Hay algunas propiedades que pueden tener o no las relaciones binarias sobre un conjunto A, las cuales son muy importantes en matematica. Algunas de estas son:

1. Reflexividad xRx, cualesquiera sea x∈A

2. Transitividad xRy y yRz implica xRz, cualesquiera sean x,y,z∈A

3. Simetria xRy implica yRx, cualesquiera sean x,y∈A

4. Antisimetria xRy y yRx implica x=y, cualesquiera sean x,y∈A

Cuando R cumpla la primer propiedad diremos que R es reflexiva, con respecto a A. Analogamente diremos que R es transitiva, simetrica o antisimetrica, con respecto a A, cuando se den, respectivamente las otras propiedades. Notese que estas propiedades dependen del conjunto A, por ejemplo si tomamos R={(r,t)∈N2:r≤t} entonces R es una relacion binaria sobre N y tambien es una relacion binaria sobre ω, pero es relexiva con respecto a N y no lo es con respecto a ω ya que (0,0) no pertenece a R. Sin envargo R es transitiva con respecto a N y tambien lo es con respecto a ω.

1.7.2 Ordenes parciales

Una relacion binaria R sobre un conjunto A sera llamada un orden parcial sobre A si es reflexiva, transitiva y antisimetrica respecto de A. Algunos ejemplos:

1. (E1) Sea R={(r,t)∈R2:r≤t}. Entonces R es un orden parcial sobre R, llamado el orden usual de R

2. (E2) Sea R={(1,2),(1,3),(1,1),(2,2),(3,3)}. Entonces R es un orden parcial sobre {1,2,3}

3. (E3) Sea R={(S,T)∈P(ω)2:S⊆T}. Entonces R es un orden parcial sobre P(ω)

4. (E4) Sea R={(x,y)∈ω2: x≤y}. Entonces R es un orden parcial sobre ω.

5. (E5) Sea R={(1,1)}. Entonces R es un orden parcial sobre {1}.

6. (E6) {(a,b):a=b} es un orden parcial sobre A, cualesquira sea el conjunto A

7. (E7) Sea ≤={(n,m)∈N2:n∣m}. Es facil ver que ≤ es un orden parcial sobre N

Notese que las relaciones dadas en (E1) y (E4) son distintas, ademas la relacion dada en (E4) no es un orden parcial sobre R (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

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

   1. Denotaremos con < a la relacion binaria {(a,b)∈A2:a≤b y a≠b}. Es decir que <={(a,b)∈A2:a≤b y a≠b}. 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 a≺b diremos que a es cubierto por b o que b cubre a a (respecto de ≤)

Algunos ejemplos:

1. (E1) Si A=R y ≤={(r,t)∈R2:r=t}, entonces <=∅

2. (E2) Si A={1,2,3,4} y ≤={(1,2),(2,3),(1,3),(1,1),(2,2),(3,3),(4,4)}, entonces <={(1,2),(2,3),(1,3)} y ≺={(1,2),(2,3)}. En particular tenemos que 1≺2, 1<3 pero no se da que 1≺3.

3. (E3) Si A=P(ω) y ≤={(S,T)∈P(ω)2:S⊆T}, entonces <={(S,T)∈P(ω)2:S⊊T} y S≺T sii hay un n∈T−S tal que T=S∪{n}

1.7.2.1 Ordenes totales sobre un conjunto

Sea A un conjunto cualquiera. Por un orden total sobre A entenderemos un orden parcial ≤ sobre A el cual cumpla:

1. (C) a≤b o b≤a, cualesquiera sean a,b∈A

Supongamos A es finito no vacio y ≤ es un orden total sobre A. La propiedad (C) nos permite probar que para cada conjunto no vacio S⊆A, hay un elemento s∈S el cual cumple s≤s′ para cada s′∈S. Por supuesto, s es unico (por que?) y habitualmente es llamado el menor elemento de S, ya que es menor que todo otro elemento de S.

Si A es finito no vacio y ≤ es un orden total sobre A, podemos definir recursivamente una funcion f:{1,...,|A|}→A de la siguiente manera:

1. - f(1)= menor elemento de A

2. - Si i∈{1,...,|A|−1}, entonces

   1. - f(i+1)= menor elemento de A−{f(1),...,f(i)}

Como es habitual, f(i) es llamado el i-esimo elemento de A.

Muchas veces para dar un orden total sobre un conjunto finito A, daremos simplemente sus elementos en forma creciente ya que esto determina el orden por completo. Por ejemplo si A={1,2,3}, el orden total dado por 2<1<3 es la relacion ≤={(2,1),(1,3),(2,3),(1,1),(2,2),(3,3)}.

Un concepto importante relativo a los ordenes totales es el de sucesor. Si ≤ es un orden total sobre A y a,b∈A, diremos que b es el sucesor de a cuando se de que a<b y b≤c, para cada c∈A tal que a<c, i.e., b es el menor elemento del conjunto {c∈A: tal que a<c}. No siempre existe el sucesor de un elemento. Por ejemplo si ≤ es el orden usual de R, entonces ningun elemento tiene sucesor (justifique).

1.7.2.2 Diagramas de Hasse

Dado un orden parcial ≤ sobre un conjunto finito A podemos realizar un diagrama de ≤, llamado diagrama de Hasse, siguiendo las siguientes instrucciones:

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

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

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

   1. (i) Si a≺b, 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 de su diagrama, a saber, a≤b sucedera si y solo si pa=pb o hay una sucesion de segmentos ascendentes desde pa hasta pb.

Ejemplos:

1.7.3 Relaciones de equivalencia

Sea A un conjunto cualquiera. Por una relacion de equivalencia sobre A entenderemos una relacion binaria sobre A la cual es reflexiva, transitiva y simetrica, con respecto a A, es decir, la cual cumple:

1. Reflexividad xRx, cualesquiera sea x∈A

2. Transitividad xRy y yRz implica xRz, cualesquiera sean x,y,z∈A

3. Simetria xRy implica yRx, cualesquiera sean x,y∈A

Algunos ejemplos:

1. (E1) Sea R={(r,t)∈R2:r=t}. Entonces R es una relacion de equivalencia sobre R

2. (E2) Dada una funcion f:A→B, el nucleo de f, i.e. ker(f)={(a,b)∈A2:f(a)=f(b)} es una relacion de equivalencia sobre A.

3. (E3) Sea R={(1,1),(2,2),(3,3),(1,2),(2,1)}. Entonces R es una relacion de equivalencia sobre {1,2,3}

4. (E4) Sea R={(x,y)∈ω2:x=y}. Entonces R es una relacion de equivalencia sobre ω

5. (E5) Sea R={(S,T)∈P(ω)2:(S−T)∪(T−S) es finito}. Entonces R es una relacion de equivalencia sobre P(ω)

6. (E7) Sea R={(1,1)}. Entonces R es una relacion de equivalencia sobre {1}.

7. (E8) Sea R={(x,y)∈Z2:x−y es multiplo de 2}. Entonces R es una relacion de equivalencia sobre Z.

Dada una relacion de equivalencia R sobre A y a∈A, definimos: a/R={b∈A:aRb} El conjunto a/R sera llamado la clase de equivalencia de a, con respecto a R. Ejemplos:

1. (E1) Si R={(r,t)∈R2:r=t}, entonces r/R={r}, cualesquier sea r∈R

2. (E2) Si R={(1,1),(2,2),(3,3),(1,2),(2,1)}, entonces 1/R=2/R={1,2} y 3/R={3}

3. (E3) Si R={(x,y)∈Z2:x−y es multiplo de 2}, entonces 0/R={t∈Z:t es par}, 1/R={t∈Z:t es impar} y en general notese que n/R={t∈Z:t es par} si n es par y n/R={t∈Z:t es impar} si n es impar. Es decir que hay solo dos clases de equivalencia con respecto a R

Algunas propiedades basicas son:

Proof. (1) es muy facil.

(2) Supongamos aRb. Veremos que a/R⊆b/R. Supongamos c∈a/R. Entonces aRc. Como aRb, tenemos que bRa, por lo cual hemos probado que bRa y aRc, lo cual implica que bRc. O sea que cRb, lo cual nos dice que c∈b/R. Esto prueba que a/R⊆b/R. Similarmente se prueba que b/R⊆a/R, con lo cual se tiene que a/R=b/R.

Reciprocamente, si a/R=b/R, entonces b∈a/R ya que b∈b/R. Pero esto nos dice que aRb.

(3) Supongamos que a/R∩b/R no es vacio, es decir hay un c∈a/R∩b/R. Entonces es facil ver que aRb. Pero entonces por (2) tenemos que a/R=b/R.  

Denotaremos con A/R al conjunto {a/R:a∈A}. Llamaremos a A/R el cociente de A por R. Ejemplos:

1. (E1) Si R={(r,t)∈R2:r=t}, entonces R/R={{r}:r∈R}

2. (E2) Si R={(1,1),(2,2),(3,3),(1,2),(2,1)}, entonces {1,2,3}/R={{1,2},{3}}

3. (E3) Si R={(x,y)∈Z2:x−y es multiplo de 2}, ya vimos que Z/R={{t∈Z:t es par},{t∈Z:t es impar}}

Si R es una relacion de equivalencia sobre A, definamos la funcion πR:A→A/R por πR(a)=a/R, para cada a∈A. La funcion πR es llamada la proyeccion canonica (respecto de R).

1.7.3.1 Correspondencia entre relaciones de equivalencia y particiones

Dado un conjunto A por una particion de A entenderemos un conjunto P tal que:

1. - Cada elemento de P es un subconjunto no vacio de A

2. - Si S1,S2∈P y S1≠S2, entonces S1∩S2=∅

3. - A={a:a∈S, para algun S∈P}

La ultima condicion dice simplemente que la union de todos los elementos de P debe ser A. Ejemplos:

1. (E1) Si A={1,2,3,4,5}, entonces P={{1,5},{2,3},{4}}

   es una particion de A

2. (E2) P={N,R−N} es una particion de R

3. (E3) P={{0},{1,2},{3,4},{5,6},{7,8},{9,10},...} es una particion de ω

Una observacion importante es que si P es una particion de A, entonces para cada a∈A hay un unico S∈P tal que a∈S (por que?). O sea que podemos hablar de EL elemento de P que contiene a a.

Dada una particion P de un conjunto A podemos definir una relacion binaria asociada a P de la siguiente manera: RP={(a,b)∈A2:a,b∈S, para algun S∈P}

Proof. (1). Es facil ver que RP es reflexiva y simetrica. Veamos que es transitiva. Supongamos que aRPb y bRPc. O sea que hay S1,S2∈P tales que a,b∈S1 y b,c∈S2. Ya que S1 y S2 tienen un elemento en comun, debera suceder que S1=S2. Pero entonces tenemos que a,c∈S1, lo cual nos dice que aRPc.

(2). Sigue facilmente del Lema 1.3.  

El siguiente teorema da una correspondencia natural entre relaciones de equivalencia sobre A y particiones de A.

Proof. Notese que por el Lema 1.2 basta con probar:

1. (1) A/RP=P, cualesquiera sea la particion P de A

2. (2) RA/R=R, cualesquiera sea la relacion de equivalencia R sobre A

Prueba de (1). Primero veamos que A/RP⊆P. Sea a∈A, veremos que a/RP={b:aRPb}∈P. Sea S el unico elemento de P que contiene a a. Es facil ver de la definicion de RP que a/RP=S por lo cual a/RP∈P. Veamos ahora que P⊆A/RP. Sea S∈P. Sea a∈S. Es facil ver de la definicion de RP que a/RP=S por lo cual S∈A/RP.

Prueba de (2). Primero veamos que RA/R⊆R. Supongamos aRA/Rb. Entonces a,b∈c/R, para algun c∈A. Es claro que entonces aRb. Veamos ahora que R⊆RA/R. Supongamos que aRb. Entonces a,b∈a/R, lo cual nos dice que aRA/Rb.  

El teorema anterior muestra que a nivel de informacion es lo mismo tener una relacion de equivalencia sobre A que tener una particion de A. 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 {1,2,3,4,5} dada por la particion P={{1,5},{4},{2,3}} nos estaremos refiriendo a RP, es decir a la relacion: {(1,1),(2,2),(3,3),(4,4),(5,5),(1,5),(5,1),(2,3),(3,2)}

1.7.3.2 Definicion de funciones con dominio A/R

Supongamos R es una relacion de equivalencia sobre R y supongamos definimos una funcion f:R/R→R de la siguiente manera: f(r/R)=r2 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 R. Supongamos que R es tal que 2R6. Entonces tendriamos que 2/R=6/R, lo cual nos diria obviamente que f(2/R)=f(6/R). Pero f(2/R)=22=4 y f(6/R)=62=36, por lo cual deberia suceder que 4 sea igual a 36. El problema aqui es que la ecuacion f(r/R)=r2 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 f debe valer 4 y si usamos el 6 la ecuacion nos dice que f debe valer 36. Claramente no estamos definiendo una funcion.

Para dar un ejemplo mas concreto de este fenomeno de ambiguedad, supongamos R={(x,y)∈Z2:x−y es multiplo de 2} y definimos una funcion f:Z/R→R de la siguiente manera: f(n/R)=1/(n2+1) Como ya vimos Z/R={{t∈Z:t es par},{t∈Z:t es impar}}, por lo cual facilmente se puede llegar a que la ecuacion f(n/R)=1/(n2+1) no define correctamente una funcion. Por ejemplo, si llamamos c a la clase {t∈Z:t es par} tenemos que la ecuacion nos diria que f(c)=f(0/R)=1/(02+1)=1 y que tambien f(c)=f(2/R)=1/(22+1)=1/5.

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.

Proof. Que la ecuacion ˉf(a/kerf)=f(a) define sin ambiguedad una funcion ˉf:A/kerf→B es obvio ya que si a/kerf=b/kerf, entonces por definicion de kerf debera suceder que a=b. Dejamos al lector la prueba de que ˉf es inyectiva. Es obvio que f y ˉf tienen la misma imagen por lo cual si f es suryectiva, ˉf lo sera.