GCED Tema 2 2020 21

GCED.
Curso 2020–2021
Tema 2
Matemática Discreta. Área de Álgebra
Conjuntos, Aplicaciones y Relaciones

Universidade da Coruña
Recuerda que estas notas son, únicamente, parte del material de trabajo de los profesores de esta
asignatura. Los contenidos de este tema se pueden ver en los siguientes libros:
• F. Aguado, F. Gago, M. Ladra, G. Vega, C. Vidal, A. Vieites Problemas Resueltos de

Combinatoria. Laboratorio con SageMath: capítulo 1. Paraninfo 2018.
• K.H. Rosen, Matemática Discreta y sus aplicaciones: capítulo 1 (secciones 1.6, 1.7 y 1.8) y
capítulos 7, 8 y 9.
• R.P. Grimaldi, Matemática Discreta y combinatoria: capítulos 3, 5 y 7.
• S.S. Epp, Matemáticas Discretas con aplicaciones: capítulos 6, 7 y 8.
2.1 Conjuntos
Consideraremos como punto de partida la noción intuitiva de conjunto, un objeto matemático que
nos proporcionará el lenguaje adecuado para la definición de conceptos que introduciremos en los
capítulos posteriores. Esta explicación intuitiva es deficiente: la teoría de conjuntos se formalizó
definitivamente a principios del siglo XX cuando se demostró que algunas colecciones no podían
denominarse conjuntos. Pero esto no nos hace falta para nuestros propósitos.
Diremos que un conjunto es una colección bien definida de objetos distinguibles entre sí. A
los objetos que constituyen un conjunto se les denomina elementos del mismo. Si la colección
carece de objetos, el conjunto se denota por ∅ o por { } y se denomina conjunto vacío.
Dado un conjunto y un objeto debemos ser capaces de decidir (a veces no es fácil) si el objeto
pertenece o no al conjunto.
Los conjuntos se designan, habitualmente, por letras latinas mayúsculas: A, B, . . . y los ele-
mentos por letras latinas minúsculas: a, b, . . . Si a es un elemento del conjunto A, se dirá que a
31
32 TEMA 2. CONJUNTOS, APLICACIONES Y RELACIONES
pertenece al conjunto A, y se escribirá a ∈ A; en caso contrario, se dirá que el elemento no

pertenece al conjunto y se denotará a 6∈ A.
Un conjunto A está bien definido cuando, dado un objeto cualquiera x, se cumple que x ∈ A
o x 6∈ A, pero no ambas proposiciones a la vez.
Ejemplos de conjuntos de números usados en matemáticas son N, los números naturales, Z, los
números enteros, Q, los números racionales, R, los números reales, y C, los números complejos.
Los conjuntos se representan encerrando entre llaves “{” y “}” bien sus elementos, bien la ley
que los determina. Por ejemplo
{0, 2, 4, 6, 8} y {n ∈ N | n es un número par no negativo menor que 10}
representan el mismo conjunto.
Ejemplo 1.
i) A = {n ∈ Z | 1 ≤ n ≤ 6} = {1, 2, 3, 4, 5, 6}
A
2
Se verifica:
1 6
2 ∈ A,
3 4 6 ∈ A,
5 13 ∈
/ A,
casa ∈
/A
A representado por un
diagrama de Venn
ii) B = {x ∈ Z | x2 ≤ 16} = {0, 1, 2, 3, 4, −1, −2, −3, −4};
iii) C = {x ∈ N | x divide a 20} = {1, 2, 4, 5, 10, 20};
iv) ∅ = {x ∈ Z | x2 = 3} = { }.
Si consideramos el conjunto formado por “Los diez mejores jugadores de fútbol de todos los
tiempos” no tenemos un conjunto bien definido puesto que la condición de “ser mejor jugador” no
es objetiva.
Nota: Es importante no confundir conjuntos con listas. Las listas se representan utilizando
corchetes “[” y “]”, y mientras que en un conjunto no se repiten los elementos ni tampoco influye el
orden en que aparecen, en las listas sí importa el lugar que ocupa un elemento así como el número
de veces que aparece cada elemento. Así pues:
[1, 3, 5] 6= [1, 5, 3]; [1, 3, 5] 6= [1, 1, 3, 5] 6= [1, 3, 3, 5]
Un conjunto A es finito si tiene un número n ∈ N de elementos; este número se llama cardinal

de A y se denota o bien por |A| o bien por #A. En caso contrario, se dice que A es no finito.
2.1. CONJUNTOS 33
Ejemplo 2.
i) Son conjuntos finitos:
• A = {1, 2, a, c}, |A| = 4;

• B = {∅, {a, b}}, |B| = 2;
• C = {∅, {∅}, {3, 2}}, |C| = 3;
• el conjunto formado por los números enteros cuyo producto por 3 es mayor que -5 y
menor o igual que 15, D = {n ∈ Z | −5 < 3n ≤ 15}, |D| = 7.
ii) Son conjuntos no finitos:
• el conjunto formado por los números naturales pares, {n ∈ N | n es par};

• el conjunto formado por los números enteros cuyo producto por 2 es menor que 100,
{n ∈ Z | 2n < 100}.
2.1.1 Inclusión
Definición 1. Dados dos conjuntos A y B, se dice que A es un subconjunto de B, y se denota
por A ⊆ B, si cada elemento de A es también elemento de B, es decir:
∀x [x ∈ A → x ∈ B] es verdadera.
Si A ⊆ B diremos que A está incluido o contenido en B.
• Cuando A no está contenido en B, se escribirá A * B (lo cual quiere decir que existe a ∈ A
tal que a 6∈ B), es decir, se verifica que
∃a [a ∈ A ∧ a ∈
/ B].
• Cualquier conjunto B, siempre admite como subconjuntos al conjunto vacío ∅ y al propio

conjunto B. Estos se denominan subconjuntos impropios o triviales. En otro caso, se habla
de subconjunto propio de B.
• Si A ⊆ B y A 6= B, se dice que A está contenido estrictamente en B y se denota A ⊂ B.
B A
Inclusión de conjuntos mediante diagramas de Venn: A ⊆ B

Ejemplo 3.
i) ∅ ⊆ ∅; v) N ⊆ Z;
ii) ∅ ⊆ {a, b, c, {a, b, c}}; vi) {a, b, c} ∈ {a, b, c, {a, b, c}};

iii) {a, b} ⊆ {a, b, c, {a, b, c}};
vii) {a, b, c} ⊆ {a, b, c, {a, b, c}}
iv) {a, {b}} * {a, b, c, {a, b, c}}; porque a, b, c ∈ {a, b, c, {a, b, c}}.
Un conjunto está totalmente determinado por sus elementos. Por ello, dos conjuntos A y B
son iguales si ambos tienen los mismos elementos, es decir, se verifica A ⊆ B y B ⊆ A
A = B ⇔ A ⊆ B ∧ B ⊆ A.
Definición 2. El conjunto formado por todos los subconjuntos de uno dado X se denomina con-
junto partes de X y se denota P(X).
Si A y X son dos conjuntos cualesquiera, se verifica que
A ∈ P(X) ⇔ A ⊆ X.
Si X es finito y tiene cardinal n entonces P(X) es finito y tiene cardinal |P(X)| = 2n .
Ejemplo 4.

i) Si X = {a, b}, entonces P(X) = ∅, {a}, {b}, X ;
ii) {2} ∈ P(Z);
A = {a, b, c} es un conjunto finito

iii) con |A| = 3 y también es finito el conjunto P(A) =
3
∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c , A} y el cardinal de este es 2 = 8.
Cuando, en un contexto determinado, consideremos varios conjuntos, estos se considerarán

subconjuntos de uno dado U . Dicho conjunto de referencia U se denomina conjunto universal
o universo.
2.2 Operaciones con conjuntos. Propiedades

Sea X un conjunto arbitrario. En esta sección vamos a definir tres operaciones sobre P(X) cuyas
propiedades se corresponderán con las vistas en el tema anterior para las operaciones negación,
disyunción y conjunción de proposiciones, como se indica en la tabla siguiente:
2.2. OPERACIONES CON CONJUNTOS. PROPIEDADES 35
Lógica Conjuntos
¬ Negación Complementario
S
∨ Disyunción Unión
T
∧ Conjunción Intersección
Definición 3. Dado un conjunto U y un subconjunto A ⊆ U se llama complementario (respecto

a U ) del conjunto A, y se denota por A, al subconjunto de U formado por todos los elementos que
no pertenecen a A, es decir:
A = {x ∈ U | x 6∈ A}.
Obsérvese que la propiedad que determina al complementario de A es la negación de la

propiedad que determina a los elementos de A.
U
A
Complementario de A respecto a U .
Propiedades 1. Dado un conjunto U y A, B ⊆ U , se verifican las siguientes propiedades:
i) ∅ = U ; iii) A = A;
ii) U = ∅; iv) A ⊆ B ⇔ B ⊆ A.
Definición 4. Dados dos conjuntos A y B se llama

• unión de A y B, y se representa por A ∪ B, al conjunto formado por los elementos que
pertenecen a A o a B:
A ∪ B = {x ∈ U | x ∈ A ∨ x ∈ B},
• intersección de A y B, y se representa por A ∩ B, al conjunto formado por los elementos

que pertenecen a A y a B:
A ∩ B = {x ∈ U | x ∈ A ∧ x ∈ B}.
Dos conjuntos que no tienen ningún elemento en común, se dice que son disjuntos, es decir:
A y B son disjuntos ⇔ A ∩ B = ∅.
A B A B
Unión de conjuntos: A ∪ B Intersección de conjuntos: A ∩ B

Ejemplo 5.
i) Si A = {a, x} y B = {b, x}, entonces A ∪ B = {a, b, x} y A ∩ B = {x}.
ii) Si A = {a, y} y B = {b, x}, entonces A ∪ B = {a, b, x, y} y A ∩ B = ∅.
iii) Si A = {a, b, c} y B = {a, b, c, m}, entonces A∪B = {a, b, c, m} = B y A∩B = {a, b, c} = A,

(nótese que A ⊆ B).
iv) Si A = {x, y} y B = {x, {y}, {x, z}}, entonces A ∪ B = {x, y, {y}, {x, z}} y A ∩ B = {x}.
Propiedades 2. Para cualesquiera conjuntos A, B y C, subconjuntos de U , se verifica:

i) A ∪ ∅ = A y A ∩ U = A.
ii) A ∪ A = U y A ∩ A = ∅.
iii) La unión y la intersección son conmutativas:

A ∪ B = B ∪ A y A ∩ B = B ∩ A.
iv) La unión y la intersección son asociativas:

A ∪ (B ∪ C) = (A ∪ B) ∪ C y A ∩ (B ∩ C) = (A ∩ B) ∩ C.
v) La unión es distributiva respecto a la intersección, y viceversa:

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) y A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
Estas propiedades permiten deducir otras que recogemos a continuación:
Propiedades 3. Dados los conjuntos A, B y C, subconjuntos de U , se verifica:
i) A ∪ A = A y A ∩ A = A.
ii) A ∪ U = U y A ∩ ∅ = ∅.
iii) A ∪ (A ∩ B) = A y A ∩ (A ∪ B) = A.
iv) (A ∪ B) = A ∩ B y (A ∩ B) = A ∪ B.
v) A ⊆ (A ∪ B) , B ⊆ (A ∪ B).
vi) (A ∩ B) ⊆ A, (A ∩ B) ⊆ B.
2.2. OPERACIONES CON CONJUNTOS. PROPIEDADES 37
vii) A ⊆ C ∧ B ⊆ C ⇔ (A ∪ B) ⊆ C.
viii) C ⊆ A ∧ C ⊆ B ⇔ C ⊆ (A ∩ B).
ix) A ⊆ B ⇔ A ∪ B = B ⇔ A ∩ B = A.
Definición 5. Se extiende la definición de unión y de intersección para una colección finita

A1 , A2 , . . . , An de subconjuntos de U :
n
[
Ai = {x ∈ U | x pertenece al menos a un conjunto Ai , con i = 1, 2, . . . , n};
i=1
n
\
Ai = {x ∈ U | x pertenece a todos los conjuntos Ai , con i = 1, 2, . . . , n}.
i=1
Si los conjuntos A1 , A2 , . . . , An son finitos y disjuntos dos a dos (es decir, Ai ∩Aj = ∅, ∀i 6= j),
entonces
|A1 ∪ A2 ∪ · · · ∪ An | = |A1 | + |A2 | + · · · + |An |.
Esta propiedad es una de las técnicas básicas de conteo, se denomina Principio de la adición
y se estudiará en el tema 3.
Sin embargo, esta igualdad no se cumple cuando los conjuntos no son disjuntos dos a dos. Por
ejemplo, para dos conjuntos finitos A y B, se verifica |A ∪ B| = |A| + |B| − |A ∩ B|. El Principio
de inclusión-exclusión es una generalización de esta fórmula y también se verá en el tema 3.
Además se verifica que : ∪ni=1 Ai = ∩ni=1 Ai y ∩ni=1 Ai = ∪ni=1 Ai .
Ejemplo 6. Consideremos los siguientes subconjuntos de Z:
A1 = {n ∈ Z | n es múltiplo de 5},
A2 = {n ∈ Z | n es múltiplo de 2},
A3 = {n ∈ Z | n es múltiplo de 3};
se verifica que
4 ∈ A1 ∪ A2 ∪ A3 ; 30 ∈ A1 ∩ A2 ∩ A3 ; 8 ∈ A1 ∩ A2 ∩ A3 ; 10 ∈ A1 ∩ A2 ∩ A3 ;
de hecho,
A1 ∪ A2 ∪ A3 = {n ∈ Z | n es múltiplo de 2 o de 3 o de 5}.
A1 ∩ A2 ∩ A3 = {n ∈ Z | n es múltiplo de 30}.
A1 ∩ A2 ∩ A3 = {n ∈ Z | n es par y no es múltiplo ni de 3 ni de 5},
Además de las operaciones anteriores se pueden definir otras en P(U ), como, por ejemplo, la
diferencia de conjuntos:
Definición 6. Dados dos conjuntos A y B se llama diferencia entre A y B, y se representa por

A\B o por A − B, al conjunto formado por los elementos de A que no pertenecen a B:
A\B = {x ∈ A | x 6∈ B}
A B
A\B
Diferencia de conjuntos A\B
Observemos que A\B = A ∩ B. Además, se verifica que

A\B = A ⇔ A ⊆ B ⇔ A ∩ B = ∅ ⇔ B ⊆ A ⇔ B\A = B
Ejemplo 7.
i) Para A = {a, b, c} y B = {b, s}, A\B = {a, c}.
ii) Si A = {a, y}, B = {b, x}, A\B = A = {a, y} (obsérvese que A ∩ B = ∅).
iii) Si A = {x, y} y B = {x, {y}, {x, z}}, A\B = {y}.
Definición 7. Una partición de A es una colección {A1 , A2 , . . . , An } de subconjuntos no vacíos

de A que verifica las dos propiedades siguientes:
[n
i) A = Ai ,
i=1
ii) Ai ∩ Aj = ∅, para todo i, j ∈ {1, 2, . . . , n}, i 6= j.
Ejemplo 8.
i) Sea B = {a, b, c, 2, 3, 4, 6, 7, 8}. Una partición de B es {A1 , A2 , A3 , A4 } donde:
A1 = {a, 2, 8}, A2 = {b, c}, A3 = {3, 4, 6}, A4 = {7}.
ii) Una partición de Z es {A1 , A2 , A3 } donde:
A1 = {n ∈ Z | n > 0}, A2 = {n ∈ Z | n < 0}, A3 = {0}.
iii) Otra partición de Z es {A1 , A2 } donde:
A1 = {n ∈ Z | n es par}, A2 = {n ∈ Z | n es impar}.
iv) La familia {A1 , A2 } donde:
A1 = {n ∈ Z | n ≤ 0}, A2 = {n ∈ Z | n ≥ 0}
no es una partición de Z pues A1 ∩ A2 6= ∅.
2.3. PRODUCTO CARTESIANO 39
2.3 Producto Cartesiano

Definición 8. Dados dos conjuntos A y B, se llama producto cartesiano de A por B, y se
denota A × B, al conjunto constituido por pares ordenados de elementos, el primero perteneciente
al conjunto A y el segundo al conjunto B. Esto es:
A × B = {(a, b) | a ∈ A ∧ b ∈ B}
Ejemplo 9. El producto cartesiano A × B de los conjuntos A = {1, 2, 3} y B = {a, b} es el

conjunto:
A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
B
(1, b) (2, b) (3, b)

b
(1, a) (2, a) (3, a)
a
1 2 3 A
Representación gráfica de A × B
Cuando sea posible, es útil representar gráficamente el producto cartesiano por medio de
diagramas de coordenadas cartesianas. Para ello se toman dos rectas OX y OY , perpendiculares,
de forma que el punto O es la intersección de ambas. Este punto recibe el nombre de origen,
la recta OX es el eje de abscisas y la OY es el eje de ordenadas. El conjunto A se representa
linealmente en OX, y el B en OY . Los elementos (a, b) de A × B se representan por puntos
resultantes de la intersección de la paralela a OY por a con la paralela a OX por b. En la figura
anterior se muestra la representación en coordenadas cartesianas del ejemplo dado.
Dos pares ordenados (a, b) y (c, d), elementos del producto cartesiano A × B, son iguales si
a = c y b = d. Es claro que, en general, A × B 6= B × A.
Se puede extender la definición de producto cartesiano a n conjuntos.
Definición 9. Dados n conjuntos A1 , A2 , . . . , An se define su producto cartesiano como:
A1 × A2 × · · · × An = {(a1 , a2 , . . . , an ) | ai ∈ Ai , ∀ i = 1, 2, . . . , n}
Cuando A1 = A2 = · · · = An = A, se suele usar la notación:
An = A × · · · × A =
Finalmente, si A1 , A2 , . . . , An son conjuntos finitos, también lo es A1 × A2 × · · · × An y se tiene

que:
|A1 × A2 × · · · × An | = |A1 | · |A2 | · . . . · |An |
2.4 Aplicaciones. Tipos de aplicaciones

El concepto de aplicación (función) es de gran importancia en Informática. Una función es el
modo más natural de implementar la correspondencia entre los datos y el resultado de un proceso
de cálculo en un ordenador. Los llamados lenguajes funcionales como HASKELL, se fundamentan
en este concepto y suelen identificar programa y función.
Definición 10. Sean A y B dos conjuntos no vacíos. Una aplicación f de A en B es una regla
que asocia a cada elemento a de A un único elemento de B que se denomina imagen por f de a
y se denota f (a).
El conjunto A se llama conjunto inicial, y el B conjunto final. La relación entre a y su imagen,
f (a), se suele representar de la forma:
f : A −→ B
a f (a) = b
Ejemplo 10.
A B
x
1
y
2
z
3
t
Aplicación entre conjuntos
B A
A x 1 B
1 x
y 2
2 y
z 3
3 z
t 4
No es aplicación porque al 2 No es aplicación porque 3 no tiene

se le asignan dos elementos de B asignado ningún elemento de B
Se suele denominar función a la correspondencia f : A → B si A y B son conjuntos de números.

Con frecuencia, se utiliza la letra x para denotar los elementos del conjunto inicial de f , y la letra
y para los elementos del conjunto final.
Dos aplicaciones f : A → B y g : C → D son iguales si A = C, B = D y f (a) = g(a), para
cualquier elemento a de A.
2.4. APLICACIONES. TIPOS DE APLICACIONES 41
Definición 11. Sea f : A → B una aplicación y sean A1 ⊆ A y B1 ⊆ B, dos subconjuntos de A

y B respectivamente. Se define la imagen por f del conjunto A1 como:
f∗ (A1 ) := {f (a) ; a ∈ A1 } ⊆ B
y la imagen recíproca por f del conjunto B1 como:

f ∗ (B1 ) := {a ∈ A ; f (a) ∈ B1 } ⊆ A
Si tomamos como A1 = A, el conjunto f∗ (A) = Im(f ) se denomina conjunto imagen.
Ejemplo 11. Sea f : A = {1, 2, 3} → B = {x, y, z, t} la aplicación representada en el ejemplo 10,

es decir, por f (1) = x, f (2) = z, f (3) = z. Es claro que
f∗ ({1}) = {x}, f∗ ({2}) = {z}, f∗ ({2, 3}) = {z}, f∗ ({1, 2}) = {x, z},
y, por otro lado,
f ∗ ({x, y}) = {1}, f ∗ ({x, z}) = A, f ∗ ({t, y}) = ∅, f ∗ ({z}) = {2, 3}.
Definición 12. Se dice que una aplicación f : A → B es:
i) inyectiva si elementos distintos de A tienen imágenes diferentes en B, esto es:
∀ a1 , a2 ∈ A [a1 6= a2 → f (a1 ) 6= f (a2 )] es verdadera
o, equivalentemente,
∀ a1 , a2 ∈ A [f (a1 ) = f (a2 ) → a1 = a2 ] es verdadera
ii) sobreyectiva si todo elemento de B es imagen de, al menos, un elemento de A, es decir:
∀b ∈ B ∃a ∈ A [b = f (a)] es verdadera
o, equivalentemente, Im(f ) = B.
iii) biyectiva o biunívoca si es inyectiva y sobreyectiva.

B A
A x 1 B
1 x
y 2
y
2
z 3
3 z
t 4
Aplicación
Aplicación inyectiva sobreyectiva

y no sobreyectiva y no inyectiva
A B
x A B
1
y 1 x
2
z 2 y
3
t 3 z
Aplicación no
inyectiva y no Aplicación biyectiva
sobreyectiva
Ejemplo 12.
i) f : N × N → N definida por f (n, m) = n · m, para cada (n, m) ∈ N × N, no es una función

inyectiva pues f (0, 3) = f (5, 0) = 0. La función f es sobreyectiva ya que para cada n ∈ N el
elemento (1, n) ∈ N × N verifica que f (1, n) = 1 · n = n. Además:
f ∗ ({5}) = {(1, 5), (5, 1)},

f ∗ ({6}) = {(1, 6), (6, 1), (3, 2), (2, 3)},
f ∗ ({2, 4}) = {(1, 2), (2, 1), (2, 2), (4, 1), (1, 4)}.
ii) Sea A = {a, b, c, d}, la función f : P(A) → Z+ = {n ∈ Z | n ≥ 0} definida por f (X) = |X|,
para cada X ∈ P(A), no es inyectiva (f ({a, b}) = f ({c, d}) = 2) ni sobreyectiva (f ∗ ({5}) =
∅).
iii) La función f : R+ → R definida por f (x) = log2 x, para cada x ∈ R+ es biyectiva.
Proposición 1. Si los conjuntos A y B son finitos y f : A → B es una aplicación entre ellos, se

verifica que:
• Si f es inyectiva entonces |A| ≤ |B|

(equivalentemente, si |A| > |B|, entonces f no es inyectiva).
2.5. COMPOSICIÓN DE APLICACIONES. APLICACIÓN INVERSA 43
• Si f es sobreyectiva, entonces |A| ≥ |B|

(equivalentemente, si |A| < |B|, entonces f no es sobreyectiva).
• Si f es biyectiva entonces |A| = |B|

(equivalentemente, si |A| =
6 |B|, entonces f no es biyectiva).
Conviene destacar que, si bien no todas las aplicaciones que se pueden definir entre conjuntos
con el mismo cardinal son biyectivas, siempre es posible encontrar una aplicación biyectiva entre
ellos.
Además, se verifica el siguiente resultado que será de utilidad en la práctica:
Proposición 2. Si A y B son dos conjuntos finitos con el mismo cardinal y f : A → B es una

aplicación entre ellos, son equivalentes:
i) f es inyectiva ii) f es sobreyectiva iii) f es biyectiva

Demostración. Si A = {a1 , . . . , an }, entonces f∗ (A) = {f (a1 ), . . . , f (an )} y, al ser f inyectiva,

|f∗ (A)| = |A| = |B|. Puesto que f∗ (A) ⊆ B y tienen el mismo cardinal, es obvio que f∗ (A) = B 1 ,
es decir f es sobreyectiva. Recíprocamente, si f es sobreyectiva y f (a1 ) = f (a2 ) con a1 6= a2 ,
entonces |f∗ (A)| < |A| = |B|, lo que contradice la sobreyectividad de f .
2.5 Composición de aplicaciones. Aplicación inversa

Definición 13. Dados tres conjuntos A, B y C, y dos aplicaciones f y g tales que
f : A −→ B g : B −→ C
a −→ f (a) = b b −→ g (b) = c
se llama composición de f con g a la aplicación:
g ◦ f : A −→ C
a −→ (g ◦ f ) (a) = g (f (a)) = g (b) = c
es decir:
g◦f
f g
A B C
a f (a) g(f (a)) = (g ◦ f )(a)
Ejemplo 13. Sea A = {1, 2, 3, 4, 5} y sean f, g : A → A las aplicaciones definidas por
f (1) = f (2) = f (3) = f (4) = f (5) = 1

g(1) = 5, g(2) = 4, g(3) = 3, g(4) = 2 y g(5) = 1.
1
Si A es un conjunto finito y B ⊆ A es un subconjunto de A, se cumple que B = A si, y sólo si, |B| = |A|.
Es evidente que
(g ◦ f )(a) = g(f (a)) = 5 y (f ◦ g)(a) = f (g(a)) = 1, para todo a ∈ A.
Por lo tanto, g ◦ f 6= f ◦ g.
La composición de aplicaciones tiene la propiedad asociativa, es decir, dadas tres aplicaciones
f : A −→ B, g : B −→ C y h : C −→ D :
h ◦ (g ◦ f ) = (h ◦ g) ◦ f
Proposición 3. Sean f : A → B y g : B → C dos aplicaciones cualesquiera. Se verifica que:

• Si f y g son inyectivas, también lo es g ◦ f
• Si f y g son sobreyectivas, también lo es g ◦ f
• Si f y g son biyectivas, también lo es g ◦ f
Demostración. Si f y g son inyectivas y a1 , a2 son dos elementos de A tales que (g ◦ f )(a1 ) =

(g◦f )(a2 ), entonces g(f (a1 )) = g(f (a2 )) (por definición de composición). Puesto que g es inyectiva,
se verifica que f (a1 ) = f (a2 ) y, la inyectividad de f permite concluir que a1 = a2 .
La demostración de las otras dos afirmaciones es un sencillo ejercicio.
Definición 14. Se llama aplicación identidad a una aplicación IA de A a A de la forma:
IA : A −→ A
a −→ IA (a) = a
Es inmediato comprobar que dada cualquier aplicación f : A → B se verifica que
f ◦ IA = f = IB ◦ f
Definición 15. Sea f : A → B una aplicación. Se llama aplicación inversa de f , y se denota
por f −1 , a una aplicación f −1 : B → A tal que, si b es un elemento de B,
f −1 (b) = a ⇐⇒ b = f (a)
Puede que no exista una aplicación inversa de f .
Proposición 4. Dada una aplicación f : A → B, f admite inversa si, y sólo si, f es biyectiva.
Además, si f tiene inversa entonces
• su inversa f −1 es la única aplicación que verifica f ◦ f −1 = IB y f −1 ◦ f = IA
• f −1 también tiene inversa y (f −1 )−1 = f
• Si f : A → B y g : B → C son dos aplicaciones invertibles (es decir, tienen inversa),
entonces g ◦ f también lo es y (g ◦ f )−1 = f −1 ◦ g −1
Ejemplo 14.
i) f : Z → Z definida por f (n) = n + 2, para cada n ∈ Z, es biyectiva, su inversa es g : Z → Z
definida por g(m) = m − 2 para cada m ∈ Z.
ii) La función f : R → R+ definida por f (x) = 2x , para cada x ∈ R es biyectiva, su inversa es
la función g : R+ → R definida por g(y) = log2 y.
2.6. RELACIONES 45
R
C
B
(2, b)
b
R
(1, a) (3, a)
a
1 2 3 A
Figura 2.1: R ⊂ A × B Figura 2.2: C ⊂ R × R
2.6 Relaciones
El concepto de relación está presente en distintas situaciones de nuestra vida cotidiana. Por
ejemplo, existe una relación entre el nombre de un alumno, la titulación en la que está matriculado
y la nota media de dicho alumno. También existe una relación entre una línea aérea, el número
de vuelo, el punto de partida, el destino, la hora de salida y la hora de llegada de un vuelo. Estas
relaciones involucran elementos de varios conjuntos y son muy utilizadas para representar bases
de datos informáticas.
Definición 16. Sean A1 , A2 , . . . , An conjuntos. Una relación R sobre A1 , A2 , . . . , An es cualquier

subconjunto del producto cartesiano A1 × · · · × An , es decir,
R ⊆ A1 × · · · × An
Nos centraremos en el caso n = 2. Dados dos conjuntos A y B, una relación binaria de A

en B es un subconjunto cualquiera R del producto cartesiano A × B. Si el par ordenado (a, b)
pertenece a R, se dice que a está relacionado con b, y se denota por aRb. Dado un conjunto A,
se llama relación binaria en A a cualquier subconjunto R ⊆ A × A.
Ejemplo 15.
i) Para los conjuntos A = {1, 2, 3} y B = {a, b}, R = {(1, a) , (2, b) , (3, a)} es una relación
binaria de A en B
R ⊆ A × B = {(1, a) , (1, b) , (2, a) , (2, b) , (3, a) , (3, b)}.
En la Figura 2.1 se muestran mediante puntos los elementos de A × B, y mediante círculos

los de R.
ii) Un ejemplo de relación en A = R es C = {(x, y) ∈ R × R | x2 + y 2 = r2 }, siendo r un

número real positivo. En la Figura 3.2 se representa el conjunto R en cada eje cartesiano y
1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
A A
B B
C C
ä
D D
c
ä
E E
ä
F F
c
G G
ä
H H
ä
I I
c
J J
Figura 2.3: Tablero de una partida de Figura 2.4: Flota de barcos (F) y tor-
barcos: X × Y . pedos disparados (T ) en un tablero de
barcos (X × Y ).
toda la superficie del papel en la que se encuentran los ejes constituye el producto cartesiano
R × R = R2 . Los elementos de la relación C son los puntos de ese plano que verifican la
ecuación que la caracteriza. En la figura, esos puntos se encuentran sobre la línea que forma
una circunferencia de radio r.
iii) Sea A un conjunto de ciudades con aeropuerto. Una relación R ⊆ A × A es el conjunto
formado por los pares (a, b) ∈ A × A definido por
(a, b) ∈ R si, y sólo si, existe un vuelo directo entre a y b.
iv) El estado de una partida de un juego de barcos se determina habitualmente en un tablero

cuadrado de 100 casillas, ordenadas en 10 filas y 10 columnas numeradas respectivamente
del 1 al 10 y de la A a la J, tal como se muestra en la Figura 2.3. Si llamamos X al conjunto
de las filas del tablero e Y al de las columnas, las casillas del tablero son pares ordenados de
la forma (x, y) ∈ X × Y .
La situación de la flota de barcos en el tablero puede considerarse como una relación F ⊂
X × Y . En concreto, los barcos que se muestran en el tablero de la Figura 2.4, constituyen
la relación:
F = {(B, 2) , (B, 3) , (B, 4) , (E, 8) , (F, 8) , (G, 8) , (H, 3) , (H, 4) , (H, 5)}
Por otra parte, los sucesivos intentos de hundir la flota, indicados mediante torpedos, cons-
tituyen otra relación T :
T = {(D, 6) , (E, 2) , (F, 8) , (H, 5) , (I, 9)}
Los impactos que los torpedos han producido en los barcos, son la relación intersección entre
ambas: I = F ∩ T = {(F, 8), (H, 5)}.
2.6. RELACIONES 47
2.6.1 Propiedades de una relación binaria

Una relación binaria R en un conjunto A se dice que es:
i) Reflexiva si
∀a ∈ A, aRa
ii) Simétrica si
∀a1 , a2 ∈ A (a1 Ra2 ⇔ a2 Ra1 )
iii) Antisimétrica si
∀a1 , a2 ∈ A [(a1 Ra2 ) ∧ (a2 Ra1 ) =⇒ a1 = a2 ]
iv) Transitiva si
∀a1 , a2 , a3 ∈ A [(a1 Ra2 ) ∧ (a2 Ra3 ) =⇒ a1 Ra3 ]
Ejemplo 16.
i) Para A = {1, 2, 3}
(a) R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2)} no es reflexiva, pues (3, 3) ∈
/ R1 , sí es
simétrica y no es transitiva, pues (3, 2) ∈ R1 y (2, 3) ∈ R1 pero (3, 3) ∈ / R1 .
(b) R2 = {(1, 1), (2, 2), (1, 2), (3, 3), (2, 3)} es reflexiva, no es simétrica (porque (1, 2) ∈ R2
pero (2, 1) ∈
/ R2 ), sí es antisimétrica y no es transitiva (porque (1, 2) ∈ R2 y (2, 3) ∈ R2
pero (1, 3) ∈
/ R2 ).
(c) R3 = {(2, 2), (1, 2), (2, 1), (2, 3)} no es reflexiva (ya que (3, 3) ∈
/ R3 ), no es simétrica
(porque (2, 3) ∈ R3 pero (3, 2) ∈ / R3 ), tampoco es antisimétrica (pues (1, 2), (2, 1) ∈ R3
pero 1 6= 2) y no es transitiva (porque (1, 2), (2, 3) ∈ R3 pero (1, 3) ∈/ R3 ).
(d) R4 = {(1, 1), (2, 2)} es simétrica, antisimétrica y transitiva, pero no reflexiva.
ii) En el conjunto de los números naturales, la relación ≤ “ser menor o igual que” es reflexiva,
antisimétrica y transitiva. También lo es en los conjuntos Z, Q y R,
iii) Dado cualquier conjunto A, la relación de inclusión en el conjunto P(A)
R ⊆ P(A) × P(A), (X, Y ) ∈ R ⇐⇒ X ⊆ Y
es reflexiva, antisimétrica y transitiva.

iv) Dados dos números enteros x e y, se dice que x divide a y si existe un número entero m
tal que y = x · m (se denota por x|y). Es fácil comprobar que la relación R = {(x, y) ∈
Z×Z ; x|y} es reflexiva y transitiva. Cuando la restringimos a un subconjunto A de números
enteros del mismo signo, es decir A ⊆ Z+ o A ⊆ Z− , verifica además la propiedad anti-
simétrica.
v) En el conjunto de personas que asisten a una fiesta, se define la relación A R B si, y sólo si,
A y B tienen la misma edad. La relación R es reflexiva, simétrica y transitiva.
2.6.2 Representación de relaciones binarias

Hay varias formas de representar una relación entre conjuntos finitos. Una de ellas es enumerar
sus pares ordenados como en Ejemplo 15 i) y Ejemplo 16 i). Otra forma importante de representar
relaciones binarias en conjuntos finitos es con grafos dirigidos2 . Intuitivamente, un grafo dirigido
de una relación binaria en A, consiste en dibujar tantos puntos (vértices) como elementos tenga
A y, para a, b ∈ A, una flecha de a a b si (a, b) ∈ R o, lo que es lo mismo, si aRb.
a
b
)•
• aR b
En el grafo se visualizan las distintas propiedades de la relación. Por ejemplo, la relación es
reflexiva si, y sólo si, existe un lazo (flecha que une un punto consigo mismo) en cada vértice; la
relación es simétrica si entre cada dos vértices distintos existen dos flechas (en distinto sentido)
o no existe ninguna, y es antisimétrica si entre cada dos vértices distintos existe una flecha o no
existe ninguna.
b
5•
•f &•
• a b 8•
a •
a c
aRb ⇔ bRa
aR a
[a R b ∧ b R c] ⇒ a R c
Ejemplo 17. Se considera en el conjunto A = {a, b, c, d} la relación binaria R dada por los pares
R = {(a, a), (a, b), (a, c), (b, a), (b, b), (c, c), (c, d), (d, b), (d, c), (d, d)};
podemos representar R de la forma siguiente:
a b) p
• f •O
•< f )•|
c d
2.6.3 Relaciones de equivalencia

Definición 17. Una relación R en un conjunto A se dice que es una relación de equivalencia
si satisface las propiedades reflexiva, simétrica y transitiva.
A partir de ahora utilizaremos el símbolo ∼ para referirnos a una relación de equivalencia.

Las relaciones de equivalencia son importantes porque nos permiten agrupar los elementos del
conjunto A en clases.
2
La teoría de grafos será tratada en detalle en el tema 4. Incluímos aquí los grafos dirigidos para poder hablar
de los diagramas de Hasse.
2.6. RELACIONES 49
Definición 18. Sea ∼ una relación de equivalencia en un conjunto A. Se llama clase de equi-
valencia del elemento a ∈ A, y se denota por [a], al conjunto de elementos relacionados con
a:
[a] = {x ∈ A ; x ∼ a}
Ejemplo 18.
i) En A = {1, 2, 3, 4, 5}, R = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (2, 1), (3, 4), (4, 3)} es una
relación de equivalencia cuyas clases de equivalencia son
[1] = {1, 2} = [2], [3] = {3, 4} = [4], [5] = {5}
ii) En Z, la relación
a ≡2 b ⇐⇒ a − b es un múltiplo de 2
es una relación de equivalencia. La relación de equivalencia ≡2 divide a los elementos del

conjunto Z en dos clases de equivalencia, P = {los números pares} e I = {los números
impares}.
iii) La relación anterior se puede generalizar considerando cualquier entero positivo m y definiendo:
a ≡m b ⇐⇒ a − b es un múltiplo de m ⇐⇒ a − b = λ · m; λ ∈ Z
Veamos que también es una relación de equivalencia:

- Reflexiva: Para cada a ∈ Z se verifica que a − a = 0 = 0 · m; 0 ∈ Z
- Simétrica: Si a y b son enteros cualesquiera tales que a ≡m b, entonces a−b = λ·m; λ ∈ Z,
de lo que se deduce que b − a = (−λ) · m; −λ ∈ Z y, por lo tanto, b ≡m a.
- Transitiva: Si a, b y c son enteros cualesquiera tales que a ≡m b y b ≡m c, entonces existen
enteros λ, β tales que a − b = λ · m y b − c = β · m. Si se suman miembro a miembro ambas
ecuaciones, se obtiene que a − c = (λ + β) · m y, entonces, a ≡m c.
Un número entero x pertenece a la clase de equivalencia [r] (0 ≤ r ≤ m − 1) si r es el resto
de la división de x entre m.
En esta relación hay m clases de equivalencia, [0], [1], . . . , [m − 1].
x ∈ [a] ⇐⇒ x ≡m a ⇐⇒ x − a = λ · m; λ ∈ Z ⇐⇒ x = a + λ · m; λ ∈ Z
Por ejemplo, para m = 3

[0] = {. . . , −9, −6, −3, 0, 3, 6, 9, . . .} = [−3] = [3]
[1] = {. . . , −8, −5, −2, 1, 4, 7, 10, . . .} = [−2] = [4]
[2] = {. . . , −7, −4, −1, 2, 5, 8, 11, . . .} = [−1] = [5]
iv) En el ejemplo v) de la pág. 47 cada clase de equivalencia la forman las personas de la misma
edad:
[a] = {b | b es una persona en la fiesta con la misma edad que a}.
En estos ejemplos puede observarse que dos elementos que están relacionados determinan
la misma clase de equivalencia y, por tanto, una clase de equivalencia puede representarse por
cualquiera de sus elementos. Además, las clases de equivalencia de dos elementos que no están
relacionados son conjuntos disjuntos. Esto se verifica para cualquier relación de equivalencia:
Propiedades 4. Sea ∼ una relación de equivalencia en un conjunto A y sean a1 , a2 ∈ A. En-

tonces:
i) a1 ∼ a2 ⇐⇒ [a1 ] = [a2 ]
ii) a1 6∼ a2 ⇐⇒ [a1 ] ∩ [a2 ] = ∅.
Demostración.
i) Si a1 ∼ a2 y x ∈ [a1 ], entonces x ∼ a1 y a1 ∼ a2 , nos permiten deducir que x ∼ a2 (propiedad

transitiva), es decir x ∈ [a2 ]. Recíprocamente, si las clases coinciden, entonces a1 ∈ [a1 ] = [a2 ], es
decir a1 ∼ a2 .
ii) Si a1 6∼ a2 y x ∈ [a1 ] ∩ [a2 ], entonces a1 ∼ x y x ∼ a2 , por tanto a1 ∼ a2 , lo que contradice
la hipótesis de partida. El recíproco es análogo.
De estas propiedades se deduce el siguiente teorema.
Teorema 1. Sea ∼ una relación de equivalencia en un conjunto A, A 6= ∅. La familia de las

distintas clases de equivalencia es una partición de A.
Demostración. Una partición debe ser una familia de conjuntos no vacíos. Esta condición se
satisface por ser ∼ reflexiva con lo que a ∈ [a] para todo a ∈ A. La primera propiedad de
partición se satisface ya que a ∈ [a] para cada elemento de A. Por lo tanto, la unión de todas las
clases de equivalencia contiene todos los elementos de A. La segunda propiedad de una partición,
la que exige que los miembros de la familia sean disjuntos dos a dos, se deduce inmediatamente
del apartado ii) de Propiedades 4.
Definición 19. Dada una relación de equivalencia ∼ definida en un conjunto A, se llama con-
junto cociente de A respecto a la relación ∼, y se denota por A/ ∼, al conjunto cuyos elementos
son las clases de equivalencia determinadas en A por ∼.
Ejemplo 19. Si consideramos la relación de equivalencia vista en el Ejemplo 18 i), el conjunto

cociente A/R es
A/R = {[1], [3], [5]} = {[2], [4], [5]} = {{1, 2}, {3, 4}, {5}} ⊆ P(A)
Para la relación de equivalencia vista en el Ejemplo 18 ii) y iii), el conjunto cociente Z/ ≡m

tiene m elementos. Este conjunto se denota por Zm y recibe el nombre de conjunto de las clases
de restos módulo m. Por ejemplo:
Z2 = {[0], [1]}, Z3 = {[0], [1], [2]}, Z7 = {[0], [1], [2], [3], [4], [5], [6]}.
2.6. RELACIONES 51
Se verifica también que:

Dada una partición de un conjunto A, puede definirse en él una relación de equivalencia R tal
que el conjunto cociente A/R coincida con la partición dada. Por ejemplo, en A = {a, b, c, d} la
partición {{a, b, c}, {d}} determina la relación de equivalencia
R = {(a, a), (b, b), (c, c), (a, b), (b, a), (a, c), (c, a), (b, c), (c, b), (d, d)}
que cumple A/R = {{a, b, c}, {d}}.

2.6.4 Relaciones de orden

Muchos conjuntos tienen un orden natural en sus elementos. Probablemente el ejemplo más
familiar es el conjunto de los números reales ordenados por su “magnitud”: estamos acostumbrados
a afirmaciones como 3 ≤ π, x2 > 0 para todo x ∈ R distinto de cero, etc.
Definición 20. Una relación binaria 4 en A se dice relación de orden si verifica las propiedades
reflexiva, antisimétrica y transitiva. El par (A, 4) recibe el nombre de poset.
Ejemplo 20. El par (Z+ , | ) es un poset ya que la relación de divisibilidad en el conjunto de

enteros positivos Z+ es de orden. Sin embargo, el par (Z+ , <) no es un poset ya que < no es
reflexiva.
Una relación de orden 4 en un conjunto A es de orden total si dados dos elementos cua-
lesquiera a, b de A, siempre se pueden comparar, es decir, o se cumple a 4 b o se cumple b 4 a.
Un ejemplo de orden total es la relación ≤ en N, Z, Q o R, mientras que las relaciones de inclusión,
⊆, y de divisibilidad, |, no son de orden total: 3 - 2 y 2 - 3 y {a} * {b} y {b} * {a}.
Ejemplo 21. Orden Lexicográfico. Sea (L, 4), donde L es un conjunto finito y 4 una relación
de orden total en L, y sea L∗ el conjunto de las palabras de longitud finita que se pueden formar con
los elementos de L. El orden de L se extiende a un orden total en L∗ , llamado orden lexicográfico
(orden del diccionario), de la forma siguiente:
Sean l1 l2 . . . lp y l10 l20 . . . lq0 elementos de L∗ , l1 l2 . . . lp 4 l10 l20 . . . lq0 si se cumple:
a) para algún k < p, se tiene que li = li0 (con i = 1, . . . , k), lk+1 4 lk+1 0 0
, lk+1 6= lk+1 (por
ejemplo, lámina y lápiz), o
b) p ≤ q y li = li0 , para i = 1, . . . , p (por ejemplo, orden y ordenar).
2.6.5 El diagrama de Hasse de un poset finito (A, 4)

Un diagrama de Hasse de una relación de orden sobre un conjunto A es una representación
simplificada del grafo de la relación. Se representan los elementos del conjunto A por vértices y
se tiene en cuenta que no se deben dibujar las flechas que se deducen de las propiedades de la
relación. En concreto:
- puesto que la relación es reflexiva, se sabe que cada elemento está relacionado consigo mismo y
se simplifica el grafo no dibujando los lazos;
- transitiva: se sabe que si x 4 z y z 4 y, entonces x 4 y; por ello, en ese caso, se omite la flecha
que va desde x hasta y (es decir, se dibuja una arista del vértice x al vértice y si x 4 y y no existe
otro elemento z ∈ A tal que x 4 z y z 4 y).
Además se adopta el convenio de leer el diagrama de abajo hacia arriba, con lo cual no es necesario
dirigir las aristas. De esta forma, un par de elementos distintos de A están relacionados si, y sólo
si, existe un camino ascendente entre sus correspondientes vértices del diagrama de Hasse.
Ejemplo 22. A continuación se muestra el grafo dirigido y el correspondiente diagrama de Hasse

de la relación “ser divisor” en el conjunto A = {1, 2, 3, 4}:
•? O 4 • 4
2 •_ •? 3 2 • • 3
•] 1 •
1
Ejemplo 23. Consideremos el poset (P ({1, 2, 3}), ⊆). Un grafo dirigido que representa esta
relación de orden y su diagrama de Hasse son los siguientes:
, r
{1, 2, 3}
9 G O e
{1, 2, 3}
_

{1,O 2}
[ e
{1,
9 H
3}e v {2,
9 C O
3} {1, 2} {1, 3} {2, 3}
{1}U e {2} s 9 {3}U {1} {2} {3}

O
∅X ∅
2.6.6 Elementos distinguidos en un poset

Hemos visto que el conjunto R de números reales con el orden ≤ es un poset. Algunos subconjuntos
de los números reales ordenados de este modo tienen un elemento “mayor” y otros no, de igual
modo un elemento “menor” y otros no. Por ejemplo, el subconjunto Z de los números enteros no
tiene ni mayor ni menor elemento; el conjunto de los enteros positivos Z+ = {1, 2, 3, 4, . . .} tiene
menor elemento, el 1, pero no mayor elemento.
2.6. RELACIONES 53
Podemos comprobar que cualquier subconjunto finito de R tiene un menor elemento y un

mayor elemento con respecto al orden ≤. Esto no siempre sucede en todo poset finito. Por
ejemplo, consideremos el conjunto de todos los subconjuntos B de {a, b, c} tales que B ⊂ {a, b, c}
ordenados por la inclusión ⊆; el elemento menor es el ∅, sin embargo no existe un “mayor” elemento.
Formalizamos esta idea con la siguiente definición.
Definición 21. Sea (P, 4) un poset.
i) Un elemento a ∈ P es un elemento maximal de P si no existe x ∈ P tal que a 4 x y a 6= x
(es decir, no hay elementos en P “estrictamente mayores” que a). Equivalentemente, para
todo x ∈ P , si a 4 x entonces a = x.
a maximal de P ⇐⇒ ¬∃x ∈ P [a 4 x ∧ a 6= x] ⇐⇒ ∀x ∈ P [a 4 x → a = x]
ii) Un elemento b ∈ P es un elemento minimal de P si no existe x ∈ P tal que x 4 b y x 6= b

(es decir, no hay elementos en P “estrictamente menores” que b). Equivalentemente, para
todo x ∈ P , si x 4 b entonces x = b.
b minimal de P ⇐⇒ ¬∃x ∈ P [x 4 b ∧ x 6= b] ⇐⇒ ∀x ∈ P [x 4 b → x = b]
iii) Un elemento M ∈ P es máximo de P si x 4 M , para todo x ∈ P

M es máximo de P ⇐⇒ ∀x ∈ P , x 4 M
iv) Un elemento m ∈ P es mínimo de P si m 4 x, para todo x ∈ P

m es mínimo de P ⇐⇒ ∀x ∈ P , m 4 x
Proposición 5. Se verifican los siguientes enunciados:

i) El máximo, si existe, es único.
ii) El mínimo, si existe, es único.
iii) Si P es finito, P tiene máximo si, y sólo si, tiene un único maximal.
iv) Si P es finito, P tiene mínimo si, y sólo si, tiene un único minimal.
Ejemplo 24. Sea A = {2, 3, 4, 5, 6, 7, 8} ordenado por la relación de divisibilidad: x 4 y si, y sólo
si, x divide a y. El conjunto A tiene cuatro elementos minimales, 2, 3, 5, 7 (si x ∈ A y x divide a
2 entonces x = 2; análogamente para 3, 5 y 7) y tiene cuatro elementos maximales, 5, 6, 7, 8 (si
5 divide a x entonces x = 5; análogamente para 6, 7 y 8). Sin embargo, A no tiene máximo ni
mínimo.
6• •8
3• •4
5• •2 •7
Ejemplo 25. En el conjunto P = {1, 2, 3, 4, 5, 6, 8, 10, 12, 20}, se considera la relación de divisi-
bilidad cuya representación en diagrama de Hasse es la siguiente
12• •8 •20
6• •4 •10
3• •2 •5
•1
El conjunto P tiene tres maximales, 8, 12 y 20, no tiene por lo tanto máximo; en cambio su
mínimo es 1.
Definición 22. Sea (P, 4) un poset y sea Q un subconjunto de P .
i) Un elemento s ∈ P es una cota superior de Q en P si q 4 s, para cualquier q ∈ Q.
ii) Un elemento f ∈ P es una cota inferior de Q en P si f 4 q, para cualquier q ∈ Q.
iii) Un elemento S ∈ P es supremo de Q en P si S es una cota superior de Q en P y, si S 0

es otra cota superior de Q en P , entonces S 4 S 0 .
iv) Un elemento I ∈ P es ínfimo de Q en P si I es una cota inferior de Q en P y, si I 0 es

otra cota inferior de Q en P , entonces I 0 4 I.
Se puede comprobar que, si el conjunto de cotas superiores de Q en P es no vacío, entonces el

supremo es el mínimo de dicho conjunto. Igualmente, si el conjunto de cotas inferiores de Q en P
es no vacío, entonces el ínfimo es el máximo de dicho conjunto.
Proposición 6. Se verifican los siguientes enunciados:
i) El supremo de Q, si existe, es único.
ii) El ínfimo de Q, si existe, es único.
iii) Existe el máximo de Q si, y sólo si, existe el supremo y este es un elemento de Q.
iv) Existe el mínimo de Q si, y sólo si, existe el ínfimo y este es un elemento de Q.
Ejemplo 26. Tomenos el conjunto P del Ejercicio 25 y consideremos el subconjunto Q = {1, 2, 4, 10}
de P
2.6. RELACIONES 55
12• •8 •20
Q Q
•4 •10
6• •4 •10
•2
3• •2 •5
•1 •1
Es fácil ver que Q no tiene máximo porque tiene dos maximales, 4 y 10. La única cota superior
de Q en P es 20, por lo tanto es el supremo de Q en P . Por otro lado, el único minimal de Q es
1, también es mínimo de Q e ínfimo de Q en P .
Consideremos, ahora el subconjunto Q0 de P dado por Q0 = {2, 3, 8, 10}.

12• •8 •20
•8
Q0
6• •4 •10 Q0
•10
3• •2 •5
3• •2
•1
Como vemos, Q0 tiene a 3 por maximal y minimal a la vez; 2 es minimal, 8 y 10 son maximales
de Q0 . La única cota inferior de Q0 en P es 1 y, por tanto, es ínfimo. Por otro lado, no hay cotas
superiores de Q0 en P .

GCED Tema 2 2020 21

Cargado por

Copyright:

Formatos disponibles

GCED Tema 2 2020 21

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

GCED Tema 2 2020 21

Cargado por

Copyright:

Formatos disponibles

GCED.

Conjuntos, Aplicaciones y Relaciones

• F. Aguado, F. Gago, M. Ladra, G. Vega, C. Vidal, A. Vieites Problemas Resueltos de

• R.P. Grimaldi, Matemática Discreta y combinatoria: capítulos 3, 5 y 7.

• S.S. Epp, Matemáticas Discretas con aplicaciones: capítulos 6, 7 y 8.

pertenece al conjunto A, y se escribirá a ∈ A; en caso contrario, se dirá que el elemento no

que los determina. Por ejemplo

{0, 2, 4, 6, 8} y {n ∈ N | n es un número par no negativo menor que 10}

representan el mismo conjunto.

ii) B = {x ∈ Z | x2 ≤ 16} = {0, 1, 2, 3, 4, −1, −2, −3, −4};

iii) C = {x ∈ N | x divide a 20} = {1, 2, 4, 5, 10, 20};

[1, 3, 5] 6= [1, 5, 3]; [1, 3, 5] 6= [1, 1, 3, 5] 6= [1, 3, 3, 5]

Un conjunto A es finito si tiene un número n ∈ N de elementos; este número se llama cardinal

i) Son conjuntos finitos:

• A = {1, 2, a, c}, |A| = 4;

ii) Son conjuntos no finitos:

• el conjunto formado por los números naturales pares, {n ∈ N | n es par};

Si A ⊆ B diremos que A está incluido o contenido en B.

• Cualquier conjunto B, siempre admite como subconjuntos al conjunto vacío ∅ y al propio

• Si A ⊆ B y A 6= B, se dice que A está contenido estrictamente en B y se denota A ⊂ B.

Inclusión de conjuntos mediante diagramas de Venn: A ⊆ B

ii) ∅ ⊆ {a, b, c, {a, b, c}}; vi) {a, b, c} ∈ {a, b, c, {a, b, c}};

Si A y X son dos conjuntos cualesquiera, se verifica que

Si X es finito y tiene cardinal n entonces P(X) es finito y tiene cardinal |P(X)| = 2n .

ii) {2} ∈ P(Z);

A = {a, b, c} es un conjunto finito

Cuando, en un contexto determinado, consideremos varios conjuntos, estos se considerarán

2.2 Operaciones con conjuntos. Propiedades

Definición 3. Dado un conjunto U y un subconjunto A ⊆ U se llama complementario (respecto

Obsérvese que la propiedad que determina al complementario de A es la negación de la

Propiedades 1. Dado un conjunto U y A, B ⊆ U , se verifican las siguientes propiedades:

Definición 4. Dados dos conjuntos A y B se llama

• intersección de A y B, y se representa por A ∩ B, al conjunto formado por los elementos

Unión de conjuntos: A ∪ B Intersección de conjuntos: A ∩ B

i) Si A = {a, x} y B = {b, x}, entonces A ∪ B = {a, b, x} y A ∩ B = {x}.

ii) Si A = {a, y} y B = {b, x}, entonces A ∪ B = {a, b, x, y} y A ∩ B = ∅.

iii) Si A = {a, b, c} y B = {a, b, c, m}, entonces A∪B = {a, b, c, m} = B y A∩B = {a, b, c} = A,

(nótese que A ⊆ B).

Propiedades 2. Para cualesquiera conjuntos A, B y C, subconjuntos de U , se verifica:

iii) La unión y la intersección son conmutativas:

iv) La unión y la intersección son asociativas:

v) La unión es distributiva respecto a la intersección, y viceversa:

Definición 5. Se extiende la definición de unión y de intersección para una colección finita

Además se verifica que : ∪ni=1 Ai = ∩ni=1 Ai y ∩ni=1 Ai = ∪ni=1 Ai .

Ejemplo 6. Consideremos los siguientes subconjuntos de Z:

Definición 6. Dados dos conjuntos A y B se llama diferencia entre A y B, y se representa por

Diferencia de conjuntos A\B

Observemos que A\B = A ∩ B. Además, se verifica que

Definición 7. Una partición de A es una colección {A1 , A2 , . . . , An } de subconjuntos no vacíos

ii) Ai ∩ Aj = ∅, para todo i, j ∈ {1, 2, . . . , n}, i 6= j.

2.3 Producto Cartesiano

Ejemplo 9. El producto cartesiano A × B de los conjuntos A = {1, 2, 3} y B = {a, b} es el

(1, b) (2, b) (3, b)

Definición 9. Dados n conjuntos A1 , A2 , . . . , An se define su producto cartesiano como:

Cuando A1 = A2 = · · · = An = A, se suele usar la notación:

Finalmente, si A1 , A2 , . . . , An son conjuntos finitos, también lo es A1 × A2 × · · · × An y se tiene

2.4 Aplicaciones. Tipos de aplicaciones

Aplicación entre conjuntos