Índice general

1. Nociones de lógica 3

1.1. Lógica proposicional . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.1.1. Conectivos y tablas de verdad . . . . . . . . . . . . . . . . . . . 5

1.1.2. Proposiciones compuestas y sus tablas de verdad . . . . . . . . 7

1.1.3. Equivalencia lógica y tautologı́as . . . . . . . . . . . . . . . . . 9

1.1.4. Razonamiento deductivo válido . . . . . . . . . . . . . . . . . . 12

1.2. Lógica de predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.2.1. Traducciones en la lógica de predicados . . . . . . . . . . . . . 14

1.2.2. Interpretaciones y verdad . . . . . . . . . . . . . . . . . . . . . 16

1.2.3. Equivalencia lógica y negación de traducciones . . . . . . . . . 17

2. Conjuntos 21

2.1. Axiomas que definen conjuntos . . . . . . . . . . . . . . . . . . . . . . 21

2.2. Intersección y unión . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3. Diferencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.4. Complementación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

2.5. Diferencia simétrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.6. Potencia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.7. Producto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3. Relaciones y Funciones 47

3.1. Relaciones de equivalencia . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.2. Particiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.3. Relaciones de orden parcial . . . . . . . . . . . . . . . . . . . . . . . . 56

1
 3.4. Funciones y gráficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.5. Tipos de funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.6. Composición de funciones y funciones inversas . . . . . . . . . . . . . . 69

4. Números naturales 75

4.1. Suma y multiplicación . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.2. Principio de inducción . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

4.3. Orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

5. Combinatoria 95

5.1. Cardinalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5.2. Principios elementales de combinatoria . . . . . . . . . . . . . . . . . . 100

5.3. Ordenaciones y permutaciones . . . . . . . . . . . . . . . . . . . . . . 104

5.4. Combinaciones y expansión binomial . . . . . . . . . . . . . . . . . . . 109

2
Capı́tulo 1
Nociones de lógica
Veremos en principio algunas nociones lógicas, esto con el objetivo de tener

una base para poder desarrollar el contenido que se presenta más adelan-

te. No profundizaremos estos conceptos, sin embargo, el lector interesado

puede consultar [?] para un estudio más completo de este tema.

1.1. Lógica proposicional

Definición 1.1: Una proposición es aquella parte de una oración que puede deter-

minarse como verdadera o falsa.

Ejemplos 1.2:

Las siguientes oraciones reflejan proposiciones:

1. Cuatro es un número primo.

2. Ningún número es primo.

3. Romeo ama a Julieta.

4. Julieta es amada por Romeo.

Las siguientes frases no reflejan proposiciones:

1. ¿Quién vino a clase?.

2. Asómate al salón.

3. La mañana húmeda y frı́a.

A partir de estos ejemplos podrı́as preguntarte, si una oración (según te enseñaron

3
en la primaria) son un conjunto de palabras ordenados con alguna lógica que tienen

un sujeto y un predicado, ¿existirá alguna oración que no refleje una proposición?

Bertrand Russell propuso la siguiente oración:

“El actual Rey de Francia es calvo”

Esta oración claramente no es verdadera, pues si revisamos el conjunto de todas

las personas calvas no encontraremos al actual rey de Francia, por lo que no es cierto

que el actual rey de Francia es calvo.

Sin embargo, esta oración tampoco es falsa pues si revisamos el conjunto de todas

las personas que no son calvas tampoco encontraremos al actual rey de Francia, por

lo que no falso que el actual rey de Francia es calvo.

Ya que nos detuvimos un poco a discutir la filosofı́a de Russell, hagamos un po-

quito más de filosofı́a. ¿Por qué una oraciı́n refleja y no es una proposición? Hay,

básicamente, dos razones. Primera, dos oraciones distintas pueden expresar la misma

proposición:

“El perro es café”

“The dog is brown”

Las oraciones claramente son distintas, pero el valor de verdad de sus proposiciones

será el mismo en cualquier mundo posible.

La segunda, y relacionada con la anterior, es que una oración es una figura del

lenguaje, mientras que una proposición es un objeto lógico. En fin, regresemos a hacer

matemáticas.

Utilizaremos las letras P, Q, R, S, etc. para representar proposiciones. Abreviamos

la frase “la verdad o falsedad de la proposición P ” como “el valor de verdad de P ”. Hay

exactamente dos, y sólo dos, valores de verdad: verdadero (V) o falso (F) y ninguna

oración puede tener más de un valor de verdad (en la lógica clásica). Es decir, la lógica

que vamos a estudiar no puede estudiar ni el significado de la oración propuesta por

Russel ni de la oración “Esta oración es falsa”.

4
1.1.1. Conectivos y tablas de verdad
Los conectivos lógicos son herramientas que utilizamos para construir nuevas pro-

posiciones a partir de viejas. Adicionalmente tratan de recuperar el uso que en el

lenguaje natural hacemos de palabras como: “no”, “y” u “o”.

La siguiente es una tabla de los conectivos lógicos más utilizados y sus traducción

al lenguaje natural:

Sı́mbolo/ Conectivo Nombre de la operación Notación Significado

¬ Negación ¬P no P

∧ Conjunción P ∧Q P yQ

∨ Disyunción P ∨Q P oQ

⇒ Implicación P ⇒Q P implica Q

⇔ Doble implicación P ⇔Q P si y solo si Q

Si los operadores lógicos son maneras como se relacionan las proposiciones, y estas

están determinadas por su valor de verdad, entonces los operadores lógicos se encuen-

tran totalmente definidos por la manera como operan con los valores de verdad.

Definición 1.3: Las tablas de verdad, como ya sabes, son la manera como describi-

mos el proceso por el que se determina el valor de verdad de una proposición nueva,

creada a partir de proposiciones viejas a través de conectivos lógicos.

Siendo ası́, veamos la manera como se definen los operadores lógicos, a través de

sus tablas de verdad.

Negación. P = 9 es un número primo, ¬P = 9 no es un número primo o no es

cierto que 9 sea un número primo.

Tabla de verdad:

P ¬P

V F

F V

5
 Conjunción. P = 9 es un número impar, Q = 3 es un número primo, P ∧ Q = 9

es un número impar y 3 es un número primo.

Tabla de verdad:

P Q P ∧Q

V V V

V F F

F V F

F F F

Disyunción. P = Hoy es viernes, Q = Hoy es sábado, P ∨ Q = Hoy es viernes o

sábado.

Tabla de verdad:

P Q P ∨Q

V V V

V F V

F V V

F F F

Implicación o Condicional P = Si llego a la presidencia, Q = Bajaré las tarifas

de luz, P ⇒ Q = Si llego a la presidencia, (entonces) bajaré las tarifas de luz.

Tabla de verdad:

P Q P ⇒Q

V V V

V F F

F V V

F F V

Doble implicación o bicondicional. P = C es un cı́rculo, Q = Los puntos que

forman a C están a la misma distancia de un punto dado, P ⇔ Q = C es un cı́rculo

si y solo si los puntos que forman a C están a la misma distancia de un punto dado.

Tabla de verdad:

6
 P Q P ⇔Q

V V V

V F F

F V F

F F V

1.1.2. Proposiciones compuestas y sus tablas

de verdad
Por la sección anterior, sabemos que si P y Q son proposiciones entonces ¬P , P ∧Q,

P ∨ Q, P ⇒ Q y P ⇔ Q son proposiciones, por lo que a su vez α = (¬P ) ∧ (P ⇒ Q)

es una proposición, a este tipo de proposiciones les llamaremos compuestas. Podemos

generalizar de manera natural las tablas de verdad:

P Q P ∧Q P Q P ∨Q

P ¬P V V V V V V

V F V F F V F V

F V F V F F V V

F F F F F F

P Q P ⇒Q P Q P ⇔Q

V V V V V V

V F F V F F

F V V F V F

F F V F F V

Usamos los paréntesis como sı́mbolos de puntuación para clarificar la proposición

de la que se trata, por ejemplo, las siguientes proposiciones son distintas:

(¬P ) ∧ (P ⇒ Q), ¬(P ∧ (P ⇒ Q)), ¬((P ∧ P ) ⇒ Q).

7
Convención: la negación es el conectivo lógico más débil, es decir, si se aplica a una

sola letra de proposición puede omitirse los paréntesis. Por ejemplo, cuando escribamos

¬P ∧ Q, la proposición de la que estamos hablando es (¬P ) ∧ Q. Veamos un ejemplo:

P Q ¬P P ⇒Q ¬P ∧ (P ⇒ Q)

V V F V F

V F F F F

F V V V V

F F V V V

La construcción de estas tablas de verdad se hizo tomando en cuenta lo siguiente.

1. Se pone una columna por cada letra de proposición que aparece en la proposición

compuesta, además de una columna por cada paso en la construcción de la

proposición final.

2. Si n es el número de letras de proposición distintas que aparecen en la proposición

completa, entonces la tabla consta de 2n renglones, que corresponden a todos

los posibles valores de verdad de las letras proposicionales que aparecen.

3. Convenimos adoptar el orden lexicográfico para colocar los valores de verdad de

las letras de proposición, donde el “abecedario” es {V, F} en este orden.

Llamamos conectivo principal al último conectivo usado en la construcción de una

proposición.

Veamos que existe una proposición que captura el sentido exclusivo del “o”, es

decir, la idea es que se cumplan P o Q pero no ambos.

P Q P ∨Q P ∧Q ¬(P ∧ Q) (P ∨ Q) ∧ ¬(P ∧ Q)

V V V V F F

V F V F V V

F V V F V V

F F F F V F

8
1.1.3. Equivalencia lógica y tautologı́as
Definición 1.4: Dos proposiciones son lógicamente equivalentes si la última columna

de construcción en su tabla de verdad es igual, es decir, si las letras de proposición

involucradas están en el mismo orden, entonces los valores de verdad de la proposición

están puestos en el mismo orden en ambas tablas.

Ejemplos 1.5:

1. P ∧ (Q ∨ R) es lógicamente equivalente a (P ∧ Q) ∨ (P ∧ R) ya que

P Q R Q∨R P ∧ (Q ∨ R)

V V V V V

V V F V V

V F V V V

V F F F F

F V V V F

F V F V F

F F V V F

F F F F F

P Q R P ∧Q P ∧R (P ∧ Q) ∨ (P ∧ R)

V V V V V V

V V F V F V

V F V F V V

V F F F F F

F V V F F F

F V F F F F

F F V F F F

F F F F F F

2. P ⇔ Q es lógicamente equivalente a (P ⇒ Q) ∧ (Q ⇒ P ) ya que

9
 P Q P ⇔Q P Q P ⇒Q Q⇒P (P ⇒ Q) ∧ (Q ⇒ P )

V V V V V V V V

V F F V F F V F

F V F F V V F F

F F V F F V V V

3. ¬(P ⇒ Q) es lógicamente equivalente a P ∧ ¬Q ya que

P Q P ⇒Q ¬(P ⇒ Q) P Q ¬Q P ∧ ¬Q)

V V V F V V F F

V F F V V F V V

F V V F F V F F

F F V F F F V F

4. ¬(¬P ) es lógicamente equivalente a P .

5. ¬(P ∧ Q) es lógicamente equivalente a ¬P ∨ ¬Q.

6. ¬(P ∨ Q) es lógicamente equivalente a ¬P ∧ ¬Q.

7. ¬(P ⇔ Q) es lógicamente equivalente a (P ∧ ¬Q) ∨ (Q ∧ ¬P ).

Definición 1.6: Una tautologı́a es una proposición que es siempre verdadera sin

importar los valores de verdad que tengan las proposiciones que la componen.

Ejemplo 1.7: ((P ⇒ Q) ∧ P ) ⇒ Q es una tautologı́a.

P Q P ⇒Q ((P ⇒ Q) ∧ P ) ((P ⇒ Q) ∧ P ) ⇒ Q

V V V V V

V F F F V

F V V F V

F F V F V

Las tautologı́as son útiles, pues, como siempre son verdaderas, pueden utilizarse

en cualquier razonamiento. Revisaremos esto en la siguiente sección con más calma.

La siguiente es una lista de tautologı́as útiles:

10
 NOMBRE TAUTOLOGIA

Doble negación ¬(¬P ) ⇔ P

Tercero excluido P ∨ ¬P

No contradicción ¬(P ∧ ¬P )

Idempotencia (P ∧ P ) ⇔ P , (P ∨ P ) ⇔ P

Conmutatividad (P ∧ Q) ⇔ (Q ∧ P ), (P ∨ Q) ⇔ (Q ∨ P )

Asociatividad ((P ∧ Q) ∧ R) ⇔ (P ∧ (Q ∧ R)), ((P ∨ Q) ∨ R) ⇔ (P ∨ (Q ∨ R))

Distributividad ((P ∨ Q) ∧ R) ⇔ ((P ∧ R) ∨ (Q ∧ R)), ((P ∧ Q) ∨ R) ⇔ ((P ∨ R) ∧ (Q ∨ R))

Leyes de De Morgan ¬(P ∧ Q) ⇔ (¬P ∨ ¬Q), ¬(P ∨ Q) ⇔ (¬P ∧ ¬Q)

Transitividad ((P ⇒ Q) ∧ (Q ⇒ R)) ⇒ (P ⇒ R)

Contrapuesta (P ⇒ Q) ⇔ (¬Q ⇒ ¬P )

Observa que en todas estas tautologı́as (excepto la segunda, la tercera y la penúlti-

ma) el conectivo principal es una doble implicación, ası́ que el hecho de que sean tau-

tologı́as expresa que las expresiones de los dos lados son equivalentes, por eso se

conocen como reglas de equivalencia lógica (y por eso están en negritas).

Definición 1.8: Una contradicción es una proposición que siempre es falsa indepen-

dientemente de los valores de verdad que tengan las proposiciones que la componen.

Ejemplo 1.9: P ∧ ¬P es una contradicción.

P ¬P P ∧ ¬P

V F F

F V F

Las contradicciones van a ser muy útiles para uno de nuestros métodos de prueba.

11
1.1.4. Razonamiento deductivo válido
Definición 1.10: Un razonamiento deductivo es una colección finita de proposicio-

nes φ1 , φ2 , . . . , φn llamadas premisas o hipótesis, junto con una proposición ψ, llamada

conclusión, respecto de la cual se afirma que se deriva de las premisas. Decimos que un

razonamiento deductivo es válido si y solo si de la verdad de las premisas se sigue la

verdad de la conclusión. Es decir, un razonamiento es válido si y solo si no es posible

que las premisas sean verdaderas y la conclusión falsa.

Lo anterior lo denotamos por

φ1

φ2
...

φn

ψ.

Puedes preguntarte ¿por qué pedimos que la colección de proposiciones sea finita?

¿Qué pasa con las pruebas por inducción?

Los siguientes razonamientos deductivos son válidos y se conocen como reglas de

inferencia lógica.

• Modus Ponens.
φ

φ⇒ψ

• Modus Tolens.
¬ψ

φ⇒ψ

¬φ

12
 • Silogismo Hipotético.
φ⇒ψ

ψ⇒χ

φ⇒χ

• Silogismo Disyuntivo.
φ∧ψ

¬φ

Puedes revisar que todos estos razonamientos son tautologı́as si interpretamos la

conclusión lógica como la implicación.

Ejemplos 1.11:

1. El siguiente es un razonamiento deductivo no válido

P ⇒Q

Para convencernos de ello, consideremos los valores de verdad F y V, para P y

Q respectivamente, obtenemos que las premisas son verdaderas y la conclusión

es falsa.

2. El siguiente es un razonamiento deductivo válido

P ∨Q

P ∨ ¬Q

Para convencernos de ello, supongamos que el valor de verdad de P es falso.

Como P es falsa, para que la primera premisa sea verdadera, se tiene que Q debe

ser verdadera. Luego, como Q es verdadera se tiene que ¬Q es falsa. Entonces,

13
 P ∨ ¬Q es falsa ya que ambas proposiciones lo son. Por lo que, no existe alguna

configuración de los valores de verdad para P y Q donde las premisas sean

verdaderas y la conclusión sea falsa. Esto es, el razonamiento anterior es válido.

1.2. Lógica de predicados

En esta sección analizaremos razonamientos deductivos del tipo

Todos los hombres son mortales

Sócrates es hombre (1.1)

Sócrates es mortal.

1.2.1. Traducciones en la lógica de predicados

El sı́mbolo P (x) será la representación de una propiedad relativos al objeto indeter-

minado x, perteneciente a cierto universo. A este tipo de representación la llamaremos

un predicado.

Ejemplo 1.12: Si a lo que nos referimos es a los seres vivos y la propiedad de ser

hombre: P (x) significa “el ser vivo x es hombre”.

Es importante notar que “el ser vivo x es hombre” no refleja una proposición, pues

no está especificado qué ser vivo es x, por lo que no podemos decir si lo que significa

la oración es verdadero o falso. Sin embargo, para cada asignación particular dada

a x, el enunciado resultante sı́ es una proposición, por ejemplo, P (Sócrates) significa

“Sócrates es hombre” lo cual es verdadero, mientras que P (King Kong) que significa

“King Kong es hombre” es falsa.

Introducimos los sı́mbolos ∀, llamado el cuantificador universal y ∃, llamado el

cuantificador existencial . De esta forma se tiene que la expresión: “Para todo x, se

cumple P (x)” se traduce como ∀ xP (x) y la expresión “existe x tal que cumple P (x)”

14
se traduce como ∃ xP (x). En el primer ejemplo, si el universo son los seres vivos,

∀ xP (x) se traduce como “Todos los seres vivos son hombres” o como “Cualquier ser

vivo es hombre”. Por otro lado, ∃ xP (x) se traduce como “Existe un ser vivo, tal que

es hombre” o como “Hay seres vivos que son hombres” o también como “Algún ser

vivo es hombre”.

Decimos que un predicado cuantificado universalmente ∀xP (x) es verdadero si son

verdaderas todas las proposiciones P (a) para cualquier a fija en nuestro universo y es

falso si hay al menos un individuo a fijo del universo tal que P (a) es falsa. Diremos

que un predicado cuantificado existencial ∃xP (x) es verdadero si hay al menos un

individuo a en nuestro universo tal que P (a) sea verdadera y es falso si para cualquier

individuo a en el universo, la proposición P (a) es falsa.

Veamos algunos ejemplos.

• Consideremos el universo de los seres vivos. Usemos P (x) para representar “x es

hombre” y Q(x) para representar “x es mortal”. Ası́, “si x es hombre entonces x es

mortal” lo podemos traducir como P (x) ⇒ Q(x) y el pedazo que dice cualquiera que

sea el ser vivo” como ∀x. De esta manera, la traducción de “Todos los hombres son

mortales” resulta ∀x(P (x) ⇒ Q(x)). Ası́, la traducción de (1.1) queda de la siguiente

manera:
∀x(P (x) ⇒ Q(x))

P (Sócrates)

Q(Sócrates)

• Consideremos la siguiente proposición: “Hay primos pares”. Para traducirla po-

demos fijar a los números enteros como nuestro universo, a R(x) para representar

la propiedad de ser primo, y a S(x) para representar la propiedad de ser par. Sirve

enunciar la proposición de otra manera: Hay números enteros que son primos y pares.

Ası́, la traducción correcta es: ∃x(R(x) ∧ S(x)).

• Consideremos la siguiente proposición: “Todo primo es impar o no existe un

impar negativo”. Ası́, la traducción queda: ∀x(P (x) ⇒ I(x)) ∨ ¬∃x(I(x) ∧ N (x)),

donde P (x) significa “x es primo”, I(x) significa “x es impar” y N (x) significa “x es

15
negativo”.

• Se pueden presentar también predicados con más de una variable, como por

ejemplo Q(x, y) que signifique “x es divisor de y”. En este ejemplo la proposición

∃x∀y(Q(x, y)) se traduce como “Existe un número entero tal que es divisor de todos

los números enteros” la cual es verdadera pues el 1 divide a todos los enteros.

1.2.2. Interpretaciones y verdad

Sean α y β cualesquiera proposiciones escritas en el lenguaje de la Lógica de predi-

cados. Dada una interpretación para ellas, es decir, un universo y una traducción

del significado de todos los predicados que aparecen en α y en β con individuos de ese

universo, la asignación de valores de verdad a esas proposiciones se realiza siguiente

las siguientes reglas:

1. ¬α es verdadera respecto a la interpretación dada si y solo si α es falsa respecto

a esa interpretación;

2. α ∧ β es verdadera respecto a la interpretación dada si y solo si α y β son ambas

verdaderas respecto a esa interpretación;

3. α ∨ β es verdadera respecto a esa interpretación dada si y solo si α es verdadera,

o β es verdadera, o ambas son verdaderas respecto a esa interpretación;

4. α ⇒ β es falsa respecto a la interpretación dada si y solo si α es verdadera y β

es falsa respecto a esa interpretación;

5. α ⇔ β es verdadera respecto a la interpretación dada si y solo si α y β son

ambas verdaderas, o α y β son ambas falsas respecto a esa interpretación;

6. ∀ x α es verdadera respecto a la interpretación dada si y solo si para todos los

individuos en el universo de esa interpretación, α es verdadera respecto a esa

interpretación y respecto a cada uno de esos individuos;

7. ∃ x α es verdadera respecto a la interpretación dada si y solo si hay al menos un

individuo en el universo de esa interpretación tal que α es verdadera respecto a

16
 esa interpretación y respecto a ese individuo.

1.2.3. Equivalencia lógica y negación de traduc-

ciones
De manera similar a como definimos equivalencia lógica para la Lógica proposi-

cional, podemos decir que dos proposiciones α y β de la Lógica de predicados son

lógicamente equivalentes si y solo si para cualquier interpretación la verdad o falsedad

de α y β coincide. En particular, los cuantificadores se relacionan con la la negación

de la siugiente manera.

¬(∀xα) es lógicamente equivalente a ∃x¬α

¬(∃xα) es lógicamente equivalente a ∀x¬α

Definir ası́ la negación de ambos operadores no sólo es elegante y sencillo, sino que

respeta la manera como, en el lenguaje natural, usammos los cuantificadores. Veamos

algunos ejemplos.

• Consideremos la proposición: “Todo entero admite un inverso aditivo”. Fijamos

nuestro universo como los números enteros y usamos P (x, y) para representar “x+y =

0”. Entonces, la proposición se traduce como ∀x∃yP (x, y) o bien ∀x∃y(x + y = 0). La

negación de esta proposición es

¬(∀x∃y(x + y = 0)), que es lógicamente equivalente a

∃x(¬∃y(x + y = 0)), que es lógicamente equivalente a

∃x∀y¬(x + y = 0), que es lógicamente equivalente a

∃x∀y(x + y ̸= 0),

cuya traducción es “Existe un entero cuya suma con cualquier otro, es distinta de

cero”.

• Consideremos la proposición: “Hay enteros pares que son primos”. Fijemos nues-

tro universo como los números enteros y usamos P (x) para representar “x es par” y

17
Q(x) para representar “x es primo”. La traducción simbólica de esta proposición es

∃x(P (x) ∧ Q(x)). La negación de esta proposición es

∀x(¬(P (x) ∧ Q(x))), que es lógicamente equivalente a

∀x(¬P (x) ∨ ¬Q(x)),

cuya traducción es “Cualquiera que sea el entero, no es par o no es primo”.

• Consideremos la proposición: “Todos las rectas son paralelas”. Fijemos nuestro

universo como los objetos geométricos y usamos P (x) para representar “x es una

recta” y Q(x, y) para representar “x es paralela a y”. La traducción simbólica de esta

proposición es ∀x∀y((P (x) ∧ P (y)) ⇒ Q(x, y)). La negación de esta proposición es

∃x¬∀y((P (x) ∧ P (y)) ⇒ Q(x, y)), que es lógicamente equivalente a

∃x∃y¬((P (x) ∧ P (y)) ⇒ Q(x, y)), que es lógicamente equivalente a

∃x∃y((P (x) ∧ P (y)) ∧ ¬Q(x, y)),

cuya traducción es “Existe dos rectas que no son paralelas”.

• Consideremos la proposición: “Todos los triángulos son equiláteros si y solo

si son isósceles”. Fijemos nuestro universo como los triángulos y usamos P (x) para

representar “x es equilatero” y Q(x) para representar “x es isósceles”. La traducción

simbólica de esta proposición es ∀x(P (x) ⇔ Q(x)). La negación de esta proposición

es

∃x¬(P (x) ⇔ Q(x)), que es lógicamente equivalente a

∃x¬((P (x) ⇒ Q(x)) ∧ (Q(x) ⇒ P (x))), que es lógicamente equivalente a

∃x(¬(P (x) ⇒ Q(x)) ∨ ¬(Q(x) ⇒ P (x))), que es lógicamente equivalente a

∃x((P (x) ∧ ¬Q(x)) ∨ (Q(x) ∧ ¬P (x)))

cuya traducción es “Existe un triángulo tal que o bien es equilátero y no es isósceles,

o bien es isósceles y no equilátero”.

Recordemos que un razonamiento deductivo es válido si y solo si suponiendo la

18
verdad de las premisas se obtiene la verdad de la conclusión. Veamos que el razona-

miento 1.1 es válido. Supongamos que ∀x(P (x) ⇒ Q(x)) y P (Sócrates) son verdaderas

donde usamos P (x) para representar “x es hombre” y Q(x) representa “x es mortal”.

Como ∀x(P (x) ⇒ Q(x)) es verdadero, P (a) ⇒ Q(a) es verdadero para cualquier in-

dividuo a del universo, en particular P (Sócrates) ⇒ Q(Sócrates) es verdadero. Siendo

ası́, tenemos que P (Sócrates) es verdadero y P (Sócrates) ⇒ Q(Sócrates) es verdadero,

por Modus ponens tenemos que Q(Sócrates) es verdadero. Por lo tanto, el razona-

miento deductivo en 1.1 es válido.

19
20
Capı́tulo 2
Conjuntos
“Un conjunto es una colección de objetos definidos de nuestra percepción

o nuestro pensamiento” Georg Cantor.

En este capı́tulo analizamos teorı́a básica de conjuntos, la cual representa

el fundamento de la matemática moderna.

Revisaremos la definición de contención y pertenencia, y hacemos notar

la diferencia entre ambos conceptos con ejemplos.

También definimos algunas operaciones básicas entre conjuntos : inter-

sección, unión (ası́ como sus versiones generalizadas), diferencia, comple-

mentación, diferencia simétrica, potencia y producto cartesiano, adiciona-

lemte estudiamos el comportamiento e interacción entre ellas.

2.1. Axiomas que definen conjuntos

En matemáticas cuando se introduce un nueva teorı́a, el primer paso a realizar es

definir claramente los objetos de esta teorı́a. Dado que la teorı́a de conjuntos funcio-

na como el fundamento del resto de teorı́as matemáticas serı́a de esperarse que esta

iniciara por definir de la manera más clara posible sus objetos, pues de ofrecer una de-

finición ambigüa, esto condenarı́a al resto de objetos matemáticos a tener definiciones

igual o más ambiguas.

Paradójicamente, no ofreceremos definición de lo que es un conjunto. Esto se de-

be a que para ofrecer una definición es necesario partir de un concepto más básico

a partir del cual definir. Pero, dado que en matemáticas los conjuntos son los con-

21
ceptos más básicos estos no pueden ser definidos de esta manera. Por lo tanto, solo

diremos de manera intuitiva que un conjunto es una colección de objetos. En esta

clase usarémos letras mayúsculas A, B, C, . . . para los conjuntos, minúsculas a, b, c, . . .

para los elementos y utilizaremos llaves para describirlos. Por ejemplo, A = {a, b, c}

denotará al conjunto A cuyos elementos son a, b, c.

La noción a pertenece a A o (equivalentemente) a es elemento de A, va a ser una

noción primitiva en nuestra teorı́a. Esto significa que, por un lado, no la vamos a

definir, y que, por la otra, representa la noción más básica de conjuntos, a partir de

la cual se definen todas las otras. Denotamos esta relación por a ∈ A.

Sin embargo, aunque no vamos a definir la relación pertenencia, sı́ vamos a decir

qué reglas cumple, a estas reglas se le conocen como los axiomas de la teorı́a de

conjuntos.

A continuación presentamos los axiomas que utilizaremos a lo largo de esta sección.

Considera estos axiomas como propiedades que todo conjunto satisface por definición.

Es decir, estas propiedades son necesariamente ciertas sin necesitar ser demostradas.

1. Axioma de Extensionalidad: Dos conjuntos son iguales si y solo si tienen

los mismos elementos. a ∈ B denotará “a pertenece a B”. En caso contrario,

escribiremos a ∈
/ B. Es decir, A = B si y solo si ∀a (a ∈ A ⇔ a ∈ B).

2. Axioma del Vacı́o: Existe un conjunto que carece de elementos. El sı́mbolo

∅ se usará para denotar al conjunto que no tiene elementos, este conjunto es

llamado el conjunto vacı́o.

3. Axioma de separación: Si A es un conjunto y P (x) un predicado (propiedad)

entonces la colección de los x ∈ A que cumplen P (x) es un conjunto. Este

conjunto se denotará por {x ∈ A : P (x)}.

Veamos unos ejemplos de cómo usar los axiomas 1 y el 3.

Por axioma de extensionalidad si A = {a, b, c} y {a, b, c, a} entonces A = B.

Por axioma de separación si Z es un conjunto y P (x) la propiedad ”x es par”,

entonces la colección de todos los enteros pares, P = {z ∈ Z : P (z)}, es un conjunto.

22
Definición 2.1: Decimos que un conjunto es unitario si únicamente tiene un ele-

mento. Esto es, B es un conjunto unitario si y solo si existe a tal que B = {a}, es

decir, B = {x : x = a}.

Observación 2.2: ∅ =
̸ {∅} por el Axioma de Extensionalidad ya que ∅ no tiene

elementos y {∅} tiene uno.

Ejemplos 2.3:

1. El conjunto de los números naturales N := {0, 1, 2, 3, . . .}.

2. El conjunto de los números enteros Z := {. . . , −3, −2, −1, 0, 1, 2, 3, . . .}.

3. Sea el conjunto A = {2, 4, 6, 8}. Entonces, 6 ∈ A y 5 ∈

/ A.

4. Sea A = {1, 3, 5, 7, . . . , 2n + 1, . . .}, el conjunto de los naturales impares. Enton-

ces, 15 ∈ A y 20 ∈
/ A.

5. El conjunto de las letras de la palabra Álgebra es {a, l, g, e, b, r}.

6. El conjunto de números reales, denotado por R.

7. El plano cartesiano R2 := {(x, y) : x, y ∈ R};

8. Y = {x ∈ Z : x2 = 1} = {1, −1};

9. D el conjunto de número racionales mayores que 2 y menores o iguales a 3.

D = {x ∈ Q : x > 2 ∧ x ≤ 3} = {x ∈ Q : 2 < x ≤ 3};

10. {1, 3, 5, 7, . . .} = {n ∈ N : n es impar} = {n ∈ N : n = 2m + 1, m ∈ N};

11. {1, 4, 9, . . . , m2 , . . .} = {n ∈ N : n = m2 , m ∈ N};

12. {0, 2, 4, 6, 8, 10} = {n ∈ N : 0 ≤ n ≤ 10 ∧ n es par}.

Definición 2.4: Sean A y B dos conjuntos. Decimos que A es un subconjunto de B

(o que A está contenido en B), denotado por A ⊆ B (o bien, por B ⊇ A), si cada

elemento de A es también elemento de B. Es decir:

A ⊆ B si y solo si ∀x (x ∈ A ⇒ x ∈ B).

Si A no es un subconjunto de B, escribimos A ⊈ B (o bien, B ⊉ A), es decir,

23
A ⊈ B si y solo si ∃x(x ∈ A ∧ x ∈
/ B).

Ejemplos 2.5:

1. Sean A = {n ∈ N : n ≤ 10}, B = {1, 2, 5, 7, 9} y C = {2, 4, 6, 8, 10}. Entonces,

B ⊆ A, C ⊆ A, B ⊈ C, C ⊈ B, A ⊈ B y A ⊈ C;

2. Sean [0, 1] = {x ∈ R : 0 ≤ x ≤ 1},

[0, 1) = {x ∈ R : 0 ≤ x < 1} y

(0, 1) = {x ∈ R : 0 < x < 1}.

Entonces, (0, 1) ⊆ [0, 1) ⊆ [0, 1] y [0, 1] ⊈ [0, 1) ⊈ (0, 1);

3. Si A = {golondrinas}, B = {aves} y C = {reptiles}, entonces A ⊆ B y B ⊈ C;

4. Si A = {n ∈ N : 1 ≤ n ≤ 7}, B = {2, 3, 7} y C = {2, 3, 8}, entonces B ⊆ A y

B ⊈ C;

5. Si z, w ∈ L, donde L es una recta en R2 , y A = {t ∈ L : t ∈ zw}, donde zw es

el segmento en L que une a z con w, entonces z ∈ L y A ⊆ L;

6. En geometrı́a euclidiana, todo punto del segmento AB pertenece a la recta de-

−→ −→
terminada por A y B, denotada por AB. Entonces, AB ⊆ AB. Los elementos
−→ −→
de AB son puntos, no segmentos, por lo que AB ∈
/ AB.

¡Pertenenencia y contención no son equivalentes!.

Lema 2.6: Sea X un conjunto cualquiera. Entonces ∅ ⊆ X.

Demostración. Sea X un conjunto cualquiera. Tenemos que demostrar que ∅ ⊆ X;

esto es, ∀ x(x ∈ ∅ ⇒ x ∈ X). Dado que al antecedente, x ∈ ∅, es falso para todo x ya

que ∅ no tiene elementos se sigue que la implicación x ∈ ∅ ⇒ x ∈ X es verdadera para

todo x. Por lo tanto, se cumple que ∀ x(x ∈ ∅ ⇒ x ∈ X) y ası́ ∅ ⊆ X.

En particular, tenemos ∅ ⊆ ∅, sin embargo, ∅ ∈

/ ∅ pues el vacı́o no tiene elementos.

Ejemplo 2.7: Sea D = {{∅}, {{∅}}}. Entonces,

24
 ∅∈
/D y ∅⊆D

{∅} ∈ D y {∅} ⊈ D

{{∅}} ∈ D y {{∅}} ⊆ D

{{{∅}}} ∈
/D y {{{∅}}} ⊆ D.

Observación 2.8: Por el Axioma de Extensionalidad, A = B si y solo si A ⊆ B y

B ⊆ A.

Ejemplo 2.9: D = {x ∈ R : x2 = 2x} y E = {x ∈ R : (x − 2)x = 0} son iguales

como conjuntos.

Definición 2.10: Si A es un subconjunto de B pero no es igual a B, escribimos

A & B y decimos que A está contenido propiamente en B.

En este caso, como A ⊆ B y A ̸= B, se tiene que B ⊈ A. Esto es, A & B significa

que todo elemento de A es un elemento de B pero existe un elemento de B que no es

elemento de A.

Ejemplo 2.11: Como (0, 1) ⊆ [0, 1) ⊆ [0, 1] y [0, 1] ⊈ [0, 1) ⊈ (0, 1) concluimos que

(0, 1) & [0, 1) & [0, 1].

Teorema 2.12: La contención tiene las siguientes propiedades.

1. Reflexividad: Todo conjunto está contenido en si mismo, es decir, para cualquier

conjunto A se tiene que A ⊆ A.

2. Transitividad: Si A, B y C son conjuntos tales que A ⊆ B y B ⊆ C entonces

A ⊆ C.

3. Antisimetrı́a: Si A y B son conjuntos tales que A ⊆ B y B ⊆ A entonces A = B.

Demostración. Sean A, B y C conjuntos cualesquiera.

25
 1. Tenemos que demostrar que ∀ x(x ∈ A ⇒ x ∈ A). Notemos que siempre que

se cumpla el antecedente se tiene que el consecuente también se cumple. Por lo

que, el enunciado ∀ x(x ∈ A ⇒ x ∈ A) es verdadero y ası́ A ⊆ A.

2. Supongamos que A ⊆ B y B ⊆ C. Veamos que ∀ x(x ∈ A ⇒ x ∈ C), es decir,

probemos que todo elemento de A pertenece a C. Como se debe probar que la

propiedad es cierta para todo elemento de A, consideremos un elemento a ∈ A

arbitrario. Luego, por hipótesis A ⊆ B, a ∈ B. Ahora bien, por la segunda

contención B ⊆ C, tenemos que a ∈ C. Por lo tanto, la contención A ⊆ C se

cumple.

3. Se sigue de la Observación 2.8.

Teorema 2.13: El conjunto vacı́o tiene las siguientes propiedades:

1. El conjunto vacı́o está contenido en cualquier conjunto.

2. El conjunto vacı́o es único.

3. Sea A cualquier conjunto. Si A ⊆ ∅ entonces A = ∅.

Demostración.

1. Es el Lema 2.6.

2. Supongamos que ∅′ es otro conjunto que carece de elementos. Al igual como en la

prueba del Lema 2.6, se puede demostrar que ∅′ ⊆ X para cualquier conjunto X.

En particular, como ∅ y ∅′ están contenidos en cualquier conjunto (ver también el

Lema 2.6), se tiene que ∅ ⊆ ∅′ y ∅′ ⊆ ∅. Por lo que, ∅ = ∅′ por el Teorema 2.12(3).

3. Como A ⊆ ∅ y ∅ ⊆ A por el Lema 2.6 se tiene por el Teorema 2.12(3) que A = ∅.

Para terminar esta sección vale la pena tener una discusión. Por razones relacio-

nadas con el famosı́simo conjunto de Russel, la colección de todos los conjuntos No

es un conjunto. Debido a esta esto, cuando estemos considerando una colección de

26
elementos (o de conjuntos), siempre debemos especificar a qué conjunto pertenecen

todo ellos (pues si no corremos el riesgo de estar hablando de la colección de todos los

conjuntos).

Siendo ası́, siempre especificaremos, al trabajar con conjuntos, que estamos traba-

jando con el conjunto universal U , el cual no es la colección de todos los conjuntos

y puede variar dependiendo de dónde estemos trabajando. Por ejemplo, en cálculo el

conjunto universal es R, mientras que en geometrı́a analı́tica (usualmente) es R2 .

En ocasiones no escribiremos a dicho conjunto (cuando sea evidente que se está

haciendo referencia a él) para no distraer al lector

2.2. Intersección y unión

Ahora que ya definición las nociones más básicas de conjuntos vamos a empezar a

definir las operaciones que se pueden realizar entre conjuntos.

Definición 2.14: Sean A y B dos conjuntos.

1. La intersección de A y B, la cual denotamos por A ∩ B, es el conjunto cuyos

elementos pertenecen a ambos, esto es,

A ∩ B := {x ∈ U : (x ∈ A) ∧ (x ∈ B)}.

2. La unión de A y B, la cual denotamos por A∪B, es el conjunto cuyos elementos

pertenecen a alguno de ellos, esto es,

A ∪ B := {x ∈ U : (x ∈ A) ∨ (x ∈ B)}.

Definición 2.15: Los conjuntos A y B son ajenos si y solo si su intersección es

vacı́a, es decir, A ∩ B = ∅.

27
Ejemplos 2.16:

1. Sean E el conjunto de elefantes, M el conjunto de mamı́feros y G el conjunto de

las gallinas. Entonces, E ∩ M = E, M ∩ G = ∅, G ∩ E = ∅ y E ∪ M = M ;

2. Sean P = {x ∈ N : x es par}, I = {x ∈ N : x es impar} y L = {x ∈ N :

x es primo}. Entonces, P ∩ I = ∅, P ∩ L = {2}, I ∩ L es el conjunto de todos los

números naturales primos que no sean el 2, P ∪ I = N.

3. Sean R y S dos rectas en un plano. Podemos pensar en estas rectas como con-

juntos cuyos elementos son los puntos que las conforman. Si R y S son ajenas,

entonces R y S son paralelas y distintas. Si R ∩ S ̸= ∅, entonces hay dos posi-

bilidades: R ∩ S tiene un solo elemento, un punto del plano; o bien, R = S, es

decir, R ∩ S = R = S.

Teorema 2.17: La intersección y la unión tienen las siguientes propiedades.

1. Idempotencia. Para todo conjunto A, se tiene que A ∩ A = A y A ∪ A = A.

2. Asociatividad. Para cualesquiera conjuntos A, B y C, se tiene que

(A ∩ B) ∩ C = A ∩ (B ∩ C) y

(A ∪ B) ∪ C = A ∪ (B ∪ C).

3. Conmutatividad. Para cualesquiera conjuntos A y B, se tiene que

A∩B =B∩A y

A ∪ B = B ∪ A.

4. El neutro para la intersección es el conjunto universal. Sea A un sub-

conjunto del conjunto universal U . Entonces, A ∩ U = A.

5. El neutro para la unión es el conjunto vacı́o. Para cualquier conjunto A

se tiene que A ∪ ∅ = A.

Observación 2.18: Una consecuencia de la propiedad de asociatividad del Teorema

anterior es que para denotar la intersección o la unión de una cantidad finita de

conjuntos, no es necesario escribir los paréntesis.

28
Proposición 2.19: Para cualesquiera conjuntos A y B, se tiene que

A ∩ B = A si y solo si A ⊆ B si y solo si A ∪ B = B.

Demostración. Ejercicio.

Hasta ahora hemos trabajado con la intersección finita y la unión finita, ahora

veremos las versiones generalizadas de estas operaciones. Estas versiones recuperan la

manera como el cuantificador universal generaliza al operador conjunción y como el

cuantificador existencial generalizar al operador disyunción.

Definición 2.20: Sean I un conjunto de ı́ndices y {Ai }i∈I una familia de conjuntos

(es decir, Ai es un conjunto para cada i ∈ I). Definimos la intersección de {Ai }i∈I

como
\
Ai := {x : ∀ i ∈ I (x ∈ Ai )}.
i∈I

Si I es un conjunto finito, entonces {Ai }i∈I = {A1 , A2 , . . . , An } consiste de un número

finito de conjuntos, entonces esta intersección generalizada coincide con la intersección

que estudiamos inicialmente A1 ∩ A2 ∩ · · · ∩ An .

Ejemplos 2.21:

1. Sean A1 = {1, 2, 3, 4}, A2 = {2, 3, 4, 5}, A3 = {3, 4, 5, 6}, A4 = {4, 5, 6, 7} y A5 =

T
{5, 6, 7, 8}. Sean I = {1, 2, 3, 4} y J = {1, 2, 3, 4, 5}. En este caso, i∈I Ai = {4}
T
y j∈J Aj = ∅;

2. Para cada n ∈ N+ , sea An = [−n, n] ⊆ R. Entonces, n∈N+ An = [−1, 1] y

T

T
n∈N An = {0}.

Proposición 2.22: Sean I un conjunto y {Ai }i∈I una familia de conjuntos. Enton-

ces, la intersección generalizada tiene las siguientes propiedades:

T
1. i∈I Ai ⊆ Aj para todo j ∈ I.
T
2. Si para alguna j ∈ I se tiene que Aj = ∅ entonces i∈I Ai = ∅.

29
Demostración. Sean I un conjunto y {Ai }i∈I una familia de conjuntos.
T
1. Sea x ∈ i∈I Ai y j ∈ I. Entonces, x ∈ Ai para todo i ∈ I. En particular,

x ∈ Aj . Por lo tanto, tenemos la contención.

T
2. Probemos la implicación por contrapuesta; esto es, veamos que si i∈I Ai ̸= ∅

entonces Ai ̸= ∅ para todo i ∈ I.

T T
Supongamos que i∈I Ai ̸= ∅. Entonces, existe x ∈ i∈I Ai y por definición de

intersección, se tiene que x ∈ Ai para todo i ∈ I. Luego, Ai ̸= ∅ ya que tiene al

menos un elemento (en este caso x). Por lo tanto, la implicación se sigue.

Definición 2.23: Sean I un conjunto de ı́ndices y {Ai }i∈I una familia de conjuntos.

Definimos la unión de {Ai }i∈I como

[
Ai := {x : ∃i ∈ I (x ∈ Ai )}.
i∈I

Si I es un conjunto finito, entonces {Ai }i∈I = {A1 , A2 , . . . , An } consiste de un

número finito de conjuntos, entonces esta unión generalizada coincide con la unión

que estudiamos inicialmente A1 ∪ A2 ∪ · · · ∪ An .

Ejemplos 2.24:
S S
1. Para cada n ∈ N, sea An = {n}. Entonces, n∈N An = n∈N {n} = N.

2. Para cada n ∈ N+ , sea An = [−n, n] ⊆ R. Entonces,

[ [
An = [−n, n] = R.
n∈N+ n∈N+

Proposición 2.25: Sean I un conjunto y {Ai }i∈I una familia de conjuntos. Enton-

ces,
S
Aj ⊆ i∈I Ai para toda j ∈ I.

Demostración. Sea j ∈ I y x ∈ Aj . Entonces, x satisface que pertenece a Ai para

30
 S
algún i ∈ I. Luego, x ∈ i∈I Ai por la definición de unión.

Proposición 2.26(Leyes distributivas): Sean I y B conjuntos y {Ai }i∈I una

familia de conjuntos. Para cualquier conjunto B se cumple lo siguiente:

S S
1. ( i∈I Ai ) ∩ B = i∈I (Ai ∩ B).
T T
2. ( i∈I Ai ) ∪ B = i∈I (Ai ∪ B).

Demostración. Sean I y {Ai }i∈I una familia de conjuntos.

S S
1. (⊆) Sea x ∈ ( i∈I Ai ) ∩ B. Entonces, por definición de intersección, x ∈ i∈I Ai

y x ∈ B. Luego, por la definición de unión tenemos que x ∈ Ai para algún i ∈ I

S
de donde obtenemos que x ∈ Ai ∩B para algún i. Por lo tanto, x ∈ i∈I (Ai ∩B).
S
(⊇) Sea x ∈ i∈I (Ai ∩ B). Entonces, x ∈ Ai ∩ B para algún i ∈ I. Por la

definición de intersección tenemos que x ∈ Ai y x ∈ B para algún i ∈ I. Luego,

S
se cumple que x ∈ Ai para algún i y x ∈ B, es decir, x ∈ i∈I Ai y x ∈ B. Por
S
lo tanto, x ∈ ( i∈I Ai ) ∩ B debido a la definición de intersección.

Como se cumplen ambas contenciones entre dichos conjuntos, por el Axioma de

Extensionalidad se sigue que son iguales.

2. Se prueba de manera similar al inciso anterior.

2.3. Diferencia
Definición 2.27: Sean A y B conjuntos (subconjuntos de un conjunto universal U ).

La diferencia de A menos B, denotada por A \ B, es el conjunto de los elementos de

A que no son elementos de B, es decir,

A \ B := {x ∈ U : (x ∈ A) ∧ (x ∈
/ B)}

31
.

Observación 2.28: Como A y B son subconjuntos de U se tiene que x ∈ A \ B si

y solo si x ∈ A y x ∈
/ B.

Ejemplos 2.29:

1. Sean A = {2, 3} y B = {2, 4, 5}. Entonces, A \ B = {3} y B \ A = {4, 5}. Por lo

que, la diferencia de conjuntos no es conmutativa.

2. Sean R el conjunto de números reales y P = {π}. Entonces, R \ P = {x ∈ R :

x < π ∨ x > π} y P \ R = ∅.

3. Sean P = {x ∈ N : x es par},

I = {x ∈ N : x es impar} y

L = {x ∈ N : x es primo}. Entonces,

P\L = {x ∈ N : x es par y x no es primo} = {x ∈ N : x es par y x ̸= 2} = P\{2},

L \ P = L \ {2},

P \ I = P,

I\P=I y

L \ I = {2}.

I\I=∅

4. Sean A = [1, ∞) y B = (−∞, 3]. Entonces, A \ B = (3, ∞) y B \ A = (−∞, 1).

Teorema 2.30: La diferencia de conjuntos tienen las siguientes propiedades.

1. El neutro por la derecha es el conjunto vacı́o. Para cualquier conjunto A,

se tiene que A \ ∅ = A.

2. El inverso de un conjunto es él mismo. Para cualquier conjunto A, se tiene

que A \ A = ∅.

3. Para cualquier conjunto A, se tiene que ∅ \ A = ∅.

32
Demostración. Sea A un conjunto cualquiera.

1. De la definición de diferencia, x ∈ A \ ∅, si y solo si, x ∈ A y x ∈

/ ∅. Como x ∈
/∅

para cualquier x se tiene que x ∈ A y x ∈

/ ∅, es lógicamente equivalente a x ∈ A.

Por lo tanto, x ∈ A \ ∅, si y solo si, x ∈ A, es decir, A \ ∅ = A.

2. Por reducción al absurdo, supongamos que existe un conjunto A tal que A\A ̸= ∅.

Entonces, existe un elemento x ∈ A \ A. Luego, por la definición de diferencia,

x∈Ayx∈
/ A lo cual es absurdo. Por lo tanto, para cualquier conjunto A se

cumple que A \ A = ∅.

3. Por reducción al absurdo, supongamos que existe un conjunto A tal que ∅\A ̸= ∅.

Entonces, existe un elemento x ∈ ∅ \ A. Por lo que, x ∈ ∅ y x ∈

/ A lo cual es una

contradicción debido a que el vacı́o no tiene elementos. Por lo tanto, ∅ \ A = ∅.

Proposición 2.31: Para cualesquiera conjuntos A y B, se tiene que

A \ B = A si y solo si A ∩ B = ∅.

Demostración. Sean A y B conjuntos cualesquiera.

(⇒) Por contradicción; supongamos A \ B = A y A ∩ B ̸= ∅. Entonces, existe

x ∈ A ∩ B y por definición de intersección x ∈ A y x ∈ B. Ahora bien, dado que

A = A \ B tenemos x ∈ A \ B, es decir, x ∈ A y x ∈
/ B lo cual es una contradicción

ya que x ∈ B.

(⇐) Supongamos que A ∩ B = ∅. Veamos que A \ B = A. La contención A \ B ⊆ A

es clara. Por otra parte, para x ∈ A tenemos que x ∈

/ B debido a A ∩ B = ∅. Luego,

x ∈ A ∩ B c = A \ B si x ∈ A. Por lo que, la contención A ⊆ A \ B es cierta.

Concluimos entonces que A \ B = A si y solo si A ∩ B = ∅.

Proposición 2.32: Sean I, B conjuntos y {Ai }i∈I una familia de conjuntos. Enton-

ces,

33
 T S
1. B \ ( i∈I Ai ) = i∈I (B \ Ai );
S T
2. B \ ( i∈I Ai ) = i∈I (B \ Ai ).

Demostración. Sean I, B conjuntos y {Ai }i∈I una familia de conjuntos.

1. Podemos ofrecer dos pruebas. Primera Prueba

T T
x ∈ B \ ( i∈I Ai ) ⇔ [x ∈ B] ∧ [x ∈
/ i∈I Ai ] (Definición de diferencia )

⇔ [x ∈ B] ∧ ¬[∀i ∈ I (x ∈ Ai )] (Definición de intersección)

⇔ [x ∈ B] ∧ [∃i ∈ I (x ∈
/ Ai )] (Propiedades de cuantificadores )

⇔ ∃i ∈ I [(x ∈ B) ∧ (x ∈
/ Ai )] (Propiedad de cuantificadores)

⇔ ∃i ∈ I [x ∈ (B \ Ai )] (Definición de diferencia)
S
⇔ x ∈ i∈I Ai (B \ Ai ) (Definición de unión)

Segunda prueba.
T
(⊆) Sea x ∈ B \ ( i∈I Ai ). Entonces, por la definición de diferencia, x ∈ B y
T
x∈/ i∈I Ai . Luego, negando la definición de intersección se tiene que para algún

i ∈ I, x ∈
/ Ai . Como además x ∈ B, obtenemos que para ese i ∈ I, x ∈ B \ Ai .
S
Por lo tanto, existe i ∈ I, tal que x ∈ B \ Ai , es decir, x ∈ i∈I (B \ Ai ).
S
(⊇) Sea x ∈ i∈I (B \ Ai ). Entonces, por la definición de unión, existe i ∈ I, tal

que x ∈ B \ Ai . Por la definición de diferencia se tiene que para ese i ∈ I, x ∈ B

yx∈/ Ai . Recordando la definición de intersección, esto significa que x ∈ B y

T T
x∈
/ i∈I Ai . Por lo tanto, x ∈ B \ ( i∈I Ai ).

Por el Axioma de Extensionalidad y las contenciones anteriores, se sigue la igual-

dad.

2. La prueba es similar al inciso anterior.

34
2.4. Complementación
En curso de nivel superior sobre conjuntos es muy usual introducir la noción de

”complemento”, esta noción se deberı́a introducir de la siguiente manera:

Definición 2.33: Sea A un conjunto (subconjunto de un conjunto universal U ). El

conjunto complemento de A con respecto a U es el conjunto formado por los elementos

de U que no pertenecen a A, y es denotado por Ac . Es decir, Ac := {x ∈ U : x ∈

/ A}.

Observación 2.34: Como x ∈ Ac si y solo si x ∈ U y x ∈ / Ac si y

/ A, se tiene x ∈

solo si x ∈
/ U o x ∈ A.

Teorema 2.35: Tenemos que ∅c = U .

Demostración. Veamos que U ⊆ ∅c . Sea x ∈ U . Como x ∈

/ ∅, pues ∅ no tiene elementos,

/ ∅. Por lo tanto, U ⊆ ∅c .
se tiene que x ∈ U y x ∈

Por otra parte, como ∅c := {x ∈ U : x ∈

/ ∅}, en particular, cualquier elemento de

∅c es elemento de U Ası́, ∅c ⊆ U .

Por lo tanto, ∅c = U por el Axioma de Extensionalidad.

Observación 2.36: Si no se tiene cuidado en aclarar que la operación complemen-

tación es relativa a un conjunto universal U se corre el riesgo de terminar hablando

de la colección de todos los conjuntos.

Por la observación anterior, en la teorı́a de conjuntos formal la noción de com-

pleto es una noción que se define a partir de la diferencia de conjuntos, la siguiente

proposición muestra cómo se harı́a esto:

Proposición 2.37: Para cualesquiera A y B subconjuntos de un conjunto universal

U , se tiene que A \ B = A ∩ B c . En particular B c = U \ B.

35
Demostración. Sean A ⊆ U y B ⊆ U . Notemos que

x∈A\B ⇔ x∈A∧x∈
/B

⇔ x ∈ A ∧ x ∈ Bc (ya que A ⊆ U )

⇔ x ∈ A ∩ Bc.

Por lo tanto, A \ B = A ∩ B c .

Observación 2.38: Recordemos que el complemento de un conjunto depende del

conjunto universal que estamos considerando. Notemos que, por la proposición ante-

rior, si A = U entonces U \ B = U ∩ B c = B c . Por lo que, en este caso, el conjunto

universal al que nos referimos queda implı́cito usando esta notación.

Ejemplo 2.39: Notemos que el complemento de un conjunto varı́a si el conjunto

universal cambia. Por ejemplo,

1. El complemento de A = {1, 2} en U = {1, 2, 3} es {3} pero en U = {1, 2, 3, 4} es

{3, 4};

2. Sea P el conjunto de los números naturales pares, es decir, P = {x ∈ N : ∃ k ∈

N (x = 2k)}. Entonces, Pc := {x ∈ N : ¬∃ k(x = 2k)} = {x ∈ N : ∀ k(x ̸= 2k)},

considerando U = N. Sin embargo, si U = Z tenemos que Pc := {x ∈ Z :

¬∃ k(x = 2k) ∨ x < 0} = {x ∈ Z : ∀ k(x ̸= 2k) ∨ x < 0}.

Teorema 2.40: Sean U un conjunto universal y A, B subconjuntos de U . Entonces,

los siguientes enunciados se cumplen.

1. (Ac )c = A;

2. U c = ∅;

3. A ⊆ B si y solo si B c ⊆ Ac ;

4. A = B si y solo si Ac = B c .

Demostración.

36
 1. Veamos que (Ac )c ⊆ A. Sea x ∈ (Ac )c . Entonces, x ∈ U y x ∈
/ Ac . Luego, por la

Observación 2.34, tenemos que x ∈

/ U o x ∈ A. Como x ∈ U se sigue que x ∈ A.

Por lo tanto, (Ac )c ⊆ A.

Veamos ahora que A ⊆ (Ac )c . Sea x ∈ A. Dado que A es subconjunto de U ,

/ Ac (ver la
en particular, se tiene que x ∈ U . Como x ∈ A obtenemos que x ∈

/ Ac . Por lo que, A ⊆ (Ac )c .

Observación 2.34). Luego, x ∈ U y x ∈

Por lo tanto, A = (Ac )c por el Axioma de Extensionalidad.

2. Por una parte, ya sabemos que ∅c = U . Luego, (∅c )c = U c . Por otra parte,

usando el primer inciso obtenemos que (∅c )c = ∅. Por lo tanto, ∅ = U c .

3. Para la implicación (⇒), procedemos por contradicción. Supongamos que existe

x ∈ B c tal que x ∈
/ Ac . Luego, por la Observación 2.34 x ∈ A y como A ⊆ B se

sigue que x ∈ B lo cual contradice que x ∈ B c . Por lo tanto, si x ∈ B c entonces

x ∈ Ac .

Para la implicación contraria (⇐), por lo anterior tenemos que si B c ⊆ Ac

entonces (Ac )c ⊆ (B c )c . Luego, A ⊆ B ya que A = (Ac )c y B = (B c )c por el

inciso 2.

4. Por el Axioma de Extensionalidad se tiene que A = B si y solo si A ⊆ B y

B ⊆ A. Por otra parte, usando el inciso anterior tenemos que estas últimas

condiciones pasan si y solo si B c ⊆ Ac y Ac ⊆ B c . Por lo tanto, B c = Ac de

nuevo por el Axioma de Extensionalidad.

Proposición 2.41(Leyes de De Morgan): Sean I un conjunto y {Ai }i∈I una

familia de subconjuntos de un conjunto universal U . Entonces,

1. ( i∈I Ai )c = i∈I Aci .

T S

2. ( i∈I Ai )c = i∈I Aci .

S T

Demostración. Sean I un conjunto y {Ai }i∈I una familia de subconjuntos de un con-

junto universal U .

37
 1. Podemos ofrecer dos pruebas. Primera prueba

 
x ∈ ( i∈I Ai )c ⇔ x ∈ U \ i∈I Ai ]
T T
(Definición de complementación )
S
⇔ x ∈ i∈I (U \ Ai ) (Proposición 2.32)

⇔ x ∈ i∈I Aci
S
(Definición de complementación)

Segunda Prueba.

(⊆) Sea x ∈ ( i∈I Ai )c . Entonces, por la definición de complemento, x ∈ U y

S

S
x ∈
/ i∈I Ai . Luego, negando la definición de unión se tiene que x ∈/ Ai para

todo i ∈ I. Como además x ∈ U , obtenemos que x ∈ Aci para todo i ∈ I. Por lo

tanto, x ∈ i∈I Aci .

T

(⊇) Sea x ∈ i∈I Aci . Entonces, x ∈ Aci para todo i ∈ I. Por la definición de
T

complemento se tiene que x ∈ U y x ∈ / Ai para todo i ∈ I, es decir, x ∈ U y

/ i∈I Ai . Por lo tanto, x ∈ ( i∈I Ai )c .

S S
x∈

Por el Axioma de Extensionalidad y las contenciones anteriores, se sigue la igual-

dad.

2. La demostración de este inciso es similar a la prueba del inciso anterior.

2.5. Diferencia simétrica

A partir de la diferencia de conjuntos se puede definir otra operación conjuntista,

esta operación tiene muchos propiedades importantes.

Definición 2.42: Sean A y B subconjuntos de U . La diferencia simétrica de A y B,

denotada por A △ B, es

A △ B := (A \ B) ∪ (B \ A).

38
 Notemos que, dado que la unión es conmutativa, la diferencia simétrica también

lo es. De esto se desprende que la diferencia simétrica no es equivalente a la diferencia

de conjuntos.

Ejemplos 2.43:

1. Sean A = {2, 3} y B = {2, 4, 5}. Entonces, A △ B = {3, 4, 5}.

2. Sean P = {x ∈ N : x es par} y L = {x ∈ N : x es primo}. Entonces,

P△L= (P \ L) ∪ (L \ P)

= {x ∈ N : x es par ∧ x no es primo} ∪ {x ∈ N : x es primo ∧ x no es par}

= {x ∈ N : x es par ∧ x ̸= 2} ∪ {x ∈ N : x es primo ∧ x ̸= 2}

= {x ∈ N : x es par o primo ∧ x ̸= 2}

= (P ∪ L) \ {2}.

3. Sean A = [1, ∞) y B = (−∞, 3]. Entonces, A △ B = (3, ∞) ∪ (−∞, 1).

Observación 2.44: Por la Proposición 2.37, tenemos que A△B = (A∩B c )∪(B∩Ac ).

Proposición 2.45: Para cualesquiera conjuntos A y B, se tiene que

A △ B = (A ∪ B) \ (A ∩ B).

Demostración. Sean A y B conjuntos cualquiera. Entonces,

A△B = (A ∩ B c ) ∪ (B ∩ Ac ) (Proposición 2.37);

= [(A ∩ B c ) ∪ B] ∩ [(A ∩ B c ) ∪ Ac ] (Proposición 2.26);

= [(A ∪ B) ∩ (B c ∪ B)] ∩ [(A ∪ Ac ) ∩ (Ac ∪ B c )] (Proposición 2.26);

= [(A ∪ B) ∩ U ] ∩ [U ∩ (Ac ∪ B c )] (B c ∪ B = U = A ∪ Ac );

= (A ∪ B) ∩ (Ac ∪ B c ) (Teorema 2.17);

= (A ∪ B) ∩ (A ∩ B)c (Proposición 2.41);

= (A ∪ B) \ (A ∩ B) (Proposición 2.37).

39
Teorema 2.46: La diferencia simétrica tiene las siguientes propiedades.

1. Conmutatividad. Para cualesquiera conjuntos A y B, se tiene que

A △ B = B △ A;

2. Asociatividad. Para cualesquiera conjuntos A, B y C, se tiene que

(A △ B) △ C = A △ (B △ C);

3. El neutro para la diferencia simétrica es el vacı́o. Para cualquier conjunto

A, se tiene que A △ ∅ = A;

4. El inverso de un conjunto con respecto a la diferencia simétrica es él

mismo. Para cualquier conjunto A, se tiene que A △ A = ∅.

Demostración. Sean A, B y C conjuntos cualesquiera.

1. Es consecuencia directa de la conmutatividad de la unión, A △ B = (A \ B) ∪

(B \ A) = (B \ A) ∪ (A \ B) = B △ A.

2. Tenemos que

(A △ B) △ C = [(A △ B) ∩ C c ] ∪ [(A △ B)c ∩ C] (1)

= [[(A ∩ B c ) ∪ (Ac ∩ B)] ∩ C c ] ∪ [[(A ∪ B) ∩ (A ∩ B)c )]c ∩ C] (2)

= (A ∩ B c ∩ C c ) ∪ (Ac ∩ B ∩ C c ) ∪ (Ac ∩ B c ∩ C) ∪ (A ∩ B ∩ C) (3)

(⋆) = (A ∩ B ∩ C) ∪ (A ∩ B c ∩ C c ) ∪ (Ac ∩ B ∩ C c ) ∪ (Ac ∩ B c ∩ C) (4)

donde,

(1) se sigue de la Proposición 2.37 y el Teorema 2.46;

(2) se sigue de las Proposiciones 2.26 y 2.41, y el Teorema 2.40;

(3) se sigue de las Proposiciones 2.26 y 2.41;

40
 (4) se sigue por la conmutatividad de la unión.

Finalmente, por el inciso anterior, la igualdad (⋆) y la conmutatividad de la

intersección obtenemos

A △ (B △ C) = (B △ C) △ A

= (B ∩ C ∩ A) ∪ (B ∩ C c ∩ Ac ) ∪ (B c ∩ C ∩ Ac ) ∪ (B c ∩ C c ∩ A)

= (A ∩ B ∩ C) ∪ (Ac ∩ B ∩ C c ) ∪ (Ac ∩ B c ∩ C) ∪ (A ∩ B c ∩ C c )

= (A △ B) △ C.

3. Notemos que

A△∅= (A \ ∅) ∪ (∅ \ A)

= A∪∅ (Teorema 2.30)

= A (Teorema 2.17)

4. Tenemos que

A△A= (A \ A) ∪ (A \ A)

= ∅∪∅ (Teorema 2.30)

= ∅ (Teorema 2.17)

2.6. Potencia
Definición 2.47: El conjunto potencia de un conjunto A, denotado por P(A), es el

conjunto P(A) := {X : X ⊆ A}. Esto es, X ∈ P(A) si y solo si X ⊆ A.

La existencia de este conjunto es consecuencia de otro axioma de la teorı́a de

conjuntos:

Axioma de las partes Si A es un conjunto, los subconjuntos de A son elementos

41
de otro conjunto.

Nótese que el conjunto vacı́o ∅ y A pertenecen al conjunto potencia de cualquier

conjunto A.

A partir de este momento de las notas nuestra convención que establecı́a que los

elementos de un conjunto se denotan con minúsculas y los conjuntos con mayúsculas

pierde sentido, pues ahora un conjunto es claramente elemento de otro conjunto. Por

esto debes poner mucha atención a los objectos sobre los que se están hablando y a

las relaciones entre ellos.

Ejemplo 2.48: Si A = {a, b} con a ̸= b entonces su conjunto potencia es P(A) =

{∅, {a}, {b}, A}.

Lema 2.49: Para cualesquiera conjuntos A, B y X, se tiene que

X ⊆ (A ∩ B) si y solo si X ⊆ A y X ⊆ B.

Demostración. (⇒) Supongamos que la contención X ⊆ (A ∩ B) es cierta. Probemos

que X ⊆ A y X ⊆ B, es decir, veamos que todo elemento de X es elemento de ambos

A y B. En efecto, como X ⊆ (A ∩ B) para un elemento x ∈ X se tiene que x ∈ A ∩ B;

esto es, x ∈ A y x ∈ B. Por lo tanto, X ⊆ A y X ⊆ B.

(⇐) Supongamos que X ⊆ A y X ⊆ B. Veamos que X ⊆ A ∩ B, es decir,

probemos que todo elemento de X es elemento de A ∩ B. Sea x ∈ X. Dado que X ⊆ A

y X ⊆ B tenemos que x ∈ A y x ∈ B, respectivamente. Por lo tanto, x ∈ A ∩ B y ası́

X ⊆ A ∩ B.

Teorema 2.50: Para cualesquiera conjuntos A y B, se tiene que

P(A ∩ B) = P(A) ∩ P(B).

42
Demostración. Tenemos que

X ∈ P(A ∩ B) ⇔ X ⊆A∩B

⇔ X ⊆A∧X ⊆B (Lema 2.49)

⇔ X ∈ P(A) ∧ X ∈ P(B)

⇔ X ∈ P(A) ∩ P(B).

Proposición 2.51: Si A y B son conjuntos cualesquiera entonces

P(A) ∪ P(B) ⊆ P(A ∪ B).

Demostración. Sea X ∈ P(A) ∪ P(B). Entonces, por definición de unión, X ∈ P(A)

o X ∈ P(B) lo cual sucede si y solo si X ⊆ A o X ⊆ B. Por el Teorema 2.12(2) y

dado que ambos A y B están contenidos en A ∪ B, si se cumple alguno de los casos

anteriores obtenemos que X ⊆ A ∪ B. Luego, X ∈ P(A ∪ B). Por lo tanto, obtenemos

la contención P(A) ∪ P(B) ⊆ P(A ∪ B).

¿Será cierta la otra contención?

2.7. Producto cartesiano

Para esta sección vamos a necesitar la noción de par ordenado. Es decir vamos a

querer definir un objeto matemático que cumpla la siguiente propiedad:

Dados a, b, c y d, las parejas ordenadas (a, b) y (c, d) satisfacen que (a, b) = (c, d)

si y sólo si a = c y b = d.

Para esto se cumplan, en la teorı́a de conjuntos se definen los pares ordenados de

la siguiete manera:

43
 (a, b) = {{a}, {a, b}}

puedes revisar que definidos de esta manera los pares ordenados cumplen la pro-
1
piedad que buscamos.

A partir de la noción de par ordenado se define el objeto que estudiaremos en esta

sección.

Definición 2.52: Sean A y B conjuntos. El producto cartesiano de A y B, denotado

por A × B, es el conjunto de parejas ordenadas

A × B = {(a, b) : a ∈ A ∧ b ∈ B}.

En particular, cuando A = B, escribimos A2 en lugar de A × A.

Ejemplos 2.53:

1. Sean A = {1, 2, 3} y B = {1, 2}. Entonces,

A × B = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (3, 2)} y

B × A = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)}.

Por lo que, el producto cartesiano no es conmutativo.

2. N2 = {(n, m) : n, m ∈ N}. De manera similar se definen Z2 y R2 , este último

llamado el plano cartesiano.

3. Sean a, b, c, d ∈ R tales que a < b y c < d. Sean A = {x ∈ R : a ≤ x ≤ b} y B =

{y ∈ R : c ≤ y ≤ d}. Entonces, A × B = {(x, y) ∈ R2 : a ≤ x ≤ b ∧ c ≤ y ≤ d} y

su descripción en el plano cartesiano es

1
Esta es sólo una de múltiples maneras como se define el par ordenado, lo importante
es que en todas ellas la propiedad de que un par ordenado es igual si y sólo si entrada por
entrada son iguales se cumple.

44
Proposición 2.54: Para cualesquiera conjuntos A y B, se tiene que A × B = ∅ si y

solo si A = ∅ o B = ∅.

Demostración. Notemos que

A × B ̸= ∅ ⇔ ∃ (x, y) ∈ A × B

⇔ ∃x ∈ A ∧ ∃y ∈ B

⇔ A ̸= ∅ ∧ B ̸= ∅

Luego, el resultado se sigue ya que es lógicamente equivalente a la equivalencia anterior.

Teorema 2.55: Sean A, B y C conjuntos cualesquiera. Entonces,

1. (A ∪ B) × C = (A × C) ∪ (B × C);

2. (A ∩ B) × C = (A × C) ∩ (B × C);

3. (A \ B) × C = (A × C) \ (B × C).

Demostración. Sean A, B y C conjuntos cualesquiera. Usando las propiedades distri-

butivas y conmutativas de la conjunción y la disyunción tenemos:

45
1.
(x, y) ∈ (A ∪ B) × C ⇔ x ∈ A ∪ B ∧ y ∈ C

⇔ (x ∈ A ∨ x ∈ B) ∧ y ∈ C

⇔ (x ∈ A ∧ y ∈ C) ∨ (x ∈ B ∧ y ∈ C)

⇔ (x, y) ∈ A × C ∨ (x, y) ∈ B × C

⇔ (x, y) ∈ (A × C) ∪ (B × C).

2.
(x, y) ∈ (A ∩ B) × C ⇔ x∈A∩B∧y ∈C

⇔ (x ∈ A ∧ x ∈ B) ∧ y ∈ C

⇔ (x ∈ A ∧ y ∈ C) ∧ (x ∈ B ∧ y ∈ C)

⇔ (x, y) ∈ A × C ∧ (x, y) ∈ B × C

⇔ (x, y) ∈ (A × C) ∩ (B × C).

3. Notemos la siguiente cadena de equivalencias: (x, y) ∈ (A × C) \ (B × C)

⇔ (x, y) ∈ A × C ∧ (x, y) ∈
/ B×C

⇔ (x, y) ∈ A × C ∧ [x ∈
/ B∨y ∈
/ C]

⇔ [(x, y) ∈ A × C ∧ x ∈
/ B] ∨ [(x, y) ∈ A × C ∧ y ∈
/ C]

⇔ [(x ∈ A ∧ y ∈ C) ∧ x ∈
/ B] ∨ [(x ∈ A ∧ y ∈ C) ∧ y ∈
/ C]

⇔ [(x ∈ A ∧ y ∈ C) ∧ x ∈
/ B]

⇔x∈A\B∧y ∈C

⇔ (x, y) ∈ (A \ B) × C.

46
Capı́tulo 3
Relaciones y Funciones
En este capı́tulo nuestro estudio se centra en los conceptos de relación y

función. Empezamos dando la definición de relación y estudiamos un caso

especial de ellas llamadas relaciones de equivalencia. Este último concepto

se relaciona con otro llamado partición. Más aún, probamos que existe una

correspondencia biyectiva entre estas dos nociones.

Posteriormente estudiaremos otro tipo de relación: las relaciones de or-

den.

Por último, analizamos otro tipo especial de relaciones llamadas funcio-

nes, caracterizamos algunas de ellas y también, mostramos ejemplos de su

representación gráfica.

Definición 3.1: Sean A y B conjuntos.

1. Una relación (binaria) entre A y B es un subconjunto R de A × B, es decir

R ⊆ A × B. En el caso en que A = B, decimos que R es una relación binaria

sobre A.

2. El dominio de una relación R ⊆ A × B, denotado por dom(R), es el conjunto

dom(R) = {x ∈ A : ∃ y ∈ B ((x, y) ∈ R)}.

3. La imagen de una relación R ⊆ A × B, denotado por im(R) es el conjunto

im(R) = {y ∈ B : ∃ x ∈ A ((x, y) ∈ R)}

Notemos que R ⊆ dom(R)×im(R). Si (a, b) ∈ R lo denotaremos por a ∼ b y cuando

R
el contexto sea claro solo escribimos a ∼ b.

Ejemplos 3.2:

47
 1. Para cualesquiera conjuntos A y B, tanto ∅ como A × B son relaciones entre A

y B. La primera es llamada la relación vacı́a y la segunda la relación total .

2. Sea H el conjunto de todos los humanos. Sea R la relación sobre H definida

como a ∼ b si y solo si a es hijo(a) de b.

R
3. Sean K = {1, 2, 3, 4} y M = {1, 2, 3, 4, 5}. Definimos la siguiente relación R =

{(2, 1), (2, 3), (3, 4), (4, 4), (4, 5)} ⊆ K × M . Entonces, dom(R) = {2, 3, 4} ⊆ K y

im(R) = {1, 3, 4, 5} ⊆ M .

Definición 3.3: Sean R y S relaciones binarias.

1. La relación inversa de una relación R, denotada por R−1 , es el conjunto

R−1 = {(y, x) : x ∼ y} = {(y, x) : (x, y) ∈ R}.

R

Notemos que R−1 ⊆ im(R) × dom(R).

2. La relación composición de R con S, denotada por S ◦ R, es el conjunto

S ◦ R := {(x, z) : ∃ y ∈ im(R) ∩ dom(S) ((x, y) ∈ R) ∧ ((y, z) ∈ S) }.

Ejemplo 3.4:

1. Sean A = {a} y B = {b}. Como A×B = {(a, b)} solo hay dos relaciones posibles:

la vacı́a y la total. En este caso, ∅−1 = ∅ y (A × B)−1 = {(b, a)}.

2. Sean A = {0, 1, 2, 3, 4}, B = {−3, −2, −1, 0, 1, 2, 3} y C = {0, 1, 2, 3}. Definimos

48
 las relaciones R ⊆ A × B y S ⊆ B × C como x ∼ y si y solo si x = y 2 , y
R
x ∼ y si y solo si x + 3 = y. Entonces, la relación compuesta S ◦ R ⊆ A × C es
S
S ◦ R = {(0, 3), (1, 2), (4, 1)}.

Proposición 3.5: Si R y S son relaciones entonces S ◦ R ⊆ dom(R) × im(S).

Demostración. Supongamos que (x, z) ∈ S ◦ R. Entonces, existe y ∈ im(R) tal que

x ∼ y y y ∼ z de donde x ∈ dom(R) y z ∈ im(S). Por lo tanto, (x, z) ∈ dom(R)×im(S)

R S
y S ◦ R ⊆ dom(R) × im(S).

Teorema 3.6: Sean T, S y R relaciones. Entonces,

1. (T ◦ S) ◦ R = T ◦ (S ◦ R);

2. (S ◦ R)−1 = R−1 ◦ S −1 .

Demostración. Sean T, S y R relaciones.

(x, y) ∈ (T ◦ S) ◦ R ⇔ ∃ z [(x, z) ∈ R ∧ (z, y) ∈ T ◦ S]

⇔ ∃ z [(x, z) ∈ R ∧ ∃ w[(z, w) ∈ S ∧ (w, y) ∈ T ]]

⇔ ∃ z ∃ w [(x, z) ∈ R ∧ (z, w) ∈ S ∧ (w, y) ∈ T ]

⇔ ∃ w ∃ z [(x, z) ∈ R ∧ (z, w) ∈ S ∧ (w, y) ∈ T ]

⇔ ∃ w [∃ z [(x, z) ∈ R ∧ (z, w) ∈ S] ∧ (w, y) ∈ T ]

⇔ ∃ w [(x, w) ∈ S ◦ R ∧ (w, y) ∈ T ]

⇔ (x, y) ∈ T ◦ (S ◦ R)

(x, z) ∈ (S ◦ R)−1 ⇔ (z, x) ∈ S ◦ R

⇔ ∃ y [(z, y) ∈ R ∧ (y, x) ∈ S]

⇔ ∃ y [(y, z) ∈ R−1 ∧ (x, y) ∈ S −1 ]

⇔ ∃ y [(x, y) ∈ S −1 ∧ (y, z) ∈ R−1 ]

⇔ (x, z) ∈ R−1 ◦ S −1 .

49
3.1. Relaciones de equivalencia
A lo largo de esta sección, dada una relación R escribimos x ∼ y para denotar que

(x, y) ∈ R en lugar de x ∼ y por motivo de simpleza.

R

Definición 3.7: Dado un conjunto A ̸= ∅, decimos que una relación R sobre A es

una relación de equivalencia si y solo si R es:

1. Reflexiva. Para todo x ∈ A se tiene que x ∼ x.

2. Simétrica. Para todo x, y ∈ A, si x ∼ y entonces y ∼ x.

3. Transitiva. Para todo x, y, z ∈ A, si x ∼ y y y ∼ z entonces x ∼ z.

Si R es una relación de equivalencia y x ∼ y diremos que x es equivalente a y.

Definición 3.8: Sean R una relación de equivalencia sobre un conjunto A ̸= ∅ y

a ∈ A. La clase de equivalencia de a, denotada por [a] o [a]∼ , es el conjunto de todos

los elementos de A equivalentes a a, es decir, [a]∼ = {x ∈ A : x ∼ a}.Un representante

de la clase [a] es cualquier elemento que pertenezca a la clase [a].

Ejemplos 3.9:

1. La relación R sobre Z definida como x ∼ y si y solo si x y y tienen la misma

paridad, es una relación de equivalencia.

2. La relación sobre M , el conjunto de todos los mexicanos nacidos en el territorio,

mexicano dada por x ∼ y si y sólo si x nació en el mismo estado que y.

3. La relación S sobre Z definida como x ∼ y si y solo si ∃ k ∈ Z tal que x − y = 3k,

es una relación de equivalencia.

4. La relación T sobre R definida como x ∼ y si y solo si x − y ∈ Z, es una relación

de equivalencia.

Proposición 3.10: Sean R una relación de equivalencia en un conjunto A ̸= ∅ y

a, a′ ∈ A. Entonces,

1. a ∼ a′ si y solo si [a] = [a′ ].

50
 2. a ≁ a′ si y solo si [a] ∩ [a′ ] = ∅.

Demostración.

1. (⇒) Supongamos que a ∼ a′ . Veamos que [a] = [a′ ] por doble contención.

(⊆) Sea b ∈ [a]. Entonces, b ∼ a y a ∼ a′ , dado que la relación es transitiva

se sigue b ∼ a′ . Luego, de la definición de clase de equivalencia obtenemos que

b ∈ [a′ ]. Para la contención contraria (⊇), sea b ∈ [a′ ]. Tenemos que b ∼ a′ y

a′ ∼ a ya que R es simétrica. Por lo tanto, b ∈ [a′ ] de nuevo por transitividad.

(⇐) Supongamos [a] = [a′ ]. Por reflexividad, tenemos que a ∼ a, lo cual implica

a ∈ [a] = [a′ ]. Por lo tanto, a ∼ a′ .

2. Por contrapuestas; esto es, demostremos que [a] ∩ [a′ ] ̸= ∅ si y solo si a ∼ a′ .

(⇒) Supongamos [a] ∩ [a′ ] ̸= ∅ y sea b ∈ [a] ∩ [a′ ]. Por definición, b ∼ a y b ∼ a′ .

Como R es simétrica, tenemos que a ∼ b y por transitividad, a ∼ a′ .

(⇐) Supongamos a ∼ a′ . Entonces, a ∈ [a′ ]. Por otra parte, como R es reflexiva

se tiene que a ∼ a, lo cual implica que a ∈ [a]. Luego, a ∈ [a] ∩ [a′ ] y ası́,

[a] ∩ [a′ ] ̸= ∅.

Definición 3.11: Sean R una relación de equivalencia en un conjunto A ̸= ∅. El

conjunto cociente de A bajo R, denotado A/∼ , es el conjunto de todas las clases de

equivalencia inducida por R, es decir, A/∼ = {[a] : a ∈ A}.

3.2. Particiones
Definición 3.12: Sean A e I conjuntos no vacı́os y P = {Ai }i∈I una familia de

subconjuntos de A. Decimos que P es una partición de A si y solo si se cumplen las

siguientes condiciones:

1. Ai ̸= ∅ para toda i ∈ I.

51
 2. Si i, j ∈ I son tales que Ai ̸= Aj entonces Ai ∩ Aj = ∅.
S
3. Para toda a ∈ A, existe i ∈ I tal que a ∈ Ai , es decir, i∈I Ai = A.

Ejemplo 3.13:

1. Sea A = {1, 2, 3}. Entonces, P = {{1, 2}, {3}} es una partición de A.

2. P = {{z ∈ Z : z es par}, {z ∈ Z : z es impar}} es una partición de Z.

3. Para cada i ∈ I := [0, 1), definimos Ai = {x ∈ R : x − i ∈ Z}. Entonces,

P = {Ai }i∈I es una partición de R.

4. Sea M el conjunto de todos los mexicanos nacidos en el territorio. Entonces

P = {X : X es un estado de la República} es una partición de M si x ∈ X

significa x nació en X.

Teorema 3.14: Sea R una relación de equivalencia en A ̸= ∅. Se cumple lo siguiente.

1. Si a ∈ A entonces [a] ̸= ∅.

2. Para cualesquiera a, a′ ∈ A, si [a] ̸= [a′ ] entonces [a] ∩ [a′ ] = ∅.

3. Para todo a ∈ A, existe a′ ∈ A tal que a ∈ [a′ ].

Demostración.

1. Se sigue de la reflexividad de R ya que a ∼ a implica que a ∈ [a].

2. Sean a, a′ ∈ A y supongamos que [a] ̸= [a′ ]. Por la contrapuesta de la Proposi-

ción 3.10(1) se tiene que a ≁ a′ y por el inciso 2 de ella misma, obtenemos que

[a] ∩ [a′ ] = ∅.

3. Como hemos notado en el inciso 1, a ∈ [a] para todo a ∈ A.

Corolario 3.15: Sea R una relación de equivalencia en un conjunto A ̸= ∅. Entonces,

el conjunto cociente A/ ∼= {[a] : a ∈ A} es una partición de A. A esta partición la

llamamos la partición inducida por R.

Demostración. Es consecuencia del Teorema 3.14.

52
Ejemplo 3.16: Sea A = R2 . Definimos la relación R en A como p ∼ q si y solo si

p y q distan lo mismo del origen. La clase de equivalencia de un punto p en el plano

está dada por todos aquellos puntos cuya distancia al origen es la misma que la de

p, es decir, [p] = {q ∈ A :∥ p ∥=∥ q ∥}, lo cual geométricamente corresponde a la

circunferencia centrada en el origen que pasa por el punto p. La colección de todas

las circunferencias con centro en el origen es la partición del plano inducida por esta

relación de equivalencia.

Teorema 3.17: Sea P = {Ai }i∈I una partición de un conjunto A ̸= ∅. La relación

sobre A definida por: a ∼ b, si y solo si, existe i ∈ I tal que a ∈ Ai y b ∈ Ai , es una

P
relación de equivalencia. Se dice que ∼P es la relación inducida por la partición P .

Demostración. Sea P = {Ai }i∈I una partición de un conjunto A. Veamos que la

relación inducida por P es una relación de equivalencia.

1. Reflexiva. Sea a ∈ A. Como P es una partición, existe i ∈ I tal que a ∈ Ai lo

cual es lógicamente equivalente a a ∈ Ai y a ∈ Ai . Luego, a ∼ a.

P
2. Simétrica. Sean a, b ∈ A tales que a ∼ b. Entonces, existe i ∈ I tal que a ∈ Ai y
P
b ∈ Ai que es lógicamente equivalente a b ∈ Ai y a ∈ Ai . Por lo tanto, b ∼ a.
P

53
 3. Transitiva. Sean a, b, c ∈ A tales que a ∼ b y b ∼ c. Entonces, existen i, j ∈ I tales
P P
que a ∈ Ai , b ∈ Ai y b ∈ Aj , c ∈ Aj . Dado que b ∈ Ai ∩ Aj y P es una partición

se sigue que Ai = Aj , lo cual implica que a ∈ Ai y c ∈ Ai para el mismo ı́ndice

i ∈ I. Por lo tanto, a ∼ c.
P

Ejemplo 3.18: Sean A = R2 y P = {Ay }y∈R la partición de A, donde para un y ∈ R

fijo Ay := {(x, y) : x ∈ R}. La relación de equivalencia inducida por P está dada por:

(x1 , y1 ) ∼P (x2 , y2 ) ⇔ ∃ y ∈ R [(x1 , y1 ) ∈ Ay ∧ (x2 , y2 ) ∈ Ay ]

⇔ ∃ y ∈ R [(x1 , y1 ) = (x1 , y) ∧ (x2 , y2 ) = (x2 , y)]

⇔ y1 = y = y2 .

Proposición 3.19: Sean R y R′ relaciones de equivalencia definidas sobre un con-

junto A ̸= ∅. Si A/∼ = A/∼′ entonces R = R′ .

Demostración. Sean R y R′ relaciones de equivalencia sobre A tales que A/∼ = A/∼′ ,

es decir, {[z]∼′ : z ∈ A} = {[z]∼ : z ∈ A}. Probemos que R = R′ ; esto es, a ∼ b si y

solo si a ∼′ b, para cualesquiera a, b ∈ A.

Sean x, y ∈ A tales que x ∼ y. Ası́, x ∈ [y]∼ . Como

[y]∼ ∈ {[z]∼ : z ∈ A} = {[z]∼′ : z ∈ A}

tenemos que [y]∼ = [z]∼′ para algún z ∈ A. Ahora bien, como x, y ∈ [y]∼ = [z]∼′ se

sigue que x ∼′ z y y ∼′ z. Luego, por simetrı́a de R′ , x ∼′ z y z ∼′ y, y por transitividad

x ∼′ y. De manera análoga se puede probar que x ∼′ y implica x ∼ y.

Observación 3.20: Sea P = {Ai }i∈I una partición de A ̸= ∅. Si x ∈ Ai entonces

54
[x]∼P = Ai . Esto ocurre pues

[x]∼P = {z ∈ A : z ∼P x} = {z ∈ A : ∃ j ∈ I(z, x ∈ Aj )}.

Por lo que, si z, x ∈ Aj como x ∈ Ai se tiene que Ai ∩ Aj ̸= ∅, lo cual implica que

Ai = Aj ya que P es una partición. Por lo tanto,

[x]∼P = {z ∈ A : z ∼P x} = {z ∈ A : z ∈ Ai } = Ai .

Proposición 3.21: Sean P = {Ai }i∈I y P ′ = {A′j }j∈J particiones sobre un conjunto

A ̸= ∅. Si las relaciones inducidas por P y P ′ coinciden entonces P = P ′ .

Demostración. Veamos que P ⊆ P ′ . Sea Ai ∈ P . Como Ai ̸= ∅, existe x ∈ Ai y por

la Observación 3.20 se tiene que [x]∼P = Ai . Por otro lado, dado que P ′ es partición

de A, existe A′j tal que x ∈ A′j y de nuevo por la Observación 3.20 obtenemos que

[x]∼P ′ = A′j . Luego, como las relaciones inducidas por P y P ′ son la misma tenemos

Ai = [x]∼P = [x]∼P ′ = A′j . Por lo tanto, Ai ∈ P ′ y ası́, P ⊆ P ′ . Similarmente, se

prueba la contención contraria.

Proposición 3.22: Sean P = {Ai }i∈I una partición de un conjunto A ̸= ∅. Enton-

ces, P = {[x]∼P : x ∈ A}.

Demostración. Veamos que P = {[x]∼P : x ∈ A} por doble contención.

(⊆) Sea Ai ∈ P . Como P es una partición sabemos que Ai ̸= ∅ y podemos conside-

rar z ∈ Ai . Luego, por la Observación 3.20, tenemos que Ai = [z]∼P ∈ {[x]∼P : x ∈ A}.

Por lo tanto, P ⊆ {[x]∼P : x ∈ A}.

(⊇) Sea [z]∼P ∈ {[x]∼P : x ∈ A}. Como P es partición y z ∈ A se tiene que existe

i ∈ I tal que z ∈ Ai . Por la Observación 3.20 se sigue que [z]∼P = Ai ∈ P . Por lo

tanto, {[x]∼P : x ∈ A} ⊆ P .

55
3.3. Relaciones de orden parcial
Definición 3.23: Dado un conjunto A ̸= ∅, decimos que una relación R sobre A es

una relación de orden parcial si y solo si R es:

1. Reflexiva. Para todo x ∈ A se tiene que (x, x) ∈ R.

2. Anti-simétrica. Para todo x, y ∈ A, si (x, y) ∈ R y (y, x) ∈ R entonces x = y.

3. Transitiva. Para todo x, y, z ∈ A, si (x, y) ∈ R y (y, z) ∈ R entonces (x, z) ∈ R.

Si R es una relación de orden parcial, la denotamos por R =≤ y denotamos (x, y) ∈≤

por x ≤ y.

Si x ≤ y diremos que x es menor o igual a y.

Ejemplo 3.24:

1. Sea A el conjunto de todas las personas en la clase y R la relación (x, y) ∈ R si

y sólo si y salta más alto que x. Como los fı́sicos en el salón nos pueden asegurar

que no hay dos personas que salten igual de alto, entonces R es una relación de

orden en A.

2. Sea A = R. Entonces la relación de orden usual, es decir, x ≤ y si y sólo si

y − x ∈ P donde P es la clase positiva, es una relación de orden parcial.

3. Consideremos R, y {(−∞, x) ⊆ R : x ∈ R}. Definimos (−∞, x) ≤ (−∞, y) si y

sólo si (−∞, x) ⊆ (−∞, y). Entonces esto define una relación de orden.

Observa dos cosas. La primera es que (−∞, x) ≤ (−∞, y) si y sólo si x ≤ y. Ası́

que en realidad esta no es una nueva relación de orden, sino una vieja definiad

en unos conjuntos raros. La segunda es que la contención siempre define una

relación de orden.

4. Sea X un conjunto, consideremos P(X) y

≤= {(A, B) ∈ P(X)2 : A ⊆ B}

Es decir, A ≤ B si y sólo si A ⊆ B. Entonces ≤ es una relación de orden en

56
 P(X).

Ahora viene un festival de definiciones que permite establecer la noción de una

relación de orden parcial:

Definición 3.25: Sea A ̸= ∅, y ≤ una relación de orden parcial sobre A.

1. Máximo Dado un subconjunto B ⊆ A, decimos que un elemento a ∈ B es

máximo de B si ∀ b ∈ B, b ≤ a, y escribimos maxB = a.

2. Mı́nimo Dado un subconjunto B ⊆ A, decimos que un elemento a ∈ B es mı́nimo

de B si ∀ b ∈ B, a ≤ b, y escribimos minB = a.

3. Cota superior Dado un subconjunto B ⊆ A, decimos que un elemento a ∈ A es

cota superior de B si ∀ b ∈ B, b ≤ a.

4. Cota inferior Dado un subconjunto B ⊆ A, decimos que un elemento a ∈ A es

cota inferior de B si ∀ b ∈ B, a ≤ b.

5. Maximal Dado un subconjunto B ⊆ A, decimos que un elemento a ∈ B es

maximal en B si ∀ c ∈ A, a ≤ c ⇒ c ∈
/ B.

6. Minimal Dado un subconjunto B ⊆ A, decimos que un elemento a ∈ B es

minimal en B si ∀ c ∈ A, c ≤ a ⇒ c ∈
/ B.

7. Supremo Dado un subconjunto B ⊆ A, decimos que un elemento a ∈ A es

supremo de B si es la mı́nima cota superior, es decir,

a = min{b ∈ A : b es cota superior de B}.

Y escribimos a = supB

8. Ínfimo Dado un subconjunto B ⊆ A, decimos que un elemento a ∈ A es ı́nfimo

de B si es la máxima cota inferior, es decir,

a = max{b ∈ A : b es cota inferior de B}.

Y escribimos a = ı́nfB

57
 Seguramente te estarás preguntando. ¿Por qué tantas definiciones? ¿No estamos

definiendo lo mismo de muchas maneras diferentes? No

Aquı́ un ejemplo.

Considera X = {1, 2, 3, 4, 5}, A = P(X) y ⊆ como la relación de orden.

Considera los conjuntos:

B1 = {{1}, {1, 2}, {1, 2, 3}} B2 = {{1}, {1, 2}, {1, 2, 3}, {1, 2, 4}}

Entonces es claro que {1, 2, 3} es máximo de B1 , pero no es máximo de B2 .

Mientras que {1, 2, 3} y {1, 2, 4} son maximales en B2 pero ninguno es máximo,

de hecho B2 no tiene máximos. Además, {1, 2, 3, 4, 5} es cota de B1 y B2 , pero

no es ni máximo ni maximal en ellos, pues no es elemento de ellos. Por último

{1, 2, 3, 4} es supremo de B2 .

Se puede construir un ejemplo análoga para establecer las distinciones entre

mı́nimo, minimal, cota inferior e ı́nfimo.

Lo que si es cierto es:

Proposición 3.26: Sea A ̸= ∅, y ≤ una relación de orden parcial sobre A y

B⊆A

a) Si a ∈ B es máximo en B entonces es maximal en, cota superior de y el

supremo de B.

b) Si a ∈ B es mı́nimo en B entonces es minimal en, cota inferior de y el

ı́nfimo de B.

La razón por la que tenemos tantas definiciones referentes al orden es porque las

relaciones de orden parcial no nos permiten comprar a cualquiera dos elementos. En

el ejemplo ofrecido B2 no tiene máximos pues no hay manera de comprar {1, 2, 3}

y {1, 2, 4}: ninguno es menor o igual que el otro. Para solucionar esto ofrecemos la

siguiente definición:

Definición 3.27: Dado un conjunto A ̸= ∅, decimos que una relación R sobre A es

una relación de orden total si y solo si R es:

58
 1. Total. Para todo x, y ∈ A se tiene: (x, y) ∈ R ó (y, x) ∈ R.

2. Anti-simétrica. Para todo x, y ∈ A, si (x, y) ∈ R y (y, x) ∈ R entonces x = y.

3. Transitiva. Para todo x, y, z ∈ A, si (x, y) ∈ R y (y, z) ∈ R entonces (x, z) ∈ R.

Si R es una relación de orden total recuperamos las convenciones para orden parcial:

La denotamos por R =≤ y denotamos (x, y) ∈≤ por x ≤ y.

Si x ≤ y diremos que x es menor o igual a y.

Puedes revisar que toda relación de orden total es relación de orden total (sólo hay

que checar que la propiedad total implica la propiedad reflexiva.)

Todos los ejemplos que habı́amos visto previamente de relaciones de orden parcial

eran relaciones de orden total, excepto el ejemplo del conjunto potencia. Lo cual

muestra que no todo orden parcial es total.

Puedes revisar como ser maximal en un conjunto totalmente ordenado implica ser

máximo.

3.4. Funciones y gráficas

Definición 3.28: Sean A y B conjuntos. Una función f de A en B es una relación

f ⊆ A × B que cumple:

1. Para todo x ∈ A, existe y ∈ B tal que (x, y) ∈ f .

2. Cada elemento de A tiene asociado solo uno de B, es decir, para cualesquiera

x ∈ A y y1 , y2 ∈ B, si (x, y1 ) ∈ f y (x, y2 ) ∈ f entonces y1 = y2 .

A f lo denotamos como f : A → B y diremos que A es el dominio de f y B el

codominio de f . Denotamos por f (x) al único elemento de B que le corresponde a x

y le llamamos la imagen de x bajo f , para denotar este hecho escribimos x 7→ f (x).

La imagen de f es la misma imagen como relación, y en este caso se puede reescribir

como

imf = {b ∈ B : ∃ a ∈ A tal que (a, b) ∈ f } = {f (a) : a ∈ A}.

59
La representación de una función mediante un sistema de coordenadas cartesianas en

el plano o en el espacio se le llama la gráfica de f . La regla de correspondencia de

una función se refiere a la manera en que se hacen corresponder los elementos del

dominio con los del codominio. Cuando el dominio de una función f : A → B es

un conjunto de n elementos, digamos a1 , a2 , . . . , an , podemos escribirla mediante un

arreglo de renglones, donde el primer renglón son los distintos elementos del dominio

y el segundo sus correspondientes imágenes

 
a1 a2 ··· an
f = .
 
f (a1 ) f (a2 ) · · · f (an )

Ejemplos 3.29:

1. Sean A = {−1, 0, 1, 2} y B = {0, 1, 4}.

a) Sea f ⊆ A × B la siguiente relación (x, y) ∈ f si y solo si y = x2 . Entonces,

f = {(−1, 1), (0, 0), (1, 1), (2, 4)}. Ası́, f es una función de A en B y imf =

{0, 1, 4} = B.

b) Sea r ⊆ B × A la siguiente relación (x, y) ∈ r si y solo si x = y 2 . Entonces

r = {(1, −1), (0, 0), (1, 1), (4, 2)}. Ası́, r no es una función ya que a 1 le

corresponden 1 y −1. Notemos que r es la relación inversa de f , por lo que

en general, no se cumple que la relación inversa de una función sea una

función.

2. Sea f : R → Z definida como





 1 si x > 0,

f (x) = 0 si x = 0,



 −1

si x < 0.

Su gráfica está dada por:

3. Sean A = {1, 2, 3, 4, 5, 6, 7}, B = {−2, −1, 0, 9} y f : A → B la función dada

60
 por f (1) = f (3) = f (5) = 0, f (2) = f (6) = −1, f (4) = f (7) = 9. Su regla de

correspondencia se puede escribir como

 
 1 2 3 4 5 6 7 
f = .
0 −1 0 9 0 −1 9

3.5. Tipos de funciones

Definición 3.30: Sea f : A → B una función.

1. Decimos que f es inyectiva (o una correspondencia uno a uno) si y solo si para

cualesquiera x1 , x2 ∈ A tales que x1 ̸= x2 se tiene que f (x1 ) ̸= f (x2 ) (lo cual es

equivalente a: para cualesquiera x1 , x2 ∈ A, si f (x1 ) = f (x2 ) entonces x1 = x2 ).

En caso de que f sea inyectiva escribimos f : A ↣ B.

2. Decimos que f es suprayectiva (o sobre) si y solo si para todo y ∈ B, existe

x ∈ A tal que y = f (x) y lo denotaremos por f : A ↠ B. Notemos que f es

suprayectiva si y solo si imf = B.

3. Decimos que f es biyectiva si y solo si f es inyectiva y suprayectiva.

Ejemplos 3.31:

1. Sea f : Z → Z dada por f (x) = −x + 1. Entonces, f es biyectiva.

2. Sean A = {0, −1, 1, 2} y B = {0, 1, 2, 3, 4}. La función f : A → B definida como

f (x) = x2 no es inyectiva ni suprayectiva.

61
 3. Sean A = {1, 2, 3, 4} y B = {1, 2, 3}. La función f : A → B definida como

f (1) = 1, f (2) = 2, f (3) = 2 y f (4) = 3 no es inyectiva pero si suprayectiva.

4. Sea f : N → N tal que f (x) = 2x. Entonces, f es inyectiva pero no suprayectiva.

Observación 3.32: Podemos restringir el dominio (respectivamente, codominio)

para crear una función inyectiva (respectivamente, suprayectiva). Por ejemplo, sea

f : A → B donde A = {0, −1, 2, 1}, B = {0, 1, 2, 3, 4} dada por f (x) = x2 . Notemos

que f no es inyectiva ni suprayectiva. Tomando A′ = {0, 1, 2}, A′′ = {0, −1, 2} y

B ′ = {0, 1, 4} tenemos que f1 : A′ → B ′ y f2 : A′′ → B ′ dadas por fi (x) = x2 para

i = 1, 2 son biyectivas y además, A′ ̸= A′′ . Por lo que, la forma de restringir no es

única.

Teorema 3.33: Sean un conjunto A ̸= ∅,

R := {R : R es una relación de equivalencia sobre A} y

P := {P : P es una partición de A}.

Entonces, existe una función biyectiva F : R → P definida como F (R) = A/∼ donde

A/∼ es el conjunto cociente de la relación de equivalencia R.

Demostración.

1. F es suprayectiva. Sea P = {Ai }i∈I una partición de A. Por el Teorema 3.17

sabemos que ∼P es una relación de equivalencia. Además, por la Proposición 3.22

se tiene que F (∼P ) = P . Por lo tanto, F es suprayectiva.

2. F es inyectiva. Sean R, R′ ∈ R. Entonces, por la Proposición 3.19, si F (R) =

F (R′ ) entonces R = R′ y por tanto F es inyectiva.

Por lo probado antes, podemos concluir que F es biyectiva.

Definición 3.34: Sean f : X → Y una función y A ⊆ X. La imagen de A bajo f ,

denotada por f [A], es el conjunto f [A] := {f (a) : a ∈ A}.

62
Ejemplos 3.35:

1. Sean A = {0, 1, 2}, B = {0, 1}, C = {{2}, {0, 1}} ⊆ P(A) y f : P(A) → P(B)

dada por f (X) = X ∩ B. Entonces, f [C] := {f ({2}), f ({0, 1})} = {∅, B}.

2. Sean f : Z → Z definida como f (x) = −x + 1 y C = {z ∈ Z : 2 < z < 100}.

Entonces, f [C] = {z ∈ Z : −99 < z < −1}.

Lema 3.36: Sean X, Y conjuntos y f : X → Y una función. Entonces,

1. f [∅] = ∅

2. Si A1 , A2 ⊆ X entonces f [A1 ∩ A2 ] ⊆ f [A1 ] ∩ f [A2 ].

3. Si A1 , A2 ⊆ X entonces f [A1 ∪ A2 ] = f [A1 ] ∪ f [A2 ].

Demostración.

1. Si f [∅] ̸= ∅ podemos considerar y ∈ f [∅]. Entonces, por definición, existe x ∈ ∅

tal que f (x) = y, lo cual es una contradición ya que ∅ no tiene elementos.

2. Sean A1 , A2 ⊆ X y y ∈ f [A1 ∩A2 ]. Entonces, existe x ∈ A1 ∩A2 tal que y = f (x).

Luego, existe x ∈ A1 tal que y = f (x) y existe x ∈ A2 tal que y = f (x). Por lo

que, y = f (x) ∈ f [A1 ] ∩ f [A2 ].

3. (⊆) Sea y ∈ f [A1 ∪ A2 ]. Entonces, existe x ∈ A1 ∪ A2 tal que y = f (x). Luego,

existe x ∈ A1 tal que y = f (x) o existe x ∈ A2 tal que y = f (x). Por lo tanto,

f [A1 ∪ A2 ] ⊆ f [A1 ] ∪ f [A2 ].

(⊇) Sea y ∈ f [A1 ] ∪ f [A2 ]. Entonces, existe x ∈ A1 ⊆ A1 ∪ A2 tal que y = f (x)

o bien, existe x ∈ A2 ⊆ A1 ∪ A2 tal que y = f (x). Sin importar el caso, existe

x ∈ A1 ∪ A2 tal que y = f (x). Por lo tanto, f [A1 ] ∪ f [A2 ] ⊆ f [A1 ∪ A2 ].

Teorema 3.37: Sean X, Y conjuntos y f : X → Y una función. Entonces, f es

inyectiva si y solo si para cualesquiera subconjuntos A1 , A2 de X se cumple f [A1 ∩

A2 ] = f [A1 ] ∩ f [A2 ].

63
Demostración. (⇒) Por el Lema 3.36 tenemos que la contención f [A1 ∩ A2 ] ⊆ f [A1 ] ∩

f [A2 ] es válida para cualesquiera subconjuntos A1 y A2 de X. Veamos la contención

contraria. Supongamos que f es inyectiva y sea y ∈ f [A1 ] ∩ f [A2 ]. Entonces, existen

x1 ∈ A1 y x2 ∈ A2 tales que f (x1 ) = y = f (x2 ). Dado que f es inyectiva se sigue que

x1 = x2 . Luego, existe x ∈ A1 ∩ A2 tal que y = f (x), es decir, y ∈ f [A1 ∩ A2 ]. Por lo

tanto, f [A1 ] ∩ f [A2 ] ⊆ f [A1 ∩ A2 ] y se obtiene la igualdad.

(⇐) Supongamos que f [A1 ∩ A2 ] = f [A1 ] ∩ f [A2 ] para cualesquiera conjuntos A1

y A2 de X. Sean x1 , x2 ∈ X tales que f (x1 ) = f (x2 ). Considerando A1 = {x1 } y

A2 = {x2 } tenemos que

f [A1 ] ∩ f [A2 ] = {f (x1 )} ∩ {f (x2 )} = {f (x1 )} =

̸ ∅.

Luego, por hipótesis f [A1 ∩A2 ] ̸= ∅ y usando el primer inciso del Lema 3.36 deducimos

que ∅ ̸= A1 ∩ A2 = {x1 } ∩ {x2 }. Esto último implica que x1 = x2 . Por lo tanto, f es

inyectiva.

Definición 3.38: Sean X, Y conjuntos, f : X → Y y B ⊆ Y . La preimagen de

B (o la imagen inversa de Y ) bajo f , denotada por Im(f )−1 [B], es el conjunto

Im(f )−1 [B] := {x ∈ X : f (x) ∈ B}.1

Ejemplos 3.39:

1. Sea f : A → B definida como f (x) = x2 donde A = {−1, 0, 1, 2} y B =

{0, 1, 2, 3, 4}. Sean C := {0, 4} y D := {0, 3, 4}. Entonces, Im(f )−1 [C] = {0, 2} =

Im(f )−1 [D] pero C ̸= D.

2. Sean A = {0, 1, 2}, B = {0, 1} y f : P(A) → P(B) dada por f (X) = X ∩ B. Sea

1
En otros textos encontras la notación f −1 [B] para este mismo conjunto. Nosotros adota-
mos nuestra notación para no confundirnos con la afirmación de que f −1 (la función inversa)
existe.

64
 C = {{0}, {0, 1}}. Entonces,

Im(f )−1 [C] = {{0}, {0, 2}, {0, 1}, {0, 1, 2}}.

Proposición 3.40: Sean X, Y conjuntos y f : X → Y una función. Entonces,

1. Im(f )−1 [∅] = ∅;

2. Si B1 , B2 son subconjuntos de Y entonces

Im(f )−1 [B1 ∪ B2 ] = Im(f )−1 [B1 ] ∪ Im(f )−1 [B2 ];

3. Si B1 , B2 son subconjuntos de Y entonces

Im(f )−1 [B1 ∩ B2 ] = Im(f )−1 [B1 ] ∩ Im(f )−1 [B2 ];

4. Si B ⊆ Y entonces

X \ Im(f )−1 [B] = Im(f )−1 [Y \ B].

Demostración.

1. Supongamos que Im(f )−1 [∅] ̸= ∅. Luego, existe x ∈ Im(f )−1 [∅], es decir, x =

f (y) para algún y ∈ ∅ lo cual es una contradicción. Por lo tanto, Im(f )−1 [∅] = ∅.

2. Sean B1 , B2 ⊆ Y . Entonces,

x ∈ Im(f )−1 [B1 ∪ B2 ] ⇔ f (x) ∈ B1 ∪ B2

⇔ f (x) ∈ B1 ∨ f (x) ∈ B2

⇔ x ∈ Im(f )−1 [B1 ] ∨ x ∈ Im(f )−1 [B2 ]

⇔ x ∈ Im(f )−1 [B1 ] ∪ Im(f )−1 [B2 ].

65
 3. Sean B1 , B2 ⊆ Y . Entonces,

x ∈ Im(f )−1 [B1 ∩ B2 ] ⇔ f (x) ∈ B1 ∩ B2

⇔ f (x) ∈ B1 ∧ f (x) ∈ B2

⇔ x ∈ Im(f )−1 [B1 ] ∧ x ∈ Im(f )−1 [B2 ]

⇔ x ∈ Im(f )−1 [B1 ] ∩ Im(f )−1 [B2 ].

4. Sea B ⊆ Y . Entonces,

x ∈ Im(f )−1 [Y \ B] ⇔ f (x) ∈ Y \ B

⇔ f (x) ∈ Y ∧ f (x) ∈
/B

⇔ / Im(f )−1 [B]

x∈X ∧x∈

⇔ x ∈ X \ Im(f )−1 [B].

Lema 3.41: Sean X, Y conjuntos y f : X → Y una función. Entonces,

1. Para cualquier A ⊆ X, se tiene que A ⊆ Im(f )−1 [f [A]];

2. Para cualquier B ⊆ Y , se tiene que f [Im(f )−1 [B]] ⊆ B;

3. Para cualquier A ⊆ X, se tiene que f [X] \ f [A] ⊆ f [X \ A].

Demostración.

1. Sean A ⊆ X y a ∈ A. Es claro que f (a) ∈ f [A]. Luego, por definición se tiene

que a ∈ Im(f )−1 [f (A)]. Por lo tanto, la contención A ⊆ Im(f )−1 [f [A]] es cierta.

2. Sean B ⊆ Y y y ∈ f [Im(f )−1 [B]]. Entonces, y = f (x) para algún x ∈ Im(f )−1 [B].

Como x ∈ Im(f )−1 [B] tenemos que f (x) ∈ B. Luego, y ∈ B. Por lo tanto,

f [Im(f )−1 [B]] ⊆ B.

3. Sean A ⊆ X y y ∈ f [X] \ f [A]. Entonces, y = f (x) para algún x ∈ X y y ∈

/ f [A]

de donde se sigue que x ∈

/ A. Luego, existe x ∈ X \ A tal que y = f (x). Por lo

tanto, y ∈ f [X \ A] y la contención f [X] \ f [A] ⊆ f [X \ A] es cierta.

66
Teorema 3.42: Sean X, Y conjuntos y f : X → Y una función. Entonces,

1. f es inyectiva si y solo si para cualquier A ⊆ X se cumple que

A = Im(f )−1 [f [A]].

2. f es suprayectiva si y solo si para cualquier B ⊆ Y se cumple que

f [Im(f )−1 [B]] = B.

3. f es biyectiva si y solo si para cualquier A ⊆ X se cumple que

Y \ f [A] = f [X \ A].

Demostración.

1. (⇒) Supongamos que f es inyectiva y A ⊆ X. Por el Lema 3.41 tenemos la

contención A ⊆ Im(f )−1 [f [A]], por lo que, es suficiente probar f −1 [f [A]] ⊆ A.

Sea x ∈ Im(f )−1 [f [A]]. Entonces, f (x) ∈ f [A]. Luego, existe a ∈ A tal que

f (x) = f (a). Dado que f es inyectiva, tenemos que x = a ∈ A. Por lo tanto,

Im(f )−1 [f [A]] ⊆ A y se sigue la igualdad.

(⇐) Supongamos que la igualdad A = Im(f )−1 [f [A]] es cierta para cualquier

A ⊆ X. Sean x, y ∈ X tales que f (x) = f (y). Consideremos A1 = {x} y A2 =

{y}. Por hipótesis, {x} = A1 = Im(f )−1 [f [A1 ]] = Im(f )−1 [{f (x)}] y {y} =

A2 = Im(f )−1 [f [A2 ]] = Im(f )−1 [{f (y)}]. Dado que f (x) = f (y) obtenemos

que

A1 = Im(f )−1 [{f (x)}] = Im(f )−1 [{f (y)}] = A2

y por tanto, x = y.

2. (⇒) Supongamos que f es sobre y sea B ⊆ Y . Por el Lema 3.41 tenemos la

67
 contención f [Im(f )−1 [B]] ⊆ B. Veamos la contención contraria, sea y ∈ B.

Dado que f es sobre, existe x ∈ X tal que y = f (x). Como y ∈ B se tiene

que x ∈ Im(f )−1 [B]. Luego, y = f (x) con x ∈ Im(f )−1 [B]. Por lo tanto,

y ∈ f [Im(f )−1 [B]].

(⇐) Supongamos que f [Im(f )−1 [B]] = B para cualquier B ⊆ Y . En particular,

considerando B = Y tenemos que f [Im(f )−1 [Y ]] = Y . Como Im(f )−1 [Y ] = X

(ya que f : X → Y ) se sigue que f [X] = Y . Por lo tanto, im(f ) = Y y ası́, f es

sobre.

3. (⇒) Supongamos que f es biyectiva y sea A ⊆ X. Veamos que Y \f [A] = f [X \A]

por doble contención.

(⊆) Como f es sobre se tiene que f [X] = Y . Por el Lema 3.41, tenemos que

Y \ f [A] = f [X] \ f [A] ⊆ f [X \ A].

(⊇) Sea y ∈ f [X \ A]. Entonces, y = f (x) para algún x ∈ X \ A. Como el

codominio de f es Y , se tiene que y = f (x) ∈ Y . Por lo que, basta probar que

/ f [A]. En efecto, si y ∈ f [A] existe x′ ∈ A tal que f (x) = y = f (x′ ) y

f (x) ∈

como f es inyectiva se sigue que x = x′ ∈ A lo cual es una contradicción. Por lo

tanto, y ∈ Y \ f [A] y la contención f [X \ A] ⊆ Y \ f [A] se cumple.

(⇐) Supongamos que la igualdad Y \ f [A] = f [X \ A] es cierta para cualquier

A ⊆ X. Veamos que f es biyectiva.

• f es inyectiva. Sean a1 , a2 ∈ X tales que a1 ̸= a2 . Veamos que f (a1 ) ̸= f (a2 ).

Consideremos A = {a1 }. Como a1 ̸= a2 se tiene que a2 ∈ X \ A y entonces

f (a2 ) ∈ f [X \ A]. Por hipótesis, f [X \ A] = Y \ f [A] de donde se obtiene que

f (a2 ) ∈
/ f [A] = {f (a1 )}, es decir, f (a2 ) ̸= f (a1 ).

• f es sobre. Por contradicción, supongamos que existe y ∈ Y tal que para todo

x ∈ X f (x) ̸= y. Entonces, y ∈ Y \ f [X] y por hipótesis (tomando A = X) tene-

mos que y ∈ f [X \ X] = f [∅] = ∅ (ver el Lema 3.36) lo cual es una contradicción.

Por lo tanto, f es sobre. Concluimos que f es biyectiva.

68
3.6. Composición de funciones y fun-

ciones inversas
Definición 3.43: Dos funciones f : A → B y g : A → B son iguales si y solo si para

toda x ∈ A, f (x) = g(x).

Ejemplos 3.44:

1. Las funciones f : N → N y g : N → N dadas por f (x) = 2 | x | y g(x) = 2x son

iguales.

2. Las funciones f : Z → Z y g : Z → Z dadas por f (x) = 2 | x | y g(x) = 2x no

son iguales.

Definición 3.45: Sean A, B, C conjuntos y B ′ ⊆ B. Si f : A → B ′ y g : B → C,

definimos la composición de f seguida de g, denotada por g ◦ f como la función g ◦ f :

A → C tal que para toda x ∈ A, (g ◦ f )(x) = g(f (x)).

Ejemplos 3.46:

1. Sean f : R → R y g : R → R definidas por f (x) = x2 + 1 y g(x) = 3x + 2.

Entonces, (g ◦ f )(x) = 3x2 + 5 y (f ◦ g)(x) = 9x2 + 12x + 5. Notemos que

(g ◦f )(2) ̸= (f ◦g)(2). Por lo que, la composición de funciones no es conmutativa.

2. Sea f : Z → Z dada por f (x) = −x + 1. Sean A = {0, −1, 1, 2}, B = {0, 1, 2, 3, 4}

y g : A → B dada por g(x) = x2 . Entonces, la composición f ◦ g : A → Z está

dada por (f ◦ g)(a) = −(a2 ) + 1 para todo a ∈ A.

3. Sea A = {1, 2, 3, 4, 5} y f : A → A, g : A → A definidas como:

   
 1 2 3 4 5   1 2 3 4 5 
f =  y g= .
3 2 5 1 4 1 2 5 4 3

69
 Entonces, f ◦ g : A → A y g ◦ f : A → A están dadas por:

   
 1 2 3 4 5   1 2 3 4 5 
g◦f =  y f ◦g = .
5 2 3 1 4 3 2 4 1 5

Concluimos que g ◦ f ̸= f ◦ g.

Definición 3.47: Sea A un conjunto. La función identidad en A, denotada por idA ,

está definida como idA : A → A donde idA (a) = a para toda a ∈ A.

Observación 3.48: Para cualquier función f : A → B, se cumple que idB ◦ f = f

y f ◦ idA = f .

Definición 3.49: Sea f : A → B una función. Un inverso izquierdo (respectivamen-

te, derecho) de f es una función g : B → A tal que g ◦ f = idA (respectivamente,

f ◦ g = idB ).

Ejemplos 3.50:
√
1. Sean f : R → [0, ∞) con f (x) = x2 y g : [0, ∞) → R con g(x) = x. Entonces,

f ◦ g = id[0,∞) pero g ◦ f ̸= idR .

2. Sean A = {1, 2, 3, 4} y B = {5, 6, 7} y f : A → B definida como

 
 1 2 3 4 
f = .
5 5 6 7

Consideremos g : B → A y h : B → A dadas por

   
 5 6 7   5 6 7 
g=  y h= .
1 3 4 2 3 4

Notemos que g ̸= h. Además, f ◦ g = f ◦ h = idB pero g ◦ f ̸= idA ̸= h ◦ f .

Por lo que, g y h son dos inversos derechos (distintos) de f pero no son inversos

70
 izquierdos de f .

3. Sean A = {1, 2, 3} y B = {4, 5, 6, 7} y f : A → B definida como

 
 1 2 3 
f = .
4 5 6

Consideremos g : B → A y h : B → A dadas por

   
 4 5 6 7   4 5 6 7 
g=  y h= .
1 2 3 1 1 2 3 2

Notemos que g ̸= h. Además, g ◦ f = h ◦ f = idA pero f ◦ g ̸= idB ̸= f ◦ h. Por

lo que, g y h son dos inversos izquierdos (distintos) de f pero no son inversos

derechos de f .

Teorema 3.51: Sean A, B conjuntos y f : A → B una función. Entonces,

1. Si A ̸= ∅, entonces f es inyectiva si y solo si f tiene inverso izquierdo.

2. f es suprayectiva si y solo si f tiene inverso derecho.

Demostración. Sean A, B conjuntos y f : A → B una función.

1. (⇒) Supongamos que f es inyectiva. Como A ̸= ∅ considera a0 ∈ A. Definimos

g : B → A de la siguiente manera:

 a

si f (a) = b
g(b) =
 a0 si b ∈
/ f [A].


Notemos que como f es inyectiva, si b ∈ f [A], existe una única a ∈ A tal que

f (a) = b. Ası́, g está bien definida, es decir, g es función. Ahora bien, de la

definición de composición, tenemos que g ◦ f y idA tienen el mismo dominio y

codominio. Además, para a ∈ A, se cumple que (g ◦ f )(a) = g(f (a)) = a =

idA (a). Por lo tanto, g ◦ f = idA y f tiene inverso izquierdo.

71
 (⇐) Supongamos que f tiene inverso izquierdo y sean x, y ∈ A tales que f (x) =

f (y). Como f tiene inverso izquierdo, existe g : B → A tal que g ◦ f = idA .

Luego,

x = idA (x) = (g ◦ f )(x) = g(f (x)) = g(f (y)) = (g ◦ f )(y) = idA (y) = y.

Por lo tanto, f es inyectiva.

2. (⇒) Supongamos que f es sobre y sea b ∈ B. Entonces, el conjunto {a ∈ A :

f (a) = b} ̸= ∅. De este conjunto, elegimos uno y solo un elemento ab , tal que

f (ab ) = b. Definimos la función g : B → A como g(b) := ab . Notemos que g está

bien definida (es decir, es función) ya que elegimos uno y solo un ab . También,

notemos que f ◦g y idB tienen el mismo dominio y el mismo codominio. Además,

para b ∈ B se cumple que (f ◦ g)(b) = f (g(b)) = f (ab ) = b = idB (b). Por lo que,

f ◦ g = idB y f tiene inverso derecho.

(⇐) Supongamos que f tiene inverso derecho y sea b ∈ B. Entonces, existe

g : B → A tal que f ◦ g = idB . Como b ∈ B se tiene que g(b) ∈ A y f (g(b)) =

(f ◦g)(b) = idB (b) = b. De aquı́ obtenemos que existe a ∈ A (tomando a := g(b))

tal que f (a) = b. Por lo tanto, f es sobre.

Ejemplo 3.52: Sean f : Z → Z y g : Z → Z dadas por f (n) = 2n y g(n) = ⌊ n2 ⌋,

donde ⌊x⌋ es el mayor entero menor o igual que x. Entonces, g◦f = idZ pero f ◦g ̸= idZ .

Lema 3.53: Sean A, B, C, D conjuntos, B ′ ⊆ B y C ′ ⊆ C. Sean f : A → B ′ ,

g : B → C ′ y h : C → D funciones. Entonces, h ◦ (g ◦ f ) = (h ◦ g) ◦ f .

Demostración. Por definición de composición de funciones se tiene que h ◦ (g ◦ f ) y

(h ◦ g) ◦ f tienen el mismo dominio y codominio. Ahora sea x ∈ A. Por una parte,

(h ◦ (g ◦ f ))(x) = h((g ◦ f )(x)) = h(g(f (x))). Por otra parte, ((h ◦ g) ◦ f )(x) =

(h ◦ g)(f (x)) = h(g(f (x))). Por lo tanto, h ◦ (g ◦ f ) = (h ◦ g) ◦ f y la composición es

72
asociativa.

Teorema 3.54: Sea f : A → B una función. Si g1 : B → A es un inverso izquierdo

de f y g2 : B → A es un inverso derecho de f entonces g1 = g2 .

Demostración. Como g1 es un inverso izquierdo de f se tiene que g1 ◦ f = idA . Por

otra parte, como g2 es un inverso derecho de f se cumple f ◦ g2 = idB . Luego, g1 =

g1 ◦ idB = g1 ◦ (f ◦ g2 ) = (g1 ◦ f ) ◦ g2 = idA ◦ g2 = g2 .

Definición 3.55: Sea f : A → B una función. Decimos que f es invertible si y solo

si existe una función g : B → A tal que g ◦ f = idA y f ◦ g = idB .

Ejemplo 3.56: Sean X = {0, 1, 2}, Y = {0, 1, 4} y h : X → Y dada por h(x) = x2 .

Entonces, h = {(0, 0), (1, 1), (2, 4)} como relación mientras que la relación inversa de h

es h−1 = {(0, 0), (1, 1), (4, 2)}. Notemos que h−1 es función y su dominio es Y . Luego,

h−1 : Y → X. Además, h ◦ h−1 = idY y h−1 ◦ h = idX .

Proposición 3.57: Sea f : A → B una función y f −1 la relación inversa de f . Los

siguientes enunciados se cumplen.

1. Si f −1 es función y f −1 : B → A, entonces f ◦ f −1 = idB y f −1 ◦ f = idA .

2. f es invertible si y solo si f −1 es una función y f −1 : B → A.

3. Si f es invertible, el inverso derecho e izquierdo de f es f −1 .

Demostración. Sea f : A → B una función y f −1 la relación inversa de f .

1. Supongamos que f −1 es función y f −1 : B → A. Entonces, para todo b ∈ B,

existe un único ab ∈ A tal que f −1 (b) = ab . Además, f −1 (b) = ab si y solo si

f (ab ) = b. Por definición de composición, f ◦ f −1 y idB tienen el mismo dominio

y codominio. Ahora bien, sea b ∈ B. Entonces, (f ◦ f −1 )(b) = f (f −1 (b)) =

f (ab ) = b = idB (b). Por lo tanto, f ◦ f −1 = idB . Análogamente, f −1 ◦ f = idA .

2. (⇒) Supongamos que f es invertible. Entonces, f tiene inverso izquierdo y de-

recho. Veamos que dom(f −1 ) = B. Por definición, dom(f −1 ) ⊆ B. Para la otra

73
 contención, sea b ∈ B. Como f tiene inversa derecha se tiene que f es sobre por

el Teorema 3.51. Luego, existe a ∈ A tal que f (a) = b, es decir, (a, b) ∈ f lo

cual implica (b, a) ∈ f −1 . Entonces, b ∈ dom(f −1 ) y ası́, B ⊆ dom(f −1 ). Por lo

tanto, dom(f −1 ) = B.

• f −1 es función. Sea (y, x1 ) ∈ f −1 y supongamos que (y, x2 ) ∈ f −1 . Veamos

que x1 = x2 . Entonces, (x1 , y) ∈ f y (x2 , y) ∈ f . Como f es función se tiene

que f (x1 ) = y = f (x2 ). Ahora bien, dado que f tiene inverso izquierdo, f es

inyectiva por el Teorema 3.51. Por lo que, x1 = x2 . Concluimos que f −1 es

función y f −1 : B → A.

(⇐) Se sigue por el inciso anterior.

3. Es consecuencia de los incisos anteriores.

Corolario 3.58: Sea f : A → B una función con A ̸= ∅. Entonces,

1. f es invertible si y solo si f es biyectiva.

2. f es biyectiva si y solo si f −1 es una función con dominio B.

Demostración. Sea f : A → B una función con A ̸= ∅.

1. (⇒) Por el Teorema 3.57, si f es invertible entonces f −1 es el inverso izquierdo

y el derecho de f . Luego, por el Teorema 3.51 se sigue que f es inyectiva y

suprayectiva. Por lo tanto, f es biyectiva.

(⇐) Si f es biyectiva, por el Teorema 3.51, f tiene inverso izquierdo y derecho.

Usando el Teorema 3.54, tenemos que el inverso izquierdo y el derecho de f

coinciden. Por lo tanto, f es invertible.

2. Por el inciso anterior, f es biyectiva si y solo si f es invertible. Por la Proposi-

ción 3.57 se tiene que f es invertible si y solo si f −1 es una función y f −1 : B → A.

Por lo tanto, f es biyectiva si y solo si f −1 es una función con dominio B.

74
Capı́tulo 4
Números naturales
En este capı́tulo daremos la definición de Von Neumann para los números

naturales. Definimos un orden lineal en este conjunto, y las operaciones

suma y multiplicación. Probamos ciertas propiedades de lo anterior usando

el Principio de inducción y finalmente, veremos como otros principios de

inducción están relacionados.

A finales del siglo XX, después de los desarrollos, gracias a David Hilbert, del

método axiomático, Giuseppe Peano introdujo una axiomatización de los números na-

turales. Los matemáticos (y toda persona que supiera contar) llevaban trabajando con

los números naturales por milenios. Sin embargo, dado el nuevo impulso formaliza-

dor de las matemáticas, resultaba deseable idear una definición axiomática de estos

números. Lo que sigue es la propuesta de este matemático, definición que hoy en dı́a

es estándar

Definición 4.1(Axiomas de Peano): Dados 0, N conjuntos y s una relación cuyo

dominio es N. Los Axiomas de Peano son los siguientes:

• Axioma 1. 0 ∈ N.

• Axioma 2. ∀ n ∈ N, hay un único m ∈ N tal que (n, m) ∈ s. Es decir, s es

función y s : N → N.

• Axioma 3. ∀n ∈ N s(n) ̸= 0. Es decir, 0 ∈

/ im(s).

• Axioma 4. ∀n, m ∈ N, s(n) = s(m) → n = m. Es decir, s es inyectiva.

• Axioma 5 (Principio de Inducción). Si A ⊆ N es tal que:

a) 0 ∈ A y;

b) ∀n ∈ N, n ∈ A → s(n) ∈ A,

75
 entonces N ⊆ A.

Notemos que por el Axioma de extensionalidad, esto último implica N = A.

Observa que esta definición no es ”constructiva”, es decir, afirma que si un conjunto

N satisface los 5 axiomas de Peano entonces a ese conjunto le llamaremos el conjunto

de los números naturales. Sin embargo, no nos dice quiénes son ni como se ven los

naturales.

Recuerda que desde la teorı́a de conjuntos un objeto existe si y sólo si es un

conjunto. Siendo ası́, la teorı́a de conjuntos nos exige una ”construcción” de los núme-

ros naturales, es decir, exhibir unos conjuntos que pueden ”interpretarse” como el

0, 1, 2 . . . y que satisfagan los axiomas de Peano.

Existen varias construcciones de los naturales, algunas de las famosas son la de

Cantor y la de Von Neumann, esta última es más pedagógica, ası́ que es la que usare-

mos.

Definición 4.2(Definición de Von Neumann): El conjunto de números natu-

rales, denotado por N, es el conjunto cuyos elementos son:

0 := ∅,

1 := 0 ∪ {0} = ∅ ∪ {∅} = {∅} = {0},

2 := 1 ∪ {1} = {0} ∪ {1} = {0, 1},

3 := 2 ∪ {2} = {0, 1} ∪ {2} = {0, 1, 2}

..
.

s(n) := n ∪ {n} = {0, 1, . . . , n},

..
.

Notemos que si n es un número natural, entonces s(n) := n∪{n} es un número natural,

a s(n) lo llamamos el sucesor de n y a s : N → N dada por n 7→ s(n) la función sucesor .

Se puede demostrar que los números naturales definidos como Von Neumann cumplen

los Axiomas de Peano. No lo vamos a hacer pues supera los objetivos del curso.

76
4.1. Suma y multiplicación
Para desarrollar esta sección necesitaremos el siguiente Teorema cuya prueba se omi-

te. El teorema se conoce como Teorema de recursión. Este teorema afirma que los

naturales traen ”de regalo” un método constructivo para crear nuevas funciones con

dominio mathbbN . La prueba se puede hacer con métodos algebráicos o conjuntistas,

pero es compleja y no ofrece mucho a la comprensión de los naturales que no sepas

ya.

Teorema 4.3(Teorema de Recursión): Sean X un conjunto, x0 ∈ X y f : X →

X una función. Entonces, existe una única función g : N → X tal que g(0) = x0 y

g(s(n)) = f (g(n)) para todo n ∈ N.

Definición 4.4(Sumar m): Sea m ∈ N. Usando el Teorema de Recursión con

X = N, x0 = m y f = s la función sucesor, existe una única función m + ( ) : N → N

tal que m + (0) = m y m + (s(n)) = s(m + (n)) para todo n ∈ N. A dicha función la

llamamos la función sumar m.

Figura 4.1: Esquema ilustrativo del Teorema de la recursión

Observa que en lugar de definir la operación ( )+( ) : N → N, directamente lo que

77
hacimos fue definir ”la tabla de sumar” de m ∈ N, usando el teorema de recursión. Sin

embargo, no importa, pues ahora ya podemos definir esta operación correctamente.

Definición 4.5: La suma en N es la función +(−, −) : N × N → N tal que (m, n) 7→

m + (n). Usaremos la notación m + n en lugar de +(m, n).

Observación 4.6: En particular, usando las definiciones anteriores obtenemos que:

1. 0 + 0 = 0 y 0 + s(n) = s(0 + n) para todo n ∈ N.

2. n + 1 = n + s(0) = s(n + 0) = s(n) para todo n ∈ N.

Ahora repetimos el proceso para la multiplicación y la exponenciación.

Definición 4.7(Multiplicar por m): Sea m ∈ N. Por el Teorema de Recursión,

tomando X = N, x0 = 0 y f = m+(−) (la función sumar m), existe una única función

m • (−) : N → N tal que m • (0) = 0 y m • (s(n)) = m + (m • (n)) para todo n ∈ N. A

esta función la llamamos multiplicar por m.

Definición 4.8: La multiplicación en N es la función •(−, −) : N × N → N tal que

(m, n) 7→ m • (n). Por motivos prácticos escribiremos m · n o bien mn, en lugar de

•(m, n).

Observación 4.9: En particular, se cumple que 0 · 0 = 0 y 0 · s(n) = 0 + 0 · n para

todo n ∈ N.

Definición 4.10(Exponenciar m): Sea m ∈ N. Por el Teorema de Recursión,

tomando X = N, x0 = 1 y f = m • (−) (la función multiplicar por m), existe una

única función m(−) : N → N tal que m(0) = 1 y m(s(n)) = m · m(n) para todo n ∈ N.

Definición 4.11: La exponenciación en N es la función (−)(−) : N × N → N tal que

(m, n) 7→ m(n) . Escribiremos mn en lugar de (m)(n) .

78
4.2. Principio de inducción
Ahora que ya definimos nuestra operaciones, quisiéramos probar que cumplen ciertas

propiedades, en particular: asociatividad, conmutatividad y distributividad. Una per-

sona muy sabia dijo una vez ”si quieres probar algo sobre los naturales, la prueba va

a ser por inducción”. Esta frase refleja que el quinto axioma de Peano nos ofrece un

método de prueba único para los naturales. En esta sección vamos a estudiarlo.

Esta técnica muy conocida de demostración llamada “prueba por inducción”. Esta

técnica consiste en utilizar el Axioma 5 de Peano como herramienta, para demostrar

una propiedad sobre los números naturales. La técnica comienza definiendo un con-

junto inductivo A ⊆ N, y lo que se busca es probar que A = N, y está dividida en las

siguientes partes:

1. Paso base. Verificar primero que 0 ∈ A. En ocasiones, se tendrá que checar que

la propiedad es cierta para naturales n ≥ 1, dependiendo del enunciado.

2. Paso inductivo. Consiste en suponer que n ∈ A, a esto se le llama hipótesis de

inducción (HI), y bajo esta suposición demostrar que s(n) ∈ A.

El hecho de que A = N permite concluir que el resultado es cierto utilizando el

Axioma 5.

Veamos un ejemplo.

Lema 4.12: Para toda n ∈ N, se tiene que s(n) ̸= n.

Demostración. Sea

A := {n ∈ N : s(n) ̸= n} ⊆ N

queremos ver que A = N. Hacemos la prueba por inducción sobre n.

1. Paso base. Veamos que el resultado es cierto para n = 0. Por el Axioma 3, se

tiene que s(n) ̸= 0 para todo n ∈ N. En particular, s(0) ̸= 0 y ası́, 0 ∈ A.

2. Demostremos que si para n es cierto el resultado entonces para s(n) = n + 1

también es cierto.

79
 Hipótesis de Inducción Supongamos que n ∈ A, esto es, s(n) ̸= n.

Paso inductivo. Veamos que s(n) ∈ A, es decir, s(s(n)) ̸= s(n). Por el Axioma

4, sabemos que s es inyectiva y dado que s(n) ̸= n se sigue que s(s(n)) ̸= s(n)

lo cual implica que s(n) ∈ A.

Por lo tanto, por el Axioma 5 concluimos que A = N. Por lo tanto para toda n ∈ N,

s(n) ̸= n.

Teorema 4.13: Para cualquier n ∈ N, se tiene que n = 0 o que existe m ∈ N tal

que s(m) = n.

Demostración. Sea

A = {n ∈ N : n = 0 o existe m ∈ N tal que s(m) = n} ⊆ N.

Queremos ver que A = N. Hacemos la prueba por inducción sobre n.

1. Paso base. Veamos que el resultado es cierto para n = 0. Por como se define A,

es claro que 0 ∈ A.

2. Demostremos que si para n es cierto el resultado entonces para s(n) = n + 1

también es cierto.

Hipótesis de inducción. Supongamos que n ∈ A.

Paso inductivo. Veamos que s(n) ∈ A. En efecto, como A ⊆ N se tiene que

n ∈ A. Luego, existe m ∈ N, a saber n mismo, tal que s(m) = s(n), usando que

s es función por el Axioma 2.

Por lo tanto, por el Axioma 5 concluimos que A = N. Esto nos permite concluir el

resultado

Teorema 4.14(Asociatividad de la suma): Para cualesquiera a, b y n ∈ N, se

tiene que (a + b) + n = a + (b + n).

80
Demostración. Sean a y b cualesquiera naturales y

A = {n ∈ N : (a + b) + n = a + (b + n)} ⊆ N.

Queremos ver que A = N. Hacemos la prueba por inducción sobre n.

1. Paso base. Veamos que el resultado es cierto para n = 0. Como

(a + b) + 0 = a+b (definición de +),

= a + (b + 0) (definición de +),

se sigue que 0 ∈ A.

2. Demostremos que si para n es cierto el resultado entonces para s(n) = n + 1

también es cierto.

Hipótesis de Inducción. Supongamos que n ∈ A, esto es, (a+b) +n = a+ (b+n).

Paso inductivo.Veamos que s(n) ∈ A, es decir, (a + b) + s(n) = a + (b + s(n)).

(a + b) + s(n) = s((a + b) + n) (definición de +),

= s(a + (b + n)) (HI ),

= a + s(b + n) (definición de +),

= a + (b + s(n)) (definición de +),

tenemos que s(n) ∈ A.

Por lo tanto, por el Axioma 5 concluimos que A = N.

Notemos que por el resultado anterior podemos simplemente escribir a + b + n, sin

riesgo de confusión, ya que (a + b) + n = a + (b + n).

Teorema 4.15(Cancelación de la suma): Para cualesquiera a, b y n ∈ N, si

a + n = b + n entonces a = b.

81
Demostración. Sean a y b cualesquiera naturales y

A = {n ∈ N : a + n = b + n implica a = b} ⊆ N.

Queremos ver que A = N. Hacemos la prueba por inducción sobre n.

1. Paso base. Veamos que el resultado es cierto para n = 0. Supongamos que a+0 =

b + 0. Por la definición de suma, se tiene que a + 0 = a y b + 0 = b. Por lo tanto,

a = a + 0 = b + 0 = b y ası́, 0 ∈ A.

2. Demostremos que si para n es cierto el resultado entonces para s(n) = n + 1

también es cierto.

Hipótesis de inducción. Supongamos que n ∈ A, esto es, que si a + n = b + n

entonces a = b.

Paso inductivo. Veamos que s(n) ∈ A, es decir, que si a+s(n) = b+s(n) entonces

a = b. En efecto, supongamos que a + s(n) = b + s(n). Por la definición de suma,

sabemos que a + s(n) = s(a + n) y b + s(n) = s(b + n). Luego, s(a + n) = s(b + n).

Como la función s es inyectiva por el Axioma 4, se sigue que a + n = b + n y por

(HI) concluimos que a = b. Por ende, s(n) ∈ A.

Por lo tanto, por el Axioma 5 concluimos que A = N.

Teorema 4.16: Se tienen las siguientes propiedades de la suma:

1. Para cualquier n ∈ N, se tiene que 0 + n = n;

2. Para cualesquiera a y n ∈ N, se tiene que a + s(n) = s(a) + n;

3. Conmutatividad de la suma: Para cualesquiera a y n ∈ N, se tiene que

a + n = n + a;

4. Para cualesquiera a y n ∈ N, si a ̸= 0 entonces a + n ̸= 0;

5. Para cualesquiera a y b, a + b = 0 si y solo si a = 0 y b = 0.

Demostración. Ejercicio.

Ya terminamos con las propiedades de la suma en N, vamos ahora con las de la

82
multiplicación.

Lema 4.17: Para cualquier n ∈ N, se tiene que 1 · n = n.

Demostración. Sea A = {n ∈ N : 1 · n = n} ⊆ N. Queremos ver que A = N. Hacemos

la prueba por inducción sobre n.

1. Paso base. Veamos que el resultado es cierto para n = 0. Tenemos que 1 · 0 = 0

por la definición de multiplicación. Por lo tanto, 0 ∈ A.

2. Demostremos que si para n es cierto el resultado entonces para s(n) = n + 1

también es cierto.

Hipótesis de Inducción. Supongamos que n ∈ A, esto es, 1 · n = n.

Paso inductivo.Veamos que s(n) ∈ A, es decir, 1 · s(n) = s(n). En efecto, como

1 · s(n) = 1 + (1 · n) (definición de •),

= 1+n (HI ),

= n+1 (conmutatividad de +),

= s(n) (Observación 4.6).

Ası́, s(n) ∈ A.

Por lo tanto, por el Axioma 5 concluimos que A = N.

Teorema 4.18(Distributividad): Para cualesquiera a, b y n ∈ N, se tiene que

(a + b) · n = a · n + b · n.

Demostración. Sean a y b cualesquiera naturales y

A = {n ∈ N : (a + b) · n = a · n + b · n} ⊆ N.

Queremos ver que A = N. Hacemos la prueba por inducción sobre n.

83
 1. Paso base. Veamos que el resultado es cierto para n = 0. Como

(a + b) · 0 = 0 (definición de •, )

= a·0 (definición de •),

= (a · 0) + 0 (definición de +),

= (a · 0) + (b · 0) (definición de •).

se sigue que 0 ∈ A.

2. Demostremos que si para n es cierto el resultado entonces para s(n) = n + 1

también es cierto.

Hipótesis de Inducción. Supongamos que n ∈ A, esto es, (a + b) · n = a · n + b · n.

Paso inductivo. Veamos que s(n) ∈ A, es decir, (a + b) · s(n) = a · s(n) + b · s(n).

En efecto, como

(a + b) · s(n) = (a + b) + ((a + b) · n) (definición de •),

= (a + b) + (a · n + b · n) (HI ),

= (a + a · n) + (b + b · n) (asoc. y conmut. de +),

= a · s(n) + b · s(n) (definición de •).

tenemos que s(n) ∈ A.

Por lo tanto, por el Axioma 5 concluimos que A = N.

En ocasiones dentro de una demostración por inducción se necesita hacer otra demos-

tración por inducción, como veremos en el siguiente teorema. Esto se conoce como

inducción doble.

Teorema 4.19(Conmutatividad de la multiplicación): Para cualesquiera n, m ∈

N, se tiene que m · n = n · m.

Demostración. Sea A = {n ∈ N : ∀ m ∈ N (m · n = n · m)} ⊆ N. Queremos ver que

A = N. Hacemos la prueba por inducción sobre n.

84
1. Paso base. Veamos que el resultado es cierto para n = 0. Debemos demostrar que

para cualquier m ∈ N se tiene que m · 0 = 0 · m. Sea A′ = {m ∈ N : m · 0 = 0 · m}.

Para ver que A′ = N, haremos la prueba por inducción sobre m.

a) Paso base. Veamos que el resultado es cierto para m = 0. Por la definición

de multiplicación, 0 · 0 = 0 = 0 · 0. Por lo tanto, 0 ∈ A′ .

b) Demostremos que si para m es cierto el resultado entonces para s(m) =

m + 1 también es cierto.

Hipótesis de Inducción Supongamos que m ∈ A′ ; esto es, m · 0 = 0 · m.

Paso inductivo. Veamos que s(m) ∈ A′ , es decir, s(m) · 0 = 0 · s(m). En

efecto, como

0 · s(m) = 0 + (0 · m) (definición de •),

= 0 + (m · 0) (HI ),

= 0+0 (definición de •),

= 0 (definición de +),

= s(m) · 0 (definición de •).

Ası́, s(m) ∈ A′ . Por lo tanto, A′ = N.

2. Demostremos que si para n es cierto el resultado entonces para s(n) = n + 1

también es cierto.

Hipótesis de Inducción. Supongamos que n ∈ A; esto es, m · n = n · m.

Paso inductivo. Veamos que s(n) ∈ A, es decir, m · s(n) = s(n) · m. En efecto,

como
m · s(n) = m + (m · n) (definición de •),

= m + (n · m) (HI ),

= (1 · m) + (n · m) (Lema 4.17),

= (1 + n) · m (distributividad),

= (n + 1) · m (conmutatividad de +),

= s(n) · m (Observación 4.6).

85
 Por lo tanto, s(n) ∈ A y podemos concluir que A = N.

Teorema 4.20: Se tienen las siguientes propiedades del producto:

1. Asociatividad de la multiplicación. Para cualesquiera a, b, n ∈ N, se tiene

que (a · b) · n = a · (b · n).

2. Cancelación de la multiplicación. Para cualesquiera n, m, k ∈ N, si k ̸= 0 y

m · k = n · k entonces n = m.

3. Para cualesquiera a, b ∈ N, a · b = 0 si y solo si a = 0 o b = 0.

Demostración. Ejercicio.

4.3. Orden
Definición 4.21: Denotamos por N+ al conjunto N \ {0}, llamado el conjunto de

los naturales positivos.

Definición 4.22: La relación “menor que” en N × N, denotada por <, está definida

como m < n si y solo si existe t ∈ N+ tal que m + t = n. En este caso, decimos que

m es menor que n (o que n es mayor que m). Diremos que m es menor o igual que n

(o que n es mayor o igual que m) si y solo si m = n o m < n lo cual denotamos por

m ≤ n o bien n ≥ m.

Observación 4.23: Dados m, n ∈ N, se tiene que m ≤ n si y solo si existe t ∈ N tal

que n = m + t. En este caso, t es único (por la cancelación de la suma) y lo denotamos

por n − m. A dicho t lo llamamos la resta o diferencia de n menos m.

Lema 4.24: Se tienen las siguientes propiedades del orden:

1. Para cualquier n ∈ N, se tiene que 0 ≤ n;

86
 2. Para cualquier n ∈ N+ , se tiene que 0 < n;

3. Para cualquier n ∈ N, se tiene que n < s(n);

4. Para cualesquiera n y m ∈ N, si m < n entonces s(m) ≤ n;

5. Para cualquier n ∈ N, si n ̸= 0 entonces 1 ≤ n.

Demostración. Solo probaremos 4 y 5, los demás incisos se dejan como ejercicio.

4. Sean n, m ∈ N tales que m < n. Tenemos que n = m + t para alguna t ∈ N+ .

Como t ̸= 0, por el Teorema 4.13, sabemos que t = s(k) para alguna k ∈

N. Luego, n = m + s(k) = m + (k + 1). Por el Teorema 4.16, tenemos que

n = m + (k + 1) = (m + 1) + k = s(m) + k con k ∈ N. Por lo tanto, por la

Observación 4.23, concluimos que s(m) ≤ n.

5. Sea n ∈ N+ . Por el Teorema 4.13, tenemos que n = s(k) = k + 1 para alguna

k ∈ N. Por lo tanto, 1 ≤ n por la Observación 4.23.

Observación 4.25: Por el Teorema anterior podemos concluir que no existe un

natural entre el 0 y el 1.

Teorema 4.26: (N, ≤) es un conjunto parcialmente ordenado.

Demostración.

1. ≤ es reflexiva. Sea n ∈ N, como n + 0 = n, sea t = 0, entonces t ∈ N y n ≤ n

2. ≤ es antisimétrica Sean n, m ∈ N tales que n ≤ m y m ≤ n. Entonces existen

t, s ∈ N tales que n + t = m y m + s = n. Por lo tanto, n = m + s = (n + t) + s =

n + (t + s). Por ley de la cancelación 0 = t + s, lo que implia que t = 0 y s = 0.

Por lo que n = m

3. ≤ es transitiva. Sean a, b, c ∈ N tales que a ≤ b y b ≤ c. Luego, existen t, r ∈ N

tales que a = b + t y b = c + r. Entonces,

a = b + t = (c + r) + t = c + (r + t)

87
 por asociatividad de la suma. Usando el Teorema 4.16, se tiene que r + t ∈ N ya

que r, t ∈ N. Ası́, a = c + k para algún k ∈ N. Por lo tanto, a ≤ c.

Teorema 4.27: La relación ≤ en N es total. Es decir, dados n, m ∈ N tenemos que

n ≤ m ó m ≤ n.

Demostración. Sean n ∈ N y A = {m ∈ N : m ≤ m o m ≤ n} ⊆ N. Haremos la

prueba por inducción sobre b.

1. Paso base. Veamos que el resultado es cierto para m = 0. Por el Lema 4.24, se

tiene que 0 ≤ n. Por lo que, 0 ∈ A.

2. Demostremos que si para m es cierto el resultado entonces para s(m) = m + 1

también es cierto.

Hipótesis de Inducción. Supongamos que m ∈ A; esto es, n ≤ m o m ≤ n.

Paso inductivo. Veamos que s(m) ∈ A, es decir, n ≤ s(m) o s(m) ≤ n. Si n ≤ m,

por el Lema 4.24, sabemos que m ≤ s(m) y por la transitividad, n ≤ s(m). Si

m ≤ n, tenemos dos casos, si m < n por el Lema 4.24, s(m) ≤ n. Si m = n

entonces n = m ≤ s(m). Luego, s(m) ∈ A en todos los casos.

Por lo tanto, A = N por el Axioma 5.

Corolario 4.28: ≤ es una relación de orden total sobre N.

Demostración. Se sigue de los Teoremas 4.26 y 4.27.

Observación 4.29(Tricotomı́a): Para cualesquiera a, b ∈ N se dá uno y solamente

uno de los siguientes casos: a < b o a = b o b < a.

Teorema 4.30: Se cumple lo siguiente.

1. Para cualesquiera n, m ∈ N, si m ̸= 0, entonces n < n + m;

2. Para cualesquiera n, m ∈ N, se tiene que n ≤ n + m;

88
 3. Para cualesquiera n, m, k ∈ N, n < m si y solo si n + k < m + k;

4. Para cualesquiera n, m, k ∈ N, si k ̸= 0 y n < m, entonces n · k < m · k;

5. Para cualesquiera n, m, k ∈ N, si n · k < m · k, entonces n < m;

6. Para cualesquiera n, m ∈ N, si m ̸= 0, entonces n ≤ n · m;

7. Para cualesquiera n, m ∈ N+ , si m ̸= 1, entonces n < n · m.

Demostración.

1. Sean n, m ∈ N tales que m ̸= 0, denotamos por k a la suma de n + m, es decir,

k = n + m. Entonces, k = n + m con m ∈ N+ . Ası́, por definición de orden,

n < k, es decir, n < n + m.

4. Sean n, m, k ∈ N tales que k ̸= 0 y n < m. Tenemos que m = n + t para

algún t ∈ N+ , y entonces m · k = (n + t) · k = n · k + t · k, por distributividad.

Por el Teorema 4.20, como t y k ∈ N+ se tiene que t · k ∈ N+ . Por lo tanto,

m · k = n · k + t · k con t · k ∈ N+ y ası́, n · k < m · k.

5. Sean n, m, k ∈ N tales que n · k < m · k. Observemos que en este caso k ̸= 0,

ya que m · 0 = 0 y no existe un natural menor que 0, por el Lema 4.24. Por

tricotomı́a, sabemos que n < m o n = m o m < n. Ahora bien, si n = m, se

tendrı́a que n · k = m · k; y si m < n, por el inciso anterior, m · k < n · k, lo que

contradice que n · k < m · k, por la Observación 4.29. Por lo tanto, n < m.

Los demás incisos se dejan como ejercicio.

En ocasiones queremos demostrar que todos los números naturales mayores que algún

natural k cumplen una propiedad. Podemos probar esto con una versión alternativa

del Principio de inducción: en el paso base se prueba que el resultado es cierto para

el primer natural en el que se afirma que se cumple, es decir, k; luego se hace el paso

inductivo de manera análoga a la versión original del Axioma 5.

Definición 4.31: Definimos la operación factorial de forma recursiva de la siguiente

manera: 0! = 1 y s(n)! = n! · s(n).

89
Proposición 4.32: Para cualquier n ∈ N, si n ≥ 4 entonces 2n < n!.

Demostración. Primera demostración. Sea

A = {n ∈ N : n ≥ 4 ⇒ 2n < n!} ⊆ N.

Queremos ver que A = N. Hacemos la prueba por inducción sobre n.

1. Paso base. Veamos que el resultado es cierto para n = 4.1 Como 24 = 16 y

4! = 4 · 3 · 2 · 1 = 24 el resultado se cumple para n = 4.

2. Demostremos que si para n es cierto el resultado entonces para s(n) = n + 1

también es cierto.

Hipótesis de Inducción Supongamos que 2n < n! con n ≥ 4.2

Paso inductivo. Veamos que 2n+1 < (n + 1)!. En efecto, como n ≥ 4 se tiene

que 2 < n + 1. Además, por hipótesis de inducción, 2n < n!. Entonces, 2n · 2 <

n! · (n + 1), por lo que 2n+1 < (n + 1)!. Luego, si la afirmación se cumple para

n se cumple para n + 1.

Segunda demostración. La proposición es equivalente a demostrar: para cual-

quier n ∈ N, se tiene que 2n+4 < (n + 4)!. Sea

A = {n ∈ N : 2n+4 < (n + 4)!} ⊆ N.

Queremos ver que A = N. Hacemos la prueba por inducción sobre n.

1. Paso base. Veamos que el resultado es cierto para n = 0. Como 20+4 = 24 = 16

y (0 + 4)! = 4! = 4 · 3 · 2 · 1 = 24 el resultado se cumple para n = 0.

2. Demostremos que si para n es cierto el resultado entonces para s(n) = n + 1

1
Notemos que, si n no es mayor que 4, el antecedente de la implicación n ≥ 4 ⇒ 2n < n!
es falso, por lo que se cumplirı́a también el resultado en este caso.
2
Si no es cierto que n ≥ 4 entonces 0 ≤ n ≤ 3. Luego, 1 ≤ n + 1 ≤ 4, de donde, por el
paso base, tenemos que el resultado es cierto para n + 1.

90
 también es cierto.

Hipótesis de Inducción. Supongamos que 2n+4 < (n + 4)!.

Paso inductivo. Queremos probar que 2(n+1)+4 < ((n + 1) + 4)!. En efecto,

como n ∈ N se tiene que 2 < (n + 4) + 1. Además, por hipótesis de inducción,

2n+4 < (n + 4)!. Entonces,

2n+4 · 2 < (n + 4)! · ((n + 4) + 1) = ((n + 4) + 1)!.

Luego, 2(n+1)+4 = 2n+4 · 2 < ((n + 4) + 1)! = ((n + 1) + 4)!. Por lo que, si la

afirmación se cumple para n se cumple para n + 1.

Por lo tanto, el resultado es cierto.

En esta sección veremos principios muy importantes que cumplen los naturales.

Primer principio de inducción o Axioma 5 de Peano. Si A ⊆ N es tal que 0 ∈ A

y ∀ n ∈ N (n ∈ A ⇒ s(n) ∈ A), entonces A = N.

Definición 4.33: Sea n un natural. Denotamos con n< al conjunto de todos los

naturales menores que n, es decir, n< := {m ∈ N : m < n}.

Segundo principio de inducción o principio de inducción fuerte. Si S ⊆ N es

tal que ∀ n ∈ N (n< ⊆ S ⇒ n ∈ S), entonces S = N.

Principio del buen orden. Si B ⊆ N es tal que B ̸= ∅, entonces

∃ b0 ∈ B ∀ n ∈ N (n ∈ B ⇒ b0 ≤ n).

Es decir, cualquier subconjunto no vacı́o de N tiene un elemento mı́nimo (respecto a

≤). Usando la totalidad de ≤, lo anterior es lógicamente equivalente a

∃ b0 ∈ B ∀ n ∈ N (n < b0 ⇒ n ∈
/ B).

Lema 4.34: Se cumple lo siguiente.

91
 1. 0< = ∅.

2. Para cualquier n ∈ N, se tiene que s(n)< = n< ∪ {n}.

3. Para cualesquiera n, m ∈ N, n ≤ m si y solo si n< ⊆ m< .

4. Para cualesquiera n, m ∈ N, n < m si y solo si n< ⫋ m< .

Demostración. Ejercicio.

Teorema 4.35: El primer principio de inducción implica el segundo principio.

Demostración. Sea S ⊆ N tal que ∀ n ∈ N (n< ⊆ S ⇒ n ∈ S). Debemos probar que

S = N. Definimos el conjunto S ′ = {n ∈ S : n< ⊆ S}. Claramente S ′ ⊆ S ⊆ N.

Veamos que N ⊆ S ′ , es decir que N = S ′ . Hacemos la prueba por inducción sobre n.

1. Paso base. Veamos que el resultado es cierto para n = 0. Como 0< = ∅, tenemos

que 0< ⊆ S ya que el vacı́o es subconjunto de cualquier conjunto. Por la hipótesis

sobre S, como 0< ⊆ S, se sigue 0 ∈ S. Luego, 0 ∈ S ′ .

2. Paso inductivo. Demostremos que si para n es cierto el resultado entonces para

s(n) = n + 1 también es cierto.

(HI): Supongamos que n ∈ S ′ . Veamos que s(n) ∈ S ′ . En efecto, por el Le-

ma 4.34, sabemos que s(n)< = n< ∪ {n}. Como n ∈ S ′ tenemos que n ∈ S y

n< ⊆ S. Entonces, s(n)< = n< ∪ {n} ⊆ S. Además, por la hipótesis sobre S, se

tiene que s(n) ∈ S. Por lo que, s(n) ∈ S ′ .

Luego, por el Axioma 5 tenemos que S ′ = N y como N = S ′ ⊆ S ⊆ N se sigue que

S = N. Por lo tanto, el segundo principio de inducción se cumple.

Teorema 4.36: El segundo principio de inducción y el principio del buen orden son

equivalentes.

Demostración. Segundo principio ⇒ Principio de buen orden. Supongamos el

Segundo principio de inducción. Sea B ⊆ N con B ̸= ∅. Queremos ver que ∃ b0 ∈

B ∀ n ∈ N (n < b0 ⇒ n ∈
/ B).

92
 Consideremos S := N \ B ⊆ N. Como B ̸= ∅, tenemos que S ̸= N y por la

contrapuesta del Segundo principio de inducción3 , existe b0 ∈ N tal que b<

0 ⊆ S y

b0 ∈
/ S. Veamos que b0 es el elemento mı́nimo de B que buscamos. En efecto, como

/ S se tiene que b0 ∈ B. Por otro lado, dado que b<

b0 ∈ N y b0 ∈ 0 ⊆ S se tiene que

∀ n ∈ N (n < b0 ⇒ n ∈ S), es decir, ∀ n ∈ N (n < b0 ⇒ n ∈

/ B). Por lo tanto, se cumple

el principio del buen orden.

Principio del buen orden ⇒ Segundo principio. Supongamos el Principio

del buen orden. Sea S ⊆ N tal que ∀ n ∈ N (n< ⊆ S ⇒ n ∈ S). Queremos ver que

S = N.

Supongamos para llegar a una contradicción que S ̸= N. Sea B = N \ S. Como

S ̸= N tenemos que B ̸= ∅. Luego, por el Principio del buen orden,

∃ b0 ∈ B ∀ n ∈ N (n < b0 ⇒ n ∈
/ B).

Ahora bien, si n < b0 entonces n ∈

/ B y como B = N \ S se sigue que n ∈ S. De

aquı́, obtenemos que b<

0 ⊆ S. Por la hipótesis sobre S, tenemos entonces que b0 ∈ S lo

cual es una contradicción ya que b0 ∈ B. Por lo tanto, S = N y se cumple el Segundo

principio de inducción.

Proposición 4.37: No hay ningún n ∈ N tal que 0 < n < s(0).

Demostración. Lo demostramos usando el Principio del buen orden. Sea A = {n ∈

N : 0 < n < s(0)} ⊆ N. Supongamos que A ̸= ∅. Entonces, por el Principio del buen

orden, ∃ a0 ∈ A ∀ n ∈ N (n ∈ A ⇒ a0 ≤ n). Notemos que a0 ̸= 0 ya que 0 < a0 y por

tricotomı́a de <. Usando el Teorema 4.30, como 0 < a0 < s(0) tenemos que

0 = 0 · a0 < a0 · a0 < s(0) · a0 = 1 · a0 = a0 < s(0).

3
Contrapuesta del Segundo principio de inducción: si S ̸= N entonces existe b0 ∈ N tal
que b<
0 ⊆ S y b0 ∈
/ S.

93
Luego, a0 · a0 ∈ A y a0 · a0 < a0 lo cual contradice que a0 es el elemento mı́nimo de

A. Por lo tanto, A = ∅ y el resultado se sigue.

94
Capı́tulo 5
Combinatoria
En este capı́tulo, estudiaremos principios elementales de combinatoria.

Para esto, damos el concepto de cardinalidad para definir a los conjuntos

finitos y no finitos. También, vemos que las cardinalidades entre conjuntos

está fuertemente relacionada con la existencia de cierto tipo de funciones

entre ellos. 1 Describiremos a través de este concepto, las nociones de orde-

nación con repetición, ordenación y permutación para cualquier conjunto

finito A y daremos fórmulas para calcular el número de estas.

5.1. Cardinalidad
Definición 5.1: Sean A y B conjuntos. Decimos que A y B tienen la misma cardi-

nalidad si y solo si existe una función biyectiva f : A → B.

Definición 5.2: Para cada n ∈ N, definimos el segmento inicial con n elementos

como el conjunto In tal que:


 ∅

si n = 0
In :=
 {1, . . . , n}

si n ̸= 0.

Definición 5.3: Decimos que un conjunto A es finito si y solo si existe n ∈ N y

1
Las pruebas en estas secciones aparecen en letras grises, esto significa que puedes saltar-
telas. Lo que nos va a interesar en este capı́tulo son esos resultados, no las ideas que están
detrás de sus demostraciones. De todas formas te dejamos las demostraciones por si quieres
revisarlas.

95
existe f : In → A tal que f es biyectiva. Un conjunto infinito es uno que no es finito.

Observación 5.4: Dado un conjunto A, si existe una función biyectiva f : In → A

con n ∈ N+ , entonces podemos enlistar a los elementos de A ası́: A = {f (1), f (2), . . . , f (n)}.

Se acostumbra denotar por ai := f (i) de modo que A = {a1 , a2 , . . . , an } donde ai ̸= aj

si i ̸= j.

Lema 5.5: Se cumple lo siguiente.

1. Para cualquier n ∈ N, se tiene que Is(n) = In ∪ {s(n)}.

2. Para cualesquiera n, m ∈ N, si n < m, entonces In ⊊ Im .

3. Para cualesquiera n, m ∈ N, se tiene que

Im+n = Im ∪ {m + 1, m + 2, . . . , m + n} y

Im ∩ {m + 1, m + 2, . . . , m + n} = ∅.

Demostración. Ejercicio.

Teorema 5.6: Sean n, m ∈ N. Si m ̸= n, entonces no existe una biyección entre Im

e In .

Demostración. Sean n, m ∈ N tales que n ̸= m. Por tricotomı́a de <, tenemos dos

casos: m < n o n < m.

Supongamos que m < n. Demostremos por inducción sobre m que para todo n ∈ N,

si m < n entonces no existe una biyección g : Im → In .

1. Paso base. Veamos que el resultado es cierto para m = 0. Sea n ∈ N tal que

0 = m < n. Entonces, I0 = ∅ y In ̸= ∅ (ya que n ∈ In pues 0 < n). Por lo

tanto, no puede existir una función g : I0 → In que sea sobre. Ası́, no existe una

biyección de I0 a In .

2. Paso inductivo. Demostremos que si el resultado es cierto para m entonces tam-

bién es cierto para s(m) = m + 1.

(HI): Supongamos que para todo n ∈ N, si m < n entonces no existe una

96
 biyección de Im a In . Veamos que para todo n ∈ N, si m + 1 < n entonces no

existe una biyección de Im+1 a In .

Para llegar a una contradicción, supongamos que sı́ existe una biyección f :

Im+1 → In para algún n ∈ N con m + 1 < n. Dado que f (m + 1) ∈ In ,

supongamos sin pérdida de generalidad que f (m + 1) = n.2 Ahora bien, como

n > m + 1 tenemos que n > 0. Entonces, restringiendo el dominio de f a

Im y el codominio a In−1 obtenemos la función h : Im → In−1 definida como

h(i) = f (i). Como h es la restricción de una función inyectiva, esta función es

también inyectiva. Además, dado que f es sobre, f (m + 1) = n y el codominio

de h es In−1 = In \ {n} se sigue que h es sobre. Ası́, h : Im → In−1 es biyectiva

con m < n − 1 (ya que m + 1 < n), esto contradice HI.

Por otra parte, notemos que si existe una biyección f : In → Im entonces f −1 :

Im → In también es una biyección con m < n lo cual contradice lo anterior. Por

lo que, tampoco puede existir una función biyectiva de In a Im . El caso n < m es

análogo.

Corolario 5.7: Si A es un conjunto finito, entonces existe un único n ∈ N tal que

hay una biyección entre In y A.

Demostración. Sea A un conjunto finito. Por definición, existe n ∈ N y una función

biyectiva f : In → A. Supongamos que para alguna m ∈ N existe una biyección

g : Im → A. Tenemos que f −1 : A → In también es una función biyectiva. Por lo

tanto, f −1 ◦ g : Im → In es biyectiva. Por el Teorema 5.6 y tricotomı́a, obtenemos que

m = n.

2
En el caso en que f (m + 1) = k con k ̸= n, definimos la función g : In → In como
g(k) = n, g(n) = k y g(j) = j para k ̸= j ̸= n (es decir, g es la función que intercambia k y
n y deja fijos a los demás elementos) y trabajamos con la biyección g ◦ f en vez de trabajar
con f .

97
Definición 5.8: Decimos que un conjunto finito A tiene n elementos si y solo si

existe una biyección f : In → A. En este caso escribimos | A |= n.

Teorema 5.9: Sea n ∈ N. Todo subconjunto de In es finito y tiene a lo más n

elementos.

Demostración. Probemos el resultado por inducción sobre n.

1. Paso base. Veamos que el resultado se cumple para n = 0. En este caso I0 = ∅

y el único subconjunto del vacı́o es el vacı́o. Por lo tanto, el enunciado es cierto

para n = 0.

2. Paso inductivo. Demostremos que si el resultado es cierto para n entonces tam-

bién es cierto para s(n) = n + 1.

(HI): Supongamos que todo subconjunto de In es finito y tiene a lo más n

elementos. Queremos probar que todo subconjunto de In+1 es finito y tiene a lo

más n + 1 elementos.

Sea A ⊆ In+1 . Por una parte, si n + 1 ∈

/ A tenemos que A ⊆ In y por HI, A es

finito. Además, también por HI, si | A |= m se tiene que m ≤ n < n + 1. Luego,

| A |= m con m < n + 1. Por otra parte, si n + 1 ∈ A consideremos el conjunto

C := A \ {n + 1}. Por su definición, C ⊆ In y por HI, C es finito. Usando HI de

nuevo, si | C |= m se tiene que m ≤ n, de donde, existe una función biyectiva

g : Im → C. Extendemos g a la función G : Im+1 → A de la siguiente manera:


 n+1

si j = m + 1,
G(j) :=
 g(j) si j ̸= m + 1.


Tenemos que G es biyectiva y entonces | A |= m + 1. Dado que m ≤ n se sigue

que m + 1 ≤ n + 1 y el resultado es cierto.

Corolario 5.10: Sea B un conjunto finito con | B |= n. Todo subconjunto de B es

98
finito y tiene a lo más n elementos.

Demostración. Sea B un conjunto finito con n elementos y A ⊆ B. Sabemos que

hay una función biyectiva g : B → In . Sea h la restricción de g a A, es decir, sea

h : A → g[A] dada por h(x) = g(x) para toda a ∈ A. La función h es una biyección de

A en g[A]. Como g[A] es un subconjunto de In , por el Teorema 5.9 tenemos que g[A]

es finito. Más aún, | g[A] |= m ≤ n. Existe entonces una biyección f : Im → g[A] y

ası́, f −1 ◦ h es una biyección de A en Im , por lo que | A |= m con m ≤ n.

Lema 5.11: Sean n ∈ N y f : In → In una función. Las siguientes condiciones son

equivalentes.

1. f es inyectiva.

2. f es suprayectiva.

Demostración. (1 ⇒ 2). Probemos que si f es inyectiva entonces f es sobre. Hacemos

la prueba por inducción sobre n.

1. Paso base. Veamos que el resultado es cierto para n = 0. Como I0 = ∅, la única

función de f : I0 → I0 es la función vacı́a que es inyectiva y sobre. Por lo tanto,

en este caso el resultado se cumple.

2. Paso inductivo. Demostremos que si el resultado es cierto para n, entonces tam-

bién es cierto para s(n) = n + 1.

(HI): Supongamos que si f : In → In es inyectiva entonces f es sobre. Sea

f : In+1 → In+1 una función inyectiva. Queremos demostrar que f es sobre. En

efecto, supongamos sin pérdida de generalidad que f (n + 1) = n + 1.3 Restrin-

giendo el dominio de f a In y también su codominio a In , obtenemos la función

h : In → In definida por h(i) = f (i) (como f (n + 1) = n + 1 efectivamente el

codominio de h es In ). Dado que f es inyectiva se sigue que h también lo es y

3
Ver la nota de pie de página de la prueba del Teorema 5.6.

99
 por HI, h es sobre. Usando que h es sobre obtenemos que f es sobre. Por lo

tanto, el resultado es cierto para n + 1 y la implicación 1 ⇒ 2 se cumple.

La implicación 2 ⇒ 1 se deja como ejercicio.

Corolario 5.12: Si A es un conjunto finito, entonces una función de A en A es

suprayectiva si y solo si es inyectiva.

Demostración. Sea A un conjunto finito. Entonces, existe un único n ∈ N tal que

hay una función biyectiva g : In → A. Supongamos que f es sobre (resp., inyectiva).

Luego, h := g −1 ◦ f ◦ g : In → In es sobre (resp., inyectiva) ya que es composición de

suprayectivas (resp., inyectivas). Por el Lema 5.11 se tiene que h es inyectiva (resp.,

sobre) y por tanto biyectiva. En consecuencia, f = g◦h◦g −1 es biyectiva y en particular

inyectiva (resp., sobre).

Proposición 5.13: Existe una función suprayectiva de Im en In si y solo si m ≥ n.

Demostración. Ejercicio.

5.2. Principios elementales de combi-

natoria
Teorema 5.14(Principio de la suma): Si A y B son conjuntos finitos tales que

A ∩ B = ∅, entonces | A ∪ B |=| A | + | B |.

Demostración. Sean A y B conjuntos finitos. Entonces, existen m y n y funciones

biyectivas f y g tales que f : Im → A y g : In → B. Ası́, | A |= m y | B |= n.

Veamos que existe una función biyectiva h : Im+n → A ∪ B. Como Im+n = Im ∪ {m +

100
1, . . . , m + n} e Im ∩ {m + 1, . . . , m + n} = ∅. Definimos h : Im+n → A ∪ B como


 f (j) si j ≤ m,

h(j) =
 g(j − m)

si j > m.

La función h está bien definida, pues para toda j ∈ Im+n , tenemos que j ∈ Im o bien

{m+1, . . . , m+n} y se dá solo uno de estos casos, es decir, j ≤ m o bien m < j ≤ m+n.

Además, si m < j ≤ m + n entonces 0 < j − m ≤ n por lo que j − m ∈ In y g(j − m)

está bien definido. Usando que f y g son biyectivas y que A ∩ B = ∅ obtenemos que

h es biyectiva. Por lo tanto, | A ∪ B |= m + n =| A | + | B |.

Corolario 5.15(Principio general de la suma): Sea k ∈ N tal que k ≥ 2.

Supongamos que A1 , A2 , . . . , Ak son conjuntos finitos ajenos por pares, es decir, tales

que si i ̸= j entonces Ai ∩ Aj = ∅. Entonces,

| A1 ∪ A2 ∪ · · · ∪ Ak |=| A1 | + | A2 | + · · · + | Ak | .

Demostración. Por inducción sobre k.

1. Paso base. Veamos que el resultado se cumple para k = 2. En efecto, si k = 2

tenemos que A1 y A2 son ajenos y por el Teorema 5.14 se sigue que | A1 ∪ A2 |=|

A1 | + | A2 |.

2. Paso inductivo. Demostremos que si el resultado es cierto para k entonces tam-

bién es cierto para s(k) = k + 1.

(HI): Supongamos que el resultado se cumple para k. Sean A1 , . . . , Ak+1 conjun-

tos finitos tales que si i ̸= j entonces Ai ∩ Aj = ∅. Notemos que (A1 ∪ · · · ∪ Ak )

y Ak+1 son ajenos ya que A1 , . . . , Ak+1 son ajenos por pares. Entonces,

| A1 ∪ · · · ∪ Ak ∪ Ak+1 |= | (A1 ∪ · · · ∪ Ak ) ∪ Ak+1 |

= | A1 ∪ · · · ∪ Ak | + | Ak+1 | (Teorema 5.14)

= | A1 | + · · · + | Ak | + | Ak+1 | (HI ).

101
Por lo tanto, el corolario es cierto para cualquier k ≥ 2.

Corolario 5.16: Sean A y B conjuntos finitos.

1. Si f : A → B es una función inyectiva, entonces | A |≤| B | .

2. Si f : A → B es suprayectiva, entonces | A |≥| B | .

Demostración. Ejercicio.

Proposición 5.17: Si A y B son dos conjuntos finitos entonces

| A ∪ B |=| A | + | B | − | A ∩ B | .

Demostración. Ejercicio.

Teorema 5.18(Principio del producto): Si A y B son conjuntos finitos, entonces

| A × B |=| A | · | B | .

Demostración. Lo demostraremos por casos dependiendo la cardinalidad de A.

Si | A |= 0 entonces A = ∅. Por la Proposición 2.54 tenemos que A × B = ∅. Por

lo tanto, | A × B |= 0 = 0· | B |=| A | · | B | y el resultado se cumple.

Supongamos que | A |= m con m > 0. Entonces, A = {a1 , a2 , . . . , am }.4 Dado

ai ∈ A, definimos la función fi : {ai } × B → B como fi (ai , b) = b. Es claro que fi es

una biyección. Por lo tanto, | {ai } × B |=| B |. Además, como {{ai } × B}i∈Im es una

partición de A × B se sigue que

[
A×B = {ai } × B
i∈Im

4
Usando que hay una biyección g de Im en A y haciendo g(i) = ai para cada i ∈ Im
podemos suponer que A es de esta forma.

102
donde los conjuntos {ai } × B son ajenos por pares. Luego,

Pn
| A × B |= i=1 | {ai } × B | (Teorema 5.15)
Pn
= i=1 |B|

= m· | B |

= |A|·|B|.

Corolario 5.19(Principio general del producto): Sea k ∈ N con k ≥ 2. Si

A1 , A2 , . . . , Ak son conjuntos finitos entonces

| A1 × A2 × · · · × Ak |=| A1 | · | A2 | · . . . · | Ak | .

Demostración. Lo hacemos por inducción sobre k.

1. Paso base. Si k = 2 se tiene que | A1 × A2 |=| A1 | · | A2 | por el Teorema 5.18.

2. Paso inductivo. Demostremos que si el resultado es cierto para k entonces tam-

bién es cierto para s(k) = k + 1.

(HI): Supongamos que el resultado es cierto para k. Sean A1 , A2 , . . . , Ak y Ak+1

conjuntos finitos. Entonces,

| A1 × · · · × Ak × Ak+1 |= | (A1 × · · · × Ak ) × Ak+1 |

= | A1 × · · · × Ak | · | Ak+1 | (Teorema 5.18)

= | A1 | · · · | Ak | · | Ak+1 | (HI ).

Por lo tanto, el resultado es cierto para cualquier k ≥ 2.

Definición 5.20: Dados A y B conjuntos, denotamos con A B al conjunto de todas

las funciones de A en B, es decir, A B = {f | f : A → B}.

103
Teorema 5.21(Principio de exponenciación): Sean A y B conjuntos finitos.

Entonces, el número de funciones de A en B es | B ||A| , es decir, | A B |=| B ||A| .

Demostración. Sea A un conjunto finito con | A |= m.

Si m = 0 entonces A = ∅ y la única función de A en B es la vacı́a. Por lo

que, | {f | f : A → B} |= 1 =| B |0 =| B ||A| . Si m > 0 entonces sea A =

{a1 , . . . , an }.5 Ahora bien, una función f : A → B queda determinada por sus valores

f (a1 ), f (a2 ), . . . , f (am ) en B. Considerando el orden natural en Im , podemos pensar

en estos valores como una m-ada ordenada (f (a1 ), f (a2 ), . . . , f (am )) de elementos de

B, es decir, como un elemento de B m = B × · · · × B . Definimos F : A B → B m como

| {z }
m veces
F (f ) = (f (a1 ), . . . , f (am )) para cada f ∈ A B. Queremos ver que F es biyectiva.

1. F es sobre. Sea (b1 , . . . , bm ) ∈ B m . Considera f : A → B dada por f (ai ) = bi

para cada i ∈ Im . Entonces, F (f ) = (f (a1 ), . . . , f (am )) = (b1 , . . . , bm ). Por lo

tanto, F es sobre.

2. F es inyectiva. Sean f y g ∈ A B tales que F (f ) = F (g). Entonces,

(f (a1 ), . . . , f (am )) = (g(a1 ), . . . , g(am )).

Luego, por definición de m-adas, f (ai ) = g(ai ) para todo i ∈ Im de donde se

sigue que F es inyectiva.

Por lo tanto, F es una biyección y | A B |=| B ||A| .

5.3. Ordenaciones y permutaciones

Definición 5.22: Sean n, m ∈ N y A un conjunto con n elementos. Las ordenaciones

con repetición de los elementos de A tomados de m en m son las funciones f : Im → A.

5
Ver la nota de pie de página de la prueba del Teorema 5.18.

104
Denotamos con ORnm al número de ordenaciones con repetición de un conjunto A con

n elementos tomados de m en m, esto es, ORnm =| Im A |.

Ejemplo 5.23: Sean M = {•, −}. Entonces, las ordenaciones con repetición de los

elementos de M tomados de 3 en 3 son:

       
 1 2 3   1 2 3   1 2 3   1 2 3 
 , , , ,
• • • • • − • − • • − −

       
 1 2 3   1 2 3   1 2 3   1 2 3 
 , , , .
− • • − • − − − • − − −

Teorema 5.24: Para cualesquiera n y m ∈ N, se tiene que ORnm = nm .

Demostración. Sea A un conjunto con | A |= n. Por definición, ORnm =| Im A |. Luego,

Im
por el Principio de exponenciación (ver Teorema 5.21), se tiene que | A |=| A |m =

nm .

Definición 5.25: Sean n, m ∈ N y A un conjunto con n elementos. Las ordenaciones

de los elementos de A tomados de m en m son las funciones f : Im → A tales que f

es inyectiva. Denotamos con Onm al número de ordenaciones de un conjunto A con n

elementos tomados de m en m.

Observación 5.26: De ahora en adelante, supondremos que A ̸= ∅, ya que si A = ∅

y m ≥ 1, no hay funciones de f : Im → A. Además, si A tiene n elementos, para que

existan funciones inyectivas de f : Im → A se necesita que m ≤ n.

Ejemplo 5.27: Sea A = {a, b, c, d, e}. Las funciones inyectivas de I1 en A son:

         
 1   1   1   1   1 
 , , , , .
a b c d e

105
  
 1 
Entonces, O51 = 5. Consideremos f =  . ¿Cuántas funciones inyectivas hay de I2
a
 
1 2
en A que extienden a f ?. Esta extensión es de la forma   con x ∈ {b, c, d, e}
 
a x
para que siga siendo inyectiva. Por lo que, hay 5 − 1 = 4 funciones inyectivas de I2 en

A que extienden a f . Ası́, hay 5(4) = 20 funciones inyectivas de I2 en A.

Lema 5.28: Sean n, m ∈ N+ tales que m + 1 ≤ n. Entonces, Onm+1 = (n − m)Onm .

Demostración. Sea A un conjunto con n elementos. Consideremos una función inyec-

tiva F : Im+1 → A

 
1 2 ··· m m+1
F = .
 
F (1) F (2) ··· F (m) F (m + 1)

Observemos que  
 1 2 ··· m 
 
F (1) F (2) ··· F (m)

es una función inyectiva de Im en A y F (m + 1) ∈ A \ {F (1), F (2), . . . , F (m)} ya que

F es inyectiva. A la inversa, si

 
1 2 ··· m
f =
 

f (1) f (2) · · · f (m)

es una función inyectiva de Im en A y b ∈ A \ {f (1), f (2), . . . , f (m)} se tiene que

 
 1 2 ··· m m+1 
 
f (1) f (2) ··· f (m) b

es una función inyectiva de Im+1 en A.

Sean f1 , f2 , . . . , fk las funciones inyectivas de Im en A, donde k = Onm . Definamos,

106
para cada i ∈ Ik , el conjunto
  
 1 2 ··· m m+1 

 

Bi =   : b ∈ A \ {fi (1), fi (2), . . . , fi (m)} .
 fi (1) fi (2) ··· fi (m) b
 


Entonces, el conjunto de funciones inyectivas de Im+1 en A, que denotaremos por B,

se puede escribir como B = B1 ∪ B2 ∪ · · · ∪ Bk . Dado que los conjuntos B1 , B2 , . . . , Bk

son conjuntos finitos ajenos por pares, por el Corolario 5.15, tenemos que | B |=|

B1 | + | B2 | + · · · + | Bk |. Además, para cada i ∈ Ik se tiene que | Bi |=|

A \ {fi (1), . . . , fi (m)} |= n − m. Concluimos que Onm+1 = (n − m)k = (n − m)Onm .

Teorema 5.29: Si m, n ∈ N+ y m ≤ n, entonces

n!
Onm = n(n − 1) · · · (n − m + 1) = .
(n − m)!

Demostración. Por inducción sobre m.

1. Paso base. Si m = 1 entonces n ≥ 1. Dado que hay n funciones inyectivas

distintas de I1 en un conjunto A con n elementos, On1 = n. Por otro lado, como

m = 1, tenemos que n(n − 1) · · · (n − m + 1) = n. Por lo tanto, el resultado es

cierto para m = 1.

2. Paso inductivo. Demostremos que si el resultado es cierto para m = 1 entonces

también es cierto para s(m) = m + 1.

(HI): Supongamos que Onm = n(n − 1) · · · (n − m + 1). Entonces,

Onm+1 = Onm (n − m) (Lema 5.28)

= n(n − 1) · · · (n − m + 1)(n − m) (HI )

= n(n − 1) · · · (n − m + 1)(n − (m + 1) + 1).

Por lo tanto, el resultado es cierto para cualesquiera n, m ∈ N+ con m ≤ n.

Definición 5.30: A las ordenaciones de un conjunto con n elementos tomados de

107
n en n se les llama permutaciones de n elementos. Denotamos con Pn al número de

permutaciones de n elementos.

Corolario 5.31: Si n ∈ N entonces Pn = n!.

Demostración. Notemos que el resultado se cumple para n = 0. Ahora bien, si n ∈ N+

entonces, por el Teorema 5.29, tenemos que

Pn = Onn = n(n − 1) · · · (n − n + 1) = n(n − 1) · · · (2)(1) = n!.

La definición anterior es equivalente a la siguiente.

Definición 5.32(Definición alternativa): Sea A un conjunto finito. Las permu-

taciones del conjunto A son las funciones biyectivas de A en A.

Ejemplo 5.33: Se quieren colocar 11 libros en un estante, 4 son novelas, 3 son

ensayos, 3 son de poemas y 1 es de cuentos. ¿De cuántas maneras puede hacerse si se

quiere que los libros del mismo tipo queden juntos?.

Por el Principio general del producto, hay P4 P3 P3 P1 arreglos de manera que queden

juntos cada tipo de libro, donde las novelas quedan primero, los ensayos segundo,

los de poemas tercero y por último el de cuentos. Similarmente, para cada posible

arreglo de los tipos de libros hay P4 P3 P3 P1 arreglos. Entonces, como hay P4 posibles

ordenes de como acomodar los tipos de libros, por el Principio del producto hay

(P4 )P4 P3 P3 P1 = 4! · 4! · 3! · 3! · 1! = 20736 maneras de acomodar los libros de manera

que los libros de un mismo tipo queden juntos.

108
5.4. Combinaciones y expansión bino-

mial
Teorema 5.34: Si A es un conjunto finito, entonces el número de subconjuntos de

A es 2|A| , es decir, | P(A) |= 2|A| .

A
Demostración. Veamos que existe una biyección de P(A) en {0, 1}. Para cada sub-

conjunto M de A definimos la función caracterı́stica XM : A → {0, 1} como:


 0 si x ∈
/ M,

XM (x) =
 1 si x ∈ M.


Sea F : P(A) → A {0, 1} definida por F (M ) = XM . Veamos que F es biyectiva.

1. F es inyectiva. Sean M y N subconjuntos de A tales que F (M ) = F (N ). Mos-

tremos que M = N . En efecto, sea m ∈ M . Entonces,

1 = XM (m) = F (M )(m) = F (N )(m) = XN (m).

Luego, por la definición de función caracterı́stica, m ∈ N . Ası́, M ⊆ N . Análo-

gamente, N ⊆ M . Por lo tanto, M = N y F es inyectiva.

2. F es sobre. Sea f ∈ A {0, 1}. Tomamos Mf = {x ∈ A : f (x) = 1} ⊆ A. Queremos

ver que F (Mf ) = f . Sea x ∈ A. Entonces,

a) Si x ∈ Mf , por la definición de Mf , f (x) = 1. Por otro lado, XMf (x) = 1.

b) Si x ∈
/ Mf , por la definición de Mf (x), f (x) ̸= 1 y como el codominio de f

es {0, 1} se sigue que f (x) = 0. Por otro lado, XMf (x) = 0.

En ambos casos se obtiene que XMf (x) = f (x). Luego, F (Mf ) = f de donde F

es sobre.

A
Por lo tanto, | P(A) |=| {0, 1} |. Por el Principio de exponenciación tenemos que

109
| A {0, 1} |=| {0, 1} ||A| = 2|A| y el resultado se sigue.

Definición 5.35: Sean m, n ∈ N tales que m ≤ n. Sea A un conjunto con n elemen-

tos. Los subconjuntos de A que constan de m elementos son llamados

 las
 combinacio-
 n 
nes de los elementos de A tomados de m en m. Denotamos por   o por Cnm al
m
número de combinaciones de un conjunto con n elementos tomados de m en m.

Ejemplo 5.36: Sea I3 = {1, 2, 3}.

1. C30 = 1, solo es el vacı́o.

2. C31 = 3, las cuales son: {1}, {2}, {3}.

3. C32 = 3, las cuales son: {1, 2}, {1, 3}, {2, 3}.

4. C33 = 1, solo es {1, 2, 3}.

Teorema 5.37: Sean n, m ∈ N tales que m ≤ n. Entonces,

 
 n  m
  Pm = On .
m

Demostración. Sea A un conjunto con n elementos. Sea O el conjunto de todas las or-

denaciones del conjunto A tomadas de m en m y C el conjunto de todas las combinacio-

 
 n 
nes de los elementos de A tomados de m en m. Entonces, | O |= Onm y | C |=  .
m
Definimos una función F : O → C como
 
 1 2 ··· m 
F  = {a1 , a2 , . . . , am }.
a1 a2 ··· am

Veamos que F es sobre. Sea C ∈ C. Entonces, C es un subconjunto de A con m

110
elementos digamos C = {b1 , b2 , . . . , bm }, donde bi ̸= bj si i ̸= j. Sea

 
 1 2 ··· m 
f = .
b1 b2 ··· bm

Entonces, f es una ordenación de los elementos de A tomados de m en m, es decir,

f ∈ O. Además,

 
 1 2 ··· m 
F  = {b1 , b2 , . . . , bm } = C.
b1 b2 ··· bm

Por lo tanto, F es sobre.

Ahora bien, sean

 C1, C2 , . . . , Ck los distintos subconjuntos de A con m elementos,

 n 
donde k =| C |=  . Definamos para cada i ∈ Ik , el conjunto
m

   
 1 2 ··· m 

 

Oi = f =  : F (f ) = Ci .
a1 a2 ··· am

 


Luego, O se puede escribir como O = O1 ∪· · ·∪Ok . Dado que los conjuntos O1 , . . . , Ok

son ajenos por pares, por el Principio general de la suma, tenemos que | O |=| O1 ∪

· · · ∪ Ok |=| O1 | + · · · + | Ok | .

Además, si m > 1, F no es inyectiva, ya que cualquier permutación del conjunto

{b1 , b2 , . . . , bm } va a dar a {b1 , b2 , . . . , bm } bajo F . En otras palabras, para cada i ∈ Ik ,

hay Pm ordenaciones de A tomadas de m en m que van a dar a Ci bajo F . Por lo

i ∈ Ik , se tiene que | Oi |= Pm . Ası́, concluimos que Onm =| O |=

tanto, paracada 

 n 
Pm k = Pm  .
m

El siguiente tal vez sea el resultado más importantes de este capı́tulo.

111
Corolario 5.38: Sean m, n ∈ N tales que m ≤ n. Entonces,

 
 n  n(n − 1) · · · (n − m + 1)
= .
m!

m

Demostración. Por los Teoremas 5.29 y 5.37 se tiene que

 
 n  Onm n(n − 1) · · · (n − m + 1)
= =
P m!

m m

Observación 5.39: Si A tiene n elementos entonces

 
   
n n n
| P(A) |= 2n =  +  + ··· .
     
0 1 n

Lema 5.40: Sean m, n ∈ N con m ≤ n. Entonces,

   
 n   n
= .


m n−m

Demostración. Sea A un conjunto con n elementos. Sea S el conjunto de todas las

combinaciones de elementos de A tomados de m en m. Sea T el conjunto de todas las

combinaciones de elementos de A tomados de n − m en n − m. Definimos la función

f : S → T como f (s) = A \ s. Si s ∈ S entonces s tiene m elementos, por lo que A \ s

tiene n − m elementos. Luego, A \ s ∈ T . Más aún, la función g : T → S dada por

g(t) = A \ t para cada t ∈ T , es la inversa de f . Por lo tanto, f es biyectiva y ası́,

   
n n
 =| S |=| T |=  .
   

m n−m

112
 El siguiente arreglo es conocido como el Triángulo de Pascal

C00 = 1

C10 = 1 C11 = 1

C20 = 1 C21 = 2 C22 = 1

C30 = 1 C31 = 3 C32 = 3 C33 = 1

.. .. ..
. . .

Teorema 5.41(Fórmula de recurrencia del triángulo de Pascal): Sean n, k ∈

N+ con n ≥ 2 y k ≤ n − 1. Entonces,

     
 n   n−1   n−1 
 = + .
k k−1 k

Demostración. Sean n ≥ 2 y k ≤ n − 1. Tomemos el conjunto In = {1, 2, . . . , n},

pues tiene n elementos. Sea C el conjunto de combinaciones de In tomadas de k

en k, es decir, C es el conjunto de subconjuntos de In con k elementos. Sean C1 y

C ′ los siguientes subconjuntos de C: C1 es el conjunto de subconjuntos de In con k

elementos que tienen al 1 como elemento y C ′ es el conjunto de subconjuntos de In con

k elementos que no tienen al 1 como elemento. Entonces, C = C1 ∪ C ′ y C1 ∩ C ′ = ∅.

Por el Principio de la suma, | C |=| C1 | + | C ′ |.

Ahora bien, para formar un subconjunto de In con k elementos que tenga  al 1, ne-

 n−1 
cesitamos elegir k −1 elementos de los n−1 restantes de In . Entonces, hay  
k−1
 
 n−1 
subconjuntos de In con k elementos que tienen al 1 y | C1 |=  . Por otro
k−1
lado, los subconjuntos de In con k elementos que no tienen al 1, se obtienen eli-

giendo k elementos del conjunto In \ {1}. Sabemos que | In \ {1} |= n − 1, por

113
  
 n−1 
lo que hay   subconjuntos de In con k elementos que no tienen al 1 y
k
 
n − 1
| C ′ |=  . Por lo tanto,
 
k

     
n ′
n − 1 n − 1
 =| C |=| C1 | + | C |=  + .
     

m k−1 k−1

El siguiente, probablemente, sea el segundo resultado más importante del capı́tulo.

Teorema 5.42(Teorema del binomio): Sean n ∈ N+ y a, b ∈ R. Entonces,

 
n
X  n  n−k k
(a + b)n =  a b .
k=0 k

Demostración. Por inducción sobre n.

1. Paso base. Si n = 1 entonces (a + b)1 = a + b. Por lo tanto,

     
1
X  1  1−k k  1  1 0  1  1−1 1
 a b =   a b +   a b = a + b.
k=0 k 0 1

2. Paso inductivo. Demostremos que si el resultado es válido para n entonces tam-

bién es válido para s(n) = n + 1.

(HI): Supongamos que

 
n
X n
(a + b)n =
 n−k k
a b .


k=0 k

114
 Entonces, por HI y el Teorema 5.41, tenemos

(a + b)n+1 = (a + b)n (a + b)

= (a + b)n a + (a + b)n b
       
P n
 n  n−k k  P n
 n  n−k k 
=   a b a +   a b b
k=0 k k=0 k
   
n
P n  n+1−k k P  n n  n−k k+1
=  a b +  a b
k=0 k k=0 k

       
n n
 n+1 P  n n  n+1−k k  n  n+1
=  a + +  a b + b
  

0 k=1 k k−1 n
     
 n  n+1 P n
 n + 1  n+1−k k  n  n+1
=  a +  a b + b
0 k=1 k n

Como
       
 n   n+1   n   n+1 
 =1=  y  =1= 
0 0 n n+1

concluimos que

     
n
 n + 1  n+1 X  n + 1  n+1−k k  n + 1  n+1
(a + b)n+1 = a +  a b + b .
0 k=1 k n+1

Por lo tanto, el Teorema se cumple.

115
Índice alfabético

Axioma diferencia, 31

de Extensionalidad, 22 diferencia simétrica, 38

de separación, 22 dominio

del vacı́o, 22, 41 relación, 47

Axiomas de Peano, 75
elemento

cardinalidad, 95 imagen de, 59

clase de equivalencia, 50
factorial, 89
representante, 50
función, 59
combinaciones, 110
biyectiva, 61
conclusión, 12
caracterı́stica., 109
conjunto, 22
codominio, 59
cociente, 51 dominio, 59
complemento, 35 gráfica de, 60
finito, 95 identidad, 70
infinito, 96 imagen, 59
potencia, 41 imagen directa, 62
conjuntos ajenos, 27 imagen inversa, 64
contención, 23 inversa, 70
propia, 25 inyectiva, 61
contradicción, 11 preimagen, 64
cuantificador regla de correspondencia, 60
existencial, 14 sucesor, 76

universal, 14 suprayectiva, 61

117
funciones producto cartesiano, 44

composición, 69 proposición, 3
iguales, 69
razonamiento deductivo, 12
imagen válido, 12
relación, 47 relación
Inducción binaria, 47
primer principio, 91
equivalencia, 50
segundo principio, 91
inversa, 48
intersección, 29
orden, 56

números naturales, 76 orden total, 58

multiplicación, 78 reflexiva, 50, 56, 59

suma, 78 simétrica, 50, 56, 59

naturales total, 48
positivos, 86 transitiva, 50, 56, 59

vacı́a, 48
ordenaciones, 105
relación de equivalencia
con repetición, 104
partición inducida, 52
partición, 51

relación inducida, 53 segmento con n elementos, 95

permutaciones, 108 subconjunto, 23

plano cartesiano, 44 sucesor, 76

predicado, 14
tautologı́a, 10
premisas, 12

Principio del buen orden, 91 unión, 30

118