Body i Margin Notes - medellin.unal.edu.coearamosn/cursos/...naturales en términos de conjuntos linealmente ordenados, discretos y sin máximo. Además dio deﬁniciones recursivas

Header

Body

Footer

MarginNotes

i8� -

i7

?

6

i1� -

�-i3 i10� -

�-i9

6

?

i11

i2?

6

6?

i46?

i56

?

i6

1 one inch + \hoffset 2 one inch + \voffset3 \oddsidemargin = 13pt 4 \topmargin = 3pt5 \headheight = 9pt 6 \headsep = 15pt7 \textheight = 600pt 8 \textwidth = 370pt9 \marginparsep = 7pt 10 \marginparwidth = 125pt11 \footskip = 16pt \marginparpush = 5pt (not shown)

\hoffset = 0pt \voffset = 0pt\paperwidth = 614pt \paperheight = 794pt

Header

Body

Footer

MarginNotes

i8� -

i7

?

6

i1� -

�-i3i10� -

�-i9

6

?

i11

i2?

6

6?

i46?

i56

?

i6

1 one inch + \hoffset 2 one inch + \voffset3 \evensidemargin = 13pt 4 \topmargin = 3pt5 \headheight = 9pt 6 \headsep = 15pt7 \textheight = 600pt 8 \textwidth = 370pt9 \marginparsep = 7pt 10 \marginparwidth = 125pt11 \footskip = 16pt \marginparpush = 5pt (not shown)

\hoffset = 0pt \voffset = 0pt\paperwidth = 614pt \paperheight = 794pt

Números, Conjuntos y Combinatoria

Johany Suárez RamírezProfesor Auxiliar

Universidad Nacional de Colombia

logo

2010

Contenido

Prefacio v

1 Números Naturales 11.1 Axiomas de Peano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Aritmética y Orden en N . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Inducción Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Números Enteros 232.1 División en Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.2 Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.3 Números Primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.4 Teorema Fundamental de la Aritmética . . . . . . . . . . . . . . . . . . 36

3 Congruencias 453.1 Aritmética Modular . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.2 Teorema Chino del Residuo . . . . . . . . . . . . . . . . . . . . . . . . . 513.3 Tres Grandes Teoremas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

4 Números Cardinales 714.1 Cardinalidad de Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . 714.2 Conjuntos Finitos y Contables . . . . . . . . . . . . . . . . . . . . . . . . 824.3 Cardinales con el Axioma de Elección . . . . . . . . . . . . . . . . . . . 894.4 Aritmética Cardinal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

5 Combinatoria Básica 103

6 Teoría de Grafos 105

A Construcción de los Números Reales 107

B Pruebas alternativas del Teorema de Schröder-Bernstein 125

Referencias 129

Indice 131

iv Contenido

Prefacio

El propósito principal de este libro es servir como texto guía para el curso Conjuntos yCombinatoria de la carrera de Matemáticas en la sede Medellín de la Universidad Na-cional de Colombia. Se presume que el lector posee un conocimiento básico del cál-culo de predicados y la teoría de conjuntos al nivel proporcionado por los primeroscapítulos de [Bl03] (tal como se desarrolla en el curso Fundamentos de Matemáticas).

Johany SuárezEscuela de Matemáticas

Medellín

vi Contenido

1

Números Naturales

1.1 Axiomas de Peano

A partir de la segunda mitad del siglo XIX, se dan los primeros intentos por explo-rar los fundamentos lógicos del concepto de número. En 1861, Hermann Grassmannmostró que muchas propiedades de los números naturales se podían derivar a partirde la operación sucesor y el principio de inducción. En su artículo On the Logic of Num-ber (Sobre la Lógica del Número, 1881), Charles Sanders Peirce analizó los númerosnaturales en términos de conjuntos linealmente ordenados, discretos y sin máximo.Además dio definiciones recursivas informales de la suma y el producto, probandoque ambas operaciones eran asociativas y conmutativas.

En 1888, Richard Dedekind publicó su célebre ensayo Was sind und was sollen dieZahlen? (¿Qué son y para qué sirven los números?), donde definió los números naturalesusando ideas de la teoría de conjuntos. Además Dedekind introdujo su definición deconjunto infinito y estableció la válidez de las definiciones por recursión primitiva.Inspirado en el trabajo de Dedekind, Giuseppe Peano propuso un conjunto equiva-lente de axiomas, pero más sencillo, en su libro Arithmetices principia, nova methodoexposita (Los Principios de la Aritmética expuestos por un nuevo método, 1889).

En 1964, William Lawvere tradujo los axiomas de Peano al lenguaje de las cate-gorías obteniendo otra axiomatización para los números naturales. Para un estudiode la equivalencia de estas axiomatizaciones, el lector puede consultar [Be03].

Ahora, enunciemos la axiomatización de Peano-Dedekind.

Axiomas de Peano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

X es un conjunto con un elemento especial 0X 2 X y una función S : X ! X que cumplen:

1. Para todo x 2 X, 0X 6= S (x) .

2. Para todo x, y 2 X, si S (x) = S (y) , entonces x = y.

3. Sea A un subconjunto de X que satisface las siguientes propiedades:

0 2 A y (8n) (n 2 A ! (n+ 1) 2 A) .

Entonces A = X.

.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

La tripleta ordenada hX, 0X , Si se suele llamar conjunto de Henkin. Cuando unconjunto de Henkin satisface los anteriores axiomas, se dice que es un sistema dePeano.

2 1. Números Naturales

Tomemos X como el conjunto de números naturales

N = f0, 1, 2, 3, . . .g

e interpretemos 0X por el número cero 0 y la función S por la función sucesor σ :N!N dada por

σ (n) = n+ 1, 8n 2N.

Suponemos que N sastiface los axiomas de Peano.

Los postulados de Peano se pueden reenunciar del siguiente modo:

P1. 0 es un número natural.

P2. Si n es un número natural, entonces n+ 1 también lo es.

P3. 0 no es sucesor de ningún número natural.

P4. Números naturales distintos tiene sucesores distintos.

P5. Principio de Inducción Matemática (versión 1)

Sea A un subconjunto de números naturales. Supongamos que

0 2 A y (8n) (n 2 A ! (n+ 1) 2 A) .

Entonces A = N.

A primera vista, podría parecer que los axiomas de Peano no son lo suficiente-mente fuertes. Por ejemplo, no hay ninguna referencia a las operaciones aritméticas,ni al orden de N. Tampoco parece claro que, a partir de ellos, se puedan demostrarresultados básicos como el teorema fundamental de la aritmética o la infinitud de losprimos. Sin embargo, es posible construir las operaciones de suma y de producto, demodo que se pueda desarrollar la teoría completa de N. Para ello, una herramientaclave será la definición de funciones por recursión.

Teorema de Recursión (versión 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sea A un conjunto arbitrario. Dados a 2 A y h : A ! A, existe una única funciónf : N! A que satisface

f (0) = a y f (n+ 1) = h ( f (n)) , para todo n 2N.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

La segunda ecuación significa que el diagrama

Nσ��! N

f??y ??y f

A ��!h

A

conmuta.

1.2. Aritmética y Orden en N 3

Teorema de Recursión (versión 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sean g : A! A y h : A�N� A! A funciones. Existe una única función f : A�N!A que satisface

f (a, 0) = g (a) y f (a, n+ 1) = h(a, n, f (a, n)), para todo n 2N y a 2 A.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Para una prueba de cualquiera de las dos versiones del teorema de recursión, sepuede consultar [Hr99] o [En77].

Lema 1.1 Sea n 2N. Si n 6= 0, existe m 2N tal que n = m+ 1.

Prueba. Sea

A = fn 2N j (n = 0) _ (9m 2N) (n = m+ 1)g .

Es claro que 0 2 A y que n+ 1 2 A, para todo n. Luego, se cumple que

(8n) (n 2 A ! (n+ 1) 2 A) .

Por el principio de inducción, A = N, lo cual concluye la prueba. �Una aplicación de la versión 1 del teorema de recursión permite establecer la uni-

cidad de los números naturales (salvo isomorfismos).

Teorema de Unicidad (Dedekind) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Dado un sistema de Peano X, existe una función biyectiva f : N! X que satisface

f (0) = 0X y f (n+ 1) = S ( f (n)) , para todo n 2N.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2 Aritmética y Orden en N

Tomemos A = N y las funciones g, h dadas por

g (m) = m y h (m, n, k) = k+ 1, para todo m, n, k 2N.

Aplicando la versión 2 del teorema de recursión, existe una única función A : N2 !N que satisface

A (m, 0) = m y A (m, n+ 1) = A (m, n) + 1, para todo n 2N.

Definamos m+ n = A (m, n) . De este modo, obtenemos las ecuaciones recursivas dela suma:

S1. m+ 0 = m S2. m+ (n+ 1) = (m+ n) + 1

Aplicando inducción matemática, se puede probar que las propiedades básicas dela suma.


Asociatividad. (m+ n) + p = m+ (n+ p) .

0 es un neutro. n+ 0 = n = 0+ n.

Conmutatividad. m+ n = n+m.

Ley cancelativa. Si m+ p = n+ p, entonces m = n.

A partir de la suma, se define recursivamente el producto: tomemos A = N y g, hdadas por

g (m) = 0 y h (m, n, k) = k+m, para todo m, n, k 2N.

Luego, existe una única función M : N2 !N que satisface

M (m, 0) = 0 y M (m, n+ 1) = M (m, n) +m, para todo n 2N.

Si hacemos m � n = M (m, n) , entonces obtenemos las ecuaciones recursivas del pro-ducto:

M1. m � 0 = 0 M2. m � (n+ 1) = (m � n) +m

Aplicando inducción matemática se muestra el producto satisface las propiedadesusuales.

Asociatividad. (m � n) � p = m � (n � p) .

1 es un neutro. n � 1 = n = 1 � n.

Conmutatividad. m � n = n �m.

Distributividad m � (n+ p) = m � n+m � p.

(m+ n) � p = m � p+ n � p.

Ley cancelativa. Si m � p = n � p, entonces m = n.

Ahora, introduzcamos el orden en N. Dados m, n 2N, definimos

n � m sii 9p 2N (m = n+ p) y n < m sii n � m ^ n 6= m.

Usando el lema 1.1, es fácil ver que

n < m sii 9p 2N (m = n+ (p+ 1)) sii n+ 1 � m.

Se puede probar que � es una relación de orden parcial en N. Esto es, se cumple que

� es reflexiva: n � n.

� es simétrica: Si n � m ^m � n, entonces n = m.

� es transitiva: Si n � m ^m � p, entonces n � p.

1.2. Aritmética y Orden en N 5

También se puede probar que el orden en N es lineal. Esto es, N satisface la ley detricotomía: dados m, n 2N, se cumple exactamente una de las siguientes posibilidades

n < m _ n = m _ m < n.

Principio de Buen OrdenSea T un subconjunto no vacío de N. Decimos que m 2N es el mínimo de T, lo cualse denota por m = min T, si

m 2 T ^ (8k 2 T) ( m � k ) .

Principio de Buen Orden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Todo subconjunto no vacío T de N tiene un elemento mínimo... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Razonemos por el absurdo y supongamos que T no tiene elemento mín-imo. Sea

A = fn 2N j (8k 2 T) (n � k)g.(a) Como k = 0+ k, tenemos que 0 � k, para todo k 2N. En particular, (8k 2 T) (0 � k) .Así, 0 2 A.

(b) Supongamos que n 2 A. Así, (8k 2 T) (n � k) . Como T no tiene mínimo, n 6= kpara todo k 2 T. Luego, (8t 2 T) (n < k) . Por tanto,

(8t 2 T) (n+ 1 � k) .

Esto es, n+ 1 2 A.

Por el principio de inducción, tenemos que A = N.

Dado que T 6= ∅, podemos tomar n 2 T. Dado que n+ 1 2 A, se sigue que n+ 1 � n.Luego, existe p tal que

n+ 0 = n = n+ 1+ p.

Por la ley cancelativa, 0 = p+ 1. Absurdo. �Mediante el principio de buen orden se puede mostrar que el conjunto de enteros

positivos no está acotado superiormente.

Teorema 1.1 (Propiedad Arquimediana en Z) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Dados dos enteros positivos a y b, existe un entero positivo n tal que n � a � b... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Razonemos por el absurdo y supongamos que n � a < b, para todo enteropositivo n. Luego,

T =�

b� n � a j n 2 Z+

es un subconjunto no vacío de N. Por el principio del buen orden, sea b � k � a elmínimo de T. Pero, por hipótesis, b� (k+ 1) � a 2 T. Además,

b� (m+ 1) � a = (b�m � a)� a < b�m � a.


Absurdo, pues se contradice la minimalidad de b�m � a. �Ejercicio Muestre que el orden en N es discreto, esto es, para todo n 2 N no existem 2N tal que

n < m < n+ 1.

Solución Razonemos por el absurdo y supongamos que existe m tal que n <m < n+ 1.

Como n < m, existe p tal que

m = n+ (p+ 1) = (n+ 1) + p.

Como m < n+ 1, existe q tal que n+ 1 = m+ q+ 1. Luego,

(n+ 1) + 0 = n+ 1 = (n+ 1) + (p+ q+ 1)

Por la ley cancelativa, 0 = p+ q+ 1. Absurdo. �X

1.3 Inducción Matemática

Decimos que A � R es inductivo si

0 2 A y (8n) (n 2 A ! (n+ 1) 2 A) .

Luego, el principio de inducción afirma que N es el menor subconjunto inductivo de R.Si queremos usar el principio de inducción para establecer una proposición, debe-mos definir un conjunto A � N, mostrar que A es inductivo y concluir que A = N.Sin embargo, en la práctica matemática, se procede de una manera más informal.Específicamente, para probar una afirmación P(n), que depende de n, se aplica lasiguiente versión del principio de inducción.

Principio de Inducción Matemática (versión 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sea P (n) una fórmula que involucra el parámetro natural n. Supongamos que

P (0) y (8n) (P (n) ! P (n+ 1)) .

Entonces para todo número natural se cumple P (n) ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Ejercicio ¿Cuál es la relación entre los conjuntos A y las fórmulas P en las dosversiones del principio de inducción?

Solución Cada fórmula P satisfecha por (algunos o todos) los elementos de N

corresponde a un subconjunto de N, a saber,

fn 2N j P (n)g .

Del mismo modo un subconjunto A de N corresponde a la fórmula P (n) := n 2 A.�X

1.3. Inducción Matemática 7

Supongamos que P (n) ! P (n+ 1) se ha probado para todo n. Además supong-amos que P (0) es cierta. Entonces la siguiente derivación es posible.

1. (8n) (P (n) ! P (n+ 1)) Premisa

2. P (0) Premisa

3. P (0) ! P (1) Particularización en 1. con n := 0

4. P (1) Modus Ponens 2, 3


6. P (2) Modus Ponens 4, 5


8. P (3) Modus Ponens 6, 7...

...

Notemos que para mostrar que P (n) se cumple para cierto n fijo, debemos contin-uar la anterior derivación un número adecuado de pasos. Por supuesto, para afirmarque (8n) P (n) es válida, la anterior prueba continuaría por siempre. El principio deinducción nos permite concluir que nuestra intuición es correcta justificando el sigu-iente método de demostración.

Demostración por Inducción Matemática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

P (0) (Paso Base)

(8n) (P (n) ! P (n+ 1)) (Paso Inductivo)

(8n) P (n).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

El enfoque usual para probar un enunciado condicional ϕ! ψ es apelar al métodode la hipótesis auxiliar. Primero, se supone que ϕ es cierta y, usándola como hipóte-sis, se deriva ψ. Si esto es posible, concluimos que ϕ ! ψ se cumple. Notemos quetan pronto que ϕ ! ψ se ha probado, ϕ se tiene que descartar; esto es, ya no sesupone más que ϕ sea cierta. Además, cualquier variable libre en ϕ se fija mien-tras se deriva ψ. Por otro lado, una vez que ϕ se ha descartado, ϕ ya no es másuna premisa y es posible aplicar generalización universal sobre cualquier variablede ϕ. Esta idea se usa frecuentemente al desarrollar el paso inductivo. Se supone queP (n) y se deriva P (n+ 1) para concluir que P (n) ! P (n+ 1) . Dado que P (n) sedescarta, n ya no está más fija y es permitido concluir que (8n) (P (n) ! P (n+ 1)).Cuando la fórmula P (n) se usa de este modo, decimos que P (n) es la hipótesis in-ductiva.

Resumiendo, se puede probar (8n) P (n) ejecutando los siguientes pasos:


Paso Base Pruebe P(0).

Hipótesis inductiva Suponga P(n).

Prueba bajo hipótesis Fije n y derive P(n+ 1).

Descarte hipótesis Concluya que P (n) ! P (n+ 1) y descarte P(n). Luego, P(n)ya no es necesariamente cierta.

Generalice A descartar P(n), n vuelve a ser una variable y, luego, se puede usargeneralización universal para concluir que

(8n) (P (n) ! P (n+ 1))

Conclusión A partir del paso base y el paso inductivo, se concluye que

(8n) P (n)

Los tres pasos “prueba bajo hipótesis”, “descarte hipótesis” y “generalice” juntosconforman el paso inductivo.

Ejemplo Considere la función f definida por recursión

f (0) = 0 y f (n+ 1) = 1+ 2 � f (n).

Pruebe que f (n) = 2n � 1.

Solución Apliquemos inducción matemática a la fórmula P (n) � f (n) = 2n �1.

Paso base. Primero, debemos establecer P (0) ; esto es, para n = 0, f (n) = 2n � 1.Dado que 20 � 1 = 0, esto es obviamente verdadero.

Hipótesis inductiva. Supongamos P (n) ; esto es, supongamos que f (n) = 2n � 1 escierto. Esta hipótesis fija n hasta que P (n) se descarte.

Prueba bajo hipótesis. Ahora tenemos que probar P (n+ 1) , esto es, mostrar que f (n+ 1) =2n+1 � 1. El uso de la hipótesis inductiva se permite en la construcción de estaprueba.

f (n+ 1) = 1+ 2 � f (n) Definición.

= 1+ 2 � (2n � 1) Hipótesis inductiva: f (n) = 2n � 1

= 2n+1 � 1

Descarte hipótesis. Si se supone P (n) , se sigue que P (n+ 1) también es cierta. Luego,

( f (n) = 2n � 1) !�

f (n+ 1) = 2n+1 � 1�

.

La hipótesis inductiva P (n) se descarta ahora; esto, ya no se supone más que seaverdadera.

Generalización. Dado que n no aparece en ninguna hipótesis, una generalización sobren lleva a

(8n) ( ( f (n) = 2n � 1) !�

f (n+ 1) = 2n+1 � 1�

).


Conclusión. De acuerdo al principio de inducción, el paso base y el paso inductivojuntos prueban que

(8n) ( f (n) = 2n � 1 ).

�X

Al desarrollar pruebas por inducción se suele ser más informales y concisos, sinentrar en tantos detalles. Se omite mencionar los pasos “descarte hipótesis” y “gen-eralice” y el paso “prueba bajo hipótesis” se denomina paso inductivo. En el pasoinductivo se enuncia la hipótesis inductiva.

Ejemplo (Suma Geométrica) Sean a, r 2 R tales que r 6= 1. Muestre que

n

∑k=0

a � rk = a ��rn+1 � 1

�r� 1

, para todo n. (1.1)

Solución Paso base. Cuando n = 0, es claro que

a ��r0+1 � 1

�a� 1

= a � (r� 1)r� 1

= a.

Paso inductivo. Supongamos que la fórmula (1.1) es valida para n. Sumando a � rn+1 aambos lados, se tiene que

n+1

∑k=0

a � rk = a ��rn+1 � 1

�r� 1

+ a � rn+1 = a � rn+1 � 1+ rn+2 � rn+1

r� 1= a �

�rn+2 � 1

�r� 1

.

Luego, (1.1) se cumple para n+ 1. Por inducción, la fórmula (1.1) es valida para todonatural n. �X

Uno puede empezar la inducción en cualquier número natural n0 al elegir P (n0)como base de la inducción. Esto lleva a la siguiente variación del método de induc-ción.

Inducción desde n0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

P (n0) (Paso Base)

(8n � n0) (P (n) ! P (n+ 1)) (Paso Inductivo)

(8n � n0) P (n).. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Ejemplo Use inducción matemática para probar que

12 + 22 + 32 + � � �+ n2 =n (2n+ 1) (n+ 1)

6, para todo n � 1. (1.2)

Solución Paso base. Es claro que

12 = 1 =1 (2+ 1) (1+ 1)

6.


Luego, (1.2) se cumple para n0 = 1.

Paso inductivo. Supongamos que (1.2) es valida para n � 1. Para obtener la suma delos primeros n + 1 cuadrados, basta que sumemos el siguiente término (n+ 1)2 aambos lados de la hipótesis inductiva. Luego,

12 + 22 + � � �+ n2 + (n+ 1)2 =n (2n+ 1) (n+ 1)

6+ (n+ 1)2

= (n+ 1)�

n (2n+ 1) + 6 (n+ 1)6

�

= (n+ 1)�

2n2 + 7n+ 66

�=(n+ 1) (2n+ 3) (n+ 2)

6.

Por tanto, (1.2) se cumple para n + 1. Por inducción, la fórmula es verdadera paratodo n � 1. �X

Definición La función factorial en N (denotada por n!) se define por

(a) 0! = 1 (b) (n+ 1)! = (n+ 1) � n!, para todo n � 0.

La existencia del factorial está garantizada por el teorema de recursión (ver ejerci-cio _).

Ejemplo Use inducción matemática para probar que 3n < n! para n � 7.

Solución Paso base. Para n0 = 7, se tiene que 37 = 2187 y

7! = 7 � 6! = (7 � 6) � 5! = (42 � 5) � 4! = (210 � 4) � 3! = (840 � 3) � 2! = (2520 � 2) � 1 = 5040 � 1 � 0! = 5040.

Luego, el paso base se cumple.

Supongamos que 3n < n! y veamos que 3n+1 < (n+ 1)!. Como

n+ 1 > n � 7 > 3,

al multiplicar a ambos lados de la hipótesis inductiva, se tiene que

3n+1 = 3n � 3 < n! � (n+ 1) = (n+ 1)!

Por inducción, la desigualdad se cumple para todo n � 7. �X

En este punto es importante llamar la atención sobre el hecho que se debe ser muycuidadoso al establecer ambos pasos del principio de inducción antes de extraercualquier conclusión. Ningún de los pasos es suficiciente por si mismo. La validezdel paso inductivo no depende necesariamente de la verdad del enunciado que seprocura probar. Por ejemplo, miremos la fórmula falsa

P (n) � 1+ 3+ 5+ � � �+ (2n� 1) = n2 + 3. (1.3)

Supogamos que P (n) . Sumando a ambos lados 2 (n+ 1)� 1 = 2n+ 1, se tiene que

1+ 3+ 5+ � � �+(2n� 1)+ (2n+ 1) =�

n2 + 3�+(2n+ 1) =

�n2 + 2n+ 1

�+ 3 = (n+ 1)2+ 3,


que es precisamente P (n+ 1) . Por tanto, (8n) (P (n) ! P (n+ 1)). Sin embargo, noes posible hallar un valor n para el cual la fórmula (1.3) sea verdadera (ver ejercicio _).

En algunas situaciones, resulta más conveniente suponer que, no sólo P(n) escierta, sino que P(k) es verdadera para todos los k con 0 � k � n y probar, a par-tir de esta hipótesis inductiva, que P(n+ 1) es verdadera. La variante de inducciónque justifica este método de demostración se denomina principio de inducción com-pleta. A continuación enunciamos dos versiones de dicho principio y dejamos comoejercicio para el lector la prueba de que son equivalentes.

Principio de Inducción Completa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(versión 1) (versión 2)

Sea A �N que satisfaga Si A �N cumple

(a) 0 2 A.(8n 2N) [(8k < n)(k 2 A)! n 2 A] ,

(b) (8n 2N) [(8k � n)(k 2 A)! n+ 1 2 A] .

Entonces A = N. entonces A = N... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Aunque las anteriores versiones pareces ser más fuertes, de hecho, son equiva-lentes al principio usual de inducción.

Teorema 1.2 Los siguientes principios son equivalentes:

(a) Principio de Inducción.

(b) Principio de Buen Orden.

(c) Principio de Inducción Completa.

Prueba. (a)! (b) Esta implicación se probó en la sección anterior.

(b) ! (c) Probemos la versión 1 del principio de inducción completa. Sea A � N

tal que 0 2 A y supongamos que

(8n 2N)[(8k � n)(k 2 A)! n+ 1 2 A].

Razonemos por el absurdo y supongamos que A 6= N. Luego, T = N� A 6= ∅.Sea m = min T. Dado que 0 2 A, se sigue que m 6= 0. Por lema 1.1, existe n tal quem = n+ 1. Por la minimalidad de m, para todo k � n : k /2 T. Así, (8k � n)(k 2 A).Lo cual implica que m = n+ 1 2 A, absurdo.

(c)! (a) Supongamos que se cumple la versión 2 del principio de inducción com-pleta. Sea A �N un conjunto inductivo. Asociemos a A, el siguiente conjunto

B = fn 2N j (8m � n)(m 2 A)g.

Supongamos que (8k � n)(k 2 B) y veamos que n+ 1 2 B. Sea m � n+ 1. Hay dosposibilidades:

Caso 1. m < n+ 1. Luego, m � n.Por la hipótesis inductiva, n 2 B y, en particular,


m 2 A.

Caso 2. m = n + 1. De nuevo, n 2 B y, particular, n 2 A. Como A es inductivo,m = n+ 1 2 A.

Podemos concluir que (8m � n+ 1)(m 2 A). Esto es, (n+ 1) 2 B. Por tanto, B = N.Notemos que B � A. Por consiguiente, A = N. �

Para ilustrar el uso de la inducción completa, consideremos los números de Fi-bonacci:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, . . .(1.4)

La sucesión recibe ese nombre en honor del matemático medieval Leonardo de Pisa,también conocido como Leonardo Fibonacci (contracción de Filius Bonaccii, hijo deBonaccio en latín). En su libro Liber Abaci (Libro del Ábaco, 1202), Fibonacci propuso unfamoso acertijo sobre crecimiento de conejos, en cuya solución surge la sucesión (1.4).

Notemos que cada número de Fibonacci es la suma de los dos números que lepreceden, excepto los dos primeros términos. Esto nos lleva a la siguiente definiciónpor recursión:

F0 = 0, F1 = 1 y Fn+2 = Fn + Fn+1, para todo n.

Ejemplo Muestre que para todo n � 2 :

Fn >

�43

�n. (1.5)

Solución Apliquemos inducción completa. Notemos que

F2 = 2 > 1.7778 ' 169=

�43

�2y F3 = 3 > 2.3704 ' 64

27=

�43

�3.

(La razón para iniciar la inducción en n = 2, 3 es que necesitamos tener n � 3 en elpaso inductivo. Es usual que en una prueba por inducción completa se deba iniciarla inducción para varios valores).

Para el paso inductivo, suponemos que (1.5) es válida para 2 � k < n + 2, donden � 2. En particular, se tiene que

Fn >

�43

�ny Fn+1 >

�43

�n+1.

(Dada la recursión de Fn es suficiente suponer que (1.5) es válida para n, n + 1. Escomún simplificar la hipótesis inductiva de ese modo dependiendo de la definiciónrecursiva del objeto en cuestión). Luego,

Fn+2 = Fn+ Fn+1 >

�43

�n+

�43

�n+1=

�43

�n �1+

43

�=

�43

�n� 7

3>

�43

�n� 16

9=

�43

�n+2

Esto completa el paso inductivo. �X


Sean

φ :=1+p

52

y φ0 :=1�p

52

.

las raíces de la ecuación cuadrática x2 � x� 1 = 0 (φ se conoce como la razón áurea).Podemos dar una fórmula explícita de Fn en términos de n.

Fórmula de Binet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Fn =1p5

h(φ)n �

�φ0�ni

. (1.6)

.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Usemos inducción completa. Paso base, debemos verificar (1.6) para n =0 :

1p5

h(φ)0 �

�φ0�0i=

1p5[ 1� 1 ] =

0p5= 0 = F0

y n = 1 :

1p5

h(φ)1 �

�φ0�1i=

1p5

"1+p

52

� 1�p

52

#=

1p5� 2p

52

= 1 = F1.

Paso inductivo. Sea n � 0 y supongamos que

Fn =1p5

h(φ)n �

�φ0�ni

y Fn+1 =1p5

h(φ)n+1 �

�φ0�n+1

i.

Dado que φ, φ0 son raíces de la ecuación x2 � x� 1 = 0, se cumple que

(φ)2 = φ+ 1 y�φ0�2= φ0 + 1.

Luego,

Fn+2 = Fn + Fn+1 =1p5

�(φ)n � (φ0)n

�+

1p5

h(φ)n+1 � (φ0)n+1

i=

1p5

h(φ)n + (φ)n+1

i� 1p

5

h(φ0)n + (φ0)n+1

i=

1p5(φ)n [ 1+ φ ] � 1p

5(φ0)n [ 1+ φ0 ]

=1p5

h(φ)n+2 � (φ0)n+2

i.

�


Existen conexiones muy interesantes entre la sucesión de Fibonacci y la razónáurea [Wa01]. Por ejemplo, las siguientes fórmulas son válidas.

limn!∞

Fn+1

Fn= φ

∞

∑n=1

1Fn= 4� φ

∞

∑n=1

(�1)n

Fn+1 � Fn= φ� 1

Ejercicio Muestre que�1 11 0

�n=

�Fn+1 Fn

Fn Fn�1

�, para todo n � 1..

Solución En este caso, no es necesario aplicar inducción completa. El paso basees inmediato �

1 11 0

�=

�F2 F1F1 F1�1

�.

Paso inductivo.

An+1 = An A =�

Fn+1 FnFn Fn�1

� �1 11 0

�=

�Fn + Fn+1 Fn+1Fn + Fn�1 Fn

�=

�Fn+2 Fn+1Fn�1 Fn

�.

�X

Por último, queremos mencionar una propiedad sorprendente de los números deFibonacci. La prueba aplica inducción completa de una manera ingeniosa, ver [En98,p. 217].

Teorema de Zeckendorf. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Cualquier entero positivo n se puede expresar de forma única como la suma de números deFibonacci distintos y no consecutivos:

n =m

∑j=1

Fkj,

��k j � k j�1�� 2.

.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Dios creo los enteros, el resto...

Bajo un enfoque axiomático, hemos introducido las operaciones básicas, junto consus elementos neutros, y el orden usual de los números naturales< . La anteriorsituación se suele representar afirmando que N, junto con las operaciones, el ordeny los neutros, forman la estructura hN,+, �, 0, 1,<i .

En general, una estructura es una tupla finita, compuesta de un conjunto no vacío,operaciones o relaciones definidas sobre el conjunto y una lista de constantes espe-ciales. En algunas ocasiones se acostumbra decir que el conjunto dado cumple ciertapropiedad, sin mencionar las operaciones o relaciones involucradas. Por ejemplo, sedice que N es un conjunto bien ordenado, cuando en realidad se debería afirmar quela estructura hN,<i está bien ordenada, es decir, que satisface el principio de buenorden.


Las propiedades fundamentales de los números naturales se pueden tomar comopunto de partida para la construcción de los sistemas numéricos fundamentales.Esto es, es posible extender la estructura de los números naturales del siguientemodo

N ( Z ( Q ( R ( C.

La motivación principal para llevar a cabo estas extensiones surge de la busquedade soluciones a ecuaciones de la forma

x+m = 0, m � x = 1, xn = m y xn + 1 = 0, con m, n 2N.

En general, la solución de ecuaciones de este tipo requiere la existencia de númerosnegativos, números racionales, números irracionales y números imaginarios, respectiva-mente.

A continuación describiremos brevemente cómo se llevan a cabo estas extensiones.Intuitivamente,

(a) Todo número entero se puede representar como una diferencia de dos númerosnaturales.

(b) Todo número racional se puede representar como una fracción de dos númerosenteros.

(c) Todo número real se puede representar como el límite de una sucesión denúmeros racionales.

(d) Todo número complejo se puede representar en la forma a + bi, con a y bnúmeros reales.

La idea es formalizar las anteriores intuiciones de una forma adecuada. Así, la difer-encia m� n de dos naturales se concibe como el par ordenado (m, n) . Como habríainfinitas representaciones para un número entero, es necesario identificarlas medi-ante la relación de equivalencia en N�N :

(m, n) �e (p, q) sii m+ q = n+ p.

De este modo, se defineZ := N�N/ �e .

Así, un número entero es una clase de equivalencia a = [(m, n)]�e:= [m� n] de

diferencias.

Sean a = [m� n] y b = [p� q] en Z. Se define

a+Z b = [(m+ p)� (n+ q)] y a �Z b = [(mp+ nq)� (mq+ np)] ,

con elementos neutros

0Z = [0� 0] y 1Z = [1� 0] .

El orden en Z se introduce de un modo análogo.

a <Z b sii m+ q < n+ p.

Despues de algo de esfuerzo, se prueba que las operaciones y el orden no dependende representantes y que satisfacen las propiedades básicas de Z. Además, se muestra


que existe una función inyectiva de N en Z que preserva las operaciones y el orden. Portanto, se puede afirmar que N ( Z y omitir el subíndice “Z” al referirnos a lasoperaciones enteras y al orden entero.

Todo lo anterior se puede resumir del siguiente modo.

hZ,+, �, 0, 1,<i es un dominio entero cuyo orden es lineal, discreto y arquimediano.

Análogamente, la fracciónab

entre dos enteros se concibe como el par ordenado

(a, b) . De nuevo, habría infinitas fracciones representando un mismo número racional.Así que se identifican por la relación de equivalencia en Z�Z� :

(a, b) �r (c, d) sii a � d = b � c.

Se defineQ := Z�Z�/ �r .

Esto es, un número racional es una clase de equivalencia r = [(a, b)]�r:=

� ab�

defracciones.

Dados r =h a

b

iy s =

h cd

ien Q, definimos

r+Q s =�

a � d+ b � cd � d

�y r �Q s =

h a � cb � d

i,


0Q =

�01

�y 1Q =

�11

�.

Luego, se introducen los elementos positivos en Q.

0Q <Q r sii a � b 2 Z+.

Es posible mostrar que las operaciones y el orden no dependen de representantes yque satisfacen las propiedades básicas de Q. De nuevo, se prueba que existe una fun-ción inyectiva de Z en Q que preserva las operaciones y el orden. Por tanto, se puede afir-mar que Z ( Q y omitir el subíndice “Q” al referirnos a las operaciones racionales yal orden racional.

Todo lo anterior se resume en que

hQ,+, �, 0, 1,<i es un campo ordenado cuyo orden es denso y arquimediano.

En la construcción de R, se puede concebir un número real como el conjunto detodos los números racionales menores que él o como el límite de una sucesión denúmeros racionales que converge a él. Para evitar problemas de circularidad, se for-maliza las anteriores intuiciones mediante cortaduras de Dedekind o de sucesionesde Cauchy, respectivamente. Esto da lugar a dos posibles enfoques en la construc-ción de los números reales. En el ápendice A, ofrecemos la construcción de la recta


real mediante sucesiones de Cauchy, debida independientemente a Weierstrass y aCantor.

Por último, se tomaC = R�R.

Así, un número complejo es un par ordenado z = (a, b) de números reales.

Dados z = (a, b) y w = (c, d) en C, definimos

z+C w = (a+ c, b+ d) y z �C w = (ac� bd, ad+ bc) ,


0C = (0, 0) y 1C = (1, 0) .

Es relativamente directo probar que C satisface las propiedades usuales de campo.Tomando aC = (a, 0) para todo a 2 R, se obtiene una función inyectiva de R en C quepreserva las operaciones. Por tanto, se puede afirmar que R ( C y omitir el subíndice“C” al hacer referencias a las operaciones complejas.

Si se toma i = (0, 1) , entonces es fácil verificar que

(a, 0) � (1, 0) + (b, 0) � (0, 1) = (a, b) y i2 = (�1, 0) .

Lo cual coincide con la notación usual z = a+ bi, donde i =p�1. Como i2 = �1,

no es posible que exista un orden en C que sea compatible con las operaciones decampo. Resumiendo

hC,+, �, 0, 1i es un campo (no ordenado).

Para un estudio detallado de la anterior construcción, se puede consultar el capítulo5 de [En77], el capítulo 6 de [Pa09] o el texto clásico de Feferman [Fe64].

Ejercicios

1. Muestre que n 6= n+ 1 y n < n+ 1, para todo n 2N.

2. Demuestre las siguientes versiones del teorema de recursión.

(a) Versión 3. Dados a 2 A y g : A�N! A, existe una única función f : N!A que satisface

f (0) = a y f (n+ 1) = g( f (n), n), para todo n 2N.

(b) Versión 4. Dados a, b 2 A y g : A � A ! A, existe una única función f :N! A que satisface

f (0) = a, f (1) = b y f (n+ 2) = g( f (n), f (n+ 1)), para todo n 2N.

3. Aplique las versiones anteriores de recursión para justificar la existencia de lafunción factorial y de la sucesión de Fibonacci.


4. Sean h : A ! A inyectiva y a 2 A tal que a /2 rango (h) . Muestre que lafunción f : N! A, definida por recursión

f (0) = a y f (n+ 1) = h ( f (n)) , para todo n 2N,

es inyectiva.

5. Pruebe el teorema de unicidad de Dedekind.

6. Use inducción matemática para probar las propiedades de la suma, el productoy el orden enunciadas en la sección 1.2.

7. Sean m, n 2N. Muestre que

(a) m+ n = 0 si y sólo si m = 0 = n.

(b) m � n = 0 si y sólo si m = 0_ n = 0.

(c) m � n = 1 si y sólo si m = 1 = n.

8. Sean m, n, k 2N. Muestre que

(a) m+ k < n+ k si y sólo si m < n.

(b) Si k 6= 0, entonces [m � k < n � k si y sólo si m < n].(c) Si k 6= 0, entonces [m � k = n � k si y sólo si m = n].

9. Obtenga las ecuaciones recursivas de la exponenciación natural

E1. m0 = 1 E2. mn+1 = mn �m

Enuncie y pruebe las leyes usuales de exponentes. Por ejemplo

mn+p = mn �mp.

10. Use el principio de buen orden para probar que no existe un número entero atal que 0 < a < 1.

11. Muestre que no existe una función f : N!N tal que para todo n 2N :

f (n+ 1) < f (n) .

12. Sea n 2N. Considere la fórmula P (n) :

(n+ 2)! < (n+ 2)n+2 .

(a) Desarrolle el paso base.

(b) Enuncie la hipótesis inductiva.

(c) Desarrolle la prueba bajo hipótesis.

(d) Descarte la hipótesis y generalice.

(e) Enuncie la conclusión.

13. Sea n un entero mayor que 1. Considere la fórmula P (n) :

1+14+

19+ � � �+ 1

n2 < 2� 1n

.


(a) Desarrolle el paso base.

(b) Enuncie la hipótesis inductiva.

(c) Desarrolle la prueba bajo hipótesis.

(d) Descarte la hipótesis y generalice.

(e) Enuncie la conclusión.

14. Sea P (n) una fórmula arbitraria. Muestre que las siguientes afirmaciones sonequivalentes.

(a) (8n 2N) [ (8k < n) P (k) ! P (n) ] ! (8n 2N) P (n) .

(b) (9n 2N) P (n) ! (9m 2N) [ P (m) ^ (8k < n):P (k) ] .

(c) (8n 2N) [ P (n) ! (9k < n) P (k) ] ! (8n 2N):P (n) .

15. Pruebe las siguientes fórmulas para todo n � 1 :

(a) 1+ 2+ 3+ � � �+ n =n (n+ 1)

2.

(b) 1+ 3+ 5+ � � �+ (2n� 1) = n2.

(c) 1 (1!) + 2 (2!) + 3 (3!) + � � �+ n (n!) = (n+ 1)!� 1.

(d) 13 + 23 + � � �+ n3 =

�n (n+ 1)

2

�2.

(e) 12 + 32 + � � �+ (2n� 1)2 =n (2n� 1) (2n+ 1)

3.

(f) 13 + 33 + � � �+ (2n� 1)3 = 2n4 � n2.

(g) 1 � 2+ 2 � 3+ � � �+ n (n+ 1) =n (n+ 1) (n+ 2)

3.

(h)1

1 � 2 +1

2 � 3 + � � �+1

n (n+ 1)=

nn+ 1

.

(i)1

1 � 3 +1

3 � 5 + � � �+1

(2n� 1) (2n+ 1)=

n2n+ 1

16. Use inducción para mostrar las siguientes desigualdades:

(a) Para todo n � 2 : n2 + n < n3 + 1 (b) Para todo n � 2 : 2n�2 < n!

(c) Para todo n � 5 : n2 + 1 < 2n (d) Para todo n � 4 : n2 < n!

(e) Para todo n � 4 : 2n2 + n < 3n. (f) Para todo n � 4 : 2n < n!

(g) Para todo n � 6 : 7n < 2n. (h) Para todo n � 6 : n3 < n!


17. Muestre que

pn �

n

∑k=1

1pk� 2

pn� 1, para todo n � 2.

Concluya que∞

∑n=1

1pn

es divergente.

18. Use inducción matemática para mostrar que para todo n � 1 :

1+ 2+ 22 + � � �+ 2n�1 = 2n � 1.

19. Use inducción completa para establecer que para todo n � 1 :

an � 1 = (a� 1)�

an�1 + an�2 + � � �+ a2 + a+ 1�

.

[Sug: an+1 � 1 = (a+ 1) (an � 1)� a�an�1 � 1

�].

20. Pruebe que el cubo de todo entero se puede escribir como la diferencia de doscuadrados. [Sug: note que

n3 =�

13 + 23 + � � �+ n3��

13 + 23 + � � �+ (n� 1)3�].

21. Use inducción matemática para probar que para todo n � 1 :

2 � 6 � 10 � 14 � � � � � (4n� 2) =(2n)!

n!.

Use la anterior fórmula para obtener la desigualdad

2n (n!)2 � (2n)!, 8n � 1.

22. Demuestre desigualdad de Bernoulli. Si a+ 1 > 0, entonces

(1+ a)n � 1+ n � a, 8n � 1.

23. Para todo n � 1, pruebe lo siguiente por inducción matemática:

(a)112 +

122 +

132 + � � �+

1n2 � 2� 1

n. (b)

12+

222 +

323 + � � �+

n2n = 2� n+ 2

2n .

24. Pruebe que el número(2n)!2n � n!

es un entero positivo para todo n � 0.

25. Resuelva el acertijo de Fibonacci. “Una pareja de conejos tarda un mes en al-canzar la edad fértil, a partir de ese momento cada vez engendra una pareja deconejos, que a su vez, tras ser fértiles engendrarán cada mes una pareja de cone-jos. ¿Cuántos conejos habrá al cabo de un determinado número de meses?”


26. Sea Fn el n-ésimo número de Fibonacci. Pruebe la fórmula de Cassini (1680) :

Fn+1 � Fn�1 � F2n = (�1)n , n � 1.

27. Sea n > 6. Pruebe que Fn = 5 � Fn�4 + 3Fn�5.

28. Pruebe que para todo n � 1 y k � 2 se cumple que

Fn+k = Fk � Fn+1 + Fk�1 � Fn.

29. Pruebe las siguientes fórmulas para todo n � 1 :

(a) F1 + F2 + F3 + � � �+ Fn = Fn+2 � 1,

(b) F1 + F3 + F5 + � � �+ F2n�1 = F2n,

(c) F2 + F4 + F6 + � � �+ F2n = F2n+1 � 1,

(d) 1 � F1 + 2 � F2 + � � �+ n � Fn = n � Fn+2 � Fn+3 + 2,

30. Muestre que para todo n � 2 :

F21 + F2

2 + F23 + � � �+ F2

n = Fn (Fn+1 + Fn�1) .

31. Defina los números de Lucas por la siguiente recursión

L0 = 2, L1 = 1 y Ln+2 = Ln + Ln+1, para todo n.

Pruebe la siguiente fórmula

Ln = (φ)n +

�φ0�n .

32. Pruebe que Ln <

�74

�n, para todo n � 1.

33. Pruebe las siguientes identidades que relacionan la sucesiones de Fibonacci yde Lucas.

(a) Ln = Fn�1 + Fn+1. (b) L2n = 5 � F2

n + 4 � (�1)n . Concluya que limn!∞

Ln

Fn=p

5.

(c) F2n = Ln � Fn. (d) Fn =Ln�1 + Ln+1

5.

34. Sean a, b 2 R. Defina los números generalizados de Fibonacci por

G0 = b� a, G1 = a y Gn+2 = Gn + Gn+1, para todo n.

Pruebe queGn = aFn�2 + bFn�1, n � 3.


35. La sucesión fgng se define por la siguiente recursión

g0 = 0, g1 = 1, y gn+2 = gn + gn+1 + gn � gn+1 para todo n.

Muestre que gn = 2Fn � 1, para todo n.

36. Suponga que los números an se definen recursivamente por

a0 = 0, a1 = 1, a2 = 2 y an+3 = an + an+1 + an+2, para todo n.

Use inducción completa para probar que an < 2n, para todo n.

37. Si los números bn se definen por

b0 = 6, b1 = 11 y bn+2 = 3bn+1 � 2bn, para todo n,

pruebe quebn = 5 � 2n + 1, 8n.

38. Sea A �N no vacío. Si existe s 2N tal que

(8a 2 A) (a � s) ,

entonces A tiene un máximo.

39. Muestre que todo conjunto no vacío de enteros negativos tiene un máximoelemento.

40. Pruebe que si A � Z tiene una cota inferior en Z, entonces A tiene mínimo.Muestre que la afirmación es falsa en Q.

2

Números Enteros

2.1 División en Z

El siguiente resultado es familiar a todos desde nuestra educación primaria; afirmaque un entero a se puede “dividir” por un entero positivo de forma tal que el residuoes menor que d. El enunciado preciso de este hecho es el siguiente teorema.

Algoritmo de la División . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Dados enteros a y d > 0, existen enteros únicos q y r que satisfacen

a = q � d+ r y 0 � r < d.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. (Existencia) Primero veamos que

T = fa� n � d j n 2 Z^ a� n � d � 0g 6= ∅.

Como d � 1, entonces jaj � d � jaj . Por tanto,

a� (� jaj) � d = a+ jaj � d � a+ jaj � 0.

Tomando n = � jaj , vemos que (a� n � d) 2 T. Aplicando el principio del buenorden, existe un entero r tal que r = min T. Por la definición de T, existe un entero qtal que

r = a� q � d y 0 � r.

Afirmamos que r < d. En caso contrario, se tendría que r � d. Luego,

m = a� (q+ 1) � d = (a+ q � d)� d = r� d � 0.

Por tanto, m 2 T y m = r� d < r, absudo. Luego, se debe cumplir que r < d.

(Unicidad) Supogamos que a tiene dos representaciones de la forma deseada:

a = q � d+ r = q0 � d+ r0 y 0 � r, r0 < d.

Entonces,

r� r0 = d � (q0 � q) y jr� r0j = jdj � jq0 � qj .

Sumando las desigualdades�d < �r0 � 0 y 0 � r < d, se obtiene que�d < r� r0 <d. Luego, jr� r0j < d y, por tanto,

0 ��q0 � q

�� < 1.

24 2. Números Enteros

Dado que jq0 � qj es un entero no negativo, la única posibilidad es que jq0 � qj = 0.Por lo cual, q = q0. Esto a su vez, implica que r = r0. �

Los enteros q y r se denominan el cociente y el residuo al dividir a por d, respecti-vamente.

En este contexto, definimos las operaciones div y mod por

a div d = q y a mod d = r.

Debemos enfatizar que a mod d 2 f0, 1, . . . , d� 1g .

Ejemplo Como aplicaciones del algoritmo de la división, probemos las siguientesafirmaciones.

(a) Para todo entero a, a2 es de la forma 4k o de la forma 4k+ 1.

(b) El cuadrado de cualquier entero impar es de la forma 8k+ 1.

(c) Para todo a � 1, la expresióna�a2 + 2

�3

es un número entero.

Solución (a) Primero, notemos que todo entero a al ser dividido por 2, deja dosposibles residuos r = 0 o r = 1. Cuando r = 0, a tiene la forma a = 2q y se denominapar. En este caso,

a2 = (2q)2 = 4q2 = 4k.

Cuando r = 1, a tiene la forma 2q+ 1 y se denomina impar. En este caso,

(a)2 = (2q+ 1)2 = 4q2 + 4q+ 1 = 4�

q2 + q�+ 1 = 4k+ 1.

En cualquier caso, a2 deja residuo 0 o 1 al ser dividido por 4.

(b) Por el algoritmo de la división, todo entero tiene una de las formas 4q, 4q + 1,4q + 2 y 4q + 3. Es claro que sólo los enteros de las formas 4q + 1 y 4q + 3 son im-pares. Luego,

(4q+ 1)2 = 8�

2q2 + q�+ 1 = 8k+ 1 y (4q+ 3)2 = 8

�2q2 + 3q+ 1

�+ 1 = 8k+ 1.

(c) De acuerdo al algoritmo de la división, todo entero a es de la forma 3q, 3q + 1,3q+ 2. En el primer caso,

a�a2 + 2

�3

=3q�9q2 + 2

�3

= q�

9q2 + 2�2 Z+.

Similarmente, si a = 3q+ 1,

a�a2 + 2

�3

=(3q+ 1)

�9q2 + 6q+ 3

�3

= (3q+ 1)�

3q2 + 2q+ 1�2 Z+.

Finalmente, si a = 3q+ 2,

a�a2 + 2

�3

=(3q+ 2)

�9q2 + 12q+ 6

�3

= (3q+ 2)�

3q2 + 4q+ 2�2 Z+.

2.1. División en Z 25

�X

Definición Un entero a se dice que es divisible por un entero d 6= 0 (en símbolos d j a),si existe algún entero q tal que a = d � q. Escribimos d - a para indicar que a no es divisiblepor d.

También se dice d es divisor de a, que a es factor de d o que a es un múltiplo ded. Siempre que se emplee la notación d j a, se entiende que d 6= 0. Notemos quelos divisores de un entero siempre ocurren en pares. Por tanto, nos limitaremos aconsiderar divisores positivos.

Teorema 2.1 Para enteros a, b y c, se cumple

(a) a j 0, 1 j a, a j a. (b) Si a j b y b 6= 0, entonces jaj � jbj .

(c) a j b y b j a si y sólo si a = �b. (d) a j 1 si y sólo si a = �1.

(e) Si a j b y b j c, entonces a j c. (f) Si a j b y c j d, entonces ac j bd.

(g) Si d j a y d j b, entonces d j (a � s+ b � t) para enteros arbitrarios s, t.

Prueba. (b) Si a j b, entonces existe un entero q tal que b = a � q. Como b 6= 0,entonces q 6= 0. Luego, jqj � 1. Por tanto,

jbj = jaj � jqj � jaj � 1 = jaj .

(c) Si a j b y b j a, entonces, por (b), jaj � jbj � jaj . Luego, jaj = jbj . Por tanto,a = �b. La otra implicación es obvia.

(g) Si d j a y d j b, entonces existen enteros q1, q2 tales que a = d � q1 y b = d � q2.Por tanto,

as+ bt = (dq1) s+ (dq2) t = d � (q1s+ q2t) .

Tomando q = q1s+ q2t, se tiene que d j (a � s+ b � t) .

(a), (e) y (f) son inmediatas de la definición. (d) se sigue de (a) y (c). �La propiedad (g) del teorema 2.1 se puede extender, por inducción, a sumas de

más de dos términos. Esto es, si d divide simultáneamente a a1, a2, . . . , an, entonces

c j (a1s1 + a2s2 + � � �+ ansn) , 8s1, s2, . . . , sn 2 Z.

Sean a, b enteros arbitarios con al menos uno de ellos distinto de cero. Decimos qued es un divisor común de a y b si d j a y d j b. Notemos que 1 siempre es divisorcomún de a y b. Como a 6= 0 o b 6= 0, existe una cantidad finita de divisores comunespositivos. Entre estos, existe uno mayor.

Definición Sean a, b 2 Z con al menos uno ellos distinto de cero. El máximo comúndivisor de a y b, denotado por gcd (a, b) , es el entero positivo d que satisface

(a) d j a y d j b. (b) Si c j a y c j b, entonces c � d.

Diremos que a y b son primos relativos si gcd (a, b) = 1.


Una combinación lineal de m y n es un entero de la forma m � s+ n � t, con s y tenteros. Veamos que el máximo común divisor de a y b se puede representar como combi-nación lineal de a y b.

Identidad de Bézout en Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Dados dos enteros a y b, no ambos iguales a cero, existen enteros s y t tales que

gcd (a, b) = a � s+ b � t.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Prueba. Considere el conjunto de todas las combinaciones lineales positivas de a

y b :T = fa � u+ b � v j au+ bv > 0^ u, v 2 Zg .

Primero veamos que T 6= ∅. Por ejemplo, si a 6= 0, jaj = a � u+ b � 0 2 T, donde

u =�

1, si a > 0.�1, si a < 0.

Aplicando el principio del buen orden, T tiene un elemento mínimo d. Por la defini-ción de T, existen enteros s y t para los cuales

d = a � s+ b � t. (2.1)

Afirmamos que d = gcd (a, b) .

(a) Aplicando el algoritmo de la división, podemos obtener enteros q y r tales quea = q � d+ r y 0 � r < d. Entonces r se puede escribir en la forma

r = a� q � d = a� q (a � s+ b � t) = a (1� q � s) + b (�q � t) .

Si r > 0, entonces la anterior representación implicaría que r 2 T y r < d = min T,absurdo. Luego, r = 0. Así, a = q � d. Esto es, d j a. Similarmente, se muestra qued j b. Entonces, d es divisor común de a y b.

(b) Ahora, sea c un divisor común positivo de a y b. Por el teorema 2.1 (g) y (2.1), sesigue que c j d. Por el teorema 2.1 (e), se sigue que c = jcj � jdj = d.

De (a) y (b), se puede concluir que d = gcd (a, b) = a � s+ b � t. �Al aplicar el principio del buen orden en la anterior prueba, obtenemos que el

máximo común divisor de a y b se puede describir como el menor entero positivo dela forma a � s+ b � t. Pero, dado que el principio del buen orden sólo asegura la exis-tencia del mínimo, la prueba no es constructiva. Sin embargo, es posible desarrollarun procedimiento algorítmico para calcular los coeficientes s y t.

Corolario 2.1 Sean I := fa � u+ b � v j u, v 2 Zg y d = gcd(a, b). Entonces

I = fn � d j n 2 Zg y d = min�

I+�= min fm 2 I j m > 0g .

Prueba. Como d j a y d j b, entonces d j a � u + b � v, 8u, v 2 Z. Por tanto, todoelemento de I es múltiplo de d. Por otro lado, como d = a � s+ b � t, entonces

n � d = n (a � s+ b � t) = a (n � s) + b (n � t) 2 I.

2.1. División en Z 27

La otra afirmación es inmediata de la prueba de la identidad de Bézout. �El siguiente resultado es consecuencia inmediata de la identidad de Bezout y el

teorema 2.1 (g).

Teorema 2.2 a y b son primos relativos si y sólo si existen s y t tales que a � s+ b � t = 1.

Corolario 2.2 Si d = gcd (a, b) , entonces gcd (a/d, b/d) = 1.

Prueba. Primero, notemos que aunque a/d y b/d tengan la apariencia de frac-ciones, de hecho, son enteros, ya que d j a y d j b. Como d = a � s+ b � t, se sigue

1 =� a

d

�� s+

�bd

�� t.

Por el teorema 2.2, a/d y b/d son primos relativos. �

Corolario 2.3 Supongamos que gcd (a, b) = 1.

(a) Si a j c y b j c, entonces ab j c.

(b) Si gcd (a, c) = 1, entonces gcd (a, b � c) = 1.

Prueba. Dado que gcd (a, b) = 1, existen enteros s, t tales que 1 = a � s+ b � t.

(a) Si a j c y b j c, existen q1, q2 tales que c = a � q1 y c = b � q2. Luego,

c = c (as+ bt) = cas+ cbt = (bq2) � (as) + (aq1) � (bt)

= (ab) � (q2s) + (ab) � (q1t) = ab � (q2s+ q1t)

Luego, ab j c.

(b) Si gcd (a, c) = 1, existen enteros u, v tales que 1 = a � u+ c � v. Por tanto,

1 = 1 � 1 = (as+ bt) (au+ cv) = a � (asu+ btu+ csv) + (bc) � (tv) .

Por el teorema 2.2, gcd (a, b � c) = 1. �Lema de Euclides . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Si a j b � c y gcd (a, b) = 1, entonces a j c.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Dado que a y b son primos relativos, existen s y t tales que 1 = a � s+ b � t.Por tanto,

c = 1 � c = (a � s+ b � t) c = (a � c) s+ (b � c) t.

Dado que a es divisor común de a � c y b � c, tenemos que a j c. �Si a y b no son primos relativos, entonces la conclusión del lema de Euclides puede

fallar. Por ejemplo, 10 divide a 20 = 4 � 5, pero 10 - 4 y 10 - 5.

El siguiente teorema da una caracterización equivalente del máximo común di-visor que no involucra la relación de orden. La ventaja de esta caracterización al-ternativa es que permite definir la noción de máximo común divisor en estructurasalgebraicas que no posean relación de orden.


Teorema 2.3 Sean a y b, no ambos cero. Para un entero positivo d, d = gcd (a, b) si y sólo si

(a) d j a y d j b. (b) Si c j a y c j b, entonces c j d.

Prueba. (!) Supongamos que d = gcd (a, b) . Por definición, se cumple (a). Supong-amos que c j a y c j b. Por la identidad de Bézout, existen s, t tales que d = a � s+ b � t.Por el teorema 2.1 (g), c j (a � s+ b � t) . Luego, c j d. Por tanto, d satisface (b).

( ) Supongamos que d satisface (a) y (b). Por (a), d es divisor común de a y b.Ahora, sea c un divisor común de a y b. Por (b), se sigue que c j d. Por el teorema 2.1(e), se tiene que c � jcj � jdj = d. Luego, d = gcd (a, b) . �

2.2 Algoritmo de Euclides

En el libro VII de los Elementos de Euclides, se describe un procedimiento eficientepara hallar el máximo común divisor de dos enteros dados. Este algoritmo involucrauna aplicación recursiva del algoritmo de la división y se fundamenta en el siguientelema.

Lema 2.1 Si a = b � q+ r, entonces gcd (a, b) = gcd (b, r) .

Prueba. Sea d = gcd (a, b) . Dado que d j a y d j b, entonces d j (a� b � q) = r. Portanto, d es divisor común de b y r. Ahora, si c es un divisor común de b y r, entoncesc j (b � q+ r) = a.Luego, c es divisor común de a y b. Así, c � d. Por definición,d = gcd (b, r) . �

El algoritmo de Euclides se puede describir del siguiente modo. Como gcd (jaj , jbj) =gcd (a, b) , dados a, b podemos suponer que a � b > 0. Definamos

r0 = a y r1 = b.

Entonces definimos recursivamente rk usando el algoritmo de la división:

rk�2 = rk�1 � qk�1 + rk donde 0 � rk < rk�1.

La desigualdad 0 � rk < rk�1 muestra que la sucesión de residuos rk es una sucesióndecreciente de números naturales. Esto implica que debe aparecer un residuo cero,digamos que, en el paso n-ésimo, cuando rn�1 se divide por rn. Por el lema 2.1,tenemos que

gcd (a, b) = gcd (r0, r1) = gcd (r1, r2) = � � � = gcd (rn�1, rn) = gcd (rn, 0) = rn.

Luego, el algoritmo termina dando como salida rn = gcd (a, b) .Una ejecución típica del algoritmo toma la forma

r0 = r1q1 + r2 0 < r2 < r1

r1 = r2q2 + r3 0 < r3 < r2

r2 = r3q3 + r4 0 < r4 < r3...

...rn�2 = rn�1qn�1 + rn 0 < rn < rn�1

"rn�1 = rnqn + 0 0 = rn+1 < rn.

2.2. Algoritmo de Euclides 29

Ejercicio Calcule gcd (2010, 871) .

Solución Apliquemos el algoritmo de Euclides.

2010 = 871 � 2 + 268

871 = 268 � 3 + 67"

268 = 67 � 4 + 0

Luego, gcd (2010, 871) = 67. �X

La identidad de Bézout afirma que gcd (a, b) se puede expresar en la forma a � s+b � t. Pero, dado que la prueba del teorema no es constructiva, no nos proporcionaninguna sugerencia de cómo determinar los enteros s y t. Sin embargo, podemosusar el algoritmo de Euclides. A partir de la penúltima ecuación que aparece en elalgoritmo, escribimos

gcd (a, b) = rn = rn�2 + rn�1 � (�qn�1) .

Ahora, resolviendo la ecuación previa en el algoritmo para rn�1 y sustituyendo seexpresa gcd (a, b) como combinación lineal de rn�2 y rn�3. Continuando hacia atrás através del sistema de ecuaciones, sucesivamente eliminamos los residuos rn�1, rn�2, rn�3, . . . , r3, r2hasta que alcanzamos un paso donde gcd (a, b) se expresa como combinación linealde r0 = a y r1 = b.

Ejemplo Representemos 67 como combinación lineal de 2010 y 871.

Solución De acuerdo a lo anterior, empezamos con la penúltima ecuación.

67 = 871� 268 � 3 = 871� (2010� 871 � 2) � 3 = 2010 (�3) + 871 � (7)

Luego, 6 = 2010 � s+ 871 � t, donde s = �5 y t = 7. �X

Notemos que si tenemos muchas ecuaciones, el anterior proceso de sustituciónse puede hacer tedioso y díficil de realizar. Sin embargo, es posible ejecutar dichoscálculos con eficiencia.

Proposición 2.1 Considere las siguientes sucesiones definidas por recursión :

s0 = 1 t0 = 0s1 = 0 t1 = 1sk = sk�2 � qk�1 � sk�1 tk = tk�2 � qk�1 � tk�1, para k � 2,

donde qk�1 denota el cociente obtenido en el paso k� 1 del algoritmo de Euclides. Entonces

rk = a � sk + b � tk, 0 � k � n.

Prueba. Usemos inducción completa. El paso base es inmediato:

r0 = a = a � 1+ b � 0 = a � s0 + b � t0 y r1 = b = a � 0+ b � 1 = a � s1 + b � t1.

Para el paso inductivo, supongamos que ri = a � si + b � ti, para i = k � 2, k � 1. Alejecutar el algoritmo de Euclides, tenemos que rk�2 = rk�1 � qk�1 + rk.Aplicando la


hipótesis inductiva:

rk = (a � sk�2 + b � tk�2)� (a � sk�1 + b � tk�1) � qk�1

= a � (sk�2 � sk�1 � qk�1) + b � (tk�2 � qk�1 � tk�1) = a � sk + b � tk.

En particular, gcd (a, b) = asn + btn. �Al ejecutar la versión extendida del algoritmo de Euclides, es preferible evitar es-

cribir tantas ecuaciones y enfocarse en los cálculos numéricos. Los cocientes y resid-uos sastisfacen la recursión

qk = rk�1 div rk y rk = rk�2 mod rk�1,

iniciando con r0 = a y r1 = b. La recursión para los coeficientes sk y tk está dada porla proposición 2.1. La ejecución se puede representar de una forma concisa como loilustra el siguiente ejemplo.

Ejemplo Dados a = 44350 y b = 20785, aplique la versión extendida del algo-ritmo de Euclides para calcular d = gcd (a, b) y expresarlo como combinación linealde a y b.

Solución Los pasos ejecutados se resumen en la siguiente tabla.

k rk qk sk tk

0 44350 1 0

1 20785 2 0 1

2 2780 7 1 �2

3 1325 2 �7 15

4 130 10 15 �32

5 25 5 �157 335

6 5 5 800 �1707"

7 0

Por tanto, gcd (44350, 20785) = 5 = 44350 � (800) + 20785 � (�1707) . �X

Ejercicio Halle enteros x, y tales que 144x+ 89y = 23.

2.2. Algoritmo de Euclides 31

Solución Apliquemos el algoritmo extendido de Euclides.

k rk qk sk tk

0 144 1 01 89 1 0 12 55 1 1 �13 34 1 �1 24 21 1 2 �35 13 1 �3 56 8 1 5 �87 5 1 �8 138 3 1 13 �219 2 1 �21 34

10 1 2 34 �5511 0

Como 1 = gcd (144, 89) = 144 � (34) + 89 � (�55) , podemos multiplicar por 23 aambos lados.

23 = 144 � (34 � 23) + 89 � (�55 � 23) = 144 � (782) + 89 � (�1265) .

�X

En el anterior ejercicio, el algoritmo operó lentamente porque el cociente en todos,excepto el último paso, dio 1. Esto ilustra un hecho interesante sobre la eficiencia delalgoritmo de Euclides. Primero, notemos que

F12 = 144 y F11 = 89

son dos números de Fibonacci consecutivos. Vimos que gcd (144, 89) = 1. En gen-eral, esto siempre se cumple.

Ejercicio Pruebe que gcd (Fn, Fn+1) = 1, para todo n � 1.

Solución Usemos inducción. El paso base es trivial: gcd (F1, F2) = gcd (1, 1) = 1.Para el paso inductivo, supongamos que gcd (Fn, Fn+1) = 1. Sea d = gcd (Fn+1, Fn+2) .Por definición,

Fn = Fn+2 � Fn+1

Por el teorema 2.1 (g), d j Fn. Por tanto, d � gcd (Fn, Fn+1) = 1. Esto es, d = 1. �X

La siguiente proposición nos dice cuántas divisiones toma el algoritmo de Euclidespara hallar que dos números de Fibonacci consecutivos son primos relativos.

Proposición 2.2 Para n > 1, el algoritmo de Euclides ejecuta exactamente n divisionespara mostrar que

gcd (Fn+1, Fn+2) = 1.


Prueba. Aplicando el algoritmo de Euclides y usando la definición recursiva parala sucesión de Fibonacci Fk = Fk�1 + Fk�2, vemos que

Fn+2 = Fn+1 � 1 + Fn

Fn+1 = Fn � 1 + Fn�1...

F4 = F3 � 1 + F2

"F3 = F2 � 2 + 0

Así, se ejecutan exactamente n divisiones para calcular gcd (Fn+1, Fn+2) = F2 = 1.�

La representación de gcd (a, b) como combinación lineal de a y b no es única. Enefecto,

gcd (a, b) = a � s+ b � t = a � s+ b � t+ (a � b� b � a) = a � (s+ b) + b � (t� a) .

Iterando este razonamiento, hallamos infinitos pares de coeficientes de la formaum = s+m � b y vm = t�m � a tales que

gcd (a, b) = a � um + b � vm.

2.3 Números Primos

Definición Un entero p > 1 se denomina un número primo, o simplemente un primo,si sus únicos divisores positivos son 1 y p. Un entero mayor que 1 que no sea un primo sedice que es compuesto.

Los enteros 2, 3, 5, 13, 101 y 163 son primos. Los enteros 4 = 2 � 2, 8 = 4 � 2, 33 =3 � 11, 111 = 3 � 37 y 1001 = 7 � 11 � 13 son compuestos.

Infinitud de los Primos

Lema 2.2 Todo entero positivo mayor que 1 tiene un divisor primo.

Prueba. Razonemos por el absurdo y supongamos que existe un entero mayor que1 que no tiene divisores primos. Por el principio del buen orden, existe un menor en-tero n > 1 que no tiene divisores primos. Como n j n, tenemos que n no es primo.Luego, n = a � b con 1 < a < n y 1 < b < n. Como a < n, entonces a debe tener undivisor primo p. Por el teorema 2.1 (c), p divide a n, absurdo. �

La proposición 20 del Libro IX de los Elementos de Euclides afirma: Hay másnúmeros primos que cualquier cantidad propuesta. En lenguaje moderno, lo anteriorsignifica que hay infinitos primos. Este es uno de los teoremas claves en teoría denúmeros que se puede probar de distintas formas. La siguiente prueba generaliza laprueba de Euclides (él lo demostró para tres primos).

Teorema 2.4 (Euclides) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Existen infinitos números primos.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3. Números Primos 33

Prueba. Supongamos que existen sólo finitos primos p1, p2, . . . , pn, donde n � 1.Consideremos el entero

Qn = (p1 � p2 � � � pn) + 1 =n

∏k=1

pk + 1, n � 1.

Por el lema 2.2, Qn tiene al menos un divisor primo, digamos q. Luego, q = pi, paraalgún i = 1, . . . , n. Por el teorema 2.1 (g), qn divide (Qn � p1 � p2 � � � pn) = 1, lo cuales absurdo. Por tanto, q tiene que ser un primo que no está en la lista dada. Esta con-tradicción muestra que el conjunto de los números primos es infinito. �

La prueba del teorema 2.4 es no constructiva, ya que el entero Qn, definido en laprueba, puede o no ser primo. Por lo tanto, en la prueba no hemos hallado efecti-vamente un nuevo primo, pero sabemos que tiene que existir. Ahora, los tests paradistinguir entre primos y compuestos son de crucial importancia tanto en la teoríacomo en las aplicaciones; dichos tests se denominan tests de primalidad. El test de pri-malidad más básico es la división por ensayo (trial division) que afirma que un númeroes primo si y sólo si no es divisible por los primos que no exceden a

pn.

Proposición 2.3 Si n es compuesto, entonces n tiene un factor primo p �p

n.

Prueba. Dado que n es compuesto, podemos escribir n = a � b, con 1 < a � b < n.Debemos tener que a �

pn, pues, de lo contrario, b � a >

pn y a � b >

pn �p

n = n,absurdo. Luego, por el lema 2.2, a debe tener un divisor primo p. Luego, p tambiénes divisor de n y p � a �

pn. �

El teorema 2.3 da lugar a la criba de Eratóstenes, un procedimiento algorítmicoque produce todos los primos menores o iguales a un entero fijo. Sin embargo, estemétodo es ineficiente para determinar si un número dado es primo, dado que esnecesario verificar la divisibilidad de n por todos los primos que no excedan a

pn.

Por ejemplo, se puede mostrar que determinar si un número de 200 dígitos es primo,usando este método, le puede tomar a los computadores más veloces billones deaños.

En 2002, M. Agrawal, N. Kayal y N. Saxena, un profesor hindú de computacióny dos de sus estudiantes de pregrado, sorprendieron a la comunidad matemática alanunciar que se puede determinar si un entero n es primo usando un algoritmo cuyacomplejidad computacional está acotada por un polinomio en el número de dígitosbinarios en n (o, equivalentemente, en ln n). Lo anterior, significa que existe un testde primalidad que es eficiente (dado que corre en tiempo polinómico). Durante siglos,los matemáticos habían buscado por dicho algoritmo.

Distribución de los Primos

Sabemos que hay infinitos primos, pero ¿podemos estimar cuántos primos hay menoresque un número real positivo x? Esta pregunta se responde con el teorema del NúmeroPrimo, uno de los resultados fundamentales de la teoría de números (y de toda lamatemática). Para enunciarlo, introducimos la siguiente notación: π (x) denota elnúmero de primos � x 2 R+. Por ejemplo, π (10) = 4 y π (100) = 25.

Teorema del Número Primo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

limx!∞

π (x)x/ ln x

= 1.


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

A finales del siglo XVIII, se usaron tablas de primos, creadas mediante cálculos man-uales, para estimar π (x) . En 1798, A. Legendre uso tablas de primos hasta 400, 031para notar que π (x) se podía aproximar por

xln x� 1.08366

.

C. F. Gauss conjeturó que π (x) crece a la misma razón que las funciones

xln x

y Li (x) =Z x

2

dtln t

.

Ni Legendre, ni Gauss pudieron probar que tales funciones se aproximaban a π (x)para grandes valores de x. Hacia 1811, se había producido una tabla de primos hasta1, 020, 000 que proporcionaba evidencia numérica para estas conjeturas.

En 1850, P. L. Chebyshev estableció el primer avance sustancial al probar que ex-isten reales positivos C1 < 1 < C2 tales que

C1 �x

ln x< π (x) < C2 �

xln x

,

para valores de x lo suficientemente grandes (En particular, mostró que el resultadose cumple para C1 = 0.929 y C2 = 1.1). También, demostró que si el cociente de π (x)y x/ ln x se aproxima a un límite, entonces este límite tiene que ser 1.

El Teorema del Número Primo fue finalmente probado en 1896, cuando J. Hadamardy C. J. de la Vallée-Poussin producieron pruebas por separado. Sus pruebas se basa-ban en resultados del análisis complejo. Ellos usaron ideas desarrolladas en 1859 porB. Riemann, quien relaciono π (x) al comportamiento de la función zeta de Riemann

ζ (s) =∞

∑n=1

1ns

en el plano complejo. La conexión viene dada por la identidad de Euler

ζ (s) =∞

∑n=1

1ns = ∏

p prime

11� p�s .

En 1949, A. Selberg y P. Erdös hallaron independientemente pruebas elementales delteorema del Número Primo. Sus pruebas, aunque elementales (significa que no usanla teoría de variable compleja) son bastante complicadas y dificiles.

¿Cuál es la probabilidad que un entero elegido al azar sea primo? Dado que hayaproximadamente x/ ln x primos por debajo de x, la probabilidad de que n sea primoes aproximadamente

n/ ln nn

=1

ln n.

Por ejemplo, la probabilidad de que un entero cercano a 101000 sea primo es aproxi-madamente

1ln 101000 '

12302

' 0.0004344

Suponga que se quiere hallar un primo con 1000 dígitos; ¿cuál es el número esper-ado de enteros que se tienen que elegir antés de hallar un primo? La respuesta es que

2.3. Números Primos 35

se deben seleccionar aproximadamente 1/ (1/2302) = 2302 enteros de este tamañopara que con seguridad uno de ellos sea primo. Por supuesto, será necesario verificarsi cada uno de ellos es primo o no.

Ahora presentamos otros resultados clásicos que nos indican cómo se distribuyenlos primos a lo largo de los enteros positivos. Primero veremos que hay sucesionesarbitrariamente largas de enteros consecutivos que no contienen primos.

Proposición 2.4 Para todo entero positivo n, hay al menos n enteros positivos compuestosconsecutivos.

Prueba. Considere los n enteros positivos consecutivos:

(n+ 1)!+ 2, (n+ 1)!+ 3, (n+ 1)!+ 4, . . . (n+ 1)!+ n+ 1.

Cuando 2 � k � n + 1, vemos que k j (n+ 1)!. Por tanto, k divide a (n+ 1)! + k.Luego, estos n enteros consecutivos son compuestos. �La anterior proposición muestra que la brecha entre dos primos consecutivos puedeser arbitrariamente larga. Sin embargo, muchos primos difieren en dos; estos paresde primos se llaman primos gemelos. Ejemplos son los pares 3 y 5, 5 y 7, 11 y 13, 101y 103, y 4967 y 4969. La evidencia numérica parece indicar que hay infinitos paresde primos gemelos (hay 1, 870, 525, 220 pares menores que 1012). Esto ha llevado a lasiguiente conjetura.

Conjetura de los Primos Gemelos Existen infinitos pares de primos p y p+ 2.

En 1845, J. Bertrand conjeturó que para todo entero n > 1, siempre existe un primo ptal que n < p < 2n. Bertrand verificó esta conjetura para n � 3, 000, 000, pero nopudo probarla. En 1852, Chebyshev probó esta afirmación, la cual actualmente seconoce como Postulado de Bertrand.

Todo entero impar es de la forma 4n + 1 o de la forma 4n + 3. ¿Hay infinitos pri-mos que sean de ambas formas? Los primos 5, 13, 17, 29, 37, 41, . . . son de la forma4n+ 1 y los primos 3, 7, 11, 19, 23, 43, . . . son de la forma 4n+ 3. La anterior evidenciasugiere que hay infinitos primos en ambas progresiones. ¿Qué decir de otras progre-siones aritméticas tales como 3n+ 1, 7n+ 4, 8n+ 5, etc? ¿Cada una de estas contieneninfinitos primos? G. L. Dirichlet resolvio esta pregunta en 1837, cuando usó métodosdel análisis complejo para probar el siguiente teorema.

Teorema de Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Si gcd (a, b) = 1, entonces la progresión aritmética a+ nb, n � 1, contiene infinitos primos.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

No se conoce una prueba sencilla del teorema de Dirichlet. En 1950, Selberg ofreciouna prueba elemental (sin variable compleja), pero complicada. Sin embargo, casosespeciales del teorema de Dirichlet se pueden probar con facilidad. En la siguientesección, ilustraremos esto al mostrar que existen infinitos primos de la forma 4n+ 3.


2.4 Teorema Fundamental de la Aritmética

El resultado principal de esta sección es una de las piedras angulares de la teoría denúmeros. Este teorema muestra que los primos son los bloques multiplicativos conlos que se construyen los enteros. Inicialmente, necesitamos unas consecuencias in-mediatas del lema de Euclides.

Corolario 2.4 Sea p un primo.

(a) Si p j ab, entonces p j a o p j b.

(b) Si p j a1a2 � � � an, entonces p j ak, para algún k, donde 1 � k � n.

(c) Si q1, q2, . . . , qn son todos primos y p j q1q2 � � � qn, entonces p = qk, para algún k,donde 1 � k � n.

Prueba. (a) Si p j a, entonces no hay nada que probar. Supongamos que p - a.Como p es primo, esto implica que gcd (p, a) = 1. Por el lema de Euclides, se sigueque p j b.

(b) Use inducción sobre n.

(c) Por (2), sabemos que p j qk, para algún k = 1, . . . , n. Dado que qk es primo yp > 1, estamos forzados a concluir que p = qk. �Teorema Fundamental de la Aritmética . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Todo entero positivo n > 1 se puede expresar como producto de primos; esta representaciónes única, excepto por el orden en que aparecen los factores.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. (Existencia) Razonemos por el absurdo y supongamos que existe un en-tero mayor que 1 que no se puede expresar como producto de primos. Por el prin-cipio del buen orden, existe un menor entero n > 1 que no se puede expresar comoproducto de primos. Si n es primo, obviamente n es producto de primos, a saber unproducto con un solo factor primo n. Luego, n debe ser compuesto. Sea n = a � bcon 1 < a < n y 1 < b < n. Dado que a y b son menores que n, entonces a y b sonproductos de primos. Por tanto, n = ab también se puede expresar como productode primos. Esta contradicción muestra que todo entero positivo se puede expresarcomo producto de primos.

(Unicidad) Supongamos que n se puede expresar como producto de primos en dosformas; digamos que

n = p1 p2 � � � pr = q1q2 � � � qs,

donde pi y qj son todos primos, escritos en orden de magnitud creciente, de formaque

p1 � p2 � � � � � pr y q1 � q2 � � � � � qs.

Dado que p1 j q1q2 � � � qs, por el corolario anterior, podemos afirmar que p1 = qkpara algún k. Luego, q1 � qk = p1. Un razonamiento análogo muestra que p1 � q1.Así, p1 = q1. Podemos cancelar este factor común y obtener

p2 p3 � � � pr = q2q3 � � � qs.

2.4. Teorema Fundamental de la Aritmética 37

Ahora repetimos el proceso para obtener que p2 = q2 y, a su vez,

p3 p4 � � � pr = q3q4 � � � qs.

Continuamos de esta manera. Si la desigualdad r < s se cumpliese, eventualmentellegariamos a que

1 = qr+1qr+2 � � � qs,

lo cual es absurdo (dado que cada qj > 1). Luego, r = s y

p1 = q1, p2 = q2, . . . , pr = qr.

Por lo cual, la factorización en primos de n es única. �Por supuesto, varios de los primos que aparecen en la factorización de un entero

positivo dado se puede repetir como en el caso de 958 320 = 2 � 2 � 2 � 2 � 3 � 3 � 5 � 11 �11 � 11. Al reunir los primos que se repiten en un único factor, podemos reenunciarel teorema fundamental de la siguiente forma.

Corolario 2.5 Cualquier entero n > 1 se puede escribir de forma única en una representacioncanonica

n = pk11 � p

k22 � � � p

krr ,

donde, para cada i = 1, 2, . . . , r, cada ki es un entero positivo y cada pi es un primo con

p1 < p2 < � � � < pr.

Para ilustrar: la forma canónica de 958 320 es 958 320 = 24 � 32 � 51 � 113. Comoejemplos adicionales, citamos

59 168 = 25 � 432 y 131 675 625 = 36 � 54 � 172.

El teorema fundamental de la aritmética no se debe tomar a la ligera, porque ex-isten sistemas numéricos en que la factorización en “primos” no es única. Quizásel ejemplo más elemental es el conjunto E = f2k j k 2 Z+g . Aceptemos llamarun entero par un e-primo si no es el producto de otros enteros pares. Por tanto,2, 6, 10, 14, 18, 20, 22 . . . son todos e-primos, mientras que 4, 8, 12, 16, 24, 28 no lo son.No es difícil ver que el entero par 60 se puede factorizar en e-primos en dos formasdistintas; a saber,

60 = 2 � 30 = 6 � 10.

Parte del problema surge del hecho que el corolario 1 no se cumple en E : 6 j 2 � 30,pero 6 - 2 y 6 - 30 (ver también el ejercicio sobre primos de Hilbert).

Ejercicio ¿Cuántos ceros hay al final de 100!?

Solución Hay que contar cuántas potencias de 10 hay en 100!. Por un ejemploanterior,

hayj

1002

k= 50 enteros � 100 divisibles por 2.

Luego, el exponente de 2 en la factorización de 100! es al menos 50 (de hecho es 97).

Por otro lado,

hayj

1005

k= 20 enteros � 100 divisibles por 5.


Luego, el exponente de 5 en la factorización de 100! es al menos 20. Ahora, hay exac-tamente

j10025

k= 4 enteros � 100 divisibles por 25 :

25 = 52, 50 = 2 � 52, 75 = 3 � 52 y 100 = 4 � 52.

Por tanto, el exponente de 5 en la factorización de 100! es exactamente 20+ 4 = 24.

Luego, hay 24 ceros al final de la expansión decimal de 100!. �X

Como una aplicación del teorema fundamental de la aritmética, mostraremos elsiguiente caso especial del teorema de Dirichlet.

Proposición 2.5 Existen infinitos primos de la forma 4n+ 3.

Necesitamos un resultado preliminar.

Lema 2.3 Si a y b son enteros de la forma 4n+ 1, entonces el producto a � b también es deesa forma.

Prueba. Supongamos que a = 4r+ 1 y b = 4s+ 1, donde r, s 2 Z. Luego,

a � b = (4r+ 1) (4s+ 1) = 16rs+ 4r+ 4s+ 1 = 4 (4rs+ r+ s) + 1,

que es de nuevo de la forma 4n+ 1. �Ahora probemos la proposición 2.5.

Prueba. Supongamos que sólo existe un número finito de primos de la forma 4n+3, digamos que p0 = 3, p1, p2, . . . , pr. Sea

Q = 4p1 p2 � � � pr + 3.

Entonces, existe al menos un primo q de la forma 4n+ 3 en la factorización de Q. Delo contrario, todos los primos en la factorización de Q serían de la forma 4n+ 1 y, porel lema 2.3, esto implicaría que Q sería de la forma 4n+ 1, lo cual es contradictorio.

Sin embargo, ninguno de los primos p0, p1, . . . , pr divide Q. El primo 3 no dividea Q, porque si 3 j Q, entonces 3 j (Q� 3) = 4p1 p2 � � � pr, absurdo. De igual modo,ninguno de los primos pk divide a Q, por que si pk j Q, tendríamos que pk j (Q� 4p1 p2 � � � pr) =3, lo cual es imposible.

Luego, existen infinitos primos de la forma 4n+ 3. �

Ejercicios

1. ¿Cuáles son el cociente y el residuo cuando

(a) 777 se divide por 21? (b) �1 se divide por 23? (c) �2010 se divide por 87?

2. Evalue esta cantidades.

(a) �17 mod 2 (b) 144 mod 7 (c) �101 mod 13 (d) 199 mod 9

(e) 13 mod 3 (f) �97 mod 11 (g) 155 mod 9 (h) �221 mod 23


3. Muestre que cualquier entero de la forma 6k+ 5 también es de la forma 3j+ 2,pero no al contrario.

4. Use el Algoritmo de la División para establecer lo siguiente:

(a) El cuadrado de cualquier entero es de la forma 3k o 3k+ 1.

(b) El cubo de cualquier entero tiene una de las formas: 9k, 9k+ 1 o 9k+ 8.

(c) La cuarta potencia de cualquier entero es de la forma 5k o 5k+ 1.

5. Pruebe que 3a2 � 1 nunca es un cuadrado perfecto [Sug: Problema 2(a)].

6. Pruebe que el cubo de cualquier entero es de la forma 7k o 7k� 1.

7. Pruebe que ningún entero en la siguiente sucesión es un cuadrado perfecto:

11, 111, 1111, 11111, 111111, . . .

[Sug: Un término típico 111 � � � 1111 se puede escribir como

111 � � � 1111 = 111 � � � 1108+ 3 = 4k+ 3].

8. Verifique si un entero es simultaneamente un cuadrado y un cubo, entoncestiene que ser de la forma 7k o 7k+ 1 (p.e. 64 = 82 = 43).

9. Para n � 1, establezca que el entero n�7n2 + 5

�es de la forma 6k.

10. Si n es un entero impar, muestre que n4 + 4n2 + 11 es de la forma 16k.

11. Si a j b, entonces (�a) j b, a j (�b) y (�a) j (�b) .

12. Dados enteros a, b, c, d, pruebe lo siguiente:

(a) Si a j b, entonces a j bc. (b) Si a j b y a j c, entonces a2 j bc.

(c) a j b si y sólo si ac j bc, donde c 6= 0 (d) Si a j b y c j d, entonces ac j bd.

13. Pruebe o refute: Si a j (b+ c) , entonces o a j b o a j c.

14. Para n � 1, use inducción matemática para establecer cada uno de los sigu-ientes enunciados de divisibilidad:

(a) 8 j�52n + 7

�. (b) 15 j

�24n � 1

�. (c) 5 j

�33n+1 + 2n+1� .

Sug. para (a): 52(k+1) + 7 = 52(52k + 7) +�7� 52 � 7

�.

15. Pruebe que para cualquier entero a, uno de los enteros a, a+ 2, a+ 4 es divisiblepor 3.

16. Para un entero arbitrario a, verifique lo siguiente:

(a) 2 j a (a+ 1) y 3 j a (a+ 1) (a+ 2) . (b) 3 j a�2a2 + 7

�.

(c) Si a es impar, entonces 32 j�a2 + 3

� �a2 + 7

�.

17. Pruebe que si a y b son ambos enteros impares, entonces 16 j a4 + b4 � 2.


18. Establezca que la diferencia de dos cubos consecutivos nunca es divisible por2.

19. Para a 6= 0, muestre que gcd (a, 0) = jaj , gcd (a, a) = jaj y gcd (a, 1) = 1.

20. Si a y b son enteros, no ambos cero, muestre que

gcd (a, b) = gcd (�a, b) = gcd (a,�b) = gcd (�a,�b) .

21. Pruebe que, para todo entero positivo n y todo entero a : gcd (a, a+ n) dividea n. Luego, gcd (a, a+ 1) = 1.

22. Dados enteros a y b, pruebe lo siguiente:

(a) Existen enteros x y y para los cuales c = ax+ by si y sólo si gcd (a, b) j c.

(b) Si existen enteros x y y para los cuales ax + by = gcd (a, b) , entoncesgcd (x, y) = 1.

23. Para cualquier entero a, muestre que gcd (2a+ 1, 9a+ 4) = 1 y gcd (5a+ 2, 7a+ 3) =1.

24. Pruebe que si a es impar, entonces gcd (3a, 3a+ 2) = 1.

25. Pruebe que la expresión (3n)!/ (3!)n es un entero para todo n � 0.

26. Suponga que gcd (a, b) = 1. Demuestre las siguientes afirmaciones.

(a) Si c j a, entonces gcd (b, c) = 1.

(b) Si c j a+ b, entonces gcd (a, c) = gcd (b, c) = 1.

(c) Si d j ac y d j bc, entonces d j c.

27. Pruebe: El producto de tres enteros consecutivos es divisible por 6; el productode cuatro enteros consecutivos es divisible por 24; el producto de cinco enterosconsecutivos es divisible por 120.[Sug. Use el corolario (a)].

28. (a) Pruebe que si d j n, entonces 2d � 1 j 2n � 1 [Sug. Use la identidad

xk � 1 = (x� 1)�

xk�1 + xk�2 + � � �+ x+ 1�].

(b) Verifique que 235 � 1 es divisible por 31 y 127.

29. Use el algoritmo extendido de Euclides para hallar gcd (a, b) y expresarlo comocombinación lineal de a y b.

(a) a = 56, b = 72 (b) a = 102, b = 222 (c) a = 1769, b = 2378

(d) a = 272, b = 1479 (e) a = 306, b = 657 (f) a = 20785, b = 44350

(g) a = 143, b = 227 (h) a = 119, b = 272 (i) a = 214 149, b = 19 635

30. Pruebe que si k > 0, entonces gcd (ka, kb) = gcd (a, b) .


31. Pruebe que si d es divisor común de a y b, entonces d = gcd (a, b) si y sólo sigcd (a/d, b/d) = 1.

32. Suponiendo que gcd (a, b) = 1, pruebe que

(a) gcd (a+ b, a� b) = 1 o 2. [Sug. Sea d = gcd (a+ b, a� b) y muestred j 2a, d j 2b, y, por tanto, d � gcd (2a, 2b) = 2 gcd (a, b)].

(b) gcd (2a+ b, a+ 2b) = 1 o 3.

(c) gcd�a+ b, a2 + b2� = 1 o 2. [Sug. a2 + b2 = (a+ b) (a� b) + 2b2].

(d) gcd�a+ b, a2 � ab+ b2� = 1 o 3. [Sug. a2 � ab+ b2 = (a+ b)2 � 3ab].

33. Pruebe que si gcd (a, b) = 1, entonces gcd (a+ b, ab) = 1.

34. Sea p un primo. Si gcd�a, p2� = p y gcd

�b, p3� = p2, entonces gcd

�ab, p4� y

gcd�a+ b, p4� .

35. Muestre que ningún entero de la forma n3 + 1 es primo, excepto 2 = 13 + 1.

36. Muestre que si a y n son enteros positivos con n > 1 y an� 1 es primo, entoncesa = 2 y n es primo. [Sug: use la identidad akl�1 =

�ak � 1

� �ak(l�1) + � � �+ ak + 1

�].

37. [Este ejercicio construye otra prueba de la infinitud de los primos]. Muestreque el entero Qn = n!+ 1, donde n � 1, tiene un divisor primo mayor que n.Concluya que existen infinitos primos.

38. Usando la prueba de Euclides del teorema 2.4, muestre que el n-ésimo primopn � 22n�1

, donde n � 1. Concluya que existen al menos n+ 1 primos menoresque 22n

, para n � 1.

39. Suponga que p es el menor factor primo de un entero n. Pruebe que si p >pn/p, entonces n/p es primo.

40. Muestre que si el menor factor primo p del entero positivo n excede 3p

n, en-tonces n/p tiene que ser primo o 1.

41. Muestre que si p es un primo en la progresión aritmética 3n+ 1, n � 1, entoncestambién está en la progresión aritmética 6n+ 1, n � 1.

42. Halle el menor primo en la progresión aritmética a+ nb, donde

(a) a = 3, b = 1. (b) a = 5, b = 1. (c) a = 5, b = 4. (d) a = 7, b = 2.

43. Muestre que 2n2+ 11 es primo para todo entero 0 � n � 10, pero es compuestopara n = 11.

44. Halle los menores cinco enteros consecutivos compuestos.

45. Muestre que no existen tripletas de primos, esto es, primos p, p+ 2 y p+ 4, ex-cepto 3, 5 y 7.

46. Halle el menor primo entre n y 2n, cuando n = 3, 5, 6, 19, 31, 47.

47. Use el Postulado de Bertrand, para mostrar que si pn es el n-ésimo primo, en-tonces pn � 2n.


48. Si p � 5 es un número primo, muestre que p2 + 2 es compuesto.

49. Establezca cada uno de los siguientes enunciados.

(a) Todo entero de la forma n4 + 4, con n > 1, es compuesto.[Sug: Escriba n4 + 4 como el producto de dos factores cuadráticos].

(b) Si n > 4 es compuesto, entonces n divide a (n� 1)!.

(c) Todo entero de la forma 8n + 1, con n � 1, es compuesto.[Sug: 2n + 1 j 23n + 1].

(d) Todo entero n > 11 se puede escribir como la suma de dos enteros com-puestos.[Sug: Si n es par, digamos n = 2k, entonces n � 6 = 2 (k� 3) ; para nimpar, considere el entero n� 9].

50. Halle todos los primos que dividen a 50!.

51. Si p � q � 5 y p y q son ambos primos, entonces 24 j p2 � q2.

52. Si p 6= 5 es un primo impar, pruebe que 10 divide a p2 � 1 o a p2 + 1.

53. Si n > 1 es un entero que no es de la forma 6k + 3, pruebe que n2 + 2n escompuesto.[Sug: Muestre que 2 o 3 divide a n2 + 2n].

54. Pruebe que un entero positivo a > 1 es un cuadrado si y sólo si en la formacanónica de a todos los exponentes de los primos son enteros pares.

55. Un entero se dice que es libre de cuadrados si no es divisible por el cuadradode algún entero mayor que 1. Pruebe lo siguiente

(a) Un entero n > 1 es libre de cuadrados si y sólo si n se puede factorizarcomo producto de primos distintos.

(b) Todo entero n > 1 es el producto de un entero libre de cuadrado y uncuadrado perfecto.[Sug: Si n = pk1

1 pk22 � � � p

kss es la factorización canónica de n, entonces es-

criba ki = 2qi + ri, donde ri = 0 o 1, de acuerdo a que ki sea par o impar].

56. Verifique que todo entero se puede escribir en la forma n = 2km, donde k � 0y m es un entero impar.

57. Este problema presenta otro ejemplo de un sistema numérico donde la factor-ización única en primos falla. Sea H = f4k+ 1 j k 2 Z+g . Note que,por ellema 2.3, el producto de dos elementos de H también está en H.

(a) Un elemento h 6= 1 en H se denomina un primo de Hilbert si la únicaforma de factorizarlo como el producto de dos enteros de H es h = 1 � h =h � 1. Halle los primeros 10 primos de Hilbert.

(b) Muestre que todo entero en H se puede factorizar en primos de Hilbert.

(c) Muestre que la factorización de elementos de H en primos de Hilbert noes necesariamente única al hallar dos factorizaciones distintas de 693 (= 173 � 4+ 1)en primos de Hilbert.


58. Muestre que existen infinitos primos de la forma 6n+ 5.

59. (a) Si p es un primo y p - b, entonces que en la progresión aritmética

a, a+ b, a+ 2b, a+ 3b, . . .

todo término p-ésimo es divisible por p.[Sug: Dado que gcd (p, b) = 1, existen enteros r, s tales que pr+ bs = 1. Hagank = kp� as, para k = 1, 2, . . . y muestre que p j (a+ nkb)].

(b) De la parte (a), concluya que si b es un entero impar, entonces todo cualquierotro término en la progresión indicada es par.

60. (a) Para cualquier entero k > 0, establezca que la progresión aritmética

a, a+ b, a+ 2b, a+ 3b, . . . ,

donde gcd (a, b) = 1, contiene k términos consecutivos que son compuestos.[Sug: Haga n = (a+ b) (a+ 2b) � � � (a+ kb) y considere los k términos

a+ (n+ 1) b, a+ (n+ 2) b, . . . , a+ (n+ k) b].

(b) Halle cinco enteros consecutivos en la progresión aritmética

6, 11, 16, 21, 26, 31, 36, . . . .


3

Congruencias

3.1 Aritmética Modular

En la sección inicial de su famoso libro Disquisitiones Aritmeticae (1799), Gauss intro-dujo su concepto de congruencia:

“Si un número n mide la diferencia entre dos números a y b, entonces a yb se dice que son congruentes relativos a n; si no, a y b son incongruentes.El número se llama el módulo”

Al trabajar con congruencias, Gauss sólo se interesó en el residuo obtenido cuandoun entero se divide por otro. La notación de congruencia que él introdujo hace mu-cho más fácil tanto formular resultados sobre las propiedades de la divisibilidadcomo ejecutar cálculos correspondientes. La noción de congruencia es fundamentalen la teoría de números moderna, pero las ideas subyacentes preceden a los aportesde Gauss por varios siglos.

Definición Sea n > 1 fijo. Dados a, b 2 Z, definimos

a � b (mod n) sii n j (a� b) sii a� b = k � n, para algún entero k.

y decimos que a es congruente a b módulo n. Cuando a no es congruente a b módulon, escribimos a 6� b (mod n) .

Ejemplo Verifique que

8 � 0 (mod 2) , �458 � 10 (mod 13) y 25 6� 5 (mod 7) .

Solución Es inmediato que

8� 0 = 2 � 4 y � 458� 10 = �468 = 13 � (�36)

Por último, 25� 5 = 20 no es divisible por 7. �X

Es muy útil concebir la relación de congruencia términos de los residuos positivosal realizarse la división por el módulo.

Teorema 3.1 Sean a, b enteros arbitrarios y n > 0 fijo. Los siguientes enunciados son equiv-alentes

(a) a � b (mod n) . (b) a = b+ k � n, para algún k 2 Z. (c) a mod n = b mod n.

Prueba. Es inmediato que (a)$ (b).

46 3. Congruencias

(b) ! (c) Supongamos que existe k 2 Z : a = b + k � n. Por el algoritmo de ladivisión, existen únicos q, r tales que

b = q � n+ r y 0 � r < n.

Luego,a = (q+ k) � n+ r y 0 � r < n.

Por unicidad, a tiene el mismo residuo r que b al ser divididos por n.

(c)! (a) Si a mod n = b mod n = r, entonces

a = q1 � n+ r y b = q2 � n+ r,

donde q1, q2 2 Z. Luego,

a� b = q1 � n+ r� q2 � n� r = (q1 � q2) � n.

Luego, n j a� b. Esto es, a � b (mod n) . �El siguiente teorema recoge algunas de las propiedades elementales de la relación

de congruencia.

Teorema 3.2 Sean n > 1 fijo y a, b, c y d enteros arbitrarios. Entonces las siguientespropiedades se cumplen

(a) a � a (mod n) . (b) Si a � b (mod n) , entonces b � a (mod n) .

(c) Si a � b (mod n) y b � c (mod n) , entonces a � c (mod n) .

(d) Si a � b (mod n) y c � d (mod n) , a+ c � b+ d (mod n) y a � c � b � d (mod n) .

(e) Si a � b (mod n) , entonces a+ c � b+ c (mod n) y a � c � b � c (mod n) .

(f) Si a � b (mod n) , entonces ak � bk (mod n) , para todo k � 1.

Prueba. (a) y (b) son obvias.

(c) Supongamos que a = b+ k � n y b = c+ j � n, para k, j 2 Z. Luego,

a = b+ k � n = (c+ j � n) + k � n = c+ (k+ j) � n.

Esto es, a � c (mod n) .

(d) Supongamos que a = b+ k � n y c = d+ j � n, para k, j 2 Z. Luego,

a+ c = (b+ d) + (k+ j) � n y a � c = b � d+ (bj+ kd+ kjn) � n.

Luego, a+ c � b+ d (mod n) y a � c � b � d (mod n) .

(e) se sigue de (d) al tomar c � c (mod n) , por (a).

(f) Usemos inducción sobre k. �Las afirmaciones (a), (b) y (c) del teorema 3.2 muestran que la congruencia módulo

n es una relación de equivalencia en Z. Si a 2 Z, la clase de equivalencia de a, denotadapor

a = fb 2 Z j a � b (mod n)g = fa+ kn j k 2 Zg ,

3.1. Aritmética Modular 47

se denomina la clase de congruencia de a módulo n. Notemos que a es el conjuntode todos los enteros que dejan el mismo residuo que a al ser divididos por n; deallí, que a también se denomine la clase residual de a módulo n. Hay exactamente nclases de congruencia módulo n.

Definición El conjunto de clases de congruencia módulo n se denomina el anillo de en-teros módulo n y se denota por Z/nZ o por Zn.

Podemos definir, de forma natural, la suma y el producto en Z/nZ :

a�n b := a+ b y a�n b := a � b.

Aplicando el teorema 3.2, es directo mostrar que estas operaciones no dependen delos representantes tomados de las clases de congruencia y que satisfacen las propiedadesusuales de la suma y el producto en Z. En particular, los neutros estás dados por

0 = fk � n j k 2 Zg y 1 = fk � n+ 1 j k 2 Zg ,

y el inverso aditivo por �a = �a. Bajo las operaciones dadas,

Z/nZ es un anillo conmutativo con unidad.

Ejemplo Las siguientes tablas dan explícitamente la suma y el producto en Z/3Z.

Suma Producto

�3 0 1 2 �3 0 1 2

0 0 1 2 0 0 0 0

1 1 2 0 1 0 1 2

2 2 0 1 2 0 2 1

Por comodidad, las barras se omiten. El lector puede exhibir tablas similares paran = 4, 5 y 6. �X

Corolario 3.1 Seap (x) = cmxm + � � �+ c1x+ c0 2 Z [x]

un polinomio con coeficientes enteros. Si a � b (mod n) , entonces p (a) � p (b) (mod n) .

Prueba. Supongamos que a � b (mod n) . Aplicando la parte (f) del teorema 3.2,tenemos que ak � bk (mod n) , para 0 � k � m. Por consiguiente,

ckak � ckbk (mod n) , para todo 0 � k � m.

48 3. Congruencias

Sumando estas m+ 1 congruencias, concluimos que

p (a) = cmam + � � �+ c1a+ c0 � cmbm + � � �+ c1b+ c0 = p (b) (mod n) .

�Ilustremos la utilidad de las congruencias para llevar a cabo ciertas pruebas y cál-

culos.

Ejemplo Muestre que 41 divide a 220 � 1.

Solución Comencemos por notar que 25 = 32 � �9 (mod 41) . Luego,

220 = (25)4 � (�9)4 = 81 � 81 � (�1) � (�1) = 1 (mod 41) .

Por tanto, 41 divide a 220 � 1. �X

Ejercicio Halle el residuo obtenido al dividir n por 12, donde

n = 1!+ 2!+ 3!+ 4!+ � � �+ 99!+ 100!

Solución Lo primero que debemos observar es que 4! = 24 � 0 (mod 12) . Portanto, para todo k � 4 :

k! = 4!� 5� 6� � � � � k � 0� 5� 6� � � � � k � 0 (mod 12) .

Luego,

1!+ 2!+ 3!+ 4!+ � � �+ 100! � 1!+ 2!+ 3!+ 0+ � � �+ 0 � 1+ 2+ 6 = 9 (mod 12) .

Por consiguiente, el residuo al dividir n por 12 es 9. �X

Ejemplo Pruebe que si el entero a no es divisible por 2 o 3, entonces a2 � 1 (mod 24) .

Solución notemos que 24 = 22 � 3. Como a no es divisible por 2, entonces a �1, 3, 5, 7 mod 8. Por tanto,

a2 � 1, 9, 25, 49 � 1 (mod 8) .

Como a no es divisible por 3, a � 1, 2 mod 8. Por tanto,

a2 � 1, 4 � 1 (mod 3) .

Por definición, existen q1, q2 2 Z tales que

3 � q1 = a2 � 1 = 8 � q2.

Luego, 3 j 8 � q2. Como gcd (3, 8) = 1, por el lema de Euclides, 3 j q2. Por tanto,q2 = 3 � k, para cierto k 2 Z. Por tanto,

a2 � 1 = 8 � q2 = 8 � (3 � k) = 24 � k.

Esto es, a � 1 mod 24. �X

Ejemplo Pruebe que ningún primo de la forma 4n+ 3 es suma de dos cuadrados.

3.1. Aritmética Modular 49

Solución Sea p un primo de la forma 4n + 3. Razonemos por el absurdo ysupongamos que p = a2 + b2, con a, b 2 Z. Dado que p es impar, uno de los cuadra-dos, digamos que, a2 tiene que ser impar y, luego, b2 tiene que ser par. Entonces, atiene que ser impar y b par. Así, existen m, n 2 Z tales que a = 2m+ 1 y b = 2n. Portanto,

p = (2m+ 1)2 + (2b)2 = 4�

m2 + n2 +m�+ 1 � 1 (mod 4) .

Absurdo, pues p � 3 mod 4. �X

Ejercicio Halle el residuo cuando 3247 se dividide por 17.

Solución Notemos que 33 = 27 � 10 y 34 = 81 � 13 mod 17. Tomandocuadrados a ambos lados, tenemos que

38 � 132 = 169 � 16 (mod 17) .

Elevando de nuevo al cuadrado:

316 � 162 = 256 � 1 (mod 17) .

Aplicando división entera (247 = 16 � 15+ 7) y leyes de exponentes, se tiene que

3247 =�

316�15� 37 � 115 � 37 = 37 = 33 � 34 � 10 � 13 = 130 � 11 (mod 17) .

Luego, el residuo al dividir 3247 por 17 es 11. �X

Ejemplo Muestre que el polinomio p (x) = x2 � 117x+ 31 no tiene raíces enteras.

Solución Supongamos, por el contrario, que existe a 2 Z tal que p (a) = 0.Luego, p (a) � 0 (mod 2) . Ahora, si a � 0 (mod 2) , entonces, por el corolario 3.1,se tiene que

31 = p (0) � p (a) = 0 (mod 2) , absurdo.

Por otro lado, si a � 1 (mod 2) , entonces, por el mismo corolario,

�85 = 1� 117+ 31 = p (1) � p (a) = 0 (mod 2) , absurdo.

Por tanto, no es posible que el polinomio p (x) tenga raíces enteras. �X

El anterior ejemplo se puede generalizar del siguiente modo.

Proposición 3.1 Sea

p (x) = cmxm + � � �+ c1x+ c0 2 Z [x]

Sip (0) � p (1) � 1 (mod 2) ,

entonces p (x) no tiene raíces enteras.

Por último, cabe mencionar que, en general, hay ciertas propiedades aritméticasde Z que no se cumplen módulo n.

En el teorema 3.2, vimos que si a � b (mod n) , entonces ac � bc (mod n) , para

50 3. Congruencias

cualquier entero c. Sin embargo, el recíproco no se cumple en general. Por ejemplo, note-mos que 2 � 4 = 8 � 2 = 2 � 1 (mod 6) , mientras que 4 6� 1 (mod 6) . Así, nosiempre es posible cancelar un factor común sin alterar la congruencia. El siguienteteorema nos muestra que es posible cancelar un factor en una congruencia al alterardebidamente el módulo.

Teorema 3.3 Sea d = gcd (c, n) . Si c � a � c � b (mod n) , entonces a � b (mod n/d) .

Prueba. Por hipótesis, c � (a� b) = n � k, para algún entero k. Por el corolario 2.2,existen enteros q1, q2 tales que

c = d � q1, n = d � q2 y gcd (q1, q2) = 1.

Sustituyendo en c � (a� b) = n � k :

(d � q1) � (a� b) = (d � q2) � k ) q1 � (a� b) = q2 � k.

Luego, q2 j q1 � (a� b) . Por el lema de Euclides, q2 j (a� b) . Esto es, a � b (mod n/d) .�

Corolario 3.2 Supongamos que c � a � c � b (mod n) .

(a) Si gcd (c, n) = 1, entonces a � b (mod n) .

(b) Si n es primo y n - c, entonces a � b (mod n) .

El producto de dos enteros, ninguno de los cuales es congruente a cero, puede resultarcongruente a cero. Por ejemplo, 4 � 3 = 12 � 0 (mod 6) , pero 4 6� 0 (mod 6) y 3 6�0 (mod 6) . Notemos que, por el lema de Euclides, se tiene que si a � b � 0 (mod n)y gcd (a, n) = 1, entonces b � 0 (mod n) . En particular, la siguiente situación esfundamental.

Teorema 3.4 n > 1 es un número primo si y sólo si

Para todo a, b : si a � b � 0 (mod n) , entonces a � 0 (mod n) o b � 0 (mod n) .

Prueba. (!) Esta implicación es una reformulación del corolario 2.4 (a).

( ) Supongamos que n satisface la propiedad. Razonemos por el absurdo, si n fuesecompuesto, habrían enteros a, b tales que

n = a � b y 1 < a � b < p.

Luego, a � b = n � 0 (mod n) . Por hipótesis, a � 0 (mod n) o b � 0 (mod n) . Dadoque a � b < p, se tendría que a = b = 0, absurdo. Por tanto, p tiene que ser primo.�

En términos algebraicos, el teorema 3.4 se puede enunciar como

Z/nZ es un dominio entero si y sólo si n es primo.

3.2. Teorema Chino del Residuo 51

3.2 Teorema Chino del Residuo

Una ecuación de la forma ax � b (mod n) se llama una congruencia lineal, y poruna solución de dicha ecuación entendemos un entero s para el cual as � b (mod n) .Es obvio que si s es una solución y s � s0 (mod n) , entonces s0 también es solución.

Es conveniente considerar dos soluciones de ax � b (mod n) que son conguentesmódulo n como la misma (aunque sean diferentes en el sentido usual). Por ejem-plo, x = 18 y x = �12 satisfacen ambas la congruencia 6x � 3 (mod 15) ; dadoque 18 � �12 (mod 15) , no las contamos como soluciones diferentes. Resumiendo,cuando nos referimos al número de soluciones de ax � b (mod n) , queremos decirel número de enteros no congruentes que satisfacen la congruencia.

El siguiente resultado da una caracterización de las congruencias que tiene solu-ción , así como una completa descripción de las soluciones.

Teorema 3.5 Sea d = gcd (a, n) . Entonces

la congruencia lineal ax � b (mod n) tiene una solución si y sólo si d j b.

Si d j b, hay exactamente d soluciones no congruentes módulo n. Si s0 es una solución,entonces las otras soluciones están dadas por

sk = s0 + k � (n/d) , 0 � k � d� 1.

Prueba. Si s0 es una solución, entonces a � s0 � b = n � q0 para algún entero q0. Portanto, b = a � s0 + n � q0. Por el teorema 2.1 (g), d j b.

Recíprocamente, supongamos que d j b. Luego, b = d � q1 para cierto q1. Por laidentidad de Bezout, existen s, t tales que a � s + n � t = d. Multiplicando por q1 seobtiene que

b = a � (s � q1) + n � (t � q1) � a � (s � q1) (mod n) .

Luego, s0 := s � q1 es solución de la congruencia.

Sea sk = s0 + k � (n/d) , donde 0 � k � d� 1. Entonces

a � sk = a � s0 + k � (a/d) � n � a � s0 � b (mod n) .

Así, todo número de la forma s0 + k � (n/d) es solución.

Supongamos que s0 + k1 (n/d) � s0 + k2 (n/d) (mod n) , donde 0 � k1 < k2 �d� 1. Luego, k1 � (n/d) � k2 � (n/d) (mod n) . Notemos que gcd (n, n/d) = n/d yn/ (n/d) = d. Aplicando el teorema 3.3, podemos cancelar el factor n/d, obteniendok1 � k2 (mod d) . Absurdo.

Ahora, suponga que u es solución de ax � b (mod n). Luego, a � (u� s0) = a �u � a � s0 � b � b = 0 (mod n) . Por tanto, n j a � (u� s0) . Luego, (n/d) divide a(a/d) � (u� s0) . Por el corolario 2.2, gcd (n/d, a/d) = 1. Por el lema de Euclides,(n/d) j (u� s0) . Esto es, existe un entero m tal que u = s0 + m (n/d) . Por el al-goritmo de la división, m = d � q + k, con 0 � k � d � 1. Sustituyendo, tenemosque

u = s0 +m (n/d) = s0 + q � n+ k (n/d) � sk (mod n) .

Por consiguiente, la congruencia lineal ax � b (mod n) sólo puede tener d solu-ciones no congruentes módulo n. �

52 3. Congruencias

Nos será muy conveniente, tener presente la forma que el teorema 3.5 toma cuandosuponemos que a y n son primos relativos.

Corolario 3.3 Si gcd (a, n) = 1, entonces la congruencia lineal ax � b (mod n) tiene unaúnica solución módulo n.

En particular, dados dos primos relativos a y n, la congruencia ax � 1 (mod n)tiene solución única. Esta solución se denomina el inverso multiplicativo de a mó-dulo n. Aunque la existencia de inversos para los enteros primos relativos con n esconsecuencia del teorema 3.5, preferimos dar otra prueba basada en la identidad deBezout.

Proposición 3.2 Si gcd (a, n) = 1, entonces existe el inverso de a módulo n. Además, esteinverso es único módulo n.

Prueba. Como gcd (a, n) = 1, existen enteros s, t tales que a � s + n � t = 1. Estoimplica que

a � s = a � s+ 0 � as+ nt � 1 (mod n) .

Por consiguiente, s es un inverso de a módulo n. Ahora, si r satisface que a � r �1 (mod n) , entonces

s � s � 1 � s � (a � r) � (a � s) � r � 1 � r � r (mod n) .

Luego, el inverso de a es único salvo módulo. �Si n es primo, entonces todo a 2 Z/nZ distinto de 0 tiene inverso multiplicativo

módulo n. Por tanto, Z/nZ es un campo. Recíprocamente, si Z/nZ es un campo,entonces Z/nZ es un dominio entero. Por el teorema 3.4, n es primo. Resuminendo,

Z/nZ es un campo si y sólo si n es primo.

Ahora ilustremos las técnicas algorítmicas que subyacen a las anteriores pruebas.

Ejemplo Halle todas las soluciones de la congruencia lineal 18x � 30 (mod 42) .

Solución Calculemos d = gcd (18, 42) y exprésemoslo como combinación linealde 42 y 18 :

42 = 18 � 2 + 6 ! 6 = 18 (�2) + 42 (1) (\)

18 = 6 � 3 + 0

Como 6 j 30, el teorema 3.5 garantiza la existencia de 6 soluciones no congruentesmódulo 42. Multiplicando (\) por 5 :

30 = 6 � 5 = 18 (�10) + 42 (5) � 18 (�10) � 18 � 32 (mod 42) .

Luego, x0 = 32 es una solución particular de la congruencia dada. Luego, las seissoluciones están dadas por

x � 32+ (42/6) � k � 32+ 7 � k (mod 42) , k = 0, 1, . . . 5.


Enumerándolas: 32, 39, 46 � 4, 53 � 11, 60 � 18 y 67 � 25. �X

Ejemplo Halle todas las soluciones de la congruencia lineal 9x � 21 (mod 30) .

Solución Como gcd (9, 30) = 3 j 9, existen tres soluciones no congruentes. Dadoque 3 = 9 (�3) + 30 (1) , tenemos que

21 = 9 (�21) + 30 (7) � 9 (�21) (mod 30) .

Luego, las soluciones están dadas por

x � �21+ (30/3) t � �21+ 10t (mod 30) , t = 0, 1, 2.

Así, tenemos las tres soluciones no congruentes

x � �21 (mod 30) , x � �11 (mod 30) y x � �1 (mod 30) .

Si se prefieren enteros positivos: x � 9, 19, 29 (mod 30) . �X

Ejemplo Halle el inverso de 10 módulo 63.

Solución Dado que gcd (10, 63) = 1, la proposición 3.2 nos dice que dicho in-verso existe. Aplicando el algoritmo de Euclides

63 = 10 � 6 + 3 1 = 10 � 1 + 3 � �3%

10 = 3 � 3 + 1 ! ! = 10 � 1 + [10 (�6) + 63 (1)] � �3

3 = 1 � 3 + 0 = 10 � 19 + 63 � �3

Luego, 10 � 19 � 1 (mod 30) . Esto muestra que 19 es el inverso de 10 módulo 63.�X

Ejemplo ¿Cuál es la solución de la congruencia lineal 3x � 4 (mod 7)?

Solución Dado que gcd (3, 7) = 1, podemos hallar el inverso de 3 módulo 7.Como 1 = 7� 6 = 7+ 3 (�2) , tenemos que �2 es el inverso de 3. Luego,

x � �6x � (�2) 3x � (�2) 4 = �8 � 6 (mod 7) .

es la solución de la congruencia.

Otra forma. Como 5 � �2 es el inverso de 3 módulo 7, tenemos que

15x � 20 (mod 7) ) x � 6 (mod 7) ,

dado que 15 � 1 y 20 � 4 (mod 7) . �X

Los sistemas de congruencias lineales surgen en muchos contextos, como, porejemplo, los métodos usados para ejecutar aritmética con enteros grandes. Dichossistemas se pueden hallar inclusive propuestos como acertijos en los escritos dematemáticos chinos e hindúes de la antigüedad.

Ejemplo. En el primer siglo D.C., el matemático chino Sun-Tsu se preguntó

54 3. Congruencias

Hay ciertas cosas cuyo número se desconoce. Cuando se divide por 3, el residuoes 2; cuando se divide por 5, el residuo es 3; y cuando se divide por 7, el residuoes 2.

¿Cuál será el número de las cosas?

Este acertijo se puede traducir , en terminología moderna, a la siguiente pregunta:

¿Cuáles son las soluciones del sistema de congruencias

x � 2 (mod 3)x � 3 (mod 5)x � 2 (mod 7)?

El siguiente teorema, nombrado así por el legado chino de problemas que involu-cran sistemas de congruencias lineales, afirma que cuando los módulos de un sistemade conguencias lineales son primos relativos por pares, existe una única solución del sistemamódulo el producto de los módulos.

Teorema Chino del Residuo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sean n1, n2, . . . , nr enteros positivos tales que gcd (ni, nk) = 1, para i 6= k. Entonces elsistema de congruencias lineales

x � a1 (mod n1)x � a2 (mod n2)

...x � ar (mod nr)

tiene una solución simultánea, que es única módulo el entero n = n1 � n2 � � � nr.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. (Existencia) Para cada k = 1, 2, . . . r, hacemos

Nk =nnk= n1 � � � nk�1nk+1 � � � nr = ∏

i 6=kni.

En otras palabras, Nk es el producto de todos los módulos ni omitiendo el factornk. Por hipótesis, los ni son primos relativos por pares, de modo que gcd (Nk, nk) =1. Luego, por la proposición 3.2, podemos calcular un entero sk (un inverso de Nkmódulo nk) tal que

Nk � sk � 1 (mod nk) .

Nuestro propósito es mostrar que el entero

x = a1N1s1 + a2N2s2 + � � �+ ar Nrsr =r

∑k=1

ak Nksk

es una solución simultánea del sistema dado.

Primero, observamos que Ni � 0 (mod nk) para i 6= k, dado que nk j Ni en estecaso. Luego,

x � 0+ 0+ � � �+ ak Nksk + � � �+ 0 � ak Nksk � ak (mod nk) , k = 1, 2, . . . r.


Esto muestra que existe una solución x al sistema de congruencias dado.

(Unicidad) Supongamos que x0 es otra solución del sistema. Entonces

x � ak � x0 (mod nk) , k = 1, 2, . . . r.

Así, nk j x� x0. Como gcd (ni, nk) = 1, por el corolario 2.3 (a), podemos afirmar quen1 � n2 � � � nr divide a x� x0. Esto es, x � x0 (mod n) . �Ejemplo Resuelva el acertijo de Sun-Tsu.

Solución En este caso, tenemos que n = 3 � 5 � 7 = 105 y

N1 =1053= 35, N2 =

1055= 21 y N3 =

1057= 15.

Ahora,

1 = 35 (�1) + 3 � 12, 1 = 21 � 1+ 5 (�4) y 1 = 15 � 1+ 7 (�2) .

Luego,s1 = �1, s2 = 1 y s3 = 1.

Por tanto, una solución al sistema está dada por x = 2 � 35 � (�1) + 3 � 21 � 1 + 2 �15 � 1 = 23. �X

Ejemplo (Johann Müller Regiomontano, s XV) Halle el menor entero que deje resid-uos 3, 11 y 15 cuando se divide por 10, 13 y 17, respectivamente.

Solución El problema se reduce a hallar la menor solución positiva del sistema decongruencias lineales

x � 3 (mod 10) ,x � 11 (mod 13) ,x � 15 (mod 17) .

Sean

n = 10 � 13 � 17 = 2210, N1 = 13 � 17 = 221, N2 = 10 � 17 = 170 y N3 = 10 � 13 = 130.

Notemos que

N1 � 1 (mod 10) y N2 � 1 (mod 13) .

Por tanto, x1 = 1 = x2. Por último,

N3 � 11 (mod 17) .

Notemos que 1 = 2 � 17+ (�3) � 11. Como �3 � 14 (mod 17) , tenemos que

14N3 � 14 � 11 � (�3) � 11 � 1 (mod 17) .

Por tanto, s3 = 14. Tomemos

x = 3 � 221 � 1 + 11 � 170 � 1 + 15 � 130 � 14 = 29 833 � 1103 (mod 2210) .

Por tanto, la menor solución positiva es x = 1103. �X

56 3. Congruencias

Ejercicio Solucione la congruencia lineal

17x � 9 (mod 276) .

Solución Dado que 276 = 3 � 4 � 23, esto es equivalente a hallar una soluciónpara el sistema de conguencias

17x � 9 (mod 3)17x � 9 (mod 4)17x � 9 (mod 23)

(3.1)

Notemos que 17 � 2 (mod 3) , 17 � 1 (mod 4) . y 17 � 19 = 323 � 1 (mod 23) .La última congruencia se cumple porque gcd (17, 23) = 1 = 17 (�4) + 23 (3) ; asíel inverso de 17 es �4 � 19 (mod 23) . Por tanto, (3.1) se transforma en el sistemaequivalente

x � 2 � 9 � 0 (mod 3)x � 1 � 9 � 1 (mod 4)x � 9 � 19 = 171 � 10 (mod 23)

Ahora, hagamos

N1 = 4 � 23 = 92, N2 = 3 � 23 = 69 y N3 = 3 � 4 = 12.

Notemos queN1 � 2 (mod 3) y N2 � 1 (mod 4) .

Así, s1 = 2 y s2 = 1. Ahora, notemos que 1 = 2 � 12 + 23 (�1) . Luego, s3 = 2.Tomemos

x = 0 � 92 � 2 + 1 � 69 � 1 + 10 � 12 � 2 = 309 � 33 (mod 2210) .

Por tanto, x � 33 (mod 276) proporciona una solución al sistema (3.1) y, a su vez,una solución a 17x � 9 (mod 276) . �X

Ejercicio Halle el menor entero positivo m que satisfaga 32 j m + 1, 42 j m +2 y 52 j m+ 3.

Solución Las condiciones del problema llevan al sistema de congruencias lin-eales:

m+ 1 � 0 (mod 9) m � �1 � 8 (mod 9)m+ 2 � 0 (mod 16) , m � �2 � 14 (mod 16)m+ 3 � 0 (mod 25) m � �3 � 22 (mod 25)

Como los residuos son primos relativos por pares, podemos aplicar el teorema Chinodel residuo. Sean

n = 9 � 16 � 25 = 3600, N1 = 16 � 25 = 400, N2 = 9 � 25 = 225 y N3 = 9 � 16 = 144.

N1 � 4 (mod 9) ) 1 = 9+ 4 (�2) ) 4 (�2) � 1 (mod 9) ) s1 =�2 � 7 (mod 9) .

N2 � 1 (mod 16) ) s2 = 1

N3 � 19 (mod 25) ) 1 = 19 (4) � 25 (3) ) 19 (4) � 1 (mod 25) )s3 = 4.


Tomemos

x = 8 � 400 � 7+ 14 � 225 � 1+ 22 � 144 � 4 � 38 222 � 2222 (mod 3600)

Tenemos que la menor solución positiva es m = 2222. �X

Ejercicio Halle el menor múltiplo positivo de 7 que deja residuo 2 cuando se dividepor 5, residuo 3 cuando se divide por 6 y residuo 5 cuando se divide por 11.

Solución 1 Sea x = 7k. Las condiciones del problema llevan al sistema de con-gruencias lineales:

x � 2 (mod 5)x � 3 (mod 6)x � 5 (mod 11)


n = 5 � 6 � 11 = 330, N1 = 6 � 11 = 66, N2 = 5 � 11 = 55 y N3 = 5 � 6 = 30.

N1 � 1 (mod 5) ) s1 = 1. N2 � 1 (mod 6) ) s2 = 1.

N3 � 8 (mod 11) ) 1 = 11 (3) + 8 (�4) ) 8 (�4) � 1 (mod 11) ) s3 =�4 � 7 (mod 11) .

Tomemos

x = 2 � 66 � 1+ 3 � 55 � 1+ 5 � 30 � 7 � 1347 � 27 (mod 330)

Luego, las soluciones al sistema de congruencias son de la forma

330t+ 27, t 2 Z.

Como 27 no es divisible por 7, tomamos la siguiente solución 330+ 27 = 357. Dadoque 357 = 7 � 51, tenemos que el número buscado es 357. �X

Solución 2 Como 7 es primo relativo con m = 5, 6, 11, podemos calcular suinverso multiplicativo mod m :

7 � 3 = 21 � 1 mod 5, 7 � 1 � 7 mod 6 y 7 � 8 = 56 � 1 mod 11.

Luego,

7k � 2 (mod 5) k � 6 � 1 (mod 5)7k � 3 (mod 6) ) k � 3 � 3 (mod 6)7k � 5 (mod 11) k � 40 � 7 (mod 11)

Aplicando el teorema Chino del residuo, obtenemos que

k = 1 � 66 � 1+ 3 � 55 � 1+ 7 � 30 � 7 � 1701 � 51 (mod 330)

Luego, el menor múltiplo de 7 pedido es 7k = 7 � 51 = 357. �X

58 3. Congruencias

Solución 3 Si x es divisible por 7, x deja residuo 0 al ser dividido por 7. Luego,

x � 2 (mod 5)x � 3 (mod 6)x � 0 (mod 7)x � 5 (mod 11)


n = 5 � 6 � 7 � 11 = 2310, N1 = 462, N2 = 385, N3 = 330 y N4 = 210.

N1 � 2 (mod 5) ) s1 = 8. N2 � 1 (mod 6) ) s2 = 1.

N3 � 1 (mod 7) ) s3 = 1. N4 � 1 (mod 11) ) s4 = 1.

Tomemos

x = 2 � 462 � 8+ 3 � 385 � 1+ 0 � 330 � 1+ 5 � 210 � 1 = 9597 � 357 (mod 2310)

Por tanto, el número es 357. �X

3.3 Tres Grandes Teoremas

Hace 25 siglos, los matemáticos chinos creían que n es un primo si y sólo si

2n�1 � 1 (mod n) .

Si esto fuera verdad, proporcionaría un test eficiente de primalidad ¿Por qué elloscreyeron que esta congruencia se podría usar para determinar si un entero es primo?Primero, ellos observaron que la congruencia se satisfacía siempre que n es primo.Por ejemplo, 5 es primo y

25�1 = 24 = 16 � 1 (mod 5) .

Segundo, ellos nunca hallaron un entero compuesto n para el cual la congruencia secumpliese. Los antiguos chinos sólo estaban parcialmente en lo correcto. Ellos teníanrazón al pensar que la congruencia se cumple siempre que n es primo, pero se equiv-ocaban en concluir que n es necesariamente primo si la congruencia se satisface.

El 18 de octubre de 1640, Fermat escribió una carta a Bernhard Frénice de Bessy, unoficial del ejercito francés que también era un gran aficionado a la teoría de números.En su carta, Fermat le comunicaba el siguiente resultado.

Pequeño Teorema de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Si p es un primo y a es un entero no divisible por p, entonces

ap�1 � 1 (mod p) .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Comencemos por considerar los primeros p� 1 múltiplos positivos de a :

a, 2a, 3a, . . . , (p� 1) a.

3.3. Tres Grandes Teoremas 59

Dado que p - a y p - k, es claro que

ka 6� 0 (mod p) , para todo k = 1, 2, . . . , p� 1.

Similarmente, si

ra � sa (mod p) , para 1 � r < s � p� 1,

tendríamos que p j a o r � s (mod p) ; absurdo.Por consiguiente, el conjuntoprevio de enteros tiene que ser congruente módulo p a los enteros 1, 2, 3, . . . , p� 1,tomados en algún orden. Multiplicando todas estas congruencias juntas , tenemosque

a � 2a � 3a � � � (p� 1) a � 1 � 2 � 3 � � � (p� 1) (mod p) .

Luego,ap�1 (p� 1)! � (p� 1)! (mod p) .

Como (p� 1)! y p son primos relativos, (p� 1)! tiene un inverso multiplicativo mó-dulo p. Por tanto, podemos concluir que ap�1 � 1 (mod p) . �

Aunque Fermat no proporcionó una prueba en la carta, adjunto una nota prome-tiendo que enviaría una prueba si esta no era muy extensa. El teorema ha recibidoese nombre para distinguirlo del Último Teorema de Fermat (probado por AndrewWiles en 1993). En 1736, Euler dio la primera prueba del pequeño teorema de Fer-mat. Casi un siglo después del anuncio de Fermat y 50 años antes que Euler, Leibnizhabía dado una prueba en un trabajo no publicado.

El pequeño teorema se puede enunciar en una forma más general.

Corolario 3.4 Si p es primo, entonces ap � a (mod p) para cualquier entero a.

Prueba. Cuando p j a, el enunciado obviamente se cumple: ap � 0 � a (mod p) .Si p - a, entonces, de acuerdo al teorema de Fermat, tenemos que ap = a � ap�1 �a � 1 = a (mod p) . �

Como habíamos mencionado el teorema de Fermat es una herramienta para ex-aminar la primalidad de un entero dado. Si se puede mostrar que la congruencia

an � a (mod n) ,

falla para alguna elección de a, entonces n es necesariamente compuesto.

Ejemplo Muestre que n = 117 es compuesto.

Solución El cómputo se mantiene bajo control si seleccionamos un entero pe-queño para a, digamos, a = 2. Dado que

2117 = 27�16+5 =�

27�16� 25 y 27 = 128 � 11 (mod 117) ,

tenemos que

2117 � (11)16 � 25 � 1218 � 25 � 48 � 25 = 221 (mod 117) .

Pero,

221 =�

27�3� 113 = 121 � 11 � 4 � 11 = 44 (mod 117) .

60 3. Congruencias

Luego, 2117 � 44 6� 2 (mod 117) . Así, n tiene que ser compuesto. De hecho, 117 =32 � 13. �X

Por otro lado, veamos que el recíproco del teorema de Fermat no es válido. En otraspalabras, mostremos que si an � a (mod n) para algún entero a, entonces n no es nece-sariamente primo. Requerimos un lema técnico.

Lema 3.1 Si p y q son primos distintos con

ap � a (mod q) y aq � a (mod p) ,

entonces apq � a (mod pq) .

Prueba. Por el último corolario, tenemos que (aq)p � aq (mod p) . Por hipóte-sis, aq � a (mod p) . Luego, apq � a (mod p) . Esto es, p j apq � a. Análogamente,q j apq � a. Como gcd (p, q) = 1, entonces pq j apq � a. Lo cual se puede reformularcomo apq � a (mod pq) . �Ejemplo Mostremos que

2341 � 2 (mod 341) , donde 341 = 11 � 31.

Solución Notemos que 210 = 1024 = (31 � 11 � 3) + 1. Luego,

211 = 2 � 210 � 2 � 1 = 2 (mod 31) y 231 = 2�

210�3� 2 � 13 = 2 (mod 11) .

Aplicando el lema anterior,

2341 = 211�31 � 2 (mod 341) .

De modo que el recíproco del pequeño teorema de Fermat es falso. �X

Ejercicio Halle el residuo cuando 242010 se divide por el número primo 17.

Solución Como 24 � 7 (mod 17) , se sigue que 242010 � 72010 (mod 17) . Por elpequeño teorema de Fermat,

716 � 1 (mod 17) .

Por el algoritmo de la división, 2010 = 16 � 125+ 10. Por tanto,

72010 = (716)125 � 710 � 710 (mod 17) .

Ahora, 72 = 49 � 15 � �2 (mod 17) . Por tanto,

710 = (72)5 � (�2)5 = �32 � 2 (mod 17) .

Por tanto, 242010 mod 17 = 2. �X

El pequeño teorema de Fermat nos permite identificar los inversos multiplicativosmódulo p.

Corolario 3.5 Sea p un primo y a un entero tal que p - a. Entonces ap�2 es un inverso de amódulo p.


En sus Meditationes Algebricae de 1770, el matemático inglés Edwar Waring anun-ció varios teoremas nuevos. Entre estos, se destacaba una propiedad interesante delos primos reportada a él por uno de sus antiguos alumnos, un cierto John Wilson.La propiedad es la siguiente: Si p es un número primo, entonces p divide a (p� 1)! +1. Parece que Wilson sospecho lo anterior basándose en cómputos numéricos; encualquier caso, ni él, ni Waring sabían cómo probarlo. Confesando su incapacidad enproporcionar una demostración, Waring afirmó “Teoremas de esta clase serán muydifíciles de probar, debido a la falta de una notación para expresar números primos”.A pesar del pronóstico pesimista de Waring, poco después Lagrange dio una prueba(1771) de lo que en la literatura se conoce como Teorema de Wilson.

Teorema de Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Si p es un primo, entonces(p� 1)! � �1 (mod p) .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Descartemos los casos evidentes p = 2 y p = 3. Tomemos p > 3. Supongaque a es cualquiera de los p� 1 enteros positivos

1, 2, 3, . . . , (p� 1)

Como gcd (a, p) = 1, a tiene un único inverso multiplicativo entre 1 y p� 1; esto es,existe un único a0, con 1 � a0 � p� 1, tal que aa0 � 1 (mod p) .

Dado que p es primo, a = a0 si y sólo si a = 1 o a = p� 1. En efecto,

a2 � 1 (mod p) sii (a� 1) (a+ 1) � 0 (mod p)

sii a � 1 o a � �1 (mod p) sii a = 1 o a = p� 1.

Si omitimos los números 1 y p� 1, el efecto es agrupar los restantes enteros 2, 3, . . . , p�2 en parejas a, a0, con a 6= a0, tales que aa0 � 1 (mod p) . Cuando multiplicamos todasestas p�3

2 congruencias y los factores se organizan adecuadamente, tenemos que

2 � 3 � � � (p� 2) � 1 (mod p) .

Equivalentemente,(p� 2)! � 1 (mod p)

Ahora multiplicando por p� 1, obtenemos que (p� 1)! � p� 1 � �1 (mod p). �Ejemplo Ilustremos la prueba del teorema de Wilson para p = 13.

Solución Es posible dividir los enteros 2, 3, . . . , 11 en p�32 = 5 parejas cuyo pro-

ducto es igual a 1 módulo 13. Explícitamente,

2 � 7 = 14 � 1, 3 � 9 = 27 � 1, 4 � 10 = 40 � 1, 5 � 8 = 40 � 1 y 6 � 11 = 66 � 1 (mod 13) .

Multiplicando estas congruencias da como resultado

11! = (2 � 7) (3 � 9) (4 � 10) (5 � 8) (6 � 11) � 15 = 1 (mod 13) .

Así,12! = 11! � 12 � 1 � 12 � �1 (mod 13) .

62 3. Congruencias

Por tanto, (p� 1)! � �1 (mod p) , cuando p = 13. �X

Lagrange observó que el recíproco del teorema de Wilson también es válido.

Proposición 3.3 Si (n� 1)! � �1 (mod n) , entonces n es primo.

Prueba. Razonemos por el absurdo y supongamos que n es compuesto. Luego, ntiene un divisor d con 1 < d < n. Como d � n� 1, entonces d j (n� 1)!. Por hipóte-sis, n j (n� 1)!+ 1. Luego, d sería divisor de (n� 1)!+ 1� (n� 1)! = 1; absurdo. �

Introduzcamos la función ϕ de Euler. Para n > 1, denotemos por ϕ (n) el númerode enteros a, 1 � a < n, tales que gcd (a, n) = 1. Por convención, ϕ (1) = 1. Porejemplo, ϕ (12) = 4, dado que 1, 5, 7 y 11 son los únicos enteros positivos, menoresque 12, que son coprimos a 12.

Cuando n = p es primo, se tiene que ϕ (p) = p� 1; también,

ϕ�

pk�= pk�1 (p� 1) = pk

�1� 1

p

�.

Además, si m, n � 1 y gcd (m, n) = 1, entonces ϕ (mn) = ϕ (m) ϕ (n) ; esto es, ϕes una función multiplicativa. Luego, para cualquier entero n = ∏p pk (producto detodos los primos que dividen a n y k � 1), entonces

ϕ (n) = ∏p

ϕ�

pk�= ∏

ppk�1 (p� 1) = ∏

ppk�

1� 1p

�= n ∏

p

�1� 1

p

�.

Otra propiedad básica esϕ (n) = ∑

djnϕ (d) .

En 1760, Euler ofreció la siguiente generalización del pequeño teorema de Fermat.

Teorema de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Si gcd (a, n) = 1, entoncesaϕ(n) � 1 (mod n) .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Sean m = ϕ (n) y 1 = r1 < r2 < � � � < rm < n tales que

ri 6� rj (mod n) y gcd (ri, n) = 1, para i, j = 1, . . . , m con i 6= j.

Como gcd (a, n) = 1, por el corolario 3.2 (a) y el corolario 2.3 (b), los enteros a �r1, . . . , a � rm también cumplen que

a � ri 6� a � rj (mod n) y gcd (a � ri, n) = 1, para i, j = 1, . . . , m con i 6= j.

De este modo, los residuos de los enteros a � r1, a � r2, . . . , a � rm módulo n son losenteros ri1 , ri2 , . . . , rim , respectivamente. Por tanto,

am �m

∏i=1

ri =m

∏i=1

a � ri �m

∏k=1

rik = 1 �r

∏i=1

ri (mod n) .


Por hipótesis, gcd (ri, n) = 1, para todo i = 1, 2, . . . , m. Por el corolario 2.3 (b) (apli-cado m veces),

gcd (∏i ri, n) = 1.

Luego, por el corolario 3.2 (a), am � 1 (mod n) . Esto es, aϕ(n) � 1 (mod n) . �

Corolario 3.6 (Pequeño Teorema de Fermat) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Si p es un primo y gcd (a, p) = 1, entonces

ap�1 � 1 (mod p) .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Ejemplo Dado que 1, 5, 7 y 11 son primos relativos a 12, ϕ (12) = 4. Por el teoremade Euler, si gcd (a, 12) = 1, entonces

a4 � 1 (mod 12) .

En particular, 14, 54, 74 y 114 son todos congruentes a 1 módulo 12. �XEl teorema de Euler es útil para hallar residuos de números que involucran expo-

nentes grandes aún si el divisor es compuesto, pero dado que el divisor sea primorelativo con la base. El siguiente ejemplo ilustra una situación típica.

Ejemplo Halle el residuo cuando 2452010 se divide por 18.

Solución Primero, calculemos ϕ (18) = ϕ (2) � ϕ�32� = 6. Dado que 245 �

11 (mod 18) , 2452010 � 112010 (mod 18) . Como gcd (11, 18) = 1, por el teorema deEuler,

11ϕ(18) = 116 � 1 (mod 18) .

Dividiendo, 2010 = 335 � 6. Por tanto,

2452010 � 112010 = (116)335 � 1335 = 1 (mod 18) .

Así, el residuo buscado es 1. �X

El teorema de Euler permite obtener un resultado análogo al corolario 3.5.

Corolario 3.7 Si gcd (a, n) = 1, entonces aϕ(n)�1 es un inverso multiplicativo de a módulon.

Ejemplo Solucione la congruencia lineal 35x � 47 (mod 24) .

Solución Como 35 � 11 (mod 24) y 47 � 23 � �1 (mod 24) , la congruencia sepuede simplificar como 11x � �1 (mod 24) . Notemos que 112 = 121 = 24 � 5+ 1.Luego, 112 � 1 (mod 24) .

Por otro lado, es claro que gcd (11, 24) = 1. Por el corolario 3.7,

x � 11ϕ(24)�1 � (�1) � 117 � (�1) � (112)3 � (�11) � �11 (mod 24) .

Luego, x � 13 (mod 24) es solución de la congruencia inicial. �X

64 3. Congruencias

Ejercicio Aplique el teorema de Euler para solucionar la congruencia lineal

x341 � 127 (mod 893) .

Solución Tenemos que ϕ (893) = ϕ (19 � 47) = 18 � 46 = 828. Del algoritmo deEuclides,

gcd (828, 341) = 1 y 1 = 828 (�7) + 341 (17) .

Luego,

(x341)17 = x1+828�7 = x ��

x828�7� x � (1)7 � x (mod 893) .

Notando que 17 = 16+ 1, tenemos que

1272 = 16 129 � 55 (mod 893) 1274 � 552 = 3025 � 346 (mod 893)

1278 � 3462 = 119 716 � 54 (mod 893) 12716 � 542 = 2916 � 237 (mod 893)

Por consiguiente,

x � (x341)17 � (127)17 = (127)16 � 1271 � 237 � 127 = 30 099 � 630 (mod 893) .

�X

Ejercicios

1. Liste cinco enteros que sean congruentes con 4 módulo 12.

2. Decida si los siguientes enteros son congruentes a 5 módulo 17.

(a) 80 (b) 103 (c) �29 (d) �122

3. Suponga que a � b (mod n) . Pruebe cada una de las siguientes afirmaciones.

(a) Si m j n, entonces a � b (mod m) .

(b) Si c > 0, entonces ca � cb (mod cn) .

(c) Si los enteros a, b y n son divisibles por d > 0, entonces a/d � b/d (mod n/d) .

4. Dé un ejemplo de que a2 � b2 (mod n) no necesariamente implica que a �b (mod n) .

5. Dé un ejemplo que muestre que ak � bk (mod n) y k � j (mod n) no necesari-amente implican que aj � bj (mod n) .

6. Construya tablas de suma y producto para Z/5Z, Z/6Z, Z/8Z y Z/10Z.

7. Muestre que Z/nZ es un anillo conmutativo con unidad bajo las operacionesdefinidas. [Sug. Z es un anillo conmutativo con unidad].

8. Pruebe que los cuadrados de los elementos de Z/4Z son sólo 0 y 1.

9. Para a, b 2 Z/nZ, defina a � b sii ab � b2 (mod n) . Pruebe o refute que � esun orden parcial en Z/nZ en cada uno de los siguientes casos.


(a) n es primo.

(b) n = pq, donde p y q son primos distintos.

(c) n es divisible por el cuadrado de un primo. [Sug: Puede ser útil considerarel caso n = 12].

10. Pruebe que para todo a y b, a2 + b2 nunca deja residuo 3 cuando se divide por4.

11. Muestre que si a � b (mod n) , entonces

gcd (a, n) = gcd (b, n) .

12. Compute el residuo de 37100 cuando se divide por 29.

13. Compute los últimos dos dígitos de 915000.

14. Halle los residuos cuando 250 y 4165 son divididos por 7.

15. ¿Cuál es el residuo cuando

15 + 25 + 35 + � � �+ 995 + 1005

se divide por 4?

16. Pruebe que el entero 53103 + 10353 es divisible por 39, y que 111333 + 333111 esdivisible por 7.

17. Para n � 1, use la teoría de congruencias para establecer cada una de los sigu-ientes enunciados de divisibilidad:

(a) 7 j 52n + 3 � 25n�2. (b) 13 j 3n+2 + 42n+1.

(c) 27 j 25n+1 + 5n+2. (d) 27 j 25n+1 + 5n+2.

18. Para n � 1, muestre que

(�13)n+1 � (�13)n + (�13)n�1 (mod 181) .

[Sug: Note que (�13)2 � �13+ 1 (mod 181) ; use inducción sobre n].

19. Pruebe los siguientes enunciados:

(a) Si a es un entero impar, entonces a2 � 1 (mod 8) .

(b) Para todo entero a, a3 � 0, 1, o 6 (mod 7) .

(c) Para todo entero a, a4 � 0 o 1 (mod 5) .

20. Pruebe que

(a) Para todo a : a � (a2 � 1) � (a+ 2) � 0 (mod 4) .

(b) Si a es impar, entonces a4 � 1 (mod 16) .

(c) Si a es un entero no divisible por 2 o 3, entonces a2 � 1 (mod 12) .

66 3. Congruencias

21. Sea a un entero tal que a 6� 0 (mod 7) . Muestre que a � 5k (mod 7) para algúnentero k.

22. Sean a, b, c, d y x enteros y p un primo. Muestre que si (ax+ b) (cx+ d) �0 (mod p) , entonces

(ax+ b) (mod p) o (cx+ d) � 0 (mod p) .

23. Muestre que hay infinitos primos congruentes a �1 módulo 6.

24. Use congruencias para mostrar que

89 j 244 � 1 y 97 j 248 � 1.

25. Sea gcd (b, n) = 1. Pruebe que si ab � cd (mod n) y b � d (mod n) , entoncesa � c (mod n) .

26. Sea n = gcd (n1, n2) . Pruebe que si a � b (mod n1) y a � c (mod n2) , entoncesb � c (mod n) .

27. Halle todos los enteros x, 0 � x < n, que satisfagan cada una de las siguientescongruencias. Si x no existe, explique porqué.

(a) x2 � 4 (mod 13) (b) 4x2 + 3x+ 7 � 0 (mod 5) (c) (2x+ 1) (3x+ 4) � 0 (mod 17)

(d) x2 � 2 (mod 6) (e) x2 � �2 (mod 6) (f) 3x2 + 14x� 5 � 0 (mod 97)

28. Sean a y n números naturales con n > 1. Sean r y s enteros tales que r �s (mod n) . Pruebe o refute.

(a) ar � as (mod n) . (b) ra � sa (mod n) .

29. Sean a y b enteros tales que a � b (mod n) . Pruebe o refute.

(a) 3a � b2 (mod n) . (b) a2 � b2 (mod n) .

(c) a2 � b3 (mod n) . (d) a2 � b2 �mod n2� .

30. Solucione las siguientes congruencias lineales.

(a) 25x � 15 (mod 29) (b) 5x � 2 (mod 26) (c) 6x � 15 (mod 21)

(d) 20x � 19 (mod 43) (e) 34x � 60 (mod 98) (f) 36x � 18 (mod 102)

31. Muestre que 15 es un inverso de 7 módulo 26 y que 937 es un inverso de 13módulo 2436.

32. Calcule un inverso multiplicativo de a módulo n.

(a) a = 13, n = 20. (b) a = 2, n = 17. (c) a = 144, n = 233.

(e) a = 69, n = 89. (f) a = 1891, n = 3797. (g) a = 60003722857, n = 77695236973.

33. Sea a 2 Z con 1 � a < n. Pruebe que si a y n no son primos relativos, existe unentero b con 1 � b < n tal que ab � 0 (mod n) .


34. Muestre que no puede existir un inverso multiplicativo de a módulo n si gcd (a, n) >1.

35. Solucione cada uno de los siguientes conjuntos de congruencias simultáneas:

(a) x � 1 (mod 3) , x � 2 (mod 5) , x � 3 (mod 7) .

(b) x � 5 (mod 11) , x � 14 (mod 29) , x � 15 (mod 31) .

(c) x � 5 (mod 6) , x � 4 (mod 11) , x � 3 (mod 17) .

(d) x � 1 (mod 4) , x � 8 (mod 9) , x � 10 (mod 25) .

(e) x � 1003 (mod 17369) , x � 2974 (mod 5472) .

(f) 2x � 1 (mod 5) , 3x � 9 (mod 6) , 4x � 1 (mod 7) , 5x � 9 (mod 11) .

36. ¿Qué enteros son divisibles por 5 y dejan un residuo de 1 cuando se dividenpor 3?

37. Halle el menor entero a > 2 tal que

2 j a, 3 j a+ 1, 4 j a+ 2, 5 j a+ 3, 6 j a+ 4.

38. Obtenga tres enteros consecutivos cada uno de ellos teniendo un factor cuadrado[Sug. Halle a tal que 22 j a, 32 j a+ 1 y 52 j a+ 2].

39. Obtenga tres enteros consecutivos, el primero de los cuales es divisible porun cuadrado, el segundo es divisible por un cubo y el cuarto por una cuartapotencia.

40. (Antiguo problema chino). Una banda de 17 piratas robo un baúl lleno de mon-edas de oro. Cuando se trato de dividir el botín en partes iguales, sobraron3 monedas. Despues de la pelea sobre quién se debía quedar con las mon-edas extras, un pirata fue asesinado. La fortuna fue redistribuida, pero estavez sobraron 10 monedas. De nuevo hubo otra discusión en la que otro piratafue muerto. Pero ahora el botín total se distribuyo totalmente entre los sobre-vivientes. ¿Cuál fue el número total de monedas que pudo haber sido robadas?

41. Cierto entero entre 1 y 1200 deja residuo 1, 2, 6 cuando se divide por 9, 11, 13,respectivamente. ¿Cuál es el entero?

42. Halle un entero que deje residuos 1, 2, 5, 5 cuando se divide por 2, 3, 6, 12,respectivamente (Yih-hing, fallecido en 717).

43. Halle un entero que deje residuos 2, 3, 4, 5 cuando se divide por 3, 4, 5, 6,respectivamente (Bhaskara, nacido en 1114).

44. Este ejercicio ofrece otro método para mostrar que 2340 � 1 (mod 341).

(a) Use el pequeño teorema de Fermar para mostrar que 2340 � 1 (mod 11)al notar que 2340 = (210)34.

(b) Muestre que 2340 � 1 (mod 31) usando el hecho que 2340 = (25)68 = 3268.

45. (a) Use el pequeño Fermar para computar 3302 mod 5, 3302 mod 7 y 3302 mod 11.

68 3. Congruencias

(b) Use el teorema chino del residuo para hallar 3302 mod 385 (Note que 385 =5 � 7 � 11).

46. (a) Use el pequeño Fermar para computar 52003 mod 7, 52003 mod 11 y 52003 mod 13.

(b) Use el teorema chino del residuo para hallar 52003 mod 1001. (Note que1001 = 7 � 11 � 13).

47. Muestre que si p y q son primos distintos, entonces pq�1+ qp�1 � 1 (mod pq) .

48. Pruebe que si p es primo y a es un entero, entonces p divide a ap + (p� 1)!a.

49. Sin usar el teorema de Wilson, verifique que (p� 1)! � �1 (mod p) para lossiguientes primos.

(a) p = 5. (b) p = 11. (c) p = 17. (d) p = 19.

50. Use el teorema de Wilson para hallar el menor residuo positivo de 8 � 9 � 10 � 11 �12 � 13 módulo 7.

51. ¿Cuál es el residuo cuando 7 � 8 � 9 � 15 � 16 � 17 � 23 � 24 � 25 � 43 se divide por 11?

52. Muestre que si n no es primo, entonces (n� 1)! � 0 (mod n) , excepto cuandon = 4.

53. Sea p un primo. Muestre que si a � 1 (mod p) , entonces

a (a+ 1) � � � (a+ p� 2) � �1 (mod p) .

54. Sea p un primo y n un entero positivo. Pruebe que

(n � p)!n! � pn � (�1)n (mod p) .

55. Sea p un primo impar. Muestre que

(a) 2 (p� 3)! � �1 (mod p) .

(b) 12 � 32 � � � (p� 2)2 � (�1)(p+1)/2 (mod p) .

(c) 22 � 42 � � � (p� 1)2 � (�1)(p+1)/2 (mod p) .

56. Un entero n � 2 es primo si y sólo si (n� 2)! � 1 (mod 24) .

57. Halle ϕ (n) para n, 13 � n � 20.

58. Muestre que si n es impar y 3 - n, entonces n2 � 1 (mod n) .

59. Muestre que a12 � 1 es divisible por 35, siempre que gcd (a, 35) = 1.

60. Use el teorema de Euler para probar las siguiente afirmaciones.

(a) Para todo entero a : a37 � a (mod 1729) . [Sug: 1729 = 7 � 13 � 19]

(b) Para todo entero a : a13 � a (mod 2730) . [Sug: 2730 = 2 � 3 � 5 � 7 � 13]

(c) Para todo entero impar a : a33 � a (mod 4080) . [Sug: 4080 = 15 � 16 � 17]


61. Use el teorema de Euler para mostrar que para todo entero n � 0 :

51 j 1032n+9 � 7.

62. Pruebe que 215 � 23 divide a a15 � a3 para todo entero a. [Sug: 215 � 23 =5 � 7 � 8 � 9 � 13]

63. Muestre que si gcd (a, n) = gcd (a� 1, n) = 1, entonces

1+ a+ a2 + � � �+ aϕ(n)�1 � 0 (mod n) .

[Sug: Recuerde que aϕ(n) � 1 = (a� 1)�

aϕ(n)�1 + � � �+ a2 + a+ 1�

]

64. Sean m y n enteros positivos. Muestre que si gcd (m, n) = 1, entonces

mϕ(n) + nϕ(m) � 1 (mod mn)

65. Pruebe que si gcd (a, n) = 1, la congruencia lineal ax � b (mod n) tiene solu-ción

x � baϕ(n)�1 (mod n) .

66. Solucione las congruencias lineales.

(a) 3x � 5 (mod 26) . (b) 13x � 2 (mod 40) . (c) 10x � 21 (mod 49) .

67. Use el teorema de Euler para evaluar 2100,000 mod 77 y 3100,000 mod 35.

68. Halle el último dígito de la expansión decimal de 31000.

69. Muestre que si a es un entero tal que a no es divisible por 3 o tal que a esdivisible por 9, entonces a7 � a (mod 63) .

70. Muestre que si n es un entero impar que no es múltiplo de 5, entonces n divideun entero cuya expansión decimal sólo contiene el dígito 1 (i.e. n divide algúnrepunit).

70 3. Congruencias

4

Números Cardinales

A finales del siglo XIX, Georg Cantor introdujo la teoría de conjuntos para poderdesarrollar la noción de infinito. Cantor había investigado el problema de unicidadde la representación de una función por una serie de Fourier, obteniendo resultadosde la forma

∞

∑n=0

(an sin x+ bn cos x) =∞

∑n=0

(a0n sin x+ b0n cos x) , 8x 2 S ) an = a0n y bn = b0n, 8n.

para varios tipos de subconjuntos S de [0, 2π] . Después de probar que que el resul-tado se cumple para conjuntos S que excluyen finitos puntos de [0, 2π] , él tambiénpudo hacerlo para conjuntos S que excluían ciertos conjuntos infinitos de puntos.Para poder explicar la estructura de los conjuntos de puntos excluidos, Cantor desar-rolló una teoría de “magnitudes” infinitas a partir de ideas sobre magnitudes finitas,i.e. los números naturales. Cantor se enfocó en extender dos usos básicos de los natu-rales: contar y ordenar. Esta extensión dio lugar a dos clases distintas de números: losnúmeros cardinales para describir tamaños de conjuntos y los números ordinales paradescribir formas de ordenar bien un conjunto. Además, Cantor dotó ambas clases denúmeros con operaciones aritméticas (suma, producto y exponenciación) que coin-cidían con la aritmética usual de los números naturales.

En este capítulo desarrollaremos los aspectos básicos de la teoría de números car-dinales. Para un desarrollo de la teoría de números ordinales se puede consultar[En77], [Go96], [Hr99] o [Le02].

4.1 Cardinalidad de Conjuntos

Intuitivamente, dos conjuntos tienen la misma cantidad de elementos si cada ele-mento de un conjunto está en correspondencia con un elemento del otro conjunto yviceversa. Por ejemplo, al entrar a un auditorio podemos afirmar que hay la mismacantidad de personas que de sillas si observamos que toda persona está sentada enuna silla y si ninguna silla está vacía. Así las correspondencias uno a uno permiten rela-cionar el tamaño de conjuntos arbitrarios sin hacer mención a un conteo específico.Esta noción de cardinalidad fue concebida por Bernard Bolzano en 1851 y por Cantoren 1878.

Definición Los conjuntos A y B son equipotentes (tienen la misma cardinalidad)si existe una función biyectiva f : A ! B. En este caso, escribimos A � B. La biyección fse denomina una correspondencia uno a uno entre A y B.

Ejemplo N � Z+. Tomemos la función sucesor σ : N! Z+, σ (n) = n+ 1. Por elcuarto axioma de Peano, σ es inyectiva. Por el lema 1.1, σ es sobre. �X

72 4. Números Cardinales

Ejemplo Sean a < b números reales. Consideremos la función lineal f : [0, 1] ![a, b] dada por.

f (x) = a+ (b� a)x.

Es fácil verificar que f es biyectiva. Luego, [0, 1] � [a, b] . Tomando la función frestringida a (0, 1) , se tiene que (0, 1) � (a, b) �X

Teorema 4.1 Sean A, B y C. Entonces se cumple que

(a) A � A. (b) Si A � B, entonces B � A. (c) Si A � B y B � C, entonces A � C.

Prueba. (a) idA : A! A es biyectiva.

(b) Si f : A! B es biyectiva, entonces f�1 : B! A también lo es.

(c) Si f : A ! B y g : B ! C son biyectivas, entonces h = g � f : A ! C también loes. �Ejemplo Sean a < b y c < d números reales. Por el ejemplo anterior,

[0, 1] � [a, b] y [0, 1] � [c, d] .

Por el teorema 4.1, [a, b] � [c, d] . Análogamente, (a, b) � (c, d) . �X

Lema 4.1 Suponga que A \ B = ∅ = C \ D. Si A � C y B � D, entonces A [ B �C [ D.

Prueba. Sean f : A ! C y g : B ! D biyectivas. Definamos h : A [ B ! C [ Dpor

h (x) =�

f (x) , si x 2 A.g (x) , si x 2 B.

Como A \ B = ∅, es claro que h está bien definida. Sea h0 : C [D ! A [ B dada por

h0 (y) =�

f�1 (y) , si y 2 A.g (y) , si y 2 B.

Dado que C \ D = ∅, h0 está bien definida. Razonando por casos se tiene que

h0 (h (x)) = x y h�h0 (y)

�= y,

para todo x 2 A [ B, y 2 C [ D. Por tanto, h es biyectiva. �Ejemplo Sean E = f2n j n 2Ng y O = f2n+ 1 j n 2Ng . Entonces

N � E y N � O.

Notemos que E\O = ∅. �X

Proposición 4.1 Z � Z� � Z+ � Z� �N.

Prueba. Mediante la biyección a 7! �a, vemos que Z� � Z+. Por tanto,

Z� �N � E y Z+ �N � O.

Por el lema 4.1, tenemos que

Z� = Z� [Z+ � E[O = N.

4.1. Cardinalidad de Conjuntos 73

Por otro lado, sea f : N! Z definida por

f (m) =�

n, si m = 2n.�n, si m = 2n+ 1.

Dado que f es biyectiva (ejercicio), se tiene que Z � N. Ahora, basta aplicar transi-tividad. �

Volvamos a considerar el ejemplo del teatro. Puede ocurrir que todas las personasesten sentadas, pero haya sillas vacías o no. En cualquier caso, la cantidad de per-sonas es menor o igual a la cantidad de sillas. La situación se generaliza del siguientemodo.

Definición A es dominado por B (notación: A � B) si existe una función inyectivaf : A! B.

Notemos que

A � B sii A � C, para algún C � B.

Escribimos A � B para indicar que A � B y A 6� B.

El teorema 4.1 muestra que la propiedad A � B se comporta como una relaciónde equivalencia. Ahora mostremos que la propiedad A � B se comporta como unorden en las “clases de equivalencia” bajo equipotencia.

Lema 4.2 Sean A, B, C y D conjuntos.

(a) Si A � B y A � C, entonces C � B. (b) Si A � B y B � D, entonces A � D.

(c) A � A. (d) Si A � B y B � C, entonces A � C.

Vemos � es reflexiva y transitiva. Faltaría mostrar que � es antisimétrica. A difer-encia de las otras propiedades, este es un resultado muy importante, descubiertoindependientemente por Dedekind y Cantor. Sin embargo, se conoce en la literaturacomo

Teorema de Schröder-Bernstein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Si A � B y B � A, entonces A � B... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

La primera prueba del teorema fue hallada por Dedekind en 1887, pero él no lapublicó en su época y aparecio sólo hasta 1932. Cantor probó el teorema en 1897,pero usando tácitamente el Axioma de Elección. Ernst Schröder anunció una pruebasin usar elección en un abstract de 1896. Luego, publicó una prueba errónea en 1898,corrigiéndola en 1911. Felix Bernstein proporcionó la primera prueba totalmente sat-isfactoria sin usar el Axioma de Elección. Esta prueba apareció en el texto Leçons surla théorie des fonctions (1898) de Emile Borel y, luego, en la tesis doctoral de Bernsteinde 1901.

Desde entonces, otros famosos matemáticos han ofrecido nuevas demostracionesal teorema de Schröder-Bernstein. Entre estas, destacamos las pruebas dadas por A.


Schoenflies (1900), Bertrand Russell (1902), Henri Poincaré (1905), Giuseppe Peano(1906), Ernst Zermelo (1908) o Banach, Knaster y Tarski (1924).

Dejaremos la prueba del teorema para el final de la sección. En el apéndice B, ofre-cemos otras pruebas alternativas que pueden ser de interés para el lector.

Corolario 4.1 Si A � B � C y A � C, entonces A � B � C.

Prueba. Como la funciones inclusión iA : A ! B e iB : B ! C son inyectivas, setiene que

A � B y B � C.

Dado que A � C, por el lema 4.2 (a), se sigue que C � B.

Por el teorema de Schröder-Bernstein, B � C. Luego, por transitividad, A � B � C.�

Proposición 4.2 N�N �N.

Prueba 1. Consideremos la función f : N�N!N dada por

f (m, n) = 2m(2n+ 1)� 1.

Notemos que f está bien definida. Dados m, n 2N se tiene que 2m(2n+ 1) � 1.

Veamos que f es inyectiva. Si f (m, n) = f (p, q), entonces

2m(2n+ 1) = 2p(2q+ 1),

Multiplicando la ecuación por 2�m, obtenemos 2n+ 1 = 2p�m(2q+ 1). Como 2n+ 1es claramente impar, se sigue que p�m = 0. Luego, 2n+ 1 = 2q+ 1. Así, p = m yq = n.

Veamos que f es sobreyectiva. Dado k 2 N, sea 2m la mayor potencia de 2 que dividea k + 1 (si k + 1 es impar, m = 0). Entonces (k + 1)/2m es un impar de la forma(2n+ 1). Luego, k 2 ran ( f ) . �

Prueba 2. Usemos el teorema de Schröder-Bernstein. Sea f : N�N ! N dadapor

f (m, n) = 2m+1 � 3n+1.

Por el teorema fundamental de la aritmética, f es inyectiva. Luego, N�N �N.

Ahora, sea g : N!N�N dada por

g (n) = (n, 0) .

Es obvio que g es inyectiva. Luego, N �N�N. Por tanto, N�N �N. �La función f de la prueba se suele denominar función de pareamiento (pairing

function). Otro ejemplo está dado por la función g dada por

g(m, n) = 12 (m+ n)(m+ n+ 1) +m.

Mediante inducción matemática, podemos generalizar la proposición 4.2. Paraello, necesitamos el siguiente lema.


Lema 4.3 Si A � C y B � D, entonces A� B � C� D.

Prueba. Sean f : A ! C y g : B ! D biyectivas. Definamos h : A� B ! C � Dpor

h (x, y) = ( f (x) , g (y)) .

Ahora basta mostrar que h es biyectiva (ejercicio). �

Corolario 4.2 Para todo k : Nk �N.

Veamos que el campo de números racionales también es equipotente con N.

Proposición 4.3 Q �N.

Prueba. Veamos que Q+ � Z+. Es obvio que Z+ � Q+. Definamos g : Q+ !Z+ �Z+ por

g (r) = g� a

b

�= (a, b) , donde gcd (a, b) = 1.

Como g es inyectiva, tenemos que Q+ � Z+ �Z+.

Por la proposiciones 4.1 y 4.2 y el lema 4.3, se tiene que

Z+ �Z+ �N�N �N � Z+.

Por el lema 4.2 (b), Q+ � Z+. Por el teorema de Schröder-Bernstein, Q+ � Z+.

Ahora, componiendo con la biyección r 7! �r, vemos que Q� � Q+ � Z+ � Z�.Esto es,

Q� � Z� y Q+ � Z+.

Por el lema 4.1, tenemos que

Q = Q� [ f0g [Q+ � Z� [ f0g [Z+ = Z.

Por transitividad, Q �N. �Ejemplo Podemos mostrar que N � Q mediante dovetailing. Arreglamos Q en unamatriz infinita la cual recorremos como lo indica la siguiente trayectoria.


� � � �[5]21

(= �[4]11

[0]01

=)[1]11

[10]21

=)[11]31

� � �

+ * + * +

� � � �22

�[3]12

(= 02

(=[2]12

22

[12]32

� � �

+ * +

� � � �[6]23

=) �[7]13

=) 03

=)[8]13

=)[9]23

33

� � �

+

� � � (= �24

(= �[15]14

(= 04

(=[14]14

(= 23

(=[13]34

� � �

Definimos f : N! Q, donde f (n) es la fracción debajo de [n] . Nos aseguramos quef es inyectiva al obviar las fracciones que ya se les ha asociado un natural. Por ejem-plo, f (1) = 1

1 = 1 y descartamos 22 , 3

3 , 44 , � � � las restantes fracciones que representan

a 1. Así, obtenemos una biyección de N en Q. �X

Ejercicio Muestre que (0, 1) � [0, 1] . Concluya que (0, 1) � [0, 1) � (0, 1] � [0, 1] .

Solución Notemos que

(0, 1) � [0, 1] � (�1, 2) y (0, 1) � (�1, 2)

Por el corolario 4.1, se sigue que (0, 1) � [0, 1] .

Para las otras equipotencias, notemos que

(0, 1) � [0, 1) � [0, 1] y (0, 1) � (0, 1] � [0, 1] .

De nuevo, aplicamos el corolario 4.1. �X

Por los ejemplos anteriores, podemos afirmar que todos los intervalos acotados de R

tienen la misma cardinalidad. ¿Qué podemos decir de los intervalos no acotados?

Primero, notemos que R+ = (0,+∞) � (1,+∞) mediante la traslación x 7! x + 1.Usando la función inverso x 7! 1

x tenemos que (1,+∞) � (0, 1) . Luego,

R+ � (0, 1) .

Por otro lado, la función exponencial x 7! ex es una biyección de R en R+. Por tanto,

R � R+ � (0, 1) .


Usando el teorema de Schröder-Bernstein, se puede mostrar que los otros tipos deintervalos también tiene la cardinalidad de R. Por ejemplo,

(0, 1) � (a, a+ 1) � (a,+∞) � [a,+∞) � R � (0, 1) .

Análogamente, se muestran los otros posibles casos. Resumiendo,

Proposición 4.4 Todos los intervalos no vacíos de R son equipotentes a R. En particular,

(0, 1) � R.

Recordemos que

BA := f f j f : A! B es funcióng y 2A := f f j f : A! f0, 1g es funcióng .

Lema 4.4 Si A � C y B � D, entonces BA � DC.

Prueba. Fijemos biyecciones ϕ : A! C y ψ : B! D.

Dada una función f : A! B, tomamos F ( f ) : C ! D tal que el siguiente diagrama

CF( f )��! D

ϕ�1??y x??ψ

A ��!f

B

conmute; esto es, F ( f ) = ψ � f � ϕ�1. Esto define una función F : AB! CD.

Afirmamos que F es biyectiva. De hecho, sea G : CD ! AB dada por

G (g) = ϕ � g � ψ�1, para toda g : C ! D.

Es fácil verificar que G es la inversa de F. �

Proposición 4.5 Para todo conjunto A : P (A) � 2A.

Prueba. Sea F : P (A) ! 2A definida como sigue: dado B � A, hacemos F (B) =χB, donde

χB (x) =�

1 si x 2 B0 si x /2 B.

es la función característica de B en A.

Veamos que F es inyectiva. Si F (B) = F (B0) , entonces para todo x 2 A :

x 2 B sii χB (x) = 1 sii χB0 (x) = 1 sii x 2 B0.

Por tanto, B = B0.Ahora, veamos que F es sobreyectiva: dada f : A! f0, 1g , tomamos

B = f�1 (1) = fx 2 A j f (x) = 1g .

Es claro que χB = f . �


Corolario 4.3 Si A � B, entonces

2A � 2B y P (A) � P (B) .

En lo que sigue supondremos válido un resultado clásico del análisis real: todonúmero real α tiene una única representación decimal

α = m+∞

∑n=1

αn

10n ,

donde m = bαc es la parte entera de α y αn 2 f0, 1, . . . 9g son dígitos decimales.

De hecho, los números de la formak

10n tiene dos representaciones. Por ejemplo,

3105 = 0.000 03 0000 � � � = 0.000 02 99999 � � � � � �

Por conveniencia, tomamos la representación que termina en infinitos nueves.

Proposición 4.6 R � P (N) .

Prueba. Sea C : R! P(Q) dada por

C (α) = fr 2 Q j r < αg .

Por la densidad de Q en R, dados α < β números reales, existe un racional r tal queα < r < β. Luego, C es inyectiva. Así, R � P(Q). Como Q �N, por el corolario 4.3,P(Q) � P (N) . Por el lema 4.2 (b), R � P (N) .

Recíprocamente, sea F : 2N ! [0, 1] definida por

F (s) = 0.s0 s1 s2 s3 � � � =∞

∑n=0

sn

10n+1 .

Dado que todo número real tiene un única representación decimal, F es inyectiva.Por tanto,

P (N) � 2N � [0, 1] � R.

De nuevo, por el lema 4.2,P (N) � R. Basta aplicar el teorema de Schröder-Bernstein.�

En vista de los resultados obtenidos hasta ahora, se podría creer que cualquier parde conjuntos infinitos son equipotentes entre sí. Uno de los grandes descubrimientosde Cantor es la existencia de distintas cardinalidades infinitas.

Teorema de Cantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Para todo conjunto A : A � P (A) ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Debemos probar que A � P (A) y A 6� P (A) .

Es fácil ver que la función f : A! P (A) , dada por f (a) = fag , es inyectiva. Luego,A � P (A) .


Supongamos que existe g : A! P(A) biyectiva. Sea

D := fa 2 A j a /2 g (a)g .

Como g es sobreyectiva, existe d 2 A tal que g (d) = D. Entonces,

d 2 D sii d /2 g (d) sii d /2 D.

Absurdo. Luego, no puede existir una biyección de A en P(A) y, por lo tanto, A 6�P(A). �

Aplicando el teorema de Cantor y la proposición 4.6, obtenemos que

N 6� R.

Cantor probó este importante resultado por primera vez en 1873. En 1891, él ofrecióuna segunda demostración mediante su famoso método de diagonalización.

Teorema 4.2 (Cantor) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

El conjunto N no es equipotente a R... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Dado que R � (0, 1) y N � Z+, basta probar que Z+ 6� (0, 1) .

Razonemos por el absurdo y supongamos que existe una biyección f : Z+ ! (0, 1) .Organicemos ran ( f ) = (0, 1) del siguiente modo:

f (1) = 0� α11 α12 α13 α14 � � � α1n � � �

f (2) = 0� α21 α22 α23 α24 � � � α2n � � �

f (3) = 0� α31 α32 α33 α34 � � � α3n � � �

f (4) = 0� α41 α42 α43 α44 � � � α4n � � �...

. . .f (n) = 0� αn1 αn2 αn3 αn4 � � � αnn � � �

.... . .

donde cada αnm es un dígito decimal. Ahora, definamos β = 0.β1β2 � � � 2 (0, 1) pordiagonalización. Para cada n � 1 :

βn =

8<: 1, si αnn 6= 1.

5, si αnn = 1.

Por construcción, βn 6= αnn, para todo n. Luego, β 6= f (n) , para todo n.

Por tanto, β /2 ran ( f ) . Absurdo, dado que f es sobreyectiva. �Definición Sea A un conjunto arbitrario.

(a) Si A �N, decimos que A es enumerable.


(b) Si A � R, decimos que A tiene la potencia del continuo.

Proposición 4.7 R�R � R y C � R.

Prueba. Primero usemos el teorema de Schröder-Bernstein para mostrar que (0, 1)�(0, 1) � (0, 1) .

(i) (0, 1)� (0, 1) � (0, 1) . Dados α, β 2 (0, 1] , hacemos

f (α, β) = f (0.α1α2α3 � � � , 0.β1β2β3 � � � ) = 0.α1β1α2β2α3β3 � � � .

Es claro que f está bien definida y que f es inyectiva.

(ii) (0, 1) � (0, 1) � (0, 1) . Dado γ 2 (0, 1] , hacemos g (γ) = (γ, 12 ). Es inmediato

que g es inyectiva.

Aplicando el lema 4.3 y la proposición 4.4, tenemos que

R�R � (0, 1)� (0, 1) � (0, 1) � R.

Dado que C = R�R dotado de ciertas operaciones, se sigue que C tiene la potenciade continuo. �

Corolario 4.4 Para todo k : Rk � R.

Los resultados que hemos obtenido en esta sección se pueden resumir en la sigu-iente tabla.

Conjuntos Conjuntos que tienenenumerables la potencia del continuo

N R

E, O [0, 1] , (0, 1)

Cualquier intervalo de R

Z, Q C

N�N, Nk R�R, Rk

P (N) , 2N


Es natural que surja la siguiente pregunta.

¿Todo conjunto infinito A de números reales es enumerable o tiene la potencia del continuo?

En 1878, Cantor planteó que la respuesta es afirmativa. Dicha conjetura se denominóla Hipótesis del Continuo de Cantor y se convirtió en uno de los problemas másimportantes de la teoría de conjuntos.

Prueba del teorema de Schröder-BernsteinSean f : A! B y g : B! A funciones inyectivas.

Definamos una familia de subconjuntos de A mediante recursión:

An+1 = (g � f ) [An] y A0 = A� ran (g) .

Hagamos Bn = f [An] . Luego,

An+1 = g [ f [An]] = g [Bn] .

Definamos h : A! B por

h (x) =�

f (x) , si x 2 An, para algún n.g�1 (x) , en caso contrario.

Afirmamos que h está bien definida.

Supongamos que x 2 An, para algún n. Notemos que Am � A para todo m. Luego,x 2 A. Por tanto, h (x) = f (x) está bien definida. En el otro caso, x /2 An, para todon. En particular, x /2 A0. Luego, x 2 ran (g) . Dado que g es inyectiva, h (x) = g�1 (x)está bien definida.

Veamos que h es inyectiva.

Sean a1 6= a2 en A. Como f y g�1 son inyectivas, basta considerar el caso en quea1 2 An para cierto n y a2 /2 Am, para todo m. Luego,

h (a1) = f (a1) y h (a2) = g�1 (a2) .

Notemos que f (a1) 2 f [An] = Bn. Luego, h (a1) 2 Bn. Si h (a2) 2 Bn, entonces

a2 = g�

g�1 (a2)�= g (h (a2)) 2 g [Bn] = An+1.

Absurdo. Por tanto, h (a1) 6= h (a2) .

Mostremos que h es sobreyectiva.

aSea b 2 B. Razonemos por casos. Si b 2 Bn, para algún n, entonces b 2 f [An] .Luego, existe a 2 An tal que

h (a) = f (a) = b.


En caso contrario, b /2 Bn, para todo n. Sea a = g (b) . Notemos que a 2 ran (g) .Luego, a /2 A0. Como b /2 Bn y g es inyectiva, tenemos que

g (b) /2 g [Bn] = An+1.

Por tanto, a /2 An+1, para todo n. En este caso,

h (a) = g�1 (a) = g�1 (g (b)) = b.

En ambos casos, b 2 ran (h) .

Como h es una función biyectiva, podemos concluir que A � B. �

4.2 Conjuntos Finitos y Contables

Conjuntos FinitosIntroducimos la siguiente notación. Para n 2N :

J0 = ∅ y Jn = fk 2N j 1 � k � ng , para n � 1.

Por ejemplo, J3 = f1, 2, 3g . Por inducción, es fácil mostrar que

Jn+1 = Jn [ fn+ 1g .

Definición Sea A un conjunto arbitrario.

(a) Si A � Jn, para algún n 2N, decimos que A es finito.

(b) Si A no es finito, decimos que A es infinito.

Si f : Jn ! A es una biyección, entonces es costumbre denotar f (k) = ak, para1 � k � n, y escribir

A = fa1, a2, . . . , ang .

Intuitivamente, el número natural n cuenta el número de elementos de A. Para for-malizar adecuadamente esta idea, debemos asegurarnos que un conjunto finito sólopuede estar en correspondencia uno a uno con un único Jn. Esto es, al contar sus el-ementos siempre obtenemos el mismo resultado. Para ello, necesitamos el siguienteresultado debido a Dirichlet.

Principio del Palomar (versión 1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Para todo n : si f : Jn ! Jn es una función inyectiva, entonces f tiene que ser sobreyectiva... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Usemos inducción sobre n. El paso base es inmediato. Para el paso inductivo,supongamos que el enunciado es válido para n.

Ahora, sea f : Jn+1 ! Jn+1 una función inyectiva. Consideremos dos casos.

4.2. Conjuntos Finitos y Contables 83

(a) f [Jn] � Jn. Dado que f es inyectiva, f (n+ 1) = n + 1 y f � Jn : Jn ! Jn esinyectiva. Por hipótesis inductiva, f � Jn es sobre. Por tanto,

ran ( f ) = ran ( f � Jn) [ f f (n+ 1)g = Jn [ fn+ 1g = Jn+1.

Esto es, f es sobre.

(b) f [Jn] ( Jn. Luego, existe k � n tal que f (k) = n + 1. Reordenemos f de unmodo conveniente: sea g : Jn+1 ! Jn+1 dada por

g (i) =

8<: f (i) , si i 6= k, n+ 1.f (n+ 1) , si i = k.

n+ 1, si i = n+ 1.

Notemos que g también es inyectiva, ran (g) = ran ( f ) y g[Jn] � Jn. Razonandocomo en el caso (a), g es sobre. Por tanto,

ran ( f ) = ran (g) = Jn+1.

Por inducción matemática, podemos concluir que la afirmación es válida para todon. �

Corolario 4.5 Sea A un conjunto finito. Si σ : A ! A es una función inyectiva, entoncesσ es sobreyectiva.

Prueba. Como A es finito, sean n 2 N y g : A ! Jn biyectiva. Consideramos elsiguiente diagrama

Jnf��! Jn

g�1??y x??g

A ��!σ

A

Como f es inyectiva, por el principio del palomar, f es sobre. Luego, σ también essobre. �

El principio del palomar se puede enunciar del siguiente modo.

Principio del Palomar (versión 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

(a) Si B es un subconjunto propio de un conjunto finito A, entonces A no es equipotentea B.

(b) Si A es equipotente a un subconjunto propio de sí mismo, entonces A es infinito.

.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Razonemos por el absurdo. Supongamos que B ( A y que f : A ! B esbiyectiva. Luego, la extensión f : A! A es una función inyectiva con ran ( f ) = B (A. Lo cual contradice el corolario anterior. �

Corolario 4.6 Sean m, n 2N. Si Jm � Jn, entonces m = n.


Prueba. Supongamos que Jm � Jn. Por la ley de tricotomía:

m < n o n < m o n = m.

Si m < n, entonces Jm ( Jn. Por la versión 2 del principio del palomar, Jn no puedeser equipotente a Jm. Análogamente, si n < m, Jm no puede ser equipotente a Jn. Portanto, la única posibilidad es que m = n. �

Corolario 4.7 Para todo conjunto finito A existe un único n 2N tal que A � Jn.

Definición El único n 2 N que satisface A � Jn se denomina el cardinal de A y sedenota por n = jAj .

Sean A y B conjuntos finitos. Entonces

A � B si y sólo si jAj = jBj .

En efecto, sean jAj = n y jBj = m. Entonces

A � B sii Jn � Jm sii n = m sii jAj = jBj .

Intuitivamente, todo subconjunto de un conjunto finito es finito con cardinalidadmenor o igual.

Lema 4.5 Si K � Jn, entonces existe k � n tal que

K � Jk y jKj = k.

Prueba. Usemos inducción sobre n. El paso base es trivial. Para el paso inductivo,supongamos que el enunciado es válido para n.

Sea K � Jn+1. Consideremos dos casos.

(a) (n+ 1) /2 K. Luego, K � Jn. Por hipótesis inductiva, existe k tal que K � Jk yjKj = k � n < n+ 1.

(b) (n+ 1) 2 K. Luego, K = I [ fn+ 1g , donde I = K� fn+ 1g � Jn. Por hipóte-sis inductiva, existe i � n tal que I � Ji. Sea g : Ji ! I biyectiva. Extendamos g deun modo natural.

Sea eg : Ji+1 ! K dada por

eg (j) = � f (j) , si j � i.n+ 1, si j = i+ 1.

Tomando k = i+ 1, tenemos que K � Jk y jKj = k � n+ 1. �

Corolario 4.8 Si existe una función f : A! Jn inyectiva, entonces A es finito y jAj � n.

Teorema 4.3 Sea A un conjunto finito. Si B � A, entonces B es finito y jBj � jAj . SiB ( A, jBj < jAj .


Prueba. Sea f : A! Jn biyectiva. Si B � A, entonces la restricción f �B: B! Jn esinyectiva. Por el anterior corolario, B es finito y jBj = k � n = jAj .

Ahora, sea B ( A. Si jBj = jAj , entonces B � A. Pero esto contradice el principiodel palomar. �

Corolario 4.9 (a) Si A es enumerable, entonces A es infinito.

(b) Si A tiene un subconjunto infinito, entonces A es infinito.

(c) Si A � B y B es infinito, entonces A también es infinito.

Teorema 4.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

N, Z, Q, R y C son conjuntos infinitos... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Proposición 4.8 Sean A y B conjuntos finitos. Si A \ B = ∅, entonces A [ B también esfinito y

jA [ Bj = jAj+ jBj .

Prueba. Sean jAj = m y jBj = n. Usemos inducción sobre n para mostrar que

A [ B también es finito y jA [ Bj = m+ n.

Paso base. Si n = 0, entonces B = ∅. Así, A [ B = A es finito y jA [ Bj = jAj = m =m+ 0.

Paso inductivo. Supongamos que el enunciado es válido para todo conjunto de cardi-nalidad n.

Sea B un conjunto finito con jBj = n + 1. Luego, podemos fijar b 2 B y tomarB0 = B� fbg . Entonces, es claro que B0 es finito, jB0j = n y A \ B0 = ∅. Entonces,por hipótesis inductiva, A [ B0 es finito y jA [ B0j = m+ n. Luego, tenemos que

A [ B0 � Jm+n y fbg � fm+ n+ 1g .

Por el lema 4.1, se sigue que

(A [ C) [ fbg � Jm+n [ fm+ n+ 1g = Jm+n+1.

Por tanto, A [ B es finito y jA [ Bj = m+ (n+ 1) . �En la proposición 4.8, podemos quitar la restricción de que A y B sean disjuntos.

Proposición 4.9 Si A y B son conjuntos finitos, entonces A [ B también es finito y

jA [ Bj = jAj+ jBj � jA \ Bj .

Prueba. Sean A y B conjuntos finitos. Como B� A � B, entonces B� A es finito.Notemos que

A [ B = A [ (B� A) y A \ (B� A) = ∅.


Por la proposición 4.8, A [ B es finito y

jA [ Bj = jAj+ jB� Aj . (4.1)

Es obvio que A \ B es finito y que

B = (B� A) [ (A \ B) y (B� A) \ (A \ B) = ∅.

De nuevo, por la proposición 4.8, tenemos que jBj = jB� Aj+ jA \ Bj . Luego,

jB� Aj = jBj � jA \ Bj . (4.2)

Ahora, basta sustituir (4.2) en (4.1). �Notemos que cuando A \ B = ∅ :

jA [ Bj = jAj+ jBj � jA \ Bj = jAj+ jBj � j∅j = jAj+ jBj .

Luego, las proposiciones 4.8 y 4.9 son equivalentes.

Proposición 4.10 Si A y B son conjuntos finitos, entonces A� B también es finito y

jA� Bj = jAj � jBj .

Prueba. Sean jAj = m y jBj = n. Usemos inducción sobre n para mostrar que

A� B también es finito y jA� Bj = m � n.

Paso base. Si n = 0, entonces B = ∅. Así, A� B = ∅ es finito y jA� Bj = j∅j = 0 =m � 0.

Paso inductivo. Supongamos que el enunciado es válido para todo conjunto de cardi-nalidad n.

Sea B un conjunto finito con jBj = n + 1. Luego, fijemos b 2 B y hagamos B0 =B� fbg . Entonces, B0 es finito y jB0j = n. Entonces, por hipótesis inductiva, A� B0

es finito y jA� B0j = m � n. Notemos que

A� B = A� (B0 [ fbg) = A� B0 [ A� fbg .

Es claro que A� fbg � A � Jn. Por la proposición 4.8, se sigue que A� B es finito yque

jA� Bj =��A� B0

��+ jA� fbgj = m � n+ n = m � (n+ 1) .

�Para la exponenciación se cumple un resultado análogo. Su prueba queda como

ejercicio.

Proposición 4.11 Sean A y B finitos con jAj = m y jBj = n. Entonces BA también esfinito y

j BA j = nm.

Corolario 4.10 Si A es finito, entonces P (A) también es finito y jP (A)j =��2A

�� = 2n,donde n = jAj .


Conjuntos ContablesDefinición Sea A un conjunto arbitrario.

(a) Si A es finito o enumerable, decimos que A es contable.

(b) Si A no es contable, decimos que A es no contable.

Sea A enumerable. Si f : N ! A es una biyección, se suele denotar f (n) = an yescribir

A = fan j n � 0g = fang∞n=0 .

También se suele decir que f es una enumeración de A.

Teorema 4.5 Si A es un subconjunto infinito de N, entonces A es enumerable.

Prueba. Sea A un subconjunto infinito de N. Primero, notemos que para todon 2 A, existe m 2 A tal que n < m. En caso contrario, existiría n 2 A tal que paratodo m 2 A : m � n. Luego, A � Jn. Absurdo, pues A es infinito.

Ahora, definamos una biyección de N en A por recursión. Sea h : A! A dada por

h (n) = min fm 2 A j n < mg .

Por el comentario anterior y el principio del buen orden, h está bien definida. Por elteorema de recursión, existe una función f : N! A tal que

a0 = min A y ak+1 = h (ak) = min fm 2 A j ak < mg .

Afirmamos que f es biyectiva.

Notemos que ak < ak+1, para todo k. Por tanto, f es inyectiva.

Supongamos que f no es sobreyectiva. Por el principio del buen orden, sea n =min (A� ran ( f )) .

Como a0 = min A 2 ran ( f ) , entonces a0 < n. Supongamos que ak < n. Por defini-ción, ak+1 � n. Como n /2 ran ( f ) , entonces ak+1 < n. Por inducción, ak < n, paratodo k.

Por tanto, f : N ! Jn es una función inyectiva. Por el corolario 4.8, N sería finito,absurdo. Luego, f tiene que ser sobreyectiva. �

Corolario 4.11 Todo subconjunto infinito de un conjunto enumerable es enumerable.

Combinando el anterior corolario con el teorema 4.3, obtenemos el siguiente resul-tado.

Teorema 4.6 Todo subconjunto de un conjunto contable es contable.

Ejercicio Sea A 6= ∅. Muestre que A es contable si y sólo si A �N.

Solución (!) Si A es finito, existe f : A ! Jn biyectiva. Luego, f : A ! N esinyectiva.

Si A es enumerable, es claro que existe f : A ! N inyectiva. En cualquier caso,A �N.


( ) Supongamos que existe una función f : A ! N inyectiva. Sea B = f [A] .Como B � N, entonces B es contable. Dado que A � B, se sigue que A también escontable. �X

En la sección 4.1, desarrollamos varias propiedades de los conjuntos enumerablesen relación a los sistemas numéricos. A continuacion, enunciamos las generaliza-ciones de dichos resultados.

Proposición 4.12 Sean A y B conjuntos enumerables. Si A \ B = ∅, entonces A [ Btambién es enumerable.

Prueba. Por hipótesis,

A �N � E y B �N � O.

Dado que A \ B = ∅, por el lema 4.1, tenemos que A [ B � E[O = N. �

Proposición 4.13 Si A y B son conjuntos enumerables, entonces A�B también es enumerable.

Prueba. Por hipótesis, A �N � B. Por el lema 4.3,

A� B �N�N.

Pero, por la proposicion 4.2, A� B �N. �Razonando por casos, se puede mostrar que los conjuntos contables son cerrados

bajo las operaciones Booleanas básicas.

Corolario 4.12 Si A y B son conjuntos contables, entonces A [ B, A \ B y A� B tambiénson contables.

Si A es enumerable, entonces

P (A) � P (N) � R 6�N.

Proposición 4.14 Si A es enumerable, entonces P (A) tiene la potencia del continuo y, portanto, es no contable.

Ejercicio El conjunto de Cantor C se define como el conjunto de todos los númerosreales de la forma

∞

∑n=1

an

3n ,

donde cada an es un dígito ternario 0 o 2. Use el método de la diagonal y muestreque C es no contable.

Solución Razonemos por el absurdo y supongamos que C � Z+. Sea f : Z+ !C una función biyectiva y escribamos

f (m) =∞

∑n=1

amn

3n , donde amn 2 f0, 2g , 8m, n � 1.

Definamos

bn =

�0, si ann = 2.2, si ann = 0.

4.3. Cardinales con el Axioma de Elección 89

Sea β =∞

∑n=1

bn

3n . Es claro que bn 2 f0, 2g , 8n � 1. Por definición del conjunto de

Cantor, β 2 C.

Como f es sobreyectiva, existe m � 1 tal que β = f (m) =∞

∑n=1

amn

3n .

En particular, bm = amm. Pero, por construcción,

bm = 0 sii amm = 2 sii bm = 2.

Absurdo. Luego, el conjunto de Cantor C no puede ser contable. �X

De hecho, el conjunto de Cantor C tiene la potencia del continuo. Basta notar que

C � f0, 2gN � f0, 1gN = 2N � R.

4.3 Cardinales con el Axioma de Elección

Después de los resultados obtenidos sobre conjuntos enumerables y no contables,parece natural afirmar que todo conjunto infinito tiene un subconjunto enumerable.

Uno razonaría del siguiente modo. Sea A un conjunto infinito arbitrario. ComoA 6= ∅, elijamos a0 2 A. Como A es infinito, A� fa0g 6= ∅. Luego, elijamos a1 2 Acon a1 6= a0. De nuevo, A� fa0, a1g 6= ∅. Luego, podemos elegir a2 2 A distinto dea0 y a1. Después de n pasos, habriamos elegido a0 6= a1 6= a2 6= � � � 6= an�1. Dado queA es infinito, podemos elegir an 2 A distintos de todos los anteriores (la elección dean depende de los valores previos ak). Luego, el conjunto

E = fang∞n=0

sería un subconjunto enumerable de A.A primera vista, el anterior razonamiento inductivo no parece problemático. Se

pensaría que para formalizarlo bastaría usar el teorema de recursión. Pero, paraaplicar el teorema de recursión, es necesario contar, de antemano, con una funciónque dado un subconjunto finito de A elija un elemento de A que no esté en dichoconjunto. El problema surge en que necesitamos un principio que nos garantice laexistencia de dicha función. Esto nos lleva a introducir el siguiente axioma funda-mental de la teoría de conjuntos.

Axioma de Elección (AC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sea fAigi2I una familia no vacía de conjuntos.

Si para todo i 2 I : Ai 6= ∅, entonces existe una función f con dominio I tal que

f (i) 2 Ai, para todo i 2 I.

.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

La utilidad esencial de AC es que nos permite realizar infinitas elecciones arbitrariasy simultáneas. Si hacemos finitas elecciones o damos instrucciones de cómo elegir, no


se necesita apelar a AC.

Ilustremos la anterior afirmación con el siguiente ejemplo debido a Russell. Supong-amos que tenemos una familia enumerable de pares de zapatos. Si elegimos el zapatoizquierdo de cada par, no necesitamos AC (dado que estamos dando una regla paraelegir). Ahora, supongamos que tenemos una familia enumerable de pares de me-dias. Dado que no hay modo de distinguir una media de la otra y tenemos infinitospares, necesitamos AC si queremos elegir una media de cada par.

En las siguientes aplicaciones, usaremos una forma equivalente de AC conocidacomo el lema de Zorn. De hecho, formularemos una variante del lema de Zorn rel-ativa a familias A de conjuntos parcialmente ordenadas por la relación de inclusión� .

Definimos una cadena (chain) como una familia no vacía C de conjuntos tal quepara todo X, Y 2 C se cumple que X � Y o Y � X. En otras palabras, una cadena esuna colección no vacía de conjuntos que es totalmente ordenada por � .

Decimos que M 2 A es maximal si no existe X 2 A tal que M � X y M 6= X.

Lema de Zorn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sea A una familia no vacía de conjuntos. Si para toda cadena C � A se cumple que[C 2 A,

entonces A tiene un elemento maximal... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Para aplicar el lema de Zorn, consideraremos familias de funciones (con cierta propiedad)parcialmente ordenadas por extensión. Decimos que la función g extiende a la fun-ción f si

dom ( f ) � dom (g) y 8x 2 dom ( f ) : f (x) = g (x) .

Escribimos f � g para indicar que g es una extensión de f . Como es común enmatemáticas, identificaremos una función f con su grafo

Γ f = f(x, f (x)) j x 2 dom ( f )g .

Bajo esta identificación, tenemos que

f � g sii Γ f � Γg.

Por consiguiente, si F es una familia no vacía de funciones, se cumple quenΓ f j f 2 F

oes una cadena sii F está totalmente ordenada por extensión.

Más aún, en dicha situación, existe una función bien definida h que satisface

Γh =[

f2FΓ f y dom (h) =

[f2F

dom ( f ) .


Por tanto, h está unívocamente determinada al decir que h es una extensión de f paratoda f 2 F y que el dominio de h es la unión de los dominios de las funciones f 2 F .Nos referiremos a h como la unión de la familia totalmente ordenada de funcionesF .

Teorema 4.7 Sean A y B conjuntos no vacíos. Las siguientes condiciones son equivalentes:

(a) Existe una función f : A! B inyectiva.

(b) Existe una función g : B! A sobreyectiva.

Prueba. (a)! (b) Sea f : A! B inyectiva. Fijemos a 2 A. Definamos g : B! Apor

g (y) =�

f�1 (y) , si y 2 ran ( f ) .a, en otro caso.

Es fácil verificar que g es sobreyectiva. De hecho, para todo x 2 A :

g ( f (x)) = x.

(b)! (a) Sea g : B! A sobreyectiva. Consideremos la familia

A = fϕ : C ! B j C � A y 8x 2 C : g (ϕ (x)) = xg .

Tomemos a 2 A. Como g es sobre, existe b 2 B tal que a = g (b) . Sea ϕ : fag ! Bdada por ϕ (a) = b. Así, ϕ 2 F y F 6= ∅.

Ahora, ordenemos parcialmente a F por extensión. Sea G una cadena de F . Es fácilverificar que

h =[G 2 F .

Por el lema de Zorn, existe un elemento maximal f 2 F .

Afirmamos que dom ( f ) = B. En caso contrario, existe a 2 A tal que a /2 dom ( f ) .Como g es sobre, existe b 2 B tal que g (a) = b. Extendamos f del modo obvio:

f 0 = f [ f(a, b)g .

Luego, f 0 2 F y que f 0 es una extensión propia de f . Absurdo, pues se contradice lamaximalidad de f en F . Por último, basta notar que f es inyectiva. �

Corolario 4.13 Sea A 6= ∅. Entonces

A es contable sii existe f : A!N inyectiva sii existe g : N! A sobreyectiva.

Ahora, mostremos que todo conjunto infinito tiene un subconjunto enumerable.Primero, necesitamos introducir una noción técnica. Diremos que S es un segmentoinicial de N si

S = N o existe n 2N tal que S = Jn.

Teorema 4.8 Si A es infinito, entonces existe f : N! A inyectiva.


Prueba. Sea A infinito. Definamos

F = fϕ : S! A j S es un segmento inicial de N y ϕ es inyectivag .

Es rutinario verificar que el lema de Zorn se aplica a F dando lugar a una funciónmaximal f 2 F .

Afirmamos que dom ( f ) = N. En caso contrario, existe n tal que dom ( f ) = Jn.Sea B = ran ( f ) . Como f es inyectiva, f : Jn ! B es biyectiva. Por tanto, B es unsubconjunto finito de A. Como A es infinito, existe a 2 A� B. Definamos

f 0 = f [ f(n+ 1, a)g .

Es claro que dom ( f 0) = Jn+1 y f 0 es inyectiva. Así, f 0 2 F extiende propiamente af , absurdo. �

Corolario 4.14 Todo conjunto infinito A contiene un subconjunto enumerable.

En 1888, Richard Dedekind propusó la siguiente definición alternativa de “con-junto infinito”.

Definición Un conjunto A se llama Dedekind infinito si A es equipotente a un sub-conjunto propio B ( A. Un conjunto Dedekind finito es un conjunto que no es Dedekindinfinito.

Por el principio del palomar,

Si A es Dedekind infinito, entonces A es infinito.

El recíproco sólo se cumple si asumimos AC.

Teorema 4.9 Un conjunto A es infinito si y sólo si es Dedekind infinito.

Prueba. Supongamos que A es infinito. Sea E = fangn un subconjunto enumerablede A. Luego,

E� fa0g � Z+ �N � E.

Sea B := A� fa0g ( A. Notemos que

(A� E) \ (E� fa0g) = ∅ = (A� E) \ E.

Por el lema 4.1,

B = (A� E) [ (E� fa0g) � (A� E) [ E = A.

Por tanto, A es Dedekind infinito. �Ahora probemos un resultado que tiene muchas aplicaciones en el análisis, el ál-

gebra y la topología. Primero, enunciemos la versión para conjuntos enumerables.

Teorema 4.10 Sea fEngn una sucesión de conjuntos enumerables. Entonces

E =∞[

n=0En es enumerable.


Prueba. Por AC, podemos elegir una función biyectiva ϕn : N! En, para cada n.

Definamos g : N�N! E por

g (m, n) = ϕn (m) , para todo (n, m) 2N2.

Veamos que g es sobreyectiva.

Sea x 2 E . Entonces, x 2 Ek para algún k. Como ϕk es sobreyectiva, existe i tal queϕk (i) = x. Luego,

g (i, k) = ϕk (i) = x.

Esto es, x 2 ran (g) .

Sea f : N ! N �N biyectiva. Luego, h = g � f : N ! E es sobreyectiva. Portanto, E es contable.

Pero, E1 es un subconjunto infinito de E . Por tanto, E es enumerable. �Ahora, enunciemos la versión para conjuntos contables.

Unión contable de contables es contable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Supongamos que I es contable y que Ai es contable para todo i 2 I. Entonces

A =[i2I

Ai es contable.

.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Si I es finito, aplique inducción matemática. Supongamos que I es enu-merable. Sin perdida de generalidad, podemos tomar I = N. También podemossuponer que An � En y En es enumerable. Luego, A es un subconjunto de un con-junto enumerable E . Por tanto, A es contable. �

Apliquemos los anteriores teoremas para mostrar la existencia de incontables númerostrascendentes.

Ejercicio Muestre que Z [x] es enumerable.

Solución Sea I = N�N. Para todo i = (n, m) 2 I, definamos el conjunto

Pi = fanxn + � � �+ a0 2 Z [x] j ja0j+ � � �+ janj = mg .

Dados n, m 2 N, hay finitas n-tuplas (k0, . . . , kn) de números naturales que satis-facen la ecuación

k0 + � � �+ kn = m.

(ver sección ??). Por tanto, Pi es finito, para todo i 2 I. Ahora, es claro que

Z [x] =[i2I

Pi.

Esto es, Z [x] es una unión enumerable de conjuntos finitos. Luego, Z [x] es contable.

Pero es obvio que Z [x] es infinito. Por tanto, Z [x] es enumerable. �X

Decimos que α 2 C es algebraico si α es solución de una ecuación de la formap(x) = 0, con p(x) 2 Z[x]. En caso contrario, se dice que α 2 C es trascendente.


Proposición 4.15 (Cantor) El conjunto A de los números algebraicos es enumerable.

Prueba. Dado p (x) 2 Z [x] , definamos el conjunto

Ap = fα 2 C j p (α) = 0g .

Por el Teorema Fundamental del Álgebra, todo polinomio con coeficientes reales de gradon tiene a lo sumo n raíces complejas. Luego, Ap es finito, para todo p 2 Z [x] .

De la definición de número algebraico, se sigue que

A =[

p2Z[x]

Ap.

Así, A es una unión enumerable de conjuntos finitos. Por tanto, A es contable.

Ahora, notemos que Z es subconjunto de A (dado a 2 Z, tome el polinomio p (x) =x� a). Por lo cual, A es infinito. Podemos concluir que A es enumerable. �

Corolario 4.15 (Cantor, 1874) El conjunto de números trascendentes es no contable.

Prueba. Razonemos por el absurdo y supongamos que C�A es contable. Luego,

C = A[ (C�A)

sería contable. Absurdo, pues C � R. �

4.4 Aritmética Cardinal

En la sección 4.2, definimos el número cardinal de un conjunto finito. Usando AC oel axioma de regularidad (ver [Je03, p.65]), es posible extender la noción de númerocardinal a conjuntos infinitos. Dado que dichos tratamientos son sofisticados y estánmás alla del alcance de este curso, preferimos introducir los números cardinales ax-iomáticamente.

Axiomas de cardinalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Para todo conjunto A existe su número cardinal jAj de modo que se cumple

(a) Para todo conjunto A y B :

A � B si y sólo si jAj = jBj .

(b) Para todo conjunto finito A, jAj es el único n 2N para el cual A � Jn.

.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4.4. Aritmética Cardinal 95

Luego, los cardinales finitos son los números naturales. Si un cardinal κ no esfinito, se dice que es un cardinal infinito (o transfinito).

El cardinal de los conjuntos enumerables se denota por aleph cero:

@0 = jNj .En general, un aleph es el número cardinal de un conjunto bien ordenado infinito.

Introduzcamos las operaciones cardinales.

Definición Supongamos que

κ = jAj y λ = jBjDefinimos

suma cardinal κ + λ = jA [ Bj , si A \ B = ∅

producto cardinal κ � λ = jA� Bj

exponenciación κλ =��AB

�� = jf f j f : B! A es funcióngj

Ejercicio Dados conjuntos arbitrarios A y B, muestre que existen conjuntos A0, B0

tales queA � A0, B � B0 y A0 \ B0 = ∅.

Solución Tome A0 = A� f0g y B0 = B� f1g . Sean f : A ! A0 y g : B ! B0

dadas porf (a) = (a, 0) y g (b) = (b, 1) .

Es inmediato que f y g son biyectivas. También es claro que A0 \ B0 = ∅. �X

Por el ejercicio anterior, la definición de suma cardinal tiene sentido. Ahora, por loslemas 4.1, 4.3 y 4.4 de la sección 4.1, las operaciones cardinales están bien definidas(no depende de representantes).

Las operaciones satisfacen las leyes aritméticas usuales (κ, λ y µ denotan númeroscardinales).

Asociatividad κ + (λ+ µ) = (κ + λ) + µ κ � (λ � µ) = (κ � λ) � µ

Conmutatividad κ + λ = λ+ κ κ � λ = λ � κ

Neutros κ + 0 = κ κ � 1 = κ

Distributividad κ � (λ+ µ) = κ � λ+ κ � µ

Leyes de Exponentes κλ+µ = κλ � κµ (κ � λ)µ = κµ � λµ

�κλ�µ

= κλ�µ κ1 = κ


Ejemplo Para todo cardinal κ : κ � 0 = 0 y κ0 = 1. En particular, 00 = 1.

Solución Sea A un conjunto de cardinalidad κ. Entonces

A�∅ = ∅ y A∅ = f f j f : ∅! A es funcióng = f∅g .

Por tanto, κ � 0 = j∅ j = 0 y κ0 = jf∅gj = 1. �X

Proposición 4.16 Para todo conjunto A de cardinalidad κ : jP (A)j = 2κ . En particular,jRj = 2@0 .

Prueba. Es obvio que jf0, 1gj = 2. Por la proposición 4.5,

jP (A)j = j 2A j = jf f j f : A! f0, 1g es funcióngj = 2jAj = 2κ .

Por último,jRj = jP (N)j = 2jNj = 2@0 .

�Definamos el orden en los números cardinales mediante la noción de dominancia.

Definición Supongamos que

κ = jAj y λ = jBj

Definimos

κ � λ sii A � B y κ < λ sii A � B.

Luego,κ < λ sii κ � λ y κ 6= λ.

Por el lema 4.2 de la sección 4.1, vemos que la anterior definición no depende delos conjuntos A y B tomados. Esto es, la relación � en los números cardinales estábien definida. Como vimos,� es una relación reflexiva, antisimétrica y transitiva encualquier colección de conjuntos. Por tanto,� es una relación de orden en la clase delos números cardinales. En particular, el teorema de Schröder-Bernstein y el teoremade Cantor se pueden enunciar del siguiente modo.

Teorema de Schröder-Bernstein . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sean κ y λ cardinales. Si κ � λ y λ � κ, entonces κ = λ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Teorema de Cantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Para todo cardinal κ : κ < 2κ . En particular, @0 < 2@0 ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Veamos cómo se comporta el orden respecto a las operaciones.


Teorema 4.11 Sean κ, λ y µ cardinales. Si κ � λ, entonces

κ + µ � λ+ µ, κ � µ � λ � µ y κµ � λµ.

Si además κ 6= 0 o µ 6= 0, entoncesµκ � µλ.

Prueba. Sean A, B y C conjuntos de cardinalidad κ, λ y µ, respectivamente, talesque A � B. Sin perdida de generalidad, podemos suponer que A � B y B \ C =∅.Se puede verificar que

A [ C � B [ C, A� C � B� C y AC � BC.

Luego, se cumplen las desigualdades enunciadas.

Para la otra desigualdad, primero supongamos que µ = 0. Por hipótesis, κ 6= 0.Luego, A 6= 0. Por tanto,

µκ = 0κ = jf f j f : A! ∅ es funcióngj = j∅ j = 0 � µλ.

Ahora, supongamos que µ 6= 0. Luego, C 6= ∅. Fijemos c 2 C. Dada una funciónf : A! C, se extiende a la función F ( f ) : B! C de un modo natural por

F ( f ) (x) =�

f (x) , si x 2 A.c, si x /2 A.

Luego, F : CA ! BC está bien definida y es inyectiva. �Introducimos @0 como notación para el cardinal de N. Debido a la proposición

4.16, el cardinal de R se denota usualmente por 2@0 . El conjunto R de todos losnúmeros reales también se denomina “el continuo”. Por esta razón, 2@0 se llama elcardinal del continuo.

El siguiente teorema resume algunas propiedades básicas del cardinal @0.

Teorema 4.12 (a) Para todo cardinal infinito κ : @0 � κ.

(b) Para todo cardinal κ : κ < @0 si y sólo si κ es finito si y sólo si κ 2N.

(c) @0 + @0 = @0 = @0 � @0.

(d) Para todo natural n : n+ @0 = @0.

(e) Para todo natural n > 0 : n � @0 = @0.

Prueba. (a) es inmediato del teorema 4.8. (b) se sigue de (a) y de la definición de@0. Por otro lado, (c) es inmediato de las proposiciones 4.12 y 4.13.

Sea n 2N. Como 0 � n < @0, por el teorema 4.11, tenemos que

@0 = 0+ @0 � n+ @0 � @0 + @0 = @0.

Si 1 � n < @0, de nuevo por el teorema 4.11, se tiene que

@0 = 1 � @0 � n � @0 � @0 � @0 = @0.

Por último, apliquemos el teorema de Schröder-Bernstein. �Ahora, enunciemos las propiedades aritméticas del cardinal 2@0 .


Teorema 4.13 (a) n+ 2@0 = @0 + 2@0 = 2@0 + 2@0 = 2@0 (n 2N) .

(b) n � 2@0 = @0 � 2@0 = 2@0 � 2@0 = 2@0 (n 2N, n > 0) .

(c)�2@0�n=�2@0�@0 = n@0 = @@0

0 = 2@0 (n 2N, n > 0) .

Prueba. (a) se sigue de las siguiente sucesión de desigualdades:

2@0 = 0+ 2@0 � n+ 2@0 � @0 + 2@0 � 2@0 + 2@0 = 2 � 2@0 = 21+@0 = 2@0 .

por el teorema de Schröder-Bernstein.

(b) Análogamente, tenemos que

2@0 = 1 � 2@0 � n � 2@0 � @0 � 2@0 � 2@0 � 2@0 = 2@0+@0 = 2@0 .

(c) Tenemos que

2@0 ��2@0�n �

�2@0�@0 = 2@0�@0 = 2@0 .

Por otro lado,

2@0 � n@0 � @0@0 �

�2@0�@0 = 2@0�@0 = 2@0 .

�

Corolario 4.16 (a) El conjunto de sucesiones infinitas de números naturales tiene cardi-nalidad 2@0 .

(b) El conjunto de sucesiones infinitas de números reales tiene cardinalidad 2@0 .

El siguiente teorema es muy útil para determinar la cardinalidad de subconjuntosde R.

Teorema 4.14 Sean A y B conjuntos tales que A � B. Si jAj = @0 y jBj = 2@0 , entonces

jB� Aj = 2@0 .

Prueba. Primero, notemos que jB� Aj > @0. En caso contrario,

2@0 = jBj = jA [ (B� A)j = jAj+ jB� Aj � @0 + @0 = @0, absurdo.

Sea C un subconjunto enumerable de B� A. Luego,

A \ C = ∅ y jA [ Cj = jAj+ jCj = @0 + @0 = @0 = jCj .

Por tanto,

jBj = jB� (A [ C)j+ jA [ Cj = j(B� A)� Cj+ jCj = jB� Aj .

Luego, jB� Aj = jBj = 2@0 . �

Corolario 4.17 (a) El conjunto de todos los números irracionales tiene cardinalidad 2@0 .

(b) El conjunto de todos los números trascendentes tiene cardinalidad 2@0 .


Los anteriores resultados muestran la importancia del número cardinal 2@0 . Luego,no es sorprendente que el problema de determinar la magnitud de 2@0 fuese tan im-portante para Cantor.

Por último, usaremos el lema de Zorn para mostrar que los números cardinales sat-isfacen la ley de tricotomía. En 1915 Friedrich Hartogs probó que la ley de tricotomíaimplica AC [Gi02, p. 551]. Por tanto, la siguiente proposición es equivalente a AC.

Proposición 4.17 (a) Sean A y B conjuntos. Entonces A � B o B � A.

(b) Sean κ y λ cardinales. Entonces κ � λ o λ � κ

Prueba. Sin perdida de generalidad, podemos tomar A, B 6= ∅. Sea

F = fϕ : C ! B j C � A y ϕ es inyectivag .

ordenada por extensión. Es fácil verificar que si G � F es una cadena, entoncesS G 2 F . Por el lema de Zorn, existe una función f : C ! B que es maximal en F .

La maximalidad de f implica que C = A o que f es sobre. En caso contrario, ex-isten a 2 A y b 2 B tales a /2 dom ( f ) y b /2 ran ( f ) . Luego, la función inyectivaf 0 = f [ f(a, b)g 2 F sería una extensión propia de f , absurdo.

Si C = A, entonces f : A ! B es inyectiva; esto es, A � B. En caso contrario,f : C ! B sería sobre. Por el teorema 4.7, existe f : B ! C � A inyectiva. Luego,B � A. �

La Hipótesis del ContinuoEn diciembre de 1873 Cantor descubrió que la cardinalidad de N es menor que lacardinalidad de R :

@0 < 2@0 .

Su prueba, mediante intervalos encajados, apareció en el primero de sus artículossobre la naciente teoría de conjuntos que publicó en el Journal de Crelle. El títulomencionaba "una propiedad del concepto [Inbegriff ] de todos los números reales al-gebraicos", a saber, que eran enumerables. En 1891, él ofreció otra demostración deque los números reales no eran enumerables usando su ingenioso argumento de ladiagonal. Sin embargo, estas pruebas no respondían a la pregunta de si existía unnúmero cardinal κ tal que

@0 < κ < 2@0 .

En su segundo artículo (1878), Cantor estudió la cardinalidad de los subconjuntos deR y Rn concluyendo que no hay cardinales entre @0 y 2@0 (ver [Ca55, p. 45] y [Gr00, p.89]). Esta es la primera vez que Cantor enunciaba la conjetura que se conocería mástarde como la Hipótesis del Continuo

2@0 = @1. (CH)

Durante décadas, Cantor intentó infructuosamente probar CH. A pesar de estos fra-casos, él siempre creyo en la validez de su conjetura.


Consciente de la relevancia de CH, David Hilbert la ubicó como el primero de los23 problemas que propusó en su famosa conferencia del Segundo Congreso Interna-cional de Matemáticos (París, 1900). Hilbert consideraba esta conjetura como uno delas preguntas abiertas fundamentales que los matemáticos debían atacar durante lassiguientes décadas e inclusive llegó a proponer un programa para su prueba. Él su-girió que inicialmente se debería demostrar otra de las conjeturas de Cantor; a saber,cualquier conjunto se puede ordenar bien.

A principios del siglo veinte, Ernst Zermelo comenzó a trabajar en los problemasde la teoría de conjuntos; en particular, consideró la idea de Hilbert como punto departida para una resolución de CH. En 1902 Zermelo publicó su primer trabajo enesta área, relacionado con la adición de cardinales transfinitos. Dos años más tarde,en 1904, tuvó éxito al dar el primer paso en el cámino sugerido por Hilbert cuandodemostró el Teorema del Buen Orden (todo conjunto se puede ordenar bien).

Para esta prueba, Zermelo introdujo el Axioma de Elección (AC), como un "prin-cipio lógico inobjetable", que le permitía construir conjuntos mediante induccióntransfinita. De hecho, AC es equivalente al Teorema del Buen Orden; lo cual, significaque es necesario usar este axioma. En 1905, Zermelo comenzó a axiomatizar la teoríade conjuntos y, en 1908, publicó sus resultados a pesar de su fracaso para obteneruna prueba de la consistencia de su sistema axiomático. En 1922, Adolf Fraenkel yThoralf Skolem independientemente mejoraron la propuesta de Zermelo. El sistemaresultante se conoce como los axiomas de Zermelo-Fraenkel (ZF).

En el siguiente Congreso de Matemáticos (Heidelberg, 1904), el matemático hun-garo Julius König anunció que CH era falsa al haber obtenido una prueba de que nopodía existir un buen orden para R. El anuncio fue tan sensacional y ampliamentereportado por la prensa, que se decidió cancelar todas las otras actividades para quetodos pudiesen escuchar su conferencia. En su demostración, König aplicaba un teo-rema probado en la tesis de doctorado de Felix Bernstein. Sin embargo, este teoremano era tan válido, en general, como Bernstein había afirmado. Al poco tiempo, Zer-melo había hallado el error. En 1905 Bernstein publicó una breve nota corrigiendo suteorema y König retiró su afirmación.

En 1908 Felix Hausdorff propuso considerar una generalización de CH al enunciarsu Hipótesis del Aleph

(8α) (2@α = @α+1). (AH)

AH es equivalente a la afirmación que actualmente se conoce como la Hipótesis Gen-eralizadada del Continuo (para todo cardinal κ, no hay un cardinal entre κ y 2κ) :

(8κ): (9λ) [κ < λ < 2κ ] . (GCH)

Después de los anteriores esfuerzos en vano por probar o refutar CH, se empezo acreer que quizás el cardinal del continuo era mayor que cualquier aleph. Pero, en1915, Friedrich Hartogs mostró que a todo cardinal κ se le podía asociar un aleph, sunúmero de Hartogs, @ (κ) , tal que

@ (κ) � κ.

Por tanto, se podía concluir que no existía un cardinal que fuese mayor que todoslos alephs. Además, la anterior propiedad le permitio a Hartogs probar que la ley deTricotomía para cardinales implica AC.

En un artículo de 1925, Alfred Tarski afirmó que GCH implica AC. Sin embargo,Tarski no probaba su afirmación, ni suministraba sugerencia para una posible prueba.Más adelante, en 1947, Wacław Sierpinski demostró la conjetura de Tarski, lo cual es-tablecía por primera vez una clara conexión entre GCH y AC. Cabe destacar que la


prueba de Sierpinski se obtenía mediante una versión más refinada del teorema deHartogs. Para más detalles se puede consultar [Gi02] o [Sm96].

En 1938, Kurt Gödel probó que GCH y AC son consistentes con ZF. Veinticinco añosdespués, Paul Cohen logró mostrar que las negaciones de CH y de AC también sonconsistentes con estos axiomas. Al tomarse juntos, estos dos resultados nos dicenque la Hipótesis del Continuo y el Axioma de Elección son independientes de losaxiomas de Zermelo-Fraenkel.


5

Combinatoria Básica

El estudio formal de la combinatoria data al menos del texto Dissertatio de Arte Com-binatoria de Gottfried Wilhelm Leibniz del siglo XVII. Sin embargo, en los últimoscincuenta años, se ha visto un enorme crecimiento en esta área, impulsado por prob-lemas y aplicaciones en muchos campos de estudio. Las aplicaciones de la combina-toria surgen, por ejemplo, en la química, al estudiar arreglos de átomos en moléculasy cristales; en la biología, en problemas sobre la estructura de genes y proteinas; enla física, en problemas de mecánica estadística; en comunicaciones, en el diseño decódigos para encriptar, comprimir y corregir errores, y, especialmente, en la cienciade computación, por ejemplo, en problemas de organización y ubicación de recursosy en el análisis de la eficiencia de algoritmos.

En esencia, la combinatoria es el estudio de arreglos. Hay tres principales ramasen este campo. La combinatoria enumerativa es la ciencia del conteo. Los problemas enesta área involucran determinar el número de arreglos bajo ciertas restricciones par-ticulares. La combinatoria existencial estudia problemas concernientes a la existenciade arreglos que posean alguna propiedad específica. La combinatoria constructiva esel diseño y el estudio de algoritmos para crear arreglos con propiedades especiales.

En este capítulo nos enfocaremos en desarrollar aspectos elementales de la combi-natoria enumerativa de conjuntos finitos. Esto es, si S es el conjunto solución de unalgún problema combinatorio y S es finito, entonces podemos estar interesados enhallar la cardinalidad de S o en enumerar los elementos de S.

104 5. Combinatoria Básica

6

Teoría de Grafos

106 6. Teoría de Grafos

Apéndice A

Construcción de los Números Reales

Las primeras dos construcciones del sistema numérico real (a partir de los racionales)fueran dadas por Richard Dedekind y Karl Weierstrass. En su monografía, Con-tinuidad y Números Irracionales (1872), Dedekind explicó que cuando él dio sus primerasclases de cálculo en 1858, se sintio profundamente insatisfecho con los fundamentosde la aritmética. Aunque reconocía la importancia de la intuición geométrica en unprimer curso de cálculo, consideraba que era pedagógicamente necesario reemplazarestos conceptos intuitivos y construir una teoría satisfactoria de las magnitudes con-tinuas que serviese como fundamento del cálculo. Dedekind señalaba que una car-acterización precisa de la continuidad de la recta numérica había eludido por mu-cho tiempo a los matemáticos e insistía que el problema era definir una “propiedadprecisa” a partir de la cual se pudiesen hacer deducciones válidas. Weierstrass, in-dependiente del trabajo de Dedekind, comenzó en 1859 una construcción de losnúmeros reales en sus clases en la Universidad de Berlín, siendo su principal mo-tivación obtener un fundamento solido para desarrollar una teoría rigurosa de lasfunciones complejas analíticas.

Aunque los cuadernos de Dedekind revelaban que él había descubierto su con-strucción de los números irracionales en Noviembre de 1858, él no se preocupo porpublicar estos resultados hasta que supó que Georg Cantor (1872) ya había pub-licado una construcción. El enfoque de Dedekind difiere radicalmente del prop-uesto por Weierstrass, Cantor y Charles Méray; los últimos usaron sucesiones fun-damentales (= de Cauchy) de números racionales para definir los números irra-cionales, mientras que Dedekind retornó a Euclides para su inspiración, basandosepara su definición en la teoría de Eudoxo de los cocientes de magnitudes. La idea deDedekind es que un número irracional α se puede definir mediante un conjunto in-finito de racionales; de hecho, el conjunto de todos los racionales menores que α. Paraevitar circularidad en esta definición, Dedekind introdujo el concepto de cortadurapara caracterizar este conjunto de racionales sin ninguna mención de α.

El enfoque de Weierstrass y Cantor se basa en la idea de que un número irra-cional se puede definir dando una sucesión de números racionales que converja a él.Así, uno puede tomar el conjunto de todas las sucesiones convergentes y dividirlopor una relación de equivalencia (dos sucesiones son equivalentes si convergen almismo límite). Pero existe un problema: los conceptos de “convergente” y “equiva-lente” tienen que ser definidos sin ninguna referencia al número real al cual la suce-sión converge (puesto que dicho real aún no existe). Sin embargo, esto se puedesolucionar apelando a las sucesiones de Cauchy. Además, este enfoque cuenta conla ventaja que se puede generalizar a otras áreas de las matemáticas, como por ejem-plo, el análisis funcional, la teoría de la medida y la topología.

108 Apéndice A. Construcción de los Números Reales

Definiciones Básicas

Campos Ordenados

Recordemos que un campo hK,+, �i es ordenado si existe un subconjunto no vacíoK+ de K que satisface las siguientes propiedades:

O1. Si a 2 K, entonces se cumple exactamente una de las siguientes afirmaciones

a 2 K+ _ a = 0 _ �a 2 K+.

O2. Si a, b 2 K+, entonces

a+ b 2 K+ y a � b 2 K+.

A partir de K+, definimos un orden estricto en K por

a < b sii b� a 2 K+.

Por tanto,Por tanto,

K+ = fa 2 K j 0 < ag y K� = fa 2 K j a < 0g

denotan los conjuntos de elementos positivos y negativos de K, respectivamente.

Teorema A.1 Sea K un campo ordenado. Entonces existe una función inyectiva E : Q! K

tal que E(Q) es un subcampo de K y para todo r, s 2 Q, se cumple que

E (r+ s) = E (r) + E (s) , E (r � s) = E (r) � E (s) y r < s$ E (r) < E (s) .

Prueba. Sea 1 2 K y S : K! K la función dada por S (x) = x+ 1, 8x 2 K. Por elteorema de recursión, existe una única función f : N! K tal que

f (1) = 1 y f (n+ 1) = f (n) + 1.

Dado n 2N, hagamos n = f (n) 2 K. Notemos que n = 1+ � � �+ 1| {z }n veces

.

Ahora, definamos E : Q ! K. Sea r 2 Q. Si r = 0, entonces E (r) = 0 2 K. Sir 2 Q+, entonces existen m, n 2 N tales que r = m

n . En este caso, E (r) = m � n�1. Sir 2 Q�, existen m, n 2N tales que r = �m

n . En este caso, E (r) = �m � n�1.

El resto de la prueba queda como ejercicio para el lector. �El anterior teorema afirma que todo campo ordenado contiene un subcampo que es iso-

morfo a Q. En lo que resta de esta sección, suponemos que Q � K y que las opera-ciones de Q coinciden con las de K.

Un campo ordenado K se denomina arquimediano si�8a, b 2 K+

�[ a < b ! (9n 2N) ( b < n � a ) ] .

Teorema A.2 Sea K un campo ordenado. LSASE

(a) K es arquimediano. (c) (8b 2 K) (9n 2N) ( b < n ).

(b) N no está acotado superiormente en K. (d) (8ε 2 K+) (9n 2N) ( 1n < ε ).

109

Prueba. (a)! (c) Si b � 1, basta tomar n = 2 2 N. Si 1 < b, como K es arqui-mediano, existe n 2N tal que b < n � 1 = n.

(c)! (d) Dado ε 2 K+, por (c), existe n 2 N tal que 0 < 1ε < n. Por tanto,

0 < 1n < ε.

(d)! (a) Sean a, b 2 K+ tales que a < b. Sea ε = ab 2 K+. Por (d), existe n 2 N

tal que 1n < ε. Como b � n > 0, se sigue que

b = b � n � 1n< b � n � ε = n � a.

Es obvio que (b) y (c) son equivalentes. �El valor absoluto de a 2 K se define por

jaj =�

a si a � 0�a si a < 0.

El valor absoluto tiene las siguientes propiedades.

1. Para todo a 2 K : jaj � 0. Si a 6= 0, entonces jaj > 0.

2. Para todo a, b 2 K :

ja � bj = jaj � jbj y ja� bj = jb� aj .

3. Para todo a, M 2 K :

jaj � M sii �M � a � M.

4. Desigualdad Triangular. Para todo a, b 2 K :

ja+ bj � jaj+ jbj y jaj � jbj � ja� bj .

En particular, para a, b, c 2 K :

ja� bj � ja� cj+ jc� bj .

Sucesiones en un campo ordenado

Sean fang∞n=1 y fbng∞

n=1 sucesiones en K, entonces fan + bg∞n=1 denota la sucesión

cuyo n-ésimo término es an + bn. Análogamente, se definen las sucesiones

fan � bng∞n=1 , f�ang∞

n=1 y fjanjg∞n=1 .

Decimos que una sucesión fang en K es una

sucesión convergente sii (9a 2 K) (8ε 2 K+) (9N 2N) (8n 2N) [n � N ! ja� anj < ε] .

sucesión de Cauchy sii (8ε 2 K+) (9N 2N) (8m, n 2N) [m, n � N ! jan � amj < ε] .

sucesión nula sii (8ε 2 K+) (9N 2N) (8n 2N) [n � N ! janj < ε] .

sucesión acotada sii (9M 2 K+) (8n 2N) [ janj � M ].


Por simplicidad, convenimos que ε siempre denotará un elemento de K y queN, n, m siempre denotarán números naturales, a menos que se especifique lo con-trario. Así, por ejemplo, una sucesión fang es convergente si existe a 2 K tal que

(8ε > 0) (9N) (8n � N) [ ja� anj < ε ].

En este caso, también se dice que fang converge a a. Es fácil de probar que unasucesión fang sólo puede converger a un único elemento a 2 K, el cual se denominael límite de la sucesión fang y se denota por

a = limn!∞

an.

No todas las sucesiones son convergentes; p.e. an = (�1)n no tiene límite.

Proposición A.1 Sea fang una sucesión en K.

(a) Si fang es convergente, entonces fang es de Cauchy.

(b) Si fang es una sucesión de Cauchy, entonces fang es acotada.

(c) Si fang es convergente, entonces fang es acotada.

Prueba. (a) Sea ε > 0. Por hipótesis, existe N tal que para todo n � N se cumpleque

ja� anj < ε2 .

Por tanto, si m, n � N se cumple que

jan � amj � jan � aj+ ja� amj < ε2 +

ε2 = ε.

(b) Para ε = 1, existe N tal que para todo n, m � N se cumple que

janj � jamj � jan � amj < 1.

Luego, para todo n � N :janj < jaN j+ 1.

Es obvio que para todo n : janj � M, donde M = max fja1j , ja2j , . . . , jaN�1j , jaN j+ 1g .�

Dado a 2 K, fag∞n=1 denota la sucesión constante cuyo n-ésimo término es an = a,

8n. Es obvio que la sucesión constante fag es convergente y lim a = a. Así, toda suce-sión constante es de Cauchy.

Enunciemos algunas de las propiedades más importantes de las sucesiones conver-gentes.

Proposición A.2 Sean fang y fbng sucesiones en K tales que lim an = a y lim bn = b enK. Entonces

(a) fan � bng es convergente y lim (an � bn) = a� b.

(b) fan � bng es convergente y lim (an � bn) = a � b.

(c) fjanjg es convergente y lim janj = jaj .

111

Prueba. (c) Usando la desigualdad triangular, se tiene que

j jxj � jyj j � jx� yj , 8x, y 2 K.

Luego, dado ε > 0, existe N tal que para todo n � N :

j jaj � janj j � ja� anj < ε.

Así, fjanjg converge a jaj. �Enunciemos algunas de las propiedades básicas de las sucesiones de Cauchy.

Proposición A.3 Sean fang y fbng sucesiones de Cauchy en K. Entonces

(a) fan � bng es una sucesión de Cauchy.

(b) fan � bng es una sucesión de Cauchy.

(c) f�ang y fjanjg son sucesiones de Cauchy.

Prueba. (a) Sea ε > 0. Por hipótesis, existen N1, N2 tales que

jan � amj < ε2 , 8m, n � N1 y jbn � bmj < ε

2 , 8m, n � N2.

Sea N = max fN1, N2g . Por tanto, para todo m, n � N se cumple que

j(an + bn)� (am + bm)j = j(an � am) + (bn � bm)j � jan � amj+ jbn � bmj < ε2 +

ε2 = ε.

Esto es, fan + bng es de Cauchy. Análogamente, se prueba que fan � bng es de Cauchy.

(b) Por la proposición A.1 (b), fang y fbng son sucesiones acotadas. Luego, existenM1, M2 2 K+ tales que

janj � M1 y jbnj � M2, 8n 2N.

Dado ε > 0, existen N1, N2 tales que

jan � amj < ε2M2

, 8m, n � N1 y jbn � bmj < ε2M1

, 8m, n � N2.

Sea N = max fN1, N2g . Por tanto, para todo m, n � N se cumple que

jan � bn � am � bmj � jan � bn � am � bnj+ jam � bn � am � bmj � jan � amj � jbnj+ jbn � bmj � jamj<

ε

2M2�M2 +

ε

2M1�M1 = ε.

Luego, fan � bng es de Cauchy en K. �Recordemos que una sucesión fang es nula si

(8ε > 0) (9N) (8n � N) [ janj < ε ].

Esto significa que

fang es nula sii fang converge a 0 2 K sii lim an = 0.

Ahora, establezcamos las propiedades más sobresalientes de las sucesiones nulas.


Proposición A.4 Sea fang una sucesión nula en K.

(a) Si fbng es una sucesión nula en K, entonces fan + bng es una sucesión nula.

(b) Si fbng es una sucesión acotada en K, entonces fan � bng es una sucesión nula.

(c) Si jbnj � janj , para todo n, entonces fbng es una sucesión nula.

Prueba. (a) Sea ε > 0. Por hipótesis, existen N1, N2 tales que

janj < ε2 , 8n � N1 y jbnj < ε

2 , 8n � N2.

Sea N = max fN1, N2g . Por tanto, para todo n � N se cumple que

jan + bnj � janj+ jbnj < ε2 +

ε2 = ε.

Esto es, fan + bng es nula.

(b) Por hipótesis, existe M 2 K+ tal que jbnj � M, 8n 2N. Sea ε > 0. Como fang esnula, existe N tq

janj <ε

M, 8n � N.

Por tanto, para todo m, n � N se cumple que

jan � bnj = janj � jbnj <ε

M�M = ε, 8n � N.

Luego, fan � bng es una sucesión nula en K. �Notemos que la afirmación (a) de la proposición A.4 se puede enunciar en una formamás sugestiva:si lim an = lim bn = 0, entonces.

lim (an + bn) = lim an + lim bn = 0+ 0 = 0.

Los siguientes lemas nos serán de mucha utilidad más adelante.

Lema A.1 Si fang una sucesión de Cauchy no nula, entonces existen c 2 K+ y N0 2 N

tales que0 < c � janj , 8n � N0.

Prueba. Razonemos por el absurdo; esto es, supongamos que�8c 2 K+

�(8N 2N) (9m > N) (jamj < c) . (A.1)

Sea ε > 0. Como fang es de Cauchy, existe N tal que

jan � amj < ε2 , 8m, n � N.

Particularizando para c = ε2 y N en (A.1), existe m > N tal que jamj < ε

2 . Así, paratodo n � N se cumple que

janj � jan � amj+ jamj < ε2 +

ε2 = ε.

Luego, fang es una sucesión nula; absurdo. �

113

Lema A.2 Dada una sucesión de Cauchy fang , se cumple una y sólo una de las siguientesposibilidades:

(a) fang es una sucesión nula.

(b) Existen c 2 K+ y N 2N tales que 0 < c < an, 8n � N.

(c) Existen c 2 K+ y N 2N tales que an < �c < 0, 8n � N.

Prueba. Es claro que si fang satisface una de las tres posibilidades, entonces nopuede satisfacer las otras dos; i.e. las posibilidades son mutuamente excluyentes.Veamos que al menos una de las posibilidades se cumple. Supongamos que fang noes una sucesión nula. Por el lema , existen c 2 K y N0 2N tales que

0 < c < janj , 8n � N0.

- Si existe N1 tal que an 2 K+, 8n � N1, basta tomar N = max fN0, N1g . Por tanto,para todo n � N :

an = janj > c > 0.

- Si existe N2 tal que an 2 K�, 8n � N2, basta tomar N = max fN0, N2g . Por tanto,para todo n � N :

�an = janj > c > 0. Así, an < �c < 0

En caso contrario, se tendría que

8N19n � N1�an /2 K+

�y 8N29n � N2

�an /2 K�

�(A.2)

Para ε = 2c > 0, existe N0 tal que

jan � amj < 2c, 8m, n � N0.

Por (A.2), podemos elegir n, m > N0 tales que an /2 K+ y am /2 K�. Por tricotomía,an � 0 y am � 0. Por tanto,

2c > jam � anj = am � an = jamj+ janj � 2c > 0.

Absurdo. �De acuerdo a la proposición A.1 (a), toda sucesión convergente es una sucesión de

Cauchy. Un campo ordenado K se denomina completo si toda sucesión de Cauchyfang en K converge a un elemento a en K. El concepto de completez juega un papelesencial en el análisis moderno. El siguiente teorema relaciona la noción de com-pletez con la noción de continuidad.

Teorema A.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Si K es arquimediano y completo, entonces K satisface el axioma del supremo.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Sea A un subconjunto no vacío de K acotado superiormente por b 2 K.Fijemos n 2N. Sea

Tn = fk 2 Z j 8a 2 A ( n � a � k)g .


Como b es cota superior de A, entonces n � a � n � b, para todo a 2 A. Como K esarquimediano, existe k 2N tal que n � b � k. Por tanto,

n � a � k, 8a 2 A.

Luego, Tn 6= ∅. Como A 6= ∅, entonces Tn está acotado inferiormente por cualquierelemento n � a0, con a0 2 A. Por tanto, existe kn 2 Z tal que kn = min Tn.

Como kn = min Tn, existe an 2 A tal que kn � 1 < n � an � kn. Por tanto,

kn

n� 1

n< an �

kn

n. (A.3)

Afirmamos quen

knn

o∞

n=1es una sucesión de Cauchy en K.

En efecto, dado ε > 0, como K es arquimediano, existe N tal que 1N < ε. Sean

m, n � N. Supongamos, sin perdida de generalidad, que knn �

kmm . Por (A.3) y dado

que knn es cota superior de A, se tiene que

km

m� 1

m< am �

kn

n� km

m<

km

m+

1m

.

Por tanto, �� kn

n� km

m

�� < 1m� 1

N< ε.

Dado que K es completo, existe α 2 K tal que lim knn = α. Afirmamos que α es el

supremo de A en K.

(a) Si α no es una cota superior de A, existe a 2 A tal que α < a. Por tanto, existe ntal que ��α� kn

n

�� < 12(a� α) .

Entonces,

a� kn

n= (a� α) + (α� kn

n) � (a� α)�

��α� kn

n

��> (a� α)� 1

2 (a� α) = 12 (a� α) > 0

Así, knn < a � kn

n , absurdo. Luego, α es una cota superior de A.

(b) Sea q una cota superior de A. Supongamos que q < α. Por la convergencia de lasucesión

nknn

oa α y por (A.3), podemos tomar n (lo suficientemente grande) tal que

kn

n� an <

1n< 1

4 (α� q) y�� kn

n� α

�� < 14 (α� q) .

Por tanto,

an � q = (α� q) + (an �kn

n) + (

kn

n� α) � (α� q)� ( kn

n� an)�

�� knn � α

��> 3

4 (α� q)� 14 (α� q)� 1

4 (α� q) = 12 (α� q) > 0.

Luego, q < an, absurdo. Por consiguiente, α � q. Podemos concluir que α = sup A.�El recíproco del teorema A.3 es cierto; esto es, un campo ordenado que satisfaga el

axioma del supremo también es arquimediano y completo. Pero la prueba de este hechoinvolucra conceptos que están más alla de los objetivos de este apéndice.

115

Sucesiones de Cauchy en Q

Sabemos que Q es un campo ordenado y arquimediano que no satisface el axiomadel supremo. Por el teorema A.3, se concluye que Q no es completo. Esto significaque podemos afirmar que existen sucesiones de Cauchy de números racionales queno son convergentes en Q. Sin embargo, construiremos algunos ejemplos familiaresde sucesiones con tales características.

Ejemplo Consideremos la sucesión fSng definida por

Sn = 1+ 1+12!+

13!+ � � �+ 1

n!= ∑n

k=01k!

.

Veamos que fSng es una sucesión de Cauchy en Q. Aplicando inducción, es fácilprobar que

2n < (n+ 1)! 8n 2N.

Ahora, notemos que para todo n, p se cumple que

Sn+p � Sn =1

(n+ 1)!+

1(n+ 2)!

+ � � �+ 1(n+ p)!

� 12n +

12n+1 + � � �+

12n+p�1

=12n

�1+

12+ � � �+ 1

2p�1

�=

22n

�1� 1

2p

�<

12n�1 .

Luego, dado ε > 0, basta tomar N tal que 21�N < ε. Si m, n � N, podemos suponerque m > n. Por tanto, existe p tal que m = n+ p. Por tanto,

jSm � Snj <1

2n�1 �1

2N�1 < ε.

Por otro lado, es un resultado clásico del análisis real que

limn!∞

Sn =∞

∑n=0

1n!= e,

donde e denota el número de Euler (cfr. [Ru76, p. 63-65]). Como e /2 Q, fSng es unasucesión de Cauchy de números racionales que no es convergente en Q. �X

Ejemplo (Mesopotamía, 1500 AC) Sea fang la sucesión en Q definida por la recur-sión:

a1 = 2 y an+1 =12

�an +

2an

�, 8n 2N.

Usando técnicas del análisis se muestra que fang es una sucesión de Cauchy en Q.Supongamos que a = lim an 2 Q. Por tanto,

a = limn!∞

an = limn+1!∞

an+1 =12

�lim an +

2lim an

�= 1

2�a+ 2

a�

.

Luego, 2a2 = a2 + 2. Así, a2 = 2, absurdo. Por tanto, fang no converge en Q. �X

Ejemplo Consideremos la sucesión fbng en Q definida por la recursión:

b1 = 1 y bn+1 =bn + 2bn + 1

, 8n 2N.


De nuevo, aceptemos, sin prueba, que fbng es una sucesión de Cauchy en Q. Supong-amos que fbng converge a b 2 Q. Por tanto,

b = limn!∞

bn = limn+1!∞

bn+1 =lim bn + 2lim bn + 1

=b+ 2b+ 1

.

Así, b2 + b = b+ 2. Luego, b2 = 2; absurdo. Por tanto, fbng no converge en Q. �X

Intuitivamente, la recta racional es una especie de queso Gruyère llena de huecos quecorresponderían a incontables números irracionales. Ahora, la idea es adicionar es-tos puntos para obtener una recta real completa y continua. En términos algo másprecisos, la recta real R se obtiene añadiendo a la recta racional Q aquellos puntosque corresponden a sucesiones de Cauchy de números racionales que no convergenen Q. Así, toda sucesión fang de Cauchy de números racionales determinaría unnúmero real de la siguiente forma:

– Si lim an = a 2 Q, entonces a se llama un número real “racional”.

– Si fang no converge en Q, entonces fang determina un número real“irracional”.

La gran dificultad que surge aquí es que un número real dado puede ser deter-minado por muchas sucesiones de Cauchy. Como vimos, las sucesiones fang y fbngdeterminan a

p2. Ahora, si r 2 Q, tanto

nr+ 1

n

ocomo la sucesión constante frg con-

vergen a r y determinan el mismo número real racional r. Por tanto, a cada númeroreal se le asociar más de una sucesión de Cauchy. Por esta razón, un número realserá definido como una clase de equivalencia de sucesiones de Cauchy de númerosracionales.

Construcción de R

Siguiendo [Bl03, p. 354], denotemos por CS el conjunto de todas las sucesiones deCauchy de números racionales. Dadas fang , fbng 2 CS , definimos � por

fang � fbng sii fan � bng es nula en Q sii 8ε > 0 9N 8n � N [ janj < ε] .

Lema A.3 � es una relación de equivalencia en CS .

Prueba. Supongamos que fang � fbng y fbng � fcng . Por tanto, fan � bngy fbn � cng son sucesiones nulas en Q. Por la proposición A.4 (a), fan � cng =fan � bng+ fbn � cng también es nula. Esto es, fang � fcng . �El lema A.3 justifica la siguiente definición:

R = CS/ � .

Por tanto, un número real α es una clase de equivalencia de sucesiones de Cauchy denúmeros racionales.

Aritmética en R

Sean α = [fangn] y β = [fbngn] números reales. Definimos

α+ β = [fan + bngn] y α � β = [fan � bngn]

117

como la suma y el producto de α y β, respectivamente.

Sean fang , fbng 2 CS . Por la proposición A.3, fan + bng y fan � bng están en CS . Sinembargo, debemos probar que las operaciones binarias + y � están bien definidas; loque significa que no dependen de las sucesiones particulares elegidas de cada clase.

Lema A.4 Si fang � frng y fbng � fsng , entonces

fan + bng � frn + sng y fan � bng � frn � sng .

Prueba. Por hipótesis, fan � rng y fbn � sng son sucesiones nulas en Q. Por laproposición A.4 (a), la sucesión

f(an + bn)� (rn + sn)g = f(an � rn) + (bn � sn)g

también es nula en Q; es decir, fan + bng � frn + sng. Por otro lado, notemos que

an � bn� rn � sn = (an � bn � rn � bn) + (rn � bn � rn � sn) = (an � rn) � bn+ (bn � sn) � rn.(A.4)

Por la proposición A.1 (b), fbng y frng son sucesiones acotadas. Así, por la proposi-ción A.4 (b), f(an � rn) � bng y f(bn � sn) � rng son sucesiones nulas. Por (A.4), fan � bn � rn � sngtambién es una sucesión nula. Es decir, fan � bng � frn � sng . �

Proposición A.5 Si α, β, γ 2 R, entonces

Leyes Asociativas α+ (β+ γ) = (α+ β) + γ α � (β � γ) = (α � β) � γ.

Leyes Conmutativas α+ β = β+ α α � β = β � α.

Leyes Distributivas α � (β+ γ) = α � β+ α � γ (α+ β) � γ = α � γ+ β � γ

Ahora, consideremos las sucesiones constantes f0, 0, . . .g y f1, 1, . . .g en Q. Defini-mos

0R =�f0g∞

n=1�

y 1R =�f1g∞

n=1�

como los elementos neutros de R para la suma y el producto, respectivamente. Enefecto,

Proposición A.6 (Existencia de Neutros) Si α 2 R, entonces

α+ 0R = α y α � 1R = α.

Dado α =�fang∞

n=1�2 R, definimos el inverso aditivo de α por

�α =�f�ang∞

n=1�

.

Como fangn 2 CS , por la proposición A.3 (c), f�angn 2 CS . Es fácil de probar que sifang � frng , entonces f�ang � f�rng. Luego,�α está unívocamente determinado.

Ahora, supongamos que α 6= 0R. Luego, fangn sería una sucesión de Cauchy nonula. Por el lema A.1, existen c 2 Q+ y N0 2N tales que

0 < c < janj , 8n � N0. (A.5)


Luego, an 6= 0, 8n � N0. Así, podemos definir una sucesión de números racionalesfa�ng∞

n=1 por

a�n = 1, si 1 � n < N0, y a�n =1an

, si n � N0. (A.6)

Por (A.5), se tiene que para todo n � N0 : 0 < 1jan j <

1c . Ahora, dado ε > 0, existe N1

tal que para todo n, m � N1 se cumple que

jan � amj < c2 � ε.

Sea N = max fN0, N1g . Luego, para todo n, m � N tenemos que

ja�n � a�mj =�� 1an� 1

am

�� = jam � anjjamj � janj

<c2 � εc � c = ε.

Así, fa�ng 2 CS . Además, se puede probar que si fang � frng , frng también es nonula y fa�ng � fr�ng.De acuerdo a la discusión anterior, es plausible definir el inverso multiplicativo deα 2 R� por

α�1 =�fa�ng∞

n=1�2 R�

Proposición A.7 (Existencia de Inversos) Sea α 2 R. Entonces

α+ (�α) = 0R y α � α�1 = 1R (si α 6= 0R).

Prueba. De acuerdo a (A.6), se tiene que

an � a�n =�

an, si 1 � n < N0.1, si n � N0.

Luego, dado ε > 0 :jan � a�n � 1j = 0 < ε, 8n � N0.

Por tanto, fan � a�ngn � f1gn . Así, α � α�1 = 1R. �Desde un punto de vista algebraico, las anteriores proposiciones afirman que

hR,+, �, 0R, 1Ri es un campo.

Orden en R

Dados los números reales α = [fangn] y β = [fbngn] , decimos que α < β si y sólo sipara cualquier par de sucesiones fang en α y fbng en β se cumple que

(9c 2 Q+) (9N0 2N) (8n � N0) (0 < an + c < bn) .

Al verificar las propiedades algebraicas de campo de R, fue necesario mostrar quelas operaciones y los inversos en R están bien definidos; esto es, son independientesde las sucesiones particulares fang y fbng que se eligieron para representar a losnúmeros reales α y β. De nuevo, un argumento similar es requerido para mostrarque la relación < está bien definida.

119

Lema A.5 Sean fang � frng y fbng � fsng . LSASE

(a) Existen c 2 Q+ y N0 2N tales que an + c < bn, 8n � N0.

(b) Existen d 2 Q+ y N1 2N tales que rn + d < sn, 8n � N1.(a)

Prueba. Basta probar (a) ! (b) Por hipótesis, para ε = c4 > 0, podemos elegir

N tal que

rn � an � jrn � anj < c4 y bn � sn � jbn � snj < c

4 , 8n � N.

Tomemos N1 = max fN, N0g . Para todo n � N1 se cumple que

sn > bn � c4 > an + c� c

4 = an +3c4 > (rn � c

4 ) +3c4 = rn +

c2 .

Luego, basta tomar d = c2 > 0. Así, rn + d < sn, 8n � N1. �

El lema A.5 significa que las condiciones enunciadas en la definición de la relación< se cumplen para todo par de sucesiones fang en α y fbng en β ó para ningún par.Ahora, definamos

R+ = fα 2 R j 0R < αg .

Notemos que

α = [fangn] 2 R+ sii (9c 2 Q+) (9N0) (8n � N0) (0 < c < an) .

En particular, 0R < 1R. Así, R+ 6= ∅.

Teorema A.4 R es un campo ordenado. Es decir,

(a) Para todo α 2 R se cumple exactamente una de las siguientes afirmaciones:

α 2 R+ _ α = 0R _ �α 2 R+.

(b) Si α, β 2 R+, entonces

α+ β 2 R+ y α � β 2 R+.

Prueba. Notemos que la ley de tricotomía (a) se sigue del lema A.2.

(b) Si α = [fang] y β = [fbng] están en R+, entonces existen c, d 2 Q+ y N0, N1 2 N

tales que0 < c < an, 8n � N0, y 0 < d < bn, 8n � N1.

Tomando N = max fN0, N1g , tenemos que para todo n � N :

0 < c+ d < an + bn y 0 < c � d < an � bn.

Por tanto, α+ β y α � β están en R+. �Por el teorema A.4, la relación � es un orden lineal en R que satisface las desigual-dades usuales:

1. α < β si y sólo si α+ γ < β+ γ.

2. Si γ > 0R, entonces α < β si y sólo si α � γ < β � γ.


3. Si γ < 0R, entonces α < β si y sólo si α � γ > β � γ.

De acuerdo a los teoremas A.1 y A.4, existe un subcampo de R isomórfico a Q. Pero,dada la naturaleza de nuestra construcción, podemos caracterizar con precisión la“copia isomórfica” de Q en R.

Dado r 2 Q, la sucesión constante fr, r, . . .g converge en Q a r y fr, r, . . .g 2 CS .Luego, podemos definir una función E : Q! R por

E (r) = r =�frg∞

n=1�= [fr, r, . . .g] 2 R.

El número real r se denomina un número real racional. Notemos que E (0) = 0 = 0R

y E (1) = 1 = 1R.

Proposición A.8 E : Q! R es una función inyectiva tal que para todo r, s 2 Q :

r+ s = r+ s, r � s = r � s y r < s$ r < s.

Prueba. Veamos que E es inyectiva. Sean r, s 2 Q tales que [frg] = E (r) = E (s) =[fsg] . Por tanto, frg � fsg . Así, lim (r� s) = 0. Por la proposición A.2, r = lim r =lim s = s.

(a) Dados r, s 2 Q, se tiene que

E (r+ s) = [fr+ sg] = [frg] + [fsg] = E (r) + E (s) .

La prueba de E (r � s) = E (r) � E (s) es análoga.

(b) Si r < s, tomando c = s�r2 2 Q+, se tiene que r+ c < s. Luego, E (r) = [frg] <

[fsg] = E (s) . Recíprocamente, si E (r) < E (s) , existe c 2 Q+ tal que r + c < s.Como r < r+ c, se sigue que r < s. �

Por el momento, será útil distinguir entre el número racional r en Q y su imagen ren R.

Teorema A.5 R es un campo arquimediano.

Prueba. Por el teorema A.2, basta ver que el conjunto de los números reales natu-rales

N = fn j n 2Ngno está acotado superiormente en R. En efecto, sea α = [fang] 2 R+. Como α > 0R,existe N0 2N tal que 0 < an, para todo n � N0. Como fang es una sucesión acotada(por ser de Cauchy), existe M 2 Q+ tal que

0 < an = janj � M, 8n � N0.

Como Q es un campo arquimediano, existe k 2 N tal que M < k. Tomando c =k�M

2 2 Q+, se tiene que M+ c < k. Por tanto, an + c � M+ c < k, 8n � N0. Así,

α = [fang] < [fkg] = k.

Así, R es un campo arquimediano. �Dado que R es un campo ordenado, podemos definir el valor absoluto para todo

α 2 R :

jαj =�

α, si α � 0R.�α, si α < 0R.

Como consecuencia de lo visto en la anterior sección (pág. 109), el valor absoluto j�jen R posee las propiedades usuales.

121

Lema A.6 Si δ 2 R+, entonces existe ε 2 Q+ tal que 0R < ε < δ.

Prueba. Sea δ = [fdng] 2 R+. Como δ > 0R, existen c 2 Q+, N 2 N tales que0 < c � dn, 8n � N. Sea ε = c

4 > 0. Para todo n � N, se tiene que

0 < ε+ c4 =

c2 < c � dn.

Por tanto, 0R < [fεg] < [fdng] . Es decir, 0R < ε < δ. �Sean fαng es una sucesión en R y α 2 R. Decimos que (ver página 109)

fαng converge a α sii (8δ 2 R+) (9N) (8n � N) ( jα� αnj < δ ).

fαng es de Cauchy sii (8δ 2 R+) (9N) (8m, n � N) ( jαn � αmj < δ ).

Por el lema A.6, podemos cambiar el “radio” real δ por un “radio” racional ε. Esdecir,

fαng converge a α sii (8ε 2 Q+) (9N) (8n � N) ( jα� αnj < ε ).

fαng es de Cauchy sii (8ε 2 Q+) (9N) (8m, n � N) ( jαn � αmj < ε ).

La completez de R descansa en la siguiente proposición.

Proposición A.9 Sea fang∞n=1 una sucesión de Cauchy en Q y α =

�fang∞

n=1�

.

Entonces la sucesión fang∞n=1 converge a α en R.

Aquí, an denota el número real�fang∞

m=1�, donde fang∞

m=1 es la sucesión con términoconstante an.

Prueba. Por hipótesis, dado ε 2 Q+ existe N tal que

jan � amj < ε2 , 8m, n � N.

Fijemos n � N. Para todo m � N, se tiene que

(am � an) +ε2 � jam � anj+ ε

2 <ε2 +

ε2 = ε.

Así, am +ε2 < an + ε. Sea r = an + ε 2 Q y c = ε

2 2 Q+. Entonces, am + c < r, 8m �N. Por tanto, α =

�famg∞

m=1�< r = an + ε. Luego,

α� an < ε. (A.7)

De nuevo, para todo m � N, se tiene que

(an � am)� ε � jan � amj � ε < ε2 � ε = � ε

2 .

Así, (an � ε) + ε2 < am. Sea s = an � ε y d = ε

2 2 Q+. Entonces, s+ d < am, 8m � N.Por tanto, an � ε = s <

�famg∞

m=1�= α. Luego,

�ε < α� an. (A.8)

De (A.7) y (A.8), se tiene que

jα� anj < ε, 8n � N.

Esto es, limn!∞

an = α en R. �


Corolario A.1 (Densidad de Q en R) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Sean α, β 2 R. Si α < β, entonces existe r 2 Q tal que

α < r < β.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Dados α < β, sea γ = 12 (α+ β) . Es fácil de verificar que α < γ < β. Como

γ 2 R, γ = [fcng] , donde fcng es una sucesión de Cauchy en Q. Por la proposiciónA.9,

limn!∞

cn = γ en R.

Por tanto, para δ = 12 (β� γ) > 0R, existe N tal que

α < γ� δ < cn < γ+ δ < β, 8n � N.

Por último, basta tomar r = cN 2 Q. �Ahora, veamos que R es un campo completo.

Teorema A.6 (Cauchy) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Toda sucesión de Cauchy de números reales converge a un número real.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Prueba. Sea fαng∞n=1 una sucesión de Cauchy en R. Por tanto, para cada n 2N :

αn =��

an,k∞

k=1

�,

donde�

an,k∞

k=1 es una sucesión de Cauchy en Q. Por la proposición A.9,

limk!∞

an,k = αn en R.

Así, para 1n 2 Q+, podemos elegir un número racional an,kn de la sucesión

�an,k

∞k=1

tal que ��αn � an,kn

�� < 1n .

Sea An = an,kn , para todo n 2N. Veamos que fAng∞n=1 2 CS .

Como fαng∞n=1 es una sucesión en R, para ε 2 Q+, existe N0 tal que

jαn � αmj < ε3 , 8m, n � N0.

Sea N1 2N tal que N1 � N0 y 1N1< ε

3 . Para todo m, n � N1 tenemos que�� An � Am�� = �� An � Am

�� an,kn � αn

��+ jαn � αmj+��αm � am,km

��< 1

n +ε3 +

1m � 1

N1+ ε

3 +1

N1< ε

3 +ε3 +

ε3 = ε.

Por tanto,�ε < An � Am < ε, 8m, n � N1.

Como An, Am y ε son números racionales, por la proposición A.8

�ε < An � Am < ε, 8m, n � N1.

123

Luego, jAn � Amj < ε, 8m, n � N1.

Ahora, sea α =�fAng∞

n=1�2 R. Veamos que fαng converge a α en R.

En efecto, sea ε 2 Q+. Por la proposición A.9, la sucesión�

An

converge a α en R.Por tanto, existe N2 tq ��An � α

�� < ε2 , 8n � N2.

Tomemos un número natural N3 tal que N3 � N2 y 1N3< ε

2 . Por tanto, para todon � N3 se cumple que

jαn � αj ��αn � An

��+ ��An � α�� < 1

n +ε2 �

1N3+ ε

2 <ε2 +

ε2 = ε.

Por tanto, fαng es una sucesión convergente en R. �Por los teoremas A.5 y A.6, R es un campo ordenado arquimediano y completo. Por el

teorema A.3, se sigue que R satisface el axioma del supremo.

Corolario A.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Todo subconjunto no vacío de R acotado superiormente tiene supremo en R.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Resumiendo

R es un campo ordenado, arquimediano, completo, que satisface el axioma del supremo

y que contiene al campo ordenado Q como un subconjunto denso.


Apéndice B

Pruebas alternativas del Teorema deSchröder-Bernstein

Primera Prueba

Primero notemos que no hay perdida de generalidad si suponemos que A \ B = ∅.(ejercicio: explique por qué). Por tanto, fijemos conjuntos disjuntos A, B y funcionesinyectivas

f : A! B y g : B! A.

Ahora, definamos J : A [ B! A [ B por

J (x) =�

f (x) , si x 2 A.g (x) , si x 2 B.

Se puede verificar fácilmente (ejercicio) que J es una función bien definida, inyectiva yque mapea A en B y a B en A.

Ahora, definamos una relación binaria E para todo x, y 2 A [ B por

xEy si y sólo si 9p, q 2N (Jp (x) = Jq (y)) .

De nuevo, es fácil mostrar (ejercicio) que E es una relación de equivalencia en A [ B.Denotemos por Ex la clase de equivalencia de x 2 A [ B bajo E.

Diremos que z 2 A es un origen si z /2 ran (J) = fJ (x) j x 2 A [ Bg .

Lema B.1 (a) Si z 2 Ex es un origen, entonces

Ex = Ez = fJp (z) j p 2Ng .

(b) Si Ex \ B no tiene un origen, entonces f mapea Ex \ A biyectivamente sobre Ex \ B.

(c) Si Ex \ B tiene un origen, entonces g mapea Ex \ B biyectivamente sobre Ex \ A.

Prueba. (a) Por definición de E, Jp (z) Ez para todo p 2N. Luego,

fJp (z) j p 2Ng � Ez = Ex.

Sea yEz. Luego, existen m, n 2 N tales que Jm (z) = Jn (y) . Tenemos que m � n,pues, en caso contrario, n�m� 1 2 N y z = J

�Jn�m�1 (y)

�, lo cual contradice que

z es un origen. Por tanto, m� n 2N y y = Jm�n (z) . Así,

Ex = Ez � fJp (z) j p 2Ng .

126 Apéndice B. Pruebas alternativas del Teorema de Schröder-Bernstein

(b) Es fácil ver f siempre mapea Ex \ A inyectivamente en Ex \ B (ejercicio). Ahora,sea b 2 Ex \ B. Como b no es un origen, existe a 2 A tal que b = J (a) = f (a) .Luego, aEbEx. Por lo cual, a 2 Ex \ A.

(c) Sea b 2 B un origen en Ex. Por la parte (a), tenemos que

Ex = fJp (b) j p 2Ng .

Es fácil de verificar (ejercicio) que para todo n :

Ex \A =n

J2n+1 (b) j n 2No

, Ex \B =n

J2n (b) j n 2No

y g�

J2n (b)�= J2n+1 (b) .

La conclusión se sigue inmediatamente de lo anterior (ejercicio). �Para probar el teorema de Schröder-Bernstein, definamos una función h : A ! B

por

h (x) =�

g�1 (x) , si Ex \ B tiene un origen.f (x) , en caso contrario.

Sea x 2 A tal que Ex \ B tiene un origen. Por el lema anterior, g mapea Ex \ B biyecti-vamente sobre Ex \ A. Como x 2 Ex \ A, existe un único y 2 Ex \ B tal que g (y) = x.Así, h (x) = g�1 (x) = y está definido. Por tanto, h es una función bien definida.

Es claro que h mapea a A en B y que h (x) 2 Ex. Mostremos que h es inyectiva en A.

En efecto, sean x, x0 2 A tal que h (x) = h (x0) . Dado que

x0Eh�x0�= h (x) 2 Ex,

tenemos que Ex = Ex0 . Por tanto, las definiciones de h (x) y h (x0) ocurren en elmismo caso. Si Ex \ B tiene un origen, entonces

g�1 (x) = h (x) = h�x0�= g�1 �x0� .

Si Ex \ B no tiene un origen, entonces

f (x) = h (x) = h�x0�= f

�x0�

.

En ambos casos, podemos concluir que x = x0.

Ahora, mostremos que h es sobreyectiva.

Sea y 2 B. Supongamos que Ey \ B tiene un origen. Sea x = g (y) 2 A. Luego, xEyy Ex = Ey. Así, Ex \ B tiene un origen. Por tanto,

h (x) = g�1 (x) = y.

Supongamos que Ey \ B no tiene un origen. Por el lema 1 (b), existe x 2 Ey \ A conf (x) = y. De nuevo, xEy y Ex = Ey. Así, Ex \ B no tiene un origen. Por tanto,

h (x) = f (x) = y.

En ambos casos, y 2 ran (h) .

Por tanto, h es biyectiva. Luego, A � B.

127

Segunda prueba

A continuación bosquejamos otra prueba del teorema de Schröder-Bernstein [Hr99],[Sm96]. Esta prueba usa un lema notable debido a Knaster y Tarski. De hecho, usaun caso especial (el lema se puede generalizar a retículos completos). Primero, nece-sitamos algo de terminología.

Sea F : P (A) ! P (A) . Decimos que F es monótona si X � Y � A implica queF (X) � F (Y) . Un conjunto X � A se denomina un punto fijo de F si F (X) = X.

Lema del Punto Fijo Toda función monótona tiene un punto fijo.

Bosquejo. Sea F : P (A)! P (A) monótona. Tome los conjuntos

A = fX � A j F (X) � Xg 6= ∅ y X =\A.

Se tiene queX 2 A, F

�X�2 A y F

�X�= X.

Por tanto, F tiene un punto fijo. �

Lema B.2 Si C1 � D � C y C � C1, entonces C � D.

Bosquejo. Use el lema del punto fijo del siguiente modo.

Dada ϕ : C ! C1 biyectiva, sea F : P (C)! P (C) definida por

F (X) = (C� D) [ ϕ (X) .

Como F es monótona, sea S un punto fijo de F; es decir,

S = (C� D) [ ϕ (S) .

Defina una biyección ψ : C ! D por

ψ (x) =�

ϕ (x) , si x 2 S.x, si x /2 S.

Por tanto, C � D. �Para finalizar, notemos que

g ( f (A)) � g (B) � A.

Como f y g son inyectivas, se cumple que

A � g ( f (A)) y B � g (B) .

Por el lema anterior, A � g (B) � B.

128 Apéndice B. Pruebas alternativas del Teorema de Schröder-Bernstein

Tercera prueba

Primero necesitamos un lema debido a Banach [Dr96, p. 43].

Lema B.3 Si f : A ! B y g : B ! A son funciones inyectivas, entonces existe S � A talque

g (B� f (S)) = A� S.

Prueba. Sean ϕ = g � f : A! A y T = A� g (B) . Ahora, tomemos

S = T [ ϕ (T) [ ϕ (ϕ (T)) [ � � �

y notemos que S = T [ ϕ (S) . Dado que g es inyectiva, se cumple que para todoy 2 B :

y /2 f (S) sii g (y) /2 (g � f ) (S) = ϕ (S) .

Dado que g (y) /2 T, esto implica que g (y) /2 T [ ϕ (S) = S. Así para todo y 2 B :

y 2 B� f (S) sii g (y) 2 A� S.

Esto es, g (B� f (S)) = A� S. �Para completar la prueba del teorema de Schröder-Bernstein, tomemos S como en

el lema B.3. Notemos que

g�1 (A� S) = B� f (S) .

Definamos h : A! B por

h (x) =�

f (x) , si x 2 S.g�1 (x) , si x /2 S.

Las propiedades de S implican que h es inyectiva. Como S\ (A� S) = ∅, se cumpleademás que

h (A) = h (S [ (A� S)) = h (S)[ h (A� S) = f (S)[ g�1 (A� S) = f (S)[ (B� f (S)) = B.

Esto es, h es sobreyectiva. Por tanto, h es biyectiva y A � B.

Referencias

[Ad95] Adler, A. & Coury, J. The Theory of Numbers. A Text and a Source of Problems.Belmont: Jones & Bartlett, 1995.

[Be03] Bedoya, L. Peano, Lawvere, Peirce: Tres Axiomatizaciones de los Números Nat-urales. Tesis. Ibague: Universidad de Tolima, 2003.

[Bl03] Blöch, E. Proofs and Fundamentals. A First Course in Abstract Mathematics.Boston: Birkhaüser, 2003.

[Bu07] Burton, D. Elementary Number Theory. New York: McGraw Hill, 2007.

[Ca55] Cantor, G. Contributions to the Founding of the Theory of Transfinite Numbers.New York: Dover, 1955.

[Dr96] Drake, F. R. & Singh, D. Intermediate Set Theory. Chichester: John Wiley &Sons, 1996.

[En77] Enderton, H. Elements of Set Theory. New York: Academic Press, 1977.

[En98] Engel, A. Problem-Solving Strategies. New York: Springer-Verlag, 1998.

[Ep95] Epp, S. Discrete Mathematics with Applications. Belmont: Brooks/Cole, 1995.

[Fe64] Feferman, S. The Number Systems. Foundations of Algebra and Analysis. Read-ing: Addison-Wesley, 1964.

[Gi02] Gillman, L. Two Classical Surprises concerning the Axiom of Choice andthe Continuum Hypothesis. American Mathematical Monthly. 109 (2002), 544-553.

[Go96] Goldrei, D. Classical Set Theory. A guided independent study. London, Chap-man & Hall, 1996.

[Go98] Goodaire, E. & Parmenter, M. Discrete Mathematics with Graph Theory. Up-per Saddle River: Prentice-Hall, 1998.

[Gr96] Grassman, W. K. & Tremblay, J. Logic and Discrete Mathematics. A ComputerScience Perspective. Upper Saddle River: Prentice-Hall, 1996.

[Gr00] Grattan-Guinness, I. The Search for Mathematical Roots, 1870� 1940. Prince-ton: Princeton UP, 2000.

[He86] Herstein, I. N. Abstract Algebra. New York: Macmillan, 1990.

[Hr99] Hrbacek, K. & Jech, T. Introduction to Set Theory. New York: Marcel Dekker,1999.

130 Referencias

[Je03] Jech, T. Set Theory. Third Millennium Edition (revised and expanded). Berlin:Springer-Verlag, 2003.

[Jo05] Johnsonbaugh, R. Discrete Mathematics. Upper Saddle River: Prentice-Hall,2005.

[Ko07] Koshy, T. Elementary Number Theory with Applications. Burlington: Acad-emic Press, 2007.

[La90] Lang, S. Undergraduate Algebra. New York: Springer-Verlag, 1990.

[La83] Larson, L. C. Problem-Solving Through Problems. New York: Springer-Verlag,1983.

[Le02] Levy, A. Basic Set Theory. New York: Dover, 2002.

[Pa09] Parra, C. Fundamentos de Matemática Abstracta. Medellín, Universidad Na-cional de Colombia, 2009.

[Ph84] Phillips, E. An Introduction to Analysis and Integration Theory. New York:Dover, 1984.

[Ro03] Rosen, K. H. Discrete Mathematics and its Applications. New York: McGraw-Hill, 2003.

[Ro05] Rosen, K. H. Elementary Number Theory and its Applications. Boston: Pear-son, 2005.

[Ru76] Rudin, W. Principles of Mathematical Analysis. New York: McGraw-Hill,1976.

[Sm96] Smullyan, R. & Fitting, M. Set Theory and the Continuum Problem. Oxford:Oxford University Press, 1996.

[St93] Straight, J. Combinatorics. An Invitation. Belmont: Brooks/Cole, 1993.

[Wa01] Walser, H. The Golden Section. Washington: Mathematical Association ofAmerica, 2001.

Indice

AxiomaAxioma de Elección, 89Axiomas de cardinalidad, 94Axiomas de Peano, 1

Cadenade conjuntos, 90

Campoordenado, 108

Cardinalaleph, 95finito, 84infinito, 95

Conjuntocontable, 87de Cantor, 88de Henkin, 1Dedekind infinito, 92enumerable, 79finito, 82inductivo, 6infinito, 82no contable, 87

Demostración por Inducción Matemática,7

Hipótesis inductiva, 7Diagonalización, 79

Equipotencia, 71Estructura, 14

Fórmula de Binet, 13Función

característica, 77de pareamiento, 74factorial, 10

Hipótesis del Continuo, 81, 99

Lema de Zorn, 90Ley

de Tricotomíaen los naturales, 5en los reales, 119en un campo ordenado, 108

para cardinales, 99

Mínimo, 5Método de la hipótesis auxiliar, 7Maximal, 90

Númeroalgebraico, 93complejo, 17de Fibonacci, 12entero, 15natural, 2racional, 16trascendente, 93

Ordenen los naturales, 4

Principiode Buen Orden, 5, 11de Inducción Completa, 11de Inducción Matemática, 2, 6, 11del Palomar, 82

Productonatural, 4

Propiedad Arquimedianaen los enteros, 5

Razón áurea, 13

Sistema de Peano, 1Suma

geométrica, 9natural, 3

Teoremade Cantor, 78, 79, 96de Recursión, 2, 3, 17de Schröder-Bernstein, 73, 81, 96,

125de Unicidad de Dedekind, 3de Zeckendorf, 14

131

Documents

Body i Margin Notes - medellin.unal.edu.coearamosn/cursos/...naturales en términos de conjuntos linealmente ordenados, discretos y sin máximo. Además dio deﬁniciones recursivas