Carlos Ivorra Castillo

TEOR´IA DE CONJUNTOS

Un conjunto es un “muchos” que puede ser pensado como uno. Georg Cantor

´Indice General Introducci´ on

ix

Cap´ıtulo I: El lenguaje de la teor´ıa 1.1 Clases y conjuntos . . . . . . . 1.2 Funciones . . . . . . . . . . . . 1.3 Formaci´ on de conjuntos . . . . 1.4 La teor´ıa de conjuntos NBG∗ . 1.5 Relaciones . . . . . . . . . . . . 1.6 Leyes de composici´ on interna .

de . . . . . . . . . . . .

Cap´ıtulo II: Ordinales 2.1 La construcci´ on de los ordinales . 2.2 Inducci´ on y recursi´ on transfinita 2.3 Ordinales y buenos ´ordenes . . . 2.4 Funciones normales . . . . . . . . 2.5 La aritm´etica ordinal . . . . . . . 2.6 Sumas finitas . . . . . . . . . . . 2.7 La forma normal de Cantor . . .

. . . . . . .

conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

1 1 9 15 19 20 27

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

39 39 48 53 56 57 64 68

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

Cap´ıtulo III: La teor´ıa de conjuntos NBG 75 3.1 Relaciones bien fundadas . . . . . . . . . . . . . . . . . . . . . . 75 3.2 El axioma de regularidad . . . . . . . . . . . . . . . . . . . . . . 81 3.3 El axioma de elecci´ on . . . . . . . . . . . . . . . . . . . . . . . . 86 Cap´ıtulo IV: Cardinales 4.1 Equipotencia . . . . . . . . . . 4.2 N´ umeros cardinales . . . . . . . 4.3 La aritm´etica cardinal . . . . . 4.4 Conjuntos finitos . . . . . . . . 4.5 Sumas y productos infinitos . . 4.6 Cofinalidad . . . . . . . . . . . 4.7 Aplicaciones sobre el axioma de v

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . elecci´ on

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

97 97 100 107 115 119 124 129

´INDICE GENERAL

vi

Cap´ıtulo V: La exponenciaci´ on cardinal 135 5.1 La exponenciaci´ on en NBG . . . . . . . . . . . . . . . . . . . . . 135 5.2 La hip´ otesis de los cardinales singulares . . . . . . . . . . . . . . 141 5.3 Cardinales fuertemente inaccesibles . . . . . . . . . . . . . . . . . 146 Cap´ıtulo VI: Conjuntos cerrados no acotados y estacionarios 6.1 Conjuntos cerrados no acotados . . . . . . . . . . . . . . . . . 6.2 Conjuntos estacionarios . . . . . . . . . . . . . . . . . . . . . 6.3 Un teorema de Silver . . . . . . . . . . . . . . . . . . . . . . . 6.4 Cardinales de Mahlo . . . . . . . . . . . . . . . . . . . . . . . 6.5 Principios combinatorios . . . . . . . . . . . . . . . . . . . . . 6.6 Puntos fijos de funciones normales . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

153 153 159 163 167 170 184

Cap´ıtulo VII: El sistema num´ erico 7.1 Los n´ umeros enteros . . . . . . 7.2 Los n´ umeros racionales . . . . . 7.3 Cuerpos m´etricos completos . . 7.4 La construcci´ on de R . . . . . . 7.5 Conjuntos ordenados completos 7.6 Sumas infinitas . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

193 193 198 201 215 222 231

Cap´ıtulo VIII: Elementos de topolog´ıa 8.1 Espacios topol´ ogicos . . . . . . . . 8.2 Algunos conceptos topol´ ogicos. . . 8.3 Aplicaciones continuas . . . . . . . 8.4 Condiciones de numerabilidad . . . 8.5 Espacios compactos . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

237 238 249 256 263 270

´ Cap´ıtulo IX: Arboles 9.1 El problema de Suslin . . . . . 9.2 Conceptos b´ asicos sobre ´arboles ´ 9.3 Arboles de Aronszajn . . . . . ´ 9.4 Arboles de Suslin . . . . . . . . ´ 9.5 Arboles de Kurepa . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

279 279 283 287 291 301

´ Cap´ıtulo X: Algebras de Boole 10.1 Conceptos b´ asicos . . . . . ´ 10.2 Algebras completas . . . . . 10.3 Ideales y filtros . . . . . . . 10.4 Espacios de Stone . . . . . . 10.5 Aplicaciones a la topolog´ıa .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

305 305 310 328 333 337

Cap´ıtulo XI: Elementos de teor´ıa de modelos 11.1 Lenguajes y modelos . . . . . . . . . . . . . 11.2 Teor´ıas formales . . . . . . . . . . . . . . . 11.3 Submodelos, inmersiones . . . . . . . . . . . 11.4 Ultraproductos . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

347 347 355 368 375

. . . . .

. . . . .

. . . . . .

´INDICE GENERAL

vii

Bibliograf´ıa

383

´ Indice de Materias

384

Introducci´ on El prop´ osito de este libro es proporcionar una introducci´ on axiom´ atica rigurosa a la teor´ıa de conjuntos que no presuponga del lector ning´ un conocimiento t´ecnico de la l´ ogica matem´ atica m´ as all´ a de una cierta familiaridad con las t´ecnicas de razonamiento informal-formalizable que emplean habitualmente los matem´ aticos. Naturalmente, una fundamentaci´ on s´ olida de la teor´ıa de conjuntos presupone la l´ ogica formal, y a este respecto podemos decir que “oficialmente” este libro debe considerarse como la continuaci´ on de mi libro de L´ ogica matem´ atica (LM), en el que, entre otras cosas, se discuten con todo el detalle y los tecnicismos necesarios diversas teor´ıas axiom´ aticas de conjuntos, entre ellas la de Zermelo-Fraenkel (ZFC) y la de von Neumann-Bernays-G¨ odel (NBG). Sin embargo, aqu´ı hemos optado por exponer la teor´ıa axiom´ atica de modo que no ha sido necesario hacer ninguna referencia expl´ıcita a LM, de tal forma que quien lea LM y contin´ ue con este libro, no s´ olo no encontrar´ a ninguna laguna entre ambos, sino que de hecho hallar´ a varios solapamientos, los que hemos considerado necesarios para que el lector familiarizado con el razonamiento matem´ atico pueda suplir con dicha familiaridad los requisitos t´ecnicos que proporciona LM. De este modo, LM y el presente libro suponen dos propuestas alternativas para introducirse en la teor´ıa de conjuntos: o bien empezando por los fundamentos l´ ogicos de LM para despu´es adentrarse en los contenidos matem´ aticos de las teor´ıas de conjuntos all´ı presentadas, o bien empezar por una introducci´ on axiom´ atica a la teor´ıa de conjuntos apoyada en la familiaridad del lector con el razonamiento matem´ atico para despu´es (opcionalmente) profundizar en sus aspectos l´ ogicos a trav´es de LM. Puesto que la distinci´ on entre conjuntos y clases propias resulta inevitable, para eliminar por completo las dificultades conceptuales que conlleva (que se discuten con detalle en LM) hemos optado por partir de la teor´ıa axiom´ atica de von Neumann-Bernays-G¨ odel NBG en lugar de la m´ as habitual, que es ZFC, puesto que as´ı el concepto de clase propia es un concepto formal m´ as que no deber´ıa presentar ninguna dificultad especial al lector, en lugar de un concepto metamatem´ atico que tiene que entenderse necesariamente en t´erminos de conceptos l´ ogicos. No obstante, ambas teor´ıas son equivalentes, y el lector familiarizado con LM se dar´ a cuenta de que, pasado el cap´ıtulo I (en el que exponemos la axiom´ atica de NBG), las siglas NBG pueden ser trivial y sistem´ aticamente sustituidas por ZFC sin necesidad de modificar absolutamente nada de lo dicho. ix

x

Introducci´ on

Los cap´ıtulos siguientes, desde el II hasta el V exponen los resultados fundamentales de la teor´ıa de conjuntos cantoriana (principalmente la teor´ıa de ordinales y de cardinales), sin perjuicio de que se presenten muchos resultados muy posteriores en el tiempo a la ´epoca de Cantor. El cap´ıtulo VI, aunque es una prolongaci´ on natural del precedente, es bastante m´ as avanzado y puede leerse tras los cap´ıtulos VII y VIII. El primero de ´estos est´ a dedicado a la construcci´ on del sistema num´erico, y termina de justificar as´ı que la teor´ıa axiom´ atica presentada es suficiente para desarrollar a partir de ella todas las ramas de la matem´ atica (´ algebra, an´ alisis, geometr´ıa, topolog´ıa, etc.) Precisamente en el cap´ıtulo 8 introducimos los elementos b´ asicos de la topolog´ıa conjuntista como requisito para la exposici´ on de aspectos m´ as avanzados de la teor´ıa de conjuntos, entre los que se cuentan varios apartados del cap´ıtulo previo VI (los relativos a principios combinatorios, cardinales inaccesibles, etc.) as´ı como los cap´ıtulos posteriores sobre ´arboles y ´algebras de Boole. El l´ımite principal que nos hemos impuesto al elegir los contenidos ha sido evitar todos aquellos que requieren considerar modelos de la teor´ıa de conjuntos (con todos los aspectos sobre l´ ogica y metamatem´ atica que ello requerir´ıa). No obstante, en el u ´ltimo cap´ıtulo presentamos los resultados b´ asicos de la teor´ıa de modelos, pero sin entrar, seg´ un acabamos de decir, en el estudio de modelos de la propia teor´ıa de conjuntos, evitando as´ı la necesidad de introducir distinciones sutiles entre f´ ormulas metamatem´ aticas y f´ ormulas definidas en la teor´ıa axiom´ atica. La mayor parte de los dos u ´ltimos cap´ıtulos puede verse como los preliminares necesarios (junto con LA) para abordar temas m´ as avanzados de la teor´ıa de conjuntos, principalmente los relativos a pruebas de consistencia, cardinales grandes, etc. Los u ´nicos resultados que se enuncian sin demostraci´ on en este libro son los que afirman la consistencia y la independencia de algunas de las afirmaciones consideradas (como la hip´ otesis del continuo, la existencia de cardinales inaccesibles, etc.) En algunos casos se esbozan sin rigor los argumentos que permiten concluir que determinados hechos no pueden ser demostrados en NBG (o, equivalentemente, en ZFC). Naturalmente, estas observaciones no demostradas no se usan en ning´ un momento, salvo para relacionar unas con otras.

Cap´ıtulo I

El lenguaje de la teor´ıa de conjuntos En este primer cap´ıtulo desarrollaremos el lenguaje necesario para hablar con precisi´ on de conjuntos, de modo que hablaremos de conjuntos en general sin hablar de ning´ un conjunto en particular. En el cap´ıtulo siguiente usaremos los conceptos introducidos aqu´ı para construir (es decir, describir) conjuntos concretos (como los n´ umeros naturales) que empezar´ an a perfilar el objeto de estudio de la teor´ıa.

1.1

Clases y conjuntos

El concepto matem´ atico de “conjunto” pretende precisar el concepto informal de “colecci´ on de objetos”, sin embargo hay razones profundas que har´ıan ingenuo pensar que un conjunto (en el sentido t´ecnico que vamos a dar a la palabra) es exactamente lo mismo que una “colecci´ on de objetos”. Ciertamente, podemos pensar tranquilamente que todo conjunto es una colecci´ on de objetos sin que ello nos lleve a ninguna contradicci´ on (que se sepa), pero pensar que cualquier colecci´ on de objetos puede identificarse con un conjunto s´ı que lleva inevitablemente a contradicciones. M´ as concretamente: al tratar de precisar el concepto informal de conjunto nos aparecen inevitablemente colecciones de objetos (muchas de las cuales tienen inter´es matem´ atico) que no pueden considerarse conjuntos sin caer en contradicciones. Por este motivo vamos a partir de un concepto m´ as general que el de “conjunto”, al que llamaremos “clase”. Las clases tambi´en ser´ an colecciones de objetos, y seguir´ a siendo cierto que si intent´ aramos identificar cualquier colecci´ on de objetos con una clase caer´ıamos inevitablemente en contradicciones, pero definiremos los conjuntos como un tipo particular de clases de modo que todas las colecciones de conjuntos que necesitaremos considerar, o bien ser´ an conjuntos, o bien ser´ an clases, y as´ı habremos obtenido un marco conveniente para desarrollar la teor´ıa de conjuntos. 1

2

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

As´ı pues, decimos que las clases de las que vamos a hablar ser´ an (o podr´ an ser consideradas como) colecciones de objetos. Quiz´ a el lector espere ahora que, en aras del rigor matem´ atico, explicitemos qu´e colecciones de objetos vamos a considerar exactamente como clases y cu´ ales van a ser exactamente los objetos que podr´ an aparecer en las colecciones llamadas clases, pero no vamos a hacer nada parecido a esto. Por el contrario vamos a limitarnos a afirmar que las clases son simplemente los objetos de los que vamos a hablar (sin especificar cu´ ales son), y que dadas dos clases A y B, entre ellas puede darse o no la relaci´ on de pertenencia, que representaremos por A ∈ B cuando se d´e y por A ∈ / B cuando no se d´e. En el primer caso diremos que la clase A pertenece a (o es un elemento de) la clase B, y en el segundo caso diremos que A no pertenece a B o que no es un elemento de B. Es en este sentido en el que podemos pensar que una clase B es la colecci´ on de todas las clases A que cumplen A ∈ B, pero ni vamos a definir qu´e es exactamente una clase, ni en qu´e consiste exactamente que una clase pertenezca o no a otra. La parte positiva es que prometemos no hacer esto nunca m´ as, de modo que desde aqu´ı nos obligamos a que cualquier otro concepto que introduzcamos en adelante sea definido con total precisi´ on a partir de los conceptos de “clase” y “pertenencia”. Un l´ ogico dir´ a que los conceptos de “clase” y “pertenencia” son los conceptos primitivos (o conceptos no definidos) de la teor´ıa de conjuntos. La forma de hablar con total rigor de unos conceptos no definidos es a trav´es de axiomas. Vamos a postular que las clases y la pertenencia de las que nos proponemos hablar (sean lo que sean) satisfacen unos axiomas y, del mismo modo que nos hemos comprometido a no introducir nuevos conceptos sin definirlos con todo rigor a partir de los conceptos primitivos de clase y conjunto (o, m´ as en general, de otros conceptos previamente definidos) nos comprometemos tambi´en a no afirmar nada sobre las clases y la pertenencia (o sobre los conceptos que introduzcamos en adelante) que no pueda ser demostrado l´ ogicamente con todo rigor a partir de los axiomas establecidos. Para ilustrar estos prop´ ositos empezamos dando la definici´ on de conjunto: Definici´ on 1.1 Diremos que una clase es un conjunto si pertenece al menos a otra clase, es decir: W cto A ≡ B A ∈ B.

Notemos que en la formalizaci´ on de esta definici´ on hemos escrito “existe un B tal que A pertenece a B”. No necesitamos especificar de ninguna forma que B es una clase, pues todos los objetos de los que vamos a hablar son clases. El primer axioma que adoptamos es el siguiente: Axioma de Extensionalidad Si dos clases tienen los mismos elementos, entonces son iguales, es decir, V V AB( x(x ∈ A ↔ x ∈ B) → A = B).

1.1. Clases y conjuntos

3

Es el axioma de extensionalidad el que nos legitima a pensar en las clases como colecciones de elementos (de clases, concretamente), pues si dos clases tienen los mismos elementos (es decir, si todo elemento de una lo es de la otra y viceversa, como dice la hip´ otesis del axioma) entonces ambas determinan la misma colecci´ on de objetos, y lo que dice el axioma es que si dos clases determinan la misma colecci´ on de objetos, entonces son una misma clase. En otros t´erminos: una clase no es ni m´ as ni menos que la colecci´ on de clases que determina mediante la relaci´ on de pertenencia. Veamos una segunda definici´ on: Definici´ on 1.2 Diremos que una clase A es una subclase de una clase B (o un subconjunto, si es que A es un conjunto) si todo elemento de A es tambi´en un elemento de B, es decir, V A ⊂ B ≡ x(x ∈ A → x ∈ B).

Observemos que A ⊂ B se cumple en particular si A = B. Cuando queramos indicar que A es una subclase de B distinta de la propia B escribiremos A √ B ≡ A ⊂ B ∧ A 6= B. Veamos ahora un ejemplo elemental de teorema: Teorema 1.3 Se cumple: V a) A A ⊂ A, V b) AB(A ⊂ B ∧ B ⊂ A → A = B), V c) ABC(A ⊂ B ∧ B ⊂ C → A ⊂ C).

´ n: Observemos que los teoremas a) y c) no requieren el Demostracio axioma de extensionalidad, es decir, son teoremas l´ ogicos que se deducen de las definiciones sin necesidad de ninguna hip´ otesis espec´ıfica sobre las clases. Por ejemplo, para demostrar c) suponemos A ⊂ B ∧ B ⊂ C y, para probar A ⊂ C tomamos una clase x ∈ A, de modo que, como A ⊂ B, podemos afirmar que x ∈ B y, como B ⊂ C, podemos afirmar que x ∈ C. Esto prueba que x ∈ A → x ∈ C y, como esto vale para toda clase x, concluimos que A ⊂ C. En cambio, el teorema b) requiere el axioma de extensionalidad (y de hecho es equivalente a ´el). Si suponemos que A ⊂ B ∧ B ⊂ A, entonces tenemos que todo x ∈ A cumple x ∈ B, y viceversa, es decir, que x ∈ A ↔ x ∈ B, luego por el axioma de extensionalidad A = B. Lo importante que el lector debe extraer de este resultado, m´ as all´ a de la trivialidad de lo que afirma en s´ı mismo, es que en ´el se pone de manifiesto c´ omo es posible razonar de forma totalmente rigurosa con unos objetos (las clases) y una propiedad (la pertenencia) que nunca hemos definido de ninguna forma, pero no importa lo que sean las clases y la pertenencia que, mientras

4

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

cumplan el axioma de extensionalidad, tendr´ an que cumplir necesariamente el teorema anterior. Toda demostraci´ on matem´ atica, por sofisticada que sea, es de la misma naturaleza, con la u ´nica diferencia de que puede apoyarse en algunos axiomas m´ as que vamos a ir introduciendo paulatinamente. El segundo axioma es el m´ as delicado desde un punto de vista t´ecnico: Axioma de comprensi´ on Si φ(x) es cualquier propiedad normal, existe una clase cuyos elementos son exactamente los conjuntos x que tienen la propiedad φ(x), es decir, W V A x(x ∈ A ↔ cto x ∧ φ(x)).

Naturalmente, aqu´ı debemos especificar qu´e queremos decir por “propiedad normal”. Ante todo, cuando decimos que φ(x) es una propiedad queremos decir, m´ as concretamente, que es una propiedad definible exclusivamente a partir de los conceptos de clase y pertenencia mediante los conectores l´ ogicos (“y”, “o”, “si y s´ olo si”, etc.) y los cuantificadores (“para todo” y “existe”) (o de otros conceptos definidos previamente en estas condiciones), entendiendo que pueden aparecer m´ as variables adem´ as de la x. Enseguida veremos ejemplos. Que la propiedad sea normal significa que los cuantificadores s´ olo recorren conjuntos, es decir, que en la definici´ on de φ(x) no se dice nunca “para toda clase A” o “existe una clase A”, sino a lo sumo “para todo conjunto A” o “existe un conjunto A”. Antes de discutir m´ as a fondo las sutilezas de este axioma, vamos a poner sobre el papel ejemplos concretos, pero primero observemos que el axioma de comprensi´ on puede ser mejorado: Teorema 1.4 En las condiciones del axioma de comprensi´ on, se cumple 1 W V A x(x ∈ A ↔ cto x ∧ φ(x)).

´ n: Se trata de probar que existe una u Demostracio ´nica clase A cuyos elementos son los conjuntos que cumplen φ(x). La existencia de tal clase la proporciona el axioma de comprensi´ on. Para probar que es u ´nica suponemos que una clase B cumple lo mismo, es decir, V V x(x ∈ A ↔ cto x ∧ φ(x)) ∧ x(x ∈ B ↔ cto x ∧ φ(x)). Es claro que de aqu´ı se deduce que V x(x ∈ A ↔ x ∈ B),

y el axioma de extensionalidad nos da entonces que A = B, es decir, s´ olo puede haber una clase que cumpla la propiedad considerada. Cuando hay una u ´nica clase que cumple una propiedad, la l´ ogica nos permite introducir un nombre para ella. En este caso: V Definici´ on 1.5 {x | φ(x)} ≡ A| x(x ∈ A ↔ cto x ∧ φ(x)), es decir, llamamos {x | φ(x)} a la u ´nica clase cuyos elementos son los conjuntos x que cumplen φ(x).

1.1. Clases y conjuntos

5

Por ejemplo, ahora podemos definir la uni´ on, la intersecci´ on, el complemento y la diferencia de clases como A ∪ B ≡ {x | x ∈ A ∨ x ∈ B}, A ≡ {x | x ∈ / A},

respectivamente.

A ∩ B ≡ {x | x ∈ A ∧ x ∈ B},

A \ B ≡ {x | x ∈ A ∧ x ∈ / B},

Tenemos as´ı cuatro ejemplos de aplicaci´ on del axioma de comprensi´ on. En la definici´ on de la uni´ on estamos tomando φ(x) ≡ x ∈ A ∨ x ∈ B, que es una propiedad definida exclusivamente en t´erminos de la pertenencia y un signo l´ ogico (la disyunci´ on), en la que, adem´ as de la variable x, figuran las variables auxiliares A y B. Como no aparecen cuantificadores, la propiedad es normal y el axioma es aplicable. Lo mismo vale para los otros tres ejemplos. Definimos ahora dos ejemplos concretos de clases, la clase universal y la clase vac´ıa: V ≡ {x | x = x}, ∅ ≡ {x | x 6= x}.

un conjunto es distinto de s´ı mismo, tenemos que V Obviamente, como ning´ xx∈ / ∅. M´ as a´ un, la clase vac´ıa es la u ´nica clase con esta propiedad, es decir: V V A( x x ∈ / A → A = ∅). Esto es una consecuencia del axioma de extensionalidad, pues si una clase A no tiene elementos, entonces tiene los mismos elementos que la clase vac´ıa (ninguno), luego ambas clases son la misma.

Respecto de la clase universal, es muy importante tener presente que, aunque toda clase A cumple A = A, eso no significa que toda clase A cumpla A ∈ V . Recordemos que, en general, los elementos de una clase {x | φ(x)} no son todas las clases que cumplen φ(x), sino todos los conjuntos que cumplen φ(x). Para pertenecer a {x | φ(x)} no basta con cumplir la propiedad φ(x), sino que se requiere adem´ as ser un conjunto. En nuestro caso, la clase universal est´ a formada por todos los conjuntos que cumplen x = x, es decir, se trata de “la clase de todos los conjuntos” (pero no de la clase de todas las clases). As´ı pues: V x(x ∈ V ↔ cto x). Observemos que ∅ y V son, respectivamente, la menor y la mayor de todas las clases, en el sentido de que V A(∅ ⊂ A ∧ A ⊂ V ).

En efecto, como los elementos de cualquier clase A son conjuntos, todos ellos son tambi´en elementos de V , luego tenemos la inclusi´ on A ⊂ V . Por otra parte, la clase vac´ıa est´ a contenida en cualquier otra clase, porque la implicaci´ on x ∈ ∅ → x ∈ A se cumple trivialmente (no es posible encontrar un conjunto x que cumpla x ∈ ∅ ∧ x ∈ / A). Diremos que dos clases A y B son disjuntas si A ∩ B = ∅, es decir, si no tienen elementos en com´ un.

6

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

Nota Los conceptos que acabamos de introducir verifican una serie de propiedades que se demuestran todas de forma elemental. Por ejemplo, se cumple que V ABC(A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)).

Para probar este tipo de igualdades basta recurrir al axioma de extensionalidad: tomamos un conjunto x ∈ A ∩ (B ∪ C) y probamos que pertenece tambi´en al otro miembro. En efecto, por definici´ on de intersecci´ on x ∈ A y x ∈ B ∪ C, y por definici´ on de uni´ on, o bien x ∈ B (en cuyo caso x ∈ A ∩ B) o bien x ∈ C (en cuyo caso x ∈ A ∩ C), luego en cualquiera de los dos casos x ∈ (A ∩ B) ∪ (A ∩ C). Esto prueba la implicaci´ on x ∈ A ∩ (B ∪ C) → x ∈ (A ∩ B) ∪ (A ∩ C), y la implicaci´ on opuesta se demuestra de forma similar. Entonces el axioma de extensionalidad nos da la igualdad. Alternativamente, podemos considerar que hemos probado la inclusi´ on A ∩ (B ∪ C) ⊂ (A ∩ B) ∪ (A ∩ C), y que la implicaci´ on contraria prueba la inclusi´ on contraria: (A ∩ B) ∪ (A ∩ C) ⊂ A ∩ (B ∪ C), y entonces concluimos mediante 1.3 b). En general una forma de probar una igualdad entre dos clases X = Y es probar la doble inclusi´ on X ⊂ Y ∧ Y ⊂ X y aplicar 1.3 b). A partir de los axiomas de extensionalidad y comprensi´ on no es posible probar que V 6= ∅, es decir, no es posible probar que existan conjuntos. Por ello introducimos ahora un axioma que postula la existencia de un conjunto: Axioma del conjunto vac´ıo cto ∅. As´ı pues, a partir de aqu´ı podemos hablar del “conjunto vac´ıo” en lugar de la “clase vac´ıa”. En particular, ahora podemos afirmar que ∅ ∈ V , luego V 6= ∅. Podemos definir unos conceptos m´ as generales de uni´ on e intersecci´ on: W V S T A ≡ {x | y ∈ A x ∈ y}, A ≡ {x | y ∈ A x ∈ y}. W Observemos que aqu´ı usamos la notaci´ on y ∈ A φ(y) como abreviatura W de y(y ∈ A ∧ x ∈ y), es decir, “existe una clase y en A tal que φ(y)”. Ahora bien, la condici´ on y ∈ A supone impl´ıcitamente que y es un conjunto (pues estamos diciendo que pertenece a otra clase), luego esto es equivalente a W y(cto y ∧ y ∈ A ∧ φ(y)). V V Similarmente, y ∈ V A φ(y) es una abreviatura por y(y ∈ A → φ(y)), que a su vez es W equivalenteVa y(cto y ∧ y ∈ A → φ(y)), luego las cuantificaciones de la forma y ∈ A o y ∈ A son cuantificaciones sobre conjuntos y determinan propiedades normales (supuesto que lo que vaya a continuaci´ on sea normal).

1.1. Clases y conjuntos

7

Estas consideraciones generales justifican en particular que la existencia de “gran uni´ on” y la “gran intersecci´ on” se S sigue de dos aplicaciones leg´ıtimas del axioma de comprensi´ on. Claramente, A resulta de reunir en una ´nica clase T u todos los elementos de todos los elementos de A, mientras que A contiene a los elementos comunes a todos los elementos de A. Observemos que S S T T ∅ = ∅, V = V, ∅ = V, V = ∅.

En efecto, vamos a probar las dos u ´ltimas igualdades: V Si x ∈ V , entonces trivialmente y ∈ ∅ x ∈ y, pues no T es posible encontrar un y ∈ ∅ que no T cumpla x ∈ y, y esto significa que x ∈ ∅, luego tenemos la inclusi´ on V ⊂ ∅, y ya hemos visto que la inclusi´ on contraria se cumple siempre. Para ´ltima igualdad requerimos el axioma del conjunto vac´ıo. En efecto, T la u si x ∈ V , entonces x pertenece aT todos los elementos de V , en particular x ∈ ∅, lo cual es imposible. Por lo tanto V no tiene elementos y es el conjunto vac´ıo. Veamos ahora un ejemplo que muestra la necesidad de distinguir entre clases y conjuntos. Definimos la clase de Russell como R ≡ {x | x ∈ / x}, es decir, se trata de la clase de todos los conjuntos que no se pertenecen a s´ı mismos. La propiedad x ∈ / x es normal (trivialmente, porque no tiene cuantificadores) luego el axioma de comprensi´ on justifica la existencia de R. Si no distingui´eramos entre clases y conjuntos, y pretendi´eramos haber definido “el conjunto de todos los conjuntos que no se pertenecen a s´ı mismos” tendr´ıamos una contradicci´ on, pues cabr´ıa plantearse si el “conjunto” R se pertenece o no a s´ı mismo, y las dos opciones resultan contradictorias: si R ∈ R entonces R deber´ıa ser uno de los “conjuntos que no se pertenecen a s´ı mismos”, y concluir´ıamos que R ∈ / R, en contra de lo supuesto. Si, por el contrario, suponemos que R ∈ / R, entonces R ser´ıa un “conjunto que no se pertenece a s´ı mismo” y deber´ıamos concluir que R ∈ R, en contradicci´ on con lo supuesto. Esta paradoja se conoce como la “paradoja de Russell”, y no afecta a la teor´ıa de conjuntos en los t´erminos que la estamos presentando, pues en nuestro contexto se reduce al teorema siguiente: Teorema 1.6 ¬ cto R. ´ n: Observemos que R ∈ Demostracio / R, pues si se cumpliera R ∈ R por definici´ on de R resultar´ıa que R ∈ / R y tendr´ıamos una contradicci´ on. Si R fuera un conjunto, entonces tendr´ıamos cto R ∧ R ∈ / R, es decir, R ser´ıa un conjunto que no se pertenece a s´ı mismo, y esto implicar´ıa R ∈ R, con lo que tendr´ıamos una contradicci´ on. As´ı pues, R no puede ser un conjunto. Las clases que no son conjuntos se llaman clases propias. Acabamos de probar que la clase de Russell es una clase propia, y que adem´ as cumple R ∈ / R.

8

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

Si no fuera por la distinci´ on entre clases y conjuntos, que hace que R ∈ / R no obligue necesariamente a que R ∈ R, tendr´ıamos una contradicci´ on.

Notemos que, como ∅ es un conjunto que no se pertenece a s´ı mismo, se cumple que ∅ ∈ R, luego R 6= ∅. Ahora es claro tambi´en que la noci´ on de clase no puede identificarse con la de “colecci´ on de objetos”, pues, admitiendo que existan clases que cumplen los axiomas que estamos suponiendo, tenemos que ∅ y R son dos clases que forman una “colecci´ on de dos clases”, pero tal colecci´ on no se corresponde con ninguna clase, en el sentido de que no existe ninguna clase cuyos elementos sean exactamente ∅ y R, pues para que ello fuera posible R deber´ıa ser un conjunto y no lo es. As´ı pues, siempre podemos pensar en colecciones de objetos (de clases, concretamente) que van m´ as all´ a de las colecciones que podemos expresar mediante clases. Nuestro prop´ osito es demostrar (adoptando para ello los axiomas adecuados) que todas las colecciones que realmente son necesarias para desarrollar las matem´ aticas (y esto no incluye a la colecci´ on formada por ∅ y R, de la que podemos hablar, pero tampoco pasa nada si no la tenemos en cuenta) son en su mayor parte conjuntos y, en algunos pocos casos, clases propias, pero clases al fin y al cabo. Nota El lector se habr´ a preguntado sin duda por qu´e hemos impuesto la condici´ on de normalidad en el axioma de comprensi´ on o, equivalentemente, qu´e problema habr´ıa en admitir que cualquier propiedad, normal o no, define una clase. La respuesta es que no habr´ıa ning´ un problema. La teor´ıa axiom´ atica de conjuntos que resulta de aceptar los axiomas que hemos introducido hasta ahora y los que introduciremos en lo sucesivo se conoce como teor´ıa de conjuntos de von Neumann-Bernays-G¨ odel, (NBG), mientras que si eliminamos la restricci´ on de normalidad en el axioma de comprensi´ on tenemos la teor´ıa de conjuntos de Morse-Kelley (MK). La diferencia entre ambas es que en NBG la noci´ on de clase propia es eliminable, es decir, toda la teor´ıa puede ser reformulada para eliminar por completo el concepto de clase propia y trabajar exclusivamente con conjuntos. El resultado es la llamada teor´ıa de conjuntos de Zermelo-Fraenkel (ZF) que es totalmente equivalente a NBG en el sentido de que un teorema que involucre exclusivamente conjuntos es demostrable en NBG si y s´ olo si es demostrable en ZF. Las clases como R, que en NBG se demuestra que son clases propias, simplemente no existen en ZF, es decir, en ZF, en lugar de “la clase de los conjuntos que no se pertenecen a s´ı mismos no es un conjunto”, se demuestra “no existe ning´ un conjunto cuyos elementos sean los conjuntos que no se pertenecen a s´ı mismos”. Por el contrario, en MK las clases propias pueden usarse para demostrar resultados sobre conjuntos (incluso afirmaciones que hablan exclusivamente de n´ umeros naturales) que no son demostrables en NBG ni, por consiguiente, en ZF. En realidad, al restringirnos a NBG, es decir, al aceptar la restricci´ on del axioma de comprensi´ on a propiedades normales, no es que estemos restringi´endonos a NBG, sino m´ as bien estamos observando que todos los resultados que vamos a probar no requieren m´ as que la forma restringida del axioma de com-

1.2. Funciones

9

prensi´ on. En ning´ un momento nos vamos a encontrar con resultado que “nos gustar´ıa” poder demostrar pero no podemos por culpa de la restricci´ on del axioma de comprensi´ on. Para encontrar resultados as´ı (que los hay) es necesario ahondar mucho en las sutilezas l´ ogicas de la teor´ıa de conjuntos, cosa que no vamos a hacer en este libro.

1.2

Funciones

Ahora vamos a enriquecer sustancialmente el lenguaje de la teor´ıa de conjuntos mostrando que a partir de las meras nociones de clase y pertenencia es posible definir funciones que hagan corresponder unos conjuntos con otros. La clave para ello es el concepto de par ordenado, que a su vez requiere definir previamente el concepto de par desordenado: Definici´ on 1.7 Dadas dos clases x e y, definimos el par (desordenado) formado por ellas como {x, y} ≡ {z | z = x ∨ z = y}. Definimos tambi´en {x} ≡ {x, x} = {z | z = x}. De este modo, {x, y} es la clase de todos los conjuntos que son iguales a x o a y. Esto hay que tomarlo con precauci´ on si x o y no son conjuntos. Por ejemplo, {∅, R} = {∅} y {R} = ∅. Con los axiomas que hemos presentado hasta ahora no es posible demostrar que exista ning´ un otro conjunto, aparte de ∅. Esto cambia dr´ asticamente si a˜ nadimos el axioma siguiente: Axioma del par

V xy (cto x ∧ cto y → cto{x, y}).

En otras palabras, el axioma del par afirma que el par definido por dos conjuntos es un conjunto. El axioma incluye el caso en que x = y, en cuyo caso tenemos: V x(cto x → cto{x}). Ahora podemos probar la existencia de muchos conjuntos, como ∅, {∅}, {∅, {∅}}, {{∅}}, etc.

M´ as en general, cuando escribamos expresiones de la forma {a, b, c, d}, habr´ a que entender que nos referimos a la clase {a, b, c, d} ≡ {x | x = a ∨ x = b ∨ x = c ∨ x = d}. Se dice entonces que hemos definido la clase A = {a, b, c, d} por extensi´ on, es decir, especificando sus elementos uno a uno, mientras que las clases definidas especificando una propiedad que deben cumplir sus elementos est´ an definidas por comprensi´ on. Obviamente, s´ olo es posible definir por extensi´ on clases con un n´ umero finito de elementos. Los axiomas vistos hasta el momento no nos

10

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

permiten asegurar que la clase {a, b, c, d} sea un conjunto aunque lo sean sus elementos. Observemos ahora que si x, y son conjuntos, se cumple que {x, y} = {y, x}, pues ambos conjuntos tienen los mismos elementos. Un hecho fundamental es que podemos definir un nuevo concepto de par en el que el orden de sus elementos sea relevante: Definici´ on 1.8 Definimos el par ordenado de componentes los conjuntos x e y como el conjunto (x, y) ≡ {{x}, {x, y}}. Observemos que si x e y son conjuntos, entonces {x} y {x, y} son conjuntos por el axioma del par, y entonces (x, y) es un conjunto por una nueva aplicaci´ on de este axioma. La definici´ on est´ a pensada para que se cumpla el teorema fundamental: Teorema 1.9 Si x, y, u, v son conjuntos, entonces (x, y) = (u, v) ↔ x = u ∧ y = v. ´ n: Una implicaci´ Demostracio on es trivial. Para probar la contraria suponemos que (x, y) = (u, v). Entonces, como {x} ∈ (x, y), tenemos tambi´en que {x} ∈ (u, v), luego {x} = {u} o bien {x} = {u, v}. Si se da el segundo caso, como u ∈ {u, v} = {x}, concluimos que u = x, y en el primer caso llegamos tambi´en a la misma conclusi´ on. Ahora distinguimos otros dos casos: si x = y, entonces (x, y) = {{x}, {x, x}} = {{x}}, y como {u, v} ∈ (u, v) = (x, y), ser´ a {u, v} = {x}, luego v ∈ {u, v} = {x}, luego v = x = y. Si, por el contrario, x 6= y, no puede ser {x, y} = {u}, pues entonces ser´ıa x = u = y, y como {x, y} ∈ (x, y) = (u, v), tiene que ser y ∈ {x, y} = {u, v}, luego y = u ∨ y = v, pero no puede ser y = u = x, luego tiene que ser y = v. Usaremos la notaci´ on {(x, y) | φ(x, y)} ≡ {z |

W xy(cto x ∧ cto y ∧ z = (x, y) ∧ φ(x, y))},

es decir, para referirnos a la clase de todos los pares ordenados (x, y) cuyas componentes cumplen la propiedad (normal) φ(x, y). Observemos que la propiedad W xy(cto x ∧ cto y ∧ z = (x, y) ∧ φ(x, y)) es normal si φ lo es, pues los dos cuantificadores que se a˜ naden a lo que afirma φ est´ an restringidos a conjuntos, por lo que si φ es normal el axioma de comprensi´ on asegura la existencia de la clase {(x, y) | φ(x, y)}. El ejemplo m´ as simple de clase definida de este modo es el producto cartesiano:

1.2. Funciones

11

Definici´ on 1.10 El producto cartesiano de dos clases A y B se define como A × B ≡ {(x, y) | x ∈ A ∧ y ∈ B}. En otros t´erminos: A × B es la clase formada por todos los pares ordenados cuya primera componente est´ a en A y su segunda componente est´ a en B. Por ejemplo, V × V es la clase de todos los pares ordenados. Definici´ on 1.11 Definimos el dominio y el rango de una clase F como las clases1 W W DF ≡ {x | y (cto y ∧ (x, y) ∈ F }, RF ≡ {y | x (cto x ∧ (x, y) ∈ F } Diremos que F es un´ıvoca si cumple V Un F ≡ xyz(cto x ∧ cto y ∧ cto z ∧ (x, y) ∈ F ∧ (x, z) ∈ F → y = z).

Notemos que en la definici´ on de clase un´ıvoca no hemos exigido que todos los elementos de F sean pares ordenados. Diremos que una clase F es una funci´ on si cumple V W Fn F ≡ z ∈ F xy(cto x ∧ cto y ∧ z = (x, y)) ∧ Un F,

o, equivalentemente, si F ⊂ V × V ∧ Un F . M´ as concretamente, diremos que F es una aplicaci´ on (o una funci´ on) de una clase A en una clase B si cumple F : A −→ B ≡ Un F ∧ DF = A ∧ RF ⊂ B. En otras palabras, una clase F es un´ıvoca si para cada x ∈ DF existe un u ´nico conjunto y (necesariamente en RF ) tal que (x, y) ∈ F . Dicho y recibe el nombre de imagen de x por F y se representa por F (x) ≡ y | (cto y ∧ (x, y) ∈ F ). Tambi´en se dice que x es una antiimagen de y por F , pero, aunque una clase F sea un´ıvoca, un elemento de RF puede tener varias antiim´ agenes por F . Si F ⊂ V × V (en particular si F es una funci´ on), entonces F ⊂ DF × RF , pero esto no es cierto si F es una clase cualquiera, pues entonces F puede contener elementos que no sean pares ordenados. Claramente, F : A −→ B significa que F asigna a cada x ∈ A una imagen F (x) ∈ B, y entonces F ⊂ A × B. Observemos que si F : A −→ B y B ⊂ C, tambi´en se cumple F : A −→ C. W W

1 Notemos

que los cuantificadores y y x que aparecen en las definiciones del dominio y el rango est´ an restringidas a conjuntos, por lo que la propiedad es normal y el axioma de comprensi´ on es aplicable.

12

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos Definimos:

V F : A −→ B inyectiva ≡ F : A −→ B ∧ xy ∈ A(F (x) = F (y) → x = y), V W F : A −→ B suprayectiva ≡ F : A −→ B ∧ y ∈ B x ∈ A f (x) = y, F : A −→ B biyectiva ≡ F : A −→ B inyectiva y suprayectiva. As´ı, F es inyectiva si asigna a cada elemento de A una imagen distinta en B (no hay dos elementos con la misma imagen), F es suprayectiva si todo elemento de B tiene una antiimagen (o, equivalentemente, si RF = B) y F es biyectiva si a cada elemento de A le asigna un u ´nico elemento de B y viceversa. Usaremos a menudo el criterio siguiente de igualdad de funciones: Teorema 1.12 Dos funciones olo si tienen el mismo V F y G son iguales si y s´ dominio A y se cumple que x ∈ A F (x) = G(x). ´ n: Una implicaci´ Demostracio on es trivial. Si F y G coinciden sobre su dominio com´ un, dado z ∈ F , por ser una funci´ on existen conjuntos x, y tales que z = (x, y). Entonces x ∈ A por definici´ on de dominio, luego y = F (x) = G(x), luego z = (x, y) ∈ G, y por lo tanto F ⊂ G. Igualmente se prueba la inclusi´ on opuesta. Veamos m´ as conceptos relacionados con las funciones: Definici´ on 1.13 La restricci´ on de una clase F a una clase X como F |X ≡ {(x, y) | x ∈ X ∧ (x, y) ∈ F }, es decir, se trata de la clase de todos los pares ordenados de F cuya primera componente est´ a en X. Es f´ acil ver que si F : A −→ B y X ⊂ A, entonces F |X : X −→ B. Definimos la clase inversa de una clase F como la clase F −1 ≡ {(y, x) | (x, y) ∈ F }. Observemos que si F ⊂ V × V , entonces (F −1 )−1 = F . Tambi´en es claro que si F : A −→ B biyectiva entonces F −1 : B −→ A biyectiva. Definimos la imagen de una clase X por una clase F como W F [X] ≡ {y | x ∈ X (x, y) ∈ F }. Equivalentemente, F [X] ≡ R(F |X ). Notemos que W F −1 [Y ] = {x | y ∈ Y (x, y) ∈ F }.

En particular, si F : A −→ B, X ⊂ A, Y ⊂ B, tenemos que W F [X] = {F (x) | x ∈ X} ≡ {y | x ∈ X F (x) = y}, F −1 [Y ] = {x | x ∈ A ∧ F (x) ∈ Y },

de modo que F [X] es la clase de todas las im´ agenes por F de elementos de X y F −1 [Y ] es la clase de todas las antiim´ agenes por F de los elementos de Y .

1.2. Funciones

13

Es f´ acil probar que si F : A −→ B, Y1 , Y2 ⊂ B y X1 , X2 ⊂ A, entonces F −1 [Y1 ∪ Y2 ] = F −1 [Y1 ] ∪ F −1 [Y2 ], F [X1 ∪ X2 ] = F [X1 ] ∪ F [X2 ],

F −1 [Y1 ∩ Y2 ] = F −1 [Y1 ] ∩ F −1 [Y2 ], pero F [X1 ∩ X2 ] ⊂ F [X1 ] ∩ F [X1 ]

y en general no se da la igualdad (pero se da si F es inyectiva). Definimos la composici´ on de dos clases F y G como la clase W F ◦ G ≡ {(x, z) | y(cto y ∧ (x, y) ∈ F ∧ (y, z) ∈ G)}.

En V particular, si F : A −→ B y G : B −→ C, se cumple que F ◦ G : A −→ C y x ∈ A (F ◦ G)(x) = G(F (x)), de modo que F ◦ G es la aplicaci´ on que resulta de “encadenar” F y G, es decir, de aplicar primero F y luego aplicar G sobre el resultado obtenido. Tambi´en es f´ acil comprobar que la composici´ on de aplicaciones inyectivas, suprayectivas o biyectivas es inyectiva, suprayectiva o biyectiva, respectivamente. En el u ´ltimo caso se cumple adem´ as que (F ◦ G)−1 = G−1 ◦ F −1 . Observemos que, dadas tres clases cualesquiera F , G, H, se cumple que F ◦ (G ◦ H) = (F ◦ G) ◦ H =

{(x, w) |

W yz(cto y ∧ cto z ∧ (x, y) ∈ F ∧ (y, z) ∈ G ∧ (z, w) ∈ H)}.

Finalmente, definimos la identidad en una clase A como la clase IA ≡ {(x, y) | x ∈ A ∧ x = y}.

Equivalentemente,Vse trata de la aplicaci´ on IA : A −→ A (claramente biyectiva) determinada por x ∈ A IA (x) = x.

Si llamamos I : V −→ V a la aplicaci´ on dada por I(x) = x, entonces IA = I|A . Si A ⊂ B, entonces se cumple tambi´en que IA : A −→ B y en este contexto se la llama inclusi´ on de A en B. Es f´ acil ver que si F : A −→ B, entonces IA ◦ F = F ◦ IB = F , y si F es biyectiva entonces F ◦ F −1 = IA , F −1 ◦ F = IB . Una forma de probar que una aplicaci´ on es biyectiva es encontrar su inversa, de acuerdo con el teorema siguiente: Teorema 1.14 Sean F : A −→ B y G : B −→ A. a) Si F ◦ G = IA entonces F es inyectiva y G suprayectiva. b) Si adem´ as G ◦ F = IB entonces F y G son biyectivas y G = F −1 .

14

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

´ n: a) Para probar que F es inyectiva tomamos x, y ∈ A y Demostracio suponemos que F (x) = F (y), con lo que G(F (x)) = G(F (y)), pero esto equivale a (F ◦ G)(x) = (F ◦ G)(y), que por hip´ otesis es IA (x) = IA (y), es decir, x = y. Para probar que la aplicaci´ on G es suprayectiva tomamos x ∈ A y observamos que y = F (x) ∈ B cumple G(y) = G(F (x)) = (F ◦ G)(x) = IA (x) = x. b) Aplicando a) con los papeles de F y G intercambiados obtenemos que F y G son biyectivas. Adem´ as, F −1 ◦ F ◦ G = F −1 ◦ IA , luego IB ◦ G = F −1 , luego −1 G=F . Terminamos esta secci´ on discutiendo algunas notaciones habituales relacionadas con las funciones. Ante todo, puesto que el teorema 1.12 nos garantiza que una funci´ on queda completamente determinada por su dominio y por la imagen que asigna a cada elemento de ´este, habitualmente definiremos las funciones especificando esta informaci´ on. on definida en la clase A tal que V Por ejemplo, si decimos “sea F la funci´ x ∈ A F (x) = {x}”, nos estamos refiriendo a F ≡ {(x, y) | x ∈ A ∧ y = {x}}.

Para que la definici´ on de F sea correcta es necesario comprobar que la propiedad y = {x} sea normal, para que el axioma de comprensi´ on sea aplicable, y adem´ as que, para cada x ∈ A, su imagen pretendida (en este caso {x}) sea un conjunto, pues en caso contrario, es decir, si y no es un conjunto, el par (x, y) ser´ıa simplemente (x, y) = {{x}, {x, y}} = {{x}, {x}} = {{x}, {x, x}} = (x, x), con lo que tendr´ıamos ciertamente la aplicaci´ on F , pero cumplir´ıa F (x) = x para todo x ∈ A cuya imagen pretendida no fuera un conjunto.2 Si se cumplen estos dos requisitos, es inmediato comprobar que F : A −→ V y que, para todo x ∈ A, F (x) toma el valor pretendido. Hay otra notaci´ on sustancialmente distinta que conviene usar a veces para representar ciertas aplicaciones. Para referirnos a una aplicaci´ on X : I −→ V usaremos a veces la notaci´ on {Xi }i∈I , y diremos entonces que {Xi }i∈I es una familia de conjuntos subindicados por la clase I. En este contexto escribimos Xi ≡ X(i) para referirnos a la imagen de i, y decimos que es el conjunto de ´ındice i en la familia considerada. Notemos que, desde un punto de vista l´ ogico, la expresi´ on X : I −→ V es la afirmaci´ on seg´ un la cual X es una aplicaci´ on de dominio X, mientras que {Xi }i∈I no es una afirmaci´ on, sino la forma de representar a una cierta 2 En

general, si t(x) es un t´ ermino delVlenguaje de la teor´ıa de conjuntos tal que la f´ ormula y = t(x) es normal y se demuestra que x ∈ A cto t(x), entonces F ≡ {(x, y) | x ∈ A ∧ y = t(x)},

define una funci´ on a la que V m´as habitualmente nos referiremos como “la funci´on F definida sobre la clase A dada por x ∈ A F (x) = t(x)”. En el ejemplo que hemos puesto, t(x) ≡ {x}.

1.3. Formaci´ on de conjuntos

15

aplicaci´ on de dominio I. No hay que confundir esta notaci´ on con {Xi | i ∈ I}, que es una forma de denotar el rango de X, es decir, RX o X[I]. Tambi´en podemos usar esta notaci´ on para definir una aplicaci´ on en los t´erminos explicados anteriormente, es decir, especificando su dominio y la imagen de cada elemento del dominio. Por ejemplo, si tenemos dos familias {Xi }i∈I e {Yi }i∈I , a partir de ellas podemos definir la familia {Xi ∩ Yi }i∈I , que ha de entenderse como la aplicaci´ on Z : I −→ V dada por Z(i) = Xi ∩ Yi o, m´ as concretamente Z ≡ {(i, y) | i ∈ I ∧ y = Xi ∩ Yi }.

Ahora bien, de momento no estamos en condiciones de justificar que esta definici´ on es correcta, pues, aunque la propiedad y = Xi ∩Yi es ciertamente normal, hay asegurar adem´ as que Xi ∩ Yi es un conjunto para todo i ∈ I. Esto lo justificaremos en la secci´ on siguiente, pero para ello ser´ a necesario un nuevo axioma. Esta notaci´ on es u ´til para hablar de grandes uniones e intersecciones, para lo cual introducimos adem´ as los convenios de notaci´ on S S T T Xi ≡ {Xi | i ∈ I}, Xi ≡ {Xi | i ∈ I}. i∈I

i∈I

De este modo V W S x(x ∈ Xi ↔ i ∈ I x ∈ Xi ), i∈I

V V T x(x ∈ Xi ↔ i ∈ I x ∈ Xi ). i∈I

No obstante, para operar con estas uniones e intersecciones es preferible contar antes con algunos de los resultados sobre formaci´ on de conjuntos que veremos en la secci´ on siguiente.

1.3

Formaci´ on de conjuntos

En esta secci´ on demostraremos (a partir de los axiomas necesarios) que pr´ acticamente todas las construcciones realizadas a partir de conjuntos dan lugar a nuevos conjuntos. Ya hemos visto dos axiomas de formaci´ on de conjuntos (es decir, axiomas que afirman que determinadas clases son, de hecho, conjuntos), el axioma del conjunto vac´ıo y el axioma del par. Aqu´ı presentaremos otros ´ tres. Este es el m´ as potente: Axioma de reemplazo Si F : A −→ B suprayectiva y A es un conjunto, entonces B tambi´en es un conjunto.3 Como primera consecuencia obtenemos: 3 Desde

un punto de vista l´ ogico conviene que los axiomas (al menos los m´ as b´ asicos de la teor´ıa) involucren los conceptos m´ as simples que sea posible, y por ello es u ´til observar que el axioma de reemplazo es equivalente a la versi´ on siguiente, en la que s´ olo aparecen los conceptos de conjunto, par ordenado y clase un´ıvoca:

V

F A(cto A ∧ Un F →

W

B(cto B ∧

V

v(v ∈ B ↔

W

u ∈ A (u, v) ∈ F ))).

Notemos que en esta sentencia necesariamente B = F [A], luego lo que afirma es que si F es un´ıvoca y A es un conjunto, entonces F [A] es un conjunto. Claramente esto implica la forma

16

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

Teorema 1.15 Toda subclase de un conjunto es un conjunto. ´ n: Sea A un conjunto y B ⊂ A. Si B = ∅, entonces B es un Demostracio conjunto por el axioma del conjunto vac´ıo. En caso contrario existe un b ∈ B. Definimos F : A −→ B mediante n x si x ∈ B, F (x) = b si x ∈ / B. Recordemos que esto es una forma pr´ actica de definir la clase F dada por F ≡ {(x, y) | x ∈ A ∧ ((x ∈ B ∧ y = x) ∨ (x ∈ / B ∧ y = b))}. Claramente F : A −→ B suprayectiva, luego B es un conjunto por el axioma de reemplazo. Como consecuencia: Teorema 1.16 La clase universal V es una clase propia. ´ n: Si V fuera un conjunto, por el teorema anterior todas las Demostracio clases ser´ıan conjuntos, pues todas est´ an contenidas en V , pero sabemos que existen clases propias, como la clase de Russell R, luego V no puede ser un conjunto. Ahora es inmediato que la intersecci´ on de una clase A y un conjunto B (en particular la intersecci´ on de dos conjuntos) es un conjunto, pues A ∩ B ⊂ B. Para probar que la uni´ on de conjuntos es un conjunto necesitamos un nuevo axioma: Axioma de la uni´ on En particular:

V S A(cto A → cto A).

Teorema 1.17 Si A y B son conjuntos, tambi´en lo es A ∪ B. S ´ n: Basta tener en cuenta que A∪B = {A, B}, y que {A, B} Demostracio es un conjunto por el axioma del par.

En particular ahora podemos probar que cualquier clase definida por extensi´ on es un conjunto, pues, por ejemplo, {a, b, c, d} = {a} ∪ {b} ∪ {c} ∪ {d}, y las cuatro clases {a}, {b}, {c}, {d} son conjuntos por el axioma del par (o por ser el conjunto vac´ıo si alguna de las clases a, b, c, d no es un conjunto). Combinando el axioma de reemplazo con el de la uni´ on obtenemos que S si {Xi }i∈I es una familia de conjuntos e I es un conjunto, entonces la uni´ on Xi i∈I

que hemos adoptado para el axioma de reemplazo y, rec´ıprocamente, a partir de ella podemos demostrar ´ esta aplic´ andola a F |A∩DF : A ∩ DF −→ F [A] suprayectiva, teniendo en cuenta que A ∩ DF es un conjunto por el teorema 1.15.

1.3. Formaci´ on de conjuntos

17

S es un conjunto, pues dicha uni´ on no es sino RX y RX es un conjunto por reemplazo y la uni´ on es un conjunto por el axioma de la uni´ on. T Notemos que la intersecci´ on Xi es tambi´en un conjunto siempre que la i∈I T clase I 6= ∅, pues si existe un i ∈ I entonces Xi ⊂ Xi y podemos aplicar i∈I T el teorema 1.15. En cambio, si I = ∅ tenemos que Xi = V , luego no es un i∈I conjunto.

Combinando tambi´en el axioma de reemplazo con el de la uni´ on obtenemos que el producto cartesiano de conjuntos es de nuevo un conjunto: Teorema 1.18 Si A y B son conjuntos, tambi´en lo es A × B. ´ n: Para cada a ∈ A, la clase {a} × B es un conjunto, pues Demostracio la aplicaci´ on F : B −→ {a} × B dada por F (b) = (a, b) es biyectiva. Esto nos permite considerar la familia de conjuntos {{a} × B}a∈A , es decir, la aplicaci´ on F : A −→ V dada por F (a) = {a} × B. Ahora basta observar que S A×B = {a} × B a∈A

y aplicar la observaci´ on precedente: como A es un conjunto, tambi´en lo es A×B. Es costumbre escribir {x ∈ A | φ(x)} ≡ {x | x ∈ A ∧ φ(x)}

para enfatizar que estamos definiendo una subclase de la clase A. Por 1.15 sabemos que si A es un conjunto, toda clase definida as´ı es de hecho un conjunto. Similarmente, usaremos la notaci´ on {(x, y) ∈ A × B | φ(x, y)} ≡ {(x, y) | (x, y) ∈ A × B ∧ φ(x, y)}, que, por el teorema anterior, tambi´en da lugar a conjuntos siempre que A y B son conjuntos. Nota Ahora ya es f´ acil trabajar con uniones e intersecciones de familias de conjuntos. Por ejemplo en la prueba de 1.18 hemos usado un caso particular de la primera de las propiedades siguientes, cuya prueba no ofrece dificultad: S S T T ( Xi ) × Y = (Xi × Y ), ( Xi ) × Y = (Xi × Y ). i∈I

i∈I

i∈I

i∈I

obviamente lo mismo vale con uniones e intersecciones en el segundo factor. Notemos que para asegurar que los segundos miembros est´ an bien definidos necesitamos saber que cada Xi × Y es un conjunto. Otras propiedades muy u ´tiles son las siguientes: si {Xi }i∈I es una familia de subconjuntos de un conjunto X, entonces S T T S X\ Xi = (X \ Xi ), X\ Xi = (X \ Xi ). i∈I

i∈I

i∈I

i∈I

18

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

En principio se requiere que I 6= ∅, pero cuando se trabaja con familias de subconjuntos de un conjunto fijo X, es conveniente considerar que, por definici´ on, T Xi = X, con lo que las igualdades anteriores valen incluso si I = ∅. i∈∅

Una consecuencia sencilla de los teoremas precedentes es la siguiente:

Teorema 1.19 Si R ⊂ V × V , entonces cto R ↔ cto DR ∧ cto RR. ´ n: La aplicaci´ Demostracio on R −→ DR dada por4 (x, y) 7→ x es suprayectiva, luego, por reemplazo, si R es un conjunto tambi´en lo es su dominio, y an´ alogamente se razona con el rango. Para la implicaci´ on opuesta basta tener en cuenta que R ⊂ DR × RR.

Sin embargo, si F es una funci´ on la equivalencia anterior se puede simplificar a cto F ↔ cto DF , puesto que si el dominio de F es un conjunto, puesto que F : DF → RF suprayectiva, por reemplazo tenemos que el rango tambi´en es un conjunto. Alternativamente, es f´ acil definir una biyecci´ on entre F y DF . As´ı pues: Teorema 1.20 Una funci´ on es un conjunto si y s´ olo si lo es su dominio. Presentamos finalmente el u ´ltimo de los axiomas de formaci´ on de conjuntos, para lo cual definimos previamente la clase de partes de una clase dada: PY ≡ {x | x ⊂ Y } Notemos que x ⊂ Y es una propiedad normal pues equivale a que todo conjunto que pertenezca a x pertenece tambi´en a Y . Hay que tener presente que PY es la clase de todos los subconjuntos (no de todas las subclases) de Y . Si Y es un conjunto no hay diferencia y PY contiene a todo x ⊂ Y , pues esto ya implica que x es un conjunto. En cambio, si Y es una clase propia, tenemos, por ejemplo, que Y ⊂ Y , pero Y ∈ / PY . Por ejemplo, es f´ acil ver que PV = V . Axioma de partes (AP)

V X(cto X → cto PX).

En otras palabras, el axioma de partes afirma que la clase de partes de un conjunto es un conjunto. A partir de aqu´ı es f´ acil demostrar que muchas otras clases son conjuntos. Por ejemplo, definimos AB ≡ {f | f : A −→ B}.

Si B es una clase propia, tenemos que AB = ∅, pues ninguna f : A −→ B es un conjunto que pueda pertenecer a AB . En cambio, si B es un conjunto (aunque A no lo sea) tenemos que AB contiene a todas las aplicaciones f : A −→ B, pues todas ellas son conjuntos. 4 M´ as

concretamente, nos referimos a F ≡ {(z, x) | z ∈ R ∧

W

y (cto y ∧ z = (x, y))}.

En lo sucesivo, en casos similares a ´ este no nos detendremos a explicitar c´ omo las funciones que definamos se reducen en u ´ltima instancia a aplicaciones del axioma de comprensi´ on.

1.4. La teor´ıa de conjuntos NBG∗ Teorema 1.21

19

V AB(cto A ∧ cto B → cto AB )

´ n: Basta observar que si f ∈ AB entonces f ⊂ B × A, luego Demostracio A ⊂ P(B × A), y basta aplicar los resultados que ya conocemos de formaci´ on de conjuntos. B

M´ as en general, dada una familia de conjuntos {Xi }i∈I , definimos su producto cartesiano como la clase V Q Xi ≡ {x | x : I −→ V ∧ i ∈ I xi ∈ Xi }. i∈I

De este modo, cada elemento del producto cartesiano es una familia de conjuntos {xi }i∈I con la propiedad de que cada componente xi pertenece al conjunto correspondiente Xi . Observemos que Q

i∈I

Xi ⊂

µ

S

i∈I

Xi

∂I

,

luego, por los resultados precedentes, si I es un conjunto tambi´en lo es el producto cartesiano. Los resultados de esta secci´ on bastan para demostrar que cualquier construcci´ on conjuntista usual proporciona conjuntos cuando parte de conjuntos.

1.4

La teor´ıa de conjuntos NBG∗

Llegados a este punto hemos presentado ya los que podemos considerar como axiomas b´ asicos de la teor´ıa de conjuntos, aunque en los cap´ıtulos siguientes introduciremos otros tres m´ as. Por ello conviene reunirlos aqu´ı para dejar constancia de la teor´ıa concreta en la que estamos trabajando. Llamaremos teor´ıa de conjuntos restringida de Von Neumann-Bernays-G¨ odel (NBG∗ ) a la teor´ıa cuyos u ´nico concepto no definido es la relaci´ on ∈ de pertenencia (entre clases) y cuyos axiomas son los siguientes: V V Extensionalidad AB( x(x ∈ A ↔ x ∈ B) → A = B) W V Comprensi´ on A x(x ∈ A ↔ cto x ∧ φ(x)) (∗) Vac´ıo cto ∅ V Par xy (cto x ∧ cto y → cto{x, y}) V S Uni´ on A(cto A → cto A) V Reemplazo F AB(F : A −→ B suprayectiva ∧ cto A → cto B) (∗) para toda propiedad normal φ(x), tal vez con m´ as variables, adem´ as de x.

Notemos que no hemos incluido el axioma de partes (AP). Ello se debe a que una parte importante de la teor´ıa de conjuntos puede desarrollarse sin ´el, y a la larga resulta u ´til saber qu´e axiomas (m´ as all´ a de los axiomas b´ asicos de NBG∗ ) son necesarios para probar cada resultado. En lo sucesivo trabajaremos en NBG∗ salvo que indiquemos lo contrario.

20

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

Como explic´ abamos al final de la secci´ on 1.1, la teor´ıa NBG∗ es equivalente a ∗ la teor´ıa ZF (la teor´ıa restringida de Zermelo-Fraenkel) que resulta de eliminar el axioma de comprensi´ on y reformular los restantes para evitar toda referencia a clases que a priori no tengan por qu´e ser conjuntos.5 Son equivalentes en el sentido de que un teorema que hable u ´nicamente de conjuntos puede demostrarse en NBG∗ si y s´ olo si puede demostrarse en ZF∗ . Las clases propias en NBG∗ son, pues, un mero recurso t´ecnico no esencial para trabajar m´ as c´ omodamente con los conjuntos.

1.5

Relaciones

Continuamos ahora con el prop´ osito principal de este cap´ıtulo, que es presentar el lenguaje b´ asico de la teor´ıa de conjuntos. Ya hemos introducido el vocabulario relacionado con las funciones, y ahora vamos a hacer lo propio con las relaciones. La definici´ on conjuntista de “relaci´ on” es muy simple: Definici´ on 1.22 Una relaci´ on (binaria) en una clase A es una clase R ⊂ A×A. Si R es una relaci´ on en A y a, b ∈ A, escribiremos a R b ≡ (a, b) ∈ R, y en tal caso diremos que a est´ a relacionado con b respecto de la relaci´ on R. Observemos que, trivialmente, toda relaci´ on en un conjunto es un conjunto. Diremos que una relaci´ on R en una clase A es: V a) Reflexiva si x ∈ A x R x,

b) Irreflexiva si c) Sim´etrica si

V x ∈ A ¬x R x,

V xy ∈ A (x R y → y R x),

d) Antisim´etrica si e) Asim´etrica si f) Transitiva si g) Conexa si

V xy ∈ A (x R y ∧ y R x → x = y)

V xy ∈ A (x R y → ¬y R x)

V xyz ∈ A (x R y ∧ y R z → x R z)

V xy ∈ A (x R y ∨ y R x)

h) D´ebilmente conexa si 5 Por

V xy ∈ A(x R y ∨ y R x ∨ x = y)

ejemplo, el axioma del par puede reformularse diciendo que para todo par de conjuntos x, y existe otro conjunto z cuyos u ´nicos elementos son x e y. El u ´nico axioma cuya reformulaci´ on no es trivial es el de reemplazo.

1.5. Relaciones

21

Relaciones de equivalencia Una relaci´ on de equivalencia en una clase A es una relaci´ on reflexiva, sim´etrica y transitiva en A. Si R es una relaci´ on de equivalencia en A y a ∈ A, definimos la clase de equivalencia de a respecto de R como [a]R ≡ {b ∈ A | a R b}, es decir, como la clase de todos los elementos de A relacionados con a. El resultado fundamental sobre clases de equivalencia es el siguiente, cuya prueba dejamos a cargo del lector: Teorema 1.23 Sea R una relaci´ on de equivalencia en una clase A y consideremos a, b ∈ A. Entonces: a) a R b ↔ [a]R = [b]R , b) ¬a R b ↔ [a]R ∩ [b]R = ∅. En particular, dos clases de equivalencia en A son iguales o disjuntas. Diremos que una relaci´ on de equivalencia en una clase A es conjuntista si todas las clases de equivalencia que determina son conjuntos. Esto sucede en particular si A es un conjunto, pues en general las clases de equivalencia son subclases de A, luego si A es un conjunto todas ellas lo son tambi´en. Si una relaci´ on de equivalencia R en una clase A es conjuntista, podemos definir la clase cociente como6 A/R ≡ {[a]R | a ∈ A}. Naturalmente, tambi´en podemos considerar la clase cociente para una relaci´ on no conjuntista, pero entonces puede ocurrir perfectamente que A/R = ∅, lo cual no significa que no haya clases de equivalencia, sino que ninguna de ellas es un conjunto. En el caso en que R es conjuntista podemos definir la aplicaci´ on can´ onica p : A −→ A/R dada por p(a) = [a]R . Obviamente es suprayectiva, luego el axioma de reemplazo nos da que si A es un conjunto, A/R tambi´en lo es, y hablamos entonces del conjunto cociente, en lugar de clase cociente (aunque en este caso se sigue hablando de clases de equivalencia). 6 T´ ecnicamente, la existencia de laWclase cociente viene dada por el axioma de comprensi´ on, teniendo en cuenta que A/R ≡ {y | a ∈ A y = [a]R }.

22

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

Relaciones de orden Una relaci´ on de orden parcial en una clase A es una relaci´ on reflexiva, antisim´etrica y transitiva en A. Si adem´ as es conexa se dice que es una relaci´ on de orden total. Es costumbre usar el signo ≤ para representar relaciones de orden arbitrarias (de modo que si decimos que ≤ es una relaci´ on de orden en una clase A hay que entender que ≤ es una clase y que ≤ ⊂ A × A). En estos t´erminos, las propiedades que definen una relaci´ on de orden se escriben as´ı: V V a ∈ A a ≤ a, ab ∈ A(a ≤ b ∧ b ≤ a → a = b), V abc ∈ A(a ≤ b ∧ b ≤ c → a ≤ c). V La relaci´ on es de orden total si adem´ as ab ∈ A(a ≤ b ∨ b ≤ a). Una relaci´ on de orden estricto en una clase A es una relaci´ on asim´etrica y transitiva en A. Si adem´ as es d´ebilmente conexa entonces es una relaci´ on de orden total estricto.

Notemos que, pese a la nomenclatura, una relaci´ on de orden estricto no es una relaci´ on de orden. La relaci´ on entre ambos conceptos es que si ≤ es una relaci´ on de orden en A, entonces la relaci´ on dada por a < b ↔ a ≤ b ∧ a 6= b es una relaci´ on de orden estricto en A y, rec´ıprocamente, si < es una relaci´ on de orden estricto en A, entonces la relaci´ on dada por a≤b↔a b ≡ b < a. Cuando digamos que (A, ≤) es una clase total o parcialmente ordenada querremos decir7 que ≤ es una relaci´ on de orden (total o parcial) en A. Sea A una clase ordenada por la relaci´ on ≤ y sea B ⊂ A. Entonces: V a) M ∈ A es una cota superior de B si x ∈ B x ≤ M , V b) m ∈ A es una cota inferior de B si x ∈ B m ≤ x, V c) M ∈ A es un maximal de B si M ∈ B y x ∈ B(M ≤ x → M = x). V d) m ∈ A es un minimal de B si m ∈ B y x ∈ B(x ≤ m → x = m).

7 Si A es un conjunto podemos entender esto como una afirmaci´ on sobre el par ordenado (A, ≤), pero usaremos esta misma expresi´ on incluso si A es una clase propia, aunque ahora la afirmaci´ on “(A, ≤) es una clase total o parcialmente ordenada” no puede interpretarse como una afirmaci´ on sobre el par ordenado (A, ≤) = {{∅}}, sino literalmente como hemos indicado: como una forma c´ omoda de expresar que ≤ es una relaci´ on de orden en la clase A.

1.5. Relaciones

23

e) M V ∈ A es el supremo de B si M es una cota superior de B y x ∈ A(x es una cota superior de B → M ≤ x). f) m V ∈ A es el ´ınfimo de B si m es una cota inferior de B y x ∈ A(x es una cota inferior de B → x ≤ m).

g) M ∈ A es el m´ aximo de B si M ∈ B y M es una cota superior de B. h) m ∈ A es el m´ınimo de B si m ∈ B y m es una cota inferior de B. Ejemplo Si A es cualquier clase, la inclusi´ on define una relaci´ on de orden parcial en PA, es decir, podemos considerar en esta clase la relaci´ on dada por X ≤ Y ↔ X ⊂ Y. Es inmediato comprobar que se trata de una relaci´ on de orden parcial cuya relaci´ on de orden estricto asociada es la inclusi´ on estricta X √ Y . Respecto de esta relaci´ on, PA tiene como m´ınimo elemento a ∅. Si A es un conjunto, entonces PA tiene como m´ aximo elemento a A, pero si A no es un conjunto, entonces PA no tiene m´ aximo elemento, pues dado cualquier X ∈ PA, ser´ a X √ A, luego existe un x ∈ A \ X, luego X √ X ∪ {x} ∈ PA, luego X no es el m´ aximo de PA. Si A 6= ∅, la subclase B = PA \ {∅} tiene por minimales a los elementos de la forma {a}, con a ∈ A, pero no tiene m´ınimo, salvo en el caso en que A = {a}, pues si A contiene al menos dos elementos a y b, entonces no se cumple {a} ⊂ {b}, luego {a} no es m´ınimo de B, pero es minimal porque ning´ un elemento de B es menor que {a}. S Si B es un subconjunto B es el supremo de B en PA, pues S de A, entonces S todo x ∈ B cumple x ⊂ B, luego B es una V cota superior de B, y si M ∈ PA es una cota superior de B, esto significa que x ∈ B x ⊂ M , de donde se sigue S S que B ⊂ M , luego B es la menor cota superior de B. T Similarmente, si B ⊂ A es no vac´ıo, entonces B es el ´ınfimo de B en PA. As´ı pues, si A tiene m´ as de un elemento, hemos visto que B = PA \ {∅} no tiene m´ınimo elemento, pero tiene por ´ınfimo a ∅. {a, b, c} M´ as concretamente, si A = {a, b, c}, donde los conjuntos ✟✟❍❍ ✟ ❍ a, b, c son distintos dos a dos, la relaci´ on de orden dada {a, b} {b, c} {a, c} por la inclusi´ on es la que muestra la figura. Vemos en✥ ✥ ❍ ❍ ✥ ❍ ❍ ✥ tonces que PA tiene por m´ınimo a ∅ y por m´ aximo a A. ✥✥❍ ❍ En cambio, PA \ {A} no tiene m´ aximo elemento, pero {a} {b} {c} tiene tres elementos maximales, los tres conjuntos con ❍ ✟ ❍❍✟✟ dos elementos. Similarmente, PA\{∅} no tiene m´ınimo, ∅ pero tiene tres minimales, a saber, los conjuntos {a},

{b}, {c}, y tambi´en tiene ´ınfimo, concretamente ∅. El conjunto B = {{a}, {b}, ∅} no tiene m´ aximo, pero tiene por supremo a {a, b}.

24

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

Es f´ acil ver que en un conjunto totalmente ordenado todo maximal es m´ aximo y todo minimal es m´ınimo. Si un conjunto tiene m´ aximo o m´ınimo, supremo o ´ınfimo, entonces ´estos son u ´nicos. El supremo (´ınfimo) de una clase es m´ aximo (m´ınimo) si y s´ olo si pertenece a la clase. Cuando tenemos una clase A ordenada por una relaci´ on ≤ y una subclase B ⊂ A, consideramos, aunque no se indique expl´ıcitamente, que B est´ a ordenada por la restricci´ on de ≤ a B, es decir, con la intersecci´ on de ≤ con B × B, de modo que si x, y ∈ B, se cumple x ≤ y como elementos de B si y s´ olo si se cumple como elementos de A. Es inmediato comprobar que esta restricci´ on es un orden en B. M´ as a´ un, B est´ a totalmente ordenada si A lo est´ a. Diremos que F : (A, ≤1 ) −→ (B, ≤2 ) es mon´ otona creciente o, simplemente, creciente si ≤1 y ≤2 son relaciones de orden parcial en A y B respectivamente, F : A −→ B y V xy ∈ A(x ≤1 y → F (x) ≤2 F (y)). Se dice que F es mon´ otona decreciente o decreciente si cumple V xy ∈ A(x ≤1 y → F (y) ≤2 F (x)).

Se dice que F es estrictamente mon´ otona creciente o decreciente si se cumple esto mismo cambiando las desigualdades no estrictas ≤ por desigualdades estrictas 0, c) negativo si a ≤ 0, d) estrictamente negativo si a < 0. Representaremos por A+ ≡ {a ∈ A | a > 0},

A− ≡ {a ∈ A | a < 0},

los conjuntos de elementos estrictamente positivos y estrictamente negativos, respectivamente, de un anillo ordenado A. De este modo, A se descompone en uni´ on disjunta A = A− ∪ {0} ∪ A+ . La primera propiedad de compatibilidad nos permite despejar sumas: a + b ≤ c → a ≤ c − b. En particular, 0 ≤ a ↔ −a ≤ 0, de modo que el inverso de un elemento (estrictamente) positivo es (estrictamente) negativo, y viceversa. La segunda propiedad de compatibilidad implica que la multiplicaci´ on por elementos positivos conserva las desigualdades: V abc ∈ A(a ≤ b ∧ c ≥ 0 → ac ≤ bc). En efecto, como b − a ≥ 0, resulta que (b − a)c = bc − ac ≥ 0, luego ac ≤ bc.

En cambio, la multiplicaci´ on por elementos negativos invierte las desigualdades: V abc ∈ A(a ≤ b ∧ c ≤ 0 → ac ≥ bc). En efecto, como −c ≥ 0, tenemos que −ac ≤ −bc, de donde, despejando dos veces, bc ≤ ac.

De estas dos propiedades se sigue en particular que el producto de dos elementos positivos o dos elementos negativos es positivo, mientras que el producto de un positivo por un negativo es negativo. En particular, todo cuadrado (todo producto de un elemento por s´ı mismo) es positivo.

1.6. Leyes de composici´ on interna

31

En particular, en un anillo unitario ordenado en el que 1 6= 0 se cumple que −1 < 0 < 1. En efecto, basta tener en cuenta que 1 = 1 · 1 > 0. Adem´ as, la igualdad a · a−1 = 1 > 0 implica que el inverso de un elemento positivo (resp. negativo) es positivo (resp. negativo). En todo anillo ordenado A podemos definir la funci´ on valor absoluto | | : A −→ A+ ∪ {0} dada por |a| =

Ω

a si a ≥ 0, −a si a ≤ 0.

Se cumplen las propiedades siguientes: a) |a| = 0 ↔ a = 0, b) |a + b| ≤ |a| + |b|, c) |ab| = |a||b|, d) | − a| = |a|, e) ||a| − |b|| ≤ |a − b|. En efecto, la propiedad a) es evidente, para probar b) conviene observar que |a| ≤ b ↔ −b ≤ a ≤ b. Las dos implicaciones se prueban trivialmente distinguiendo dos casos, seg´ un si a es positivo o negativo. En particular, como |a| ≤ |a| y |b| ≤ |b|, tenemos que −|a| ≤ a ≤ |a|,

−|b| ≤ b ≤ |b|,

de donde, aplicando varias veces las propiedades de compatibilidad, −|a| − |b| ≤ a + b ≤ |a| + |b|, lo que a su vez implica que |a+b| ≤ |a|+|b|. Las propiedades c) y d) se obtienen f´ acilmente distinguiendo casos. Para probar e) observamos que |a| = |a − b + b| ≤ |a − b| + |b| ⇒ |a| − |b| ≤ |a − b|. Invirtiendo los papeles probamos que |b| − |a| ≤ |b − a| = | − (a − b)| = |a − b|, luego −|a − b| ≤ |a| − |b| ≤ |a − b|, y hemos visto que esto equivale a ||a| − |b|| ≤ |a − b|.

32

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

Cuerpos de cocientes Como muestra de que NBG∗ es suficiente para formalizar los razonamientos conjuntistas elementales vamos a demostrar un resultado algebraico, seg´ un el cual todo dominio ´ıntegro puede extenderse hasta un cuerpo. En todo este apartado (D, +, ·) ser´ a un dominio ´ıntegro prefijado. Definimos D∗ = D \ {0} y consideramos en D × D∗ la relaci´ on de equivalencia dada por (a, b) ∼ (c, d) ↔ ad = bc. Es f´ acil ver que ciertamente es una relaci´ on de equivalencia. Por ejemplo, para probar la transitividad partimos de que (a, b) ∼ (c, d) ∼ (e, f ), lo que significa que ad = bc y cf = de, de donde adcf = bcde y, como los elementos no nulos son simplificables, si c 6= 0 podemos concluir af = be, mientras que si c = 0 tenemos que ad = 0 = de, luego a = e = 0, luego af = be igualmente. Representamos por KD = (D × D∗ )/ ∼ el conjunto cociente. Para cada par (a, b) ∈ D × D∗ , representaremos por a/b su clase de equivalencia. Claramente, el teorema 1.23 a) se traduce en este caso en la equivalencia a c = ↔ ad = bc. b d Definimos en KD las operaciones + y · dadas por a c ad + bc a c ac + = , · = . b d bd b d bd Observemos que, desde un punto de vista conjuntista, W + ≡ {((x, y), z) ∈ (KD × KD ) × KD | abcd ∈ D(x = a/b ∧ y = c/d ∧ z = (ad + bc)/bd)}.

La definici´ on es correcta, en el sentido de que determina un conjunto +, pero no podemos asegurar a priori que sea una funci´ on + : KD × KD −→ KD .

En primer lugar, el hecho de que todo par (x, y) tenga al menos una imagen z se debe a que, por definici´ on de cociente, siempre podemos expresar x = a/b, y = c/d y, como bd 6= 0 (ya que D es un dominio ´ıntegro), podemos formar la fracci´ on z = (ad + bc)/bd, con lo que ((x, y), z) ∈ +. Por otra parte, debemos probar que la imagen z es u ´nica. Para ello suponemos que ((x, y), x), (x, y), z 0 ) ∈ +, lo cual significa que podemos expresar x=

a a0 = 0, b b

y=

c c0 = 0, d d

y que

ad + bc a0 d0 + b0 c0 , z0 = , bd b0 d0 y debemos demostrar que z = z 0 . Esto equivale a que z=

(ad + bc)b0 d0 = (a0 d0 + b0 c0 )bd, o tambi´en a que (ab0 )(dd0 ) + (cd0 )(bb0 ) = (a0 b)(dd0 ) + (c0 d)(bb0 ), y esto se sigue inmediatamente de las igualdades de las expresiones para x e y.

1.6. Leyes de composici´ on interna

33

El hecho que acabamos de comprobar suele enunciarse diciendo que la suma est´ a bien definida. En general, cuando definimos una aplicaci´ on f y uno o varios de sus argumentos son clases de equivalencia de uno o varios conjuntos cociente y en la definici´ on de f usamos un elemento concreto de cada clase de equivalencia, decimos que f est´ a bien definida cuando comprobamos que la imagen de unos argumentos dados no depende del representante concreto elegido en cada clase de equivalencia. Por ejemplo, la forma habitual de tratar las situaciones como la que estamos considerando sin entrar en detalles conjuntistas que podr´ıamos calificar de pedantes es decir, en el caso del producto, “vamos a comprobar que el producto est´ a bien definido”, lo cual supone comprobar que si

a a0 = 0 b b

y

c d0 = 0, d d

entonces

ac a0 c0 = 0 0, bd bd

es decir, que el producto definido con unos representantes de las fracciones es el mismo que el definido con otros. (Aparte de esto, hay que observar que el producto es realmente una fracci´ on porque bd 6= 0.) Omitimos la comprobaci´ on, que es m´ as sencilla que la de la suma, as´ı como la comprobaci´ on rutinaria de que la suma y el producto de fracciones cumplen todas las propiedades requeridas por la definici´ on de anillo. Indiquemos u ´nicamente que el neutro para la suma es la fracci´ on 0 = 0/1 y que el opuesto de una fracci´ on es −(a/b) = (−a)/b. En cuanto al producto, es inmediato comprobar que tiene por neutro a la fracci´ on 1 = 1/1 y que todo elemento no nulo tiene inverso, pues si a/b 6= 0/1, entonces a 6= 0, luego podemos considerar la fracci´ on b/a, que claramente es la inversa de a/b, es decir: ≥ a ¥−1 b = . b a Por lo tanto, KD es un cuerpo con las operaciones que hemos definido. Consideramos ahora la aplicaci´ on iD : D −→ KD dada por iD (a) = a/1. Es trivial comprobar que es inyectiva, as´ı como que iD (a + b) = iD (a) + iD (b),

iD (ab) = iD (a)iD (b).

Conviene introducir algunos conceptos para describir esta situaci´ on: Definici´ on 1.29 Una aplicaci´ on f : A −→ B entre dos anillos es un homomorfismo de anillos si cumple11 V V xy ∈ A f (x + y) = f (x) + f (y), xy ∈ A f (xy) = f (x)f (y).

Si adem´ as es inyectiva, suprayectiva o biyectiva se dice que es un monomorfismo, epimorfismo o isomorfismo de anillos, respectivamente. Dos anillos son isomorfos si existe un isomorfismo de anillos entre ellos. 11 Estas

propiedades implican que f (0) = 0, pues f (0) = f (0 + 0) = f (0) + f (0), luego f (0) = 0, y si f es un monomorfismo y A y B son dominios ´ıntegros entonces f (1) = 1, pues igualmente f (1) = f (1)f (1), luego f (1)(1 − f (1)) = 0 y f (1) 6= f (0) = 0, luego f (1) = 1.

34

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

Si dos anillos A y B cumplen que A ⊂ B y las operaciones de A son las restricciones de las de B (es decir, que x + y y xy significa lo mismo en A y en B) entonces se dice que A es un subanillo de B. En estos t´erminos, lo que hemos probado es que iD : D −→ K es un monomorfismo de dominios ´ıntegros. En general, si f : A −→ B es un homomorfismo de anillos, entonces f [A] es un subanillo de B con la suma y el producto de B, pues dos elementos de f [A] son de la forma f (x) y f (y), para ciertos x, y ∈ A, luego su suma y su producto son f (x) + f (y) = f (x + y) ∈ f [A], f (x)f (y) = f (xy) ∈ f [A], luego al sumar y multiplicar con las operaciones de B no nos salimos de f [A], y tenemos, por consiguiente, dos leyes de composici´ on interna en i[A], que obviamente cumplen todas las propiedades requeridas para formar un anillo. Si adem´ as f es un monomorfismo, entonces f : A −→ f [A] es por definici´ on un isomorfismo de anillos, por lo que podemos decir que A es isomorfo a un subanillo de B. Por u ´ltimo, si dos anillos son isomorfos, esto significa que tienen las mismas propiedades que dependan u ´nicamente de la suma y del producto. ¯ = iD [D] ⊂ KD , resulta que D, ¯ con En nuestro contexto, si llamamos D ¯ las operaciones de KD es un anillo y iD : D −→ D es un isomorfismo de ¯ cumple adem´ anillos, pero D as que est´ a contenido en un cuerpo. En definitiva, hemos probado que todo dominio ´ıntegro puede reemplazarse por otro isomorfo contenido en un cuerpo. El cuerpo KD que hemos construido se llama cuerpo de cocientes o cuerpo de fracciones de D. M´ as a´ un, si D es un anillo ordenado, podemos transportar la relaci´ on de orden a KD definiendo x≤y≡

W a c abcd ∈ D(c > 0 ∧ d > 0 ∧ x = ∧ y = ∧ ad ≤ bc). b d

En primer lugar observamos que, puesto que a −a = , b −b

toda fracci´ on admite un representante con denominador positivo. Y si tomamos dos fracciones a/b y c/d con denominador positivo, entonces a c ≤ ↔ ad ≤ bc. b d Una implicaci´ on se cumple por la definici´ on que hemos dado de ≤, pero la otra no es inmediata, pues, en principio, que se cumpla la parte izquierda significa que a a0 c c0 = 0, = 0, b b d d

1.6. Leyes de composici´ on interna

35

con b0 , d0 > 0 y a0 d0 ≤ b0 c0 . Vamos a probar que esto implica ad ≤ bc. En principio tenemos que ab0 = ba0 y cd0 = dc0 . Notemos tambi´en que c es positivo si y s´ olo si lo es cd0 , si y s´ olo si lo es c0 d si y s´ olo si lo es c0 . Hay que distinguir dos 0 casos, seg´ un si c y c son ambos positivos o son ambos negativos. Trataremos el caso en que ambos son negativos y dejamos el otro a cargo del lector: a0 d0 ≤ b0 c0 ⇒ a0 bd0 c ≥ b0 c0 bc ⇒ b0 c0 ad ≥ b0 c0 bc ⇒ b0 d0 (ad − bc) ≥ 0 ⇒ ad − bc ≤ 0 ⇒ ad ≤ bc. Observemos que, dadas tres fracciones cualesquiera se pueden expresar en la forma a b c , , d d d con d > 0. En efecto, si en principio las fracciones son a/b, a0 /b0 , a00 /b00 , donde podemos suponer que los denominadores son positivos, y entonces a ab0 b00 = 0 00 , b bb b

a0 ba0 b00 = , b0 bb0 b00

a00 bb0 a00 = , b00 bb0 b00

con denominador positivo. Para fracciones con denominador com´ un positivo la relaci´ on que hemos definido se reduce a a c ≤ ↔ a ≤ c. d d Teniendo esto en cuenta es inmediato comprobar que la relaci´ on ≤ es una relaci´ on de orden en KD y que es compatible con la estructura de anillo, es decir, que convierte a KD es un cuerpo ordenado. Definici´ on 1.30 Un homomorfismo (resp. monomorfismo, epimorfismo, isomorfismo) de anillos ordenados es un homomorfismo (resp. monomorfismo, epimorfismo, isomorfismo) de anillos f : A −→ B que adem´ as cumpla la relaci´ on V xy ∈ A(x ≤ y → f (x) ≤ f (y)).

Equivalentemente, un isomorfismo de anillos ordenados es un isomorfismo de anillos que adem´ as es una semejanza, lo cual hace que ambos anillos sean indistinguibles respecto de todas las propiedades definibles en t´erminos de la suma, el producto o la relaci´ on de orden. En nuestro contexto, es claro que iD : D −→ KD es un monomorfismo de anillos ordenados, es decir, que V ab ∈ D (a ≤ b ↔ iD (a) ≤ iD (b)).

¯ es una semejanza cuando consideramos en D ¯ el orden Por lo tanto iD : D −→ D de KD . As´ı pues, sustituyendo D por una “copia” isomorfa, tenemos que todo dominio ´ıntegro ordenado puede extenderse a un cuerpo ordenado.

36

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

Terminamos este apartado insistiendo en que lo importante en nuestro contexto de los argumentos que acabamos de dar es que todos ellos son demostrables a partir de los axiomas de NBG∗ . Observemos que los resultados que hemos visto sobre formaci´ on de conjuntos nos garantizan que todos los objetos que hemos construido son conjuntos. Por ejemplo, si D es un conjunto, D∗ lo es por ser un subconjunto de D, y D × D∗ lo es porque el producto cartesiano de conjuntos es un conjunto, y KD lo es porque todo cociente de un conjunto es un conjunto, y las operaciones en KD son conjuntos porque son funciones cuyo dominio es un conjunto, etc. En general, todas las construcciones que realizan los matem´ aticos para construir unos conjuntos a partir de otros pueden ser justificadas en NBG. Para las m´ as elementales (como la que acabamos de ver) basta con NBG∗ , aunque otras pueden requerir AP o incluso los axiomas de infinitud y elecci´ on que todav´ıa no hemos presentado. Ideales y anillos cociente Presentamos algunos elementos m´ as de la teor´ıa de anillos que nos ser´ an u ´tiles m´ as adelante: Definici´ on 1.31 Sea A un anillo conmutativo y unitario. Un ideal de A es un conjunto I ⊂ A tal que: a) 0 ∈ I, V b) xy ∈ I x + y ∈ I, V V c) a ∈ A b ∈ I ab ∈ I.

Por ejemplo, si x ∈ A el conjunto (x) = {ax | a ∈ A} de los m´ ultiplos de x es claramente un ideal12 de A. Los ideales de esta forma se llaman ideales principales de A. Tambi´en es claro que {0} y A son ideales de A. El ideal {0} se llama ideal trivial. Un ideal I es propio si I 6= A e I 6= {0}. Observemos que un ideal I cumple I = A si y s´ olo si contiene un elemento inversible, pues si es propio contiene a 1 y, si contiene a un elemento inversible x, entonces contiene a 1 = x−1 x por c) y, dado a ∈ A, tenemos que a = a · 1 ∈ I de nuevo por c). Esto implica que un anillo conmutativo y unitario A es un cuerpo si y s´ olo si no tiene ideales propios. En efecto, si A es un cuerpo, todo ideal no trivial contiene un elemento inversible, luego es impropio. Rec´ıprocamente, si A no es un cuerpo, tiene un elemento no nulo no inversible x, y entonces (x) es un ideal propio (porque si fuera (x) = A tendr´ıamos que 1 ∈ (x), y entonces x ser´ıa inversible). 12 De

hecho, hist´ oricamente el concepto de ideal surgi´ o como una abstracci´ on de los conjuntos de m´ ultiplos, de modo que I puede verse como el conjunto de los m´ ultiplos de un “elemento ideal” de A, que ser´ a un elemento real de A si I es de la forma I = (x).

1.6. Leyes de composici´ on interna

37

Si I es un ideal en un anillo A, definimos la relaci´ on de congruencia m´ odulo I como la relaci´ on en A dada por x ≡ y (m´od I) ↔ x − y ∈ I. Se trata de una relaci´ on de equivalencia: es reflexiva por la propiedad a), es sim´etrica por c) (pues y − x = (−1)(x − y)) y es transitiva por b). Representaremos por A/I el conjunto cociente de A respecto de la congruencia m´ odulo I. El resultado fundamental es el siguiente: Teorema 1.32 Si A es un anillo conmutativo y unitario e I es un ideal de A, entonces A/I se convierte en un anillo conmutativo y unitario con las operaciones dadas por [a] + [b] = [a + b] y [a][b] = [ab]. ´ n: Lo u Demostracio ´nico que no es inmediato es que las operaciones est´ an bien definidas, es decir, que si [a] = [a0 ] y [b] = [b0 ] entonces [a + b] = [a0 + b0 ] y [ab] = [a0 b0 ]. Ahora bien, tenemos que a − a0 = u ∈ I,

b − b0 = v ∈ I,

luego a + b − (a0 + b0 ) = u + v ∈ I y ab − a0 b0 = ab − ab0 + ab0 − a0 b0 = a(b − b0 ) + (a − a0 )b0 = av + ub0 ∈ I. A partir de aqu´ı, cada propiedad de la suma y el producto de A implica trivialmente la propiedad correspondiente en A/I. En vista del teorema anterior, A/I se conoce como el anillo cociente de A determinado por I. Definici´ on 1.33 Un ideal M de un anillo A es maximal si M √ A y no existe ning´ un ideal M √ I √ A. Un ideal P de A es primo si P 6= A y V xy ∈ A (xy ∈ P → x ∈ P ∨ y ∈ P ). Estos conceptos son muy importantes en el estudio de la aritm´etica de un anillo, pero aqu´ı s´ olo necesitaremos el resultado siguiente: Teorema 1.34 Si A es un anillo conmutativo y unitario, entonces un ideal I de A es maximal si y s´ olo si A/I es un cuerpo. A su vez, I es primo si y s´ olo si A/I es un dominio ´ıntegro. ´ n: Si I es maximal, observamos en primer lugar que 1 ∈ Demostracio / I, luego [1] 6= [0], que es uno de los requisitos que debe cumplir A/I para ser cuerpo. Tomemos [x] ∈ A/I tal que [x] 6= 0, lo cual equivale a que x ∈ / I. Es f´ acil ver que J = {u + ax | u ∈ I ∧ a ∈ A}

es un ideal de A que contiene a I y a x, luego I √ J ⊂ A. Por la maximalidad de I tiene que ser J = A, luego 1 ∈ J, luego 1 = u + ax, para cierto u ∈ I y

38

Cap´ıtulo 1. El lenguaje de la teor´ıa de conjuntos

cierto a ∈ A, luego 1 = [1] = [a][x], luego [x] tiene inverso y por lo tanto A/I es un cuerpo. Si A/I es un cuerpo entonces [1] 6= [0], luego 1 ∈ / I, luego I 6= A. Si un ideal cumple I √ J ⊂ A, tomemos x ∈ J \ I, entonces [x] 6= 0, luego existe un a ∈ A tal que [a][x] = [1], luego 1 = ax + u, para cierto u ∈ I, luego 1 ∈ J, luego J = A. Esto prueba que I es maximal. Si I es primo, como el en caso anterior vemos que [1] 6= [0], lo cual es parte de la definici´ on de dominio ´ıntegro. Sean x, y ∈ A tales que [x][y] = [0]. Entonces xy ∈ I, luego x ∈ I o bien y ∈ I, luego [x] = 0 o [y] = 0. Esto prueba que A/I es un dominio ´ıntegro. Rec´ıprocamente, si A/I es un dominio ´ıntegro entonces, como antes, I 6= A, y si xy ∈ I, entonces [x][y] = 0, luego [x] = 0 o bien [y] = 0, luego x ∈ I o bien y ∈ I. Esto prueba que I es primo. En particular, como todo cuerpo es un dominio ´ıntegro, concluimos que todo ideal maximal es primo.

Cap´ıtulo II

Ordinales En el cap´ıtulo precedente hemos presentado el vocabulario b´ asico de la teor´ıa de conjuntos, pero sin presentar realmente ning´ un conjunto “interesante” al que aplicar dicho vocabulario. El lector puede pensar provisionalmente a modo de motivaci´ on que el prop´ osito de este cap´ıtulo es construir los n´ umeros naturales, pero lo cierto es que el proceso de construcci´ on que vamos a presentar nos proporcionar´ a un concepto mucho m´ as potente, el de n´ umero ordinal, de modo que los n´ umeros naturales resultar´ an ser los ordinales finitos. Los ordinales representan el mismo papel respecto a conjuntos arbitrarios que los n´ umeros naturales representan respecto de los conjuntos finitos y, bajo el axioma de regularidad, que presentaremos m´ as adelante, se convierten en el “esqueleto” o el “armaz´ on” de la clase universal V .

2.1

La construcci´ on de los ordinales

Nos marcamos, pues, como objetivo provisional construir los n´ umeros naturales en el seno de NBG∗ . Tienen que ser ciertos conjuntos, de modo que el problema es realmente definir una sucesi´ on de conjuntos a los que podamos llamar 0, 1, 2, 3, etc. Hay una elecci´ on muy natural: como 0 podemos tomar un (el) conjunto con cero elementos, de modo que 0 ≡ ∅, como 1 podemos tomar un conjunto con un elemento, y la elecci´ on m´ as simple es 1 ≡ {0}, como 2 podemos tomar un conjunto con dos elementos, y la elecci´ on m´ as simple es 2 = {0, 1}, y as´ı: 0 1 2 3 4

= ∅, = {0}, = {0, 1}, = {0, 1, 2}, = {0, 1, 2, 3},

6 7 8 9

= {0, 1, 2, 3, 4, 5}, = {0, 1, 2, 3, 4, 5, 6}, = {0, 1, 2, 3, 4, 5, 6, 7}, = {0, 1, 2, 3, 4, 5, 6, 7, 8}, ···

El primer paso para formalizar esta idea es el siguiente:

39

40

Cap´ıtulo 2. Ordinales

Definici´ on 2.1 Llamaremos 0 ≡ ∅ y, para toda clase x, definimos x0 ≡ x ∪ {x}. Definimos 1 ≡ 00 = {0}, 2 ≡ 10 = {0, 1}, 3 ≡ 20 = {0, 1, 2}, etc. El etc´etera final significa que, prosiguiendo del mismo modo, podemos definir el 4 y el 5 y el 10 472, pero por mucho que prolonguemos las definiciones de n´ umeros naturales particulares, eso no nos va a proporcionar una definici´ on de “n´ umero natural”, es decir, una propiedad definida exclusivamente a partir de ∈ y los signos l´ ogicos (o de propiedades definidas previamente a partir de estos signos b´ asicos) que nos permita definir por comprensi´ on la clase de los n´ umeros naturales. Para ello “etc.” resulta inadmisible porque no est´ a definido a partir de ∈ y de los signos l´ ogicos. Presentamos a continuaci´ on una lista de propiedades comunes a todos los n´ umeros naturales que sabemos definir individualmente: Una clase Y es transitiva si cumple V x∈Y x⊂Y V o, equivalentemente (y de aqu´ı el nombre) uv(u ∈ v ∧ v ∈ Y → u ∈ Y ). Y transitiva ≡

Una clase Y es ∈-conexa si cumple V ∈ -conexa Y ≡ uv ∈ Y (u ∈ v ∨ v ∈ u ∨ u = v).

Una clase Y est´ a bien fundada si cumple V W Y bien fundada ≡ X(X ⊂ Y ∧ X 6= ∅ → u ∈ X u ∩ X = ∅).

Un conjunto u que cumpla u ∈ X ∧ u ∩ X = ∅ se llama un ∈-minimal de X, de modo que la buena fundaci´ on afirma que toda subclase no vac´ıa de Y tiene al menos un ∈-minimal. Observemos que u es un ∈-minimal de X si u ∈ X y ning´ un v ∈ u cumple v ∈ X. Ciertamente, los n´ umeros naturales que queremos definir cumplen estas propiedades. Son transitivos, pues, si, por ejemplo, 4 ∈ 7, se cumple tambi´en que 4 = {0, 1, 2, 3} ⊂ {0, 1, 2, 3, 4, 5, 6} = 7, y esto no se cumple casualmente en este ejemplo, sino que vale en todos los casos.1 En cuanto a la conexi´ on, si por ejemplo tomamos 3, 7 ∈ 9, ciertamente se cumple que 3 ∈ 7 y, en general, si tomamos dos elementos distintos de un n´ umero natural, el menor pertenecer´ a al mayor. Por lo tanto, los n´ umeros naturales son ∈-conexos.

1 No vamos a demostrar que todo n´ umero natural es transitivo, en parte porque para ello necesitar´ıamos una definici´ on de n´ umero natural que no tenemos, y en parte porque usaremos la transitividad como parte de la definici´ on de n´ umero natural. Lo mismo vale para las otras dos propiedades que estamos considerando.

2.1. La construcci´ on de los ordinales

41

Tambi´en est´ an bien fundados, pues si tomamos un n´ umero natural, por ejemplo 8 y un subconjunto no vac´ıo, por ejemplo X = {3, 5, 6}, se cumple que X tiene un ∈-minimal, concretamente u = 3, pues ciertamente 3 ∈ X, pero ning´ un v ∈ 3 cumple v ∈ X. De hecho, vemos que cada subconjunto no vac´ıo de un n´ umero natural tiene un u ´nico ∈-minimal, a saber, el m´ınimo n´ umero natural que contiene. El lector debe entender que la cuesti´ on aqu´ı no es demostrar si realmente, lo que hemos constatado con ejemplos particulares vale para todos los n´ umeros naturales, sino m´ as bien si podemos definir un n´ umero natural como un conjunto transitivo, ∈-conexo y bien fundado, o si, por el contrario, existen conjuntos con estas tres propiedades que no tienen nada que ver con los conjuntos 0, 1, 2, . . . , de modo que necesitamos introducir m´ as propiedades para quedarnos u ´nicamente con los n´ umeros naturales. Como respuesta provisional damos una nueva definici´ on: Definici´ on 2.2 Una clase Y es un ordinal si es transitiva, ∈-conexa y bien fundada. Llamaremos Ω a la clase de todos los (conjuntos) ordinales. Observemos que la propiedad “Y es un conjunto y es un ordinal” es normal. El u ´nico punto problem´ atico es la definici´ on de clase bien fundada, que incluye una cuantificaci´ on sobre toda subclase de Y , pero si Y es un conjunto, es lo mismo decir “para toda clase X, si X ⊂ Y · · · ” que decir “para todo conjunto X, si X ⊂ Y · · · ”, porque toda subclase de un conjunto es un conjunto. Por consiguiente Ω ≡ {α | cto α ∧ ordinal α} es una aplicaci´ on v´ alida del axioma de comprensi´ on. As´ı pues, en estos t´erminos la pregunta que nos hac´ıamos es si existen ordinales que no sean (o no deban ser considerados como) n´ umeros naturales. En cualquier caso, lo cierto es que los n´ umeros naturales que pretendemos definir son ordinales, luego al estudiar los ordinales estamos estudiando en particular los n´ umeros naturales, con la diferencia de que los ordinales los tenemos correctamente definidos mediante una propiedad del lenguaje de la teor´ıa de conjuntos. Empezamos observando que, trivialmente, toda subclase de una clase ∈conexa o bien fundada es tambi´en ∈-conexa o bien fundada, pero no podemos decir lo mismo de las clases transitivas (pensemos, por ejemplo, en {3, 5} ⊂ 7). Veamos ahora un resultado t´ecnico sencillo sobre clases bien fundadas: Teorema 2.3 Si x es una clase bien fundada entonces2 x ∈ / x. 2 Quiz´ a el lector se pregunte si es posible que una clase (necesariamente un conjunto) cumpla x ∈ x. Nos falta presentar tres axiomas de NBG, uno de los cuales, el axioma de regularidad, afirma precisamente que toda clase est´ a bien fundada, luego, bajo dicho axioma, no puede darse el caso. No obstante, en su momento discutiremos debidamente la situaci´ on.

42

Cap´ıtulo 2. Ordinales

´ n: Si x ∈ x entonces x es un conjunto y {x} ⊂ x ∧ {x} 6= ∅. Demostracio Sea u un elemento ∈-minimal de {x}. Necesariamente, u = x, pero x ∈ x ∩ {x}, contradicci´ on. Con esto podemos probar: Teorema 2.4 0 ∈ Ω ∧

V x ∈ Ω x0 ∈ Ω.

´ n: Notemos que 0 = ∅ cumple trivialmente las tres condiDemostracio ciones de la definici´ on de ordinal (es transitivo porque no existe ning´ un u ∈ ∅ que pueda incumplir la definici´ on, es ∈-conexo porque no existen u, v ∈ ∅ que puedan incumplir la definici´ on, y est´ a bien fundado porque no existe ning´ un u ⊂ ∅, u 6= ∅ que pueda incumplir la definici´ on). Supongamos ahora que x es un ordinal. Si u ∈ x0 = x ∪ {x}, entonces u ∈ x ∨ u = x, pero en ambos casos u ⊂ x, en el primero porque x es transitivo. Esto prueba que x0 es transitivo. Si u, v ∈ x0 , entonces u ∈ x ∨ u = x y v ∈ x ∨ v = x. Esto nos da cuatro casos: u ∈ x ∧ v ∈ x o bien u ∈ x ∧ v = x, o bien u = x ∧ v ∈ x, o bien u = x = v. En el primero tenemos que u ∈ v ∨ v ∈ u ∨ u = v porque x es ∈-conexo, y en los otros tres tenemos u ∈ v, v ∈ u, u = v respectivamente. Esto prueba que x0 es ∈-conexo. Tomemos u ⊂ x0 ∧ u 6= ∅ y veamos que tiene ∈-minimal. Tratemos aparte el caso en que u = {x}. Entonces v = x es un ∈-minimal de u, pues x∩{x} = ∅. En efecto, si existiera w ∈ x ∩ {x}, ser´ıa x = w ∈ x, en contradicci´ on con el teorema anterior. Como u ⊂ x ∪ {x}, si no se da la igualdad u = {x} es porque u ∩ x 6= ∅, y tenemos as´ı un subconjunto no vac´ıo de x. Como x est´ a bien fundado existe un v ∈ u ∩ x que es ∈-minimal para esta intersecci´ on. Vamos a ver que es ∈-minimal de u. En efecto, si w ∈ v ∩ u, entonces w ∈ x0 , luego w ∈ x ∨ w = x. En el primer caso w ∈ u ∩ x y w ∈ v, lo que contradice que v sea ∈-minimal de u ∩ x. En el segundo caso x = w ∈ v ∈ x, luego, por la transitividad de x, resulta que x ∈ x, en contradicci´ on con el teorema anterior. En vista de este teorema resulta que 0 es un ordinal, luego 1 = 00 es un ordinal, luego 2 = 10 es un ordinal y, en definitiva, todos los n´ umeros naturales son ordinales, pero no podemos demostrar tal cosa porque no tenemos una definici´ on de n´ umero natural. Observemos que los elementos de los n´ umeros naturales (que pretendemos definir) son tambi´en n´ umeros naturales. De momento podemos probar que esto es cierto para ordinales: Teorema 2.5 Los elementos de los ordinales son ordinales.

2.1. La construcci´ on de los ordinales

43

´ n: Sea Y un ordinal y sea x ∈ Y . Por transitividad x ⊂ Y y Demostracio por consiguiente x es conexo y bien fundado. Falta probar que es transitivo, es V decir, que uv(u ∈ v ∧ v ∈ x → u ∈ x). Si u ∈ v ∧ v ∈ x, tenemos v ∈ x ∧ x ∈ Y , y como la clase Y es transitiva, v ∈ Y , e igualmente u ∈ Y . As´ı pues, {u, v, x} ⊂ Y . Como Y est´ a bien fundada se cumplir´ a uno de los tres elementos del subconjunto tiene que ser ∈-minimal, es decir, u ∩ {u, v, x} = ∅ ∨ v ∩ {u, v, x} = ∅ ∨ x ∩ {u, v, x} = ∅, pero u ∈ v ∩ {u, v, x} y v ∈ x ∩ {u, v, x}, luego ha de ser u ∩ {u, v, x} = ∅. Como Y es conexa ha de ser u ∈ x ∨ x ∈ u ∨ u = x, pero si x ∈ u entonces x ∈ u ∩ {u, v, x} = ∅, y si x = u entonces v ∈ u ∩ {u, v, x} = ∅. As´ı pues, se ha de cumplir u ∈ x, como quer´ıamos. En particular vemos que V αβ(α ∈ β ∧ β ∈ Ω → α ∈ Ω),

pero esto es tanto como decir que la clase Ω es transitiva. Nuestra observaci´ on siguiente es que, para los n´ umeros naturales que pretendemos definir, la relaci´ on de orden usual se corresponde con la inclusi´ on, es decir, es lo mismo 3 ≤ 7 que 3 ⊂ 7. Veamos ahora que la inclusi´ on define un buen orden en cualquier ordinal: Teorema 2.6 Si Y es un ordinal, entonces la relaci´ on de inclusi´ on es un buen orden en Y . ´ n: Sea Y un ordinal, y consideramos la relaci´ Demostracio on en Y dada por u ≤ v ↔ u ⊂ v. Sabemos que, en general, se trata de una relaci´ on de orden parcial. Vamos a probar que toda subclase X ⊂ Y no vac´ıa tiene m´ınimo elemento. M´ as concretamente, tomamos un ∈-minimal u ∈ X cualquiera y vamos a ver que es el m´ınimo de X (lo que, en particular, implica que cada subclase no vac´ıa de un ordinal tiene un u ´nico ∈-minimal). Si tomamos cualquier otro v ∈ X, tenemos que u, v ∈ Y , luego por la conexi´ on tiene que ser u ∈ v ∨ v ∈ u ∨ u = v, pero el caso v ∈ u contradice la minimalidad de u, luego nos queda u ∈ v ∨ u = v, y en ambos casos u ⊂ v (en el primero porque v es un ordinal, luego es transitivo). As´ı pues u ≤ v para todo v ∈ X. Esto es lo que significa que u sea el m´ınimo de X. A continuaci´ on notamos que la relaci´ on de orden estricto en los n´ umeros naturales se corresponde con la pertenencia, es decir, que 3 < 7 es lo mismo que 3 ∈ 7. El teorema siguiente demuestra este hecho para ordinales: Teorema 2.7 Si X, Y son ordinales, entonces X ⊂ Y ↔ X ∈ Y ∨ X = Y . ´ n: Una implicaci´ Demostracio on es trivial, pues si X ∈ Y entonces X ⊂ Y por transitividad. Supongamos ahora que X ⊂ Y pero X 6= Y y veamos que X ∈Y.

44

Cap´ıtulo 2. Ordinales

Tenemos que Y \ X 6= ∅, luego por la buena fundaci´ on esta clase tiene un ∈-minimal u ∈ Y \ X. Basta probar que u = X. Si z ∈ u, entonces z ∈ / Y \ X (por la minimalidad de u) y z ∈ Y (por transitividad, pues z ∈ u ∈ Y ), luego z ∈ X. Por lo tanto u ⊂ X. Si z ∈ X, entonces tenemos z, u ∈ Y , luego z ∈ u ∨ u ∈ z ∨ z = u. Si u ∈ z, entonces u ∈ z ∈ X, luego u ∈ X, contradicci´ on (pues u ∈ Y \ X). Si z = u entonces de nuevo u ∈ X, contradicci´ on. Por lo tanto z ∈ u, y as´ı X ⊂ u. En definitiva, tenemos la igualdad u = X. Ahora necesitamos un sencillo resultado t´ecnico: Teorema 2.8 La intersecci´ on de dos ordinales es un ordinal. ´ n: Sean X, Y ordinales. Como X ∩ Y ⊂ X, trivialmente la Demostracio clase X ∩ Y es conexa y bien fundada. Falta ver que es transitiva, pero es cierto en general que la intersecci´ on de clases transitivas es transitiva: Si u ∈ X ∩ Y , entonces u ∈ X ∧ u ∈ Y , u ⊂ X ∧ u ⊂ Y , luego u ⊂ X ∩ Y . De aqu´ı deducimos una propiedad nada trivial: Teorema 2.9 Si X e Y son ordinales, entonces X ∈ Y ∨ Y ∈ X ∨ X = Y . ´ n: X ∩ Y es un ordinal, X ∩ Y ⊂ X y X ∩ Y ⊂ Y . Por el Demostracio teorema 2.7 tenemos (X ∩ Y ∈ X ∨ X ∩ Y = X) ∧ (X ∩ Y ∈ Y ∨ X ∩ Y = Y ). Esto nos da cuatro casos: (X ∩ Y ∈ X ∧ X ∩ Y ∈ Y ) ∨ (X ∩ Y ∈ X ∧ X ∩ Y = Y ) ∨ (X ∩ Y = X ∧ X ∩ Y ∈ Y ) ∨ (X ∩ Y = X ∧ X ∩ Y = Y ), o sea X ∩ Y ∈ X ∩ Y ∨ Y ∈ X descarta por el teorema 2.3.

∨ X∈Y

∨ X = Y . El primer caso se

Notemos que, en principio, la definici´ on de ordinal dice que dos elementos de un mismo ordinal est´ an conectados por la relaci´ on de pertenencia, pero lo que acabamos de probar es que dos ordinales cualesquiera, que en principio no tienen ninguna relaci´ on entre s´ı, tambi´en est´ an conectados por la relaci´ on de pertenencia, y uno tiene que ser un elemento del otro salvo que sean el mismo. En particular, V αβ ∈ Ω (α ∈ β ∨ β ∈ α ∨ α = β), luego la clase Ω es ∈-conexa (y ya hab´ıamos probado que era transitiva). De hecho, se cumple algo m´ as fuerte: Teorema 2.10 Ω es un ordinal. ´ n: Ya hemos probado que Ω es transitiva y ∈-conexa. S´ Demostracio olo falta probar que est´ a bien fundada. Para ello tomamos una clase X ⊂ Ω no vac´ıa, y vamos a encontrarle un ∈-minimal. Tomemos cualquier u ∈ X. Si ya

2.1. La construcci´ on de los ordinales

45

es un ∈-minimal, no hay nada que probar. En caso contrario u ∩ X 6= ∅ y u ∩ X ⊂ u. Como u ∈ Ω, es un ordinal y est´ a bien fundado, luego u ∩ X tiene un ∈-minimal v, es decir, v ∈ u ∩ X y v ∩ u ∩ X = ∅. Ahora bien, como v ∈ u, por transitividad v ⊂ u, de donde concluimos que v ∩ X = v ∩ u ∩ X = ∅. Adem´ as v ∈ X, luego v es un ∈-minimal de X. Con esto termina el “trabajo duro” de la construcci´ on de los ordinales, y podemos empezar a extraer consecuencias: Teorema 2.11 Ω es una clase propia. ´ n: Si Ω fuera un conjunto, puesto que es un ordinal, tendr´ıamos Demostracio que Ω ∈ Ω, en contradicci´ on con el teorema 2.3. As´ı pues, la clase de todos los (conjuntos) ordinales es un ordinal que no es un conjunto. Seguidamente probamos que es el u ´nico caso: Teorema 2.12 Si Y es un ordinal, o bien Y ∈ Ω, o bien Y = Ω. ´ n: Basta aplicar el teorema 2.9, que nos da en principio las Demostracio opciones Y ∈ Ω ∨ Ω ∈ Y ∨ Y = Ω, pero la segunda es imposible, pues implica que Ω es un conjunto. Definici´ on 2.13 Llamaremos n´ umeros ordinales a los elementos de Ω, es decir, a los conjuntos que son ordinales. En lo sucesivo usaremos letras V griegas W min´ usculas para referirnos a los n´ u meros ordinales, de modo que α o α V W deber´ a entenderse como α ∈ Ω o α ∈ Ω, respectivamente. Llamaremos ≤ a la inclusi´ on en Ω, de modo que, seg´ un el teorema 2.6, sabemos que (Ω, ≤) es una clase bien ordenada. As´ı pues, α ≤ β es equivalente a α ⊂ β.

El teorema 2.7 implica que la relaci´ on de orden estricto asociada a ≤ es equivalente a la pertenencia, es decir, que α < β es equivalente a α ∈ β. (Aqu´ı hay que tener en cuenta que no puede suceder a un tiempo α ∈ β y α = β, pues entonces tendr´ıamos α ∈ α.) El teorema siguiente recoge los hechos b´ asicos sobre el buen orden de los ordinales: Teorema 2.14 Se cumple: a) 0 es el m´ınimo ordinal. b) Si α es un ordinal, entonces α0 tambi´en lo es, y es el m´ınimo ordinal V mayor que α (es decir, β ∈ Ω (α < β → α0 ≤ β). S c) Todo conjunto de ordinales A ⊂ Ω tiene supremo σ = A.

46

Cap´ıtulo 2. Ordinales

´ n: a) ya hemos probado que 0 es un ordinal, y es el m´ınimo Demostracio porque el conjunto vac´ıo est´ a contenido en cualquier conjunto. b) Ya hemos probado que α0 ∈ Ω. Si α < β entonces α ∈ β, luego α ⊂ β, luego α0 = α ∪ {α} ⊂ β, luego α0 ≤ β. c) Como todo α ∈ A est´ a contenido en Ω, es claro que σ ⊂ Ω, luego es un conjunto conexo y bien fundado. Hemos de probar que es transitivo, pero si β ∈ σ, entonces existe un α ∈ A tal que β ∈ α, luego por la transitividad de α es β ⊂ α ⊂ σ. Por consiguiente σ ∈ Ω. Teniendo en cuenta que el orden es la inclusi´ on, es inmediato que σ es el supremo de A. Volvemos ahora a la cuesti´ on de si hay ordinales que no sean n´ umeros naturales (aparte de Ω). Para ello introducimos los conceptos siguientes: W Definici´ on 2.15 Un ordinal α ∈ Ω es un ordinal sucesor si β < α α = β 0 , y es un ordinal l´ımite si no es 0 ni un ordinal sucesor, es decir, si cumple V α l´ımite ≡ 0 ∈ α ∧ δ ∈ α δ 0 ∈ α.

Trivialmente entonces, todo α ∈ Ω est´ a en uno (y s´ olo uno) de los tres casos siguientes: o bien es α = 0, o bien es un ordinal sucesor, o bien es un ordinal V l´ımite. W Usaremos la letra λ para referirnos a ordinales l´ımite, de modo que λ y λ significar´ an, respectivamente, “para todo ordinal l´ımite λ” y “existe un ordinal l´ımite λ”. Ahora bien, ¿existen ordinales l´ımite? Ciertamente, los n´ umeros naturales distintos de 0 son ordinales sucesores, luego la existencia de un ordinal l´ımite implica la existencia de un n´ umero ordinal que no es un n´ umero natural. Antes de entrar en este asunto observamos que ya podemos cumplir el objetivo que nos hab´ıamos marcado: Definici´ on 2.16 Diremos que un conjunto n es un n´ umero natural si V W n ∈ Ω ∧ m ∈ Ω(m ≤ n → m = 0 ∨ r ∈ m m = r0 ). Llamaremos ω a la clase de todos los n´ umeros naturales.

As´ı pues, hemos definido un n´ umero natural como un ordinal tal que los ordinales no nulos menores o iguales son todos sucesores. Enseguida discutiremos si la definici´ on es razonable, pero antes observamos lo siguiente: Teorema 2.17 ω es un ordinal. ´ n: Como ω ⊂ Ω, es trivialmente una clase ∈-conexa y bien Demostracio fundada, y basta ver que es transitiva. Si u ∈ v ∧ v ∈ ω, entonces v es un n´ umero natural y u es un ordinal u < v, luego todos los ordinales no nulos m ≤ u son ordinales no nulos m ≤ v, luego, al ser v un n´ umero natural, todos ellos son sucesores, lo que significa que u tambi´en es un n´ umero natural, luego u ∈ ω. Nuestra definici´ on de n´ umero natural est´ a justificada por el teorema siguiente:

2.1. La construcci´ on de los ordinales

47

Teorema 2.18 (Axiomas de Peano) Se cumple: 1) 0 ∈ ω, V 2) n ∈ ω n0 ∈ ω, V 3) n ∈ ω n0 6= 0, V 4) mn ∈ ω (m0 = n0 → m = n), V V 5) A(A ⊂ ω ∧ 0 ∈ A ∧ n ∈ A n0 ∈ A → A = ω). ´ n: 1) es trivial. Demostracio

2) Si n ∈ ω y α ≤ n0 , entonces, o bien α ∈ n0 o bien α = n0 . En el primer W caso α ≤ n, luego α = 0 ∨ β ∈ α α = β 0 , porque n ∈ ω. Esto tambi´en se cumple en el segundo caso, tomando β = n. Por consiguiente n0 ∈ ω. Las propiedades 3) y 4) son trivialmente v´ alidas para ordinales cualesquiera, pues 0 ≤ n < n0 , luego 0 ∈ n0 , luego n0 6= 0. Por otra parte, si m0 = n0 , tiene que ser m = n, ya que si fuera m < n entonces m0 ≤ n < n0 , luego m0 6= n0 , e igualmente si n < m. V 5) Si A ⊂ ω ∧ 0 ∈ A ∧ n ∈ A n0 ∈ A pero A 6= ω, entonces, como hemos probado que Ω es un ordinal, existe un ∈-minimal n ∈ ω \ A. No puede ser n = 0, pues 0 ∈ A, n ∈ / A. Como n es un n´ umero natural, por definici´ on existe un m ∈ n tal que n = m0 . Como n es minimal, no puede ser que m ∈ ω \ A, pues entonces m ∈ n ∩ (ω \ A). Por lo tanto m ∈ A (notemos que m ∈ n ∈ ω, luego m ∈ ω, por transitividad). Pero estamos suponiendo que m ∈ A implica n = m0 ∈ A, contradicci´ on. Est´ a claro que los axiomas de Peano son propiedades que los matem´ aticos usan cuando tratan con n´ umeros naturales, luego cualquier definici´ on de n´ umero natural aceptable para un matem´ atico debe dar lugar a un conjunto (o, al menos, a una clase) que, con un cero y una operaci´ on “siguiente” definidos adecuadamente satisfaga los axiomas de Peano. En la secci´ on siguiente (teorema 2.24) demostraremos que los elementos de cualquier clase que satisfaga los axiomas de Peano se corresponden biun´ıvocamente con los n´ umeros naturales que hemos definido, de modo que dos definiciones alternativas de los n´ umeros naturales (aceptables, en cuanto que cumplan los axiomas de Peano) corresponden simplemente a elecciones distintas de los conjuntos concretos con los que estamos representando cada n´ umero natural. Por ejemplo, en lugar de haber tomado 0 = ∅, 1 = {0}, 2 = {0, 1}, 3 = {0, 1, 2}, etc., podr´ıamos haber optado por 0 = ∅, 1 = {0}, 2 = {1}, 3 = {2}, etc. y as´ı tendr´ıamos otra clase de n´ umeros naturales, distinta, pero equivalente a la que hemos elegido. El hecho de que ω sea un ordinal s´ olo nos deja dos posibilidades: o bien ω = Ω, en cuyo caso no hay m´ as ordinales que los n´ umeros naturales y Ω y no existen ordinales l´ımite, o bien ω ∈ Ω, en cuyo caso ω es un ordinal l´ımite, por el segundo axioma de Peano. M´ as precisamente:

48

Cap´ıtulo 2. Ordinales

Teorema 2.19 Las afirmaciones siguientes son equivalentes: W V a) x(cto x ∧ 0 ∈ x ∧ u ∈ x u0 ∈ x), b) cto ω,

c) ω ∈ Ω, d) ω es un ordinal l´ımite, e) Existe un ordinal l´ımite. ´ n: Si x es un conjunto que cumple a), entonces y = x ∩ ω Demostracio est´ a en las condiciones del quinto axioma de Peano, que nos da que x ∩ ω = ω, es decir, que ω ⊂ x, luego ω es un conjunto y tenemos b). A su vez, b) implica trivialmente c), que a su vez implica d), por el segundo axioma de peano. Obviamente d) implica e), y un ordinal l´ımite cumple lo requerido para x en a). Las afirmaciones del teorema anterior no pueden demostrarse a partir de los axiomas que hemos considerado hasta ahora, lo que nos lleva a un nuevo axioma: Axioma de infinitud (AI) cto ω. Naturalmente, cualquiera de las afirmaciones del teorema anterior sirve como versi´ on alternativa del axioma de infinitud. De momento seguiremos trabajando en NBG∗ , es decir, sin suponer AP o AI salvo que lo indiquemos expl´ıcitamente.

2.2

Inducci´ on y recursi´ on transfinita

Los ordinales son una poderosa herramienta fundamental en el estudio de los conjuntos gracias a los teoremas que vamos a demostrar en esta secci´ on. Empezamos con el principio de inducci´ on, que no es sino un caso particular del teorema 1.24: Teorema 2.20 (Inducci´ on transfinita) V V A( α(α ⊂ A → α ∈ A) → Ω ⊂ A).

Es decir: si bajo la hip´ otesis de inducci´ on de que todos los ordinales β < α pertenecen a una clase A podemos probar que α ∈ A, entonces todo n´ umero ordinal est´ a en A. La prueba es la misma que la de 1.24: ´ n: Si no se cumpliera Ω ⊂ A, entonces Ω \ A 6= ∅, y debe Demostracio existir un m´ınimo elemento α ∈ Ω \ A, pero esto significa que todo ordinal menor que α est´ a en A, es decir, α ⊂ A, luego la hip´ otesis nos da que α ∈ A, contradicci´ on. En la pr´ actica aplicaremos este teorema a clases de la forma A = {α ∈ Ω | φ(α)},

2.2. Inducci´ on y recursi´ on transfinita

49

para cierta propiedad (normal) φ(x), de modo que lo que estamos afirmando es que si el hecho de que todos los ordinales menores que un α tienen la propiedad φ implica que α tambi´en la tiene, entonces todos los n´ umeros ordinales tienen la propiedad φ. A menudo el planteamiento de la inducci´ on se simplifica si distinguimos casos seg´ un si α = 0 (en cuyo caso la hip´ otesis de inducci´ on es vac´ıa), si α es un sucesor (en cuyo caso a menudo basta aplicar la hip´ otesis de inducci´ on a su anterior) o si es un l´ımite. Esto nos lleva al enunciado siguiente: Teorema 2.21 (Inducci´ on transfinita) V V A(0 ∈ A ∧ α(α ∈ A → α0 ∈ A) V V ∧ λ( δ(δ < λ → δ ∈ A) → λ ∈ A) → Ω ⊂ A).

En otras palabras, una forma alternativa de probar que todos los ordinales tienen una propiedad (cosa que puede expresarse como la pertenencia a una clase A) es probar que 0 la tiene, que si un ordinal α la tiene entonces tambi´en la tiene α0 , y que si todos los ordinales menores que un l´ımite λ la tienen, tambi´en la tiene λ. La prueba sigue el mismo argumento: si no fuera Ω ⊂ A la clase Ω\A deber´ıa tener un m´ınimo elemento β, pero no puede ser β = 0 por la primera parte de la hip´ otesis, ni β = α0 por la segunda (porque α < β estar´ıa en A y entonces β tambi´en deber´ıa cumplir β ∈ A) ni puede ser un l´ımite por la tercera, luego tenemos una contradicci´ on. Vemos as´ı que los resultados de inducci´ on son poco menos que triviales. La parte delicada es demostrar el teorema de recursi´ on transfinita. Se trata de probar que para definir una funci´ on F : Ω −→ A podemos definir F (α) suponiendo que F ya est´ a definida para los ordinales menores que α, es decir, usando los valores F (δ) con δ < α para definir F (α) o, m´ as precisamente, usando F |α para definir F (α). Con exactitud: Teorema 2.22 (Recursi´ on transfinita) Sea A una clase cualquiera, sea W X ≡ {f | α f : α −→ A}

y sea G : X −→ ´nica funci´ on F : Ω −→ A caracteriV A. Entonces existe una u zada por que α F (α) = G(F |α ).

´ n: Diremos que f : β −→ A es una β-aproximaci´ Demostracio on si para todo α < β se cumple f (α) = G(f |α ). Es claro que si existe una β-aproximaci´ on entonces es u ´nica. En efecto, supongamos que f y g son dos β-aproximaciones. Entonces sea α < β el m´ınimo ordinal en el que difieran (si es que existe). Esto significa que f |α = g|α , pero que f (α) 6= g(α). Ahora bien, esto es absurdo, pues f (α) = G(f |α ) = G(g|α ) = g(α). Ahora veamos por inducci´ on que existen β-aproximaciones para todo β.

50

Cap´ıtulo 2. Ordinales

Es claro que ∅ es trivialmente una 0-aproximaci´ on. Si f : α −→ A es una αaproximaci´ on, entonces g = f ∪ {(α, G(f ))} es una α0 -aproximaci´ on. En efecto, tenemos que g : α0 −→ A y si β < α0 , o bien β < α, en cuyo caso g(β) = f (β) = G(f |β ) = G(g|β ), o bien β = α, en cuyo caso g(β) = G(f ) = G(g|β ). Finalmente, supongamos que existen δ-aproximaciones para todo δ < λ y veamos que existe una λ-aproximaci´ on. Por la unicidad que hemos probado, para cada δ < λ existe una u ´nica δaproximaci´ on, a la que podemos dar nombre. Definimos: fδ ≡ f |f es una δ-aproximaci´ on,

y as´ı

V δ(δ < λ → fδ es una δ-aproximaci´ on).

De la definici´ on se sigue inmediatamente que si δ < ≤ < λ entonces f≤ |δ es una δ-aproximaci´ on, luego la unicidad implica que f≤ |δ = fδ . Esto implica que f=

S

fδ : λ −→ A,

δ