Facultad de Matem´aticas Universidad de Sevilla

Teor´ıa de Conjuntos

Curso 2010–2011

Contenido I.

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

1

1.

Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

2.

La idea intuitiva de conjunto . . . . . . . . . . . . . . . . . . . . . . . .

6

2.A.

El lenguaje de la Teor´ıa de Conjuntos . . . . . . . . . . . . . . .

6

2.B.

Clases y conjuntos . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.

La Teor´ıa de Conjuntos de Zermelo–Fraenkel . . . . . . . . . . . . . . .

9

4.

Extensionalidad, Vac´ıo y Separaci´on . . . . . . . . . . . . . . . . . . . .

13

5.

Axiomas del Par, de la Uni´on y de las Partes . . . . . . . . . . . . . . .

13

6.

Par ordenado. Axioma del Producto Cartesiano . . . . . . . . . . . . .

14

7.

Relaciones y aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . .

15

8.

Funciones. Axioma de Reemplazamiento . . . . . . . . . . . . . . . . .

17

9.

Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

II.

Buenos ´ ordenes. Ordinales 1.

2.

3.

23

Clases bien ordenadas [[Z− ∗ ]] . . . . . . . . . . . . . . . . . . . . . . . .

23

1.A.

Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

1.B.

Los teoremas de minimizaci´on, inducci´on y recursi´on . . . . . .

24

1.C.

Isomorfismos entre clases bien ordenadas . . . . . . . . . . . . .

26

N´ umeros ordinales [[Z− ∗ ]] . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.A.

La clase de los n´ umeros ordinales . . . . . . . . . . . . . . . . .

28

2.B.

Ord como clase bien ordenada . . . . . . . . . . . . . . . . . . .

30

2.C.

Ordinales l´ımites . . . . . . . . . . . . . . . . . . . . . . . . . .

33

2.D.

Conjuntos bien ordenados y ordinales . . . . . . . . . . . . . . .

35

2.E.

Teoremas de inducci´on y recursi´on sobre Ord . . . . . . . . . .

35

El teorema del buen orden [[ZF∗ ]] . . . . . . . . . . . . . . . . . . . . .

36

i

Contenido

II

4.

Sucesiones de ordinales [[ZF− ∗ ]] . . . . . . . . . . . . . . . . . . . . . . .

37

5.

Aritm´etica ordinal [[ZF− ∗ ]] . . . . . . . . . . . . . . . . . . . . . . . . .

39

6.

N´ umeros naturales [[ZF− ∗ ]] . . . . . . . . . . . . . . . . . . . . . . . . .

41

7.

Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

III. Cardinales

45

1.

El n´ umero de elementos de un conjunto [[ZF− ∗ ]] . . . . . . . . . . . . . .

45

2.

Conjuntos finitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ´ 2.A. Algebra de conjuntos finitos [[Z− ∗ ]] . . . . . . . . . . . . . . . . .

47

Conjuntos D–finitos [[ZF− ∗ ]] . . . . . . . . . . . . . . . . . . . . .

49

3.

Conjuntos numerables [[ZF− ∗ ]] . . . . . . . . . . . . . . . . . . . . . . .

50

4.

N´ umeros enteros y racionales [[ZF− ∗ ]] . . . . . . . . . . . . . . . . . . . .

53

4.A.

N´ umeros enteros . . . . . . . . . . . . . . . . . . . . . . . . . .

53

4.B.

N´ umeros racionales . . . . . . . . . . . . . . . . . . . . . . . . . ´ Ordenes totales densos . . . . . . . . . . . . . . . . . . . . . . .

54

5.

Conjuntos no numerables. La funci´on ℵ [[ZF∗ ]] . . . . . . . . . . . . . .

56

6.

Aritm´etica cardinal [[ZF∗ ]] . . . . . . . . . . . . . . . . . . . . . . . . .

58

6.A.

Suma y producto . . . . . . . . . . . . . . . . . . . . . . . . . .

59

6.B.

Exponenciaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

N´ umeros reales [[ZF∗ ]] . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

7.A.

Completaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . .

61

7.B.

Topolog´ıa de la recta real . . . . . . . . . . . . . . . . . . . . .

63

7.C.

El cardinal de R. La Hip´otesis del Continuo, CH . . . . . . . .

64

8.

Aritm´etica cardinal infinita [[ZF∗ ]] . . . . . . . . . . . . . . . . . . . . .

67

9.

Exponenciaci´on cardinal [[ZF∗ ]] . . . . . . . . . . . . . . . . . . . . . .

69

9.A.

Cofinalidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

9.B.

Cardinales regulares . . . . . . . . . . . . . . . . . . . . . . . .

70

9.C.

El lema de K¨onig . . . . . . . . . . . . . . . . . . . . . . . . . .

71

9.D.

Las funciones Continuo y Gimel . . . . . . . . . . . . . . . . . .

72

9.E.

La Hip´otesis Generalizada del Continuo, GCH . . . . . . . . .

73

Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

2.B.

4.C.

7.

10.

IV. El axioma de regularidad

47

54

81

Contenido

III

1.

La clase WF [[ZF∗ ]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

2.

El axioma de regularidad [[ZF∗ ]] . . . . . . . . . . . . . . . . . . . . . .

84

3.

∈–Inducci´on y ∈–recursi´on [[ZF− ∗ ]] . . . . . . . . . . . . . . . . . . . . .

86

3.A.

Relaciones adecuadas . . . . . . . . . . . . . . . . . . . . . . . .

86

3.B.

Teoremas de inducci´on y recursi´on sobre relaciones bien fundamentadas y adecuadas . . . . . . . . . . . . . . . . . . . . . . .

86

Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87

4. V.

El Axioma de Elecci´ on 1.

89

Resultados conjuntistas equivalentes a AC . . . . . . . . . . . . . . . .

89

1.A.

El Axioma de Elecci´on . . . . . . . . . . . . . . . . . . . . . . .

89

1.B.

Principios maximales . . . . . . . . . . . . . . . . . . . . . . . .

90

2.

Cardinales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

3.

Formas d´ebiles del Axioma de Elecci´on . . . . . . . . . . . . . . . . . .

91

4.

Equivalencias bajo el axioma de regularidad . . . . . . . . . . . . . . .

93

5.

Espacios compactos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

94

6.

Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

VI. Espacios Polacos 1.

Espacios Polacos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.A.

2.

3.

4.

99 99

1.B.

Conjuntos Gδ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 ´ Arboles [[ZF∗ ]] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

1.C.

El espacio m´etrico Aω

. . . . . . . . . . . . . . . . . . . . . . . 102

Inmersiones entre Espacios Polacos . . . . . . . . . . . . . . . . . . . . 103 2.A.

El Conjunto de Cantor . . . . . . . . . . . . . . . . . . . . . . . 103

2.B.

Esquemas de Lusin . . . . . . . . . . . . . . . . . . . . . . . . . 104

Espacios Polacos no numerables . . . . . . . . . . . . . . . . . . . . . . 106 3.A.

Espacios Polacos perfectos . . . . . . . . . . . . . . . . . . . . . 106

3.B.

El teorema de Cantor–Bendixson [[ZF∗ + ACω ]] . . . . . . . . . 108

3.C.

La derivada de Cantor–Bendixson [[ZF∗ ]] . . . . . . . . . . . . . 110

Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

Cap´ıtulo I La Teor´ıa de Conjuntos de Zermelo–Fraenkel §1

Objetivos

Los objetivos b´asicos de la Teor´ıa de Conjuntos son los siguientes. 1. Fundamentar las Matem´aticas: Desde el punto de vista de la Teor´ıa de Conjuntos todos los objetos matem´aticos son conjuntos. ´ (–) En Algebra se estudia la estructura de grupo. Un grupo es un conjunto con una ´ operaci´on entre sus elementos que satisface ciertas propiedades. En Algebra es irrelevante la naturaleza conjuntista de los elementos de un grupo: dos grupos isomorfos son id´enticos. Sin embargo, desde la fundamentaci´on que proporciona la Teor´ıa de Conjuntos, los elementos de un grupo tambi´en son conjuntos. A lo largo del curso se describir´an los objetos m´as importantes en Matem´aticas: (–) Conjuntos b´asicos en Matem´aticas: N´ umeros naturales (II.6), enteros, racionales (III.3) y reales (III.7). (–) Conjuntos esenciales en Matem´aticas: Aplicaciones y relaciones (I.7). Para obtener esta descripci´on se introduce la Teor´ıa de Conjuntos de Zermelo–Fraenkel. Para la Teor´ıa de Conjuntos este objetivo es secundario. Por ejemplo, se define el conjunto de los n´ umeros reales, R, y las operaciones aritm´eticas habituales (suma y producto), la relaci´on de orden y el valor absoluto. Sin embargo, se considera que a partir de estas definiciones, con una formaci´on b´asica en Matem´aticas, se puede probar sin grandes dificultades que: R es un cuerpo conmutativo, el orden es total y denso, y con respecto al valor absoluto es un espacio m´etrico separable y completo. 2. Conjuntos y clases: La idea intuitiva de que toda colecci´on de objetos es un conjunto es inconsistente (ver I.2). Existen colecciones de objetos que no son conjuntos y las denominaremos clases propias. Es importante determinar que ciertas clases son propias. 1

2

1. Objetivos

La clase de todos los conjuntos y la clase de los n´ umeros ordinales son los ejemplos m´as importantes de clases propias. 3. Inducci´on y recursi´on: Las pruebas por inducci´on y las definiciones por recursi´on son herramientas b´asicas en Matem´aticas. Sin embargo, no es posible justificar determinadas construcciones usando esta metodolog´ıa (inducci´on y recursi´on) sobre los n´ umeros naturales, conjunto que se denota por ω. Para ello introduciremos la clase de los n´ umeros Ordinales (ω es un ordinal) y demostramos que esta clase satisface los teoremas de inducci´on y recursi´on. En el curso veremos numerosas aplicaciones del uso de inducci´on y recursi´on sobre la clase de los n´ umeros ordinales y sobre ordinales mayores que ω; por ejemplo, en el estudio sobre subconjuntos de R: conjuntos de Borel, anal´ıticos, de Baire y medibles. Hist´oricamente, el primer resultado cuya prueba requiere una definici´on por recursi´on sobre un ordinal mayor que ω, trata sobre la existencia y estructura del mayor subconjunto sin puntos aislados de un conjunto (cerrado) de n´ umeros reales (para m´as detalles ver VI.3.C). Puntos aislados: En lo que sigue R es el conjunto de los n´ umeros reales. (–) Sean a, b ∈ R tales que a < b. El intervalo abierto de extremos a y b, (a, b), es (a, b) = {c ∈ R : a < c < b}. (–) Sea A ⊆ R. (–) Sea a ∈ A. Diremos que a es aislado en A si existen b1 < b2 ∈ R tales que A ∩ (b1 , b2 ) = {a}. (–) A0 = {a ∈ A : a no aislado en A}. (–) Por recursi´on sobre n ∈ ω definimos A(n) . ½ A, si n = 0; (n) A = (m) 0 A , si n = m + 1. Sea A ⊆ R. Diremos que A es n–Cantor si ∀m < n [A(m) 6= ∅] ∧ A(n) = ∅. Seguidamente describiremos conjuntos n–Cantor. Sea a ∈ R. Un conjunto 1–Cantor: Sea A1,a = {a}. Es evidente que A1,a es 1–Cantor. Un conjunto 2–Cantor: Para cada n ∈ ω sea an = a − A2,a = {an : n ∈ ω} ∪ {a}.

1 . n+1

Sea

Para todo n ∈ ω, an es aislado en A2,a . Por tanto, A02,a = A1,a = {a}. En consecuencia, A2,a es 2–Cantor. S Un conjunto 3–Cantor: Sea A3,a = n∈ω A2,an ∪ {a}. Entonces S S S A03,a = ( n∈ω A02,an ) ∪ {a} = ( n∈ω A1,an ) ∪ {a} = ( n∈ω {an }) ∪ {a} = A2,a . Por tanto, A3,a es 3–Cantor. Un conjunto 4–Cantor: Sea A4,a = Por tanto, A4,a es 4–Cantor.

S n∈ω

A3,an ∪ {a}. Entonces A04,a = A3,a .

Cap´ıtulo I.

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

3

T Un conjunto ω–Cantor: Sea A(ω) = n∈ω A(n) . Diremos que un conjunto es ω–Cantor si ∀n ∈ ω [A(n) 6= ∅] ∧ A(ω) = ∅. ¿Existe un conjunto ω–Cantor? Sean ~b = {bk : k ∈ ω} una sucesi´on creciente de S n´ umeros reales, y A~b = k∈ω Ak+1,bk . Entonces S S (1) (1) (–) A~b = k∈ω Ak+1,bk = k≥1 Ak,bk ; S S (2) (2) (–) A~b = k∈ω Ak+1,bk = k≥2 Ak−1,bk . Por tanto, T (n) = ∅. n∈ω A En consecuencia, A~b es ω–Cantor. 0

Un conjunto (ω + 1)–Cantor: Sea A(ω+1) = A(ω) . Diremos que A es (ω + 1)– Cantor si A(ω) 6= ∅ ∧ A(ω+1) = ∅. ¿Existe un conjunto (ω + 1)–Cantor? En el ejemplo anterior supongamos que la sucesi´on {bk : k ∈ ω} es convergente. Sean c = limk∈ω bk , y A~b,c = A~b ∪ {c}. (n)

(ω)

(ω+1)

Entonces para todo n ∈ ω, c ∈ A~b,c . En consecuencia, A~b,c = {c} y A~b,c Por tanto, A~b,c es (ω + 1)–Cantor.

= ∅.

M´as importante, que el ejemplo anterior, para la consolidaci´on de la Teor´ıa de Conjuntos es la prueba del Teorema del Buen Orden: Todo conjunto puede ser bien ordenado. En este caso es necesaria una definici´on por recursi´on sobre la clase de los ordinales. Las pruebas por inducci´on y las definiciones por recursi´on sobre clases bien ordenadas es la forma m´as com´ un de estas metodolog´ıas. La propiedad fundamental para aplicar estas herramientas es que todo subconjunto no vac´ıo tiene un elemento minimal. Puesto que no es necesario que exista un u ´nico elemento minimal, podemos usar inducci´on y recursi´on sobre ´ordenes parciales que verifiquen la propiedad anterior. 4. Cardinales: El objetivo principal de la Teor´ıa de Conjuntos es estudiar el concepto de cardinal (n´ umero de elementos) de un conjunto. En el Cap´ıtulo III estableceremos las propiedades b´asicas de las operaciones entre cardinales infinitos. Mientras que la suma y el producto de cardinales (asociadas a la uni´on y al producto cartesiano) tienen una soluci´on elemental, la exponenciaci´on (asociada a las partes de un conjunto) no es posible determinarla. En este sentido, uno de los problemas m´as conocidos es la Hip´otesis del Continuo, CH: para todo A ⊆ R, ¿es A numerable o tiene el cardinal de R? La Hip´otesis del Continuo es independiente de la Teor´ıa de Conjuntos de Zermelo– Fraenkel; es decir, en esta teor´ıa no se puede probar la Hip´otesis del Continuo ni su negaci´on. 5. El Axioma de Elecci´on, AC: El Axioma de Elecci´on es el axioma de la Teor´ıa de Conjuntos que ha suscitado m´as controversia. El Cap´ıtulo V est´a dedicado al estu-

4

1. Objetivos

dio del Axioma de Elecci´on. Se probar´a la equivalencia del Axioma de Elecci´on con otras propiedades (lema de Zorn, . . . ) usadas en Matem´aticas. Uno de los objetivos es aprender a determinar cuando se usa el Axioma de Elecci´on y si es posible eliminar su uso. En algunos casos el Axioma de Elecci´on s´olo hace que la prueba sea m´as simple. En otros, la prueba del resultado en su forma m´as general usa el Axioma de Elecci´on; sin embargo, casos particulares de ´este, de gran inter´es, no requieren el Axioma de Elecci´on para su demostraci´on. Por ejemplo: Lema. (AC). Si A es un conjunto infinito, existe f : A −→ A2 biyectiva. La prueba de este resultado requiere el uso del Axioma de Elecci´on. Sin embargo, se tiene que: Lema. (–) Si A es un conjunto numerable infinito, existe f : A −→ A2 biyectiva. (–) Existe f : R −→ R2 biyectiva. Veamos otro ejemplo. Lema. Sean X de Hausdorff y A ⊆ X. A compacto

=⇒

A cerrado.

´ n: Supongamos que A no es cerrado. Entonces existe a ∈ cl(A) − A. Demostracio Puesto que X es de Hausdorff, para cada x ∈ A existen Gx y Ux abiertos tales que (–) x ∈ Gx , a ∈ Ux , (–) Gx ∩ Ux = ∅.

S Es evidente que A ⊆ x∈A Gx . Puesto que A es compacto, existen Gx1 , . . . , Gxn tales que A ⊆ Gx1 ∪ . . . ∪ Gxn . Entonces (–) a ∈ Ux1 ∩ . . . ∩ Uxn . (–) A ∩ (Ux1 ∩ . . . ∩ Uxn ) = ∅. Lo cual est´a en contradicci´on con a ∈ cl(A). La prueba anterior usa el Axioma de Elecci´on para elegir Gx y Ux . Para los siguientes espacios es posible eliminar el uso del axioma de elecci´on. Espacios segundo numerables: Sea B = {Vn : n ∈ ω} una base numerable de X. Para cada x ∈ X sean ¾ ½ x ∈ Vk ∧ a ∈ Vk0 Gx = Vn 0 ⇐⇒ (n, m) = (µ(k, k )) Vk ∩ Vk0 = ∅. Ux = V m   r = d(x, a) Gx = B(x, r/2) Espacios m´etricos: Para cada x ∈ X sean  Ux = B(a, r/2) En ambos casos la prueba procede como anteriormente. Sin embargo, la prueba del lema no requiere el uso del Axioma de Elecci´on. Nueva prueba: Supongamos que A no es cerrado, sea a ∈ cl(A) − A. Sea

Cap´ıtulo I.

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

5

GA = {G ∈ G(X) : ∃U ∈ G(X) (a ∈ U ∧ G ∩ U = ∅)}. Se tiene que: Aserto. Para todo x ∈ A existe G ∈ GA tal que x ∈ G. Prueba del aserto: Sea x ∈ A. Puesto que X es de Hausdorff, existen Gx y Ux abiertos tales que x ∈ Gx , a ∈ Ux y Gx ∩ Ux = ∅. Lo que prueba el aserto. 2 S Por el aserto, A ⊆ GA . Puesto que A es compacto, existen G1 , . . . , Gn ∈ GA tales que A ⊆ G1 ∪ . . . ∪ Gn . Sean U1 , . . . , Un ∈ G(X) tales que para todo j, 1 ≤ j ≤ n, (–) a ∈ Uj , (–) Gj ∩ Uj = ∅. Entonces (–) a ∈ U1 ∩ . . . ∩ Un . (–) A ∩ (U1 ∩ . . . ∩ Un ) = ∅. Lo cual est´a en contradicci´on con a ∈ cl(A).

¥

Resumen de resultados: Resumimos a continuaci´on los resultados m´as importantes que se presentan en el curso. Teorema 1. (a) La clase de los ordinales, Ord, es una clase propia. (b) La relaci´on α < β es un buen orden sobre Ord Teorema 2. Son equivalentes: (a) El Axioma de Elecci´on. (b) Todo conjunto puede ser bien ordenado. Teorema 3. (a) |A| ≤ |B| ∧ |B| ≤ |A| (b) |A| < |P(A)|.

=⇒

|A| = |B|.

Teorema 4. ℵ0 < |R| = |Rn | = 2ℵ0 . Teorema 5. (a) ℵα + ℵβ = ℵα · ℵβ = max(ℵα , ℵβ ). (b) ℵα < 2ℵα = ℵαℵα . (c) (AC). ℵα+1 ≤ 2ℵα . ℵα < cf(2ℵα ). Teorema 6. (AC). ℵα+1 es regular. Teorema 7. (AC). Supongamos GCH(≡ ∀α (2ℵα = ℵα+1 )). Para todo λ ≥ ℵ0 , κ ≥ 2

6

2. La idea intuitiva de conjunto

 +  λ , si κ ≤ λ; λ κ = κ+ , si cf(κ) ≤ λ < κ  κ, si λ < cf(κ).

§2

La idea intuitiva de conjunto

En Matem´aticas el procedimiento b´asico para describir los objetos de estudio es caracterizarlos mediante una definici´on. Por ejemplo, sea R el conjunto de los n´ umeros reales Definici´on: Sea f una aplicaci´on de R en R. Diremos que f es continua si ∀x ∀ε > 0 ∃δ > 0 ∀y [d(x, y) < δ =⇒ d(f (x), f (y)) < ε]. Por tanto, debemos proceder a definir lo que es un conjunto. “Definici´on”: Un conjunto es cualquier colecci´on de objetos que verifican una determinada propiedad. La definici´on de funci´on continua se basa en otros conceptos definidos con anterioridad: aplicaci´on, n´ umeros reales, 0, relaci´on de orden, distancia. La definici´on de conjunto se construye usando: colecci´on, objetos, propiedad. Esta definici´on es (en apariencia) circular pues “colecci´on” y “objetos” son palabras sin´onimas de conjunto. M´as a´ un, en I.2.A y I.2.B veremos que la “definici´on” de conjunto dada anteriormente es “incorrecta”.

2.A

El lenguaje de la Teor´ıa de Conjuntos

Notas I.2.1. (Primera incorrecci´ on: La paradoja de Berry). Sea P (n) la propiedad: P (n) ≡ n es un n´ umero natural definible con menos de mil s´ımbolos. Consideremos el conjunto: C = {n : P (n)}. Sea m el menor n´ umero natural que no est´a en C. Se tiene que: (a) Existe m. Basta observar que C es finito. (b) m ∈ / C. Se sigue de la definici´on de m. (c) m ∈ C. En efecto, m est´a definido por: “el menor n´ umero natural no definible con menos de mil s´ımbolos”. Lo anterior es una definici´on de m que usa menos de mil s´ımbolos. De (b) y (c) se sigue una contradicci´on. El lenguaje de la Teor´ıa de Conjuntos. La contradicci´on obtenida en I.2.1 se debe a que la propiedad P (n) que considerabamos para definir al conjunto C no tiene una

Cap´ıtulo I.

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

7

formulaci´on adecuada. Ahora precisaremos lo que entenderemos que es una propiedad. (–) El lenguaje de la Teor´ıa de Conjuntos consta de un u ´nico s´ımbolo de predicado binario, ∈ (pertenencia). Adem´as, tiene los simbolos habituales: (–) variables: x, y, . . .; (–) = (igualdad); (–) conectivas proposicionales: ∨ (disyunci´on), ∧ (conjunci´on), → (implicaci´on), ↔ (equivalencia), ¬ (negaci´on); y (–) cuantificadores: ∃ (existencial) y ∀ (universal). Las f´ormulas del lenguaje de la Teor´ıa son: (–) x = y, (x es igual a y). (–) x ∈ y (x pertenece a y). (–) Si Φ y Ψ son f´ormulas, entonces las siguientes expresiones son f´ormulas (–) Φ ∨ Ψ, Φ ∧ Ψ, Φ → Ψ, Φ ↔ Ψ, ¬Φ. (–) Si Φ(x) es una f´ormula, entonces son f´ormulas (–) ∃x Φ(x) (existe x tal que Φ(x)). (–) ∀x Φ(x) (para todo x se tiene Φ(x)). Usaremos (–) (–) (–) (–) (–)

∀x ∈ y Φ(x) para denotar a ∀x (x ∈ y → Φ(x)). ∃x ∈ y Φ(x) para denotar a ∃x (x ∈ y ∧ Φ(x)). ∃!x Φ(x) para denotar a ∃x Φ(x) ∧ ∀x ∀y (Φ(x) ∧ Φ(y) → x = y). x 6= y para denotar a ¬(x = y). x∈ / y para denotar a ¬(x ∈ y).

Ahora podemos precisar que es una propiedad: (–) Una propiedad es una f´ormula del lenguaje de la Teor´ıa de Conjuntos. No se trata de realizar un desarrollo formal de la Teor´ıa de Conjuntos. Por tanto, las propiedades sobre conjuntos se presentar´an, analizar´an y demostrar´an de la forma habitual en Matem´aticas, con las notaciones espec´ıficas de la Teor´ıa de Conjuntos, ver I.2.3. Sin embargo, debemos tener presente que toda propiedad sobre conjuntos que consideremos debe transcribirse sin ambig¨ uedad al lenguaje de la Teor´ıa de Conjuntos. Por ejemplo, la propiedad P (x) (considerada en I.2.1) “x es un n´ umero natural definible con menos de mil s´ımbolos” s´olo la aceptar´ıamos si la transcribimos al lenguaje de la Teor´ıa de Conjuntos. Extensiones por definici´ on. El lenguaje de la Teor´ıa de Conjuntos es muy simple, s´olo tiene el s´ımbolo ∈ (pertenencia). Describir en este lenguaje propiedades sobre conjuntos es en general muy laborioso. Por ello el lenguaje se extiende a˜ nadi´endole nuevos simbolos que hace m´as simple la descripci´on de propiedades. Este proceso de

8

2. La idea intuitiva de conjunto

extensi´on del lenguaje se realiza en ciertas condiciones, descritas m´as abajo en (a) y (b), de forma que no es posible: (–) describir nuevas propiedades en la extensi´on (es decir, toda f´ormula de la extensi´on es equivalente a una del lenguaje original); (–) probar m´as propiedades sobre conjuntos (la extensi´on es conservativa). Los m´etodos de extensi´on se dividen en los siguientes tipos: (a) Predicados: Sean Φ(x1 , . . . , xn ) una f´ormula y p un nuevo s´ımbolo predicado n– ario. Se tiene que: Aserto. T + p + [p(x1 , . . . , xn ) ↔ Φ(x1 , . . . , xn )] es conservativa sobre T. Ejemplos: Contenci´on (x ⊆ y); x es una aplicaci´on; x es un ordinal (Ord(x)); x e y tienen el mismo cardinal (|x| = |y|). (b) Funciones: Sean Φ(x1 , . . . , xn , y) una f´ormula y f un nuevo s´ımbolo de funci´on n–aria (si n = 0, se considera un nuevo s´ımbolo de constante). Se tiene que: Aserto. Si T ` ∀~x ∃!y Φ(~x, y), entonces la teor´ıa T + f + [f (~x) = y ↔ Φ(~x, y)] es conservativa sobre T. Ejemplos: El conjunto vac´ıo (∅); la uni´on de x e y (x ∪ y); las partes de x (P(x)); el conjunto de los numeros naturales (ω); el conjunto de los n´ umeros reales (R); el cardinal de un conjunto (card(x)); la funci´on aleph (ℵα ).

2.B

Clases y conjuntos

Sea Φ(x) una f´ormula. La colecci´on de los conjuntos que satisfacen Φ(x) diremos que es una clase, que notaremos por: {x : Φ(x)}. Usaremos (–) las letras a, b, c, . . ., A, B, C, . . . para designar conjuntos. (–) las letras A, B, C, . . . (en negrita) para designar clases. Sea A la clase {x : Φ(x)}. Probar que (–) A es una clase propia, es decir que no es un conjunto, consiste en establecer que: ¬∃y ∀x [x ∈ y ↔ Φ(x)]. (–) A es un conjunto consiste en establecer que: ∃y ∀x [x ∈ y ↔ Φ(x)]. Teorema I.2.2. (Segunda incorrecci´ on: La paradoja de Russell). La clase {x : x ∈ / x} es una clase propia. ´ n: Supongamos que R = {x : x ∈ Demostracio / x} es un conjunto. Entonces

Cap´ıtulo I.

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

R∈R

⇐⇒

9

R∈ / R.

Lo cual es una contradicci´on.

¥

Nota I.2.3. (Operaciones y relaciones entre clases). En lugar de usar directamente f´ormulas del lenguaje de la Teor´ıa de Conjuntos, para referirnos a propiedades sobre conjuntos, usaremos el concepto de clase. Sean A = {x : Φ(x)} y B = {x : Ψ(x)} clases. En primer lugar prestaremos atenci´on a las relaciones b´asicas entre conjuntos: pertenecia, ∈, e igualdad, =. (–) Escribiremos x ∈ A y x ∈ / A en lugar de Φ(x) y ¬Φ(x), respectivamente. Nota: Observemos que si escribimos a ∈ A, entonces a es un conjunto. Si B es una clase propia, no tiene ning´ un sentido escribir B ∈ A. (–) A = B representar´a: ∀x (x ∈ A ⇐⇒ x ∈ B); es decir, ∀x [Φ(x) ↔ Ψ(x)]. (–) A 6= B representar´a: ¬(A = B). Ahora describiremos sobre clases las relaciones y operaciones b´asicas sobre conjuntos. (–) (–) (–) (–) (–) (–) (–) (–) (–) (–)

A ⊆ B representar´a: ∀x (x ∈ A =⇒ x ∈ B). A ⊂ B representar´a: A 6= B ∧ A ⊆ B. Ac = {x : x ∈ / A}. A ∩ B = {x : x ∈ A ∧ x ∈ B}. A ∪ B = {x : x ∈ A ∨ x ∈ B}. A − B = {x : x ∈ A ∧ x ∈ / B}. S A = {x : ∃y ∈ A (x ∈ y)}. T A = {x : ∀y ∈ A (x ∈ y)}. P(A) = {x : x ⊆ A}. La clase vac´ıa, ∅, es la clase definida por: ∅ = {x : x 6= x}.

(–) Par no ordenado de x e y, {x, y}, es la clase definida por: {x, y} = {z : z = x ∨ z = y}. (–) La clase universal, V, es la clase definida por: V = {x : x = x}.

§3

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

Si los conjuntos son los objetos b´asicos de las Matem´aticas, entonces no disponemos, como en el caso de las funciones continuas, de objetos m´as simples a partir de los cu´ales podamos definir lo que es un conjunto. La soluci´on consiste en caracterizar los conjuntos como los elementos de un sistema de objetos con una relaci´on binaria

10

3. La Teor´ıa de Conjuntos de Zermelo–Fraenkel

entre ellos (relaci´on de pertenencia) que satisfacen determinadas propiedades (f´ormulas del lenguaje de la Teor´ıa de Conjuntos) que denominaremos axiomas. Los conjuntos que existen son aquellos cuya existencia se puede probar usando estos axiomas. Los conjuntos satisfacen las propiedades que podamos deducir a trav´es de los axiomas. La Teor´ıa de Conjuntos apareci´o en la primeras d´ecadas del siglo XX. Con anterioridad, durante m´as de dos milenios, se desarrollaron conceptos, m´etodos y resultados matem´aticos muy importantes. Los axiomas de la Teor´ıa de Conjuntos sirven para fundamentar y unificar toda esta metodolog´ıa; en particular, el desarrollo que se hab´ıa llevado a cabo en la segunda mitad del siglo XIX. Por tanto, la configuraci´on del sistema axiom´atico es un acto convencional que est´a guiado por la necesidad de clarificar ciertos conceptos y justificar m´etodos y resultados sobre ´estos. La primera axiom´atica de conjuntos apareci´o en 1908. E. Zermelo introdujo estos axiomas para justificar la prueba del Teorema del Buen Orden que hab´ıa presentado en 1904. Los axiomas que presentamos son esencialmente los que consider´o Zermelo con ligeras modificaciones. El Axioma de Reemplazamiento fue introducido por Fraenkel (1922), el Axioma de Regularidad por Hausdorff (e independientemente por otros) (1920). T. Skolem (1925) propuso que el concepto de propiedad se sustituyese por el de f´ormula del lenguaje de primer orden de la Teor´ıa de Conjuntos.

Axiomas: Los axiomas de la Teor´ıa de Conjuntos de Zermelo–Fraenkel garantizan que los conjuntos satisfacen determinadas propiedades. Dividimos los axiomas en cuatro grupos. Grupo I: Existencia de determinados conjuntos: (–) Axioma del Vac´ıo, Ax0; (–) Axioma del Infinito, Ax8. Grupo II: Propiedades b´asicas de la relaci´on de pertenencia: (–) El car´acter fundamental: Axioma de Extensionalidad, Ax1. Lo importante es la extensi´on de un conjunto no la intenci´on (propiedades con las se puede definir dicho conjunto). (–) Descripci´on estructural: Axioma de Regularidad, Ax9. Es posible, sin usar este axioma, describir los objetos b´asicos de las Matem´aticas de tal forma que todos ellos lo satisfacen. Este axioma afirma que la relaci´on de pertenencia es bien fundamentada. Esto permite realizar pruebas por inducci´on sobre la relaci´on de pertenencia. Sin embargo, en Matem´aticas la naturaleza conjuntista de los elementos de un conjunto es, en general, irrelevante; por tanto, es poco habitual usar inducci´on y recursi´on sobre la relaci´on de pertenencia entre los elementos de un conjunto para establecer propiedades de dicho conjunto. Grupo III: Procesos para obtener conjuntos.

Cap´ıtulo I.

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

11

½

Axioma de Separaci´on, Ax2; Axioma de Reemplazamiento, Ax7.  Axioma del Par, Ax3;    Axioma de la Uni´on, Ax4; (–) Mediante operaciones: Axioma de las Partes, Ax5;    Axioma del Producto Cartesiano, Ax6.

(–) Usando propiedades:

Grupo IV: Axioma de Elecci´on, AC, Ax10. Todo conjunto puede ser bien ordenado. Este axioma es puramente existencial: afirma que existe un buen orden. Sin embargo, para conjuntos muy importantes (por ejemplo, los n´ umeros reales) no existe una descripci´on expl´ıcita de un buen orden del conjunto. Por ello su uso ha generado muchas controversias. Los axiomas de la Teor´ıa de Conjuntos de Zermelo–Fraenkel son los siguientes. Ax0. Axioma del Conjunto Vac´ıo. Existe un conjunto que no tiene elementos. ∃y ∀x (x ∈ / y). Ax1. Axioma de Extensionalidad. Si dos conjuntos tienen los mismos elementos, entonces son iguales. A ⊆ B ∧ B ⊆ A =⇒ A = B. Ax2. Axioma de Separaci´ on (esquema). Sea C una clase. Para todo conjunto A la clase {x : x ∈ A ∧ x ∈ C} = {x ∈ A : x ∈ C} = C ∩ A es un conjunto. Ax3. Axioma del Par. Para cualesquiera conjuntos x, y, la clase {x, y} = {z : z = x ∨ z = y} es un conjunto. Ax4. Axioma de la Uni´ on. Para todo conjunto A, la clase S A = {y : ∃x ∈ A (y ∈ x)} es un conjunto. Ax5. Axioma de las Partes. Para todo conjunto A, la clase P(A) = {x : x ⊆ A} es un conjunto. Ax6. Axioma del Producto Cartesiano. Para cualesquiera conjuntos A y B, la clase A × B = {hx, yi : x ∈ A ∧ y ∈ B} es un conjunto.

12

3. La Teor´ıa de Conjuntos de Zermelo–Fraenkel

Ax7. Axioma de Reemplazamiento (esquema). Si F es una funci´on, entonces para todo conjunto A la clase F[A] = {y : ∃x (x ∈ A ∧ F(x) = y)} = {F(x) : x ∈ A} es un conjunto Ax8. Axioma del Infinito. ∃x (∅ ∈ x ∧ ∀y ∈ x (y ∪ {y} ∈ x)). Ax9. Axioma de Regularidad. x 6= ∅ =⇒ ∃y ∈ x (x ∩ y = ∅). Ax10. Axioma de Elecci´ on, (AC). Para todo conjunto A existe f tal que f es una aplicaci´on ∧ dom(f ) = A ∧ ∀y ∈ A (y 6= ∅ =⇒ f (y) ∈ y). Diremos que f es una funci´on de elecci´on sobre A. En los cap´ıtulos que siguen usaremos las siguientes teor´ıas. Z Z− Z− ∗ ZF ZFC PA

Ext. s´ı s´ı s´ı s´ı s´ı s´ı

Sep. s´ı s´ı s´ı s´ı s´ı s´ı

Par si s´ı s´ı s´ı s´ı s´ı

Un. s´ı s´ı s´ı s´ı s´ı s´ı

Partes s´ı no no s´ı s´ı s´ı

Cart. si s´ı

Rp no no no s´ı s´ı s´ı

Inf. s´ı s´ı s´ı s´ı s´ı ¬Inf

Reg. s´ı s´ı no s´ı s´ı s´ı

Elec. no no no no s´ı s´ı

Si T es una teor´ıa, notaremos por (–) (–) (–) (–)

T∗ = T − Ax. Regularidad. T− = T − Ax. Partes. TF = T + Ax. Reemplazamiento. TC = T + AC.

En las siguientes secciones de este cap´ıtulo describiremos las notaciones que vamos a usar a lo largo del curso (algunas de ellas se han empleado para formular los axiomas) y estableceremos algunas propiedades elementales sobre conjuntos. No se trata de desarrollar de forma axiom´atica la Teor´ıa de Conjuntos. No estamos interesados en especificar los axiomas usados en cada demostraci´on. Sin embargo, (–) en cada cap´ıtulo al inicio de una secci´on o subsecci´on indicaremos los axiomas que usaremos en las pruebas de los resultados que all´ı aparecen; (–) el cap´ıtulo V est´a dedicado al estudio del Axioma de Elecci´on. En los cap´ıtulos que siguen los resultados que se obtengan estar´an probados en ZFC. Sin embargo, debido a la posici´on particular que ocupa el Axioma de Elecci´on, escribiremos las siglas AC (Axiom of Choice) delante de todos los resultados cuya prueba (o al menos la prueba que presentamos) dependa de este axioma. Por ejemplo,

Cap´ıtulo I.

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

13

Lema. (AC). Si A es un conjunto infinito, existe f : A −→ A2 biyectiva.

§4

Extensionalidad, Vac´ıo y Separaci´ on

´ n I.4.1. Ax0 ∧ Ax1 Proposicio

=⇒

∃!y ∀x (x ∈ / y).

´ n I.4.2. (El Conjunto Vac´ıo). A = ∅ Definicio Lema I.4.3. Ax2

=⇒

⇐⇒

∀x (x ∈ / A).

Ax0.

´ n: Sea A un conjunto. Por Ax2, la clase B = {x : x ∈ A ∧ x 6= x} es Demostracio un conjunto. Adem´as, ∀x (x ∈ / B). ¥ Lema I.4.4. (Ax2). Sea A una clase. Si existe un conjunto B tal que A ⊆ B, entonces A es un conjunto. ´ n: Sea B un conjunto tal que A ⊆ B. Entonces (por el axioma de Demostracio separaci´on) C = {x : x ∈ B ∧ x ∈ A} es un conjunto. Es evidente que ∀x (x ∈ A ⇐⇒ x ∈ C), Por tanto, A es un conjunto. Teorema I.4.5. Ax2

=⇒

¥ V es una clase propia.

´ n: En caso contrario, por Ax2, la clase {x : x ∈ V ∧ x ∈ Demostracio / x} es un conjunto. Es decir, {x : x ∈ / x} es un conjunto. Lo cual est´a en contradicci´on con el teorema I.2.2, paradoja de Russell. ¥

§5

Axiomas del Par, de la Uni´ on y de las Partes

´ n I.5.1. Definicio (a) {x, y} = {u : u = x ∨ u = y}. (b) {x} = {x, x}. ´ n I.5.2. Definicio S (a) A = {z : ∃u (u ∈ A ∧ z ∈ u)}. S (b) A ∪ B = {A, B} = {z : z ∈ A ∨ z ∈ B}. T (c) A = {z : ∀u (u ∈ A → z ∈ u)}.

14

6. Par ordenado. Axioma del Producto Cartesiano

T (d) A ∩ B = {A, B} = {z : z ∈ A ∧ z ∈ B}. (e) A − B = {z : z ∈ A ∧ z ∈ / B}. (f ) A 4 B = (A − B) ∪ (B − A). Lema I.5.3. [(Ax1, Ax2)] T (a) A 6= ∅ =⇒ A es un conjunto. T (b) ∅ = V. Sin embargo, si entendemos que ∅ ⊆ P(A) (es T decir, si consideramos a ∅ como una familia de subconjuntos de A), definimos ∅ = A (c) A ∩ B es un conjunto. (d) A − B es un conjunto. ´ n I.5.4. Definicio (a) A ⊆ B ⇐⇒ ∀z (z ∈ A =⇒ z ∈ B). [[A es un subconjunto de B]]. (b) A ⊂ B ⇐⇒ A ⊆ B ∧ A 6= B. [[A es un subconjunto propio de B]]. (c) P(A) = {z : z ⊆ A}. ´ n I.5.5. Definicio (a) Si A ∩ B = ∅, diremos que A y B son disjuntos. (b) Diremos que A es una colecci´on de conjuntos disjuntos dos a dos (o una colecci´on disjunta) si para cualesquiera B, C ∈ A tales que B 6= C, entonces B ∩ C = ∅.

§6

Par ordenado. Axioma del Producto Cartesiano

´ n I.6.1. (Par ordenado). hx, yi = {{x}, {x, y}}. Definicio Teorema I.6.2. hx, yi = hz, ui

=⇒

x = z ∧ y = u.

´ n: Veamos primero que x = z. Demostracio hx, yi = hz, ui =⇒ {{x}, {x, y}} = {{z}, {z, u}} =⇒ {x} ∈ {{z}, {z, u}} =⇒ {x} = {z} ∨ {x} = {z, u} =⇒ z ∈ {x} =⇒ z = x. Para concluir la prueba del teorema probaremos primero el siguiente resultado. Aserto I.6.2.1. {x1 , x2 } = {x1 , x3 }

=⇒

x2 = x3 .

Prueba del aserto: Primero observemos que

Cap´ıtulo I.

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

15

x3 ∈ {x1 , x3 } =⇒ x3 ∈ {x1 , x2 } [[{x1 , x2 } = {x1 , x3 }]] =⇒ x3 = x1 ∨ x3 = x2 . Supongamos que x3 = x1 . Entonces x2 ∈ {x1 , x2 } =⇒ x2 ∈ {x1 , x3 } [[{x1 , x2 } = {x1 , x3 }]] =⇒ x2 ∈ {x3 } [[x1 = x3 ]] =⇒ x2 = x3 . Lo que prueba el aserto. Veamos ahora que y = u. ¾ x=z =⇒ hx, yi = hz, ui =⇒ =⇒ =⇒

2

hx, yi = hx, ui {{x}, {x, y}} = {{x}, {x, u}} {x, y} = {x, u} [[I.6.2.1]] y=u [[I.6.2.1]].

Lo que prueba el teorema.

¥

Lema I.6.3. [(Ax2, Ax5)] (a) ∀x ∀y, z ∈ x [{y, z} es un conjunto]. (b) ∀x ∀y, z ∈ x [hy, zi es un conjunto]. ´ n I.6.4. (Producto Cartesiano). Definicio A × B = {hx, yi : x ∈ A ∧ y ∈ B}. ´ n I.6.5. Ax2 ∧ Ax3 ∧ Ax4 ∧ Ax5 Proposicio

§7

=⇒

Ax6.

Relaciones y aplicaciones

´ n I.7.1. Definicio (a) x es un par ordenado ⇐⇒ ∃y ∃z (x = hy, zi). ( Π1 (x) = y ⇐⇒ ∀u [u ∈ y ↔ ∃v ∃w (x = hv, wi ∧ u ∈ v]. (b) Π2 (x) = y ⇐⇒ ∀u [u ∈ y ↔ ∃v ∃w (x = hw, vi ∧ u ∈ v]. ½ y, si ∃w (x = hy, wi); Observemos que: Π1 (x) = ∅, en cualquier otro caso. (c) R es una relaci´on ⇐⇒ ∀y (y ∈ R =⇒ y es un par ordenado). ½ dom(R) = {y : ∃z (hy, zi ∈ R)} (d) rang(R) = {z : ∃y (hy, zi ∈ R)} (e) R|A = {hz, ui ∈ R : z ∈ A ∧ u ∈ A} = R ∩ (A × A).

16

7. Relaciones y aplicaciones

(f ) R es una relaci´on sobre A ⇐⇒ (g) R−1 = {hy, xi : hx, yi ∈ R}.

R es una relaci´on ∧ dom(R), rang(R) ⊆ A.

´ n I.7.2. Proposicio (a) dom(R) y rang(R) son conjuntos. (b) R|A es un conjunto. ´ n I.7.3. Definicio (a) R es una relaci´on de equivalencia sobre A si: (a.1) R es una relaci´on sobre A, y   ∀y ∈ A (hy, yi ∈ R) ∀y, z ∈ A (hy, zi ∈ R =⇒ hz, yi ∈ R) (a.2)  ∀y, z, u ∈ A (hy, zi ∈ R ∧ hz, ui ∈ R =⇒ hy, ui ∈ R). (b) < es una relaci´on de orden parcial sobre A si: (b.1) < es una relaci´on sobre A, y ½ ∀y ∈ A (y 6< y) (b.2) ∀y, z, u ∈ A (y < z ∧ z < u =⇒ y < u) (c) < es una relaci´on de orden total sobre A si: (c.1) < es una relaci´on de orden parcial sobre A, y (c.2) ∀y, z ∈ A (y < z ∨ z < y ∨ y = z). (d) Sean < una relaci´on de orden parcial sobre A, B ⊆ A (B 6= ∅), y z ∈ A. Diremos que: (d.1) z es un elemento maximal de B si: z ∈ B ∧ ∀u ∈ B (z 6< u). (d.2) z es un elemento minimal de B si: z ∈ B ∧ ∀u ∈ B (u 6< z). (d.3) z es el mayor elemento de B si: z ∈ B ∧ ∀u ∈ B (u ≤ z). (d.4) z es el menor elemento de B si: z ∈ B ∧ ∀u ∈ B (z ≤ u). (d.5) z es una cota superior de B si: ∀u ∈ B (u ≤ z). (d.6) z es una cota inferior de B si: ∀u ∈ B (z ≤ u). (d.7) z es el supremo de B, z = sup(B), si: z es la menor cota superior de B. (d.8) z es el ´ınfimo de B, z = inf(B), si: z es la mayor cota inferior de B. ´ n I.7.4. Definicio (a) f es una aplicaci´on

½ ⇐⇒

f es una relaci´on ∧ ∀x ∀y ∀z (hx, yi ∈ f ∧ hx, zi ∈ f =⇒ y = z)

Si f es una aplicaci´on y hx, yi ∈ f , escribiremos f (x) = y. Usaremos indistintamente los t´erminos aplicaci´on y funci´on. (b) f|A = {hy, zi ∈ f : y ∈ A}. Observemos que f|A , considerando f como una aplicaci´on, no coincide con f|A ,

Cap´ıtulo I.

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

17

considerando f como una relaci´on. (c) f : A −→ B ⇐⇒ f aplicaci´on ∧ dom(f ) = A ∧ rang(f ) ⊆ B. Leeremos f : A −→ B como f es una aplicaci´on de A en B. (d) Si f : A −→ B y g : B −→ C, g ◦ f = {hu, vi : ∃w (hu, wi ∈ f ∧ hw, vi ∈ g)} (e) Sea f : A −→ B. (e.1) f es suprayectiva ⇐⇒ rang(f ) = B. (e.2) f es inyectiva ⇐⇒ ∀z, u ∈ A (f (z) = f (u) =⇒ z = u). (e.3) f es biyectiva ⇐⇒ f es suprayectiva e inyectiva. (f ) A B = {f : f es una aplicaci´on de A en B}. ½ f [C] = {y : ∃x (x ∈ C ∧ f (x) = y)}, (g) f −1 [C] = {x : f (x) ∈ C}. ´ n I.7.5. Proposicio (a) A B es un conjunto. (b) Sean f : A −→ B, C ⊆ A y D ⊆ B. Entonces f|C , , f [C] y f −1 [D] son conjuntos. (c) f : A −→ B ∧ g : B −→ C =⇒ g ◦ f : A −→ C. En particular, g ◦ f es un conjunto. Lema I.7.6. Sea f : A −→ B una aplicaci´on inyectiva. Entonces (a) f −1 es una aplicaci´on, y (b) dom(f −1 ) = rang(f ) y rang(f −1 ) = A.

§8

Funciones. Axioma de Reemplazamiento

´ n I.8.1. Definicio (a) Sea R una clase. Diremos que R es una relaci´on (binaria) si ∀x ∈ R (x es un par ordenado). (b) Sea F una relaci´on. Diremos que F es una funci´on si ∀x ∀y ∀z (hx, yi, hx, zi ∈ F =⇒ y = z). Notaremos (b.1) F(x) = y ⇐⇒ hx, yi ∈ F. (b.2) dom(F) = {x : ∃y (hx, yi ∈ F)}. (b.3) rang(F) = {y : ∃x (hx, yi ∈ F)}. (c) F : A −→ V ⇐⇒ F funci´on ∧ dom(F) = A. Lema I.8.2. Ax7

=⇒

Ax2.

18

8. Funciones. Axioma de Reemplazamiento

´ n: Sean C una clase y A un conjunto. Veamos que A∩C es un conjunto. Demostracio Sea F : C −→ V la funci´on: F(x) = x. Por el Axioma de Reemplazamiento F[A] = {F(x) : x ∈ A}. es un conjunto. Por tanto, {x ∈ A : x ∈ C} es un conjunto. Lo que prueba el resultado. Lema I.8.3. Ax5 ∧ Ax7

=⇒

¥

Ax3.

´ n: Por el Axioma de las Partes, Ax5, existe P(∅). Usando otra vez el Demostracio Axioma de las Partes, P(P(∅)) es un conjunto. Adem´as, P(P(∅)) = {∅, {∅}}. Sean a y b conjuntos. Consideremos la funci´on F definida por

½ F(x) =

a, b,

si x = ∅; en caso contrario.

Entonces F[P(P(∅))] = {a, b}. Por el Axioma de Reemplazamiento, Ax7, {a, b} es un conjunto. ¥ ´ n I.8.4. Ax3 ∧ Ax4 ∧ Ax7 Proposicio

=⇒

Ax6.

´ n I.8.5. Sea I un conjunto. Una familia de conjuntos sobre I, {Aj : j ∈ I}, Definicio es una aplicaci´on H tal que (a) dom(H) = I, y (b) para todo j ∈ I, H(j) = Aj . Puesto que {Aj : j ∈ I} = H[I], por el Axioma de Reemplazamiento, una familia de conjuntos sobre I es un conjunto. ´ n I.8.6. Sean C una clase y A un conjunto. Proposicio (a) Si existe F : A −→ C suprayectiva, entonces C es un conjunto. (b) Si existe F : C −→ A inyectiva, entonces C es un conjunto. ´ n: ((a)): Sea F : A −→ C suprayectiva. Entonces C = F[A]. Entonces, Demostracio por el Axioma de Reemplazamiento, C es un conjunto. ((b)): Sea D = F[C]. Puesto que D ⊆ A, D es un conjunto. Puesto que F es inyectiva, F−1 es una funci´on. Adem´as, F−1 [D] = C. Puesto que D es un conjunto, por el Axioma de Reemplazamiento, C es un conjunto. ¥

Cap´ıtulo I.

§9

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

19

Ejercicios

Ejercicio I.9.1. (I.4.1). Ax0 ∧ Ax1 =⇒ ∃!y ∀x (x ∈ / y). Ejercicio I.9.2. (I.5.3). [(Ax1), (Ax2)] (a) A 6= ∅ → ∃!y ∀z (z ∈ y ↔ ∀u (u ∈ A → z ∈ u)). (b) ∀x ∀y ∃!u ∀z (z ∈ u ↔ z ∈ x ∧ z ∈ / y). Ejercicio I.9.3. (I.5.3). T (a) Si A 6= ∅, entonces A es un conjunto. T (b) ∅ = V. Sin embargo, si entendemos que ∅ ⊆ P(A) (es T decir, si consideramos a ∅ como una familia de subconjuntos de A), definimos ∅ = A Ejercicio I.9.4. (I.6.3). [(Ax2, Ax4)] (a) ∀x ∀y, z ∈ x [{y, z} es un conjunto]. (b) ∀x ∀y, z ∈ x [hy, zi es un conjunto]. Ejercicio I.9.5. (I.6.5). Ax2 ∧ Ax3 ∧ Ax4 ∧ Ax5

=⇒

Ax6.

Ejercicio I.9.6. (I.7.2). (a) dom(x) y rang(x) son conjuntos. (b) x|y es un conjunto. Ejercicio I.9.7. (I.7.5). (a) A B es un conjunto. (b) Sean f : A −→ B, C ⊆ A y D ⊆ B. Entonces f|C , , f [C] y f −1 [D] son conjuntos. (c) f : A −→ B ∧ g : B −→ C =⇒ g ◦ f : A −→ C es un conjunto. Ejercicio I.9.8. (I.7.6). Si f : A −→ B es una aplicaci´on inyectiva, entonces (a) f −1 es una aplicaci´on, y (b) dom(f −1 ) = rang(f ) y rang(f −1 ) = A. Ejercicio I.9.9. (I.8.4). Ax3 ∧ Ax4 ∧ Ax7 Ejercicio I.9.10.

=⇒

Ax6.

20

(a) (b) (c) (d)

9. Ejercicios

Encontrar dos conjuntos A y B tales que A 6= B y S Para todo B ∈ A, B ⊆ A. S S A ⊆ B =⇒ A ⊆ B. S ∀C ∈ A (C ⊆ B) =⇒ A ⊆ B.

S

A=

S

B.

Ejercicio I.9.11. Definimos la diferencia sim´etrica de dos conjuntos como sigue A 4 B = (A − B) ∪ (B − A). Probar que (a) (b) (c) (d) (e) (f ) (g) (h) (i) (j) (k) (l) (m) (n) (˜ n)

A 4 B es un conjunto. A 4 B = B 4 A. A 4 (B 4 C) = (A 4 B) 4 C. A ∩ (B 4 C) = (A ∩ B) 4 (A ∩ C). A 4 B = C ⇐⇒ A 4 C = B. A 4 ∅ = A. A 4 A = ∅. A 4 B = C 4 B ⇐⇒ A = C. A 4 B = ∅ ⇐⇒ A = B. A 4 B = (A ∪ B) − (A ∩ B). (A ∪ C) 4 (B ∪ C) = (A 4 B) − C. A ∪ C = B ∪ C ⇐⇒ A 4 B ⊆ C. ∀A, B ∃!C (A 4 C = B). A, B disjuntos ⇐⇒ A ∪ B = A 4 B. A ∪ B = A 4 B 4 (A ∩ B).

Ejercicio I.9.12. Sean A y B conjuntos y F una funci´on. Probar que S S (a) F −1 [ A] = {F −1 [C] : C ∈ A}. T T (b) A 6= ∅ =⇒ F −1 [ A] = {F −1 [C] : C ∈ A}. (c) F −1 [A − B] = F −1 [A] − F −1 [B]. Ejercicio I.9.13. Sean A y B conjuntos. Probar que las siguientes clases son conjuntos. (a) (b) (c) (d) (e)

{R : R relaci´on sobre A}. {{{x}} : x ∈ A ∪ B}. {A ∪ C : C ∈ B}. {P(C) : C ∈ A}. {C ∪ D : C ∈ A, D ∈ B}.

En cada caso especificar los axiomas que se usan.

Cap´ıtulo I.

La Teor´ıa de Conjuntos de Zermelo–Fraenkel

21

Ejercicio I.9.14. Sea A un conjunto. Probar que: (a) {x : x ∈ / A} es una clase propia. (b) Si ∅ ∈ / A, {f : f funci´on de elecci´on sobre A} es un conjunto. ¿Qu´e sucede si ∅ ∈ A? (c) ¿Es {f : f aplicaci´on ∧ dom(f ) = A} una clase propia? (d) No existe ning´ un conjunto cuyos elementos sean los conjuntos que no pertenecen a alg´ un elemento de A. (e) No existe ning´ un conjunto cuyos elementos sean los conjuntos que no pertenecen a alg´ un elemento de un elemento de A. Ejercicio I.9.15. Sea f : A −→ B. (a) Sea g la aplicaci´on de dominio P(A) definida por: g(C) = f [C]. Probar que f inyectiva =⇒ g : P(A) −→ P(B) inyectiva (b) Sea g : B −→ P(A) definida por: g(c) = {x ∈ A : f (x) = c}. Probar que f suprayectiva =⇒ g inyectiva ¿Es cierto el rec´ıproco? Ejercicio I.9.16. (a) Demostrar que siguiente definici´on sirve para definir el concepto de par ordenado; es decir, hx, yi = hx0 , y 0 i ↔ x = x0 ∧ y = y 0 . hx, yi = {{{x}, ∅}, {{y}}} (b) Determinar cu´ales de las siguientes propuestas puede servir como definici´on de par ordenado. (b.1) hx, yi = {{x, ∅}, y}. (b.2) hx, yi = {{x, ∅}, {y, ∅}}. (b.3) hx, yi = {{x, ∅}, {y}}. Ejercicio I.9.17. Usando el axioma de regularidad, Ax9, probar que: ∀x (x ∈ / x).

22

9. Ejercicios

Cap´ıtulo II Buenos ´ ordenes. Ordinales §1

Clases bien ordenadas [ Z− ∗]

1.A

Introducci´ on

´ n II.1.1. Sean A una clase y < una relaci´on sobre A; es decir, < ⊆ A × A. Definicio Sean x, y ∈ A. Notaremos (–) x < y si hx, yi ∈