ApuntesConjuntos2

Vista previa del material en texto

TEORÍA DE RAMSEY
G. PADILLA
Contenido
I. Introducción a la Teoŕıa de Conjuntos 2
1. Fórmulas 3
1.1. Śımbolos lógicos y variables 3
1.2. Fórmulas 3
2. Axiomas de la Teoŕıa de Conjuntos 3
2.1. Axioma de Extensión 3
2.2. Axioma del Vaćıo 4
2.3. Axioma de Pares 4
2.4. Axioma de Unión 4
2.5. Axioma de Partes 4
2.6. Ejercicios 5
2.7. Los Axiomas de Reemplazo 5
2.8. Ejercicio 6
2.9. Intersección de un conjunto, diferencia de conjuntos 6
2.10. Producto cartesiano 6
2.11. Relaciones, funciones 7
2.12. Equivalencias 7
2.13. Relaciones de Orden 7
2.14. Ejercicios 8
3. Aritmética basada en la Teoŕıa de Conjuntos 9
3.1. Números naturales 9
3.2. Conjuntos inductivos 9
3.3. El Axioma del Infinito 10
3.4. El conjunto de los números naturales 10
3.5. Propiedades de los números naturales 10
3.6. Ejercicios/Ejemplos 11
3.7. Aritmética en los naturales 12
3.8. Operaciones entre números naturales 12
3.9. Orden de los naturales 14
3.10. Ejercicios 14
3.11. Números enteros 15
3.12. Números racionales 15
3.13. Números reales 17
3.14. Suma en R 18
4. Conjuntos equipotentes 18
4.1. Conjuntos equipotentes 18
1
2 G. PADILLA
4.2. Potencias de conjuntos 19
4.3. Conjuntos finitos 21
4.4. Conjuntos totalmente ordenados 22
4.5. Segmentos iniciales 23
5. Ordinales 26
5.1. Propiedades de los ordinales 27
5.2. Inducción en Ord 27
5.3. Operaciones en Ord 28
5.4. Operaciones normales 28
5.5. Forma normal de Cantor 29
6. La jerarqúıa de Von Neumann 29
6.1. El universo de Von Neumann 29
6.2. Axioma de Regularidad 30
7. Cardinales 31
7.1. Propiedades básicas de los cardinales 31
7.2. La función ℵ 31
7.3. Cardinalidad de un C.B.O. 32
8. El Axioma de Elección 32
8.1. Funciones selectoras en conjuntos finitos 33
8.2. El Axioma de Elección y sus formas equivalentes 33
8.3. Axioma de elección y cardinalidad 35
II. Filtros, Ultrafiltros y convergencia general 36
9. Espacios compactos 37
9.1. Espacios compactos 37
9.2. La Propiedad de Intersección Finita 37
10. Filtros y Ultrafiltros 39
10.1. Filtros 39
11. El Teorema de Tijunov 41
11.1. El Teorema de Tijunov 42
11.2. Convergencia de Moore-Smith 43
11.3. Ideales 43
11.4. Ultrafiltros 44
11.5. Ultrafiltros y el Teorema de Tijunov revisado 44
III. Teoŕıa de Ramsey 45
12. Grafos 46
12.1. Grafos 46
12.2. Morfismos de grafos 46
12.3. Grafos completos 46
12.4. Operaciones entre grafos 47
12.5. Grado de un vértice 48
12.6. Caminos 49
12.7. Ciclos 49
12.8. Distancia entre vértices 50
12.9. Grafos conexos 51
12.10. Árboles 51
13. El Teorema de Ramsey 53
13.1. El principio del casillero 53
TEORÍA DE RAMSEY 3
13.2. Teorema de Ramsey finito 53
13.3. Teorema de Ramsey infinito 55
13.4. Ejercicio 57
13.5. Versiones del Teorema de Ramsey para grafos 57
14. El espacio de Cantor 58
14.1. El espacio de Cantor 58
14.2. Topoloǵıa de 2
N
58
14.3. Distancia en 2
N
58
14.4. El 2-árbol infinito de 2
N
, orden lexicográfica 59
14.5. Medida de probabilidad en 2
N
60
14.6. Topoloǵıa en P(N) 60
14.7. Segmentos iniciales 60
15. El Teorema de Ellentuck 61
15.1. Tipos de Baire en un espacio topológico 61
15.2. Conjuntos anaĺıticos, conjuntos perfectos 61
15.3. El Teorema de Ellentuck 61
15.4. Aplicación 1: El Teorema de Ellentuck 61
16. Espacios Topológicos Ramsey 62
IV. Ultrafiltros y Ĺımites de Estructuras 62
17. Estructuras sobre un lenguaje 62
17.1. Lenguajes y Estructuras 62
17.2. Morfismos, embebimientos, subestructuras 62
17.3. Términos, fórmulas, teoŕıas 63
17.4. Preservación de validez 63
17.5. Estructuras finitamente generadas 64
17.6. Edad de una estructura 64
17.7. Familias de Fräıssé 65
18. Ĺımites categóricos 65
18.1. Categoŕıas 65
18.2. Transformaciones naturales 65
18.3. Aplicacion #4: Ĺımites categóricos 65
18.4. Aplicacion #5: Coĺımites de estructuras, Teorema de Los revisado 65
19. Haces 65
19.1. Haces topológicos 65
19.2. Prehaces y haces categóricos 65
19.3. Aplicacion #5: Haces generales; haces de estructuras 65
19.4. Aplicacion #6: Categóıas (ultra)filtradas 65
Referencias 66
4 G. PADILLA
Primera parte
I. Introducción a la Teoŕıa de Conjuntos
En estas primeras secciones veremos los resultados generales de un curso básico de Teoŕıa de
Conjuntos. Trataremos los axiomas ZF y la aritmética de los números naturales, enteros, racionales
y reales que se deducen a partir de esta teoŕıa. Estudiaremos asimismo los conjuntos parcialmente
ordenados, los ordinales y cardinales. Terminaremos con una introducción al axioma de elección y
una buena definición de cardinalidad de conjuntos. A lo largo de toda esta primera parte seguiremos
principalmente el texto de [6], al cual remitimos para cualquier duda.
TEORÍA DE RAMSEY 5
1. Fórmulas
1.1. Śımbolos lógicos y variables. Los śımbolos lógicos dela Teoŕıa de Conjuntos son:
• El śımbolo de pertenencia ∈.
• El śımbolo de igualdad =.
• Los conectivos lógicos ∧, ∨.
• El śımbolo de negación ¬.
• Los contadores existencial y universal ∃, ∀.
• Los signos de agrupación (, ), [, ].
• Las llaves enumerativas {, } (sirven para definir conjuntos especificando sus elementos).
Una variable es, en general, cualquier signo que no es un śımbolo lógico (e.d. no figura en la
lista anterior). Para las variables usaremos, en general y de modo preferente, letras latinas a, b . . .
etc. Emplearemos letras griegas α, β, . . . para denotar secuencias finitas de signos que incluyen
variables y śımbolos lógicos. Si dentro de una secuencia α aparece cierta variable, digamos x,
diremos que x es una variable libre siempre que x no es precedida por ningún contador ∃, ∀.
Toda variable que no es libre es llamada una ”variable muda” por motivos que se explican más
adelante. Si x es una variable libre de una secuencia finita α escribimos α(x), queriendo decir con
ello, de modo amplio, que el ”sentido” de la secuencia simbólica α ”depende” de x.
1.2. Fórmulas. Una fórmula de la Teoŕıa de Conjuntos es cualquier secuencia finita de śımbolos
que se construye de modo inductivo a partir de las siguientes reglas:
(1) x ∈ y es una fórmula atómica con variables libres x, y. Esta fórmula se lee ”x pertenece
a y” o ”x es un elemento de y”.
(2) Si α, β son fórmulas entonces α∧β, α∨β, ¬α son fórmulas; las cuales se leen respectivamente
”α y β” (conjunción), ”α ó β” (disyunción no excluyente); y ”no-α (negación).
(3) Si α(x) es una fórmula, entonces ∀x α(x), ∃x α(x) son fórmulas.
Emplearemos las siguientes abreviaturas y equivalencias usuales.
Abreviaturas:
x 6∈ y para ¬(x ∈ y).
x 6= y para ¬(x = y).
α⇒ β para ¬[α ∧ (¬β)].
α 6⇒ β para ¬(α⇒ β), que es equivalente a α ∧ (¬β).
α⇐ β para β ⇒ α.
α⇔ β para (α⇒ β) ∧ (β ⇒ α).
∃!xα para ∃x[α ∧ (∃yα)⇒ (x = y)] (e.d., existe un único x tal que α).
Equivalencias: Dos fórmulas α, β son equivalentes si vale α⇔ β. En particular
α es equivalente a ¬(¬α).
∀x(¬α) es equivalente a ¬(∃xα).
∃x(¬α) es equivalente a ¬(∀xα).
α⇒ β es equivalente a (¬β)⇒ (¬α).
2. Axiomas de la Teoŕıa de Conjuntos
Un conjunto es un objeto matemático que satisface los siguientes axiomas.
2.1. Axioma de Extensión. Expresa que dos conjuntos son indistinguibles si poseen los mismos
elementos:
∀x ∀y(x = y ⇔ ∀z(z ∈ x⇔ z ∈ y))
6 G. PADILLA
Este axioma se puede tomar, asimismo, como una definición del significado del śımbolo de igualdad.
2.2. Axioma del Vaćıo. Expresa que existe un conjunto que no posee elementos
∃x ∀y (y 6∈ x)
Por el axioma de extensión, este conjunto es único. En adelante lo denotaremos por ∅.
2.3. Axioma de Pares. Expresa que, si x, y son dos conjuntos, entonces existe un conjunto cuyos
elementos son los dos conjuntos dados:
∀x ∀y ∃w (z ∈ w ⇔ (z = x) ∧ (z = y))
De nuevo, por el axioma de extensión, el conjunto que satisface la propiedad de arriba es único;
lo denotamos por {x, y}. Nótese que {x, y} = {y, x} son dos escrituras del mismo conjunto. En
particular, si x = y entonces x, y son dos nombres del mismo conjunto x; por lo cual escribimos
{x, y} = {x, x} = {x}. El axioma de pares nos permite definir también pares ordenados. Elpar
ordenado (x, y) es el conjunto {x, {x, y}}.
2.4. Axioma de Unión. Expresa que dado un conjunto x existe otro conjunto y cuyos elementos
son los elementos de elementos de x:
∀x ∃y(w ∈ y ⇔ ∃z(w ∈ z) ∨ (z ∈ x))
La escritura usual de este conjunto en la literatura matemática es ∪
z∈x
z. En adelante, dentro de
estos apuntes, usaremos indistintamente cualquiera de las siguientes notaciones:
∪x = ∪{z : z ∈ x} = ∪
z∈x
z
Por ejemplo; si a, b son conjuntos entonces, por el axioma de pares, existe el conjunto {a, b} y por
el axioma de unión existe el conjunto ∪{a, b} el cual solemos escribir como a ∪ b.
2.5. Axioma de Partes. Dados dos conjuntos a, b decimos que b es una parte o subconjunto
de a si todo elemento de b es un elemento de a. Escribimos b ⊆ a para abreviar ”b es una parte o
subconjunto de a”. De este modo
(b ⊆ a) ⇔ ∀z(z ∈ b⇒ z ∈ a)
En este texto emplearemos la notación b ⊂ a para decir que b ⊆ a y b 6= a; decimos en este caso
que b es un subconjunto propio de a.
El Axioma de Partes expresa que dado cualquier conjunto x, existe un conjunto cuyos elementos
son precisamente todas las partes de x:
∀x ∃y (z ∈ y ⇔ z ⊆ x)
El conjunto de partes de un conjunto a se denota por P(a). En otras palabras; si a es un conjunto
entonces
P(a) = {b : b ⊆ a}
es un conjunto.
TEORÍA DE RAMSEY 7
2.6. Ejercicios.
(1) Si α es una fórmula, x es una variable muda en α y z no es una variable de α; sea β la
fórmula que se obtiene de α sustituyendo toda aparición de x por z. Demuestra que α⇔ β.
Ayuda: Procede por inducción sobre las fórmulas. Muéstralo primero para las fórmulas
atómicas y luego para las concatenaciones de conectivos, negaciones y contadores.
(2) Demuestra que (x, y) = (a, b) si y solo si x = a y y = b.
(3) Define (a, b, c) = (a, (b, c). Demuestra que (x, y, z) = (a, b, c) si y solo si x = a, y = b y
z = c. Generaliza este ejercicio para secuencias ordenadas (a
1
, . . . , a
n
) de conjuntos.
(4) Demuestra que
(a) ∪∅ = ∅.
(b) ∪{a} = a.
(c) a ∪ b = b ∪ a.
(d) a ∪ a = a.
(e) a ∪ (b ∪ c) = (a ∪ b) ∪ c.
2.7. Los Axiomas de Reemplazo. Dado un entero n > 0, una relación n-aria es una cor-
respondencia que valida (o no) n-secuencias ordenadas de conjuntos. Más precisamente; cada
f’ormula α(x1 , . . . , xn) con n variables libres x1 , . . . , xn , determina una relación n-aria R sobre
las secuencias ordenadas (a1 , . . . , an) de conjuntos, del modo siguiente: Decimos que (a1 , . . . , an)
están relacionados si y solo si vale α(a
1
, . . . , a
n
). Por ejemplo:
aRb ⇔ a ∈ b.
aRb ⇔ a ⊆ b.
aRb ⇔ a = b.
son ejemplos de relaciones binarias. Un ejemplo de una relación ternaria es R(a, b, c) ⇔ a ∈ b∪ c.
Una relación (n+2)-aria dada por una fórmula α(x, y;x
1
, . . . , x
n
) es funcional en x con parámetros
en una n-secuencia de conjuntos c = (c
1
, . . . , c
n
) si y solo si, para cada conjunto a existe a lo sumo
un único conjunto b tal que vale α(a, b; c). En śımbolos;
∀x [∃y α(x, y; c)]⇒ ∀z[α(x, z; c)⇒ (z = y)]
O, equivalentemente;
∀x [∃y α(x, y; c) ⇒ ∃!y α(x, y; c)]
Intuitivamente; si α(x, y; c) define una relación funcional; entonces la correspondencia x 7→ y es
una ”función” en el sentido usual. Los Axiomas de Reemplazo permiten definir de modo preciso
la idea de función.
Del mismo modo en que escribimos c = (c
1
, . . . , c
n
) para una secuencia ordenada de conjuntos;
escribamos w = (w1 , . . . , wn) para una secuencia de variables libres. Dada cualquier fórmula
α(x, y, w) el Axioma de Reemplazo para α expresa que si la relación binaria α(x, y, c) es fun-
cional; entonces dado un conjunto u, existe un conjunto v cuyos elementos son todas las imágenes
de los elementos de u por α. En śımbolos;
∀c∀x [∃y α(x, y; c) ⇒ ∃!y α(x, y; c)]] ⇒ ∀u∃v∀y [y ∈ v ⇔ ∃x(x ∈ u) ∨ α(x, y, c)]
Teorema 2.7.1. [Separación] Dada una fórmula α(x,w), un conjunto a y una secuencia ordenada
de conjuntos c; existe un único conjunto b que satisface b = {x ∈ a : α(x, c)}.
[Demostración] Fijemos c = (c1 , . . . , cn). Si no existe ningún conjunto u ∈ a tal que α(u, c);
basta tomar b = ∅. Supongamos lo contrario y fijemos algún u ∈ a tal que α(u, c). Consideremos
8 G. PADILLA
la fórmula
β(x, y, z, w) :=
(i)︷ ︸︸ ︷
[(y = x) ∧ α(x,w)] ∨
(ii)︷ ︸︸ ︷
[(y = z) ∧ (¬α(x,w))]
donde (i) y (ii) se refiere a los dos casos posibles para cada (x, y) dados (z, w). Entonces
• β(x, y, u, c) es funcional: Sean d, e, e′ conjuntos tales que β(d, e, u, c) y β(d, e′, u, c). Si para
(d, e, u, c) vale (i) y para (d, e′, u, c) vale (ii) entonces, por definición; (e = d) ∧ α(e, c) y (e′ =
u) ∧ ¬α(e, c). Se deduce que α(e, c) ∧ (¬α(e, c)), lo cual es absurdo. De este modo se puede ver
que los casos ”cruzados” (i)-(ii) o (ii)-(i) son imposibles. Solo quedan entonces los casos parejos,
(i)-(i) que implica e = d = e′, o (ii)-(ii) que implica e = u = e′. En cualquiera de ellos, se obtiene
e = e′.
• Existe el conjunto b: Aplicamos directamente el Axioma de Reemmplazo para la fórmula fun-
cional β(x, y, u, c) y el conjunto a. Entonces y ∈ b si y solo si existe x ∈ a tal que β(x, y, u, c).
Este es el caso para y = u y x ∈ a cualquier elemento tal que ¬α(x, c). Ahora bien, si y 6= u
entonces, necesariamente, para (x, y, u, c) debe valer (i). Se deduce que y = x y α(y, c) es α(x, c).
Esto concluye la demostración. �
2.8. Ejercicio. Deduzca el Axioma de Pares del resto de los axiomas de Teoŕıa de Conjuntos
(extensión, vaćıo, partes, unión y reemplazo). Resp.- Para cada par de conjuntos a, b considere el
conjunto
c = P(a ∪ b) = {x : x ⊆ a ∪ b}
cuya existencia es dada por el Axioma de Unión y el Axioma de Partes. Luego considere la fórmula
α(x, y, z) := (z = x) ∧ (z = y)
Por los Axiomas de Vaćıo, Extensión y Reemplazo, podemos aplicar el Teorema de Separación
para la fórmula α(a, b, z) tomando z ∈ c. El conjunto que se obtiene es b = {z ⊆ a ∪ b : (z =
a) ∧ (z = b)} = {a, b}.
2.9. Intersección de un conjunto, diferencia de conjuntos. Dado un conjunto no vaćıo a;
la intersección de a es ∩a = {y : ∀b(b ∈ a ⇒ y ∈ b)}. Notemos que ∩a es un conjunto, para lo
cual basta aplicar el Teorema de Separació a la fórmula α(x, y) := ∀z(z ∈ x⇒ y ∈ z) al conjunto
x = a. Solemos escribir a ∩ b en lugar de ∩{a, b}.
Dados dos conjuntos a, b; la diferencia de a menos b es a\b = {z ∈ a : z 6∈ b}. Por un argumento
similar es inmediato que a\b es un conjunto.
2.10. Producto cartesiano. Dados dos conjuntos a, b el producto cartesiano a× b es el conjunto
de todos los pares ordenados (d, e) = {d, {d, e}} tales que d ∈ a y e ∈ b; notemos que en tal
caso (d, e) ∈ P(a ∪ P(a ∪ b)); este último es un conjunto por los Axiomas de Partes y Unión.
Consideremos la fórmula Dada la fórmula α(x, y, z) := ”z es un par ordenado de x× y”. Es decir:
α(x, y, z) := ∃u∃v(u ∈ x) ∨ (v ∈ y) ∨ (z = (u, v))
Entonces a × b se obtiene al aplicar el Teorema de Separación a α(a, b, z) sobre los elementos
z ∈ P(a ∪ P(a ∪ b)). Se deduce que a× b es un conjunto. De manera similar se define el producto
cartesiano de n conjuntos a
1
× · · · × a
n
(n > 0 entero).
TEORÍA DE RAMSEY 9
2.11. Relaciones, funciones. Una relación binaria entre elementos de dos conjuntos a, b es
un subconjunto R ⊆ a × b. Dados u ∈ a, v ∈ b decimos que u está relacionado con v si y
solo si (u, v) ∈ R. Más en general, dado un entero n > 0 una relación n-aria entre elementos
de n conjuntos dados, digamos a
1
, . . . , a
n
; es un subconjunto R ⊆ a
1
× · · · × a
n
. Decimos que
u
1
∈ a
1
, . . . , u
n
∈ a
n
están relacionados si y solo si (u
1
, . . . , u
n
) ∈ R.
Dados dos conjuntos a, b; una función de a en b es una relación F ⊆ a × b tal que, para cada
u ∈ a, existe a lo sumo un único v ∈ b tal que (u, v) ∈ F ; y en tal caso escribimos v = F (u). En
otras palabras, una función de a en b es una relación F ⊆ a× b tal que, para la fórmula
α(u, v, x, y, z) := [(u ∈ x) ∨ (v ∈ y) ∨ (u, v) ∈ z]
se tiene que α(u, v, a, b, F ) es funcional en el sentido de 2.7. Si F es una función de a en b solemos
escribir a
F
- b. El dominio deF es el conjunto dom(F ) = {x ∈ a : ∃y ∈ b(b = F (a))}.
El rango de F es el conjunto ran(F ) = {y ∈ b : ∃x ∈ a(b = F (a))}. Si c ⊆ a, la función F
restringida a c es el conjunto F � c = {(x, y) ∈ F : x ∈ c}. Denotamos por F [c] = ran(F � c) al
conjunto de imágenes de elementos de c.
2.12. Equivalencias. Dado un conjunto no vaćıo a; una equivalencia en a es una relación R ⊆
a× a que satisface las siguientes propiedades:
• Reflexividad: (u, u) ∈ R para todo u ∈ a.
• Simetŕıa: Si (u, v) ∈ R entonces (v, u) ∈ R, para todo u, v ∈ a.
• Transitividad: Si (u, v) ∈ R y (v, w) ∈ R entonces (u,w) ∈ R.
Si R es una equivalencia en a; la clase de equivalencia de un elemento u ∈ a es [u] = {v ∈ a :
(u, v) ∈ R} (este es un conjunto por el Teorema de Separación).
Fijemos ahora una equivalencia R en a. Dados u, v ∈ a, si [u] 6= [v] entonces [u]∩[v] = ∅. En efecto,
si w ∈ [u] ∩ [v] entonces (u,w) ∈ R y (w, v) ∈ R; por transitividad ello implica que (u, v) ∈ R. De
nuevo, por transitividad, si (u, z) ∈ R entonces (v, z) ∈ R de donde [u] ⊆ [v]. De modo similar se
ve que [v] ⊆ [u]; luego [u] = [v]. El conjunto cociente inducido por R es
a/R = {[u] : u ∈ a}
Para verificar que este es un conjunto, basta considerar las siguientes fórmulas:
(1) α(x, Y ) := ”Y es una relación de equivalencia en Y ”. En otras palabras; α(x, Y ) :=
∀u∀v∀w[[(u, u) ∈ Y ] ∧ [(u, v) ∈ Y ⇔ (v, u) ∈ Y ] ∧ [(u, v) ∈ Y ∧ (v, w) ∈ Y ⇒ (u,w) ∈ Y ]].
(2) β(z, Y ) := z es una clase de equivalencia de Y ”. Es decir; β(x, Y, z) := ∃u(u ∈ x)∧∀y(y ∈
z)⇔ [y ∈ x ∧ (u, y) ∈ Y ].
(3) γ(x, Y, z) := α(x, Y ) ∧ β(x, Y, z).
Entonces a/R se obtiene a partir de γ(a,R, z) tomando z ∈ a. Por el Teorema de Separación, a/R
es un conjunto.
Es inmediato que ∪a/R = a; en efecto, para cada u ∈ a se tiene que [u] ⊆ a. Por ello, z ∈ ∪a/R⇒
∃u(u ∈ a) ∧ (z ∈ [u]); pero esto implica que z ∈ a. Se deduce que ∪a/R ⊆ a. Finalmente; si u ∈ a
entonces [u] ∈ a/R; luego u ∈ ∪a/R. Se deduce que a ⊆ ∪a/R; luego a = ∪a/R.
2.13. Relaciones de Orden. Dado un conjunto no vaćıo a; una relación de orden parcial en
a es una relación R ⊆ a× a que satisface las siguientes propiedades:
• Reflexividad: (u, u) ∈ R para todo u ∈ a.
• Antisimetŕıa: Si (u, v) ∈ R y (v, u) ∈ R, entonces u = v; para todo u, v ∈ a.
• Transitividad: Si (u, v) ∈ R y (v, w) ∈ R entonces (u,w) ∈ R.
10 G. PADILLA
Si R es un orden parcial en a, solemos escribir u ≤ v en lugar de (u, v) ∈ R y decimos que (a,≤) es
un conjunto parcialmente ordenado o poset. De este modo u ≤ u, si u ≤ v y v ≤ w entonces
u ≤ w; y si u ≤ v y v ≤ u entonces u = v para cualesquiera u, v, w ∈ a. También escribimos u < v
para abreviar (u ≤ v) ∧ (u 6= v).
Un poset (a,≤) es totalmente ordenado (a veces también se le dice ”linealmente ordenado”) si
para cualesquiera u, v ∈ a se tiene (u ≤ v) ∨ (v ≤ u).
Dados un poset (a,≤), b ⊆ a y u ∈ b; decimos que u es minimal en B si no existe v ∈ B tal que
v < u. Decimos que u es el primer elemento (o el ”menor elemento” de B si ∀v ∈ b(u ≤ v).
Un conjunto bien ordenado es un poset (a,≤) tal que todo subconjunto b ⊆ a no vaćıo posee
un primer elemento.
2.14. Ejercicios.
(1) Si a ⊆ b, muestra que P(a) ⊆ P(b).
[Demostración] Por la transitividad de la relación ⊆; pues si c ⊆ a, como a ⊆ b se tiene
que c ⊆ b. Luego c ∈ P(a)⇒ c ∈ P(b); es decir, P(a) ⊆ P(b). �
(2) Dar ejemplos de conjuntos a 6= b tales que ∪a = ∪b.
[Demostración] Basta tomar, por ejemplo, a = {{u}, {v, w}} y b = {{u, v}, {w}}. �
(3) Muestra que si a ∈ b entonces P(a) ∈ P(P(∪b)).
[Demostración] Si a ∈ b entonces a ⊆ ∪b por la definición de ∪b. Por el ejercicio (1) esto
implica que P(a) ⊆ P(∪b). Luego P(a) ∈ P(P(∪b)) como se queŕıa. �
(4) Si (a,≤) es un conjunto bien ordenado, mostrar que también es totalmente ordenado.
[Demostración] Sea (a,≤) bien ordenado. Dados cualesquiera u, v ∈ a; el subconjunto
{u, v} es no vaćıo, por lo cual debe tener un primer elemento. Si el primer elemento es u,
entonces u ≤ v; caso contrario v ≤ u. En cualquier caso, u, v son comparables. �
(5) Mostrar que la familia de todos los conjuntos no puede ser un conjunto.
[Demostración] Sea Ω la familia de todos los conjuntos. Supongamos que Ω es un con-
junto. Entonces, al aplicar el Teorema de Separación a la fórmula α(x) := (x 6∈ x) sobre el
conjunto Ω; obtenemos el conjunto de todos los conjuntos que no pertenecen a śı mismos,
es decir, A = {x : x 6∈ x} es un conjunto. Pero entonces (A ∈ A) ⇔ (A 6∈ A), lo cual es
una contradicción. �
(6) Productos cartesianos arbitrarios: Si a es un conjunto cualquiera, el producto cartesiano
de los elementos de a, que escribimos
∏
a; se define del modo siguiente:∏
a = {f : f es una función de a en ∪ a, y ∀u ∈ a(f(u) ∈ u)}
Las funciones f que satisfacen la propiedad anterior (e.d. que pertenecen a
∏
a se llaman
funciones de selección en a.
(a)
∏
a es un conjunto.
[Demostración] Consideremos las siguientes fórmulas:
• α(x, y, f) := ”f es una función de x en ∪y”; es decir α(x, y, f) := ∀u(u ∈ x⇒
∃!v ∈ y[(u, v) ∈ f ].
TEORÍA DE RAMSEY 11
• β(x, f) := ”f es una función de elección en x”; es decir, β(x, f) := ∀u∀v[(u ∈
x) ∧ (v ∈ ∪x) ∧ ((u, v) ∈ f) ⇒ v ∈ u)]. En otras palabras y abreviando;
β(x, f) := ∀u[(u ∈ x)⇒ (f(u) ∈ u)].
• γ(x, f) := α(x,∪x, f) ∧ β(x, f).
Entonces,
∏
a se obtiene al aplicar el Teorema de Separación a la fórmula γ(a, f)
tomando f en el conjunto a× ∪a. �
(b) Si a = {u, v} entonces
∏
a = u× v.
[Demostración] Una función de selección f en a = {u, v}; es la selección de dos pares
ordenados cualesquiera f = {(u, x); (v, y)} ⊆ ({u, v} × (u ∪ v) tales que x ∈ u, y ∈ v.
A cada f podemos asociar un par ordenado único en u× v, el par de sus imágenes:∏
a
ψ
- (u× v) {(u, x); (v, y)} 7→ (x, y)
En otras palabras,∏
a
ψ
- (u× v) f 7→ (f(u), f(v))
Es inmediato que la función ψ es biyectiva. �
(c) Si ∅ ∈ a entonces
∏
a = ∅.
[Demostración] Pues toda función de selección f en a debe satisfacer f(u) ∈ u para
todo u ∈ a; en particular f(∅) ∈ ∅, lo cual es absurdo por la definición de vaćıo; luego
a no puede tener funciones de selección. �
(d) Si ∩a 6= ∅ entonces
∏
a 6= ∅.
[Demostración] Basta elegir u ∈ ∩a. Entonces la función constante a
f
- ∪ a
dada por f(x) = u para todo x ∈ a, es una función de selección. �
(e) Si a = {x
i
: i ∈ N} es una sucesión de conjuntos; entonces
∏
a =
∏
i∈N
x
i
es el conjunto
de las sucesiones (a
i
)
i∈N tales que ai ∈ xi para todo i.
[Demostración] La demostración es análoga a la del ejercicio 6.b. Basta considerar
la biyección ∏
a
ψ
-
∏
i∈N
xi f 7→ (f(ai))i∈N
�
3. Aritmética basada en la Teoŕıa de Conjuntos
3.1. Números naturales. Los números naturales son los siguientes conjuntos:
0 = ∅.
1 = {0} = {∅}.
2 = {0, 1} = {∅, {∅}}.
3 = {0, 1, 2} = {∅, {∅}, {∅, {∅}}}.
Y aśı sucesivamente; (n+ 1) = {0, 1, . . . , n} = n ∪ {n}.
12 G. PADILLA
3.2. Conjuntos inductivos. Dado un conjunto cualquiera a; el sucesor de a es el conjunto
a′ = a ∪ {a}. Un conjunto x es inductivo si satisface las siguientes propiedades:
• Contiene al vaćıo: ∅ ∈ x.
• Si contiene a un conjunto, también contiene a su sucesor: y ∈ x⇒ y′ ∈ x.
3.3. El Axioma del Infinito. También llamado ”Axioma de inducción”: Existen conjuntos in-
ductivos.
∃x[(∅ ∈ x) ∧ ∀y(y ∈ x⇒ y′ ∈ x)]
Proposición 3.3.1. La intersección arbitraria de conjuntos inductivos es un conjunto inductivo.
En otras palabras, si a es un conjunto tal que, para todo u ∈ a, se tiene que u es inductivo; entonces
∩a es inductivo.
[Demostración] Sea a como en la hipótesis. Directamente de la definición de conjuntos induc-
tivos, deducimos que:
• ∅ ∈ ∩a: Como u es inductivo para todo u ∈ a, se tiene que ∅ ∈ u para todo u ∈ a; luego
∅ ∈ ∩a.
• b ∈ ∩a ⇒ b′ ∈ ∩a: Si b ∈ ∩a entonces b ∈ u para todo u ∈ a; como cada uno de estos
elementos u es inductivo, se tiene que b′ = (b ∪ {b}) ∈ u para todo u ∈ a. Luego b′ ∈ ∩a.
Esto concluye la demostración. �
3.4. El conjunto de los números naturales. Un conjunto a es un número natural si y solo
si pertenece a todo conjunto inductivo.Ejemplos de los números naturales son los dados en 3.1.
Consideremos la fórmula α(z) :=”z es un número natural” o, equivalentemente, ”z pertenece a
todo conjunto inductivo”;
α(z) := ∀w[(∅ ∈ w) ∧ ∀y(y ∈ w ⇒ y′ ∈ w)⇒ z ∈ w]
Por el Axioma del Infinito, existe al menos un conjunto inductivo, digamos a. Por el Teorema
de Separación; el conjunto de todos los elementos z ∈ a que satisfacen α(z) es un conjunto; lo
denotamos ω = {z ∈ a : α(z)}. Notemos que
ω = {z ∈ a : z es un número natural } = {z : z es un número natural }
Lema 3.4.1. ω es un conjunto.
[Demostración] Es directo del razonamiento anterior. �
Notemos que ω = {0, 1, 2, 3, . . . etc.}. Asimismo; 0 ∈ 1 ∈ 2 ∈ 3 . . . ; y también
0 ⊆ 1 ⊆ 2 ⊆ 3 ⊆ · · · Finalmente; notemos que el sucesor de un número natural n es precisa-
mente n′ = n ∪ {n} = (n+ 1).
3.5. Propiedades de los números naturales.
Lema 3.5.1. ω es el conjunto inductivo más pequeño: Si a es un conjunto inductivo entonces
ω ⊆ a.
[Demostración] Por la definición de los números naturales 3.4, si n ∈ ω es un número natural
y a es inductivo, entonces n ∈ a. Se deduce que, si a es inductivo, entonces ω ⊆ a. �
Lema 3.5.2 (Principio de Inducción). Todo subconjunto inductivo de ω es igual a ω.
TEORÍA DE RAMSEY 13
[Demostración] Si a es inductivo y a ⊆ ω entonces, por el Lema 3.5.1; ω ⊆ a. Luego a = ω por
el Axioma de Extensión. �
Lema 3.5.3. Todo número natural diferente de 0 es sucesor de algún número natural.
[Demostración] Sea a = {z : (z = 0) ∧ ∃y ∈ ω(z = y′)}. Es inmediato que a ⊆ ω. Por otra
parte, si z ∈ a entonces, como z es un número natural, su sucesor z′ ∈ ω también es un número
natural. Puesto que z ∈ a esto implica, por definición, que z′ ∈ a. Se deduce que a es inductivo.
Por el Principio de Inducción 3.5.2; a = ω. �
Un conjunto x es transitivo si satisface la siguiente propiedad:
∀y∀z[(z ∈ y) ∧ (y ∈ x)⇒ (z ∈ x)]
es decir, si todo elemento de un elemento de x es también un elemento de x. Por ejemplo; {4} no
es transitivo; {0, 1, 2} śı es transitivo.
Lema 3.5.4. Las siguientes propiedades son equivalentes:
(1) a es un conjunto transitivo.
(2) ∪a ⊆ a.
(3) a ⊆ P(a).
(4) ∪a′ = a.
[Demostración] Procedemos por pasos.
(1)⇔(2) Suponga que a es transitivo. Si u ∈ ∪a entonces existe b ∈ a tal que u ∈ b; puesto que a
es transitivo, u ∈ a. Se deduce que ∪a ⊆ a. El rećıproco es similar.
(1)⇔(3) Suponga que a es transitivo. Dado b ∈ a, puesto que a es transitivo; para todo u ∈ b se
tiene que u ∈ a. Luego b ⊆ a, es decir, b ∈ P(a). De la arbitrariedad de b se deduce que a ⊆ P(a).
El rećıproco es similar.
(1)⇔(4) Por definición a′ = a∪{a}; luego ∪a′ = (∪a)∪a. Si a es transitivo, entonces, por la primera
equivalencia (1)⇔(2) se tiene que ∪a ⊆ a. En consecuencia ∪a′ = (∪a) ∪ a = a. Rećıprocamente,
si ∪a′ = a entonces, necesariamente, ∪a ⊆ a. Por la misma equivalencia (1)⇔(2) esto implica que
a es transitivo. �
Lema 3.5.5. Todo número natural es transitivo.
[Demostración] Sea a = {z ∈ ω : z es transitivo}. Por el Teorema de Separación, a es un
conjunto. Es inmediato que 0 ∈ a. Suponga que n ∈ a. Entonces, por el Lema 3.5.4; ∪(n′) =
∪(n ∪ {n}) = (∪n) ∪ n = n ⊆ n′; de donde se deduce que n′ es transitivo. Por ello mismo, n′ ∈ a,
de donde a es un conjunto inductivo. Por el Principio de Inducción 3.5.2 a = ω. �
Proposición 3.5.6. ω es transitivo.
[Demostración] El enunciado equivale a decir que todo elemento de un número natural es
también un número natural; es decir, si n es un número natural entonces n ⊆ ω. Sea a = {n ∈ ω :
n ⊆ ω}. Entonces 0 = ∅ ∈ a trivialmente. Supongamos ahora que n ∈ a; es decir, n ∈ ω y n ⊆ ω.
Entonces, por definición, n′ = n∪{n} satisface n′ ⊆ ω; luego n′ ∈ a. Se deduce que a es inductivo;
luego a = ω por el Principio de Inducción 3.5.2. �
14 G. PADILLA
Lema 3.5.7. Si los sucesores de dos números naturales coinciden, entonces dichos números coin-
ciden: (m,n ∈ ω) ∧ (m′ = n′)⇒ (m = n).
[Demostración] Por el Lema 3.5.4; si m′ = n′ entonces m = ∪m′ = ∪n′ = n. �
Lema 3.5.8. Ningún número natural pertenece a śı mismo: (m ∈ ω)⇒ (m 6∈ m).
[Demostración] Por inducción. Sea a = {m ∈ ω : m 6∈ m}. Es inmediato que 0 = ∅ ∈ a.
Fijemos m ∈ a y supongamos que m′ 6∈ a. Entonces, por definición de a se tiene que m′ ∈ m′;
luego m′ ⊆ ∪m′ = m, la última igualdad se debe a que m′ = m ∪ {m} y m es transitivo, por el
Lema 3.5.4. Ya que, por definición del sucesor, se tiene que m ⊆ m′; entonces m = m′. Debido
a nuestra suposición sobre m′, se deduce que m 6∈ a, lo cual es una contradicción. Como nuestra
suposición es falsa, se deduce que (m ∈ a)⇒ (m′ ∈ a); luego a es un subconjunto inductivo de ω.
Por el principio de inducción (Lema 3.5.2) a = ω. �
3.6. Ejercicios/Ejemplos.
(1) Si un conjunto a es transitivo; entonces a′ y ∪a son transitivos.
[Demostración] Procedemos por pasos.
(a) Por definición a′ = a ∪ {a}; luego ∪a′ = ∪{a, {a}} = [∪a] ∪ a. Ahora bien; por
definición, a es transitivo sii [∪a] ⊆ a. En tal caso, por el primer argumento es
imediato que [∪a′] = [∪a] ∪ a ⊆ a ⊆ a′; luego a′ es transitivo.
(b) Si a es transitivo entonces [∪a] ⊆ a. Luego ∪[∪a] ⊆ ∪a.
�
(2) Si un conjunto a es transitivo, entonces para toda cadena finita de pertenencia x
1
∈ x
2
∈
· · · ∈ xn ∈ a se tiene que x1 ∈ a.
[Demostración] El enunciado es equivalente a decir que se tiene una cadena de con-
tenciones
a ⊇ [∪a] ⊇ [∪ ∪ a] ⊇ · · · ⊇ [∪n veces· · · ∪ a]
Esto es inmediato. �
(3) Un conjunto a es transitivo ⇔ el conjunto de partes P(a) es transitivo.
[Demostración] Notemos que
(a) Para cualquier conjunto x se tiene ∪[P(x)] = x y x ∈ P(x).
(b) Por el Lema 3.5.4 las siguientes afirmaciones son equivalentes:
(i) a es transitivo.
(ii) [∪a] ⊆ a.
(iii) Todo elemento de a es un subconjunto de a; es decir: ∀x(x ∈ a)⇒ x ⊆ a.
(iv) ∀x(x ∈ a)⇒ x ∈ P(a).
(v) a ⊆ P(a).
Si a es transitivo entonces, por (a) y (b.v) tenemos ∪P(a) = a ⊆ P(a); luego P(a) es
transitivo por (b.ii). Rećıprocamente; si P(a) es transitivo entonces a = ∪P(a) ⊆ P(a)
luego a es transitivo por las equivalencias de (b). �
(4) Si ∪a′ = a entonces a es un conjunto transitivo. [Demostración] Como ya se ha visto,
∪a′ = ∪{a, {a}} = [∪a] ∪ a. De este modo, ∪a′ = a si y solo si [∪a] ⊆ a, lo cual sucede sii
a es transitivo. �
TEORÍA DE RAMSEY 15
3.7. Aritmética en los naturales.
Teorema 3.7.1 (Teorema de recursión). Dados un conjunto x, a ∈ x y una función x
f
- x;
existe una única función ω
ν
- x tal que ν(0) = a y ν(n′) = f(ν(n)) para todo n ∈ ω.
[Demostración] Digamos que una función g ⊂ ω × x es ”aceptable” si satisface las siguientes
propiedades del enunciado sobre algún subconjunto de los números naturales; es decir, sii:
(1) [0 ∈ dom(g)]⇒ [g(0) = a].
(2) [n′ ∈ dom(g)]⇒ [n ∈ dom(g)] ∧ [g(n′) = f(g(n)].
Sea A ⊆ P(ω×x) el conjunto de todas las funciones aceptables (este es un conjunto por el axioma
de reemplazo). Entonces
(a) A 6= ∅: Pues la función vaćıa ∅ ∈ A satisface todas las condiciones. También la función dada
por un único par g = {(0, a)} ∈ A.
(b) Si g, h ∈ A y n ∈ dom(g) ∩ dom(h) entonces g(n) = h(n): Para n = 0 es inmediato pues, por
la propiedad (1), g(0) = a = h(0). A continuación la idea básica es aplicar una inducción finita;
por ejemplo si n = 1 entonces g(1) = f(g(0)) = f(a) = f(h(0)) = h(1); etc. De este modo,
Dado n 6= 0 en ω supongamos que g(n) = b, h(n) = c; es decir, (n, b) ∈ g y (n, c) ∈ h. Por
el Lema 3.5.3 n = m′ es el sucesor de algún m ∈ ω. En virtud de la propiedad (2), aplicada
a g, h respectivamente; se tiene que m ∈ dom(g) ∩ dom(h). Por inducción finita obtenemos que
g(m) = h(m); luego g(n) = g(m′) = f(g(m)) = f(h(m)) = h(m′) = h(n) como se queŕıa.
(c) ν = ∪A es una función aceptable: Es inmediato que ν ⊆ ω × x. Dado n ∈ ω tenemos que
ν(n) = y (e.d. (n, y) ∈ ν) si y solo si existe g ∈ A tal que g(n) = y. Por el paso (b) y es único
pues, si h ∈ A y h(n) = y′ entonces y = y′. Para n = 0, por la propiedad (1), ν(0) = a. Para
n 6= 0, de nuevo por el Lema 3.5.3 n = m′ para algún m ∈ ω. Porla propiedad (2) aplicada a g,
tenemos que ν(m) = g(m) = z para algún z ∈ x, luego m ∈ dom(ν); y ν(n) = ν(m′) = g(m′) =
f(g(m)) = f(ν(m)) como se queŕıa.
(d) dom(ν) = ω: Por el paso anterior dom(ν) ⊆ ω es un subconjunto inductivo. Basta aplicar el
Lema 3.5.2.
(e) ν es única: Si µ es cualquier otra función aceptable cuyo dominio es todo ω entonces basta ver
que a = {n ∈ ω : ν(n) = µ(n)} es inductivo. Puesto que ν(0) = µ(0) = a, se tiene que 0 ∈ a. Si
n ∈ a, por otra parte, entonces ν(n) = µ(n); luego ν(n′) = f(ν(n)) = f(µ(n)) = µ(n′), de donde
n′ ∈ a.
�
La función ν obtenida en el teorema anterior a partir de f se llama función de recursión
asociada a f con condición inicial ν(0) = a.
Lema 3.7.2. Si x
f
- x es una función inyectiva y a ∈ [x\Im(f)] 6= ∅, entonces la función de
recursión ν asociada a f es inyectiva.
Nota La condición a 6∈ Im(f) es necesaria. Por ejemplo; si n ∈ ω, x = n′ y f es el ciclo
f(m) = m′ para m ∈ n, f(n) = 0; entonces la función de recursión ν satisface ν(kn) = 0 para
16 G. PADILLA
todo k ∈ ω, i.e. ν recorre el ciclo infinitamente. Por otra parte, para que una f inyectiva no sea
sobreyectiva se requiere que x sea, al menos, un conjunto infinito; pues toda función inyectiva sobre
un conjunto finito es biyectiva.
[Demostración del Lema 3.7.2] Por reducción al absurdo: Supongamos que ν no es inyectiva. Es
suficiente demostrar la siguiente afirmación:
(1) ∃n ∈ ω : (n 6= 0) ∧ (ν(n) = ν(0))
En tal caso, puesto que n = m′ para algún m ∈ ω (Lema 3.5.3), por la definición de la función
de recursión se tiene que a = ν(0) = ν(n) = ν(m′) = f(ν(m)). En resumen a = f(ν(m)) luego
a ∈ Im(f); lo cual contradice la hipótesis.
Por otra parte; ¿Qué sucede si m,n ∈ ω, m 6= n y ν(m) = ν(n)? Si n = 0 o m = 0 la observación
anterior vale. Supongamos que ambos son distintos de cero; entonces la idea básica es la siguiente:
Notemos que ν(0) = a, ν(1) = f(a), ν(2) = f(f(a)) = f
2
(a),...etc. Puesto que ν(m) = ν(n)
esto implica que f
n
(a) = f
m
(a). Dado que m,n son distintos, podemos asumir que, digamos,
n > m. Aplicando la inversa g = f
−1
a ambos lados de la última igualdad m veces llegamos a que
f
(n−m)
(a) = a, luego a ∈ Im(f). En la demostración presente hemos empleado dos argumentos;
el principio de tricotomı́a (dos números naturales o son iguales o alguno es mayor que el otro,
véase el Teorema 3.9.2) y la resta de enteros (para calcular n − m). El principio de tricotomı́a
será estudiado en lo sucesivo. En cuanto a las operaciones entre números naturales (suma, resta,
multiplicación), éstas se definen a partir de una función de recursión.
A fin de evitar demostraciones circulares; damos una segunda prueba de la afirmación (1) sin
emplear las operaciones entre naturales. Tomemos cualesquiera k 6= l en ω tales que ν(k) = ν(l).
La idea esencial de nuestra demostración es la siguiente:Si la suposición es cierta, entonces todas
las imágenes de ν ocurren antes de llegar a l. Sin pérdida de generalidad supondremos que ambos
k, l son diferentes de 0 y k ∈ l (véase de nuevo el Teorema 3.9.2). Sea p ∈ ω tal que l = p′ (Lema
3.5.3). Consideremos el conjunto
b = {ν(0), . . . , ν(p)} = {ν(j) : j ∈ l} ⊆ Im(ν) ⊆ x
Demostraremos que b = Im(ν); es decir, que b ⊇ Im(ν). Esto equivale a afirmar que la preimagen
c = ν
−1
(b) = {i ∈ ω : ∃j ∈ l[ν(i) = ν(j)]}
es todo ω. Notemos que
• 0 ∈ c: Es inmediata, pues 0 ∈ l.
• i ∈ c ⇒ i′ ∈ c: Fijemos cualquier j ∈ l tal que ν(i) = ν(j). Si j ∈ p entonces j′ ∈ p′ = l;
luego ν(i′) = f(ν(i)) = f(ν(j)) = ν(j′) ∈ b, de donde i′ ∈ c. Si, por el contrario, j 6∈ p;
entonces necesariamente j = p. Por un argumento similar, ν(i′) = ν(p′) = ν(l) = ν(k) ∈ b
pues, por hipótesis, k ∈ l.
De las observaciones anteriores deducimos que c es inductivo, luego c = ω por el principio de
inducción. Esto implica que b = Im(ν). Finalmente, notemos que ν(0) = a; ν(1) = f(a), ν(2) =
f(f(a)) = f
2
(a),...etc. En resumen;
ν(k) = f
k
(a) ∀k ∈ l
De este modo reescribimos el conjunto b como sigue:
b = {a, f(a), . . . , f
p
(a)} = {f
k
(a) : k ∈ l} ⊆ x
TEORÍA DE RAMSEY 17
Puesto que la función f es inyectiva y b es un conjunto finito, se deduce que f es una ”permutación”
en b. Más aún; f es un ciclo. El número de elementos de b (el ”cardinal”), digamos n = |b|, satis-
face n ∈ l y fn(a) = a, de manera que f se identifica con el ciclo (1, 2, . . . , n) en el grupo simétrico
Sn
∼= Sb . El orden de este ciclo es precisamente n; es decir, f
n
= id es la funciń identidad en
b. Una descripción detallada del entero n y la manera de conseguirlo involucran al Axioma de
Elección en la forma del Principio del Buen Orden para ω, pues n es de hecho el primer número
natural k ∈ l tal que fk(a) ∈ {a, f(a), . . . , fk−1(a)}. El Axioma de Elección será estudiado con
detenimiento en lo sucesivo. Para más detalles sobre el grupo simétrico véase [18, 20]. �
3.8. Operaciones entre números naturales. Para cada número natural m ∈ ω definimos la
función de recursión
(2) S
m
(0) = m, S
m
(n′) = [S
m
(n)]′ ∀n ∈ ω
La suma de dos números naturales n,m ∈ ω se define como
(3) m+ n = S
m
(n)
Proposición 3.8.1. La suma de números naturales satisface las siguientes propiedades:
(1) 0 + n = n.
(2) m+ 1 = m′.
(3) m+ n′ = (m+ n)′.
(4) m+ n = n+m.
(5) m+ (n+ o) = (m+ n) + o.
[Demostración] Todas las afirmaciones se demuestran por inducción. Procedemos por pasos.
(1) Inmediata.
(2) Es un caso particular de la afirmación siguiente, para n = 1 = 0′.
(3) Por definición, m+ n′ = Sm(n
′) = [Sm(n)]
′ = [m+ n]′.
(4) Sea a = {m ∈ ω : ∀n ∈ ω[m+ n = n+m]}. Demostraremos que a es inductivo:
(a) 0 ∈ a: Por definición, m + 0 = S
m
(0) = m. Veamos por inducción que 0 + m =
S
0
(m) = m: Si b = {m : 0 + m = m} entonces 0 ∈ b pues S
0
(0) = 0. Si m ∈ b
entonces, por el paso (3), 0 + m′ = (0 + m)′ = m′ luego m′ ∈ b. Puesto que b es
inductivo se deduce que b = ω.
(b) Si m ∈ a entonces m′ ∈ a: Fijemos m ∈ a. Sea c = {j ∈ ω : m′ + j = j +m′}. Por el
paso anterior 0 ∈ c. Supongamos que n ∈ c. Por el paso (3), tenemos
m′ + n′ = [m′ + n]′ = [n+m′]′ = [n+m]′′ = [m+ n]′′ = (m+ n′)′ = (n′ +m)′ = n′ +m′
Luego n′ ∈ c. Concluimos que c es inductivo, luego c = ω. Esto implica que m′ ∈ a.
(5) Fijemos m,n ∈ ω. Sea
d = {o ∈ ω : (m+ n) + o = m+ (n+ o)}
Es inmediato que 0 ∈ d. Supongamos que o ∈ d. Entonces
(m+ n) + o′ = [(m+ n) + o]′ = [m+ (n+ o)]′ = m+ (n+ o)′ = m+ (n+ o′)
luego o ∈ d. Concluimos que d es inductivo, luego d = ω.
�
Para cada número natural m ∈ ω definimos la función de recursión
(4) P
m
(0) = 0, P
m
(n′) = P
m
(n) +m ∀n ∈ ω
18 G. PADILLA
El producto de dos números naturales n,m ∈ ω se define como
(5) mn = Pm(n)
La demostración del siguiente resultado se deja de ejercicio.
Proposición 3.8.2. El producto de números naturales satisface las siguientes propiedades:
(1) 0n = 0.
(2) m(n′) = mn+m.
(3) mn = nm.
(4) m(no) = (mn)o.
(5) m(n+ o) = mn+mo.
[Demostración] Ejercicio. �
3.9. Orden de los naturales. La relación de pertenencia define un orden en los números natu-
rales. Notemos que
• Si m ∈ n y n ∈ p entonces m ∈ p: Por el Lema 3.5.5.
• ∀m ∈ ω(m 6∈ m): Por el Lema 3.5.8.
• Si m ∈ n entonces n 6∈ m: Supongamos lo contrario; es decir que m ∈ n y n ∈ m. Entonces,
por la observación anterior, m ∈ m. Esto contradice el Lema 3.5.8.
Lema 3.9.1. Dados m,n ∈ ω se tiene: m ∈ n si y solo si m′ ∈ n′.
[Demostración] Antes que nada; recordemos qued
• Por el Lema 3.5.7 se tiene que (m = n)⇔ (m′ = n′) para cualesquiera m,n ∈ ω.
• Por definición, n′ = n ∪ {n} para cualquier n ∈ ω.
A continuación verificamos ambas implicaciones.
(⇒) Sea a = {n : ∀m(m ∈ n ⇒ m′ ∈ n′)}. Es inmediato que 0 = ∅ ∈ a. Para ver que a es
inductivo, supongamos que n ∈ a. Para demostrar que n′ ∈ a fijemos un m ∈ n′ arbitrario;
mostraremos que m′ ∈ n′′. Consideremos dos casos:
m ∈ n: Entonces, por la definición de a, se tiene m′ ∈ n′ ∈ n′′. Por la transitividad de los
naturales (Lema 3.5.5), m′ ∈ n′′.
m = n: Entonces, por la definicióndel sucesor, m′ = n′ ∈ n′′ = n′ ∪ {n′}.
(⇐) Supongamos que m′ ∈ n′ = n ∪ {n}. Luego m′ ∈ n o m′ = n. Puesto que m ∈ m′, por la
transitividad de los números naturales (Lema 3.5.5) se tiene que m ∈ n en cualquier caso.
�
Teorema 3.9.2 (Principio de Tricotomı́a). Dados m,n ∈ ω una, y solo una de las siguientes
posibilidades, es cierta: m = n, m ∈ n ó n ∈ m.
[Demostración] Separemos la demostración en dos partes:
Las tres posibilidades son excluyentes: Esto es consecuencia de la transitividad de los naturales
(Lema 3.5.5) y la propiedad de regularidad (Lema 3.5.8). La demostración es sencilla; se deja de
ejercicio.
Para cada entero vale una de las tres posibilidades: Sea
a = {n ∈ ω : ∀m ∈ ω[(n = m) ∨ (m ∈ n) ∨ (n ∈ m)]}
Notemos que
TEORÍA DE RAMSEY 19
• 0 ∈ a: Considere b = {m ∈ ω : (m = 0) ∨ (0 ∈ m)}. Desde luego, 0 ∈ b. Si m ∈ b y m 6= 0,
entonces 0 ∈ m ∈ m′. Por la transitividad de los naturales, 0 ∈ m′; luego m′ ∈ b. Se
concluye que b es inductivo, luego b = ω; de donde 0 ∈ a.
• n ∈ a ⇒ n′ ∈ a: Sea m ∈ ω. Si m ∈ n′ no hay nada que demostrar. Supongamos lo
contrario: m 6∈ n′ = n ∪ {n}; entonces m 6∈ n y m 6= n. Puesto que n ∈ a; deducimos que
n ∈ m. Ello nos lleva a considerar otros dos casos: (a) m = n′; entonces, de nuevo, no hay
nada que demostrar. (b) m 6= n′; entonces, por el Lema 3.9.1, deducimos que n ∈ n′ ∈ m′.
Por la transitividad de los naturales, n ∈ m′, como se deseaba.
�
Corolario 3.9.3. Dados m,n ∈ ω; se tiene m ∈ n si y solo si m ( n.
[Demostración] Si m ∈ n entonces, por transitividad, m ⊆ n y la contención es estricta. Por
otra parte, Si m ( n (contención estricta) entonces, por el principio de tricotomı́a, m y n son
comparables: (m ∈ n) ∨ (n ∈ m). Ahora bien; si n ∈ m entonces, por la primera implicación
n ⊆ m y, entonces, son iguales. Ello contradice que la contención sea estricta. Se concluye que
n 6∈ m. De nuevo; por el principio de tricotomı́a, m ∈ n. �
Teorema 3.9.4 (Principio de Buen Orden para ω). Todo subconjunto no vaćıo de ω posee un
primer elemento. En otras palabras: si a ⊆ ω y a 6= ∅; entonces existe un único m ∈ a tal que,
para cualquier otro n ∈ a, se tiene (m = n) ∨ (m ∈ n).
[Demostración] Sea a ⊆ ω y supongamos que a no posee un primer elemento. Considere
b = {m : ∀k ∈ ω[k ∈ m ⇒ k 6∈ a]}
Notemos que
• 0 ∈ b: Pues para k = 0 = ∅, el condicional es trivial.
• m ∈ n ⇒ m′ ∈ b: Supongamos que m ∈ b. Entonces, dado k ∈ m′ = m ∪ {m} consid-
eramos dos casos. (a) k ∈ m; luego k 6∈ a. (b) k = m: Supongamos que m = a. Dado
que (n ∈ a) ⇒ (n 6∈ m); Por el principio de tricotomı́a, esto implica que (n ∈ a) ⇒ (n =
m)∨ (m ∈ n); i.e. m es el primer elemento de a. Esto es una contradicción; la cual se debe
a nuestra suposición inicial. Concluimos que m 6∈ a.
Deducimos que b es inductivo; luego b = ω. Esto implica que a = ∅.
�
3.10. Ejercicios.
(1) Principio de inducción fuerte: Sea a ⊆ ω; supongamos que para todo n ∈ ω se tiene la
siguiente propiedad: [∀m(m ∈ n⇒ m ∈ a)]⇒ n ∈ a. Entonces a = ω.
[Demostración] Es suficiente demostrar que a es inductivo. Es inmediato que 0 ∈ a. Por
otra parte, dado n ∈ a; supongamos que n′ 6∈ a. Entonces, por contrarrećıproco; existe
m ∈ n′ = n ∪ {n} tal que m 6∈ a. Notemos que m 6= 0 y m 6= n. Sea entonces
b = {j ∈ n : j 6∈ a}
Este conjunto es no vaćıo pues m ∈ b; por el principio del buen orden (Teorema 3.9.4) b
posee un primer elemento, digamos i ∈ b. Como los naturales son transitivos (Lema 3.5.5);
obtenemos j ∈ i ⇒ j ∈ n ⇒ j ∈ a (pues de lo contrario, si j 6∈ a entonces j ∈ b luego i
20 G. PADILLA
no seŕıa el primer elemento de b). Por la hipótesis del problema, esto implica que i ∈ a; lo
cual es una contradicción. Se deduce que n′ ∈ a. �
(2) Dados m,n, p ∈ ω;
(a) m ∈ n ⇔ (m+ p) ∈ (n+ p).
(b) Si p 6= 0; entonces m ∈ n ⇔ (mp) ∈ (np).
[Demostración] Ambas afirmaciones se demuestran por inducción. Verificamos la primera.
(⇒): Sea
a = {p ∈ ω : ∀m,n ∈ ω(m ∈ n)⇒ [(m+ p) ∈ (n+ p)]}
Es inmediato que 0 ∈ a. Supongamos que p ∈ a. Entonces, dados cualesquiera m,n ∈ ω;
si m ∈ n entonces (m+ p) ∈ (n+ p). En virtud de los Lemas 3.8.1 y 3.9.1,
m+ p′ = (m+ p)′ ∈ (n+ p)′ = n+ p′
luego p′ ∈ a.
(⇐) Consideremos
b = {p : S
p
es inyectiva }
Es inmediato que 0 ∈ b. Supongamos que p ∈ b y m+ p′ = n+ p′ para algunos m,n ∈ ω.
Entonces (m + p)′ = m + p′ = n + p′ = (n + p)′. Por el Lema 3.9.1, esto implica que
m + p = n + p. Como S
p
es inyectiva, se concluye que m = n. De la arbitrariedad de
m,n deducimos que S
p′ es inyectiva, e.d. p
′ ∈ b. Luego b es inductivo, de donde = ω y
obtenemos el resultado.
De un modo similar se demuestra la segunda afirmación. �
(3) Dados m,n ∈ ω; si m ∈ n entonces existe k ∈ ω tal que m+ k = n.
[Demostración] Similar al ejercicio anterior. �
En la situación del ejercicio (3), solemos decir que k es la diferencia entre m y n; y
escribimos k = m− n.
3.11. Números enteros. La construcción de los números enteros es algebraica: El conjunto de
los números enteros Z = ω × ω/ ∼ es el conjunto cociente de ω × ω partido por la relación de
equivalencia
R : (a, b) ∼ (c, d)⇔ b+ c = a+ d
Notemos que
(1) R es una equivalencia: Verificamos las propiedades,
(a) Reflexiva: (a, b) ∼ (a, b) es trivial, pues a+ b = a+ b.
(b) Simétrica: Pues (a, b) ∼ (c, d) ⇔ b+ c = a+ d ⇔ a+ d = b+ c ⇔ (c, d) ∼ (a, b).
(c) Transitiva: Supongamos que (a, b) ∼ (c, d) y (c, d) ∼ (e, f). Consideramos las
siguientes posibilidades tricotómicas:
• a ∈ b: Sea k = (b− a) ∈ ω, e.d. a+ k = b. Como a+ d = b+ c = (a+ k) + c =
a + (k + c); por el ejercicio (2) parte (a) de la sección de arriba, se tiene que
d = k + e; luego k = d− e y, desde luego, c ∈ d. De un modo similar se verifica
que e ∈ f y k = f − e. Entonces (b− a) = k = (f − e); luego a+ f = b+ e.
• a 3 b: Similar al caso anterior.
TEORÍA DE RAMSEY 21
• a = b: Como a+ d = b+ c, se tiene que c = d. De modo similar se verifica que
e = f . Ahora bien; puesto que a = b y e = f , se tiene que a + f = b + e, e.d.
(a, b) ∼ (e, f).
(2) Z es un conjunto: Por §2.12. Un número entero es la clase de equivalencia [a, b] ∈ Z de
un par (a, b) ∈ ω × ω.
(3) Suma de enteros: En Z se define la siguiente operación de suma:
[a, b] + [x, y] := [a+ x, b+ y]
Esta operación:
(a) Está bien definida: Si [a, b] = [c, d] y [x, y] = [w, z] entonces a+d = b+c y x+z = y+w.
Por la Proposición 3.8.1; (a+ x) + (d+ w) = (a+ d) + (x+ z) = (b+ c) + (y + w) =
(b+ y) + (c+ w); luego [a+ x, b+ y] = [c+ w, d+ z].
(b) Posee elemento neutro: Este es la clase [0, 0].
(c) Es conmutativa y asociativa: Porque se define a partir de la suma en los naturales,
que es conmutativa y asociativa, cf. Prop. 3.8.1.
(d) Hay elementos opuestos: Para cada [a, b] ∈ Z existe [x, y] ∈ Z tal que [a, b] + [x, y] =
[0, 0]. Basta tomar x = b, y = a; etonces [a, b] + [b, a] = [a + b, b + a] = [0, 0]. Al
opuesto de [a, b] lo denotamos [b, a] = −[a, b].
(4) Producto de números enteros: El producto de dos números enteros [a, b]; [c, d] ∈ Z es
[a, b] · [x, y] = [ay + bx, ax+ by]
Notemos que esta operación depende del producto y la suma definidos para a, b, x, y en el
conjunto de los naturales ω. La operación,
(a) Está bien definida: Supongamos que [a, b] = [c, d] y [x, y] = [w, z]. Debemos de-
mostrar que [a, b] · [x, y] = [c, d] · [w, z]; es decir, que
(6) [ay + bx, ax+ by] = [cz + dw, cw + dz]
En otras palabras; en términos de la equivalencia R, tenemos que a + d = b + c,
x+ z = y + w y debemos demostrar que
(7) ay + bx+ cw + dz = ax+ by + cz + dw
Las dos igualdades (??) y (??) son equivalentes; es suficiente demostrar una de ellas.
Dividimos la argumentación en tres casos excluyentes:
(i) Alguno de los enteros [a, b], [x, y] es cero: Sunpongamos, por ejemplo, que [a, b] =
[0, 0] = [c, d], por lo cual a = b y c = d. Por la definición del producto y la
Proposición 3.8.2;
[a, b] · [x, y] = [ay+bx, ax+by] = [ay+ax, ax+ay] = [a(y+x), a(x+y)] == [a(x+y), a(x+y)][0, 0]
De modo similar se muestra que [c, d] · [w, z] = [0, 0], con lo cual se verifica la
igualdad (??).
(ii) a ∈ b, x ∈ y: Comovimos en el punto (4.a); c ∈ d, w ∈ z y, más aún; existen
j, k ∈ ω tal que (b− a) = k = (d− c) y (y − x) = j = (z − w). Entonces
(b− a)(x− y) = kj = (c− d)(z − w)
Por la Proposición 3.8.2 y la distributividad de los signos (punto 4.c de arriba)
deducimos que
bx+ ay − by − ax = cz + dw − cw − dz
Esta última igualdad es equivalaente a (??).
22 G. PADILLA
(iii) Otros casos: Los casos restantes son (a ∈ b) ∧ (x 3 y), (a 3 b) ∧ (x 3 y); ambos
se tratan de modo similar al anterior.
(b) Posee elemento absorbente: Este es la clase [0, 0].
(c) Posee elemento neutro: Este es la clase [0, 1].
(d) Es conmutativa y asociativa: Porque se define a partir de la suma en los naturales,
que es conmutativa y asociativa, cf. Prop. 3.8.1.
(e) Distribuye respecto a la suma: Dados [a, b], [c, d], [x, y] en Z, por la distributividad
del producto en ω (Proposición 3.8.2, propiedad 5); se tiene
([a, b] + [c, d]) · [x, y] = [a+ c, b+ d] · [x, y]
= [(a+ c)y + (b+ d)x, (a+ c)x+ (b+ d)y]
= [ay + bx, ax+ by] + [cy + dx, cx+ dy]
= [a, b] · [x, y] + [c, d] · [x, y]
(f) Vale la ley de cancelación: Dado [a, b] y [x, y] en Z; si [a, b] · [x, y] = [0, 0] entonces
[a, b] = [0, 0] o [x, y] = [0, 0]. Para demostrar esto; notemos primero que una ley
similar vale para el producto en ω; si m,n ∈ ω y mn = 0 entonces m = 0 o n = 0;
ello es consecuencia de la definición del producto, y se puede deducir fácilmente de
la Proposición 3.8.2. Para verificarlo en Z supongamos que x, y ∈ ω y x 6= y. Sin
pérdida de generalidad, podemos asumir que x ∈ y; etonces
[a, b] · [x, y] = [0, 0] ⇔ [ay + bx, ax+ by] = [0, 0] ⇔ ax+ by = ay + bx
Puesto que x ∈ y, sea j ∈ ω tal que x+ j = y. Entonces, por las proposiciones 3.8.1
y 3.8.2;
ax+ by = ay + bx ⇒ ax+ b(x+ j) = a(x+ j) + bx ⇒ bj = aj
Aplicando la ley de cancelación en ω, esto implica que a = b, luego [a, b] = [0, 0].
Nota: De las observaciones anteriores se deduce que Z es un dominio entero en el sentido
de la teoŕıa de anillos; cf.[18].
(5) Orden de los números enteros: Dotamos a Z del orden parcial siguiente:
[a, b] < [x, y] ⇔ (b+ x) ∈ (a+ y)
Verificamos que
(a) Está bien definida: Supongamos de nuevo que [a, b] = [c, d] y [x, y] = [w, z]; es decir,
qued a+ d = b+ c y x+ z = y + w. Entonces; por el resultado del Ejercicio 3.10-(2)
y la Proposición 3.8.1,
(b + x) ∈ (a + y) ⇒ (b + x) + w ∈ (a + y) + w = a + (y + w) = a + (x + z)
⇒ x + (b + w) ∈ (a + z) + x ⇒ (b + w) ∈ (a + z)
⇒ (b + w) + d ∈ (a + z) + d = z + (a + d) = z + (b + c)
⇒ b + (w + d) ∈ b + (z + c) ⇒ (w + d) ∈ (z + c)
TEORÍA DE RAMSEY 23
(b) Es Transitiva: Supongamos que [a, b] < [c, d] y [c, d] < [x, y]. Sean j, k ∈ ω tales que
j + (b+ c) = (a+ d) y k + (d+ x) = (c+ y). Por los mismos argumentos de antes,
[j + (b + c)] + [k + (d + x)] = (a + d) + (c + y) ⇒ (j + k) + (b + x) + (d + c) = (a + y) + (d + c)
⇒ (j + k) + (b + x) = (a + y)
⇒ (b + x) ∈ (a + y)
⇒ [a, b] < [x, y]
(c) Es no reflexiva: Es inmediata del Lema 3.5.8.
(d) Satisface la Tricotomı́a: La tricotomı́a en Z para dos enteros [a, b], [c, d]; es una con-
secuencia inmediata de la tricotomı́a en ω para los números naturales (b+ c), (a+ d).
(6) La suma de enteros preserva el orden: En otras palabras, dados [a, b], [c, d], [x, y] en Z;
por el resultado del Ejercicio 3.10-(2)
[a, b] < [c, d] ⇔ (b + c) ∈ (a + d)
⇔ (b + c) + (x + y) ∈ (a + d) + (x + y)
⇔ (b + y) + (c + x) ∈ (a + x) + (d + y)
⇔ [a + x, b + y] < [c + x, d + y]
⇔ [a, b] + [x, y] < [c, d] + [x, y]
(7) El producto por enteros positivos preserva el orden: En otras palabras, dados [a, b], [c, d],
[x, y] en Z; con [0, 0] ∈ [x, y]; se tiene [a, b] < [c, d] ⇔ [a, b] · [x, y] < [c, d] · [x, y]. Esto es
inmediato, la demostración es similar a la del punto anterior.
(8) Z contiene una copia de ω: Para cada par (a, b) se tiene alguna de las siguientes posibili-
dades excluyentes:
(a) (a ∈ b)⇔ [a, b] = [0, b− a]: Si a ∈ b entonces, por el ejercicio (3) de la sección anterior,
sea k = b − a; e. d. k ∈ ω tal que a + k = b = b + 0. Entonces, por definición,
(a, b) ∼ (0, k); e.d. [a, b] = [0, k] = [0, b− a].
(b) (b ∈ a)⇔ [a, b] = [a− b, 0]: Similar al caso anterior.
(c) (a = b)⇔ [a, b] = [0, 0]: Entonces a+ 0 = a = b = 0 + b.
Cada m ∈ ω se identifica con la clase [0,m] ∈ Z. Como consecuencia de (a), la función
ω
Φ
-Z m 7→ [0,m]
satisface las siguientes propiedades:
(d) Φ es inyectiva: por la parte (a).
(e) Φ(m+ n) = Φ(m) + Φ(n), ∀m,n ∈ ω.
(f) Φ(mn) = Φ(m) · Φ(n), ∀m,n ∈ ω.
(g) [a, b] > [0, 0] ⇔ ∃k ∈ ω : Φ(k) = [a, b]. Este k es precisamente la diferencia b− a del
Ejercicio 3.10-(3).
Las observaciones anteriores justifican la siguiente notación usual: Para cada m ∈ ω iden-
tificamos, en adelante, a m con Φ(m) ∈ Z. De este modo
m = [0,m] −m = −[0,m] = [m, 0]
tiene perfecto sentido, pues
m+ (−m) = [0,m] + [m, 0] = [m,m] = [0, 0] = 0
24 G. PADILLA
Es inmediato que 0 = −0. En general, −(−z) = z para todo z ∈ Z. Esta notación preserva
la ”distributividad” de los signos. Asimismo,
[a, b] = [0, b] + [a, 0] = b+ (−a) = b− a
Notemos que el −a solo tiene sentido en Z, y nunca en ω.
3.12. Números racionales. Los números racionales son una nueva extensión algebraica de los
enteros. Se construyen del modo siguiente: En Z× (Z\{0}) consideramos la siguiente equivalencia:
(a, b) ∼ (c, d) ⇔ ad = bc
donde, ahora, a, b, c, d ∈ Z son números enteros. Las siguientes observaciones se dejan de ejercicio:
(1) La relación de arriba es una equivalencia. Los números racionales son los elementos del
cociente Q = Z×(Z\{0})∼ . La clase de un par (a, b) en Z× (Z\{0}) será denotada [a, b].
(2) Los racionales [0, 1] y [1, 1] serán denotados, respectivamente, 0Q , 1Q . Cuando no exista
duda omitiremos los sub́ındices y escribiremos simplemente 0, 1 ∈ Q.
(3) Q admite una suma dada por:
[a, b] + [c, d] = [ad+ bc, bd]
Esta operación es conmutativa, asociativa, y posee elemento neutro 0 ∈ Q. Posee asimismo
elementos opuestos; el opuesto de un número racional [a, b] es −[a, b] = [−a, b].
(4) Q admite un producto dada por:
[a, b] · [c, d] = [ac, bd]
Esta operación es conmutativa, asociativa, posee elemento neutro 1 ∈ Q y elemento ab-
sorbente 0 ∈ Q, y distribuye respecto a la suma. Los racionales diferentes de 0 poseen
inversos; el inverso de [a, b] 6= 0 es [a, b]−1 = [b, a].
(5) Para todo [a, b] ∈ Q se tiene [a, b] · 0 = 0.
(6) Q es un dominio entero: Si r, s ∈ Q entonces r · s = 0 ⇔ r = 0 ó s = 0.
(7) Q posee un orden parcial dado por la siguiente relación:
[a, b] <Q [c, d]⇔ ad <Z bc
Cuando no exista duda, omitiremos el sub́ındice y escribiremos simplemente [a, b] < [c, d].
Proposición 3.12.1. El orden de Q es total (lineal); e.d. cualesquiera dos números racionales
siempre son comparables. El orden en Q satisface la ley de Tricotomı́a.
[Demostración] Dados cualesquiera x, y ∈ Q tomemos algunos representantes, x = [a, b], y =
[c, d] con a, b, c, d ∈ Z; b y d distintos de 0. Consideremos los enteros u = ad, v = bc. Puesto que el
orden de los enteros es tricotómica; tenemos tres posibilidades excluyentes: u = v, u < v, u > v.
Estas tres posibilidades son equivalentes a los casos x = y, x < y, x > y. �
Proposición 3.12.2. Sean r, s, t ∈ Q. Entonces:
(1) r < s ⇒ r + t < s+ t.
(2) Si t > 0 entonces r < s ⇔ rt < st.
[Demostración] Vamos por pasos. Sean r = [a, b], s = [c, d], t = [e, f ] con a, b, c, d, e, f ∈ Z;
Supongamos que r < s, es decir, ad <Z bc. Entonces,
TEORÍA DE RAMSEY 25
(1) Por definición, r + t = [af + be, bf ], s+ t = [cf + de, df ]. Luego
(af + be)df = (ad)f
2
+ bdef < (bc)f
2
+ bdef = (cf + de)bf
implica que r + t < s+ t.
(2) Puesto que 0 = [0, 1]; tenemos que 0 <Q t si y solo si 0 <Z e. Como f 6= 0 tenemos que
ef 6= 0; luego
ad <Z bc ⇒ (ad)(ef) <Z (bf)(ce) ⇔ rt <Q st
�
Proposición 3.12.3. Q contiene una copia de Z.
[Demostración] Considere la función Z
Ψ
-Q dada por Ψ(p) = [p, 1]. Muestre que esta
función posee propiedades similares a la Φ dada en la sección de números enteros §3.11-(8). �
Proposición 3.12.4. Sip, q ∈ Q y p < q entoncesexiste r ∈ Q tal que p < r < q.
[Demostración] De hecho, existen infinitos racionales distintos entre p y q. Es suficiente tomar,
por ejemplo, r = [1,m] · (p + q) donde m ∈ ω, m > 0. La demostración formal se deja como
ejercicio. �
3.13. Números reales. Usamos para la construcción de Dedekind de los números reales. Un
corte de Dedekind es un subconjunto x ⊆ Q tal que:
(1) ∅ 6= x 6= Q.
(2) ∀q ∈ Q (q ∈ x) ∧ (r < q)⇒ r ∈ x (decimos que x es ”cerrado hacia abajo”).
(3) x no posee un elemento máximo; e. d. no existe q ∈ x tal que ∀r ∈ x(r ≤Q q).
Por ejemplo: los siguientes conjuntos son cortes de Dedekind,
• {[1,m] : 0 <Z m};
• {q : (q < 1) ∨ (q · q < 2)}
El conjunto de los números reales es el subconjunto R ⊆ P(Q) de todos los cortes de Dedekind.
El orden en R se define como sigue:
x ≤R y ⇔ x ⊆ y
Proposición 3.13.1. R es totalmente ordenado.
[Demostración] Sean x 6= y en R. Supongamos que x 6< y; es decir, x 6⊆ y. Entonces existe
algún r ∈ (x\y). Tomemos q ∈ y; y notemos que r 6∈ y ⇒ q 6= r. Asimismo, si r <Q q entonces,
por la propiedad (2), r ∈ y lo cual, de nuevo, contradice la elección de r. Por la tricotomı́a en
Q concluimos que q < r y, como r ∈ x, de nuevo por la propiedad (2), se deduce que q ∈ x.
Finalmente; de la arbitrariedad en la elección de q se deduce que ∀q ∈ y(q ∈ x), es decir, y ⊆ x;
luego y < x. �
Dado a ⊆ R diremos que a es acotado superiormente ⇔ existe algún c ∈ R tal que ∀y ∈
a(y ≤ c). Cualquier c que satisfaga la propiedad anterior es una cota superior de a.
Un supremo de a ⊆ R es una cota superior s de a tal que, para cualquier otra cota superior c de
a se tiene s ≤ c.
26 G. PADILLA
Teorema 3.13.2 (Axioma del supremo). Todo subconjunto no vaćıo y superiormente acotado de
R posee un supremo.
[Demostración] Sea ∅ 6= a ⊆ R superiormente acotado. Consideremos s = ∪a; demostraremos
que s es un supremo de a.
(1) s es un número real: Como los elementos de a ⊆ R son subconjuntos de Q; es claro que
s = ∪a ⊆ Q. Verificaremos que s es un corte de Dedekind.
(a) s 6= ∅: Trivial.
(b) s es cerrado hacia abajo: Si q ∈ s y r < q entonces existe algún x ∈ a tal que q ∈ x.
Puesto que x es un corte de Dedekind; por la propiedad (2) r ∈ x; luego r ∈ s.
(c) s no tiene elemento máximo: Suponga que q ∈ s es un elemento máximo en s y sea
x ∈ a tal que q ∈ x. Es inmediato que q es un elemento máximo en x; pero esto es
una contradicción, pues x es un corte de Dedekind.
(2) s es una cota superior de a: Por la definición de s es inmediato que si x ∈ a entonces
x ⊆ s; luego x ≤R s.
(3) s es la menor cota superior de a: Si c es cualquier otra cota superior de a entonces x ≤R s
para todo x ∈ a; es decir, ∀x ∈ a(x ⊆ c); luego s = ∪a ⊆ c, i.e. s ≤R c.
�
3.14. Suma en R . La suma de dos números reales x, y ∈ R es
x+ y := {p+ q : p ∈ x, q ∈ y}
Entonces
(1) x+ y 6= ∅: Trivial.
(2) x+ y 6= Q: Como x 6= Q y y 6= Q tomemos p 6∈ x, q 6∈ y. Entonces para todo a ∈ x, b ∈ y
se tiene necesariamente que a < p, b < q; luego a + b < p + q. De la arbitrariedad de a, b
deducimos que
a+ b < p+ q ∀ a ∈ x, b ∈ y
es decir, r < (p+ q)∀r ∈ (x+ y). En particular; (p+ q) 6∈ x+ y.
(3) x+ y es cerrado hacia abajo: Dados q ∈ x, r ∈ y; si p < (q + r) entonces, sumando (−q),
por la Prop. 3.12.2, (p − q) < r; luego por la propiedad (2) tenemos que (p − q) ∈ y.
Entonces p = q + (p− q) ∈ x+ y por definición.
(4) s no tiene elemento máximo: Dado p+ q ∈ x+ y, como x, y no poseen elemento máximo;
existen a ∈ x, b ∈ y, tales que p < a, q < b. Luego p + q < p + b < a + b por la Prop.
3.12.2.
Luego x+ y es un corte de Dedekind.
Teorema 3.14.1. La suma de números reales satisface las siguientes propiedades:
(1) Conmutativa: x+ y = y + x.
(2) Asociativa: (x+ y) + z = x+ (y + z).
(3) Elemento neutro 0R := {p : p < 0Q}.
(4) Opuestos: Para cada x ∈ R su opuesto es el conjunto −x := {p ∈ Q : ∃q(q > p)∧(−q 6∈ x)}.
(5) Continua: x < y ⇔ para todo z ∈ R se tiene x+ z < y + z.
[Demostración] Las tres primeras propiedades son inmediatas. Verificamos (3);
• −x es un corte de Dedekind:
�
TEORÍA DE RAMSEY 27
4. Conjuntos equipotentes
4.1. Conjuntos equipotentes. Dos conjuntos a, b son equipotentes si existe una biyección
a
φ
- b; esto lo denotamos por A ≈ B. Por ejemplo; 3 ≈ {1, 2, 3}; ω ≈ Q.
Teorema 4.1.1. Para cualesquiera conjuntos a, b, c siempre se tiene:
(1) a ≈ a.
(2) (a ≈ b)⇒ (b ≈ a).
(3) (a ≈ b) ∧ (b ≈ c)⇒ (a ≈ c).
[Demostración] Ejercicio. �
Teorema 4.1.2. Dados cualesquiera conjuntos a, b existen c, d tales que a ≈ c, b ≈ d, y c∩ d = ∅.
[Demostración] Tome c = a× {∅}; d = b× {1}. �
4.2. Potencias de conjuntos. Dados cualesquiera conjuntos a, b definimos la potencia a
b
como
el conjunto de todas las funciones b
ψ
- a (no necesariamente biyectivas). Es claro que a
b ⊆
P(b× a); por el Teorema de reemplazo, ab es un conjunto.
Teorema 4.2.1. La potencia de conjuntos satisface las siguientes propiedades:
(1) (a ≈ c) ∧ (b ≈ d)⇒
(
a
b ≈ cd
)
.
(2) (b ∩ c = ∅)⇒
(
a
b∪c ≈ ab × ac
)
.
(3) (a× b)c ≈ ac × bc .
(4)
(
a
b
)c
≈ ab×c .
[Demostración] Vamos por pasos; en cada caso construimos una biyección α.
(1) Dadas a
φ
- c, b
ψ
- d biyecciones; la función a
b α- c
d
dada por α(f) = φfψ
−1
es una biyección.
(2) La función a
b∪c α- a
b×ac dada por α(f) = (f |
b
, f |
c
) es una biyección; donde el śımbolo
f |
b
denota la restricción de cualquier función b ∪ c
f
- a a b; es decir, la composición
con la inclusión b
ıb- b ∪ c
f
- a; f |
b
= fı
b
.
(3) Si a × b
π1- a, a × b
π2- b son las proyecciones coordenadas; entonces la función
(a× b)c
α
- a
c × bc dada por α(f) = (π1f, π2f) es una biyección.
(4) Se deja de ejercicio.
�
Teorema 4.2.2. Para todo conjunto a se tiene P(a) ≈ 2a .
28 G. PADILLA
[Demostración] La función P(a)
χ
- 2
a
que a cada subconjunto b ⊆ a lo manda enla función
a
χb- 2 χ
b
(x) =
{
1 x ∈ b
0 x 6∈ b
es una biyección; su inversa ν es la función que a cada a
f
- 2 la manda en ν(f) = f
−1
({1}).
�
Teorema 4.2.3. No existe una función sobreyectiva de un conjunto a en P(a).
[Demostración] Suponga que existe a
f
-P(a) sobreyectiva, y considere b = {x ∈ a : x 6∈
f(x)}; por el Teorema de Reemplazo b ⊆ a es un conjunto, luego b ∈ P(a). Puesto que f es
sobreyectiva; existe c ∈ a tal que f(c) = b. Notemos entonces que c ∈ b ⇔ c 6∈ b; lo cual es una
contradicción. �
Corolario 4.2.4 (Teorema de Cantor). Para todo conjunto a se tiene a 6≈ P(a).
En adelante utilizaremos la notación a w b para decir que existe alguna función inyectiva
a
f
- b. Escribiremos a ≺ b si a w b y a 6≈ b.
Lema 4.2.5. Si c ⊆ a y a w c entonces a ≈ c.
[Demostración] Vamos a construir una familia de subconjuntos de a de manera recursiva. Sea
a
f
- c inyectiva. Definamos
a0 = a\c an+1 = f(an) ∀n ∈ ω
Sea A = ∪
n∈ω
a
n
. Notemos que, por definición,
f(A) = f
(
∪
n∈ω
an
)
= ∪
n∈ω
f(an) = ∪
n∈ω
an+1 ⊆ A
Consideremos la función
a
F
- c F (x) =
{
f(x) x ∈ A
x x 6∈ A
Etonces:
• F es inyectiva: Sean x 6= y en a. Debemos mostrar que F (x) 6= F (y). Si ambos x, y 6∈ A es
inmediato. Por otra parte; si x ∈ A, y 6 inA; entonces F (x) = x 6∈ A, pero F (y) = f(y) ∈ A;
luego F (x) 6= F (y). Finalmente; si ambos x, y ∈ A entonces F (x) = f(x), F (y) = f(y);
por la inyectividad de f obtenemos F (x) 6= F (y).
• F es sobreyectiva: Sea y ∈ c. Si y 6∈ A entonces F (y) = y, luego y está en la imagen. Por
otra parte; si y ∈ A entonces existe algún n ∈ ω tal que y ∈ a
n
. Para n = 0 esto no es
posible, pues a0 = a\c y, por hipótesis, y ∈ c, lo cual llevaŕıa a una contradicción. Para
n > 0 entonces n = m+ 1 para algún m; y y ∈ am+1 = f(am), luego existe x ∈ am tal que
y = f(x) = F (x), de donde y está en la imagen.
�
TEORÍA DE RAMSEY 29
Teorema 4.2.6 (Schroeder-Bernstein). Dados dos conjuntos a, b; si a w b y b w a entonces a ≈ b.
[Demostración] Sean a
f
- b, b
g
- a inyectivas, c = g(b) ⊆ a. Aplique el Lema 4.2.5 a
a, c. �
Por ejemplo; es inmediato que [0, 1] ≈ (0, 1) ≈ R .
4.3. Conjuntos finitos. Un conjunto a es finito ⇔ a ≈m para algún m ∈ ω; e infinito en caso
contrario.
Proposición 4.3.1. Sea a un conjunto finito. Toda función inyectiva de a en a es biyectiva.
[Demostración] Puesto que todo conjunto finito es equipotente a un número natural; es sufi-
ciente demostrar el enunciado para todo número natural a = n ∈ ω. Sea
b = {n ∈ ω : toda inyección de n en n es biyectiva}
Es obvio que 0 = ∅ ∈ b. Supongamos que n ∈ b y sea n′
f
- n′ una inyección. Consideramos
dos posibilidades:
(1) f [n] ⊆ n: Entonces la restricción f |n es inyectiva, y va de n en n. Puesto que n ∈ b se
tiene que f |
a
es biyectiva, y f [n] = n (como conjuntos). De nuevo, por la inyectividad de
f , esto implica que f(n) 6∈ n, luego f(n) = n, de donde f es biyectiva.
(2) f [n] 6⊆ n: Sea x ∈ n tal que f(x) 6∈ n, entonces necesariamente f(x) = n. Por la inyec-
tividad de f , esto implica que f(n) 6= n, luego, de modo similar, f(n) ∈ n de modo que
existe y ∈ n tal que f(n) = y. Finalmente, si z ∈ n es diferente de x, y entonces, por la
inyectividad de f , se tiene que f(z) ∈ n. Definamos
n
g
- n g(z) =

f(z) (z 6= x) ∧ (z 6= y)
y z = x
x z = y
n z = n
Es inmediato que g es inyectiva y satisface g[n] ⊆ n; luego g es biyectiva. Se deduce que f
también es biyectiva.
�
Corolario 4.3.2. Ningún conjunto finito es equipotente a un subconjunto propio.
[Demostración] Puesto que todo conjunto finito es equipotente a un número natural; de-
mostraremos un enunciado equivalente, a saber, que ”ningún número natural es equipotente a
un número natural menor”.
Sean m ∈ n ∈ ω; y supongamos que m ≈ n. Tomemos una biyección n
f
-m. Puesto que
m ⊆ n, la inclusión define una función inyectiva de m en n; y la composición de ambas funciones
n
f
-m
ı
- n
30 G. PADILLA
da una función inyectiva de n en śı mismo. Por la Proposición 4.3.1, g = ıf es biyectiva. Sea
h = f
−1
la inversa de f . Entonces
gh = (ıf)h = ı(fh) = ıid = ı
de donde ı es una composición de funciones biyectivas, por lo cual es biyectiva. Se deduce que
m = ı[m] = n. Puesto que m ∈ n por hipótesis; por el principio de tricotomı́a en ω -véase el
Teorema 3.9.2- llegamos a una contradicción. �
Corolario 4.3.3. Dados a, b conjuntos; si b ⊂ a y b ≈ a entonces a es infinito.
Corolario 4.3.4. ω es infinito.
[Demostración] Por el Corolario 4.3.3; basta tomar b = ω\{0} = {1, 2, . . . } y verificar que la
función ω
f
- b dada por n 7→ n′ es una biyección. Los detalles se dejan de ejercicio. �
Corolario 4.3.5. Todo conjunto finito es equipotente a un único número natural.
[Demostración] Sea a un conjunto finito. Suponga que m ≈ a ≈ n para m,n ∈ ω. Entonces
m ≈ n. Por el Teorema 4.3.2 m no puede ser subconjunto propio de n, y viceversa. Esto implica
que m 6∈ n y n 6∈ m. Por el principio de tricotomı́a (Teorema 3.9.2), m = n. �
4.4. Conjuntos totalmente ordenados.
Proposición 4.4.1 (Principio de inducción transfinita). Sea (x,<) un conjunto bien ordenado, y
φ(u) una fórmula de la teoŕıa de conjuntos. Si, para cada a ∈ x, se tiene [∀b ∈ x(b < a)⇒ φ(b)]⇒
φ(a); entonces φ(a) vale para todo a ∈ x.
[Demostración] Suponga lo contrario; entonces, por el Teorema de Separación 2.7.1, aplicado
a x, φ; se tiene que y = {b ∈ x : ¬φ(b)} ⊆ x es un subconjunto no vaćıo; luego y posee un primer
elemento, digamos a ∈ y. Ahora bien; por la definición de a se tiene ∀z ∈ x(z < a) ⇒ (z 6∈ y)
pues, de lo contrario, a no seŕıa el primer elemento de y. De este modo,
∀z ∈ x(z < a)⇒ φ(z)
Por la hipótesis sobre la fórmula φ(u) esto implica que φ(a) es válida; luego a 6∈ y, lo cual de nuevo
lleva a una contradicción. �
Un morfismo entre conjuntos parcialmente ordenados (x,<), (y,<); es una función x
f
- y
tal que f es ”creciente” en el sentido siguiente: x < y ⇒ f(x) < f(y). Un isomorfismo es un
morfismo f tal que f es biyectiva. Note que, si f es un isomorfismo, entonces su inversa g = f
−1
también es un isomorfismo.
Proposición 4.4.2. Si dos conjuntos totalmente ordenados son isomorfos, entonces el isomorfismo
entre ellos es único.
[Demostración] Sean (x,<)
f,g
- (y,<) dos isomorfismos entre conjuntos totalmente orde-
nados. Puesto que f, g son isomorfismos, x, y son bien ordenados; f, g mandan ambas al primer
elemento de x (digamos x0) en el primer elemento de y (digamos y0); es decir, f(x0) = y0 = g(x0).
Por lo tanto, φ(x
0
) es válida.
TEORÍA DE RAMSEY 31
Dado a > x
0
en x; supongamos que
[∀b ∈ x(b < a)⇒ f(b) = g(b)] ∧ [f(a) 6= g(a)]
Como y está bien ordenado, sin pérdida de generalidad, supongamos que f(a) < g(a) (el caso g(a) <
f(a) se puede tratar aparte, de modo similar). Puesto que h = g
−1
es un isomorfismo, tenemos
entonces que h(f(a)) < h(g(a)) = a. Por la suposición de arriba, f(h(f(a))) = g(h(f(a))) = f(a).
Puesto que f es biyectiva, esto implica que h(f(a)) = a. Aplicando g a ambos lados obtenemos
f(a) = g(h(f(a))) = g(a), lo cual es una contradicción. Se deduce que nuestra suposición es falsa.
En resumen; si para todo b < a se tiene f(b) = g(b), entonces f(a) = g(a). En términos de la
fórmula φ(u) := [f(u) = g(u)], acabamos de demostrar que
[∀b ∈ x(b < a)⇒ φ(b)] ⇒ φ(a)
Si aplicamos ahora el principio de inducción transfinita a φ(u), definida en x, obtenemos ∀a ∈
x[φ(a)]; es decir, ∀a ∈ x[f(a) = g(a)]. Luego f ≡ g. �
Corolario 4.4.3. Si (x,<) es totalmente ordenado; entonces el único isomorfismo de x en śı
mismo es la función identidad.
[Demostración] Es inmediato que la función identidad es un isomorfismo de x en śı mismo. La
Prop. 4.4.2 implica que no hay más isomorfismos. �
Proposición 4.4.4. Si (x,<) es bien ordenado, y ⊆ x es un subconjunto bien ordenado de x y
(x,≤)
f
- (y ≤) es un isomorfismo; entonces a ≤ f(a) para todo a ∈ x.
[Demostración] La demostración es similar a la de la Prop. 4.4.2; dejamos los detalles de
ejercicio. �
4.5. Segmentos iniciales. Fijemos un conjunto bien ordenado (x,<). Un segmento inicial de
x es un subconjunto y ⊆ x tal que y es transitivo respecto al orden parcial. Es decir,
∀a ∈ y ∀b ∈ x (b < a)⇒ (b ∈ y)
En tal caso, solemos escribir y v x. Decimos que y es un segmento inicial propio si y v x y y ⊂ x
está propiamente contenido en x; en cuyo caso escribimos y @ x.
Dado a ∈ x, el segmento inicial inducido por a es el subconjunto
S(x, a) = {b ∈ x : b < a}
El conjunto de todos los segmentos iniciales de x lo denotamos por S(x).
Lema 4.5.1. La unión de segmentos iniciales es un segmento inicial.
[Demostración] Sea Y ⊂ P(x) un conjunto de segmentos iniciales de x, veamos que y = ∪Y es
un segmento inicial. Si b < a ∈ y entonces a ∈ z para algún z ∈ Y . Puesto que z es un segmento
inicial, b ∈ z, luego b ∈ y. �
Proposición 4.5.2. Ningún conjunto totalmente ordenado es isomorfo a un segmento inicial
propio.
32 G. PADILLA
[Demostración] Un segmento inicial y v x es propio ⇔ existe alǵun a ∈ (x\y). Este elemento
a satisface entonces ∀b ∈ y(a > b). Suponga que existe un isomorfismo, digamos, x
f
- y.
En virtud de la Prop. 4.4.4, ∀u ∈ x[u ≤ f(u)]. En particular, a ≤ f(a) ∈ y, lo cual es una
contradicción. �
Por ejemplo; con el orden usual de los reales, y = [0, 1] no puede ser bien ordenado, pues
f(t) = t/2 es un isomorfismo de y en z = [0, 1/2], y z @ y.
Lema 4.5.3. y @ x ⇔ ∃a ∈ x[y = S(x, a)].
[Demostración] Procedemos por pasos.
(⇒) y @ x si y solo si y es segmento inicial y subconjunto propio. Dado que w = x\y 6= ∅ y x es
bien ordenado; deducimos que w posee un primer elemento, digamos a = min(w). Entonces a 6∈ y
por lo cual ∀b ∈ y(b < a). Por otra parte, puesto que a es el primer elemento de w = (x\y), se
tiene ∀b 6∈ y(a ≤ b). Se deduce entonces que
∀b ∈ x[b < a⇔ b ∈ y]
En otras palabras; y = S(x, a).
(⇐) Suponga que y = S(x, a) para algún a ∈ x. Entonces y es propio, pues, de lo contrario, como
y = x, en particular y contiene al elemento a; con lo cual a ∈ S(x, a). Esto implica que a < a, lo
cual es absurdo. �
Proposición 4.5.4. Considere en S(x) la relación de orden @. La correspondencia
x
Φ
- S(x) a 7→ S(x, a)
es un isomorfismo.[Demostración] Primero que nada, veamos que Φ es un morfismo: Supongamos que b < a en
x. Entonces b 6∈ S(x, b), y b ∈ S(x, a). Por otra parte; z ∈ S(x, b) ⇔ [z < b], en cuyo caso, por
transitividad, z < a, luego z ∈ S(x, a). Se deduce que S(b, x) @ S(a, x). En particular, Φ es
biyectiva. Por el Lema 4.5.3 se tiene que Φ es sobreyectiva; luego es un isomorfismo. �
Corolario 4.5.5. Todo conjunto bien ordenado es isomorfo al conjunto de sus segmentos iniciales,
ordenados por contención.
Teorema 4.5.6 (Recursión transfinita). Sean (x,<) bien ordenado; y cualquier conjunto; F una
función (operador) tal que, a cada función S(x, a)
h
- y definida en algún segmento inicial de
x; F le asigna un único F (h) ∈ y. Entonces, existe una única función de recursión x
φ
- y
inducida por F ; tal que, para todo a ∈ x, se tiene φ(a) = F (φ � S(x, a)).
[Demostración] Antes que nada, expliquemos brevemente el enunciado: F es una función del
tipo ”tomar el supremo” (o el ı́nfimo, o la integral numérica) de una función h dada; es decir,
se comporta como un ”operador” el cual asigna, a cada función S(x, a)
h
- y, un elemento
F (h) ∈ y. Dada F ; la función de recursión φ se construye como sigue: Si x
0
∈ x es el primer
TEORÍA DE RAMSEY 33
elemento, entonces S(x, x
0
) = ∅ y S(x, x
0
)
h
- y es la función vaćıa h = ∅. Basta definir
φ(x0) = F (∅). Aplicando inducción transfinita, si a ∈ x y para todo b < a hemos definido φ(b);
entonces tenemos S(x, a)
φ
- y bien definida; es decir, tenemos φ restringida a S(x, a). Tiene
sentido tomar entonces φ(a) = F (φ � S(x, a)). Para demostrar esto, procedemos por pasos.
Unicidad: Sean φ, ψ dos funciones que satisfacen el enunciado. Entonces, por definición, φ(x
0
) =
F (∅) = ψ(x
0
). Dado a ∈ x; si φ(b) = ψ(b) para todo b < a, entonces φ � S(x, a) = ψ � S(x, a).
Puesto que φ, ψ satisfacen el enunciado, obtenemos que φ(a) = F (φ � S(x, a)) = F (ψ � S(x, a)) =
ψ(a). Se deduce que la fórmula ϕ(u) := [φ(u) = ψ(u)] satisface la hipótesis del principio de in-
ducción transfinita (Proposición 4.4.1). Luego φ(a) vale para todo a ∈ x; es decir, φ ≡ ψ.
Existencia: Sea H el conjunto de todas las funciones h definidas sobre algún segmento inicial
S(x, a); tales que para todo b ∈ S(x, a) se tiene h(b) = F (h � S(x, b)). En otras palabras:
H =
S(x, a) h - y
∣∣∣∣∣∣
1. a ∈ x.
2. h es una función.
3. ∀b[b < a ⇒ h(b) = F (h � S(x, b))]

Notemos que H 6= ∅ pues la función vaćıa h = ∅, definida en el segmento inicial S(x, x
0
) = ∅,
satisface h ∈ H. Consideremos la siguiente relación: Dadas h, g ∈ H, tales que h está definida en
S(x, a) y g está definida en S(x, b) para ciertos a, b ∈ x; diremos que
h @ g ⇔ [a < b] ∧ [h = g � S(x, b)]
Finalmente, sea φ = ∪H. Afirmamos que φ satisface las condiciones del enunciado; para de-
mostrarlo, notemos que:
(1) (H,@) es totalmente ordenado: Es inmediato que @ es un orden parcial en H. Dadas
h, g definidas respectivamente en S(x, a), S(x, b); puesto que x es bien ordenado, a, b son
comparables. Supongamos que a ≤ b. Entonces, es suficiente demostrar que h @ g. Para
ello, notemos que h(x
0
) = F (∅) = g(x
0
). Si c < a y para todo t < c se tiene h(t) = g(t)
entonces h � S(x, c) = g � S(x, c); luego h(c) = F (h � S(x, c)) = F (g � S(x, c)) = g(c).
Aplicando inducción transfinita en S(x, a) se deduce que h(c) = g(c) para todo c < a; es
decir h @ g; luego H es totalmente ordenado.
(2) φ Es una función: Por construcción, φ es el supremo del conjunto bien ordenado (H,@).
Dado u ∈ x, supongamos que (u, z); (u,w) ∈ φ. Entonces existen h, g ∈ H tal que (u, z) ∈ h
y (u,w) ∈ g; es decir, h(u) = z y g(u) = w. Puesto que H es totalmente ordenado;
h, g están definidas en S(x, a), S(x, b) respectivamente, y son comparables. Supongamos
sin pérdida de generalidad que h v g. Entonces u < a ≤ b y h = g � S(x, a); luego
z = h(u) = g(u) = w.
(3) dom(φ) = x: Puesto que dom(φ) = ∪{dom(h) : h ∈ H} es unión de segmentos iniciales, es
él mismo un segmento inicial. Si dom(φ) 6= x entonces es un segmento inicial propio. Por
el Lema 4.5.3 dom(φ) = S(x, a) donde a es el primer elemento de x que no pertenece al
dominio de φ. Entonces ψ = φ ∪ {(a, F (φ))} ∈ H, luego ψ no es el supremo de H, lo cual
es una contradicción.
(4) φ(a) = F (φ � S(x, a)) ∀a ∈ x: Es inmediata.
�
34 G. PADILLA
Proposición 4.5.7. Dos conjuntos bien ordenados o son isomorfos, o uno de ellos es isomorfo a
un segmento inicial propio del otro.
[Demostración] Sean (x,<), (y,<) dos conjuntos bien ordenados. Si y es isomorfo a algún
segmento inicial propio de x, ya está. Supongamos lo contrario; construiremos una inmersión
x
φ
- y, es decir, un morfismo tal que x
∼=- φ(x) es un isomorfismo. Para ello emplearemos
el principio de recursión.
Sea H el conjunto de todos los isomorfismos de algún segmento inicial propio de x en algún segmento
inicial de y. Es decir;
H =
S(x, a) h - y
∣∣∣∣∣∣
1. a ∈ x.
2. h es un morfismo.
3. h(S(x, a)) es un segmento inicial de y.

Este conjunto es no vaćıo pues la función vaćıa h = ∅ definida en S(x, x0), satisface h ∈ H;
donde como es usual x
0
es el primer elemento de x. Empleando la Proposición 4.4.2 y el principio
de inducción transfinita, se puede demostrar (procedimiento análogo al del teorema anterior) que
(H,@) es totalmente ordenado, donde h @ g si y solo si dom(h) ⊆ dom(g) y h = g � dom(h).
Consideramos el supremo φ = ∪H. Es inmediato que φ es una función y φ(x0) = y0 es el primer
elemento de y. Dado a ∈ x; supongamos que hemos definido φ � S(x, a). Entonces tenemos dos
opciones:
(1) φ(S(x, a)) = y; en cuyo caso φ es sobreyectiva y y es isomorfo a un segmento propio de x.
(2) φ � S(x, a) no es sobreyectiva para ningún elemento a ∈ x. En ese caso φ(S(x, a)) ⊂ y es
un segmento inicial (pues φ � S(x, a) es un isomorfismo) propio (pues φ no es sobreyectiva)
de y. Por el Lema 4.5.3; φ(S(x, a)) = S(y, b) donde b ∈ y es el primer elemento de y que
no pertenece a la imagen de φ � S(x, a). Definimos φ(a) = b. Debido a nuestra suposición;
φ(a) se puede definir para todo a ∈ x. Tenemos, de nuevo, dos posibilidades excluyentes:
(a) φ es sobreyectiva: Entonces φ es un isomorfismo de x en y.
(b) φ no es sobreyectiva: Entonces, por el mismo razonamiento anterior; φ es un isomor-
fismo de x en un segmento inicial propio de y.
�
4.6. Ejercicios.
(1) Deduzca el principio de inducción fuerte en ω a partir del principio de inducción transfinita:
[Demostración] (ω,∈) es un conjunto bien ordenado; todo segmento inicial propio de ω es
de la forma S(ω, n) para algún n ∈ ω. Por definición de los números naturales, S(ω, n) = n.
Aplicando el principio de inducción transfinita a ω y cualquier fórmula φ(u); obtenemos
que si, para cada n ∈ ω, se tiene [∀m ∈ nφ(m)]⇒ φ(n) entonces se tiene ∀n ∈ ω φ(n). �
(2) Da un ejemplo de un morfismo inyectivo (a,<)
α
- (b,<) cuya imagen no es un seg-
mento inicial de b.
[Demostración] Basta tomar como a el conjunto de todos los enteros pares, y b = ω, con
la inclusión a - b. �
(3) ¿Es ω isomorfo a ω\{0}?.
[Demostración] Śı. La función n 7→ n′ es un isomorfismo. �
TEORÍA DE RAMSEY 35
(4) Da un ejemplo de un conjunto totalmente ordenado (a,≤) y un isomorfismo a
α
- a tal
que x 6= α(x) para todo x ∈ a.
[Demostración] Tome (Z, <) con la función z 7→ z + 1. �
(5) ¿Es Q isomorfo a Q\{0}?
(6) Dado un conjunto (a,≤) totalmente ordenado; muestra que a está bien ordenado ⇔ todo
segmento inicial propio de a está bien ordenado. [Demostración] (⇒) es trivial. (⇐)
Sea b ⊂ a un subconjunto no vaćıo. �
(7) Halla dos conjuntos totalmente ordenados, no isomorfos, tales que cada uno de ellos es
isomorfo a un segmento inicial del otro.
5. Ordinales
Un ordinal es un conjunto a tal que
• (a,∈) está bien ordenado.
• a es transitivo, es decir; ∀x ∀y(x ∈ y ∈ a)⇒ (x ∈ a).
La familia de todos los conjuntos ordinales la denotamos por Ord. Por ejemplo
(1) ∅ es un ordinal.
(2) Todo número natural n ∈ ω es un ordinal.
(3) ω es un ordinal.
(4) Si α es un ordinal