Mathematics">
Cap. 2 Relaciones y Funciones
Cap. 2 Relaciones y Funciones
Cap. 2 Relaciones y Funciones
Capı́tulo 2
Relaciones y Funciones
En este capı́tulo se hace un estudio formal de dos tipos fundamentales de conjuntos: las
relaciones y las funciones.
2.1. Relaciones
Para definir relaciones y funciones como conjuntos particulares es necesario definir primero
el concepto de pareja ordenada.
2.1.1 Definición. Para conjuntos a y b se define (a, b) := {a}, {a, b} .
Esta definición fue propuesta por Kuratowski en 1921 y, aunque no es obvia ni natural,
resulta adecuada para distinguir {a, b} de (a, b). En el siguiente teorema se demuestra la
propiedad caracterı́stica de las parejas ordenadas.
2.1.2 Teorema. Si (a, b) = (a′ , b′ ) si y solo si a = a′ y b = b′ .
Demostración. (=⇒) Se parte de la igualdad
concluye que a = a′ = b = b′ .
17
Introducción a la Teorı́a de la Conjuntos Capı́tulo 2 18
primero un conjunto suficientemente grande que incluya entre sus elementos tanto las
primeras como las segundas componentes de todas las parejas de R. Obsérvese que
S
(a, b) ∈ R =⇒ {a}, {a, b} ∈ R =⇒ {a}, {a, b} ∈ R
S S
=⇒ a, b ∈ R .
Por consiguiente, se puede definir
S S
dom(R) := a ∈ R : ∃b (a, b) ∈ R ,
S S
rango(R) := b ∈ R : ∃a (a, b) ∈ R .
S S S S
De manera que si R es un conjunto de parejas ordenadas, entonces R ⊆ R × R .
La propiedad asociativa permite escribir la composición de tres o más relaciones sin utilizar
paréntesis. Ası́, tanto R ◦ S ◦ T como R ◦ S ◦ T ◦ U representan composiciones de relaciones
sin ninguna ambigüedad.
Siguiendo esta idea se pueden definir a continuación cuádruplas, quı́ntuplas, etc, pero una
definición general del concepto de n-tupla requiere haber definido previamente el conjunto
N de los números naturales. Esto se hará detalladamente en el Capı́tulo 3. La noción de
producto cartesiano también se puede extender a una colección arbitraria de conjuntos,
pero un tratamiento general depende del Axioma de Elección (véase el Capı́tulo 5).
Ejercicios de la sección 2.1
(i) A × B = ∅ ⇐⇒ A = ∅ ∨ B = ∅.
(ii) A × (B ∪ C) = (A × B) ∪ (A × C),
(B ∪ C) × A = (B × A) ∪ (C × A).
(iii) A × (B ∩ C) = (A × B) ∩ (A × C),
(B ∩ C) × A = (B × A) ∩ (C × A).
(iv) A × (B − C) = (A × B) − (A × C),
(B − C) × A = (B × A) − (C × A).
(v) A × (B △ C) = (A × B) △ (A × C),
(B △ C) × A = (B × A) △ (C × A).
A × B ⊆ C × D =⇒ A ⊆ C ∧ B ⊆ D.
6. Sean ≤ y ≥ las relaciones usuales “menor o igual que” y “mayor o igual que”
definidas sobre el conjunto de los números reales R.
1. R es reflexiva
si todo
elemento de A está relacionado consigo mismo, es decir, si
∀a ∈ A (a, a) ∈ R .
2. R es simétrica si
∀a, b ∈ A (a, b) ∈ R −→ (b, a) ∈ R .
3. R es transitiva si
∀a, b, c ∈ A (a, b) ∈ R ∧ (b, c) ∈ R −→ (a, c) ∈ R .
Si no hay peligro de confusión, se escribe [a] en lugar de [a]R . Como aRa, a ∈ [a]; por
consiguiente, las clases de equivalencia son conjuntos no vacı́os. La siguiente proposición
establece las propiedades fundamentales de las clases de equivalencia.
(2) [a] = [b] ó [a] ∩ [b] = ∅. Es decir, dos clases de equivalencia son iguales o disyuntas.
Demostración.
1. (=⇒) Si x ∈ [a], entonces xRa. Como aRb, por la transitividad de R se sigue que
xRb, de donde x ∈ [b]. Esto muestra que [a] ⊆ [b]. Análogamente se demuestra que
[b] ⊆ [a].
(⇐=) Sea [a] = [b]. Como a ∈ [a], entonces a ∈ [b]; de donde aRb.
2. Si [a] ∩ [b] = ∅ no hay nada que demostrar. Si [a] ∩ [b] ̸= ∅, existe x ∈ [a] ∩ [b].
Entonces, x ∈ [a] y x ∈ [b]. Por la simetrı́a de R, aRx y xRb. Por transitividad, aRb
y por (1), [a] = [b].
(2) X, Y ∈ P y X ̸= Y =⇒ X ∩ Y = ∅.
S
(3) P = A.
5. Sea R una relación reflexiva sobre A. Demostrar que R es una relación de equiva-
lencia sobre A si y sólo si
∀a, b, c, d ∈ A (a, b) ∈ R ∧ (c, b) ∈ R ∧ (c, d) ∈ R −→ (a, d) ∈ R .
nRm ⇐⇒ n = ±m.
aRb ⇐⇒ a − b ∈ Z.
aSb ⇐⇒ a − b ∈ Q.
2.3. Funciones
Una función es una relación (conjunto de parejas ordenadas) con la propiedad de que no
hay dos parejas diferentes con la misma primera componente. Formalmente, una función
f es un conjunto de parejas ordenadas tal que
∀a∀b∀c (a, b) ∈ f ∧ (a, c) ∈ f −→ b = c . (2.3.1)
Si f es una función tal que dom(f ) = A y rango(f ) ⊆ B, se dice que f es una función
f
de A en B, lo cual se denota como f : A −→ B o como A −→ B. Por lo tanto, f es una
función de A en B si para todo a ∈ A, existe un único b ∈ B tal que (a, b) ∈ f . Esto se
puede expresar formalmente usando el cuantificador ∃!. En general, ∃!x φ(x) se lee “existe
un único x tal que φ(x)” y significa
f |X = f↾X = f ∩ (X × B).
9. Sea f : A −→ B.
(2) i, j ∈ I, i ̸= j =⇒ Ai ∩ Aj = ∅.
S
(3) i∈I Ai = A.
Para una familia doblemente indexada {Ai,j } i∈I la unión y la intersección se pueden
j∈J
expresar como
[
Ai,j = {x : (∃i ∈ I)(∃j ∈ J)(x ∈ Ai,j )},
i∈I
j∈J
\
Ai,j = {x : (∀i ∈ I)(∀j ∈ J)(x ∈ Ai,j )}.
i∈I
j∈J
Se tiene que [[ [[ [
Ai,j = Ai,j = Ai,j .
i∈I j∈J j∈J i∈I i∈I
j∈J
ya que
[[ [
x∈ Ai,j ⇐⇒ (∃i ∈ I) x ∈ Ai,j ⇐⇒ (∃i ∈ I)(∃j ∈ J)(x ∈ Ai,j )
i∈I j∈J j∈J
[
⇐⇒ x ∈ Ai,j .
i∈I
j∈J
Ejercicios de la sección 2.4
1. Sean {Ai }i∈I y {Bi }i∈I dos familias de conjuntos indexadas por elSmismo conjunto
S
Demostrar que si Ai ⊆ Bi para todo i ∈ I, entonces i∈I Ai ⊆ i∈I Bi
deTı́ndices I. T
y i∈I Ai ⊆ i∈I Bi .
Introducción a la Teorı́a de la Conjuntos Capı́tulo 2 32
2. Sean {Ai }i∈I y {Bj }i∈J familias arbitrarias de conjuntos. Demostrar que
S S S
(i) i∈I Ai ∪ j∈J Bj = i∈I (Ai ∪ Bj ).
j∈J
T T T
(ii) i∈I Ai ∩ j∈J Bj = i∈I (Ai ∩ Bj ).
j∈J
3. Sean {Ai }i∈I y {Bj }i∈J familias arbitrarias de conjuntos y B un conjunto cualquiera.
Demostrar las siguientes propiedades distributivas.
T T
(i) B ∪ i∈I A i = i∈I (B ∪ Ai ).
S S
(ii) B ∩ i∈I Ai = i∈I (B ∩ Ai ).
T T T
(iii) i∈I Ai ∪ j∈J Bj = i∈I (Ai ∪ Bj ).
j∈J
S S S
(iv) i∈I A i ∩ j∈J B j = i∈I (Ai ∩ Bj ).
j∈J
4. Sea {Ai }i∈I una familia de conjuntos y B un conjunto cualquiera. Demostrar las
siguientes propiedades distributivas del producto cartesiano con respecto a uniones
e intersecciones:
S S
(i) B × i∈I A i = i∈I (B × Ai ).
T T
(ii) B × i∈I Ai = i∈I (B × Ai ).
6. Demostrar la siguiente forma de las leyes de De Morgan, para el caso en que existe
un conjunto universal de referencia X, tal que Ai ⊆ X para todo i ∈ I, y los
complementos se toman con respecto a X:
S T
(i) i∈I Aj = i∈I Ai .
T S
(ii) i∈I Aj = i∈I Ai .
7. Sean {Ai }i∈I y {Bi }i∈I dos familias de conjuntos indexadas por el mismo conjunto
de ı́ndices I.
T T T
(i) Demostrar que i∈I Ai × i∈I Bi = i∈I (Ai × Bi ).
S S S
(ii) Demostrar que i∈I Ai × i∈I Bi ⊇ i∈I (Ai × Bi ).
S S S
(iii) Encontrar un contraejemplo para i∈I Ai × i∈I Bi ⊆ i∈I (Ai × Bi ).
8. Sean f : A −→ B, {Xi }i∈I una familia de subconjuntos de A y {Yi }i∈I una familia
de subconjuntos de B. Demostrar que
Introducción a la Teorı́a de la Conjuntos Capı́tulo 2 33
S S
(i) f i∈I X i = i∈I f [Xi ].
T T
(ii) f i∈I Xi ⊆ i∈I f [Xi ].
(iii) f −1 i∈I Yi = i∈I f −1 [Yi ].
S S
9. Sean {Ai }i∈I una partición de A y {Bj }j∈J una partición de B. Demostrar que
{Ai × Bj } i∈I es una partición de A × B.
j∈J
2.5.1 Definición. Dos funciones f y g son compatibles si f (x) = g(x) para todo x ∈
dom(f ) ∩ dom(g).
2.5.3 Proposición. Sea F un conjunto de funciones compatibles dos a dosS (es decir,
si dos funciones f y g pertenecientes a F son compatibles). Entonces g = F es una
función. Se tiene además que:
S
(1) dom(g) = {dom(f ) : f ∈ F }.
S
(2) rango(g) = {rango(f ) : f ∈ F }.
1. R es antisimétrica si
∀a, b ∈ A (a, b) ∈ R ∧ (b, a) ∈ R −→ a = b .
Equivalentemente,
∀a, b ∈ A aRb ∧ bRa −→ a = b .
Introducción a la Teorı́a de la Conjuntos Capı́tulo 2 35
1. A ⊆ A (Reflexividad).
2. A ⊆ B ∧ B ⊆ A =⇒ A = B (Antisimetrı́a).
3. A ⊆ B ∧ B ⊆ C =⇒ A ⊆ C (Transitividad).
La siguiente proposición indica cómo se pueden obtener nuevas relaciones de orden a partir
de una relación de orden dada. La proposición se sigue directamente de las definiciones.
2.6.2 Proposición. Sea R es una relación de orden sobre A. Entonces
1. La relación inversa R−1 también es una relación de orden sobre A. Si R se denota
por ≤, la inversa R−1 se denota por ≥. En general, a ≥ b también se lee “a es mayor
o igual que b”.
Introducción a la Teorı́a de la Conjuntos Capı́tulo 2 36
•
a
Ejemplo A continuación se exhibe un diagrama de Hasse para el conjunto de sub-
conjuntos de {a, b, c}, ordenado por contenencia, es decir, para el orden
(℘({a, b, c}), ⊆).
{a, b, c}
•
{a, b} • • {b, c}
•{a, c}
•
{a} • {b} • {c}
•
∅
Dado un conjunto ordenado (A, ≤), un diagrama de Hasse para la relación inversa (A, ≥)
se obtiene invirtiendo verticalmente el diagrama de (A, ≤).
a < b ⇐⇒ a ≤ b ∧ a ̸= b
2. Ejercicio.
Los procedimientos de la Proposición 2.6.4 son mutuamente reversibles (véase el Ejerci-
cio 2.6.4).
2.6.5 Definición. Sea (A, ≤) un conjunto ordenado.
1. Un elemento m ∈ A es minimal si (∀a ∈ A)[a ≤ m −→ a = m].
Esto quiere decir que m es minimal si no existe en A un elemento que sea estrictamen-
te menor que m. Análogamente, m es maximal si no existe en A un elemento que sea
estrictamente mayor que m, es decir, si ¬(∃a ∈ A)[m < a].
Si (A, ≤) tiene un elemento mı́nimo m, éste debe ser único ya que si m′ es también
mı́nimo, se tendrá m ≤ m′ y m′ ≤ m y, por lo tanto, m = m′ por la propiedad anti-
simétrica. En tal caso, se dice que m es el mı́nimo de (A, ≤) y se escribe m = min(A).
Similarmente, si (A, ≤) tiene un elemento máximo m, éste es único y se denota por
m = max(A). Se acostumbra denotar el máximo por ⊤ y el mı́nimo por ⊥ (cuando estos
existen, por supuesto). Nótese además que si m = min(A) existe, entonces m es el único
elemento minimal de (A, ≤), y si m = max(A) existe, entonces m es el único elemento
maximal de (A, ≤).
Ejemplo Considérense los conjuntos A = {a, b, c, d, x, y} y B = {p, q, r, s, t, u}, orde-
nados como lo muestran los siguientes diagramas.
t
x• •y •
b• •d q• r• •s
•c
• • •u
a p
Se tiene que min(A) = a, ası́ que a es el único elemento minimal de A. Los elementos
maximales de (A, ≤) son c, x y y. (A, ≤) no tiene máximo. Por otro lado, (B, ≤) no tiene
ni mı́nimo ni máximo. Sus elementos minimales son son p, q, u; sus maximales son u y t.
Estos ejemplos ilustran que el máximo o el mı́nimo no siempre existen, y que un elemento
puede ser tanto minimal como maximal.
⊤
•
p
• •q •r
e
d• • x•
a• b• •c
•
⊥
Introducción a la Teorı́a de la Conjuntos Capı́tulo 2 40
3. Se dice que (A, ≤) es bien ordenado (o que es un buen orden) si todo subconjunto
no vacı́o de A tiene elemento mı́nimo. Es decir, si para todo B ⊆ A y B ̸= ∅, existe
min(B).
Nótese que todo conjunto bien ordenado necesariamente es totalmente ordenado ya que,
dados a, b ∈ A, el subconjunto no vacı́o {a, b} debe tener elemento mı́nimo y, por lo tanto,
se tendrá a ≤ b o b ≤ a. Pero, no todo conjunto totalmente ordenado es bien ordenado,
como se mostrará más adelante.
4
En castellano, retı́culo significa “que tiene forma de red”.
Introducción a la Teorı́a de la Conjuntos Capı́tulo 2 41
Isomorfismo entre conjuntos ordenados. Sean (P, ≤) y (Q, ≼) dos conjuntos par-
cialmente ordenados. Un isomorfismo de orden (o simplemente un isomorfismo) entre P
y Q es una función inyectiva h : P −→ Q tal que
(Véase el Ejercicio 2.6.9). Intuitivamente, si (P, ≤) y (Q, ≼) son isomorfos, entonces son
idénticos como conjuntos ordenados (salvo el nombre de sus elementos). Para capturar
acertadamente esta idea, en la condición (2.6.1) la doble implicación no se puede reem-
plazar por una implicación simple; es decir, si se cumple
no podemos concluir que, como conjuntos ordenados, (P, ≤) y (Q, ≼) son idénticos (orden-
isomorfos). Por ejemplo, para los conjuntos P = {a, b, c, d} y Q = {a′ , b′ , c′ , d′ }, ordenados
como se muestra en la siguiente gráfica, la función h definida por h(a) = a′ , h(b) = b′ ,
h(c) = c′ y h(d) = d′ , satisface (2.6.3) pero no (2.6.1). Se observa que (P, ≤) y (Q, ≼) no
son isomorfos.
d
• • d′
• c′
b• c •
• b′
• • a′
a
En el caso en que (P, ≤) y (Q, ≼) sean linealmente ordenados, las condiciones (2.6.1) y
(2.6.3) sı́ resultan equivalentes (véase el Ejercicio 2.6.14).
Ejercicios de la sección 2.6
a ∼ b si y sólo si a ≤ b y b ≤ a.
Demostrar que ⪯ que está bien definida, es decir, no depende de los represen-
tantes a y b de las clases [a] y [b], respectivamente.
(iii) Demostrar que ⪯ es una relación de orden sobre A/ ∼.
Introducción a la Teorı́a de la Conjuntos Capı́tulo 2 43
⊤
•
p
• •q •r
e
d• • x•
• • •
a b c
10. Sea (A, ≤) un conjunto ordenado y sea f : A −→ ℘(A) la función definida por
f (a) = {x ∈ A : x ≤ a}, para cada a ∈ A. Demostrar que f es un isomorfismo de
orden entre (A, ≤) y (℘(A), ⊆).
11. Demostrar que si (P, ≤) y (Q, ≼) son isomorfos y ≤ es un orden lineal, entonces ≼
es un orden lineal.
12. Demostrar que si h es un isomorfismo de (P, ≤) sobre (Q, ≼), entonces h−1 es un
isomorfismo de (Q, ≼) sobre (P, ≤).
15. Sean (A, ≤1 ) y (B, ≤2 ) dos conjuntos parcialmente ordenados. Sobre el producto
cartesiano A × B se define la relación ≤ de la siguiente manera:
(a, b) ≤ (a′ , b′ ) ⇐⇒ a ≤1 a′ ∧ b ≤2 b′ ,
para todo a, a′ ∈ A y b, b′ ∈ B.
Introducción a la Teorı́a de la Conjuntos Capı́tulo 2 44
(i) Demostrar que ≤ es una relación de orden sobre A×B. Este orden se denomina
orden puntual.
(ii) Demostrar o refutar: Si (A, ≤1 ) y (B, ≤2 ) son conjuntos linealmente ordenados,
entonces (A × B, ≤) es linealmente ordenado.
(iii) Demostrar o refutar: Si (A, ≤1 ) y (B, ≤2 ) son conjuntos bien ordenados, en-
tonces (A × B, ≤) es bien ordenado.
(iv) Sean C ⊆ A, D ⊆ B, sup(C) = a, sup(D) = b. Demostrar que sup(C × D) =
(a, b).
16. Sean (A, ≤1 ) y (B, ≤2 ) dos conjuntos parcialmente ordenados. Sobre el producto
cartesiano A × B se define la relación ≺ de la siguiente manera:
para todo a, a′ ∈ A y b, b′ ∈ B.
(i) Demostrar que la relación ≺ es un orden estricto sobre A×B. El orden estricto
≺ (o el orden parcial inducido ≼) se denomina orden lexicográfico.
(ii) Demostrar que si (A, ≤1 ) y (B, ≤2 ) son bien ordenados, entonces (A × B, ≼)
es también un buen orden.