Teoría de Conjuntos PDF

Teor
a de Conjuntos
Lic. Dennis A. Redtwitz
FaCEN - UNA
Indice general
1. Teora Elemental de Conjuntos 5
1.1. Notaci on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.1. Conjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2. Subconjunto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2. Conjuntos especiales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.1. Conjunto vaco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.2. Conjunto universal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3. Operaciones unitarias y binarias . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.1. Interseccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3.2. Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3.3. Complemento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.3.4. Diferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.5. Diferencia simetrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.6. Conjunto de Partes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4. Diagramas de Venn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.5. Operaciones generalizadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.1. Interseccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
1.5.2. Union . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.6. Producto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6.1. Par ordenado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.6.2. Producto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.7. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2. Relaciones 31
2.1. Deniciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.1.1. Denicion conjuntista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.1.2. Representaci on gr aca . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.1.3. Relaciones binarias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.2. Relaciones de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2.1. Denicion y ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.2.2. Clases de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2.3. Particiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.3. Relaciones de orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3.1. Denicion y ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3.2. Diagramas de Hasse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.3.3. Cotas inferiores y elementos minimales . . . . . . . . . . . . . . . . . . . 43
2.3.4. Cotas superiores y elementos maximales . . . . . . . . . . . . . . . . . . 45
2.3.5.

Inmos y supremos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.3.6. Buen orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
2.4. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3
3. Funciones 53
3.1. Deniciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.1. Denicion conjuntista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.1.2. Representacion gr aca . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.2. Im agenes y preim agenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2.1. Imagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.2.2. Preimagen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.3. Composici on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.3.1. Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.3.2. Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.4. Clasicaci on de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4.1. Inyectividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4.2. Sobreyectividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.4.3. Biyectividad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.5. Funciones especiales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.6. Inversas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.6.1. Relaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.6.2. Inversas a la izquierda . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.6.3. Inversas a la derecha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.6.4. Inversas bilaterales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.7. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4. Sistema Axiomatico de Morse-Kelley 73
4
Captulo 1
Teora Elemental de Conjuntos
1.1. Notacion
1.1.1. Conjunto
Georg Cantor es el padre de la teora de conjuntos. Fue la primera persona en estudiar los
conjuntos como tales, y no solo sus aplicaciones (funciones, etc.). Describio la palabra conjunto
con las siguientes palabras:
Entenderemos por conjunto cualquier reunion M de objetos determinados x, bien distintos
de nuestra percepcion o de nuestro pensamiento (que son denominados elementos de M), en
un todo.
Estos conjuntos (salvo conjuntos especiales), denotaremos con letras may usculas y sus ele-
mentos, con letras min usculas. Por ejemplo, N es el tradicional signo utilizado para denotar el
conjunto de todos los n umeros naturales.
Para denotar que cierto elemento pertenece a un conjunto dado, utilizamos el signo de per-
tenencia . As, 1 N se lee 1 pertenece al conjunto de los n umeros naturales. En general
x M se lee x pertenece al conjunto M o, brevemente, x pertenece a M.
Tenemos dos maneras formales de denotar un conjunto especco: por extension o por
comprensi on.
Denotar un conjunto por extensi on consiste en enumerar cada uno de sus elementos
(potencialmente con puntos suspensivos si el conjunto es innito) entre llaves inglesas
y separando los elemetos por comas. Por ejemplo, 0, 1, 2, 3 denota el conjunto cuyos
unicos elementos son los n umeros naturales 0, 1, 2 y 3.
Por la denici on de conjunto, dos conjuntos son iguales si y solo si poseen los mismos
elementos, pero la denicion no menciona ning un tipo de orden entre los elementos. Esto
implica que los conjuntos 0, 1, 2, 3, 3, 2, 1, 0 y 1, 3, 0, 2 son todos iguales.
La denici on de conjunto menciona que los elementos deben ser distintos. As, el conjunto
0, 0, 1, 2, 3 no puede contener el 0 dos veces, de manera que este conjunto tambien es
igual al conjunto 0, 1, 2, 3.
Podemos denotar el mismo conjunto utilizando comprension, que consiste en mencionar
un conjunto al que estos elementos pertenecen (denominado conjunto universal), y
5
establecer una propiedad que re unen los elementos, y solamente ellos. Para la notaci on,
utilizamos el signo : que se lee tal que o tales que de la siguiente manera:
x N : x 3
Se lee el conjunto de todos los x en N tales que x es menor o igual a 3 o, brevemente,
el conjunto de todos los n umeros naturales que son menores o iguales a 3. Claramente,
este es el conjunto 0, 1, 2, 3.
Ejemplo 1.1.1 Cuatro maneras posibles de denir I como el conjunto de todos los n umeros
impares positivos son:
I = 1, 3, 5, 7, (por extension)
I = x N : x es impar (por comprension)
I = x N : (2[n) (por comprension)
I = 2x + 1 : x N (por comprension)
Las deniciones por comprension dicen esencialmente lo mismo, pues [ es el signo de divi-
sibilidad, de manera que (2[x) se lee 2 no divide a x, y todo n umero impar positivo puede
expresarse de la forma 2x + 1 con x N.
En la practica, a menudo usamos una manera bastante informal de denir I: Simplemente
decimos I es el conjunto de todos los n umeros impares positivos.
Ejemplo 1.1.2 Fuera del contexto, el conjunto universal no siempre se sobreentiende, de ma-
nera que omitirlo al denir un conjunto por comprension dejara lugar a ambig uedades. Si
denimos:
A = x N : x < 3
B = x Z : x < 3
tenemos que A = 0, 1, 2 mientras que B = , 2, 1, 0, 1, 2. Claramente, estos dos
conjuntos no son iguales, pues no poseen los mismos elementos. Es por esto que x : x <
3 carece de sentido, a no ser que estamos trabajando solamente con n umeros naturales y
sobreentendemos que el conjunto universal debe ser N.
1.1.2. Subconjunto
Denici on 1.1.3 Diremos que M
1
es un subconjunto de M
2
si todos los elementos de M
1
pertenecen tambien a M
2
. Usaremos la notacion M
1
M
2
. Diremos tambien que M
1
esta in-
cluido en M
2
o que M
1
es una parte de M
2
. En ocasiones, usaremos tambien la notacion
M
2
M
1
, y diremos que M
2
es un superconjunto de M
1
o que M
2
contiene a M
1
.
Por ejemplo, 1, 2, 3 1, 2, 3, 4, 0, 2, 4, 6 2, 4 y N Z. Sin embargo, 0, 1 ,
1, 2, 3, 4, pues 0 pertenece al primer conjunto, pero no al segundo.
Para denir conceptos como el de inclusion, haremos uso de los siguientes nueve smbolos:
( )
6
se lee no, se lee y, se lee o, se lee si ... entonces, se lee si y s olo si,
se lee para todo, se lee existe y usaremos los parentesis para agrupaciones.
Por ejemplo, para denir M
1
M
2
podemos usar la notaci on x, x M
1
x M
2
o equivalentemente x M
1
, x M
2
. Respectivamente, esto se lee para toda x, si x per-
tenece a M
1
entonces x pertenece a M
2
y para toda x en M
1
, (se tiene que) x pertenece a M
2
.
Mencionamos que dos conjuntos son iguales si poseen los mismos elementos. Esto podemos
representar simb olicamente as: M
1
, M
2
, M
1
= M
2
(x, x M
1
x M
2
). Esto se
lee para todo par de conjuntos M
1
y M
2
, M
1
y M
2
son iguales si y solo si para toda x, x
pertenece a M
1
si y solo si x pertenece a M
2
. Este ejemplo ilustra c omo utilizar los parente-
sis para evitar ambig uedades. Tambien podramos dar la denicion M
1
, M
2
, M
1
= M
2

(M
1
M
2
M
2
M
1
). Podemos omitir los parentesis y convenimos que la conjuncion ()
liga m as fuerte que las condicionales ( y ), igual que la multiplicacion liga m as fuerte
que la adici on. Mas adelante, veremos ejemplos de c omo se utilizan los demas smbolos.
Una propiedad muy importante de la inclusion es la transitividad:
Proposicion 1.1.4 A, B, C A B B C A C
Demostraci
on:
Sea x A arbitrario pero jo. Como x A y A B, concluimos que x B. Luego, como
B C, concluimos que x C. Acabamos de probar que x A, x C. Esto es la denici on
de A C.
//
(Las barras indican que la demostracion ha terminado.)
7
1.2. Conjuntos especiales
1.2.1. Conjunto vaco
Denici on 1.2.1 Un conjunto es vaco si no posee elementos.
Los conjuntos vacos tienen una propiedad muy particular: Estan incluidos en cualquier con-
junto.
Proposicion 1.2.2 Si A y B son conjuntos y A es vaco, entonces A B.
Demostraci
on:
Supongamos que la inclusion A B no es cierta. Tendramos que x A : x / B (se lee
existe un x en A tal que x no pertenece a B). Pero esto es imposible, pues A es vaco y ning un
x puede pertenecer a A. Luego, la inclusi on debe cumplirse.
//
Utilizando esta proposici on, podemos probar que existe un solo conjunto vaco.
Corolario 1.2.3 Existe un solo conjunto vaco.
Demostraci
on:
Supongamos que
1
y
2
son dos conjuntos vacos distintos. Por la proposici on anterior,
como
1
es vaco,
1

2
, y como
2
es vaco,
2

1
. La doble inclusi on prueba que
1
=
2
.
//
Este unico conjunto vaco indicaremos con el smbolo (la letra griega que tambien se
escribe o ). Podramos haber denido el conjunto vaco por extension o por comprensi on:
= o bien = x : x ,= x.
1.2.2. Conjunto universal
En la teora elemental de conjuntos, estamos obligados a trabajar con conjuntos universales.
El conjunto universal (o universo) es aquel al que pertenecen todos los elementos de interes.
Por ejemplo, si estamos investigando propiedades de los n umeros racionales, podemos tomar
Q como conjunto universal, y si estamos investigando propiedades de los triangulos, podemos
tomar el conjunto de todos los tri angulos como conjunto universal.
Aunque en el contexto generalmente no hay confusiones, el conjunto universal no siempre se
sobreentiende en la pr actica. En el caso de los n umeros racionales, podramos tomar R, y en el
caso de los triangulos, el conjunto de todos los polgonos como respectivos conjuntos universales.
En la teora, no hay confusiones posibles, pues s olo estudiamos las propiedades del conjunto
universal, sin preocuparnos de cual se trata. El conjunto universal, simbolizaremos con U. La
manera tradicional de denir el conjunto universal es U = x : x = x.
Parecido a las propiedades del conjunto vaco, se prueba la siguiente proposicion, cuya
demostraci on dejaremos como ejercicio al estudiante.
Proposicion 1.2.4 A, A U
8
1.3. Operaciones unitarias y binarias
1.3.1. Intersecci on
Denici on 1.3.1 La interseccion de dos conjuntos A y B es el conjunto de los elementos
comunes, y se denota con AB. Simbolicamente, AB = x : x Ax B. Si AB = ,
diremos que A y B son disjuntos.
Ejemplo 1.3.2 Consideremos los conjuntos A = 1, 2, 3, B = 2, 3, 4 y C = 4, 5. Las
intersecciones posibles son AB = 2, 3, B C = 4 y AC = . Notemos que A y C son
disjuntos, mientras que los otros pares no lo son.
De la denici on de intersecci on es inmediato que AB = BA. Para corroborar esta igualdad
y otras menos evidentes, podemos usar una herramienta parecida a las tablas de verdad de la
L ogica, que llamaremos tablas de pertenencia.
El primer paso es dibujar una tabla con columnas que representen la pertenecia de un
determinado elemento a los conjuntos involucrados A, B, A B y B A:
A B A B B A
Luego simbolizamos todos los casos posibles de pertenencia de un determinado elemento a los
conjuntos simples A y B. Hay cuatro casos posibles: un elemento puede pertenecer a A y a B,
a A pero no a B, a B pero no a A o a ninguno:
A B A B B A

/
/
/ /
Si un elemento pertenece o no a los conjuntos simples, determina por completo si pertenece a
los demas conjuntos. Completamos la tabla la por la:
A B A B B A

/ / /
/ / /
/ / / /
Como las columnas de A B y B A son identicas, tenemos que A B = B A.
La demostraci on de propiedades utilizando tablas no tiene que involucrar necesariamente
m as que un conjunto, y tambien puede involucrar conjuntos especiales (como ). Veamos que
A A = A y que A = :
A A A

/ /
A A
/ /
/ / /
9
Claramente s olo existe un caso posible para la pertenencia a .
Daremos a continuaci on la prueba de la asociatividad de la interseccion. Es decir, A, B, C,
(A B) C = A (B C). Incluiremos tambien A B y B C en la tabla, lo que facili-
tar a determinar si el elemento pertenece o no a (A B) C y A (B C).
A B C A B B C (A B) C A (B C)

/
/
/ /
/
/ /
/ /
/ / /

/ /
/ / /
/ / / /
/ /
/ / / /
/ / / /
/ / / / /

/ / / /
/ / / / /
/ / / / / /
/ / / /
/ / / / / /
/ / / / / /
/ / / / / / /
A partir de ahora, escribiremos simplemente A B C, pues, gracias a la asociatividad, no
hay confusiones prosibles.
Vale mencionar que el principio fundamental del conteo del an alisis combinatorio revela que
si en una tabla intervienen n conjuntos simples, habr a 2
n
casos que considerar. Mientras mas
conjuntos intervienen, mas extensa se hace la prueba (con tan s olo 6 conjuntos, habra 2
6
= 64
casos). Con innitos conjuntos, es imposible construir una tabla completa.
Tambien podemos demostrar equivalencias utilizando tablas. Por ejemplo, si A y B son
conjuntos cualesquiera, A B si y s olo si A B = A. Comenzamos, como de costumbre,
haciendo una tabla con conjuntos A, B y A B, simbolizando todos los casos posibles. Para
probar la equivalencia, a nadimos las proposiciones A B y A B = A:
A B A B A B A B = A

/ /
/ /
/ / /
10
Luego, analizamos la veracidad de las proposiciones para un determinado elemento. La propo-
sici on A B es falsa si un elemento pertenece a A, pero no a B, de lo contrario es cierta, y
la proposici on A B = A es cierta si un elemento pertenece a ambos o a ninguno de los dos
conjuntos. Llenamos la tabla:
A B A B A B A B = A
V V
/ / F F
/ / V V
/ / / V V
Como las columnas de las proposiciones coinciden, son equivalentes. Esto demostro la siguiente
Proposicion 1.3.3 A, B, A B A B = A
Las tablas no son la unica manera de demostrar teoremas. De hecho, mientras m as conjuntos
y proposiciones intervienen en una proposici on, m as extensa se hace su demostracion. Demos-
traremos la siguiente proposici on sin utilizar tablas.
Proposicion 1.3.4 A, B, C, A B A C A B C
Demostraci
on:
Sean A, B y C conjuntos arbitrarios pero jos, y supongamos que A B A C. Para
cualquier x A, tenemos que x B (pues A B) y x C (pues A C). As, x B C.
Acabamos de probar que x A, x B C. Esto es la denicion de A B C.
//
1.3.2. Uni on
Denici on 1.3.5 La union de dos conjuntos A y B es el conjunto de los elementos de ambos
conjuntos, y se denota con AB. Simbolicamente, AB = x : x Ax B. La union se
dice disjunta si A y B son disjuntos. Para hacer enfasis en el hecho que la union es disjunta,
utlizaremos la notacion A
B (el punto indica que que se trata de union disjunta).

Ejemplo 1.3.6 Consideremos los conjuntos A = 1, 2, B = 2, 3 y C = 3, 4, 5. Las
uniones posibles son AB = 1, 2, 3, B C = 2, 3, 4, 5 y AC = 1, 2, 3, 4, 5. Como A y
C son disjuntos, podemos escribir A
C en vez de A C. A
B no tiene sentido, pues A y B

no son disjuntos.
La uni on posee, igual que la intersecci on, la propiedad conmutativa (A B = B A) y la
propiedad asociativa ((AB) C = A(BC)). Las demostraciones son muy similares a las
de la interseccion, y las dejaremos a cargo del estudiante.
Como la multiplicacion es distributiva sobre la adici on (a (b + c) = a b + a c), la uni on
tambien es distributiva sobre la intersecci on. Lo probaremos utilizando tablas:
A B C B C A (B C) A B A C (A B) (A C)

/ /
/ /
/ / /
/
/ / / / / /
/ / / / / /
/ / / / / / / /
11
Esto demostro la siguiente
Proposicion 1.3.7 A, B, C, A (B C) = (A B) (A C)
Obviamente, la distribuci on puede hacerse tambien por la derecha, ya que intersecci on y uni on
son conmutativas.
Podramos usar tablas para demostrar la siguiente proposici on, pero la tabla tendra 16
las. La demostraremos como corolario de la proposici on anterior.
Corolario 1.3.8 A, B, C, D, (A B) (C D) = (A C) (B C) (A D) (B D)
Demostraci
on:
Para facilitar la lectura de la demostraci on, tomaremos E = A B. As, aplicando la pro-
posicion anterior, tenemos que (A B) (C D) = E (C D) = (E C) (E D) =
((AB)C)((AB)D). Aplicando, de nuevo, la proposicion anterior a ambos miembros de
la interseccion, tenemos que (AB)C = (AC)(BC) y que (AB)D = (AD)(BD).
Reemplazando, queda (AB) (C D) = ((AC) (BC)) ((AD) (BD)). Como la
intersecci on es asociativa, podemos omitir los parentesis innecesarios. As, (AB) (CD) =
(A C) (B C) (A D) (B D).
//
Dejaremos la prueba de la siguiente proposicion y su corolario como ejercicio al estudiante:
Proposicion 1.3.9 A, B, C, A (B C) = (A B) (A C)
Corolario 1.3.10 A, B, C, D, (A B) (C D) = (A C) (B C) (A D) (B D)
1.3.3. Complemento
Fijado un conjunto universal, podemos denir el complemento de un conjunto respecto al
conjunto universal.
Denici on 1.3.11 El complemento de un conjunto A es el conjunto de todos los elementos
que no pertenecen a A, y se denota con A
c
(las notaciones

A y C(A) tambien son comunes).
Simbolicamente, A
c
= x U : x / A.
En contraste a la interseccion y la union de conjuntos, el complemento de un conjunto no
depende unicamente de el, sino tambien de U.
Ejemplo 1.3.12 Consideremos el conjunto A = 0, 1, 2. Si U = N, A
c
= 3, 4, 5, 6, ,
mientras que si U = Z, A
c
= , 4, 3, 2, 1, 3, 4, 5, 6, . Es por ello que si el conjunto
universal no se sobreentiende, el complemento respecto a U suele denotarse A
c
U
(respectivamen-
te,

A
U
y C
U
(A)).
Analicemos el doble complemento de un conjunto utilizando tablas de pertenencia:
A A
c
(A
c
)
c
/
Para llenar la tabla, tengamos en cuenta la denici on de complemento que dice que un elemento
pertenece a A
c
si y s olo si no pertenece a A:
A A
c
(A
c
)
c
/
/
12
Aplicando esta misma regla al complemento de (A
c
)
c
, obtenemos:
A A
c
(A
c
)
c
/
/ /
Esto demostro la siguiente
Proposicion 1.3.13 A, (A
c
)
c
= A
La siguiente tabla ilustra dos casos muy particulares del complemento:
c
y U
c
:
U
c
U
c
/
Claramente, para y U s olo hay un respectivo caso posible; ning un elemento pertenece a y
todo elemento pertenece a U. Completemos la tabla:
U
c
U
c
/ /
Esto ilustra que
c
= U y que U
c
= .
Otro par de propiedades muy importante del complemento se conoce como Leyes de De-
Morgan. Demostraremos uno de ellos utilizando tablas:
A B A B (A B)
c
A
c
B
c
A
c
B
c

/
/
/ /
A B A B (A B)
c
A
c
B
c
A
c
B
c
/ /
/ /
/ /
/ / /
A B A B (A B)
c
A
c
B
c
A
c
B
c
/ / / /
/ / / /
/ / / /
/ / /
Esto demostr o la primera Ley de Morgan, y la segunda dejaremos como ejecicio al estudiante.
Proposicion 1.3.14 (Leyes de DeMorgan)
(1) A, B, (A B)
c
= A
c
B
c
(2) A, B, (A B)
c
= A
c
B
c
Similarmente debera cumplirse que (ABC)
c
= A
c
B
c
C
c
. De nuevo, en vez de elaborar
una tabla con 8 las, podemos demostrar esto como corolario de la proposici on anterior.
13
Corolario 1.3.15 A, B, C, (A B C)
c
= A
c
B
c
C
c
Demostraci
on:
Para facilitar la lectura de la demostraci on, tomaremos D = A B. As, aplicando asocia-
tividad y la proposici on anterior, tenemos que (A B C)
c
= ((A B) C)
c
= (D C)
c
=
D
c
C
c
= (A B)
c
C
c
= (A
c
B
c
) C
c
= A
c
B
c
C
c
.
//
Como ejercicio, el estudiante podr a probar las proposiciones (A B C)
c
= A
c
B
c
C
c
,
(A B C D)
c
= A
c
B
c
C
c
D
c
y (A B C D)
c
= A
c
B
c
C
c
D
c
.
1.3.4. Diferencia
Denici on 1.3.16 La diferencia entre dos conjuntos A y B es el conjunto de los elementos
del primer conjunto que no pertenecen al segundo, y se denota con A B. Simbolicamente,
A B = x A : x / B.
Por denici on, U A = A
c
.
Ejemplo 1.3.17 Consideremos los conjuntos A = 1, 2, 3, 4, 5, B = 2, 3 y C = 3, 4, 5.
Las diferencias posibles son A B = 1, 4, 5, B A = , A C = 1, 2, C A = ,
B C = 2 y C B = 4, 5. Observemos que la diferencia entre conjuntos, al igual que la
diferencia entre n umeros, no es conmutativa; es decir, en general, A B ,= B A.
Proposicion 1.3.18 A, B, A B = A B
c
Demostraci
on:
Basta observar la tabla:
A B A B B
c
A B
c
/ / /
/
/ / / /
/ / / /
//
La siguiente proposicion podra ser f acilmente demostrada utilizando tablas, pero practicaremos
un poco m as el metodo general de demostracion:
Proposicion 1.3.19
(1) A, B, C, (A B) C = A (B C)
(2) A, B, C, A (B C) = (A B) (A C)
(3) A, B, C, (A B) C ,= A (B C) (es decir, la diferencia no es asociativa)
Demostraci
on:
(1)
(A B) C = (A B
c
) C
c
proposici on 1.3.18
= A (B
c
C
c
) Asociatividad
= A ((B
c
)
c
(C
c
)
c
)
c
Ley de DeMorgan
= A (B C)
c
proposici on 1.3.13
= A (B C) proposici on 1.3.18
14
(2)
A (B C) = A (B C
c
)
c
proposici on 1.3.18
= A (B
c
(C
c
)
c
) Ley de DeMorgan
= A (B
c
C) proposici on 1.3.13
= (A B
c
) (A C) Distributividad
= (A B) (A C) proposici on 1.3.18
(3) Basta considerar los conjuntos A = 1, 2, B = 2 y C = 1. (AB)C = 1C = ,
mientras que A (B C) = A 2 = 1.
//
Los primeros dos apartados no son sucientes para probar el tercero, pues a pesar de ellos
podra tratarse de una equivalencia. La manera m as concreta de probar la existencia de ciertos
conjuntos es dando un ejemplo. Sin embargo, habra otro metodo para probar el tercer apartado
de la proposicion anterior: Construir una tabla para vericar que, en ciertos casos, (AB)C ,=
A (B C). Dejaremos esto como ejercicio al estudiante.
1.3.5. Diferencia simetrica
Denici on 1.3.20 La diferencia simetrica entre dos conjuntos A y B es el conjunto de los
elementos que pertenecen a exactamente uno de los conjuntos, y se denota con AB. Simboli-
camente, AB = (A B) (A B).
Como ya probamos que la intersecci on y la uni on son conmutativas, esto vale tambien para la
diferencia simetrica. Es decir, AB = BA.
Ejemplo 1.3.21 Consideremos los conjuntos A = 1, 2, 3, B = 2, 3, 4 y C = 3, 4, 5. Las
diferencias simetricas posibles son AB = 1, 4, AC = 1, 2, 4, 5 y BC = 2, 5.
Para poner en pr actica los conocimientos adquiridos, sugerimos que el estudiante demuestre
la siguiente proposici on, utilizando en cada apartado (excepto en el primero y el cuarto) los
resultados de los apartados anteriores.
Proposicion 1.3.22
(1) A, AA =
(2) A, B, C, (AB)C = A(BC) (Asociatividad)
(3) A, B, C, AB = AC B = C (Cancelacion)
(4) A, A = A
(5) A, B, AB = A = B
1.3.6. Conjunto de Partes
Denici on 1.3.23 El conjunto de partes de un conjunto A es el conjunto cuyos elementos son
todos los subconjuntos de A, y se denota con P(A). Simbolicamente, P(A) = P : P A.
La denicion hace obvio que los elementos de un cierto conjunto pueden ser, a su vez, conjuntos.
Si todos los elementos de un conjunto son conjuntos (como es el caso con el conjunto de partes),
se suele decir que el conjunto es una familia y sus elementos se denominan miembros.
15
Ejemplo 1.3.24 P() = , pues el unico subconjunto de es el mismo conjunto. P() no
es el conjunto vaco, pues posee un elemento (). Esto hace obvio la diferencia entre pertenecia
y subconjunto, pues , pero / .
Ejemplo 1.3.25 Consideremos los conjuntos A = 1, B = 1, 2 y C = 1, 2, 3. P(A) =
, A, P(B) = , 1, 2, B y P(C) = , 1, 2, 3, 1, 2, 1, 3, 2, 3, C. En gene-
ral, , M P(M), para cualquier conjunto M.
El principio fundamental del conteo del analisis combinatorio revela que si C tiene n ele-
mentos, P(C) tendra 2
n
elementos.
Entre las pocas propiedades que analizaremos del conjunto de partes, se destaca la de mono-
tona:
Proposicion 1.3.26 A, B, A B P(A) P(B)
Dejamos la demostracion como ejercicio al estudiante.
16
1.4. Diagramas de Venn
Una manera sencilla de representar gr acamente a conjuntos y a las relaciones y opera-
ciones entre ellos, son los diagramas de Venn: Dibujamos una gura cerrada (normalmente
un rect angulo) que representar a al universo. Dentro en este, dibujamos otras guras cerradas
(normalmente circunferencias o elipses) que representar an los conjuntos. El interior de estas
guras cerradas ser a la parte del universo en el que se sit uan los elementos de los conjuntos.
Figura 1.1: A
Para simbolizar que un conjunto est a incluido en otro, dibujamos su gura en el interior
de la otra, y para simbolizar que dos conjuntos son disjuntos, dibujamos sus guras de manera
que sean ajenas. Por ejemplo:
Figura 1.2: B A A C =
Para simbolizar una operaci on, podemos sombrear la parte del universo que corresponde a
esta operacion. Por ejemplo:
Figura 1.3: A
c
17
Figura 1.4: A B
Figura 1.5: A B
Figura 1.6: A B
Figura 1.7: AB
18
Adem as, si los conjuntos son nitos, podemos representar cada uno de sus elementos como
un punto. Esto puede ser util para determinar operaciones. Por ejemplo:
Figura 1.8: Operaciones binarias
De la gura anterior, se deduce que A = 1, 2, 3, 4, 7, 8, B = 1, 4, 5, 6, 9, AB = 1, 4,
A B = 1, 2, 3, 4, 5, 6, 7, 8, 9, A B = 2, 3, 7, 8 y AB = 2, 3, 5, 6, 7, 8, 9
19
1.5. Operaciones generalizadas
1.5.1. Intersecci on
Denici on 1.5.1 Sea F una familia. La (gran) interseccion de F es el conjunto de los elemen-
tos que pertenecen a todos los miembros de la familia, y se denota con
MF
M o simplemente
F. Simbolicamente,
MF
M = x : M F, x M.
La variable M en la denici on de la intersecci on es muda. Es decir,
MF
M =
XF
X.
Observemos que la interseccion que denimos en la seccion 1.3.1 es un caso particular de
la gran interseccion, pues para dos conjuntos A y B cualesquiera, tenemos que:
M{A,B}
M = x : M A, B, x M = x : x A x B = A B
Ejemplo 1.5.2 Consideremos la familia F = 1, 1, 2, 1, 2, 3. La gran interseccion de
F es
MF
M = 1, pues el 1 es el unico elemento com un de los tres miembros de F.
Ejemplo 1.5.3 La denicion de la gran interseccion recien nos es util al tratar con innitos
miembros. Como ejemplo, consideremos la familia F = n, n + 1, n + 2, : n N =
1, 2, 3, , 2, 3, 4, , 3, 4, 5, , . Supongamos que alg un n
MF
M. Claramente,
n debe ser un n umero natural, pues todos los miembros de la familia son subconjuntos de N.
Pero al ser un n umero natural, n / n + 1, n + 2, n + 3, F, contradiciendo la denicion
de interseccion. Esto prueba que ning un elemento puede pertenecer a la interseccion. Es decir,
MF
M = .
La siguiente proposici on enumera las propiedades m as resaltantes de la gran interseccion. Como
las familias son potencialmente innitas, no podemos recurrir a las tablas para su demostracion.
Proposicion 1.5.4 Sean F y G familias arbitrarias.
(1) Si X F, entonces
MF
M X.
(2) Si X es tal que M F, X M, entonces X
MF
M.
(3) Si X F es tal que M F, X M, entonces
MF
M = X.
(4) Si G F, entonces
MF
M
MG
M.
(5)
MFG
M =
MF
M
MG
M
20
Demostraci
on:
(1) Sea a
MF
M arbitrario pero jo. Por denici on, M F, a M. Como, en particular,
X F, tenemos que a X. Acabamos de probar que a
MF
M, a X. Esto es la
denici on de
MF
M X.
(2) Sean a X y M F arbitrarios pero jos. Como a X M, tenemos que a M.
Siendo M F arbitrario esto prueba que M F, a M. Esto prueba que a
MF
M.
Acabamos de probar que a X, a
MF
M. Esto es la denicion de X
MF
M.
(3) Este apartado es consecuencia inmediata de los dos anteriores.
(4) Sea a
MF
M arbitrario pero jo. Por denici on, M F, a M.
Sea M G arbitrario pero jo. Como G F, tenemos que M F, lo que implica que
a M. Esto prueba que a
MG
M. Acabamos de probar que a
MF
M, a
MG
M.
Esto es la denici on de
MF
M
MG
M.
(5) Como F y G son subconjuntos de F G, dos aplicaciones del apartado anterior reve-
lan que
MFG
M
MF
M y que
MFG
M
MG
M. Luego, por la proposicion 1.3.4,
MFG
M
MF
M
MG
M, y s olo nos resta probar la inclusi on inversa.
Sea a
MF
M
MG
M arbitrario pero jo. Por denici on de intersecci on, a
MF
M y
a
MG
M, y por denicion de gran interseccion, M F, a M y M G, a M.
Sea M F G arbitrario pero jo. Por denici on de uni on, M F o M G, y en ambos
casos tenemos que a M. Esto prueba que a
MFG
M. Acabamos de probar que a
MF
M
MG
M, a
MFG
M. Esto es la denicion de
MF
M
MG
M a
MFG
M.
Hemos comprobado ambas inclusiones, y esto prueba la igualdad.
//
1.5.2. Union
Denici on 1.5.5 Sea F una familia. La (gran) union de F es el conjunto de los elementos
que pertenecen a alguno de los miembros de la familia, y se denota con
_
MF
M o simplemente
F. Simbolicamente,
_
MF
M = x : M F : x M.
21
Como sucede con la interseccion, la union que denimos en la seccion 1.3.2 es un caso particular
de la gran uni on, pues para dos conjuntos A y B cualesquiera, tenemos que:
_
M{A,B}
M = x : M A, B : x M = x : x A x B = A B
Ejemplo 1.5.6 Consideremos la familia F = 1, 1, 2, 1, 2, 3. La gran union de F es
_
MF
M = 1, 2, 3, pues son los unicos elementos de los miembros de F.
Ejemplo 1.5.7 Como ejemplo de la gran union de una familia innita, consideremos la familia
F = 1, , n : n N = 1, 1, 2, 1, 2, 3, . Claramente, todo elemento de la gran
uni on debe ser un n umero natural, pues todos los miembros de la familia son subconjuntos de N.
Ademas, si n N, n 1, , n F, y por tanto, n
_
MF
M. Esto implica que
_
MF
M = N.
La siguiente proposici on enumera las propiedades mas resaltantes de la gran uni on. Como las
propiedades (y sus respectivas demostraciones) son parecidas a las de la gran intersecci on,
dejaremos su demostracion como ejercicio al estudiante.
Proposicion 1.5.8 Sean F y G familias arbitrarias.
(1) Si X F, entonces X
_
MF
M.
(2) Si X es tal que M F, M X, entonces
_
MF
M X.
(3) Si X F es tal que M F, M X, entonces
_
MF
M = X.
(4) Si F G, entonces
_
MF
M
_
MG
M.
(5)
_
MFG
M =
_
MF
M
_
MG
M
Haber denido la gran intersecci on y la gran union, nos permite generalizar las Leyes de
DeMorgan:
Proposicion 1.5.9 Sea F una familia arbitraria, y sea G = M
c
: M F.
(1)
_

MF
M
_
c
=
_
MG
M
(2)
_
_
MF
M
_
c
=
MG
M
22
Demostraci
on:
Probaremos s olo el primer aparatado, y dejaremos la prueba del segundo como ejercicio al
estudiante:
Supongamos que a
_

MF
M
_
c
. Por denicion de complemento, esto implica que a /
MF
M y que, por tanto, no es cierto que M F, a M. A su vez, esto implica que
M F : a / M (si no se cumple para todos, debe haber al menos uno para el que no
se cumple). Por denici on de complemento, M F : a M
c
. Como M F, por cons-
trucci on de G, M
c
G, de manera que a M
c
G. Esto prueba que a
_
MG
M. Luego,
_

MF
M
_
c
_
MG
M.
Recprocamente, supongamos que b
_
MG
M. Por denici on de uni on, M G : b M.
Como (M
c
)
c
= M G, M
c
F y b / M
c
F. Esto implica que b /
MF
M, o bien,
b
_

MF
M
_
c
. Luego,
_
MG
M
_

MF
M
_
c
.
Hemos comprobado ambas inclusiones, y esto prueba la igualdad.
//
23
1.6. Producto
1.6.1. Par ordenado
En los dos captulos siguientes, necesitaremos de pares ordenados de elementos; es decir,
de conjuntos binarios (con dos elementos) tales que podemos armar que uno de ellos es el
primero y el otro, el segundo. Ya hemos menciado que los conjuntos a, b y b, a son identi-
cos, pues poseen los mismos elementos. Por ende, no tendra sentido decir que a es el primer
elemento de a, b, pues tambien sera el primer elemento de b, a.
Algunos textos denen los pares ordenados como expresiones de la forma (a, b). Esta
denici on tiene la desventaja que una expresi on de la forma... no tiene propiedades innatas.
Por ende, tendramos que denir unos cuantos conceptos mas como, por ejemplo, que dos pares
ordenados (a, b) y (c, d) son iguales si y s olo si a = c b = d.
En vez de dar muchas deniciones, deniremos los pares ordenados en terminos de conjun-
tos, de manera que todas sus propiedades podr an deducirse directamente de la denici on:
Denici on 1.6.1 El par ordenado de los elementos a y b (en este orden) es el conjunto
a, a, b, y se denota con (a, b). Simbolicamente, (a, b) = a, a, b.
Esta denici on, aunque parece algo extra na a primera vista, nos ser a util pues cumple todos
los requisitos que hemos menciado. Tiene sentido decir que a es el primer elemento (diremos:
primera coordenada) de (a, b), pues (a, b) = a, a, b mientras que (b, a) = b, b, a.
Para demostrar cuando dos pares ordenados son iguales, usaremos el siguiente resultado previo.
Lema 1.6.2 a, b, c, a = b, c a = b = c
Demostraci
on:
Como b b, c = a, b a y, por tanto, b = a. Analogamente, c = a.
//
Proposicion 1.6.3 a, b, c, d, (a, b) = (c, d) a = c b = d
Demostraci
on:
Sean a, b, c y d elementos arbitrarios pero jos y tales que (a, b) = (c, d).
Probaremos primero que a = c.
Como a a, a, b = (a, b) = (c, d) = c, c, d, a = c a = c, d. Si
a = c, a = c, y si a = c, d, por el lema previo, a = c = d. En ambos casos posibles,
queda probado que a = c.
Ahora probaremos que b = d.
Como a, b a, a, b = (a, b) = (c, d) = (a, d) = a, a, d, a, b = aa, b =
a, d. En ambos casos, a, b a, d.
Como b a, b a, d, b a, d y, por tanto, b = a b = d. Si b = d, no hay
nada que probar. Por otro lado, si b = a, a, a, d = (a, d) = (c, d) = (a, b) = (a, a) =
a, a, a = a. Esto, por el lema previo, implica que a = a, d y, por tanto, a = d.
Como ademas b = a, b = d.
//
24
1.6.2. Producto cartesiano
Denici on 1.6.4 El producto cartesiano de dos conjuntos A y B (en este orden) es el conjunto
de todos los pares ordenados cuya primera coordenada pertenece a A y cuya segunda coordenada
pertenece a B, y se denota con A B. Simbolicamente, A B = (a, b) : a A b B.
Ejemplo 1.6.5 Consideremos los conjuntos A = 1, 2, B = 2, 3. Los productos carte-
siandos posibles son A B = (1, 2), (1, 3), (2, 2), (2, 3) y B A = (2, 1), (3, 1)(2, 2), (3, 2).
Notemos que (AB)(BA) = (2, 2), de manera que los productos cartesianos conmutados
pueden tener elementos en com un, pero (en general) no son iguales.
Cuando A y B son n umeros reales, es com un representar al producto cartesiano A B en en
plano cartesiano. Si A y B son ambos nitos, cada elemento de AB puede ser representado
por un punto:
Figura 1.9: A = 1, 2, 4, 6, 7, B = 1, 3, 5, 7
Si A y B son ambos intervalos, el producto catesiano es un rectangulo. Si los intervalos son
cerrados, dibujamos solo lneas s olidos. De lo contrario, dibujamos lneas punteadas en donde
uno de los intervalos es abierto:
Figura 1.10: A = [1, 8], B = [1, 7], C = (1, 8], D = (1, 7)
Tambien pueden combinarse los dos casos anteriores si uno de los conjuntos es nito y
el otro, un intervalo. En este caso, si el intervalo es abierto en uno de los extremos, este se
25
simboliza con un peque no crculo:
Figura 1.11: A = [1, 8], B = 1, 3, 5, 7, C = (1, 8]
Entre todas las propiedades del producto cartesiano, se destacan las siguientes:
Lema 1.6.6 A, B, A B = A = B =
Demostraci
on:
) Sean A y B arbitrarios pero jos y tales que A B = , y supongamos que A ,= .
Por suposici on, a A. Si B ,= , tambien b B y, por denici on de producto cartesiano,
(a, b) A B = , lo cual es imposible. Esto prueba la primera implicaci on.
) Sean A y B arbitrarios pero jos y tales que A = B = , y supongamos que AB ,= .
Por suposici on, (a, b) A B, de manera que a A y b B. Esto imposibilita que
A = B = .
//
Proposicion 1.6.7 A, B, C, D, A B = C D ,= A = C B = D
Demostraci
on:
Sean A, B, C y D conjuntos arbitrarios pero jos y tales que A B = C D ,= . Para
probar que A C, jemos arbitrariamente a A. Como A B ,= , por el lema, B ,= , de
manera que b B. As, (a, b) A B = C D, de manera que a C. Esto prueba que
A C. Las inclusiones C A, B D y D B se prueban de forma analoga.
//
26
1.7. Ejercicios
Secci on 1: 1. Sea P el conjunto de todos los n umeros pares. Dena P por comprension sin
utilizar la palabra par.
2. Sea P el conjunto de todos los n umeros primos. Dena P por comprensi on sin
utilizar la palabra primo.
3. Pruebe que 2x + 5 : x Z = 1 + 2y : y Z.
4. Cuales de las proposiciones a continuaci on son verdaderas y cuales falsas?
a) 1 N
b) 1 N
c) 1 N
d) 1, 2 N
5. Cuales de las proposiciones a continuacion son verdaderas y cuales falsas? Jus-
tique su respuesta en ambos casos.
a) Si para todo elemento de un conjunto A, se tiene que este elemento tambien
pertenece al conjunto B, entonces puede concluirse que A = B.
b) La relacion basica entre un elemento de A y el conjunto A es la relacion de
inclusi on.
c) Ning un conjunto es parte de s mismo.
d) x, M, x M x M
e) A, B, C, A B C B A C
Secci on 2: 1. Cu ales de las proposiciones a continuacion son verdaderas y cu ales falsas?
a) M, M
b)
c)
2. Se dice que A es un subconjunto propio de B si A B pero A ,= B.
a) Si A B, B C y por lo menos una de las inclusiones es propia, pruebe que
A es un subconjunto propio de C.
b) Es cierto que todo conjunto posee un subconjunto propio? Justique su
respuesta.
a) El unico conjunto que es subconjunto de todos los conjuntos, es el conjunto
vaco.
b) Sean A y B conjuntos. Si se tiene que todo elemento de A pertenece a B pero
que ning un elemento de B pertenece a A, entonces A = .
c) M : M
4. Demuestre la proposici on 1.2.4.
Secci on 3: 1. Sean A = x N : x 10 y B = x N : x > 5. Determine A B y A B.
2. Pruebe que A, B, A B A A B A B B A B.
3. Demuestre la proposici on 1.3.3 sin utilizar tablas.
4. Pruebe que A, B, A B = B A B.
27
5. Pruebe que A, B, A B = B A.
6. Pruebe que A, B, C, (A B) C = A (B C).
7. Pruebe que A, B, C, D, A C B D AB C DAB C D.
8. Demuestre la proposici on 1.3.9 y su corolario.
9. Cu ales de las proposiciones a continuacion son verdaderas y cuales falsas? Jus-
a) Si A y B son disjuntos, A B no es un conjunto.
b) Si A y B son disjuntos, A , B B , A.
c) Si A y B son ambos no vacos, A B ,= .
d) Si A y B son ambos no vacos, A B ,= .
e) A, B, C, (A B) C = A (B C)
f) A, B, C, A (B C) = (A B) (A C)
g) A, B, C, A B = A C B = C
h) Si A B y B y C son disjuntos, entonces A (B C) = A.
10. Pruebe que A, B, A B A B
c
= .
11. Pruebe que A, B, A B B
c
A
c
.
12. Demuestre el segundo apartado de la proposicion 1.3.14.
13. Pruebe que A, B, C, (A B C)
c
= A
c
B
c
C
c
.
14. Pruebe que A, B, C, D, (A B C D)
c
= A
c
B
c
C
c
D
c
.
15. Pruebe que A, B, C, D, (A B C D)
c
= A
c
B
c
C
c
D
c
.
16. Dados los conjuntos A y B, sea X un conjunto tal que A X, B X y
A Y B Y X Y . Pruebe que X = A B.
17. Pruebe que A, B, A = (A B)

(A B).
18. Pruebe que A, B, A B = A
(B A).
19. Pruebe que A, B, A B A B = .
20. Utilice tablas para probar el tercer apartado de la proposicion 1.3.19.
21. Cuales de las proposiciones a continuacion son verdaderas y cu ales falsas? Jus-
a) Si A y B no son disjuntos, A B ,= .
b) A B es un conjunto si y solo si B A.
c) A, B, A B = A (A B)
d) A B y B A siempre son disjuntos.
22. Pruebe que AB = (A B)

(B A).
23. Pruebe que (AB)
c
= (A B) (A B)
c
.
25. Si A B, cual es el conjunto AB?
26. Cual es el conjunto AU?
27. Si A = 1, 2, 3, 4, 5, determine P(A).
28. Pruebe la proposicion 1.3.26.
29. Averig ue si existe alguna relaci on de inclusion entre los conjuntos a continuaci on:
28
a) P(A B) vs P(A) P(B)
b) P(A B) vs P(A) P(B)
c) P(A
c
) vs (P(A))
c
d) P(A B) vs P(A) P(B)
Secci on 4: 1. Utilice diagramas de Venn para representar gracamente los conjuntos de todos
los tri angulos rectangulos (R), de todos los tri angulos is osceles (I), de todos los
tri angulos equil ateros (E) y de todos los tri angulos de permetro 1 (U), tomando
como conjunto universal el conjunto de todos los tri angulos (T).
2. Utilice diagramas de Venn para representar gracamente las siguientes operacio-
nes:
a) A B C
b) A B C
c) (A B) B
d) (A B) C
e) A (B C)
f) (AB) B
g) ABC
Secci on 5: 1. Averig ue cuales son los conjuntos
M
M y
_
M
M.
2. Averig ue cu ales son los conjuntos
MP(U)
M y
_
MP(U)
M.
4. Demuestre el segundo apartado de la proposicion 1.5.9.
5. Sea F una familia arbitraria y X un conjunto arbitrario. Si G = MX : M F,
pruebe que
_

MF
M
_
X =
MG
M.
6. Sea F una familia arbitraria y X un conjunto arbitrario. Si G = MX : M F,
pruebe que
_
_
MF
M
_
X =
_
MG
M.
Secci on 6: 1. Pruebe que A, B, C, D, A C B D A B C D
2. Pruebe que A, B, C, (A B) C = (A C) (B C)
a) A, B, C, D, (A B) (C D) = (A C) (B D)
b) A, B, C, D, (A B) (C D) = (A C) (A D) (B C) (B D)
c) A, B, C, D, (A B) (C D) = (A C) (B D)
d) A, B, C, D, (A B) (C D) = (A C) (A D) (B C) (B D)
29
30
Captulo 2
Relaciones
2.1. Deniciones
2.1.1. Denici on conjuntista
Denici on 2.1.1 Sean A, B y R conjuntos. Si R A B, diremos que R es una relacion
entre A y B (en este orden). En vez de (a, b) R, podemos escribir aRb, lo que leeremos a
se relaciona con b.
Ejemplo 2.1.2 Sean A = 1, 2 y B = 3, 4, 5. Los conjuntos R = (1, 3), (2, 5), S =
(1, 3), (1, 4), (2, 3), (2, 4) y T = (1, 5), (2, 5) son ejemplos de relaciones entre A y B.
Ejemplo 2.1.3 La denicion de relacion deja abierta la posibilidad de que una relacion sea
vaca, de manera que tambien es una relacion entre A y B. Ademas, el conjunto AB tambien
es una relacion entre A y B. En el primer ejemplo, ning un elemento de A se relaciona con
alg un elemento de B. En el segundo ejemplo, todos los elementos de A se relacionan con todos
los elementos de B. Estas dos relaciones, se denominan relaciones triviales entre A y B.
Ejemplo 2.1.4 Los conjuntos A y B de una relacion no son jos. Por ejemplo, R =
(1, 1), (1, 2), (2, 1) es una relacion entre 1, 2 y 1, 2 (pues R 1, 2 1, 2), entre
1, 2, 3 y 1, 2, 4 o entre N y C.
En general, sea R es una relacion entre A y B. Si C A y D B, R tambien es una
relacion entre C y D.
Ejemplo 2.1.5 Sean A = 1, 2, 4, 6, 7, 8 y B = 1, 3, 5, 7, y sea la relacion mayor o
igual entre A y B. Recordando que x y es otra forma de escribir (x, y) , tenemos que =
(1, 1), (2, 1), (4, 1), (4, 3), (6, 1), (6, 3), (6, 5), (7, 1), (7, 3), (7, 5), (7, 7), (8, 1), (8, 3), (8, 5), (8, 7)
(todos los pares (x, y) con x A, y B y x y).
Ejemplo 2.1.6 Una relacion entre N y Z es R = (m, n) N Z : m
2
= n
2
. Por ejemplo,
2R2 y 4R 4. Sin embargo, (3R5) y (2R2) (pues 2 / N).
2.1.2. Representaci on graca
En casos particulares, es sencillo representar una relaci on numerica gr acamente.
Si A y B (y por ende, R) son nitos, podemos representar cada elemento de R por un
punto. La representaci on gr aca del ejemplo 2.1.5 es:
31
Figura 2.1: Ejemplo 2.1.5
Tambien podemos visualizar la relaci on entre los intervalos A = [1, 8] y B = [1, 7]:
Figura 2.2: entre [1, 8] y [1, 7]
Si A y B son nitos, tambien podemos representar R mediante un diagrama de Venn.
Representamos los conjuntos A y B de forma usual (con todos sus elementos) y cada
elemento (x, y) R por un segmento que une x A e y B:
Figura 2.3: Ejemplo 2.1.5
A medida que A y B tengan mas elementos, esta representaci on de R se hace menos
entendible.
32
2.1.3. Relaciones binarias
Denici on 2.1.7 Sea R una relacion. Si R AA (tambien escribiremos A
2
), diremos que
R es una relacion binaria (en A).
Si R es una relacion entre A y B, R A B. Como A B (A B)
2
, R (A B)
2
. Esto
muestra que podemos considerar cualquier relacion entre A y B una relacion binaria en AB.
Ejemplo 2.1.8 La relacion binaria tal vez mas utilizada en un determinado conjunto A es la
de igualdad. Denimos
A
= (x, x) : x A (si A se sobreentiende, obviaremos el subndice).
Gracamente, la relacion de igualdad es la diagonal con pendiente positiva.
Ejemplo 2.1.9 Una relacion binaria muy utilizada es la de divisibilidad entre los enteros:
[ = (n, k n) Z
2
: n, k Z. De la denicion se deduce directamente que n[m k
Z : m = k n. Por ejemplo, 2[6, 3[ 9 y n Z, 1[n. Si n Z 0, (0[n) (pues
k Z, k 0 = 0 ,= n). Recprocamente, n Z, n[0 (pues 0 n = 0). Observemos que
Z
[,
ya que n Z, n[n (pues 1 n = n).
Denici on 2.1.10 Sea R una relacion binaria en A. Diremos que R es reexiva (en A) si
A
R. Esto es, x A, xRx.
Ejemplo 2.1.11 Claramente, las relaciones de igualdad y divisibilidad son reexivas. Tambien
la relacion trivial A
2
es siempre es reexiva en A
2
. La relacion vaca solamente es reexiva en
2
= . La relacion R = (x, x) : x R no es reexiva en R, pues xRx x = x
x = 0.
Ejemplo 2.1.12 Para cada k Z, sea
k
= (m, n) Z
2
: k[m n. Claramente,
k
es
reexiva, pues k[0 = m m, m Z.
k
se denomina congruencia modulo k y es una
relacion muy utilizada en el algebra (se usa la notacion m n(k)). Es facil comprobar que
m
k
n si y solo si m y n tienen el mismo resto en la division por k.
Denici on 2.1.13 Sea R una relacion binaria. Diremos que R es simetrica si x, y, xRy
yRx.
Ejemplo 2.1.14 La relacion R = (1, 1), (1, 2), (2, 1) es claramente simetrica. Por otro lado,
la relacion S = (1, 2), (2, 1), (1, 3) no es simetrica pues 1R3 pero (3R1).
Ejemplo 2.1.15 La relacion de divisibilidad en los enteros no es simetrica pues 2[4 pero
(4[2).
Ejemplo 2.1.16 La relacion de congruencia modulo cualquier entero es simetrica. En efecto,
para k, n, m Z arbitrarios pero jos tenemos que n
k
m k[n m l Z : l k =
n m (l) k = (n m) = m n k[m n m
k
n, lo que prueba que
k
es
simetrica.
Denici on 2.1.17 Sea R una relacion binaria. Diremos que R es antisimetrica si x, y, xRy
yRx x = y.
Ejemplo 2.1.18 La relacion R = (1, 1), (1, 2), (2, 2) es antisimetrica. Por otro lado, la re-
lacion S = (1, 1), (1, 2), (2, 1) no es antisimetrica, pues 1R2 2R1 pero 1 ,= 2.
33
Ejemplo 2.1.19 La relacion de divisibilidad en los enteros no es antisimetrica, pues 1[ 1
1[1 pero 1 ,= 1. Sin embargo, [ = (n, k n) : n, k N - la relacion de divisibilidad en los
naturales - lo es. En efecto, si n y m son naturales arbitrarios, n[mm[n k, l N : m =
k n n = l m m = k n = k (l m) = (k l) m. Si m = 0, n = l m = 0 = m. Caso
contrario, k l = 1, de manera que l = 1 y n = l m = 1 m = m. En ambos casos, n = m.
Esto prueba que [ es antisimetrica.
Denici on 2.1.20 Sea R una relacion binaria. Diremos que R es transitiva si x, y, z xRy
yRz xRz.
Ejemplo 2.1.21 Las relaciones R = (1, 1), (1, 2), (2, 2) y S = (1, 2), (2, 3), (1, 3) son tran-
sitivas. Por otro lado, la relacion S = (1, 1), (1, 2), (2, 1) no es transitiva, pues 2R1 1R2
pero (2R2).
Ejemplo 2.1.22 La relacion de divisibilidad en los enteros es transitiva. En efecto, si x, y y
z son enteros arbitrarios pero jos, x[y y[z k, l Z : y = k x z = l y z = l y =
l (k x) z = (l k) x l k Z x[z. Esto prueba que [ es transitiva.
Ejemplo 2.1.23 La relacion de congruencia modulo cualquier entero es transitiva. En efecto,
para k, x, y, z Z arbitrarios pero jos tenemos que x
k
y y
k
z k[x y k[y z
n, m Z : x y = n k y z = m k x z = (x y) + (y z) = n k + m k
x z = (n +m) k n +m Z k[x z x
k
z, lo que prueba que
k
es transitiva.
34
2.2. Relaciones de equivalencia
2.2.1. Denici on y ejemplos
Denici on 2.2.1 Sea una relacion binaria en A. Diremos que es de equivalencia (en A)
si es reexiva (en A), simetrica y transitiva.
Se le denomina de equivalencia porque comparte estas tres propiedades con la igualdad. La
proposici on a b leeremos a es equivalente a b.
Ejemplo 2.2.2 Ya vimos que
k
es de equivalencia mientras que [ no lo es (porque no es
simetrica).
Ejemplo 2.2.3 Sea = (m, n) Z
2
: m
2
= n
2
. Veamos que es de equivalencia:
Sean x, y, z Z arbitrarios pero jos.
Como x
2
= x
2
, x x. Esto prueba que es reexiva.
x y x
2
= y
2
y
2
= x
2
y x. Esto prueba que es simetrica.
x y y z x
2
= y
2
y
2
= z
2
x
2
= z
2
x z. Esto prueba que es
transitiva.
Ejemplo 2.2.4 Sea = (x, y) R
2
: x y Q. Veamos que es de equivalencia:
Sean x, y, z R arbitrarios pero jos.
Como x x = 0 Q, x x. Esto prueba que es reexiva.
x y x y Q y x = (x y) Q y x. Esto prueba que es
simetrica.
x y y z x y Q y z Q x z = (x y) + (y z) Q x z.
Esto prueba que es transitiva.
Ejemplo 2.2.5 Sea R = (x, y) R
2
: x y Q
c
(tomando R como conjunto universal).
Veamos que R es simetrica, pero que no es reexiva ni transtiva:
Como 0 0 = 0 Q, (0R0). Esto prueba que R no es reexiva.
Sean x, y R arbitrarios pero jos. xRy x y Q
c
y x = (x y) Q
c
yRx. Esto prueba que R es simetrica.

1R
2 (pues 1
2 Q
c
) y
2R0 (pues
2 0 =
2 Q
c
), pero (1R0) (pues
1 0 = 1 Q). Esto prueba que R no es transitiva.
35
2.2.2. Clases de equivalencia
Denici on 2.2.6 Sea una relacion de equivalencia en A, y sea a A. La clase (de equiva-
lencia) de a es el conjunto de todos los elementos que son equivalentes a a (que se relacionan
con a mediante ), y se denota a
(o simplemente a si la relacion se sobreentiende). Simboli-

camente, a
= x A : x a.
Ejemplo 2.2.7 Sean A = 1, 2, 3, 4 y = (1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1). Clara-
mente, es de equivalencia. Las clases de equivalencia son 1 = 2 = 1, 2, 3 = 3 y 4 = 4.
Ejemplo 2.2.8 Sea la relacion de equivalencia del ejemplo 2.2.3. Si n Z, x n
x
2
= n
2
x
2
n
2
= 0 (x n) (x + n) = 0 x = n x = n, de manera que
n = n, n. As, 0 = 0, 1 = 1 = 1, 1, 2 = 2 = 2, 2...
Ejemplo 2.2.9 Sea la relacion de equivalencia del ejemplo 2.2.4. Si a R, x a
xa Q r Q : xa = r r Q : x = a +r x a +r : r Q, de manera
que a = a +r : r Q. En particular, 0 = Q.
En todos los ejemplos pudimos observar que distintas clases de equivalencia son disjuntas. Esto
formaliza la proposici on a continuaci on:
Proposicion 2.2.10 Sea una relacion de equivalencia en A, y sean a, b A. Los enunciados
a continuacion son equivalentes:
(1) a b ,=
(2) a b
(3) a = b
Demostraci
on:
Para probar la equivalencia de los enunciados, es suciente comprobar que (1) (2),
(2) (3) y (3) (1).
Supongamos (1). Entonces, x a b. Como x a, x a; y como x b, x b. Siendo
simetrica, de x a se sigue a x. As, siendo transitiva, de a x y x b se sigue (2).
Esto prueba que (1) (2).
Supongamos (2). Sea x a arbitrario pero jo. Por denici on, x a. Siendo transitiva,
de x a y (2) se sigue x b, la denicion de x b. Esto prueba que a b. Adem as, siendo
simetrica, de (2) se sigue b a, lo cual prueba que b a. De la doble inclusion se sigue (3).
Esto prueba que (2) (3).
Supongamos (3). Como es reexiva, a a, de manera que a a = ab. Como a ab,
tenemos (1). Esto prueba que (3) (1).
//
Observemos que sin reexividad no sera necesariamente cierto que (3) (1), pues podra
darse el caso que a = b = .
Denici on 2.2.11 Sea una relacion de equivalencia en A. El conjunto cociente (entre A y
) es el conjunto de todas las clases de equivalencia de los elementos de A, y se denota
A
.
Simbolicamente,
A
= a : a A.
36
Ejemplo 2.2.12 Sea la relacion del ejemplo 2.2.3.
Z
= 0, 1, 1, 2, 2, .
Ejemplo 2.2.13 Sea la relacion del ejemplo 2.2.4.
R
= a + r : r Q : a R. Como
sucede con R, es imposible denotar este conjunto por extension, pero podemos observar que
Q
R
.
2.2.3. Particiones
Denici on 2.2.14 Sea A un conjunto. Se dice que la familia P es una particion de A si / P,
los miembros de P son dos a dos disjuntos (M
1
, M
2
P, M
1
M
2
,= M
1
= M
2
) y
_
MP
M = A.
Ejemplo 2.2.15 Sea A = 1, 2, 3, 4. Las familias P = 1, 2, 3, 4, Q = 1, 2, 3, 4
y R = 1, 2, 3, 4 son particiones de A, mientras que las familias S = , A, T =
1, 2, 3, 2, 3, 4 y W= 1, 2, 3 no lo son.
Ejemplo 2.2.16 Para cada n Z
+
(enteros positivos), sea D
n
el conjunto de todos los enteros
positivos que poseen exactamente n divisores. D = D
1
, D
2
, D
3
, es una particion de Z
+
.
Es notable que cada D
n
con n > 1 es innito y existe una cantidad innita de ellos.
Existe un fuerte vnculo entre las particiones y las relaciones de equivalencia que los siguientes
dos teoremas ponen en evidencia:
Teorema 2.2.17 Sea A un conjunto y una relacion binaria en A. Si es de equivalencia,
A
es una particion de A.
Demostraci
on:
La proposici on 2.2.10 prueba que los miembros de
A
son dos a dos disjuntos y, como a = a

que a ,= . Solo resta probar que
_
M
A
M = A. En efecto:
Como M
A
M A, es claro que
_
M
A
M A (1.5.8). Para probar la otra inclusi on,

sea a A arbitrario pero jo. Como a a (pues es reexiva), a a. Luego, como a
A
,
la denicion de gran uni on implica que a
_
M
A
M. Esto prueba que A

_
M
A
M. Por doble
inclusi on, el enunciado queda probado.
//
Ejemplo 2.2.18 Sea la relacion del ejemplo 2.2.4. Por el teorema anterior,
R
es una
particion de R. Es notable que la diferencia de dos n umeros cualesquiera de miembros distintos
de la particion es un n umero irracional.
Teorema 2.2.19 Sean A un conjunto no vaco y P una particion de A. En estas condiciones,
la relacion = (x, y) A
2
: P P tal que x, y P es de equivalencia y verica que
A
= P.
37
Demostraci
on:
Notemos que x, y A, x y P P : x, y P.
Primero probaremos que es de equivalencia.
Sean x, y, z A arbitrarios pero jos.
Como P es una partici on, P P : x P. As, x, x = x P P y x x. Esto
prueba que es reexiva.
x y P P : x, y P y, x P P y x. Esto prueba que es
simetrica.
Supogamos que x y y z. Por denici on, P
1
, P
2
P : x, y P
1
y, z P
2
.
Notemos que y P
1
P
2
. Siendo P una partici on, esto implica que P
1
= P
2
. As,
x, z x, y, z = x, y y, z P
1
, lo que implica que x z. Esto prueba que es
transitiva.
Hemos comprobado que es de equivalencia, de manera que podemos considerar el cociente
A
. Falta probar que

A
= P.
Probaremos que todos los miembros de P son clases de equivalencia bajo .
Designemos con P
a
el unico (por denicion de particion) miembro de P tal que a P
a
. Si
x a, por denicion, x a, de manera que P P : x, a P. Como a P, necesaria-
mente P = P
a
, de manera que x P
a
. Esto prueba que a P
a
. Recprocamente, si x P
a
,
x, a P
a
P, de manera que x a y x a. Esto prueba que P
a
a. Por doble inclusion,
a = P
a
.
Si M
A
, debe existir a A : M = a, de manera que M = a = P

a
P. Esto prueba que
A
P.
Recprocamente, si M P, elegimos a M ,= de manera que M = P
a
= a
A
. Esto
prueba que P
A
.
Por doble inclusion, queda probado que
A
= P, lo cual completa la demostracion.

//
Ejemplo 2.2.20 Es claro que P = R
+
, R
, 0 es una particion de R. Por el teorema

anterior, la relacion denida por x, y R, xy R
+
x = y = 0 es de equivalencia y su
conjunto cociente es P.
38
2.3. Relaciones de orden
2.3.1. Denici on y ejemplos
Denici on 2.3.1 Sea A un conjunto y una relacion binaria en A. Diremos que pre-
ordena a A si es reexiva en A y transitiva.
Una relacion que pre-ordena a alg un conjunto, llamaremos una relacion de pre-orden.
La proposicion a b leeremos a precede a b.
Ejemplo 2.3.2 Consideremos el conjunto A = 1, 2, 3. Tenemos que las relaciones
A
,
1
=
A
(1, 2), (1, 3) y
2
=
1
(2, 3), (3, 2) pre-ordenan a A, mientras que R =
A

(1, 2), (2, 3) no pre-ordena a A pues no es transitiva: 1R2 y 2R3 pero (1R3).
Ejemplo 2.3.3 La forma usual de ordenar R es admitir que posee un subconjunto R
+
(con-
junto de los reales positivos) tal que la suma y el producto de n umeros positivos es postivo y
tal que para todo x R, ocurre exactamente una de las siguientes tres proposiciones: x R
+
,
x R
+
y x = 0.
Sea = (x, x +h) : h R
+
0. Probemos que pre-ordena a R:
Sean x, y, z R arbitrarios pero jos.
Como 0 R
+
0, (x, x) = (x, x+0) , o bien, x x. Esto prueba que es reexiva.
x y y z h
1
, h
2
R
+
0 : y = x + h
1
z = y + h
2
z = y + h
2
=
(x +h
1
) +h
2
= x +(h
1
+h
2
) h
1
+h
2
R
+
0 x z, donde h
1
+h
2
R
+
0
pues la suma de n umeros positivos es un n umero positivo (suposicion hecha sobre R
+
).
De manera parecida, pueden denirse las relaciones menor o igual en Q, Z y N. En vez denir
la relaci on tres veces mas y probar que estas relaciones pre-ordenan a los respectivos conjuntos,
podemos deducir estos resultados de la proposicion a continuaci on:
Proposicion 2.3.4 Sea A un conjunto, y sea una relacion que pre-ordena a A. Si B A,
B
= B
2
pre-ordena a B.
La demostracion es sencilla y la dejaremos como ejercicio al estudiante.
Ejemplo 2.3.5 Sea [ la relacion de divisibilidad en Z. [ pre-ordena a Z, pues [ es claramente
reexiva y en el ejemplo 2.1.22 probamos que [ es transitiva.
Denici on 2.3.6 Sea A un conjunto y una relacion binaria en A. Diremos que ordena
a A si pre-ordena a A y es antisimetrica.
Una relacion que ordena a alg un conjunto, llamaremos una relacion de orden.
Ejemplo 2.3.7 Consideremos el conjunto A = 1, 2, 3. Tenemos que las relaciones
A
y
=
A
(1, 2), (1, 3) ordenan a A, mientras que R = (2, 3), (3, 2) no ordena a A pues
no es antisimetrica: 2R3 y 3R2 pero 2 ,= 3.
39
Ejemplo 2.3.8 La relacion ordena a R. Ya probamos que pre-ordena a R, y solo nos falta
probar la antisimetra:
Sean x, y R tales que x y y x. Por construccion de , h
1
, h
2
R
+
0 : y =
x+h
1
x = y+h
2
. As, x = y+h
2
= (x+h
1
)+h
2
= x+(h
1
+h
2
), de manera que 0 = h
1
+h
2
o
bien h
2
= h
1
. Si h
1
,= 0, tendramos que h
1
R
+
y que h
1
= h
2
R
+
. Esto contradice una
suposicion hecha sobre R
+
. As, h
1
= 0 y y = x+h
1
= x+0 = x, lo que prueba la antisimetra.
An alogamente al caso de las relaciones de pre-orden, los subconjuntos de conjuntos ordenados
heredan un cierto orden. La demostracion de la proposici on que arma esto, dejaremos como
ejercicio al estudiante.
Proposicion 2.3.9 Sea A un conjunto, y sea una relacion que ordena a A. Si B A,
B
= B
2
ordena a B.
Ejemplo 2.3.10 Sean [ y [
N
las relaciones de divisibilidad en los enteros y los naturales,
respectivamente. Ya vimos que [ pre-ordena a Z y que [
N
pre-ordena N ([
N
es de pre-orden por
la proposicion 2.3.4). En el ejemplo 2.1.19 probamos que [
N
es antisimetrica, mientras que [ no
lo es. Esto implica que [
N
ordena a N, pero [ no ordena a Z.
Toda relaci on de pre-orden puede ser extendida - en cierto sentido - a una relaci on de orden:
Proposicion 2.3.11 Sean A un conjunto y una relacion que pre-ordena a A. En estas
condiciones, la relacion = (a, b) A
2
: a b b a es de equivalencia y la relacion
=
__
a, b
_
: (a, b) A
2
a b
_
ordena a
A
.
Demostraci
on:
Probaremos primero que es de equivalencia:
Sean a, b, c A arbitrarios pero jos.
Como pre-ordena a A (en particular, es reexiva en A), a a, de manera que a a.
Esto prueba que es reexiva en A.
a b a b b a b a a b b a. Esto prueba que es simetrica.
Supongamos que a b b c. Por construcci on de , a b b a b c c b.
Como pre-ordena a A, es transitiva. Por tanto, a c (pues a b b c) y c a
(pues c b b a), de manera que a c. Esto prueba que es transitiva.
Probaremos ahora que a b a b:
Sean a, b A arbitrarios pero jos y tales que a b. Por denicion de , podemos concluir
unicamente que c, d A : c = a d = b c d. Sin embargo, como c = a d = b, la proposi-
ci on 2.2.10 implica que c a d b, lo que por construcci on de implica que a c d b.
Adem as, tenemos que c d. Por transitividad de concluimos que a b.
Por utlimo, probaremos que ordena a
A
. Sean a, b, c
A
arbitrarios pero jos.

Como es reexiva en A, a a, de manera que a a. Esto prueba que es reexiva
en
A
.
40
Supongamos que a b b a. Ya hemos comprobado que esto implica que a b b a,
y, por tanto a b. Por la proposici on 2.2.10, a = b. Esto prueba que es antisimetrica.
Supongamos que a b b c. Ya hemos comprobado que esto implica que a b b c,
y como es transitiva, esto implica que a c. Por construcci on de , a c. Esto prueba
que es transitiva.
//
Denici on 2.3.12 Sea A un conjunto, y sea una relacion que ordena a A. Diremos que
B A es una -cadena (o simplemente cadena si la relacion se sobreentiende) si x, y
B, x y y x.
En la teora utilizaremos esta denici on solamente en otras deniciones. Dejaremos a cargo del
estudiante averiguar las propiedades de las cadenas.
Denici on 2.3.13 Sea A un conjunto y una relacion binaria en A. Diremos que ordena
totalmente a A si es ordena a A y A es una -cadena.
Una relacion que ordena totalmente a alg un conjunto, llamaremos una relacion de orden
total.
Una relacion que es de orden, pero no de orden total, llamaremos una relacion de orden
parcial y diremos que ordena parcialmente al conjunto.
Ejemplo 2.3.14 Consideremos el conjunto A = 1, 2, 3. Tenemos que la relacion =
A
(1, 2), (1, 3), (2, 3) ordena totalmente a A, mientras que

A
no ordena totalmente a A pues
A no es una
A
-cadena: (1
A
2) y (2
A
1).
Ejemplo 2.3.15 ordena totalmente a R. Ya vimos que ordena a R, y solo nos falta pro-
bar que R es una -cadena:
Sean x, y R arbitrarios pero jos, y sea h = y x. Por la suposicion hecha sobre R
+
,
h R
+
h R
+
h = 0.
Si h R
+
, como y = x +h, x y.
Si h R
+
, como x = y + (h), y x.
Si h = 0, x = y y, como es reexiva, x y y x.
En cualquier caso, x y y x. Esto prueba que R es una -cadena.
La demostracion de la siguiente proposici on dejaremos, de nuevo, como ejercicio al estudiante.
Proposicion 2.3.16 Sea A un conjunto, y sea una relacion que ordena totalmente a A. Si
B A,
B
= B
2
ordena totalmente a B.
Ejemplo 2.3.17 Sea [ la relacion de divisibilidad en N. Aunque [ ordena a N, no lo ordena
totalmente: Ninguna de las proposiciones 2[3 y 3[2 es cierta, lo que implica que N no es una
[-cadena.
41
2.3.2. Diagramas de Hasse
Toda relacion de pre-orden en un conjunto nito tiene una representacion graca muy util
llamada diagrama de Hasse. Consiste en representar cada punto de A por un punto y el hecho
que a precede a b por una echa de a a b sin representar las precedencias reexivas ni las que se
pueden deducir de la transitividad. Si la relaci on es de orden, podemos reemplazar una echa
de a a b por una arista ascendente de a a b.
Por ejemplo, si A = 1, 2, 3, la relacion de orden total =
A
(1, 2), (1, 3), (2, 3) queda
completamente caracterizada por el hecho que 1 22 3, pues como es reexiva,
A

y como es transitiva, (1, 3) . Dos diagramas de Hasse para esta relaci on (utilizando aristas
y echas) son:
Figura 2.4: Orden total
La relacion de arriba es de orden total. El siguiente diagramas de Hasse representa una
relaci on de orden parcial en el mismo conjunto:
Figura 2.5: Orden parcial
El diagrama indica explcitamente que (1, 2), (1, 3) . Por reexividad,
A
. As,
=
A
(1, 2), (1, 3).
Para representar una relacion de pre-orden (que no es antisimetrica) con un diagrama de
Hasse, podemos convenir que una arista horizontal signica precedencia en ambos sentidos.
Esto indicamos con echas dobles en el otro metodo. Por ejemplo:
Figura 2.6: Pre-orden
El diagrama indica explcitamente que (1, 2), (1, 3), (2, 3), (3, 2) . Por reexividad,
A
. As, =
A
(1, 2), (1, 3), (2, 3), (3, 2).
El diagrama con echas no presenta problemas para las relaciones de pre-orden, pero la
falta de antisimetra puede complicar considerablemente representar una relacion de pre-orden
utilizando aristas. En general, utilizaremos el metodo mas facil.
A continuaci on, representaremos la relacion de divisibilidad restringida al conjunto de los
divisores de 24. Como esta relacion es de orden, utilizaremos el metodo de las aristas:
42
Figura 2.7: Divisores de 24
Cuando la relaci on es de orden, nos es util la siguiente regla: Representamos a b por una
arista si y solo si no existe c distinto de a y b tal que a c b. En el ejemplo de arriba, hicimos
justamente esto: Representamos x[y por una arista si y solo si x[z z[y z = x z = y.
Pero esto ocurre solamente si
y
x
es primo. Por ejemplo, representamos 2[4 y 4[12 por aristas
pues
4
2
= 2 y
12
4
= 3 son primos.
En cierto casos, es posible representar una relacion innita mediante un diagrama de Hasse,
pero esto depende de nuestra capacidad de interpretar puntos suspensivos.
Figura 2.8: en Z
Figura 2.9: en N
Mientras que es claro que el primer diagrama representa la relaci on menor o igual en Z,
admitir que segundo diagrama representa la relacion de divisibilidad en N depende de nuestra
buena voluntad. Finalmente, hay relaciones que son imposibles de representar por diagramas:
Por ejemplo, para en Q, no existen a, b Q tales que ning un c Q distinto de a y b cumple
que a c b.
2.3.3. Cotas inferiores y elementos minimales
Denici on 2.3.18 Sean A un conjunto y una relacion que pre-ordena a A. Diremos que c
es una -cota inferior del conjunto B A si y solo si b B, c b.
Si B A posee alguna -cota inferior, diremos que B es inferiormente -acotado.
En general, la cota inferior de un conjunto no es unica, pues si c es una cota inferior de B y
d c, d tambien es una cota inferior de B.
Ejemplo 2.3.19 0 es una -cota inferior de R
+
, pues si x R
+
, 0 x. Con mas razon,
todo n umero real negativo es una cota inferior de R
+
.
43
Ejemplo 2.3.20 Sea la relacion menor o igual en Z. Z no es acotado pues si tuvieramos
que c Z es una cota inferior de Z, tendramos por contradiccion que c 1 Z pero c , c 1.
Ejemplo 2.3.21 Sean A = 1, 2, 3 y =
A
(1, 2), (1, 3), (2, 1), (2, 3). El subconjunto
B = 1, 2 posee dos cotas inferiores: 1 y 2. En efecto, 1 es cota inferior de B pues 1 12 1
y 2 es cota inferior de B pues B pues 2 1 2 2.
En el diagrama de Hasse se ve claramente que 1 y 2 preceden a todos los elementos de B:
Figura 2.10: en A
Ejemplo 2.3.22 Sean A = 1, 2, 3 y =
A
(1, 3), (2, 3). El subconjunto B = 1, 2,
aunque nito, no posee una cota inferior: En efecto, 1 no es cota inferior de B pues 1 , 2, 2
no es cota inferior de B pues 2 , 1 y 3 no satisface 3 1 ni 3 2.
Estudiar estas propiedades es mucho mas sencillo con el diagrama de Hasse:
Figura 2.11: en A
Se ve que B = 1, 2 no posee una cota inferior pues no hay ning un elemento que preceda
a 1 y 2 simultaneamente.
Ejemplo 2.3.23 Sean A = 1, 0, 1, 2, 3 y
=
A
(1, 0), (1, 1), (1, 2), (1, 3), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3).
Figura 2.12: en A
Con esta relacion, B = 1, 2 es inferiormente acotado, pues posee dos cotas inferiores (0
y 1).
Aunque un conjunto no sea inferiormente acotado, puede tener elementos minimales en el
sentido de la denici on a continuaci on:
Denici on 2.3.24 Sean A un conjunto y una relacion que pre-ordena a A. Diremos que
m B es un elemento -minimal del conjunto B A si y solo si b B, b m m b.
La implicaci on de la dencion parece extra na a primera vista, pero su signicado quedar a claro
con los ejemplos a continuaci on:
44
Ejemplo 2.3.25 El conjunto B del ejemplo 2.3.21 posee dos elementos minimales: 1 y 2. En
efecto, si b B b 1 b = 1 b = 2
1112
1 b. Esto prueba que 1 es un elemento
minimal de B. La prueba para el 2 es analoga. En este ejemplo, las cotas inferiores coinciden
con los elementos minimales.
En el diagrama de Hasse se visualiza bien el signicado de la denicion: 1 es un elemento
minimal de B pues todos los elementos que preceden al 1 tambien le siguen.
Ejemplo 2.3.26 El conjunto B del ejemplo 2.3.22, aunque no es inferiormente acotado, posee
dos elementos minimales: 1 y 2. En efecto, el 1 es el unico elemento que precede al 1 y el 2 es
el unico elemento que precede al 2.
Ejemplo 2.3.27 El conjunto B del ejemplo 2.3.23, al igual que el conjunto del ejemplo ante-
rior, posee dos elementos minimales: 1 y 2. 0 y 1, aunque son cotas inferiores de B, no son
elementos minimales de B, pues no pertenecen a B.
Ejemplo 2.3.28 R
+
, aunque inferiormente -acotado, no posee elementos minimales.
En efecto, si m R
+
fuese un elemento -minimal de R
+
, tendramos que
m
2
m pero que
m ,
m
2
. Como
m
2
R
+
(suposicion hecha sobre R
+
), esto es una contradiccion.
La siguiente denicion combina las propiedades de la cota inferior y elemento minimal:
Denici on 2.3.29 Sean A un conjunto y una relacion que pre-ordena a A. Diremos que m
es un -mnimo del conjunto B A si y solo si m B y m es una cota inferior de B.
Ejemplo 2.3.30 0 es un -mnimo de N y 1 es un [-mnimos de Z.
Ejemplo 2.3.31 Las cotas inferiores del conjunto B del ejemplo 2.3.21 son tambien mnimos
de B pues pertenecen a B.
Ejemplo 2.3.32 El conjunto B del ejemplo 2.3.23 posee dos cotas inferiores (0 y 1), pero
ninguna de ellas es un mnimo pues no pertenecen a B.
2.3.4. Cotas superiores y elementos maximales
Las deniciones de cota superior, elemento maximal y maximo son respectivamente analogas
a las de cota inferior, elemento minimal y mnimo. Enunciaremos apenas las deniciones y
dejaremos la b usqueda de ejemplos an alogas a cargo del estudiante.
Denici on 2.3.33 Sean A un conjunto y una relacion que pre-ordena a A. Diremos que c
es una -cota superior del conjunto B A si y solo si b B, b c.
Si B A posee alguna -cota superior, diremos que B es superiormente -acotado. Si
B A es inferior y superiormente -acotado, diremos que B es -acotado.
Denici on 2.3.34 Sean A un conjunto y una relacion que pre-ordena a A. Diremos que
m B es un elemento -maximal del conjunto B A si y solo si b B, m b b m.
Denici on 2.3.35 Sean A un conjunto y una relacion que pre-ordena a A. Diremos que m
es un -maximo del conjunto B A si y solo si m B y m es una cota superior de B.
45
2.3.5.

Inmos y supremos
Los conceptos de nmo y supremo generalizan los de mnimo y m aximo, repectivamente:
Denici on 2.3.36 Sean A un conjunto, una relacion que pre-ordena a A, B A y C
el
conjunto de todas las cotas inferiores de B. Diremos que i es un -nmo de B si y solo si i
es un maximo de C
.
En otras palabras, el nmo es el maximo entre las cotas inferiores. En particular, el nmo es
una cota inferior. Por tanto, para que un conjunto pueda poseer nmo, debe ser inferiormente
acotado.
Denici on 2.3.37 Sean A un conjunto, una relacion que pre-ordena a A, B A y C
+
el
conjunto de todas las cotas superiores de B. Diremos que s es un -supremo de B si y solo si
s es un mnimo de C
+
.
Valen las aclaraciones analogas al nmo. Estudiaremos, de nuevo, solo el caso del nmo pues
el otro es an alogo. Una fuente natural de nmos son los mnimos:
Proposicion 2.3.38 Sean A un conjunto y una relacion que pre-ordena a A. Todo -
mnimo de B A es tambien un -nmo de B.
La demostracion es sencilla, y la dejaremos como ejercicio al estudiante.
Ejemplo 2.3.39 Recordemos que las cotas inferiores del conjunto B del ejemplo 2.3.23 son
1 y 0. Claramente, 0 es un maximo del conjunto de las cotas inferiores, de manera que 0 es
un nmo de B, aunque B no posea mnimo.
Ejemplo 2.3.40 Un conjunto inferiormente acotado no posee necesariamente nmo. Sea
la relacion menor o igual en Q, y sea B = r Q : 0 r 2 r
2
. B es inferiormente
acotado por 0 pero no posee nmo. En efecto:
Supongamos que i Q es un nmo de B. Como i Q, i
2
,= 2. Probaremos que las
suposiciones i
2
< 2 e 2 < i
2
llevan ambas a contradicciones:
Supongamos que 2 < i
2
. Como ambos miembros de la desigualdad son positivos, podemos
aplicar raz cuadrada de manera que
2 < i. A continuacion, elijamos n Z

+
:
1
n
<
i
2. As, debe existir m Z

+
:
2 <
m
n
< i, de manera que 2 <
m
2
n
2
< i
2
. As,
m
2
n
2
B
pero
m
2
n
2
< i
2
, lo que contradice la denicion de cota inferior.
Supongamos que i
2
< 2. Analogamente al caso anterior, existen m, n Z
+
tales que
i <
m
n
< 2, donde
m
n
Q. Esto implica que
m
n
es una cota inferior de B pero i <
m
n
, lo
que contradice la denicion de nmo.
Todo subconjunto no vaco e inferiormente -acotado de R posee -nmo, pero no estamos
en condiciones de probarlo.
2.3.6. Buen orden
Denici on 2.3.41 Sean A un conjunto y una relacion binaria en A. Diremos que ordena
bien a A si ordena a A y todo subconjuntono vaco B A posee un -mnimo.
Una relacion que ordena bien a alg un conjunto, llamaremos una relacion de buen orden.
46
Ejemplo 2.3.42 Sean A = 1, 2, 3 y =
A
(1, 2), (1, 3), (2, 3).
Los posibles subconjuntos de A son 1, 1, 2, 1, 3, A (mnimo: 1), 2, 2, 3 (mnimo:
2), 3 (mnimo: 3).
Estas aramciones se verican facilmente mediante el diagrama de Hasse:
Figura 2.13: en A
Ninguna relaci on que no es de orden total puede ser de buen orden. Esto es lo que arma la
proposici on a continuaci on, cuya demostracion dejaremos como ejercicio al lector.
Proposicion 2.3.43 Sea A un conjunto. Toda relacion que ordena bien a A, ordena totalmente
a A.
Ejemplo 2.3.44 El recproco de la propsicion anterior no es cierto. Consideremos la relacion
en R. Ya vimos que es de orden total en R. Sin embargo, R
+
no posee -mnimo. Si
m R
+
fuese un -mnimo, tendramos por contradiccion que m ,
m
2
.
Una forma practica de denir una relacion de buen orden en un conjunto, es particionarlo
convenientemente, ordenar bien a la particion y ordenar bien luego a cada miembro de la
partici on.
Proposicion 2.3.45 Sean A un conjunto y P una particion de A. Supongamos que
P
ordena
bien a P y que para cada M P existe una relacion
M
que ordena bien a M. En estas
condiciones, = (a, b) A
2
: (P
a

P
P
b
P
a
,= P
b
) (P
a
= P
b
a
P
a
b) ordena bien a A,
donde P
a
es el unico elemento de P tal que a P
a
.
Demostraci
on:
Primero probaremos que es de orden en A.
Sean a, b, c A arbitrarios pero jos.
Trivialmente, P
a
= P
a
, y como
P
a
es reexiva en P
a
, a
P
a
a. As, a a. Esto prueba
que es reexiva.
Supongamos que a b b a. Como a b, (P
a

P
P
b
P
a
,= P
b
) (P
a
= P
b
a
P
a
b).
En ambos casos, P
a

P
P
b
. Por otro lado, como b a, (P
b

P
P
a
P
b
,= P
a
) (P
b
=
P
a
b
P
b
a), y en ambos casos, P
b

P
P
a
. As, siendo
P
antisimetrica, P
a
= P
b
. Esto
implica que a
P
a
b y que b
P
b
a. Siendo
P
a
=
P
b
antisimetrica, tenemos que a = b.
Esto prueba que es antisimetrica.
Supongamos que a b b c. Como a b, (P
a

P
P
b
P
a
,= P
b
) (P
a
= P
b
a
P
a
b).
En ambos casos, P
a

P
P
b
. Por otro lado, como b c, (P
b

P
P
c
P
b
,= P
c
) (P
b
=
P
c
b
P
b
c), y en ambos casos, P
b

P
P
c
. As, siendo
P
transitiva, P
a

P
P
c
.
Si P
a
,= P
c
, no hay nada que probar pues, por construcci on de , a c. Supongamos
que P
a
= P
c
. As, P
a

P
P
b

P
P
c
= P
a
y, por antisimetra de
P
, P
a
= P
b
= P
c
. Luego,
a
P
a
b y b
P
b
c. Siendo
P
a
=
P
b
transitiva, tenemos que a
P
a
c y, por tanto, a c.
47
S olo falta probar que todo subconjunto no vaco de A posee un -mnimo. En efecto:
Sea X A no vaco.
Sea X = M P : M X ,= . Siendo P una particion de A, X P no puede ser vaco,
de manera que X posee un
P
-mnimo (pues
p
ordena bien a P) que designaremos con P.
As, P X ,= y P X P, de manera que P X posee un
P
-mnimo que designaremos
con m. Con nuestra notaci on, P = P
m
. Veamos que m es un -mnimo de X:
Sea x X arbitrario pero jo. Debemos probar que m x. Como x P
x
X, P
x
X ,= ,
de manera que P
x
X y, como P
m
es un mnimo de X, P
m

P
P
x
. Si P
m
,= P
x
, no hay nada
que probar pues, por construcci on, de , m x. Supongamos que P
m
= P
x
. En este caso,
como m es el mnimo de P X y m, x P X, m x. Esto prueba que ordena bien a A.
//
En este captulo, a un no estamos en condiciones de probar que ordena bien a N, pero el
resultado es intuitivo y ya lo utilizaremos en este captulo.
Ejemplo 2.3.46 En el ejemplo 2.3.20 vimos que Z no es inferiormente -acotado. En parti-
cular, esto implica que no ordena bien a Z. A continuacion, deniremos una relacion que
s lo hace:
Sea P = 0, 1, 1, 2, 2, . Claramente, P es una particion de Z. Sea
P
=
(m, m, n, n) : m N n N m n. Como ordena bien a N,
P
ordena
bien a P. Ademas, para cada n N, ordena bien a n, n. Por la proposicion 2.3.45, =
(m, n) Z
2
: (m, m
P
n, nm, m , = n, n)(m, m = n, nm n),
de manera que m n m
2
< n
2
(m
2
= n
2
m n).
El diagrama de Hasse asociado es:
Figura 2.14: Buen orden en Z
Ejemplo 2.3.47 Analogamente al caso de Z, Q no es inferiormente -acotado. Como hici-
mos con Z, deniremos ahora una relacion que ordena bien a Q:
Cada n umero racional r puede expresarse de forma unica como un cociente
p
q
tal que p Z,
q Z
+
y tal que p y q tengan MCD 1. Designemos con (r) la suma [p[ +q ([p[ se llama valor
absoluto de p e indica el n umero positivo x tal que x
2
= p
2
).
P = r Q : (r) = n : n N es claramente una particion de Q, donde r
Q : (r) = 1 =
0
1
= 0, r Q : (r) = 2 =
1
1
,
1
1
= 1, 1, r Q : (r) =
3 =
1
2
,
1
2
,
2
1
,
2
1
=
1
2
,
1
2
, 2, 2, r Q : (r) = 4 =
1
3
,
1
3
,
3
1
,
3
1
=
1
3
,
1
3
, 3, 3,
r Q : (r) = 5 =
1
4
,
1
4
,
2
3
,
2
3
,
3
2
,
3
2
,
4
1
,
4
1
=
1
4
,
1
4
,
2
3
,
2
3
,
3
2
,
3
2
, 4, 4...
Sea
P
= (r Q : (r) = m, r Q : (r) = n) : m Z
+
n Z
+
m n. Como
ordena bien a N Z
+
,
P
ordena bien a P.
48
Como ordena totalmente a Q y cada r Q : (r) = n es nito, ordena totalmente a
cada r Q : (r) = n (esto depende del buen orden de N y lo probaremos posteriormente).
Por la proposicion 2.3.45, = (r, s) Q
2
: (r) < (s) ((r) = (s) r s) ordena
bien a Q.
El diagrama de Hasse asociado es:
Figura 2.15: Buen orden en Q
49
2.4. Ejercicios
Secci on 1: 1. Represente gr acamente a cada una de las siguientes relaciones binarias:
a) 5, 4, 3, 2, 1, 0, 1, 2, 3, 4, 5
2
b) [ D
2
, donde D N es el conjunto de los divisores de 60
c) R = (x, y) R
2
: 0 x 2 0 y 4 x 2y
2. Clasique las siguientes relaciones binarias seg un reexividad, simetra, antisi-
metra y transitividad:
a) en cualquier conjunto A
b) A
2
en cualquier conjunto A
c) R = (1, 2), (2, 3), (3, 4), (4, 1) en 1, 2, 3, 4
d) S = (1, 1), (3, 3), (3, 4), (4, 3), (4, 4) en 1, 2, 3, 4
e) T = (1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 3), (1, 3) en 1, 2, 3, 4
f) < en Z
g) W = (x, y) Q
2
: x y Z en Q
h) X = (x, y) R
2
: x
2
+y
2
= 1 en R
i) Y = (x, y) R
2
: x
2
1 +y
2
en R
j) Z = (x, y) R
2
:
x
y
1 en R
a) Toda relacion simetrica y transitiva es tambien reexiva.
b) Una relaci on no puede ser simetrica y antisimetrica a la vez.
c) Si R es reexiva en A y S es reexiva en B, entonces R S es reexiva en
A B.
d) Si R es reexiva en A y S es reexiva en B, entonces R S es reexiva en
A B.
e) Si R y S son ambas simetricas, R S es simetrica.
f) Si R y S son ambas antisimetricas, R S es antisimetrica.
g) Si R y S son ambas transitivas, R S es transitiva.
h) Si R y S son ambas simetricas, R S es simetrica.
i) Si R y S son ambas antisimetricas, R S es antisimetrica.
j) Si R y S son ambas transitivas, R S es transitiva.
4. De ejemplo de una relacion que no sea reexiva, simetrica, antisimetrica ni tran-
sitiva.
Secci on 2: 1. Cu ales de los siguientes ejemplos intuitivos es una relacion de equivalencia?
Justique su respuesta.
a) A se relaciona con B si y solo si A tiene la misma edad que B en el conjunto
de todas las personas.
b) A se relaciona con B si y s olo si A y B tienen el mismo color en el conjunto
de todos los autos.
c) A se relaciona con B si y s olo si A es hermano de B en el conjunto de
todos los adolescentes.
d) A se relaciona con B si y s olo si A es por lo menos tan alto como B en el
conjunto de todos los arboles.
50
e) A se relaciona con B si y s olo si A es perpendicular a B en el conjunto de
todas las rectas.
2. Sean A = 1, 2, 3, 4, 5 y =
A
(2, 3), (3, 2). Aseg urese que es de equi-
valencia y determine
A
por extension.
3. Determine (por extensi on) la relaci on de equivalencia en A = 1, 2, 3, 4, 5, 6
tal que
A
= 1, 2, 3, 4, 5, 6.
4. Dena (en R) la relacion de manera que x y x
2
x = y
2
y. Pruebe que
es de equivalencia en R, determine cada clase de equivalencia por extensi on y
determine el conjunto cociente.
5. Encuentre el error en el razonamiento a continuacion: Sea R una relaci on simetri-
ca y transitiva. Como R es simetrica, aRb implica bRa, y como R es transitiva,
aRb bRa implica aRa. Luego, R es reexiva y, por tanto, de equivalencia.
6. Dena (en Z
2
) la relacion de manera que (a, b) (c, d) a + d = b + c.
Pruebe que es de equivalencia en Z
2
y que (a, b) (a
, b
) (a +c, b +d)
(a
+c, b
+d).
7. Si R es una relacion binaria en A, denamos la clase lateral derecha de a A
como Ra = x A : xRa. Si A ,= y Ra : a A forma una partici on de A,
es seguro armar que R es de equivalencia? Justique su respuesta.
8. Si R es una relacion binaria en A, denamos la clase lateral izquierda de a A
como aR = x A : aRx. Cuales de las proposiciones a continuacion son
verdaderas y cuales falsas? Justique su respuesta en ambos casos.
a) R es simetrica si y s olo si a A, aR Ra
b) R es simetrica si y s olo si a A, Ra aR
c) R es simetrica si y s olo si a A, aR = Ra
d) Si R es transitiva y a A, aR Ra ,= , entonces R es reexiva.
e) Si R es transitiva, simetrica y a A, Ra ,= , entonces R es de equivalencia.
9. Sean P y Q particiones del conjunto A. Pruebe que R = P Q : P PQ
Q P Q ,= tambien es una partici on de A.
10. Sean P y Q particiones de los conjuntos A y B respectivamente. Pruebe que
R = P Q : P P Q Q es una partici on de A B.
Secci on 3: 1. Sea A = 1, 2, 3, 4, 5, 6. Determine (por extensi on) relaciones
1
,
2
,
3
,
4
,
5
y
6
de manera que:
a)
1
y
2
son de pre-orden pero no de orden y
1
,=
2
b)
3
y
4
son de orden parcial y
3
,=
4
c)
5
y
6
son de orden total y
5
,=
6
Represente cada relacion por un diagrama de Hasse.
2. Explique las diferencias entre los diagramas de Hasse de relaciones de pre-orden,
orden y orden total.
3. Clasique las siguientes relaciones seg un pre-orden, orden y orden total:
a) en P(N)
b) denida por (a, b) (c, d) a
2
+b
2
c
2
+d
2
en R
2
c) denida por (a, b) (c, d) a < c (a = c b d) en R
2
51
7. Represente la relacion [ D
2
por un diagrama de Hasse, donde D N es el
conjunto de los divisores de 60.
8. Clasique la relaci on en A =
1
n
: n Z
+
.
10. Sean A un conjunto y una relaci on de pre-orden en A. Enuncie condiciones
sucientes (tan debiles como sea posible) para que cada una de las siguientes
proposiciones (por separadas) sea cierta:
a) Todo B A posee a lo mas un -mnimo.
b) Todo B A posee a lo mas un -nmo.
c) Todo B A no vaco posee exactamente un -mnimo.
Cuando existen y son unicos, simbolizamos el -mnimo B por mn
B y el
-nmo de B por nf
B (an alogamente: max
, sup
).
11. Sea la relacion menor o igual en R. Determine las cotas inferiores, los ele-
mentos minimales, el nmo y el mnimo (todos si existen) de A =
1
n
: n Z
+
y B = A 0.
12. Sea [ la relaci on de divisibilidad en N. Determine las cotas inferiores y superiores,
los elementos minimales y maximales, el nmo, el supremo, el mnimo y el
m aximo (todos si existen) de A = 2, 3, 5, B = 2, 4, 6, C = 2, 4, 6, 8, ,
D = 4, 9, E = 10
n
: n Z
+
y N.
13. Si A, B R, denamos A+B = a+b : a Ab B. Pruebe que nf
A+B =
nf
A +nf
B.
14. Sean A, B R tales que a A, b B, a b. Pruebe que sup
A nf
B.
15. Sean A, B R tales que a A, b B, a < b. Es seguro armar que
sup
A <nf
B? Justique su respuesta.
17. Sea A un conjunto, y sea una relacion que ordena bien a A. Si B A, pruebe
que
B
= B
2
ordena bien a B.
18. Sean A y B disjuntos. Si
A
ordena bien a A y
B
ordena bien a B, pruebe que
existe una relaci on que ordena bien a A B.
19. Si
A
ordena bien a A y
B
ordena bien a B, pruebe que existe una relaci on
que ordena bien a A B.
20. Si
A
ordena bien a A y
B
ordena bien a B, pruebe que existe una relaci on
que ordena bien a A B.
21. Dena una relaci on de buen orden en N tal que m ax
N = 0. Pruebe que
su relaci on es efectivamente de buen orden, y representela por un diagrama de
Hasse.
22. Dena una relaci on de buen orden en Z con la siguiente propiedad: si x Z
+
e
y Z
, entonces x y. Pruebe que su relacion es efectivamente de buen orden,

y representela por un diagrama de Hasse.
52
Captulo 3
Funciones
3.1. Deniciones
3.1.1. Denici on conjuntista
Denici on 3.1.1 Sean A, B y F conjuntos no vacos. Decimos que f = (A, B, F) es una
funcion (de A en B) si F es una relacion entre A y B y se verican las siguientes condiciones:
x A, y B : xFy
x A, y, z B, xFy xFz y = z
En caso armativo, decimos que A el es dominio de f, que denotaremos con D(f), B es el
codominio de f, que denotaremos con C(f), y F es la graca de f, que denotaremos con G(f).
Bien entendido, las dos condiciones de la denici on expresan que para cada elemento x del
dominio debe haber un unico elemento y del dominio tal que x se relaciona con y mediante
F. A este unico y, llamamos imagen de x por f, y escribimos f(x) = y (se lee: f de x es y).
Recpocamente, si f(x) = y, decimos que x es una preimagen de y por f.
Ejemplo 3.1.2 Sean A = 1, 2, B = 1, 2, 3, F = (1, 3), (2, 1) y f = (A, B, F). Es claro
que F es una relacion entre A y B (pues F A B) y que a cada x A le corresponde
un unico y B (al 1 le corresponde el 3 y al 2 le corresponde el 1), de manera que f es una
funcion de A en B. Tenemos que f(1) = 3 y que f(2) = 1.
Notemos que no existe un x A tal que f(x) = 2. Esto no es exigido por la denicion, de
manera que en el codominio pueden sobrar elementos.
Ejemplo 3.1.3 Sean A = 1, 2, B = 1, 2, 3, G = (1, 2), (2, 2) y g = (A, B, F). Es claro
que g es una funcion. Tenemos que g(1) = 2 y que g(2) = 2.
Notemos que 1 y 2 tienen la misma imagen por g. La denicion no descarta esto, de manera
que los elementos del codominio se pueden repetir.
Ejemplo 3.1.4 Sean A = 1, 2, B = 1, 2, 3, F = (1, 1), G = (1, 2), (2, 1), (2, 3),
f = (A, B, F) y g = (A, B, G).
f no es una funcion, pues el 2 no tiene imagen en el codominio, y g no es una funcion,
pues el 2 tiene dos imagenes en el codominio (1 y 3).
Notemos que f(2) no tiene sentido porque no hay un elemento al que es igual, y que g(2)
no tiene sentido, pues debera cumplirse que 1 = g(2) = 3.
53
Ejemplo 3.1.5 Sean A = 1, 2, B = 1, 2, 3, F = (1, 2), (2, 3), (3, 1), G = (1, 2), (2, 4),
f = (A, B, F) y g = (A, B, G).
f y g no son funciones porque F y G no son relaciones entre A y B.
Para simbolizar que f es una funcion de A en B, utilizaremos la notacion f : A B (usamos
la echa para las implicaciones). Similarmente, para expresar que f(x) = y, tambien po-
demos escribir f : x y.
Establecer funciones mediante la denici on puede resultar algo inc omodo. Por ejemplo, si
queremos establecer f como la funci on de Z en N que a cada n umero entero le asigna su cuadra-
do, debemos establecer previamente la gr aca como F = (k, k
2
) : k Z, y luego establecer
que f = (Z, N, F).
Para el efecto, podemos utilizar las notaciones que hemos mencionado. Una manera formal
que denir f es escribir:
f : Z N
x x
2
.
Menos formal, pero m as utilizado, es sea f : Z N la funcion denida por f(x) = x
2
.
Sin embargo, debemos tener cuidado con estas deniciones. De manera parecida, podramos
establecer sea g : N Z la funcion denida por g(n) =

n, sin tener en cuenta que esto no
dene realmente a una funcion. Por ejemplo, aunque
2 tiene sentido en R, no tiene sentido

en Z, pues el cuadrado de cualquier n umero entero es distinto de 2.
3.1.2. Representaci on graca
Para representar gracamente a una funci on f, recurrimos a la tecnicas mencionadas en la
secci on 2.1.2 para gracar la relaci on G(f) (es por esto que se llama gr aca de f).
Si el dominio y el codominio son nitos, los diagramas de Venn son la forma mas pr actica
de representar a una funci on, y tambien para evidenciar que una terna f = (A, B, F) no es
una funcion.
A continuaci on, damos unos ejemplos de funciones y no funciones.
Los diagramas a continuacion representan las funciones de los ejemplos 3.1.2 y 3.1.3
Figura 3.1: Funci on
los diagramas a continuacion las no funciones del ejemplo 3.1.4
54
Figura 3.2: No funciones
y los diagramas a continuaci on las no funciones del ejemplo 3.1.5
Figura 3.3: No funciones
Si el dominio de una funci on es un intervalo (o uni on de intervalos), solo nos resta la repre-
sentaci on gr aca en el plano cartesiano. Sean F = (x, y) : x
2
+ y
2
= 1 y G = (x, y) : y =
1 x
2
. Estos dos conjuntos pueden parecer iguales a primera vista, pero no lo son, pues la
segunda coordenada en G es siempre positiva. Por ejemplo, (0, 1) F G.
La representaci on gr aca de F es:
Figura 3.4: F
y la representacion gr aca de G es:
55
Figura 3.5: G
Analicemos si f = ([1, 1], R, F), g
1
= (R, R, G) y g
2
= ([1, 1], R, G) son funciones:
f no es una funci on pues la recta x = 0 interseca a G(f) en dos puntos distintos ((0, 1)
y (0, 1)), de manera que (0, 1) F y (0, 1) F.
g
1
no es una funci on pues la recta x = 2 no interseca a G(g
1
), de manera que g
1
(2) no
tiene sentido, pero 2 D(g
1
) = R.
g
2
es una funci on. Para todo x
0
D(g
2
) = [1, 1], la recta x = x
0
interseca a G(g
2
) en
exactamente un punto, de manera que para cada x
0
D(g
2
) = [1, 1], existe un unico
y
0
R tal que (x
0
, y
0
) G.
56
3.2. Imagenes y preimagenes
3.2.1. Imagen
Denici on 3.2.1 Sea f : A B una funcion. Si X A, la imagen de X por f es el
conjunto de las imagenes (por f) de los elementos de X, y se denota f[X]. Simbolicamente,
f[X] = f(x) : x X.
Ejemplo 3.2.2 Sea f : N N la funcion denida por f(x) = 2x + 1. La imagen de X =
1, 2, 5 es f[X] = f(x) : x X = 2x + 1 : x 1, 2, 5 = f(1), f(2), f(5) = 3, 5, 11.
Ejemplo 3.2.3 Sea f : N N la funcion denida por f(x) = 2x. La imagen del conjunto de
los n umeros pares P = n N : 2[n es f[P] = f(x) : x P = 2x : x N 2[x = x
N : 4[x, el conjunto de los m ultiplos de 4.
La imagen cumple las siguientes propiedades:
Proposicion 3.2.4 Sea f : A B una funcion.
(1) f[] =
(2) X P(A), f[X] = X =
(3) X
1
, X
2
P(A), X
1
X
2
f[X
1
] f[X
2
]
Demostraci
on:
(1) Supongamos que y f[]. Por denicion de imagen, esto implica que existe un x tal
que y = f(x), lo cual es absurdo. Por tanto, f[] es vaco.
(2) Supongmaos que x X. Por denicion de imagen, esto implica que f(x) f[X] = , lo
cual es absurdo. Por tanto, X = .
(3) Sea y f[X
1
] arbitrario pero jo. Por denicion de imagen, x X
1
: y = f(x). Como
X
1
X
2
, x X
2
, de manera que y = f(x) f[X
2
]. Hemos probado que y f[X
1
], y
f[X
2
], la denici on de f[X
1
] f[X
2
].
//
Para las operaciones entre conjuntos, tenemos las siguientes propiedades para las imagenes:
(1) X
1
, X
2
P(A), f[X
1
X
2
] f[X
1
] f[X
2
]
(2) X
1
, X
2
P(A), f[X
1
] f[X
2
] f[X
1
X
2
]
(3) X
1
, X
2
P(A), f[X
1
X
2
] = f[X
1
] f[X
2
]
Demostraci
on:
(1) Como X
1
X
2
X
1
y X
1
X
2
X
2
, por la proposicion 3.2.4, f[X
1
X
2
] f[X
1
] y
f[X
1
X
2
] f[X
2
]. Luego, f[X
1
X
2
] f[X
1
] f[X
2
].
(2) Sea y f[X
1
] f[X
2
] arbitrario pero jo. Como y f[X
1
], x X
1
: y = f(x). Como
f(x) = y / f[X
2
], x / X
2
. Por tanto, x X
1
X
2
, de manera que y = f(x) f[X
1
X
2
].
Esto prueba que f[X
1
] f[X
2
] f[X
1
X
2
].
57
(3) Como X
1
X
1
X
2
y X
2
X
1
X
2
, por la proposicion 3.2.4, f[X
1
] f[X
1
X
2
] y
f[X
2
] f[X
1
X
2
]. Luego, f[X
1
] f[X
2
] f[X
1
X
2
].
Para probar la inclusi on inversa, sea y f[X
1
X
2
] arbitrario pero jo. Por denicion de
imagen, x X
1
X
2
: y = f(x). Si x X
1
, y = f(x) f[X
1
] f[X
1
]f[X
2
], y si x X
2
,
y = f(x) f[X
2
] f[X
1
] f[X
2
]. En ambos casos, queda probado que y f[X
1
] f[X
2
].
Esto prueba que f[X
1
X
2
] f[X
1
] f[X
2
].
La igualdad se sigue de la doble inclusion.
//
La proposicion anterior tambien es v alida para las operaciones generalizadas.
Proposicion 3.2.6 Sea f : A B una funcion, F P(A).
(1) f
_

MF
M
_

MF
f[M]
(2) f
_
_
MF
M
_
=
_
MF
f[M]
Demostraci
on:
(1) Como, por la proposici on 1.5.4, X F,
MF
M X, la proposicion 3.2.4 implica
que X F, f
_

MF
M
_
f[X]. De nuevo por la proposici on 1.5.4, esto implica que
f
_

MF
M
_

XF
f[X] =
MF
f[M], lo cual prueba el apartado.
(2) Como, por la proposici on 1.5.8, X F, X
_
MF
M, la proposicion 3.2.4 implica
que X F, f[X] f
_
_
MF
M
_
. De nuevo por la proposici on 1.5.8, esto implica que
_
MF
f[M] =
_
XF
f[X] f
_
_
MF
M
_
, lo cual prueba una inclusion del apartado.
Para probar la inclusion inversa, sea y f
_
_
MF
M
_
arbitrario pero jo. Por denici on de
imagen, x
_
MF
M : y = f(x). Por denici on de uni on, X F : x X, de manera que
y = f(x) f[X]
_
XF
f[X]. Esto prueba la inclusion inversa.
//
3.2.2. Preimagen
Denici on 3.2.7 Sea f : A B una funcion. Si Y B, la preimagen de Y por f es el
conjunto de los elementos del dominio cuya imagen (por f) esta en Y , y se denota f
1
[Y ].
Simbolicamente, f
1
[Y ] = x A : f(x) Y .
58
Ejemplo 3.2.8 Sea f : Z N la funcion denida por f(x) = x
2
. La preimagen de Y =
1, 2, 4 es f
1
[Y ] = x N : f(x) Y = x : x
2
1, 2, 4 = 1, 1, 2, 2.
Ejemplo 3.2.9 Sea f : N N la funcion denida por f(x) = 2x. La preimagen del conjunto
de los n umeros pares P = n N : 2[n es f
1
[P] = x : f(x) P = x N : 2[2x = N, el
conjunto de todos los n umeros naturales.
A continuaci on, enunciamos las propiedades que poseen las preim agenes de una funci on. Sus
demostraciones son parecidas a las de las im agenes, y las dejaremos como ejercicio al estudiante.
(1) f
1
[] =
(2) f
1
[B] = A
(3) Y
1
, Y
2
P(B), Y
1
Y
2
f
1
[Y
1
] f
1
[Y
2
]
(1) Y
1
, Y
2
P(B), f
1
[Y
1
Y
2
] = f
1
[Y
1
] f
1
[Y
2
]
(2) Y
1
, Y
2
P(B), f
1
[Y
1
Y
2
] = f
1
[Y
1
] f
1
[Y
2
]
(3) Y P(B), f
1
[Y
c
] = (f
1
[Y ])
c
(4) Y
1
, Y
2
P(B), f
1
[Y
1
Y
2
] = f
1
[Y
1
] f
1
[Y
2
]
Proposicion 3.2.12 Sea f : A B una funcion, F P(B).
(1) f
1
_

MF
M
_
=
MF
f
1
[M]
(2) f
1
_
_
MF
M
_
=
_
MF
f
1
[M]
59
3.3. Composicion
3.3.1. Relaciones
Denici on 3.3.1 Sean R y S relaciones. La composicion de R con S (en este orden) es el
conjunto (x, z) : y : xRy R ySz, y se denota con S R.
Ejemplo 3.3.2 Sean R = (1, 2), (2, 3), (2, 4), (4, 3) y S = (1, 5), (3, 1). Claramente, R y
S son realciones de 1, 2, 3, 4, 5 en s mismo.
Sean T
1
= S R y T
2
= R S. Como 2R3, 4R3 y 3S1, tenemos que 2T
1
1 y 4T
1
1. Como
3S1 y 1R2, 3T
2
2. Es facil ver que estos son los unicos elementos de las composiciones; es
decir, T
1
= ((2, 1), (4, 1)) y T
2
= (3, 2). Notemos que la composicion de relaciones no es
conmutativa.
Una forma facil de determinar la composici on de relaciones nitas es la representaci on graca
mediante diagramas de Venn:
Figura 3.6: S R
Los elementos de la composicion son todos los pares de los conjuntos extremos que pueden
ser unidos mediante un camino poligonal.
Para la composici on recproca, tenemos el diagrama a continuaci on:
Figura 3.7: R S
Ya vimos que la composici on no es conmutativa. Sin embargo, es asociativa.
Proposicion 3.3.3 Para cada terna de relaciones R, S y T, T (S R) = (T S) R.
60
Demostraci
on:
Sea (x, w) T (S R) arbitrario. Por denicion de composici on, existe un z tal que
(x, z) (S R) y (z, w) T. Como (x, z) (S R), por denici on de composicion, existe un
y tal que (x, y) R e (y, z) S.
Como (y, z) S y (z, w) T, (y, w) (T S). Recordando que (x, y) R, se sigue que
(x, w) (T S) R. Esto prueba que T (S R) (T S) R.
Para probar la inlcusion recproca, sea (x, w) (T S) R arbitrario. Por denici on de
composici on, existe un y tal que (x, y) R y (y, w) (T S). Como (y, w) (T S), por
denici on de composici on, existe un z tal que (y, z) S y (z, w) T.
Como (x, y) R y (y, z) S, (x, z) (S R). Recordando que (z, w) T, se sigue que
(x, w) T (S R). Esto prueba que (T S) R T (S R).
Por doble inclusion, el enunciado queda probado.
//
3.3.2. Funciones
A partir de la composici on de relaciones, recordando que el gr aco de una funci on es una
relaci on, podemos denir la composicion de funciones. Previamente, debemos vericar cu ando
la compsocion de dos gr acas es la graca de una funcion.
Proposicion 3.3.4 Sean f = (A, B, F) y g = (B, C, G) funciones. Entonces h = (A, C, GF)
es una funcion, y vale que h(x) = g(f(x)), x A.
Demostraci
on:
Para simplicar la notaci on, sea H = G F.
Sea x A arbitrario. Entonces (x, f(x)) F, lo cual implica, en particular, que f(x) B.
As, (f(x), g(f(x))) G, lo cual implica en particular, que g(f(x)) C. Por denici on de
composici on, (x, g(f(x)) H. Esto prueba que x A, z(= g(f(x))) C : (x, z) H.
Supongamos que (x, z) verica que (x, z) H. Por denici on de composici on, existe un y tal
que (x, y) F e (y, z) G. Como (x, y) F, y = f(x); y como (y, z) G, z = g(y) = g(f(x)).
Esto prueba que h es una funci on y que h(x) = g(f(x)), x A.
//
A partir de este resultado, podemos denir la composici on de dos funciones f y g como la
funci on h de la proposici on anterior.
Denici on 3.3.5 Sean f : A B y g : B C funciones. La composicion de f con g (en
este orden) es la funcion h : A C denida por h(x) = g(f(x)), que denotaremos con g f.
Con esta notacion, la proposicion 3.3.4 estipula que G(g f) = G(g) G(f). Ademas, si
f : A B, g : B C y h : C D son tres funciones, h (g f) = (h g) f, ya que, por la
proposici on 3.3.3, G(h(gf)) = G(h)G(gf) = G(h)(G(g)G(f)) = (G(h)G(g))G(f) =
G(h g) G(f) = G((h g) f), y sus dominios y codominios son claramente iguales.
61
Si las gracas de dos funciones son nitas, podemos pensar en la composicion de las funcio-
nes como tal o como la composicion de sus gr acas. Sin embargo, si las gr acas son innitas,
es mas sencillo tratar las funciones como tales.
Ejemplo 3.3.6 Sean f, g : Z Z las funciones denidas por f(x) = x
2
y g(y) = y + 1.
g f : Z Z es la funcion denida por (g f)(x) = g(f(x)) = g(x
2
) = x
2
+1, y f g : Z Z
es la funcion denida por (f g)(y) = f(g(y)) = f(y + 1) = (y + 1)
2
= y
2
+ 2y + 1. Notemos
que la composion de funciones tampoco es conmutativa.
Dejaremos la demostracion de la proposici on a continuacion como ejercicio al estudiante.
Proposicion 3.3.7 Sean f : A B y g : B C funciones.
(1) Si X P(A), (g f)[X] = g[f[X]].
(2) Si Z P(C), (g f)
1
[Z] = f
1
[g
1
[Z]].
62
3.4. Clasicaci on de funciones
3.4.1. Inyectividad
Denici on 3.4.1 Sea f : A B una funcion. Diremos que f es inyectiva si las imagenes
de elementos distintos de A por f son distintas. Simbolicamente, f es inyectiva si y solo si
x
1
, x
2
A, f(x
1
) = f(x
2
) x
1
= x
2
.
Ejemplo 3.4.2 Sea f : Z Z. La funcion denida por f(x) = 2x. Si f(x
1
) = f(x
2
), tenemos
que 2x
1
= 2x
2
y, dividiendo por 2, que x
1
= x
2
. Por tanto, f es inyectiva.
Ejemplo 3.4.3 Sea f : Z Z. La funcion denida por f(x) = x
2
. Como f(1) = 1 = f(1),
f no es inyectiva, pues 1 y 1 poseen la misma imagen por f.
Proposicion 3.4.4 Sea f : A B y g : B C funciones. Si f y g son ambas inyectivas,
entonces la composicion g f tambien es inyectiva.
Demostraci
on:
Observemos que la composicion esta bien denida (pues C(f) = D(g)) y que D(g f) =
D(f) = A.
Sean x
1
, x
2
A, y supongamos que (g f)(x
1
) = (g f)(x
2
). Por denicion de composicion,
g(f(x
1
)) = g(f(x
2
)).
Como g es inyectiva y f(x
1
) y f(x
2
) poseen la misma imagen por g, f(x
1
) = f(x
2
). Siendo
f inyectiva, esto implica que x
1
= x
2
.
Esto prueba que g f es inyectiva.
//
Ejemplo 3.4.5 Sean A = 1, 2, B = 3, 4, 5, F = (1, 3), (2, 4), G = (3, 1), (4, 2), (5, 2),
f = (A, B, F) y g = (B, A, G). Claramente, g no es inyectiva, pues g(4) = 2 = g(5). Sin
embargo, la composicion g f es inyectiva, pues D(g f) = A, (g f)(1) = g(f(1)) = g(3) = 1
y (g f)(2) = g(f(2)) = g(4) = 2.
Aunque no necesariamente ambas funciones cuya composicion es inyectiva son inyectivas, s lo
es la funci on derecha.
Proposicion 3.4.6 Sea f : A B y g : B C funciones. Si g f es inyectiva, entonces la
funcion f tambien es inyectiva.
Demostraci
on:
Observemos que la composici on esta bien denida (pues C(f) = D(g)).
Sean x
1
, x
2
A tales que f(x
1
) = f(x
2
). Aplicando g a ambos miebros, queda g(f(x
1
)) =
g(f(x
2
)), de manera que (g f)(x
1
) = (g f)(x
2
). Como g f es inyectiva, esto implica que
x
1
= x
2
, de manera que f es inyectiva.
//
63
3.4.2. Sobreyectividad
Denici on 3.4.7 Sea f : A B una funcion. Diremos que f es sobreyectiva si cada elemento
del codominio posee una preimagen. Simbolicamente, f es sobreyectiva si y solo si f[A] = B.
Ejemplo 3.4.8 La funcion f : Q Q denida por f(x) = 2x es sobreyectiva, pues para cada
y Q, f(
y
2
) = 2
y
2
= y, de manera que cada y Q pertenece a f[Q].
Ejemplo 3.4.9 La funcion f : Z Z denida por f(x) = 2x, aunque muy parecida a la
anterior, no es sobreyectiva. 3 Z, pero para cada x Z, f(x) = 2x ,= 3. De hecho, f[Z] es el
conjunto de todos los n umeros enteros pares (positivos y negativos) y, por tanto, distinto de Z.
De manera parecida al caso de las funciones inyectivas, tenemos que:
Proposicion 3.4.10 Sea f : A B y g : B C funciones. Si f y g son ambas sobreyectivas,
entonces la composicion g f tambien es sobreyectiva.
Proposicion 3.4.11 Sea f : A B y g : B C funciones. Si g f es sobreyectiva, entonces
la funcion g tambien es sobreyectiva.
Las demostraciones son sencillas, y las dejaremos a cargo del estudiante.
3.4.3. Biyectividad
Denici on 3.4.12 Sea f : A B una funcion. Diremos que f es biyectiva si es tanto inyec-
tiva como sobreyectiva.
Las propiedades de las funciones biyectivas, se deducen directamente de las dos secciones
anteriores.
64
3.5. Funciones especiales
Denici on 3.5.1 Sea A un conjunto no vaco. La identidad en A es la funcion (A, A,
A
),
que se denota con I
A
.
Otra forma de especicar I
A
sera: sea I
A
: A A la funci on denida por I
A
(x) = x. Aplicar
I
A
a un elemento de A reproduce el mismo elemento. Es claro que toda funcion identidad es
biyectiva, pues I
A
(x
1
) = I
A
(x
2
) es literalmente igual a x
1
= x
2
e I
A
[A] = I
A
(x) : x A =
x : x A = A.
Denici on 3.5.2 Sean A y B conjuntos no vacos tales que A B. La inclusion de A en B
es la funcion (A, B,
A
), que se denota con i
A;B
.
La inclusi on posee la misma regla de asignacion que la identidad; es decir, si x A B,
i
A;B
(x) = x = I
A
(x). Sin embargo, si A ,= B, estas dos funciones son distintas, pues poseen
codominios distintos. En efecto, i
A;B
no es sobreyectiva, pues i
A;B
[A] = i
A;B
(x) : x A =
x : x A = A ,= B.
La funcion inclusi on nos permite denir la restricci on de una funcion.
Denici on 3.5.3 Sea f : A B una funcion. Si X P(A) es no vaco, la restriccion de f
a X es la funcion f i
X;A
, que se denota con f[
X
.
De nuevo, las funciones f y su restriccion f[
X
poseen la misma regla de asignaci on; es decir, si
x X, f(x) = f[
X
(x). Sin embargo, si X ,= A, no son iguales, pues poseen dominios distintos.
En efecto, si x A X, f(x) representa un elemento del codominio de f, pero f[
X
(x) carece
de sentido, ya que x / X = D(f[
X
).
Denici on 3.5.4 Sean A
1
, , A
n
conjuntos no vacos y A = A
1
A
n
. Para cada k
1, , n, la proyeccion sobre la k-esima coordenada es la funcion
A;k
: A A
k
denida por
A;k
(a
1
, , a
k
, , a
n
) = a
k
.
Por ejemplo,
Z
2
;1
,
Z
2
;2
: Z
2
Z son la funciones denidas por
Z
2
;1
(x, y) = x y
Z
2
;2
(x, y) = y.
Notemos que estas funciones asignan a cada vector (x, y) Z
2
su primera y segunda coorden-
dada.
Dejaremos a cargo del estudiante vericar que las proyecciones son siempre sobreyectivas.
Hemos probado que la composici on de dos inyecciones (funciones inyectivas) o de dos sobre-
yecciones (funciones sobreyectivas), siempre es una inyecci on o una sobreyeccion. Es natural
que nos preguntemos si la composicion de una inyeccion con una sobreyeccion resulta ser una
funci on especial. La respuesta es negativa. En efecto, cualquier funci on es composicion de
una inyeccion y una sobreyecci on, en ambos sentidos. La proposici on a continuaci on prueba
esto. Aparte de satisfacer esta curiosidad, no posee aplicaci on practica.
Proposicion 3.5.5 Si f : A B es una funcion, existen inyecciones y y sobreyecciones
y tales que = f = .
Demostraci
on: Sean : A B y : A f[A] las funciones denidas por (x) = (x, f(x))
y (x) = f(x). es inyectiva, pues si (x
1
) = (x
2
), (x
1
, f(x
1
)) = (x
2
, f(x
2
)), de manera que
x
1
= x
2
(por la proposici on 1.6.3). Adem as, es sobreyectiva, pues [A] = (x) : x A =
f(x) : x A = f[A].
65
Sean =
AB;2
y = i
f[A];B
. Ya hemos visto que es sobreyectiva y que es inyectiva,
y solo falta comprobar que = f = .
D( ) = D() = A = D(f) y C( ) = C() = B = C(f). Para probar la igual-
dad de las gr acas, basta comprobar que las reglas de asignacion son iguales; es decir,
x A, ()(x) = f(x). En efecto, si x A, ()(x) = ((x)) =
AB;2
(x, f(x)) = f(x).
D( ) = D() = A = D(f) y C( ) = C() = B = C(f). Ademas, si x A,
( )(x) = ((x)) = i
f[A];B
(f(x)) = f(x). Esto prueba el enunciado.
//
66
3.6. Inversas
3.6.1. Relaciones
Denici on 3.6.1 Sea R una relacion. La relacion inversa de R es la relacion (y, x) : (x, y)
R, que se denota con R
1
.
Ejemplo 3.6.2 Claramente, la relacion inversa de R = (1, 2), (2, 3), (3, 2), es la relacion
R
1
= (2, 1), (2, 3), (3, 2).
Observemos que R da lugar a la funcion f = (1, 2, 3, 2, 3, R), mientras que R
1
no puede
ser la gr aca de ninguna funci on pues 2R
1
1 2R
1
3.
Las mayora de las propiedades de las relaciones inversas no seran necesarias en nuestro
estudio, y dejaremos sus demostraciones como ejercicio al estudiante. La principal propiedad
de las relaciones inversas es la siguiente:
Proposicion 3.6.3 Sea f = (A, B, F) una funcion. Si f es biyectiva, entonces g = (B, A, F
1
)
tambien es una funcion.
Demostraci
on:
Sea y B. Como f es sobreectiva, y f[A]; es decir, existe x A tal que y = f(x),
o bien, (x, y) F. Por denici on de relaci on inversa, (y, x) F
1
, donde x A. Es decir,
y B, z(= x) A : (y, z) F
1
.
S olo falta comprobar la unicidad. Supongamos que (y, x
1
), (y, x
2
) F
1
. Por denici on de
relaci on inversa, (x
1
, y), (x
2
, y) F; es decir, f(x
1
) = y = f(x
2
). Como f es inyectiva, se sigue
que x
1
= x
2
. Esto prueba el enunciado.
//
3.6.2. Inversas a la izquierda
Denici on 3.6.4 Sea f : A B una funcion. Se dice que g es una inversa a la izquierda de
f si g f = I
A
.
Observemos que, para que la composici on g f tenga sentido, es necesario y suciente que
D(g) = C(f) = A. Adem as, para que C(g f) = C(I
A
) = A, debe cumplirse que C(g) = A.
Es decir, si g es una inversa a la izquierda de f, g : B A.
Ejemplo 3.6.5 Sea f = (A, B, F) una funcion, donde A = 1, 2, 3, B = 1, 2, 3, 4 y F =
(1, 2), (2, 3), (3, 4). Para que g : B A pueda ser una inversa a la izquierda de f, es necesario
y suciente que g(2) = g(f(1)) = I
A
(1) = 1, g(3) = g(f(2)) = I
A
(2) = 2 y g(4) = g(f(3)) =
I
A
(3) = 3. Por tanto, si G
1
= (1, 1), (2, 1), (3, 2), (4, 3), G
2
= (1, 2), (2, 1), (3, 2), (4, 3)
y G
3
= (1, 3), (2, 1), (3, 2), (4, 3), las funciones g
1
= (B, A, G
1
), g
2
= (B, A, G
2
) y g
3
=
(B, A, G
3
) son inversas a la izquierda de f.
Hemos visto que la inversa a la izquierda de una funci on no es necesariamente unica. En
contraste, ciertas funciones no poseen ninguna inversa a la izquierda.
Ejemplo 3.6.6 Sea f = (A, B, F) una funcion, donde A = 1, 2, 3, B = 1, 2 y F =
(1, 2), (2, 1), (3, 2). Para que g : B A pueda ser una inversa a la izquierda de f, es
necesario que g(2) = g(f(1)) = I
A
(1) = 1 y que, por otro lado, g(2) = g(f(3)) = I
A
(3) = 3.
Claramente, esto imposibilita la existencia de una inversa a la izquierda de f.
67
Basado en el ejemplo anterior, podemos establecer un criterio para la existencia de una inversa
a la izquierda.
Proposicion 3.6.7 Sea f : A B una funcion. A n de que f posea una inversa a la
izquierda, es necesario y suciente que f sea inyectiva.
Demostraci
on:
Supongamos que g sea una inversa a la izquierda de f. Como g f = I
A
es inyectiva, por
la proposicion 3.4.6, f debe ser inyectiva. Esto prueba que la inyectividad es necesaria.
Supongamos que f sea inyectiva, y sea F = G(f). Consideremos la funcion

f = (A, f[A], F)
que es claramente biyectiva. Por la proposicion 3.6.3, g = (f[A], A, F
1
) tambien es una
funci on. Si f[A] = B, sea g = g. De lo contrario, elijamos arbitrariamente a A. Co-
mo (B f[A], A, (B f[A]) a) es claramente una funci on (llamada funci on constante),
g = (B, A, G) tambien es una funci on, donde G = F
1
((B f[A]) a) (confronte los
ejercicios de la secci on 3.1). S olo nos falta comprobar que g f = I
A
. En efecto:
Es claro que g f est a bien denido y que D(g f) = C(g f) = A. Sea x A arbitrario.
Entonces (x, f(x)) F, de manera que (f(x), x) F
1
G. Por denicion de composicion,
(x, x) GF; esto es, (g f)(x) = x. Como esto vale para cada x A, se sigue que g f = I
A
.
Esto prueba que la inyectividad es suciente.
//
Ejemplo 3.6.8 La funcion f : R
+
0 R denida por f(x) =

x es claramente inyectiva,
de manera que debe poseer una inversa a la izquierda. En efecto, la funcion g : R R
+
0
denida por g(y) = y
2
cumple que (g f)(x) = g(f(x)) =

x
2
= x, ya que, por denicion,

x
es el n umero positivo cuyo cuadrado es igual a x.
Observemos que f g no es la funcion identidad en R. (f g)(y) = f(g(y)) =
_
y
2
= y si
y solamente si y 0, pues la raz de un n umero no puede ser negativa.
3.6.3. Inversas a la derecha
Denici on 3.6.9 Sea f : A B una funcion. Se dice que g es una inversa a la derecha de f
si f g = I
B
.
Ya vimos que la funcion f : R
+
0 R denida por f(x) =

x es una inversa a la derecha
de la funci on g : R R
+
0 denida por g(y) = y
2
.
De hecho, por la denicion es claro que f es una inversa a la derecha de g si y s olo si g es
una inversa a la izquierda de f.
Ejemplo 3.6.10 Sean A = 3, 2, 1, 1, 2, 3, B = 1, 2, 3, F = (x, y) AB : x
2
= y
2
y f = (A, B, F). Determinar una inversa a la derecha de f es tarea facil: Para cada y B,
debemos elegir un x A tal que f(x) = y; es decir, podemos tomar g = (B, A, G), donde
G = (1, 1), (2, 2), (3, 3), G = (1, 1), (2, 2), (3, 3) o G = (1, 1), (2, 2), (3, 3), para
citar algunas de las (8) inversas a la derecha de f.
Por el ejemplo, parece ser obvio que toda funcion sobreyectiva posee inversa a la derecha. Este
resultado, que dista de ser obvio o incluso intuitivo, se probara en el captulo 4. A un as, ya lo
consideraremos un resultado v alido.
Por de pronto, probaremos la implicaci on inversa.
68
Proposicion 3.6.11 Sea f : A B una funcion. Si f posee inversa a la derecha, entonces
es sobreyectiva.
Demostraci
on:
Supongamos que g sea una inversa a la derecha de f. Como f g = I
B
es sobreyectiva, por
la proposicion 3.4.11, f debe ser sobreyectiva. Esto prueba el enunciado.
//
3.6.4. Inversas bilaterales
Denici on 3.6.12 Sea f : A B una funcion. Se dice que g es una inversa (bilateral) de f
si es tanto una inversa a la izquierda como a la derecha de f.
El termino inversa bilateral es poco com un. Siempre que digamos que g es una inversa de f
o que f posee inversa, nos referiremos a las inversas bilaterales. Con esta terminologa, una
inversa a la izquierda no es una inversa, pues no es bilateral.
Hemos visto que inversas a la izquierda no son necesariamente inversas a la derecha y, por
tanto, viceversa. Esto no puede ocurrir para funciones biyectivas.
Proposicion 3.6.13 Sea f : A B una funcion biyectiva. Si g es una inversa a la izquierda
de f, entonces es una inversa de f. Si h es una inversa a la derecha de f, entonces es una
inversa de f. Ademas, dos inversas unilaterales cualesquiera, son iguales.
Demostraci
on:
Sean g y h inversas a la izquierda y a la derecha, repectivamente, de f (su existencia
est a asegurada, pues f es biyectiva). Por denici on de inversas laterales y por la asociatividad
de la composici on, queda que g = g I
B
= g (f h) = (g f) h = I
A
h = h, de manera que
g = h, g es tambien una inversa a la derecha y h es tambien una inversa a la izquierda. Esto
prueba el enunciado.
//
A partir de este resultado, la prueba del siguiente corolario es inmediata.
Corolario 3.6.14 Sea f : A B una funcion. Los enunciados a continuacion son equivalen-
tes:
(1) f es biyectiva.
(2) f posee exactamente una inversa.
(3) f posee una inversa.
Demostraci
on:
Supongamos (1). Como f es, en particular, inyectiva, la proposici on 3.6.7 revela que f posee
una inversa a la izquierda g (digamos). Por la proposici on 3.6.13, g es una inversa de f. Esto
prueba (2).
Es claro que (2) implica (3).
Supongamos (3), y sea g una inversa de f. Como g es una inversa a la izquierda y a la
derecha, por las proposiciones 3.6.7 y 3.6.11, f debe ser biyectiva. Esto prueba (1).
//
Como la inversa de una funci on f es unica (si existe), la denotaremos con f
1
.
69
3.7. Ejercicios
Secci on 1: 1. Cu ales de las ternas (A, B, F) a continuacion representan funciones? Justique
su respuesta en ambos casos.
a) A = N, B = N, F = (x, y) N
2
: 2x = y + 1
b) A = N, B = N, F = (x, y) N
2
: 5x = y 1
c) A = Z, B = Z, F = (x, y) Z
2
: y = x
2
d) A = Z, B = Z, F = (x, y) Z
2
: x = y
2
e) A = Z, B = Z, F = (x, y) Z
2
: x
2
= y
2
f) A = Z, B = N, F = (x, y) Z N : x
2
= y
2
g) A = N, B = Z, F = (x, y) N Z : x
2
= y
2
2. Sea (A, B, F) una funci on. Cu ales de las proposiciones a continuaci on son ver-
daderas y cu ales falsas? Justique su respuesta en ambos casos.
a) Si C A, entonces (C, B, F) tambien es una funcion.
b) Si C A, entonces (C, B, G) tambien es una funci on, donde G = F (CB).
c) Si A C, entonces (C, B, F) tambien es una funcion.
d) Si A C, entonces (C, B, G) tambien es una funci on, donde G = F
CA
.
e) Si D B, entonces (A, D, F) tambien es una funcion.
f) Si D B, entonces (A, D, G) tambien es una funci on, donde G = F(AD).
g) Si B D, entonces (A, D, F) tambien es una funcion.
h) Si B D, entonces (A, D, G) tambien es una funci on, donde G = F
DB
.
3. Pruebe que si f
1
= (A
1
, B
1
, F
1
) y f
2
= (A
2
, B
2
, F
2
) son funciones y A
1
y A
2
son
disjuntos, entonces g = (A
1
A
2
, B
1
B
2
, F
1
F
2
) tambien es una funcion.
4. Sean f
1
= (A
1
, B
1
, F
1
) y f
2
= (A
2
, B
2
, F
2
) funciones, y sea g = (A
1
A
2
, B
1

B
2
, F
1
F
2
). Pruebe que g es una funci on si y s olo si x A
1
A
2
, f
1
(x) = f
2
(x).
Secci on 2: 1. Sea f : Z Z la funci on denida por f(x) =
x
2
. Determine f[Z
+
], f[Z
],
f
1
[Z
+
] y f
1
[Z
].
5. Sea f : A B una funci on. Cu ales de las proposiciones a continuacion son
verdaderas y cuales falsas? Justique su respuesta en ambos casos.
a) Si X
1
, X
2
P(A) y f[X
1
] f[X
2
], entonces X
1
X
2
.
b) Si X
1
, X
2
P(A), entonces f[X
1
X
2
] = f[X
1
] f[X
2
].
c) Si X
1
, X
2
P(A), entonces f[X
1
X
2
] = f[X
1
] f[X
2
].
d) Si X
1
, X
2
P(A), entonces f[X
1
X
2
] = f[X
1
]f[X
2
].
e) Si Y P(B) y f
1
[Y ] = , entonces Y = .
f) Si Y
1
, Y
2
P(B) y f
1
[Y
1
] f
1
[Y
2
], entonces Y
1
Y
2
.
g) Si Y
1
, Y
2
P(B), entonces f
1
[Y
1
Y
2
] = f
1
[Y
1
]f
1
[Y
2
].
6. Pruebe que si f : A B es una funcion y X A, entonces X f
1
[f[X]]. Es
cierta la inclusi on inversa? Justique su respuesta.
7. Pruebe que si f : A B es una funci on e Y B, entonces f[f
1
[Y ]] Y .
De una formula explcita para f[f
1
[Y ]], exclusivamente en terminos de imagenes
e intersecciones.
70
Secci on 3: 1. Cu ales son las relaciones R que verican que RR R? Justique su respuesta.
2. Sean f : Q1 Q1 y g : Q1 Q1 las funciones denidas
por f(x) =
x1
x+1
y g(y) =
1+y
1y
. Compruebe que f y g est an bien denidas (que
verdaderamente son funciones), y determine g f y f g.
4. Sean f : A B, g : B C, h : C D y : D E funciones. Pruebe que
(h (g f)) = (( h) g) f.
5. Si h = (A, C, G F) es una funcion, existe un conjunto B tal que f = (A, B, F)
y g = (B, C, G) son funciones? Justique su respuesta.
Secci on 4: 1. Clasique las funciones a contiunuaci on seg un inyectividad y sobreyectividad,
justicando en cada caso.
a) f : N N, denida por f(x) = x
2
.
b) g : R R, denida por g(x) = x
2
.
c) h : Q
, denida por h(x) =

1
x
. (Q
= Q0)
d) : R
R
+
, denida por (x) =

x.
e) : Q
Q, denida por (x) =

x+1
x
.
4. Si la composicion de dos funciones es sobreyectiva, ambas funciones son sobre-
yectivas? Justique su respuesta.
5. Sea f : A B una funci on. Pruebe que los enunciados a continuacion son
equivalentes.
(1) f es inyectiva
(2) X P(A), f
1
[f[X]] = X
(3) X
1
, X
2
P(A), f[X
1
X
2
] = f[X
1
] f[X
2
]
6. Sea f : A B una funci on. Pruebe f es sobreyectiva si y s olo si Y
P(B), f[f
1
[Y ]] = Y .
Secci on 5: 1. Sean f : A B una funcion. Pruebe que I
B
f = f = f I
A
.
2. Pruebe que toda proyeccion es sobreyectiva.
3. Pruebe que toda restricci on de una inyecci on es una inyeccion.
4. La restriccion de una sobreyecci on, es necesariamente una sobreyeccion? Justi-
que su respuesta.
5. La restriccion de una sobreyeccion, puede ser una sobreyecci on? Justique su
respuesta.
6. Sean f y g funciones. Pruebe que f = g si y solo si D(f) = D(g), C(f) = C(g)
y x D(f), f(x) = g(x).
Secci on 6: 1. Sea : P(A B) P(A B) la funci on denida por (X) = X
1
. Pruebe
que es biyectiva y que preserva inclusiones; es decir, si X Y , (X) (Y ).
(Observe que la notacion (X) indica que X P(A B), a diferencia de la
notaci on [X] que indica que X P(A B).)
2. Cuales son las relaciones R que verican que R
1
R. Justique su respuesta.
71
3. Cuales son las relaciones R que verican que R
1
= R. Justique su respuesta.
4. Cuales de la funciones a continuaci on poseen inversa a la izquierda, inversa a
la derecha o inversa bilateral? Justique su respuesta en ambos casos, y deter-
mine las inversas (unilaterales o bilaterales) que existen, y compruebe que estas
funciones son efectivamente inversas.
a) f : Z Z denida por f(x) = 2x + 1
b) g : Q Q denida por g(x) = 2x + 1
c) h = (Z, N, H), donde H = (x, y) Z N : x
2
= y
2
d) : Q Q denida por (x) =

x
2
1+x
2
e) : Q
Q, denida por (x) =

x+1
x
.
5. En la teora, hemos atribuido dos signicados distintos al smbolo
1
(un llamado
abuso de notaci on). Mientras que f
1
(x) indica claramente la imagen de x por
la inversa de la funcion f, f
1
[X] puede referirse tanto a la preimagen de X por
la funcion f, como a la imagen X por la inversa de la funcion f.
Pruebe que no existe confusion posible; es decir, si f : A B es una funci on
g es su inversa y X P(A), entonces f
1
[X] = g[X] (donde f
1
denota la
preimagen).
6. Sean f : A B y g : B C funciones que poseen inversas. Pruebe que g f
posee inversa y que (g f)
1
= f
1
g
1
.
7. Se dice que una funci on f : A A es idempotente en A si f f = f. Pruebe
que en cada conjunto no vaco A, existe una unica funcion idempotente que es
inyectiva.
8. Se dice que una funci on f : A A es involutiva en A si f f = I
A
. Es cierto que
en cada conjunto no vaco A existe una unica funci on involutiva que es biyectiva?
Justique su respuesta.
72
Captulo 4
Sistema Axiomatico de Morse-Kelley
73

Teoría de Conjuntos PDF

Cargado por

Copyright:

Formatos disponibles

Teoría de Conjuntos PDF

Cargado por

Información del documento

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

Teoría de Conjuntos PDF

Cargado por

Copyright:

Formatos disponibles

Teor

B (el punto indica que que se trata de union disjunta).

B no tiene sentido, pues A y B

yRx. Esto prueba que R es simetrica.

(o simplemente a si la relacion se sobreentiende). Simboli-

son dos a dos disjuntos y, como a = a

M A (1.5.8). Para probar la otra inclusi on,

M. Esto prueba que A

. Falta probar que

, debe existir a A : M = a, de manera que M = a = P

= P, lo cual completa la demostracion.

, 0 es una particion de R. Por el teorema

arbitrarios pero jos.

(1, 2), (1, 3), (2, 3) ordena totalmente a A, mientras que

2 < i. A continuacion, elijamos n Z

2. As, debe existir m Z

B (an alogamente: max

, entonces x y. Pruebe que su relacion es efectivamente de buen orden,

2 tiene sentido en R, no tiene sentido

, denida por h(x) =

Q, denida por (x) =

d) : Q Q denida por (x) =

Q, denida por (x) =

También podría gustarte