ALGEBRA (Ciencias) – ano 2009

Algo sobre relaciones.

Sean A,B,Cy D conjuntos.

Se llama producto cartesiano de A por B al conjunto

A×B = {(x, y)/x ∈ A ∧ y ∈ B}.

Vale que:

1. A× ∅ = ∅ × A = ∅2. Si A y B son conjuntos no vacıos, A×B = B × A ↔ A = B.

3. Si A y B son conjuntos no vacıos, A×B ⊆ C ×D ↔ A ⊆ C ∧B ⊆ D.

4. (A×B) ∪ (C ×D) ⊆ (A ∪ C)× (B ∪D).

5. (A×B) ∩ (C ×D) = (A ∩ C)× (B ∩D).

Una relacion de A en B es un subconjunto del producto cartesiano de A por B, es decir:

R es una relacion de A en B ↔R ⊆ A×B ↔R ∈ P(A×B).

Sea x ∈ A e y ∈ B. Se dice que x esta R-relacionado con y; o que x esta relacionado con ypor R, si (x, y) ∈ R, tambien suele notarse xRy.

A se dice el conjunto de partida de la relacion R.

B se dice el conjunto de llegada de la relacion R.

Se llama dominio de R a

Dom(R) = {x ∈ A/ existe algun elemento y ∈ B tal que (x, y) ∈ R}

Se llama rango o imagen de R a

Rg(R) = {y ∈ B/ existe algun elemento x ∈ A tal que (x, y) ∈ R}

Se llama relacion inversa de R a la relacion de B en A

R−1 = {(y, x) ∈ B × A/(x, y) ∈ R}.

Si A′ ⊆ A, se llama imagen de A′ por R al conjunto

R(A′) = {y ∈ B/ existe algun elemento x ∈ A′ tal que (x, y) ∈ R}.

Si B′ ⊆ B, se llama imagen inversa de B′ por R al conjunto

R−1(B′) = {x ∈ A/ existe algun elemento y ∈ B′ tal que (x, y) ∈ R},

coincide con la imagen de B′ por R−1.

Vale que:

1

1. (R−1)−1 = R.

2. Dom(R−1) = Rg(R).

3. Rg(R−1) = Dom(R).

4. Si A′ ⊆ A, entonces (R−1)−1(A′) = R(A′).Demostracion:b ∈ R(A′) ↔ existe a′ ∈ A′ : a′Rb por definicion de imagen

↔ existe a′ ∈ A′ : bR−1a′ por definicion de relacion inversa↔ existe a′ ∈ A′ : a′(R−1)−1b por definicion de relacion inversa↔ b ∈ (R−1)−1(A′) por definicion de imagen

Sea R una relacion en A (es decir una relacion de A en A).

R se dice reflexiva si para todo elemento x ∈ A se verifica que xRx o equivalentemente si

(∀x)(x ∈ A → (x, x) ∈ R).

R se dice simetrica si para todo par de elementos x, y ∈ A se verifica que (xRy → yRx) oequivalentemente si

(∀x)(∀y)((x, y) ∈ R → (y, x) ∈ R).

R se dice antisimetrica si para todo par de elementos x, y ∈ A se verifica que (xRy∧yRx →x = y) o equivalentemente si

(∀x)(∀y)((x, y) ∈ R ∧ (y, x) ∈ R → x = y).

R se dice transitiva si dados elementos cualesquiera x, y, z ∈ A se verifica que (xRy∧yRz →xRz) o equivalentemente si

(∀x)(∀y)(∀z)((x, y) ∈ R ∧ (y, z) ∈ R → (x, z) ∈ R).

Vale que,

1. R∪R−1 es simetrica.

2. Si R reflexiva ⇒R−1 es reflexiva.

3. Si R simetrica ⇒R−1 es simetrica.

4. Si R transitiva ⇒R−1 es transitiva.

5. Si R antisimetrica ⇒R−1 es antisimetrica.

Demostracion:

debemos probar que R−1 es antisimetrica, es decir debemos probar que

xR−1y ∧ yR−1x ⇒ x = y.

Lo vemos,

xR−1y ⇒ yRx, (I), por definicion de relacion inversa.yR−1x ⇒ xRy, (II), por definicion de relacion inversa.

(I) ∧ (II) ⇒ xRy ∧ yRx⇒ x = y pues, por hipotesis, R es antisimetrica.

2

SeaR una relacion en A. Se dice queR es una relacion de orden si es reflexiva, antisimetricay transitiva.

R se dice una relacion de orden total si es una relacion de orden y ademas para todo parde elementos x, y ∈ A se verifica que xRy ∨ yRx.

Ejemplos:

1) ≤ es una relacion de orden total en R.

2) Si E es un conjunto no vacıo cualquiera, ⊆ es una relacion de orden en P(E). Si E tieneal menos dos elementos, ⊆ no es un orden total.

3) En N se define la relacion /, divide, en la forma:

m/n ↔ existe k ∈ N tal que n = k.n

/ es una relacion de orden, no total, en N.

4) En RR = {f : R → R} (el conjunto de las funciones de R en R) se define la relacion ≤en la forma,

f ≤ g ↔ para todo x ∈ R, se verifica que f(x) ≤ g(x).

Esta es una relacion de orden, no total, en RR.5) Sea R es una relacion de orden en A y S es una relacion de orden en B. Se define enA×B la relacion ∼ en la forma:

(a, b) ∼ (a′, b′) ↔ aRb ∧ a′Sb′

Veamos que ∼ es una relacion de orden en A×B.

Demostracion:

∼ es reflexiva:

(a, b) ∈ A×B ⇒ a ∈ A ∧ b ∈ B ⇒ aRa ∧ bSb (pues R y S son reflexivas) ⇒ (a, b) ∼ (a, b)(por definicion de ∼).

∼ es antisimetrica:

(a, b) ∼ (a′, b′) ∧ (a′, b′) ∼ (a, b) ⇒ (aRa′ ∧ bSb′) ∧ (a′Ra ∧ b′Sb) (por definicion de ∼)⇒ (aRa′∧a′Ra)∧(bSb′∧b′Sb) (por asociatividad y conmutatividad de ∧) ⇒ a = a′∧b = b′

(pues R y S son antisimetricas) ⇒ (a, b) = (a′, b′).

∼ es transitiva:

(a, b) ∼ (a′, b′) ∧ (a′, b′) ∼ (a′′, b′′) ⇒ (aRa′ ∧ bSb′) ∧ (a′Ra′′ ∧ b′Sb′′) (por definicion de ∼)⇒ (aRa′∧a′Ra′′)∧(bSb′∧b′Sb′′) (por asociatividad y conmutatividad de ∧) ⇒ aRa′′∧bSb′′

(pues R y S son transitivas) ⇒ (a, b) ∼ (a′′, b′′) (por definicion de ∼).

Sea ∼ una relacion de orden en A.

Si x,y son elementos distintos de A y x ∼ y, se dice que x es mas chico que y o quey es mas grande que x.

Si x,y,z son elementos distintos de A y x ∼ y ∼ z, se dice que y esta entre x y z.

3

Si x,y son elementos distintos de A y x ∼ y y no existe un elemento w ∈ A tal quex ∼ w ∼ y decimos que y es sucesor inmediato de x, o que x es antecesor inmediato de y,o que y cubre a x.

Sea A’ un subconjunto no vacıo de A y a ∈ A.

a se dice maximal en A’ si a ∈ A′ y en A′ no hay un elemento mas grande que a, es decira ∈ A′ ∧ (x ∈ A′ ∧ a ∼ x → x = a).

a se dice minimal en A’ si a ∈ A′ y en A′ no hay un elemento mas chico que a, es decira ∈ A′ ∧ (x ∈ A′ ∧ x ∼ a → x = a).

a se dice una cota superior de A’, si (∀x)(x ∈ A′ → x ∼ a).

a se dice una cota inferior de A’, si (∀x)(x ∈ A′ → a ∼ x).

a se dice primer elemento de A’ si a ∈ A′ y a es mas chico que cualquier otro elementode A′, es decir a ∈ A′ ∧ (∀x)(x ∈ A′ → a ∼ x).

a se dice ultimo elemento de A’ si a ∈ A′ y a es mas grande que cualquier otro elementode A′, es decir a ∈ A′ ∧ (∀x)(x ∈ A′ → x ∼ a).

a se dice supremo de A’ si es el primer elemento del conjunto formado por todos loselementos de A que son cotas superiores de A’.

a se dice ınfimo de A’ si es el ultimo elemento del conjunto formado por todos los elementosde A que son cotas inferiores de A’.

Vale que:

a primer elemento de A′ ⇒ a cota inferior de A′. En general de recıproca no vale.

a primer elemento de A′ ⇒ a ınfirmo de A′. En general de recıproca no vale.

a primer elemento de A′ ⇒ a minimal de A′. En general de recıproca no vale.

a ınfimo de A′ ⇒ a cota inferior de A′. En general de recıproca no vale.

Observar que en general:

ınfimo ; minimal.

minimal ; ınfimo.

minimal ; cota inferiror.

cota inferior ; minimal.

Una relacion de orden en un conjunto A se dice un buen orden si todo subconjunto no vacıode A tiene primer elemento.

Si ∼ es un buen orden en A ⇒ ∼ es un orden total en A. En general la recıproca no esverdadera.

Sea R una relacion en A y sea A′ un subconjunto de A. Se llama restriccion a A′ de R ala relacion de A′ dada por:

R∩ (A′ × A′) = {(x, y) ∈ A′ × A′/(x, y) ∈ R}Si R es una relacion de orden en A y A′ es un subconjunto cualquiera de A, la restricciona A′ de R es tambien una relacion de orden, suele llamarse el orden inducido en A′ por R.En general el orden inducido se vuelve a indicar por R. Por ejemplo:

4

1. ≤ es una relacion de orden en cualquier subconjunto de R.

2. / es una relacion de orden en cualquier subconjunto de N.

Sea R una relacion en A. Se dice que R es una una relacion de equivalencia si es reflexiva,simetrica y transitiva.

Ejemplos:

1. La relacion = en un conjunto cualquiera.

2. La relacion de R dada porx ∼ y ↔ x− y ∈ Z

3. La relacion de Z dada por

m ≡n m′ ↔ n divide a m−m′

Esta relacion se llama equivalencia modulo n.

Sea ∼ una relacion de equivalencia en A y sea a ∈ A. Se llama clase de equivalencia de a(segun la relacion ∼) al conjunto que denotamos a formado por todos los elementos de Aque estan relacionados con a, es decir:

a = {x ∈ A/x ∼ a}.

Se llama conjunto cociente de A por ∼ al conjunto que se indica A/∼ formado por las clasesde equivalencias de los elementos de A, es decir:

A/∼ = {a, a ∈ A}.

Observar que:

Para todo elemento a ∈ A, se verifica a ⊆ A y ademas a 6= ∅.Para todo par de elementos a, a′ ∈ A, vale que si a ∩ a′ 6= ∅, entonces a = a′.

Resulta que A/∼ es una particion de A.

Sea P una particion de A. La relacion R definida en A en la forma

xRy ↔ existe un conjunto F ∈ P tal que x ∈ F ∧ y ∈ F,

es una relacion de equivalencia en A. Ademas, la particion A/R es la misma P . En otraspalabras, existe una correspondencia uno a uno entre las particiones de A y las relacionesde equivalencia de A.

5