Mathematics">
Conjuntos Relaciones y Funciones
Conjuntos Relaciones y Funciones
Conjuntos Relaciones y Funciones
Funciones
0.1 Conjuntos
A, B, C, . . .
a, b, c, . . . .
A = {1, 2, 3, 4}.
1
Otra forma de especificar los elementos de un conjunto es dando una regla.
Por ejemplo:
A = {a : a es un entero y 1 ≤ a ≤ 4}
(A = B) ←→ [(∀ x , x ∈ A −→ x ∈ B) ∧ (∀ x , x ∈ B −→ x ∈ A)]
(A = B) ←→ (∀ x , x ∈ A ←→ x ∈ B).
Ejemplo
2
Los siguientes conjuntos son usualmente empleados en matemática:
N = {x : x es un número entero x ≥ 1}
= {1, 2, 3, 4, . . .} (Conjunto de los números naturales)
Z = {x : x es un entero }
= {. . . , −2, −1, 0, 1, 2, . . .} (Conjunto de los números enteros)
x
Q = { : x, y ∈ Z, y 6= 0}
y
4 3 2 1 0 1
= {. . . , − , − , − , − , , , . . .} (Conjunto de los números racionales)
3 2 1 1 2 3
R = {x : x es número real }.
A⊆B ó B ⊇ A.
En simbolos:
A ⊆ B ←→ (∀ x , x ∈ A −→ x ∈ B).
Si A no es subconjunto de B, se escribe A * B.
Note que A ⊆ A. Si A ⊆ B pero A 6= B se dice que A es un subconjunto
propio de B, y se escribe
A⊂B ó B ⊃ A.
A⊂
/ B.
3
Es posible tener un conjunto sin elementos. Por ejemplo, el conjunto de
todos los estudiantes que miden 6 metros. Tal conjunto se llama conjunto
vacı́o y se denota ∅. En simbolos:
∅ = {x : p(x) ∧ ¬p(x)}
A ∪ B = {x : x ∈ A ∨ x ∈ B}.
A ∩ B = {x : x ∈ A ∧ x ∈ B}.
B r A = {x : x ∈ B ∧ x∈/ A}.
✤✜
✤✜
✣✢
✣✢
A B
4
A∩B
✤✜
✤✜
✣✢
✣✢
A B
A∪B
✤✜
✤✜
✣✢
✣✢
A B
ArB
★✥
B C
✧✦
✧✦
A
✧✦
5
Bc = A ; BrA=B ; C ∩D =D ; C*D;
DrC =∅ ; D⊆C ; D⊂C ; Dc ⊇ A ;
P(D) = {∅, {1}, {3}, {1, 3}} ; 1*D ; 1∈D ; A∪C =A∪D ;
∅ ∈ P(D) ; {1} ∈ P(D) ; 1∈/ P(D).
Comentarios
6
la semana siguiente, seamos capaces de entenderla. De lo contrario, debemos
incluir mayores detalles.
Note que la demostración comienza: “Sea a ∈ A”. Este es otro ejemplo
del uso de una variable “fija pero arbitraria”. Se asume que a es un elemento
de A pero nada más.
Observemos que en “Sea a ∈ A”estamos en realidad incluyendo dos casos,
uno de los cuales no hemos mencionado. Cuando se dice “Sea a ∈ A”,
estamos asumiendo que A 6= ∅. ¿Qué sucede si A = ∅? La razón de lo anterior
es que si A = ∅ la demostración es trivial. En efecto, ∅ es subconjunto de
cualquier conjunto, en particular de B. Ası́, cada vez que escribamos algo de
la forma :
“Sea a ∈ A”
A − B = A ∩ Bc.
7
Teorema 7 Si A, B, C son conjuntos con A ⊆ B y B ⊆ C entonces A ⊆ C.
A ⊆ B ←→ A ∩ B = A.
8
Suponga que existe y ∈ A ∩ (B − A). Entonces y ∈ A y y ∈ B − A. Pero
y ∈ B − A implica que y ∈ B y y ∈
/ A. Ası́, se tiene que y ∈ A y y ∈
/ A, una
contradicción. Esto completa la prueba.
P := {x ∈ D : p(x) es verdadero }.
Ejemplos
b) Sea D = R, p(x) : “x2 − 3x + 2 = 0”y q(x) : “ sin2 (x) + cos2 (x) = 1”.
Entonces
P = {1, 2} Q=R
(Verificación: Ejercicio).
9
Se pueden usar las operaciones entre conjuntos para expresar los conjuntos
de validez de funciones proposicionales compuestas. Ası́, por ejemplo, si P ,
Q corresponden a los conjuntos de validez de funciones proposicionales p, q
respectivamente, entonces
P ∩ Q = {x : p(x) ∧ q(x)},
P ∪ Q = {x : p(x) ∨ q(x)},
P c = {x : ¬p(x)},
(p −→ q) ⇐⇒ (¬p ∨ q)
entonces se ve que
P c ∪ Q = {x : ¬p(x) ∨ q(x)}
Ejemplos
P ∪ Q = D.
10
ii) El conjunto de validez de p(x) ∧ q(x) es:
P ∩ Q = ∅.
P c ∪ Q = {1, 3, 5}.
Rc = {1, 4, 5, 6}.
(x − 2)(x − 1) > 0.
P1 = (2, ∞)
P2 = (1, ∞)
P3 = (−∞, 2)
P4 = (−∞, 1).
(P1 ∩ P2 ) ∪ (P3 ∩ P4 ),
11
esto es :
(Verificación: Ejercicio).
0.3 Relaciones
Sabemos que un conjunto está determinado por sus elementos; esto es, {a, b} =
{b, a} y que el orden en el cual los elementos aparecen no hace diferencia.
En ocasiones, deseamos distinguir cuando los mismos elementos están
puestos en orden diferente. Para hacer esto introducimos el concepto de par
ordenado.
Es posible realizar lo anterior en términos de conjuntos (ver lista de ejer-
cicios), sin embargo esta definición no es muy útil, de manera que conside-
raremos un par ordenado como un término indefinido. La notación será
estándar:
(a, b)
Definición 11 Sean (a, b), (c, d) pares ordenados. Entonces (a, b) = (c, d)
si y sólo si a = c y b = d.
Note que la definición anterior distingue orden: (a, b) 6= (b, a) a menos que
a = b.
Con el concepto de par ordenado, se puede definir una nueva operación
entre conjuntos: El producto cartesiano de dos conjuntos:
12
Definición 12 Sean A, B conjuntos. El producto cartesiano de A con B,
denotado A × B; es el conjunto de todos los pares ordenados con primer
elemento en A y segundo elemento en B. En simbolos:
A × B = {(a, b) : a ∈ A y b ∈ B}.
A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
B × A = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}
A×C = ∅
B × C = ∅.
1 2 3
A
Observe en este ejemplo que A × B 6= B × A y que A × C = B × C no implica
que A = B.
aRb.
13
La imagen de R (denotado por Im(R)) es el conjunto de todos los segundos
elementos de R; en simbolos
1 2 3
A
donde cada elemento de este arreglo es un elemento de A × A y, (1, 3), (2, 3)
y (1, 2) son los pares ordenados de la relación R.
En este ejemplo: Dom(R) = {1, 2}, Im(R) = {2, 3}.
Antes de seguir adelante con la teorı́a, veremos una serie de ejemplos para
fijar ideas.
14
b) Sea A = R. Para x, y ∈ R definimos
xRy si y sólo si y = x2 .
xRy si y sólo si x = y.
Entonces R es una relación en A. Los pares ordenados son de la forma (x, x),
Dom(R) = A y Im(R) = A.
BRC si y sólo si B ⊆ C.
R = {(∅, ∅), (∅, {1}), (∅, {2}), (∅, A), ({1}, {1}), ({1}, A), ({2}, {2}), ({2}, A), (A, A)}
15
f) Sea A = {1, 2, 3}, B = {1, 2}. Entonces R = {(3, 1), (3, 2)}, S = ∅,
T = A × B son todas relaciones de A en B.
x|y ←→ ∃z ∈ Z ∋ y = xz.
16
k) Para x, y ∈ N se define xRy si y sólo si 5|(x − y). Entonces R es una
relación en N con Dom(R) = Im(R) = N (Verificación: Ejercicio).
Entonces:
R no es reflexiva, no es simétrica, no es transitiva, es antisimétrica, es
irreflexiva, no es completa, es asimétrica.
17
S no es reflexiva, no es simétrica, es transitiva, no es antisimétrica, no es
irreflexiva, no es completa, no es asimétrica.
T es reflexiva, es simétrica, es transitiva, es antisimétrica, no es irreflexiva,
no es completa, no es asimétrica.
1 2 3 4
A
1 2 3 4
A
18
≤ y ⊆ : son ordenes parciales.
< y ⊂ : son ordenes parciales estrictos.
≤ : es un orden total.
< : es un orden total estricto.
19
Como un ejemplo de compuestas de relaciones, sean
y
R = {(1, a), (1, b), (3, a)} , S = {(a, 5), (b, 4), (a, 6), (c, 6)}.
Ası́, S ◦ R = {(1, 5), (1, 4), (3, 5), (1, 6), (3, 6)}.
IA = {(x, x) : x ∈ A}.
Ejemplo Sea A = {1, 2, 3} y R la relación en A dada por R = {(1, 2), (1, 3), (2, 3)}.
Entonces
a) R−1 = {(2, 1), (3, 1), (3, 2)}.
b) IA = {(1, 1), (2, 2), (3, 3)}.
c) R−1 ◦ R = {(1, 1), (1, 2), (2, 2), (2, 1)}.
20
d) R ◦ R−1 = {(2, 2), (2, 3), (3, 3), (3, 2)}.
e) R ◦ R = {(1, 3)}.
f) R−1 ◦ R−1 = {(3, 1)}.
g) R ◦ IA = IA ◦ R = {(1, 2), (1, 3), (2, 3)}.
h) R−1 ◦ IA = IA ◦ R−1 = {(2, 1), (3, 1), (3, 2)}.
R ◦ R−1 6= R−1 ◦ R,
una relación de A en B, y
una relación de B en C.
Lo anterior se puede mostrar con un diagrama:
✬✩✬✩✬✩
✫✪✫✪✫✪
Algunos cálculos muestran que:
a) S ◦ R = {(1, 2), (1, 3), (3, 2), (3, 3), (2, 2)}.
b) R−1 = {(4, 1), (5, 1), (6, 2), (4, 3)}.
c) S −1 = {(2, 4), (3, 4), (2, 6)}.
d) R−1 ◦ S −1 = {(2, 1), (3, 1), (2, 3), (2, 2), (3, 3)}.
e) (S ◦ R)−1 = {(2, 1), (3, 1), (2, 3), (3, 3), (2, 2)}.
Se observa que R ◦ S y S −1 ◦ R−1 no están definidos y que R−1 ◦ S −1 =
(S ◦ R)−1 .
21
A fin de practicar un poco más con demostraciones, veremos que esta
última igualdad es siempre verdadera.
(S ◦ R)−1 = R−1 ◦ S −1 .
✬✩✬✩✬✩
A B C
✫✪✫✪✫✪
22
Definimos las siguientes relaciones
✬✩✬✩✬✩✬✩
✫✪✫✪✫✪✫✪
y
T ◦ S = {(4, 1), (4, 4), (6, 6)} una relación de B en D.
y
(T ◦ S) ◦ R = {(1, 1), (1, 4), (3, 6)} una relación de A en D.
T ◦ (S ◦ R) = (T ◦ S) ◦ R.
23
Se deja la demostración del resultado anterior como un ejercicio, ası́ como
la del siguiente:
Si definimos
Si = {x : xRi} , i ∈ N,
se tiene
Gráficamente
N
24
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
.. .. .. .. ..
. . . . .
S1 S2 S3 S4 S5
Ejemplos
25
a) Sea A un conjunto no vacı́o. Entonces Π1 = {{x} : x ∈ A} y Π2 = {A}
son particiones de A. En cierto sentido, Π1 es la partición “más fina”de A
mientras que Π2 es la partición “menos fina”.
b) Sea A = {1, 2, 3, 4}. Entonces Π1 = {{1}, {2, 3}, {4}} y
Π2 = {{1, 4}, {2, 3}} son particiones de A.
c) Con respecto a los conjuntos Si de la introducción, se observa que
{S1 , S2 , S3 , S4 , S5 } es una partición de N.
26
Como otros ejemplos, sea A un conjunto no vacı́o y R la relación de igualdad:
xRy si y sólo si x = y. Sea S = A×A (también una relación de equivalencia).
Entonces, para cada x ∈ A:
Demostración.
27
Se deja como ejercicio probar que [y]R ⊆ [x]R .
Demostración. Ejercicio.
Hemos visto que una relación de equivalencia induce una partición del
conjunto. Este proceso también trabaja en reversa, esto es, una partición de
un conjunto induce una relación de equivalencia en el conjunto.
A|Π2 = {(1, 1), (1, 4), (4, 1), (4, 4), (2, 2), (2, 3), (3, 3), (3, 2)}.
28
R es reflexiva: Sea x ∈ A. Como x es un elemento de algún bloque de Π,
se tiene xRx. Luego, R es reflexiva.
0.5 Funciones
29
Si f es una función de A en B entonces la “propiedad funcional”de cada
x ∈ A relacionado a exactamente un y ∈ B permite el uso de la notación
funcional
y = f (x).
A = {1, 2, 3, 4} , B = {1, 2, 3, 4, 5}
f = {(1, 2), (2, 3), (3, 4), (4, 5)}
g = {(1, 2), (1, 3), (2, 4), (3, 5), (4, 5)}
h = {(1, 1), (2, 2), (3, 3)}.
30
Observe que se usa “la”cuando se habla de imagen y se usa “una”cuando
se habla de preimagenes ya que un elemento de B puede tener varios elemen-
tos de A relacionados.
Ya que f es una relación se puede hablar de su dominio e imagen, com-
poner f con otras relaciones y analizar su inversa.
Note que aunque Dom(f ) = A, no necesariamente es Im(f ) = B. De
esta manera es conveniente tener también un nombre para B. Usualmente
se le denomina codominio de f .
✫✪ ✫✪
31
(w, z) ∈ g y se tiene f ⊆ g. Intercambiando los roles de f y g se puede
mostrar que g ⊆ f de lo cual se obtiene que f = g.
✬✩✬✩ ✬✩✬✩
✫✪✫✪ ✫✪✫✪
✬✩✬✩ ✬✩✬✩
✫✪✫✪ ✫✪✫✪
Recordemos que ya que funciones son relaciones, ellas tienen inversas que
son relaciones. Ası́, podemos hablar de la inversa de cualquier función, pero
no hay razón para esperar que esta inversa sea también una función.
En este sentido las funciones biyectivas son importantes, ya que ellas son
exactamente aquellas funciones cuyas inversas son también funciones.
32
Teorema 30 Sea f : A → B una función. Entonces f −1 : B → A es una
función si y sólo si f es biyectiva.
33
composición de f y g.
Si (g ◦ f )(x) = z, entonces (x, z) ∈ (g ◦ f ), lo cual significa que existe
y ∈ B tal que (x, y) ∈ f y (y, z) ∈ g. Luego, f (x) = y y g(y) = z. Por lo
tanto, z = g(y) = g(f (x)) ó
(g ◦ f )−1 = f −1 ◦ g −1
34
Sea f : A → B. Una demostración directa para probar que f es 1-1
podrı́a tomar la siguiente forma: Sean x, y ∈ A con f (x) = f (y).
..
.
“Alguna cosa u otra dependiente de f ”
..
.
Ası́ x = y y f es 1-1.
Una demostración directa para mostrar que f es sobre, podrı́a ser: Sea
y∈B
..
.
“Algo dependiente de f ”
..
.
35
Primero una prueba directa que f es 1-1.
Sean x, y ∈ R con f (x) = f (y). Entonces ax + b = ay + b, lo cual implica
que ax = ay. Ya que a 6= 0, se tiene x = y y por lo tanto f es 1-1.
La demostración queda como ejercicio. Sin embargo note que la mayor parte
ya fué mostrada previamente.
36
Demostración.
a) y b) son fáciles de probar, pues si x ∈ A, entonces
y
(IB ◦ f )(x) = IB (f (x)) = f (x).
Para mostrar c), observemos primero que como f es biyectiva, f −1 es una
función, de modo que f (x) = y si y sólo si f −1 (y) = x.
Ahora, sea x ∈ A y sea y = f (x). Entonces
Si D ⊆ B entonces
f −1 (D) = {x : f (x) ∈ D}.
f (C) se llama la imagen de C y f −1 (D) la preimagen de D.
37
Teorema 35 Sea f : A → B y sean C ⊆ D ⊆ B. Entonces
f −1 (C) ⊆ f −1 (D).
a ∗ b = b ∗ a.
a ∗ (b ∗ c) = (a ∗ b) ∗ c.
38
c) Se dice que e ∈ A es una identidad para ∗ si y sólo si ∀ a ∈ A,
a ∗ e = e ∗ a = a.
d) Si e es una identidad para ∗ y x ∈ A se dice que x es invertible si y
sólo si ∃ y ∈ A ∋ x ∗ y = y ∗ x = e. El elemento “y” es llamado una inversa
de x.
e) Se dice que a ∈ A es idempotente para ∗ si y sólo si a ∗ a = a.
Ejemplos:
e = e ∗ e′ = e′ .
39
Demostración. Suponga que x ∈ A tiene y e y ′ como inversas. Entonces
x ∗ y = y ∗ x = e y x ∗ y ′ = y ′ ∗ x = e. Luego
y = y ∗ e = y ∗ (x ∗ y ′ ) = (y ∗ x) ∗ y ′ = e ∗ y ′ = y ′ .
40
0.6 Ejercicios
a) A ∪ B b) A ∩ (B ∪ C) c) C − A d) C ∪ Ac
e) (A ∪ C)c f) Ac ∩ C c g) P(B)
a) A ∪ ∅ = A b) A ∩ ∅ = ∅
c) A − ∅ = A d) A ∪ U = U
e) A ∩ U = A f) A ∪ Ac = U
g) A ∩ Ac = ∅ h) A − A = ∅
i) A − B ⊆ A j) A ∩ B ⊆ A
k) A ∪ B ⊇ A l) A ∩ B ⊆ A ∪ B
m) (Ac )c = A n) (A ∪ B)c = Ac ∩ B c
o) (A ∩ B)c = Ac ∪ B c p) A ∪ (B − A) = A ∪ B
q) (A ∪ B) − (A ∩ B) = (A − B) ∪ (B − A)
r) A − (B ∪ C) = (A − B) ∩ (A − C)
s) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
t) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
41
b) P(A) ∩ P(B) ⊆ P(A ∩ B)
c) P(A ∪ B) ⊆ P(A) ∪ P(B)
d) P(A ∩ B) ⊆ P(A) ∩ P(B)
e) P(A ∩ B) ⊆ P(A ∪ B).
a) A × (B ∪ C) = (A × B) ∪ (A × C)
b) A × (B ∩ C) = (A × B) ∩ (A × C)
c) (A × B) ∩ (Ac × B) = ∅
d) (A ⊆ B ∧ C ⊆ D) −→ A × C ⊆ B × D
e) A ∪ (B × C) = (A ∪ B) × (A ∪ C)
f) A ∩ (B × C) = (A ∩ B) × (A ∩ C)
g) (A × B) ∩ (C × D) = (A ∩ C) × (B ∩ D)
h) A × (B − C) = A × B − A × C
42
7. Se define el par ordenado (a, b) por: (a, b) = {{a}, {a, b}}. Demuestre
que con la definición anterior se tiene:
8. Sean A = {1, 2, 4}, B = {1, 3, 4}. Sean R = {(1, 3), (1, 4), (4, 4)} una
relación de A en B, S = {(1, 1), (3, 4), (3, 2)} una relación de B en A y
T = ∅ una relación de A en B. Encuentre:
g) S ◦ R h) R ◦ S.
m) R−1 n) S −1 .
o) IA p) IB .
q) R−1 ◦ S −1 r) S −1 ◦ R−1 .
s) (R ◦ S)−1 t) (S ◦ R)−1 .
u) T −1 v) IB−1 .
w) (R ◦ S) ◦ R x) R ◦ (S ◦ R).
a) Dom(S ◦ R) ⊆ Dom(R).
b) Im(S ◦ R) ⊆ Im(S).
43
10. Sean A = {1, 2, 3, 4, 5, 6} y Π = {{2, 4, 6}, {1, 5}, {3}}. Liste los ele-
mentos de A|Π. Encuentre [2]A|Π .
A = {1, 2, 3, 4}
B = {1, 2, 3}
Encuentre f −1 ◦ f .
Encuentre:
44