Lewin-teoria Conjuntos

TEORIA AXIOMATICA DE CONJUNTOS Versi´ on Preliminar Renato A. Lewin Author address: ´ lica de Chile, Facultad de Pontificia Universidad Cato ´ ticas, Casilla 306 - Correo 22, Santiago CHILE. Matema e-mail: [email protected]

Indice CAPITULO 1. Introducci´on. Los Axiomas de Zermelo Fraenkel 1. El Lenguaje Formalizado L 2. Los Axiomas de la Teor´ıa ZF. Conceptos Fundamentales CAPITULO 2. Teor´ıa Elemental 1. Operaciones 2. Relaciones 3. Funciones 4. Relaciones de Equivalencia 5. Relaciones de Orden

5 7 9 17 17 23 30 40 44

CAPITULO 3. Ordinales 1. N´ umeros Naturales 2. Ordinales 3. Inducci´on Transfinita 4. Recursi´on 5. Funciones Normales 6. Ordinales y Buenos Ordenes 7. Aritm´etica Ordinal 8. La Jerarqu´ıa Acumulativa de Conjuntos

57 57 64 70 72 75 78 80 101

CAPITULO 4. El Axioma de Elecci´on 1. Equivalencias del Axioma de Elecci´on 2. Aplicaciones

105 105 111

CAPITULO 5. Cardinales 1. Definiciones y Resultados B´asicos 2. Conjuntos Finitos y Conjuntos Infinitos 3. Aritm´etica Cardinal 4. Cardinales Regulares y Singulares 5. La Hip´otesis del Continuo

117 117 125 129 144 146

Bibliograf´ıa

151

Glosario

153

3

4

CAPITULO 1

Introducci´ on. Los Axiomas de Zermelo Fraenkel Este libro trata sobre los conjuntos. Intuitivamente un conjunto es una colecci´on (clase, agregado, conglomerado, etc.) de objetos, los que pertenecen a (forman parte de, son los elementos de, etc.) el conjunto. En toda teor´ıa axiom´atica debemos partir de t´erminos que no podemos definir para no correr el riesgo de caer en un c´ırculo vicioso. Tal es el caso de los conceptos de conjunto y pertenencia dentro de la Teor´ıa de Conjuntos. Todas nuestras intuiciones descansan sobre la idea intuitiva que tengamos sobre estos conceptos primitivos, sin embargo, para el desarrollo de la teor´ıa no es necesario contar con estas intuiciones. Una teor´ıa axiom´atica es un modelo formal de una realidad que queremos estudiar. Est´a compuesta por axiomas, o sea, oraciones a partir de las cuales, usando s´olo reglas l´ogicas, podamos obtener todas las propiedades de aquello que queremos modelar. Los axiomas tratan de establecer las caracter´ısticas y propiedades esenciales de los objetos que estamos tratando de describir en nuestro modelo. El ideal ser´ıa en primer lugar que los axiomas modelaran las intuiciones que tenemos de la realidad y en segundo lugar que la lista fuera completa, es decir, que todas y s´olo aquellas propiedades de los objetos a describir se puedan obtener a partir de nuestra lista. Diversas teor´ıas axiom´aticas de conjuntos han logrado en mayor o menor grado el segundo de estos objetivos. El primero en cambio, obtener todas las propiedades de los conjuntos a partir de un sistema de axiomas, no se ha logrado. El motivo de ´esto es muy sencillo: no se puede. En efecto, los resultados obtenidos por el l´ogico Kurt G¨odel alrededor de 1930, demuestran que es imposible dar una axiomatizaci´on completa de la Teor´ıa de Conjuntos. Lo mismo es cierto de otras teor´ıas matem´aticas como la teor´ıa de n´ umeros. Lo anterior parece condenar nuestro proyecto al fracaso, sin embargo ´esto no es as´ı, s´olo nos advierte que el ideal es imposible. De hecho numerosos matem´aticos han logrado establecer teor´ıas axiom´aticas que, si bien no completas, son suficientes para construir en ellas casi toda la matem´atica. Estudiaremos una de ellas en estas p´aginas, a saber, la teor´ıa de Zermelo–Fraenckel, ZF, desarrollada a partir del 5

trabajo de E. Zermelo el primero en proponer una teor´ıa en los primeros a˜ nos de este siglo. Un conjunto est´a definido por los objetos que contiene. Nuestra intuici´on nos dice que a cada conjunto corresponde una propiedad, es decir, aquello que caracteriza a sus elementos, por ejemplo al conjunto formado por los n´ umeros 1, 2, . . . , 99, le corresponde la propiedad “ser n´ umero entero mayor que cero y menor que cien”. A la inversa, a toda propiedad le debe corresponder un conjunto, la colecci´on de todos los objetos que verifican dicha propiedad. Temprano en el desarrollo de la teor´ıa de conjuntos se descubri´o que esta intuici´on conduc´ıa a contradicciones y que deb´ıa descartarse. A fines del siglo pasado, el matem´atico ingl´es Bertrand Russell di´o con la siguiente paradoja. Consideremos el conjunto R definido por la propiedad “un objeto pertenece al conjunto R si y s´olo si no pertenece a si mismo”. En s´ımbolos1 R = {x : x 6∈ x}. La pregunta entonces es ¿pertenece R a R?, o en s´ımbolos, ¿R ∈ R?. Si la respuesta es afirmativa, entonces R verifica la propiedad que define a R, o sea, R 6∈ R. Si la respuesta es negativa, entonces, por definici´on, R ∈ R. En cualquier caso obtenemos la contradicci´on R ∈ R ↔ R 6∈ R . La paradoja de Russell (y otras) nos dice que el concepto de “propiedad”es m´as delicado de lo que suponemos y que definitivamente no debe corresponder a lo que llamamos un conjunto. Debemos tomar medidas para evitar que esta paradoja y ninguna otra se produzca en nuestra teor´ıa. Sin embargo, la noci´on de que a cada propiedad deber´ıa corresponder la colecci´on de objetos que la verifican o “extensi´on”de la propiedad, tiene fuerte arraigo en nuestra intuici´on. Algunos matem´aticos no han querido deshacerse de ella y han elaborado teor´ıas bastante complejas, que incluyen dos tipos de objetos, conjuntos y clases propias. Deciamos antes que lo que caracteriza a los conjuntos es sus elementos y por ende para poder afirmar que algo es un conjunto, es preciso ser capaz de determinar exactamente cuales son los elementos de dicho conjunto. Las clases son las extensiones de propiedades. Si ´esta pertenece a otra clase, entonces decimos que es un conjunto, si no, hablamos de 1

Supondremos que el lector est´a familiarizado con la terminolog´ıa y simbolog´ıa conjuntista pero lo prevenimos de que estos tendr´an un sentido muy preciso en nuestra teor´ıa y el que, a veces, difiere del popularizado en la ense˜ nanza b´asica y media. 6

una clase propia. Es decir, las clases propias son las extensiones de una propiedad que de alguna manera son “demasiado grandes”, no las podemos aprehender. Ejemplos de estas u ´ltimas son la clase R definida anteriormente o la clase V formada por todos los conjuntos (o clase universal). En nuestra teor´ıa, ZF, no existen las clases propias, s´olo conjuntos. Esto implica que, por ejemplo, no podemos hablar de la clase R. Sin embargo, la situaci´on no es tan mala como parece. Si bien no podemos hablar de R, nada nos impide hablar de la propiedad x 6∈ x. As´ı, aunque no podemos afirmar “a ∈ R00 (porque R no existe dentro de la teor´ıa), podemos perfectamente decir a 6∈ a que significa lo mismo. En otras palabras, si queremos hablar de una clase propia, en ZFdebemos hacerlo mediante la propiedad que la define. La noci´on de “propiedad” no la hemos definido pero de lo anterior se desprende que es central en nuestro estudio. Vamos a continuaci´on a definir este concepto. Como dijimos, una teor´ıa axiom´atica se desarrolla a partir de ciertos enunciados o axiomas mediante la aplicaci´on de reglas l´ogicas. Por ello, es fundamental que el lenguaje usado sea lo m´as preciso posible. Esto se logra mediante la formalizaci´on del lenguaje. S´olo aquellas expresiones escritas en ´este ser´an aceptables en nuestra teor´ıa y representaran propiedades. No es el prop´osito de este texto introducir al lector a la L´ogica Matem´atica. Tampoco suponemos que ´este sepa l´ogica m´as all´a de los conocimientos que se aprende en un curso universitario de Introducci´on al Algebra o similar. Cierta madurez matem´atica es desde luego necesaria para mantener la fluidez de las demostraciones. Usaremos por lo tanto un estilo semi formal el que, por un lado, es habitual en el tema y por el otro, no apabulla al lector con un rigor tedioso y excesivo. 1. El Lenguaje Formalizado L Un lenguaje formalizado est´a constituido por un conjunto de s´ımbolos b´asicos y por reglas que nos permiten formar expresiones m´as complicadas a partir de esos s´ımbolos originales. Los s´ımbolos de L ser´an: 1. Variables: x, y, z, X, Y, Z, x1 , x2 , . . . , en general, las u ´ltimas letras del alfabeto latino, min´ usculas o may´ usculas, con o sin sub´ındices. Su significado es el habitual en matem´aticas y su rango son los conjuntos. 2. Constantes: a, b, c, A, B, C, . . . , en general, las primeras letras del alfabeto latino. Sirven para referirnos a conjuntos espec´ıficos. 7

3. S´ımbolo de pertenencia: ∈ 4. S´ımbolo de igualdad: = 5. Conectivos l´ogicos: ¬, ∨, ∧, →, ↔, es decir, los s´ımbolos habituales para la negaci´on, disyunci´on, conjunci´on, implicaci´on y equivalencia. 6. Cuantificadores: ∀, ∃, con su significado habitual. 7. Par´entesis: ( , ). Usados como signos de puntuaci´on. Cualquier cadena finita formada por estos s´ımbolos es una expresi´ on del lenguaje, pero no toda expresi´on es aceptable o significativa. S´olo aceptaremos aquellas a las que llamaremos f´ormulas de L. Una f´ormula de L es una expresi´on de L construida como sigue: 1. X ∈ Y, X = Y son f´ormulas de L para cualquiera dos variables o constantes X e Y no necesariamente distintas. La primera se lee X pertenece a Y o bien Y contiene a X y la segunda X es igual a Y . Su significado intuitivo es el obvio. Estas se llamar´an f´ ormulas at´omicas. 2. Si ϕ y ψ son f´ormulas de L , entonces tambi´en lo son (ϕ ∨ ψ), (ϕ ∧ ψ), (ϕ → ψ), (ϕ ↔ ψ). Estas f´ormulas corresponden respectivamente a la disyunci´on, conjunci´on, implicaci´on y equivalencia de ϕ y ψ. 3. Si ϕ es una f´ormula de L , entonces ¬ϕ tambi´en es una f´ormula de L . La f´ormula ¬ϕ corresponde a la negaci´on de ϕ . Tambi´en usaremos los s´ımbolos auxiliares X ∈ / Y y X 6= Y para escribir ¬(X ∈ Y ) y ¬(X = Y ), respectivamente. 4. Si ϕ es una f´ormula de L y x es una variable, ∀xϕ, ∃xϕ son f´ormulas de L . Estas se leen cualquier conjunto x verifica ϕ y existe (por lo menos) un conjunto x que verifica ϕ , respectivamente. Su significado es tambi´en evidente.

Solamente aquellas expresiones obtenidas por la aplicaci´on de (un n´ umero finito de) estas reglas es una f´ormula de L . Si ϕ es una f´ormula de L y x una variable que aparece en ϕ , decimos que x aparece ligada en ϕ si su aparici´on se produce bajo la influencia de un cuantificador ∀x o ∃x. En caso contrario decimos que x aparece libre en ϕ . Por ejemplo, en ∀x x 6∈ y, la variable x aparece ligada pero y aparece libre y en ∃x(x ∈ y ∨ ∀z x ∈ z), las variables x y z aparecen ligadas e y aparece libre. Una f´ormula que no contiene variables libres se llama una oraci´ on. Una oraci´on de L es siempre verdadera o falsa (¡pero puede ser que no 8

seamos capaces de determinar cu´al de las dos se cumple!). Una oraci´on hace una afirmaci´on acerca de los conjuntos a los que se refiere, una f´ormula que contiene variables libres no hace ninguna afirmaci´on, pero si asignamos interpretaciones a sus variables libres, entonces s´ı estaremos afirmando algo. A menudo escribiremos ϕ(x1 , x2 , . . . , xn ) para dejar en claro que las variables libres de ϕ est´an entre x1 , x2 , . . . , xn . Como hemos dicho, s´olo aceptaremos f´ormulas de L para hablar de objetos y hacer afirmaciones en ZF. Sin embargo, la expresi´on en L de conceptos bastante sencillos puede resultar increiblemente complicada. As´ı, aceptaremos abreviaciones que faciliten la lectura. Por ejemplo el concepto de subconjunto se denota x ⊆ y se puede expresar en terminos de los s´ımbolos b´asicos de L mediante: x⊆y

ssi ∀z(z ∈ x → z ∈ y).

Entonces, como ya sabemos que x ⊆ y puede escribirse en el lenguaje L, permitiremos el s´ımbolo ⊆ en nuestras f´ormulas. Lo mismo suceder´a con otros s´ımbolos. M´as a´ un, en general usaremos expresiones del castellano y no su formalizaci´on en L para trabajar con el concepto intuitivo y no con la a menudo ilegible f´ormula de L . Lo importante es que dicha traducci´on sea posible para que, llegado el caso, podamos hacer una demostraci´on rigurosa de nuestras afirmaciones. 2. Los Axiomas de la Teor´ıa ZF. Conceptos Fundamentales A1. Axioma de Extensionalidad: “Si todo elemento de X es un elemento de Y y todo elemento de Y es un elemento de X , entonces X es igual a Y ”. Dicho de otro modo, si dos conjuntos tienen los mismos elementos, entonces son iguales. Este axioma nos dice que lo que caracteriza a un conjunto son sus elementos. En L , este axioma se escribe ∀X∀Y (∀z(z ∈ X ↔ z ∈ Y ) → X = Y ). ´ n 1.1. Decimos que X es subconjunto de Y , en s´ımbolos, Definicio X ⊆ Y , si y s´olo si todo elemento de X es un elemento de Y . O sea, X ⊆ Y ↔ ∀x(x ∈ X → x ∈ Y ). Con esta definici´on A1 puede escribirse m´as abreviadamente ∀X∀Y (X ⊆ Y ∧ Y ⊆ X → X = Y ). A2. Axioma del conjunto vac´ıo: “Existe un conjunto que no contiene ning´ un elemento”. 9

En L escribimos

∃X∀x x 6∈ X. Observemos que, en particular, este axioma garantiza que existe al menos un conjunto. Lema 1.1. Existe un u ´nico conjunto que no contiene ning´ un elemento. ´ n. Supongamos que existen dos conjuntos distintos Demostracio a y b ambos sin elementos. Por A1 ∃x((x ∈ a ∧ x 6∈ b) ∨ (x ∈ b ∧ x 6∈ a)), una contradicci´on. Luego hay un u ´nico conjunto vac´ıo. ´ n 1.2. El (´ Definicio unico) conjunto que no tiene elementos se llama el conjunto vac´ıo y se le denota ∅ . Obs´ervese que el s´ımbolo ∅ no es la letra griega ϕ . A3. Axioma de Separaci´ on: “Si ϕ(x) es una f´ormula de L y X es un conjunto, entonces existe un conjunto Y cuyos elementos son aquellos elementos de X que verifican ϕ(x)”. En L escribimos ∀X∃Y ∀z(z ∈ Y ↔ (z ∈ X ∧ ϕ(x)). Este axioma nos dice que para cualquier propiedad (expresada por ϕ(x)) y cualquier conjunto A existe el subconjunto de A formado por los elementos que verifican esa propiedad. Obviamente este conjunto es u ´nico. ´ n 1.3. Si ϕ(x) es una f´ormula de L y A un conjunto, Definicio el conjunto cuya existencia est´a garantizada por A3 se denotar´a con el s´ımbolo {x ∈ A : ϕ(x)} y se lee “el conjunto de los elementos de A tales que ϕ(x)”. Recordemos que la paradoja de Russell se produce al tratar de construir el conjunto de todos los conjuntos que verifican una propiedad cualquiera ϕ(x). Este axioma limita nuestra capacidad de formar conjuntos de objetos que verifican una cierta propiedad, s´olo podemos referirnos a aquellos elementos que perteneciendo a un cierto conjunto dado, verifican la propiedad en cuesti´on. Veamos que esta restricci´on evita que se produzca la paradoja. Para ello tratemos de formar la clase de Russell. Dado un conjunto A , el axioma de extensionalidad nos permite formar el conjunto R = {x ∈ A : x 6∈ x}. 10

En este caso tenemos que si R ∈ R, entonces R∈A

y

R 6∈ R,

lo cual es una contradicci´on, luego R ∈ / R, lo que, a diferencia de antes, no es contradictorio, s´olo implica que R ∈ / A. Teorema 1.2. No existe el conjunto de todos los conjuntos. ´ n. Supongamos que si existe y llamemoslo V . EnDemostracio tonces en virtud de A3 podemos construir el conjunto de Russell R = {x ∈ V : x 6∈ x}, contradicci´on. Por u ´ltimo, cabe destacar que este no es propiamente un axioma sino m´as bien un esquema. En efecto, para cada f´ormula ϕ(x) de L tenemos un axioma distinto, o sea, hay una cantidad ilimitada de instancias de este axioma. A4. Axioma de Pares: “Dados dos conjuntos X e Y , existe un conjunto cuyos u ´nicos elementos son X e Y ”. Su expresi´on en L es ∀X∀Y ∃Z ∀x(x ∈ Z ↔ (x = X ∨ x = Y )). Resulta claro por A1 que este conjunto es u ´nico. Lo denotamos {X, Y }. y lo llamamos el par no–ordenado X, Y . El axioma A1 tambi´en garantiza la existencia del conjunto cuyo u ´nico elemento es el conjunto X {X, X} = {X}, el que a menudo recibe el nombre de singleton X . A5. Axioma de Uniones: “Si X es un conjunto, entonces existe un conjunto cuyos elementos son los elementos de los elementos de X ”. En L escribimos ∀X ∃Y ∀z(z ∈ Y ↔ ∃u(z ∈ u ∧ u ∈ X)). Nuevamente por ´nico, se llama la uni´ on de S A1, este conjunto es u X y se le denota X. 11

Un caso particular que merece una notaci´onSespecial es el siguiente. Si X e Y son conjuntos, entonces existe {X, Y }. (¿Por qu´e ?) Entonces [ x ∈ {X, Y } ↔ (x ∈ X ∨ x ∈ Y ). S {X, Y } se llama la uni´on de X e Y y se le denota X ∪ Y . Corresponde al conjunto de todos los conjuntos que pertenecen ya sea a X o a Y (o a ambos). M´as generalmente, dados los conjuntos X1 , X2 , . . . , Xn de manera an´aloga al caso de la uni´on de dos conjuntos, definimos [ X1 ∪ X2 ∪ · · · ∪ Xn = {X1 , X2 , . . . , Xn }. de tal manera que

x ∈ X1 ∪ X2 ∪ · · · ∪ Xn ↔ x ∈ X1 ∨ x ∈ X2 ∨ · · · ∨ x ∈ Xn .

El lector seguramente est´a familiarizado con el concepto de uni´on de dos o de una cantidad finita de conjuntos, el axioma A5 generaliza este concepto a la uni´on de una familia arbitraria, incluso infinita, de conjuntos. Observemos que para definir la uni´on de dos conjuntos son necesarios el Axioma de Pares, el Axioma de Uniones y el Axioma de Extensionalidad (para garantizar unicidad). Usando la definici´on de uni´on de dos conjuntos, podemos tambi´en definir triples no–ordenados {x, y, z} = {x, y} ∪ {z}

y, en general, iterando el proceso, podemos definir n–tuplas no–ordenadas {x1 , x2 , . . . , xn }. Otra generalizaci´on de un concepto familiar es el de intersecci´ on de T un conjunto no–vac´ıo X , en s´ımbolos, X, definida por \ [ X = {x ∈ X : ∀y(y ∈ X → x ∈ y)}. T Observemos que en virtud de A5 y de A3, X es efectivamente un conjunto. ¿Por qu´e debemos exijir que X sea no–vac´ıo? La intersecci´on de dos conjuntos X e Y , X ∩ Y , se define por \ X ∩ Y = {X, Y } y en general

X1 ∩ X2 ∩ · · · ∩ Xn =

\

{X1 , . . . , Xn }.

En rigor, para definir x ∩ y no necesitamos A5. ¿C´omo podr´ıamos hacerlo? Diremos tambi´en que dos conjuntos X e Y son disjuntos si X ∩ Y = ∅. 12

A6. Axioma del Conjunto Potencia: “Si X es un conjunto, entonces existe el conjunto de todos los subconjuntos de X ”. Esto es ∀X ∃Y ∀z(z ∈ Y ↔ z ⊆ X)) (En rigor deberiamos excribir

∀X ∃Y ∀z(z ∈ Y ↔ ∀u(u ∈ z → u ∈ X)) sin embargo, como la lectura de la f´ormula se complica bastante y ya sabemos c´omo definir ⊆ usando s´olo ∈ y los s´ımbolos l´ogicos, preferimos la escritura abreviada). Creemos que este axioma se explica por s´ı mismo. El (´ unico) conjunto cuya existencia garantiza este axioma se designa por PX y se llama el conjunto potencia de X . A7 Axioma de Regularidad: “Todo conjunto no vac´ıo contiene un elemento con el que no comparte ning´ un elemento.” En L escribimos ∀x(x 6= ∅ → ∃y(y ∈ x ∧ y ∩ x = ∅)). A pesar de que no resulta evidente a partir de su formulaci´on, este axioma impide la existencia de un conjunto a tal que a ∈ a o incluso a ∈ b ∈ a , o a ∈ c ∈ b ∈ a , etc. Como veremos en su oportunidad, intuitivamente este axioma dice que ∈ , considerada como una relaci´on entre conjuntos,verifica una condici´on an´aloga a la del orden de los n´ umeros naturales, ´esta es, que todo conjunto no vac´ıo tiene un menor elemento. Teorema 1.3. i) ∀x x 6∈ x. ii) ∀x ∀y(x 6∈ y ∨ y 6∈ x). iii) En general, no existen a1 , a2 , . . . , an tales que a1 ∈ a2 ∈ · · · ∈ an ∈ a1 . iv) No existen conjuntos a1 , a2 , a3 , . . . , an , . . . tales que · · · ∈ an ∈ · · · ∈ a2 ∈ a1 . ´ n. Demostracio i) Supongamos que existe a tal que a ∈ a , entonces A = {a} contradice a A7. ii) Idem i) con A = {x, y} iii) Idem i) con A = {a1 , a2 , . . . , an }. iv) Supongamos que existe el conjunto cuyos elementos son precisamente a1 , a2 , a3 , . . . . Llamemoslo A . Entonces A contradice a 13

A7 ya que para cualquier y ∈ A, digamos y = am para alg´ un m , am+1 ∈ am y am+1 ∈ X, o sea y ∩ X 6= ∅. El problema entonces se reduce a verificar que existe tal conjunto A. Sin embargo para poder hacerlo no bastan los axiomas que tenemos hasta ahora, necesitamos dos axiomas m´as. La demostraci´on deber´a posponerse hasta entonces. (Ver ejercicio 7.) Aunque la mayor parte de las matem´aticas puede desarrollarse sin el axioma de regularidad es m´as c´omodo contar con ´el. A8. Axioma del Conjunto Infinito: “Existe un conjunto que tiene infinitos elementos”. Para escribirlo en el lenguaje L debemos usar una expresi´on que no es muy transparente. ∃X(∅ ∈ X ∧ ∀y(y ∈ X → y ∪ {y} ∈ X). Es claro que el conjunto as´ı formado es intuitivamente infinito, basta verificar que contiene a los siguientes conjuntos ∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}, . . . por supuesto que habr´ıa que demostrar adem´as que todos estos conjuntos son distintos. Para introducir el u ´ltimo axioma de ZF, debemos estudiar antes un cierto tipo de f´ormula de L . Una f´ormula ϕ(x, y) de L con dos variables libres x e y se dir´a funci´ on proposicional si para todo conjunto a existe un u ´nico conjunto b tal que ϕ(a, b) se verifica. Ejemplos de ´estas son las f´ormulas ϕ(x, y) siguientes: y y y y

= = = =

∪x, Px, x ∪ {x}, x ∩ a,

donde a es un conjunto fijo, etc. A9. Axioma de Reemplazo: “Si ϕ(x, y) es una funci´on proposicional y A es un conjunto, entonces existe el conjunto de los elementos b que verifican ϕ(a, b) para alg´ un a ∈ A”. Expresado en L , tenemos ∀X∃Y ∀y(y ∈ Y ↔ ∃x(x ∈ X ∧ ϕ(x, y))). 14

De hecho, este axioma parece m´as complicado de lo que es. La idea intuitiva es que si tenemos un conjunto A y una funci´on f cuyo dominio es A , f [A] = {f (x) : x ∈ A}, es tambi´en un conjunto. El problema se suscita cuando vemos que en nuestra teor´ıa la “funci´on” x 7−→ Px no es, como veremos formalmente m´as adelante, un objeto de nuestra teor´ıa, es decir, no es un conjunto, sino que corresponde a lo que llamamos una clase propia. Como ya hemos dicho antes, nuestro lenguaje nos permite referirnos a dichos objetos mediante la f´ormula que los define, lo que para los efectos pr´acticos es casi lo mismo. As´ı, ϕ(x, y) no es una funci´on dentro de nuestra teor´ıa sino m´as bien una regla que nos permite asociar a cada elemento de un conjunto A un u ´nico elemento. Algunos matem´aticos llaman a la f´ormula que define una funci´on, su gr´afico. Siguiendo con esta nomenclatura, el problema aqu´ı es que el dominio de esta funci´on es la clase de todos los conjuntos que, como ya vimos, no es un conjunto. Sin embargo, cuando restringimos dicho “dominio” a un conjunto A , A9 garantiza que existe el recorrido de la funci´on. Esta lista de axiomas conforman ZF. Junto con el Axioma de Elecci´on, que estudiaremos en el cap´ıtulo 3, son suficientes para desarrollar casi toda la matem´atica. Inmediatamente se nos ocurren varias preguntas ¿son estos axiomas independientes entre s´ı ? Es decir, ¿no pueden obtenerse unos de otros? La respuesta es no, el axioma de pares puede obtenerse a partir de los axiomas de reemplazo y del conjunto potencia. Por su parte el axioma del conjunto vac´ıo puede obtenerse a partir del axioma de especificaci´on y del axioma del conjunto infinito (habr´ıa que darle otra formulaci´on a este u ´ltimo). El problema de la independencia del axioma de elecci´on del resto de los axiomas es mucho m´as complicado. Fue resuelto positivamente por K. G¨odel (1940). M´as importante a´ un es el problema de la consistencia, es decir, ¿es posible deducir una contradicci´on a partir de estos axiomas? Este problema no se ha resuelto y no parece probable que vaya a resolverse debido a los resultados de G¨odel en 1930. Por supuesto no se ha descubierto ninguna contradicci´on (de no ser as´ı, no tendr´ıa sentido el estudio de esta teor´ıa) y se estima que s´ı son consistentes. El otro problema que surge naturalmente es el de la completud de este sistema de axiomas. Es decir, ¿son suficientes estos para deducir todos los teoremas posibles sobre conjuntos? La respuesta es tambi´en no. Mas a´ un, sabemos (nuevamente en virtud de los trabajos de K. 15

G¨odel en 1930) que no puede completarse, es decir, aunque agreguemos una lista de infinitos axiomas a ZF, seguir´a siendo incompleto, es decir, siempre existir´a una f´ormula ϕ tal que ni ϕ ni ¬ϕ puede demostrarse a partir de esa lista. Todos estos problemas requieren de conocimientos de L´ogica Matem´atica y est´an fuera del alcance de esta obra. Nos parece interesante eso s´ı mencionarlos para que el lector investigue por su cuenta. Ejercicios. 1. Demuestre que el axioma de pares puede ser reemplazado por el axioma m´as d´ebil: “Dados dos conjuntos X e Y , existe un conjunto los contiene a ambos”. 2. Demuestre que el axioma de uniones puede ser reemplazado por el axioma m´as d´ebil: “Si X es un conjunto, entonces existe un conjunto que contiene a todos los elementos de los elementos de X ”. 3. Demuestre que el axioma del conjunto potencia puede ser reemplazado por el axioma m´as d´ebil: “Si X es un conjunto, entonces existe un conjunto que contiene a todos los subconjuntos de X ”. 4. Demuestre que el Axioma de Pares puede obtenerse a partir de los axiomas de Reemplazo y del Conjunto Potencia. 5. Demuestre el Axioma del Conjunto Vac´ıo a partir de de los otros axiomas y el nuevo axioma “Existe un conjunto infinito”. 6. Indique c´omo definir x ∩ y sin usar el axioma A5. 7. Use el axioma de reemplazo y el de conjunto infinito para demostrar que el conjunto A definido en la demostraci´on del teorema 1.3 existe.

16

CAPITULO 2

Teor´ıa Elemental En este cap´ıtulo formalizaremos y profundizaremos las nociones de la teor´ıa intuitiva de conjuntos que el lector probablemente ha estudiado en cursos de Algebra, Geometr´ıa u otros. Por tratarse de material familiar, la mayor´ıa de las demostraciones se dejar´an como ejercicio. Debemos cuidarnos eso s´ı de no dar a las intuiciones el car´acter de teoremas y demostrar cuidadosamente todas nuestras afirmaciones a partir de los axiomas. Una de las dificultades que enfrenta el principiante en Teor´ıa Axiom´atica de Conjuntos es precisamente ese conocimiento intuitivo del tema. En nuestra teor´ıa todo es un conjunto, as´ı los elementos de un conjunto son a su vez, conjuntos que contienen elementos que a su vez son conjuntos. Es decir, la familiar distinci´on entre elemento y conjunto no existe y si se dice por ejemplo “ a es elemento de b ” es s´olo para enfatizar que a y b satisfacen a ∈ b, pero no para separar a a y b en dos categor´ıas distintas. As´ı, un mismo conjunto puede jugar ambos papeles en distintas situaciones, por ejemplo: ∅ ∈ {∅} {∅} ∈ {∅, {∅}}. Lo mismo puede decirse de pares ordenados, relaciones, funciones etc, etc, todo ente del cual hablemos ser´a un conjunto. 1. Operaciones En el cap´ıtulo anterior hemos definido las operaciones x ∪ y y x ∩ y. Definiremos ahora una tercera operaci´on ´ n 2.1. Dados dos conjuntos a y b definimos el compleDefinicio mento relativo de b con respecto a a , o su diferencia como sigue a − b = {x ∈ a : x ∈ / b}. Notese que en virtud de A3, a − b es un conjunto. Como lo demuestra la siguiente proposici´on, la noci´on de complemento de un conjunto a , es decir, el conjunto de aquellos conjuntos que no pertenecen a a , no puede definirse en ZF. 17

Teorema 2.1. No existe el “complemento”, de ning´ un conjunto. ´ n. Sea a un conjunto. Si existiera su complemento Demostracio 0 llam´emoslo a , entonces en virtud de A5, a ∪ a0 ser´ıa un conjunto, pero a ∪ a0 = V , la clase de todos los conjuntos que, como vimos, no es un conjunto. El siguiente teorema nos da las propiedades de estas tres operaciones. Teorema 2.2. (Algebra de Conjuntos). Para todo conjunto a, b, c : i) Asociatividad a ∪ (b ∪ c) = (a ∪ b) ∪ c , a ∩ (b ∩ c) = (a ∩ b) ∩ c . ii) Conmutatividad a∪b=b∪a , a∩b=b∩a. iii) Idempotencia a∪a=a , a∩a=a. iv) Absorci´on a ∪ (a ∩ b) = a , a ∩ (a ∪ b) = a . v) Neutro a∪∅=a , a∩∅=∅. vi) Distributividad a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∩ c) , a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c) . vii) Leyes de De Morgan a − (b ∪ c) = (a − b) ∩ (a − c) , a − (b ∩ c) = (a − b) ∪ (a − c) . viii) a − a = ∅ ix) a = (a ∩ b) ∪ (a − b) ´ n. Ejercicio Demostracio La relaci´on a ⊆ b se relaciona con las otras operaciones como sigue. Teorema 2.3. Para todo conjunto a, b, c, d. i) a ∩ b ⊆ a y a ∩ b ⊆ b. ii) Si c ⊆ a y c ⊆ b, entonces c ⊆ a ∩ b. iii) a ⊆ b si y s´olo si a ∩ b = a. 18

iv) v) vi) vii) viii)

Si a ⊆ c y b ⊆ d, entonces a ∩ b ⊆ c ∩ d. a ⊆ a ∪ b y b ⊆ a ∪ b. Si a ⊆ c y b ⊆ c, entonces a ∪ b ⊆ c. a ⊆ b si y s´olo si a ∪ b = b. Si a ⊆ c y b ⊆ d, entonces a ∪ b ⊆ c ∪ d.

´ n. Ejercicio. Demostracio Algunas propiedades del conjunto potencia de un conjunto son interesantes. Teorema 2.4. Para todo conjunto a, b: i) ∅ ∈ Pa y a ∈ Pa. ii) P∅ = {∅}. iii) Si a ⊆ b, entonces Pa ⊆ Pb. iv) Pa ∪ Pb ⊆ P(a ∪ b). v) Pa ∩ Pb = P(a ∩ b). vi) P(a − b) ⊆ (Pa − P(b)) ∪ {∅}. ´ n. A modo de ejemplo demostraremos vi). El resto Demostracio queda como ejercicio. Sea x ∈ P(a − b), es decir, x ⊆ a − b. Si x = ∅, entonces x ∈ (Pa − Pb) ∪ {∅}. Si x 6= ∅, entonces para todo z ∈ x, z ∈ a y z ∈ / b, o sea, x ⊆ a y x 6⊆ b, luego x ∈ Pa − Pb.

Ejercicios. 1. Determine si a pertenecea , es subconjunto, o ni pertenece ni es subconjunto de alguno de los siguientes conjuntos. (a) {{a}, a} , (b) a , (c) ∅ ∩ a , (d) {a} − {{a}} , (e) {a} ∪ a , (f) {a} ∪ {∅} . 2. Sea a un conjunto. Si para todo conjunto b se tiene a ∪ b = b, probar que a = ∅ . 19

3. Demostrar S que : (a) T{{a, b, c}, {a, d, e}, {a, f }} = {a, b, c, d, e, f } . (b) S{{a, b, c}, {a, T d, e}, {a, f }} = {a} . (c) T{a} = T a = {a} T , para todo conjunto a . (d) ( a) ∩ ( b) 6= (a ∩ b) . 4. Probar que: (a) Si a ∩ c = ∅ , entonces a ∩ (b ∪ c) = a ∩ b . (b) Si a ∩ b = ∅ , entonces a − b = a . (c) Si a ∩ b = ∅ y a ∪ b = c , entonces a = c − b. (d) a ∩ (b − c) = (a ∩ b) − c . (e) (a ∪ b) − c = (a − c) ∪ (b − c) . (f) Si a ∪ b = ∅ , entonces a = ∅ y b = ∅ . 5. Definamos 0 = ∅ , 1 = 0 ∪ {0} , 2 = 1 ∪ {1} , 3 = 2 ∪ {2} , 4 = 3 ∪ {3}. Entonces: (a) Probar que 0 , 1 , 2 , 3 y 4 son conjuntos. (b) Expresar 0 , 1 , 2 , 3 y 4 usando s´olo los s´ımbolos “ { ” , “}”,“ ∅ ”y“,”. (c) Decidir si son ciertas o falsas las afirmaciones siguientes: (i) 1 ∈ 2 (ii) 1 ∩ 2 = 0 (iii) (0 S ∩ 2) ∈ 1 (iv) 1T ⊆2 (v) 1 ∪ 2 = 2 (vi) 3 ⊆ 3 (vii) 4 ∈ 4

(d) Expresar los siguientes conjuntos usando los conjuntos 0, 1, 2, 3 yS4. Simplifique. SS SSS ∅ , P∅ , ∅ , PP∅ , T S∅ , PPP∅. (e) Si a = {{2,T3}, ( a − 4) . S 4, {4}} , encontrar (f) Construir (P2 − 2) . (g) Si a = {{1, 2}, {2, S T 0}, S {1, S 3}} T,Tconstruir: ST TS a, a, a, a, a, a. 6. Dar contraejemplo de P(a ∪ b) = Pa ∪ Pb . 7. ProbarSque: (a) Pa S =a. (b) a ⊆ P a . (c) No es cierto que si a ∈ b, entonces Pa ∈ Pb . S (d) Si S a ∈ b, entonces PaS∈ PP a . (e) {Px : x ∈ a} ⊆ P a. (f) {∅, {∅}} ∈ PPPa , para todo conjunto a . (g) Si Pa = Pb, entonces a = b . 8. Se define a + b = (a − b) ∪ (b − a) , para a y b conjuntos. Probar que si a, b , c son conjuntos, entonces: (a) a + ∅ = a (b) a + a = ∅ 20

(c) (d) (e) (f) (g) (h) (i) 9. Sean

a + (b + c) = (a + b) + c a ∩ (b + c) = (a ∩ b) + (a ∩ c) a−b⊆a+b a = b si y s´olo si a + b = ∅ Si a + c = b + c , entonces a = b a ∪ c = b ∪ c si y s´olo si a + b ⊆ c (a ∪ c) + (b ∪ c) = (a + b) − c a = {x ∈ Z : x es divisible por 4} b = {x ∈ Z : x es divisible por 9} c = {x ∈ Z : x es divisible por 10}

(a) Describir a ∩ b ∩ c . (b) Sean n , m ∈ Z. Si d = {x ∈ Z : x es divisible por n} e = {x ∈ Z : x es divisible por m}, describa d ∩ e . ¿ Qu´e pasa si m y n son n´ umeros primos? ¿ Qu´e pasa si m = −n ? 10. Probar que si a, b , c son conjuntos, entonces (a ∩ b) ∪ c = a ∩ (b ∪ c) si y s´olo si c ⊆ a. 11. Para las siguientes oraciones, dar una demostraci´on o un contraejemplo: (a) (a − b) − c = a − (b − c) . (b) Si a ∩ b = a ∩ c , entonces b = c . (c) Si a ∪ b = a ∪ c y a ∩ b = a ∩ c , entonces b = c . (d) a − b = (a ∪ b) − b = a − (a ∩ b) . (e) a ∩ b = a − (a − b) . (f) a − (b − c) = (a − b) ∪ (a ∩ c) . (g) a − b = b − a . (h) a ∩ (a − b) = (a − b) . (i) (a − b) ∪ b = a ∪ b . (j) (a ∩ b) − b = ∅ . (k) (a − b) ∩ b = ∅ . 12. Probar que la inclusi´on ⊆ de conjuntos cumple: (a) a ⊆ a ( reflexividad ); (b) Si a ⊆ b y b ⊆ a , entonces a = b ( antisimetr´ıa ); (c) Si a ⊆ b y b ⊆ c , entonces a ⊆ c ( transitividad ). 13. Si a ⊆ b y b ⊆ c y c ⊆ a, probar que a = b = c. 21

14. Si b ⊆ a y c ⊆ a , probar que b ⊆ c si y s´olo si (a − c) ⊆ (a − b). 15. Sean b, c, d subconjuntos del conjunto a. Abreviaremos “a−x” por “ x 0 ” . Probar o dar contraejemplo de: (a) b ⊆ c si y s´olo si b ∩ c 0 = ∅ (b) b ⊆ c si y s´olo si b 0 ∩ c = ∅ (c) b ⊆ c si y s´olo si b 0 ∪ c = a (d) b ⊆ c si y s´olo si b ∩ c 0 ⊆ b 0 (e) b ⊆ c si y s´olo si b ∩ c 0 ⊆ c (f) b ⊆ c si y s´olo si b ∩ c 0 ⊆ d ∩ d 0 16. Probar o dar contraejemplo de: (a) a ⊆ b ∩ c si y s´olo si a ⊆ b y a ⊆ c (b) b ∪ c ⊆ a si y s´olo si b ⊆ a y c ⊆ a (c) Si a ⊆ b ∪ c , entonces a ⊆ b ´o a ⊆ c (d) Si b ∩ c ⊆ a , entonces b ⊆ a ´o c ⊆ a 17. Probar: (a) Si S paraStodo c ∈ a existe d ∈ b tal que c ⊆ d, entonces Ta ⊆ b T (b) {c : c = {x}−b y x ∈ a} = ( {c : c = {x} y x ∈ a})−b (c) [ [ x= a x∈a

(d)

\

x=

\

b) =

[ (a ∩ c)

x∈a

(e) a∩(

[

a

c∈b

(f) Si d 6= ∅, entonces \ \ a ∪ b = (a ∪ c). c∈b

18. Demuestre todas las afirmaciones que no se demostraron en el teorema 2.2. 19. Demuestre todas las afirmaciones que no se demostraron en el teorema 2.3. 20. Demuestre todas las afirmaciones que no se demostraron en el teorema 2.4. 22

2. Relaciones Vamos ahora a introducir algunos conceptos matem´aticos familiares, como par ordenado, relaci´on, funci´on, etc. Debemos tener especial cuidado de que estos sean conjuntos en virtud de alg´ un axioma de ZF. Por otra parte, tambi´en queremos que estos conjuntos se comporten como los objetos con que trabaja el matem´atico a quien no preocupan los problemas de fundamento. ´ n 2.2. Dados dos conjuntos a y b llamamos par ordenado Definicio a, b al siguiente conjunto. ha, bi = {{a}, {a, b}}.

a y b se llaman la primera y segunda coordenada de ha, bi , respectivamente. Notemos que ha, bi es efectivamente un conjunto. Para justificarlo, basta usar dos veces el axioma de pares. En el par no ordenado {a, b} no podemos distinguir ambos elementos ya que {a, b} = {b, a} (¿por qu´e?). En cambio, los elementos del par ordenado ha, bi si y s´olo si son distinguibles, es decir, si y s´olo si sabemos cu´al es el primero y cu´al es el segundo. Este es el contenido del pr´oximo teorema. Teorema 2.5. Si ha, bi = hc, di , entonces a = c y b = d. ´ n. Supongamos que ha, bi = hc, di , ´esto es, Demostracio {{a}, {a, b}} = {{c}, {c, d}}.

Si a = b, tenemos {{a}} = {{c}, {c, d}}, entonces {a} = {c} = {c, d}, o sea a = b = c = d. (¿Qu´e axiomas hemos usado?). Si a 6= b, {a} = {c} o {a} = {c, d}. En el primer caso, tenemos a = c y como {a, b} ∈ {{c}, {c, d}} y a 6= b, {a, b} = {c, d} luego a = c y b = d. En el segundo caso, a = c = d , luego {a, b} ∈ {{a}}, o sea b = a , contradicci´on, o sea, este segundo caso no se puede dar. Por lo tanto, si ha, bi = hc, di, entonces a = c y b = d.

Podemos ahora definir triples ordenados y, en general, n-tuplas ordenadas. ha, b, ci = hha, bi, ci ha, b, c, di = hha, b, c, i, di ha1 , a2 , . . . , an i = hha1 , . . . , an−1 i, an i. 23

Lema 2.6. Si a ∈ A y b ∈ A, ha, bi ∈ PPA. ´ n. Ejercicio. Demostracio ´ n 2.3. Llamaremos producto cartesiano de los conjuntos Definicio a y b al conjunto a × b = {z ∈ PP(a ∪ b) : ∃x∃y(x ∈ a ∧ y ∈ b ∧ z = hx, yi)}. Notemos que por el axioma de especificaci´on de clases y el axioma del conjunto potencia, a × b es un conjunto. Usaremos en general una notaci´on informal aunque m´as intuitiva a × b = {hx, yi : x ∈ a ∧ x ∈ b}. Podemos tambi´en introducir productos cartesianos triples y cuadruples etc., de la manera obvia, por ejemplo a × b × c = {hx, y, zi : x ∈ a ∧ y ∈ b ∧ z ∈ c} Algunas propiedades de los productos cartesianos est´an resumidas en el siguiente teorema. Teorema 2.7. Para conjunto a, b , c , d , i) a × ∅ = ∅ × a = ∅. ii) Si a 6= ∅ y b 6= ∅, entonces a × b 6= ∅. iii) Si a ⊆ c y b ⊆ d, entonces a × b ⊆ c × d. iv) a × (b ∪ c) = a × b ∪ a × c. v) a × (b ∩ c) = a × b ∩ a × c. vi) a × (b − c) = a × b − a × c ´ n. Ejercicio. Demostracio ´ n 2.4. Un conjunto R es una relaci´ Definicio on si todos sus elementos son pares ordenados. Definimos tambi´en el dominio de R [[ Dom R = {x ∈ R : ∃yhx, yi ∈ R},

el recorrido de R

Rec R = {y ∈ y el campo de R ,

[[

R : ∃xhx, yi ∈ R}

Cam R = Dom R ∪ Rec R. Si Dom R ⊆ A y Rec R ⊆ B, decimos que R es una relaci´ on entre A y B o una relaci´on de A en B . 24

Es claro que tanto Dom R como Rec R son conjuntos (¿qu´e axiomas usamos?). Lo que no es tan claro es que estos conjuntos correspondan a la idea informal que tenemos del dominio, es decir, el conjunto de las primeras coordenadas de los pares que est´an en la relaci´on, y recorrido, el conjunto de las segundas coordenadas de los pares que est´an en la relaci´on. Basta para ello comprobar que, efectivamente, ambas coordenadas de los pares que pertenecen a una relaci´on R est´an SS en R. Esto es f´acil ya que para ha, bi ∈ R; a, b ∈ {a, b} ∈ ha, bi ∈ R, lo que implica por definici´on de uni´on que {a, b} ∈

o sea, o sea,

[

R ,

a, b ∈ {a, b} ∈ a, b ∈

[[

[

R,

R.

´ n 2.5. La composici´ Definicio on de dos relaciones R y S es la relaci´on S ◦R = {u ∈ Dom R×Rec S : u = hx, yi∧∃z(hx, zi ∈ R∧hz, yi ∈ S)} y la relaci´on inversa de R R−1 = {u ∈ Rec R × Dom S : u = hx, yi ∧ hy, xi ∈ R}. En general escribimos m´as informalmente S ◦ R = {hx, yi : ∃z(hx, zi ∈ R ∧ hz, yi ∈ S)} y R−1 = {hy, xi : hx, yi ∈ R}.

Es claro que S ◦ R y R−1 son conjuntos.

Teorema 2.8. Si R , S y T son relaciones, entonces i) (T ◦ S) ◦ R = T ◦ (S ◦ R). ii) (S ∪ T ) ◦ R = (S ◦ R ∪ T ◦ R), y T ◦ (S ∪ R) = (T ◦ S ∪ T ◦ R). iii) (S ∩ T ) ◦ R ⊆ (S ◦ R ∩ S ◦ T ), y T ◦ (S ∩ R) ⊆ (T ◦ S ∩ T ◦ R). iv) Si R ⊆ S, entonces T ◦ R ⊆ T ◦ S y R ◦ T ⊆ S ◦ T. v) (R−1 )−1 = R. vi) (S ◦ R)−1 = R−1 ◦ S −1 . ´ n. iii) Sea hx, yi ∈ (S ∩ T ) ◦ R, entonces existe Demostracio z tal que hx, zi ∈ S ∩ T y hz, yi ∈ R. 25

Esto implica que existe z tal que hx, zi ∈ S y hz, yi ∈ S, vale decir, hx, yi ∈ S ◦R, pero adem´as, hx, zi ∈ T y hz, yi ∈ R, o sea, hx, yi ∈ T ◦ R, o sea, (S ∩ T ) ◦ R ⊆ (S ◦ R) ∩ (T ◦ R). Para ver que la inclusi´on anterior no es una identidad basta dar un ejemplo en el que la inclusi´on inversa es falsa. Consid´erese R = {ha, bi, ha, a, i}, S = {hb, ai}, T = {ha, ai}, donde a 6= b. Entonces S ∩ T = ∅, luego (S ∩ T ) ◦ R = ∅. Sin embargo, como ha, bi ∈ R y hb, ai ∈ S, ha, ai ∈ S ◦ R y como ha, ai ∈ R y ha, ai ∈ T, ha, ai ∈ T ◦ R, o sea, ha, ai ∈ S ◦ R ∩ T ◦ R, luego S ◦ R ∩ T ◦ R 6= ∅. vi) Sea hx, yi ∈ (S ◦ R)−1 . Entonces hy, xi ∈ S ◦ R, o sea, existe z tal que hy, zi ∈ R y hz, xi ∈ S, es decir, existe z tal que hx, zi ∈ S −1 y hz, yi ∈ R−1 , o sea, hx, yi ∈ R−1 ◦ S −1 , luego (S ◦ R)−1 ⊆ R−1 ◦ S −1

La inclusi´on inversa se demuestra en forma an´aloga y se deja como ejercicio. El pr´oximo teorema nos da las principales propiedades del dominio y del recorrido de una relaci´on. Teorema 2.9. Sean R , S relaciones. i) Dom (R ∪ S) = Dom R ∪ DomS. ii) Rec (R ∪ S) = Rec R ∪ Rec S. iii) Dom (R ∩ S) ⊆ Dom R ∩ DomS. iv) Rec (R ∩ S) ⊆ Rec R ∩ Rec S. v) DomR − DomS ⊆ Dom(R − S). vi) Rec R − Rec S ⊆ Rec(R − S). vii) Si R ⊆ S, entonces Dom R ⊆ Dom S y Rec R ⊆ Rec S. viii) Dom R−1 = Rec R y Rec R−1 = Dom R. ix) Dom S ◦ R ⊆ Dom R y Rec S ◦ R ⊆ Rec S. vii) Cam R = Cam R−1 . viii) Cam (S ◦ R) ⊆ Dom R ∪ Rec S. ´ n. Ejercicio. Demostracio La siguiente operaci´on ser´a muy importante especialmente cuando tratemos con funciones. 26

´ n 2.6. Si R es una relaci´on y a un conjunto la imagen Definicio de a por R es el conjunto. R∗ a = {y ∈ Rec R : ∃x(x ∈ a ∧ hx, yi ∈ R)}. Las principales propiedades de teorema.

∗

est´an resumidas en el siguiente

Teorema 2.10. Sean R , S relaciones y a y b conjuntos. i) ii) iii) iv) v) vi) vii) viii) ix)

∅∗ a = ∅. R∗ ∅ = ∅. R∗ (a ∪ b) = R∗ a ∪ R∗ b. R∗ (a ∩ b) ⊆ R∗ a ∩ R∗ b. R∗ a − R∗ b ⊆ R∗ (a − b). Si a ⊆ b, entonces R∗ a ⊆ R∗ b. (S ◦ R)∗ a = S ∗ (R∗ a). Dom(S ◦ R) = R−1∗ (DomS) y Rec(S ◦ R) = S ∗ (Rec R). R∗ a ⊆ Rec R.

´ n. Demostracio x ∈ R∗ (a ∩ b) ⇔ ⇒ ⇔ ⇔

iv) ∃y(y ∈ a ∩ b ∧ hy, xi ∈ R) ∃y(y ∈ a ∧ hy, xi ∈ R) ∧ ∃y(y ∈ b ∧ (y, x) ∈ R) x ∈ R∗ a ∧ x ∈ R∗ b x ∈ R∗ a ∩ R∗ b

Es decir R∗ (a ∩ b) ⊆ R∗ a ∩ R∗ b. Para ver que la inclusi´on contraria no es v´alida basta el siguiente contraejemplo. Sean a = {∅} ,

viii)

b = {{∅}} y R = {h∅, ∅i, h{∅}, ∅i}.

Entonces a ∩ b = ∅, luego R∗ (a ∩ b) = ∅. Pero R∗ a = {∅} y R∗ b = {∅} luego R∗ a ∩ R∗ b = {∅} = 6 ∅. x ∈ Dom (S ◦ R) ⇔ ⇔ ⇒ ⇔

∃y hx, yi ∈ S ◦ R ∃y ∃z(hx, zi ∈ R ∧ hz, yi ∈ S) ∃z(hz, xi ∈ R−1 ∧ z ∈ Dom S) x ∈ R−1∗ (Dom S).

Esto demuestra que Dom(S◦R) ⊆ R−1∗ (Dom S), la otra inclusi´on y el resto del teorema se deja como ejercicio. 27

Ejercicios. 1. Probar que si definimos ha, bi0 = {{a, 0}, {b, 1}}, entonces se satisface: ha, bi0 = hc, di0 si y s´olo si a = c y b = d . 2. Sean a, b, c conjuntos. Definimos el conjunto ha, b, ci0 = {{a}, {a, b}, {a, b, c}} . 3.

4. 5. 6. 7.

8.

9.

Probar que ha, b, ci0 = hd, e, f i0 no implica que a = d y b=e y c=f . ProbarTque: (a) T ha, T bi = {a} . S T (b) T S ha, bi = a = ha, bi . (c) T Sha, bi = S a ∩ bS. S ST (d) ( ha, bi) ( ha, bi − ha, bi) = b. Mostrar que no siempre el conjunto ha, bi tiene dos elementos distintos. Probar que no existe el conjunto de todos los pares ordenados. Probar que no es cierto que hha, bi, ci es igual a ha, hb, cii . (a) Probar que a × b = b × a si y s´olo si a = ∅ o b = ∅ o a=b . (b) Probar que si a 6= ∅ y a × b ⊆ a × c , entonces b ⊆ c . (c) Probar que no es cierto : a × (b × c) = (a × b) × c . (d) Encontrar conjuntos a, b, c tales que a ∪ (b × c) = (a ∪ b) × (a ∪ c). (e) Probar que a × b ∩ c × d = a × d ∩ c × d . (f) Probar que a × a ∩ b × c = a ∩ b × a × c . (g) Probar que a × b − c × c = (a − c) × b ∪ a × (b − c) . (h) Probar que a × a − b × c = (a − b) × a ∪ a × (a − c) . (i) Probar que no es cierto que a × b = c × d ocurra si y s´olo si a = b y c = d . Si a, b son conjuntos, probar que existe un conjunto c tal que y ∈ c si y s´olo si existe un conjunto d que satisfaga que d ∈ a e y = {d} × b . S Concluir que a × b = c . (a) Encontrar todas las relaciones cuyo dominio est´a contenido en {a, b, c} y cuyo recorrido esta contenido en {s} . (b) Encontrar todas las relaciones en 2 y en 3 (ver definici´on de 2 y de 3 en ejercicios de la secci´on anterior). 28

(c) ¿Cu´antas relaciones se pueden formar en un conjunto de n elementos? 10. Probar que existe una relaci´on I que act´ ua como neutro para la composici´on de relaciones sobre un conjunto a , es decir, para cualquier relaci´on R sobre a R ◦ I = I ◦ R = R.

11. Probar que si R, S, T son relaciones y a, b, c conjuntos, entonces: (a) S ∩ T y S ∪ T son relaciones . (b) (S ∩ T )−1 = S −1 ∩ T −1 . (c) (S ∪ T )−1 = S −1 ∪ T −1 . (d) (R − S)−1 = R−1 − S −1 . (e) (R ◦ S) − (R ◦ T ) ⊆ R ◦ (S − T ) . (f) R ⊆ S si y s´olo si S −1 ⊆ R−1 . (g) (a × b)−1 = b × a . (h) Si a y b no son disjuntos, entonces (a×b)◦(a×b) ⊆ (a×b). (i) Si a y b son disjuntos, entonces (a × b) ◦ (a × b) = ∅ . (j) Si b no es vac´ıo, entonces (b × c) ◦ (a × b) = a × c . (k) Si R ⊆ a × b y S ⊆ b × c , entonces S ◦ R ⊆ a × c . 12. Probar que ∅ es relaci´on y que para todo conjunto a se tiene que a ◦ ∅ = ∅ ◦ a = ∅ . 13. Se define la suma de dos relaciones R y S por: R + S = (R ∪ S) ∩ (Cam R) × (Cam S) .

(a) Si R = {h1, 2i, h1, 3i} y S = {h3, 3i}, calcular R + S y S+R . (b) Encontrar Cam (R + S). (c) Determinar cu´ales de las siguientes leyes distributivas son v´alidas para la suma de relaciones: R + (S ∪ T ) R + (S ∩ T ) R ∪ (S + T ) R ∩ (S + T )

= = = =

(R + S) ∪ (R + T ) (R + S) ∩ (R + T ) (R ∪ S) + (R ∪ T ) (R ∩ S) + (R ∩ T )

14. Encontrar contraejemplos para las siguientes afirmaciones: (a) Dom (R ∩ S) = Dom R ∩ Dom S . (b) Rec (R ∩ S) = Rec R ∩ Rec S . (c) Dom R − Dom S = Dom (R − S) . (d) Rec R − Rec S = Rec (R − S) . (e) Cam (S ◦ R) = Dom R ∪ Rec S . (f) R∗ (a ∩ b) = R∗ a ∩ R∗ b . (g) R∗ a − R∗ b = R∗ (a − b) . 29

15.

16.

17. 18. 19. 20.

(h) R∗ a = Rec R . (i) ( R−1 )∗ ( R∗ a ) = a . (j) R∗ ( ( R−1 )∗ b ) = b . Probar las siguientes afirmaciones: (a) ( R−1 )∗ (a ∪ b) ⊆ ( R−1 )∗ a ∪ ( R−1 )∗ b . (b) ( R−1 )∗ (a ∩ b) ⊆ ( R−1 )∗ a ∩ ( R−1 )∗ b . (c) ( R−1 )∗ a − ( R−1 )∗ b ⊆ ( R−1 )∗ (a − b) . (d) a ⊆ ( R−1 )∗ ( R∗ a ) . (e) b ⊆ R∗ ( ( R−1 )∗ b ) . (f) Si R ⊆ a × b , entonces R∗ a = Rec R y ( R−1 )∗ b = Dom R . (a) Probar que R∗ a = ∅ si y s´olo si Dom R ∩ a = ∅ . (b) Probar que Dom R ∩ a ⊆ ( R−1 )∗ ( R∗ a ). (c) Probar que ( R∗ a ) ∩ b ⊆ R∗ (a ∩ ( R−1 )∗ b ) . (d) ¿ Bajo qu´e condiciones se tiene que Cam (a × b) = a ∪ b? (e) Probar que si x ∈ Dom R , entonces hx, xi ∈ R−1 ◦ R . Demuestre todas las afirmaciones que no se demostraron en el teorema 2.7. Demuestre todas las afirmaciones que no se demostraron en el teorema 2.8. Demuestre todas las afirmaciones que no se demostraron en el teorema 2.9. Demuestre todas las afirmaciones que no se demostraron en el teorema 2.10. 3. Funciones

El concepto de funci´on es uno de los m´as importantes en matem´aticas. Intuitivamente, una funci´on es una regla que asigna a cada elemento de un conjunto un u ´nico elemento de otro conjunto (no necesariamente distinto). ´ n 2.7. Una relaci´on F es una funci´ Definicio on si y s´olo si ∀x∀y∀z((hx, yi ∈ F ∧ hx, zi ∈ F ) → y = z) Obs´ervese que una funci´on es, en particular, una relaci´on, as´ı es que los conceptos de dominio, recorrido, campo, composici´on de funciones, funci´on inversa, imagen, etc. se aplican a ellas tal y como se aplican a otras relaciones. Habitualmente se usa la siguiente notaci´on. ´ n 2.8. Sea F una funci´on, x ∈ Dom F , Definicio [ F (x) = {z ∈ Rec F : ∀y(hx, yi ∈ F → z ∈ y)}. 30

En otras palabras, F (x) es aquel u ´nico conjunto con el que x est´a relacionado seg´ un la funci´on F . Observemos que el axioma de extensionalidad aplicado a funciones F y G nos dice que F =G

si y s´olo si

Dom F = Dom G y ∀x F (x) = G(x).

Observemos tambi´en que de acuerdo con esta notaci´on, G ◦ F (x) = G(F (x)). ´ n 2.9. Definicio i) Si F es una funci´on, Dom F = a y Rec F ⊆ b decimos que F es una funci´on de a en b y escribimos F : a −→ b x 7−→ F (x). ii) a

b = {F ∈ P(a × b) : F : a −→ b}.

iii) F es una funci´on inyectiva o uno a uno si

∀x∀y(F (x) = F (y) → x = y), es decir, a conjuntos distintos F asigna conjuntos distintos. iv) Un funci´on F de a en b se dice sobreyectiva si ∀y(y ∈ b → ∃x(x ∈ a ∧ y = F (x))), es decir, todo elemento de b es asignado a alg´ un elemento del dominio de F . El siguiente teorema nos da algunas propiedades de las funciones. Teorema 2.11. Sean F , G , H funciones, a , b , c conjuntos. i) F es una funci´on de Dom F en Rec F . ii) F ∈ ∅ a si y s´olo si F = ∅. iii) Si F ∈ a ∅, entonces F = a = ∅. iv) Si b 6= ∅, entonces a b 6= ∅. v) Si F ∈ a b y b ⊆ c, entonces F ∈ a c. vi) Si F ∈ a b y G ∈ b c, entonces G ◦ F ∈ a c. vii) F ∈ a b es inyectiva si y s´olo si para todo c y todo G ∈ c a, H ∈ c a, si F ◦ G = F ◦ H, entonces G = H. viii) F ∈ a b es sobreyectiva si y s´olo si para todo c y todo G ∈ b c, H ∈ b c, si G ◦ F = H ◦ F , entonces G = H. ´ n. Demostraremos vii). El resto queda como ejerciDemostracio cio. 31

(⇒) Supongamos que F es inyectiva y sean c un conjunto cualesquiera y G, H ∈ c a. Supongamos que para todo x ∈ c F ◦ G(x) = F ◦ H(x) F (G(x)) = F (H(x)) , G(x) = H(x) .

o bien y como F es inyectiva,

Como adem´as Dom G = Dom H = c, G = H. (⇐)) Supongamos que se verifica la afirmaci´on de la derecha y que sin embargo F no es inyectiva. Entonces existen d, e ∈ a , d 6= e y F (d) = F (e). Consideremos el caso particular en que c = a y definamos G : a −→ a x 7−→ d tonces para todo x ,

H : a −→ a x 7−→ e.

En-

F ◦ G(x) = F (G(x)) = F (d) = F (e) = F (H(x)) = F ◦ H(x), es decir F ◦ G = F ◦ H, ya que tienen el mismo dominio. Pero entonces, por hip´otesis, G = H, una contradicci´on. Luego F es inyectiva.

Teorema 2.12. Sean F , G funciones. i) ii) iii) iv)

x ∈ F −1∗ a si y s´olo si F (x) ∈ a. Dom (F ◦ G) = G−1∗ (Dom F ) ⊆ Dom G. Rec (F ◦ G) = F ∗ (Rec G) ⊆ Rec F. F es inyectiva si y s´olo si F −1 es funci´ on.

´ n. Demostracio i) x ∈ F −1∗ a si y s´olo si ∃y(y ∈ a ∧ hy, xi ∈ F −1 ) si y s´olo si ∃y(y ∈ a ∧ hx, yi ∈ F ) si y s´olo si ∃y(y ∈ a ∧ y = F (x)) si y s´olo si F (x) ∈ a. ii) y iii), por teorema 2.10, viii). iv) Ejercicio.

Teorema 2.13. Sean F , G funciones. i) F −1∗ (a ∩ b) = F −1∗ a ∩ F −1∗ b ii) F −1∗ (a − b) = F −1∗ a − F −1∗ b 32

´ n. Demostracio i) Por el teorema 2.10, iv), basta demostrar −1∗ −1∗ que F a ∩ F b ⊆ F −1∗ (a ∩ b). Sea x ∈ F −1∗ a ∩ F −1∗ b. Entonces por teorema 2.12, i), F (x) ∈ a y F (x) ∈ b, o sea, F (x) ∈ a∩b, luego x ∈ F −1∗ (a∩b). ii) Ejercicio. ´ n 2.10. Definicio i) Si a es un conjunto, la funci´on Ia : a −→ a x 7−→ x

se llama la funci´on identidad en a . ii) Si F es una funci´on y a un conjunto. La restricci´ on de F a a , F  a, es la funci´on F  a : a ∩ Dom F −→ F ∗ a x 7−→ F  a(x) = F (x). El siguiente teorema nos permite “pegar” funciones que coinciden en la parte com´ un de sus dominios. Teorema 2.14. Sean F , G funciones tales que F  a = G  a, donde a = Dom F ∩ Dom G. Entonces F ∪ G es una funci´on. ´ n. Recordemos que Dom (F ∪ G) = Dom F ∪ Demostracio Dom G. Si x ∈ Dom F − Dom G o x ∈ Dom G − Dom F , entonces es claro que existe un u ´nico y tal que hx, yi ∈ F ∪ G. Como F y G son funciones, para x ∈ Dom F ∩ Dom G, existe un u ´nico y y un u ´nico z tal que hx, yi ∈ F y hx, zi ∈ G. Pero por hip´otesis y = z , luego en este caso tambi´en hay un u ´nico y tal que hx, yi ∈ F ∪ G. Observemos en el teorema anterior que si Dom F ∩ Dom G = ∅, F ∪ G es siempre una funci´on. El pr´oximo teorema es muy u ´til para probar que ciertas funciones son inyectivas o sobreyectivas. Teorema 2.15. Sea F : a −→ b. i) Si existe una funci´on G : b −→ a tal que F ◦ G = Ib , entonces F es sobreyectiva. ii) F es inyectiva si y s´olo si a = ∅ o a = 6 ∅ y existe una funci´on G : b −→ a tal que G ◦ F = Ia . 33

iii) F es biyectiva si y s´olo si existe una funci´on G : b −→ a tal que F ◦ G = Ib y G ◦ F = Ia . En este caso G = F −1 . ´ n. Demostracio i) Sea G : b −→ a tal que F ◦ G = Ib . Entonces para todo y ∈ b, G(y) ∈ a y F (G(y)) = F ◦ G(y) = Ib (y) = y, es decir F es sobreyectiva. ii) (⇒) Supongamos F es inyectiva y a 6= ∅. Sea c ∈ a y definamos

G = F −1 ∪ {hx, ci : x ∈ b − F ∗ a}

(Obs´ervese que G es efectivamente un conjunto. ¿C´omo verificamos ´esto?) Es f´acil ver que G es una funci´on tal que Dom G = b. Para todo x ∈ a, G ◦ F (x) = G(F (x)) = F −1 (F (x)) = x,

ya que F (x) ∈ F ∗ a. Y como Dom G ◦ F = Dom F = a, G ◦ F = Ia . (⇐) Si a = ∅, entonces F = ∅ y por lo tanto F es inyectiva. Si a 6= ∅ y existe G : b −→ a tal que G ◦ F = Ia . Supongamos que F (x) = F (y). Entonces G(F (x)) = G(F (y)), o sea, x = G ◦ F (x) = G ◦ F (y) = y, luego F es inyectiva. iii) Ejercicio Notemos que en el teorema anterior parte i) no tenemos una equivalencia como en ii) y iii). Para demostrar el rec´ıproco de i), es decir, si F es sobreyectiva, entonces existe G : b → a tal que F ◦ G = Ib , necesitamos el u ´ltimo axioma de nuestra teor´ıa, el Axioma de Elecci´on. Debido a la importancia de ´este, le dedicaremos un cap´ıtulo completo, el cuarto. S´olo entonces podremos analizar este problema.

Ejercicios. 34

1. Considerando los conjuntos N, Z, Q y R, d´e ejemplos de funciones F tales que: (a) F : N −→ N , F no es inyectiva ni sobreyectiva. (b) F : N −→ N , F es inyectiva pero no sobreyectiva. (c) F : N −→ Z , F no es inyectiva ni sobreyectiva. (d) F : Z −→ N , F no es inyectiva ni sobreyectiva. (e) F : Q −→ R , F no es inyectiva ni sobreyectiva. (f) F : R −→ Q , F es sobreyectiva pero no inyectiva. (g) F : R −→ Z , F sobreyectiva tal que F (x) 6= x para todo x en R . 2. Probar que no toda inyecci´on de un conjunto en s´ı mismo es sobreyectiva. 3. Dar ejemplos de funciones tales que: (a) F : 1 −→ 1 . (b) F : 0 −→ 1 . (c) F : 2 × 3 −→ 6 , F biyecci´on. 4. Supongamos que existe una funci´on de a en b que no es inyectiva. Probar que a 6= ∅ y b 6= ∅ . 5. Supongamos que existe una funci´on de a en b que no es sobreyectiva. Probar que b 6= ∅ . 6. Sean F : a −→ b y G : a −→ b funciones. Probar que si F ⊆ G , entonces F = G . 7. Sean F : a −→ b y G : c −→ d funciones. Se define el producto entre F y G por (F ∗ G)(x, y) = hF (x), G(y)i

8.

9.

10.

11.

para hx, yi ∈ a × c. Probar que: (a) F ∗ G es una funci´on de a × c en b × d . (b) Si F y G son sobreyectivas, entonces F ∗G es sobreyectiva. (c) Si F y G son inyectivas, entonces F ∗ G es inyectiva . (d) Rec (F ∗ G) = (Rec F ) × (Rec G) . Sean F : a −→ b y G : b −→ a funciones. Supongamos que y = F (x) si y s´olo si x = G(y). Probar que F −1 es funci´on y que F −1 = G . Sean G : b −→ c y H : b −→ c funciones. Supongamos que G ◦ F = H ◦ F para toda funci´on F : a −→ b, donde a 6= ∅. Probar que G = H . Sean G : a −→ b y H : a −→ b funciones. Sea c un conjunto con m´as de un elemento y supongamos que F ◦ G = F ◦ H para toda funci´on F : b −→ c . Probar que G = H . Sean F : a −→ c y G : a −→ b funciones. Probar que existe una funci´on H : b −→ c tal que F = H ◦ G si y s´olo 35

12.

13.

14. 15.

16.

17. 18. 19. 20.

21.

si para todos x, y ∈ a se tiene que G(x) = G(y) implica F (x) = F (y). Probar que H es u ´nica. Sean F : c −→ a y G : b −→ a funciones, con G inyectiva. Probar que existe una funci´on H : c −→ b tal que F = G ◦ H si y s´olo si Rec F ⊆ Rec G. Probar que H es u ´nica . Probar que si F y G son funciones, entonces F ⊆ G si y s´olo si Dom F ⊆ Dom G y para todo x ∈ Dom F se tiene F (x) = G(x) . Probar que no existe el conjunto de todas las funciones. Sea F : a −→ b funci´on. Se define G por G(y) = F −1∗ {y} . Probar que G es funci´on y que si F es sobreyectiva, entonces G es inyectiva . Probar tambi´en que el rec´ıproco es falso. Determinar cuales de las siguientes relaciones son funciones: (a) R es relaci´on de R en R tal que ha, bi ∈ R si y s´olo si a2 + b2 = 1. (b) R es relaci´on de R en R tal que ha, bi ∈ R si y s´olo si a 0 ≤ a < 1 y b = 1−a . (c) R es relaci´on entre (R)2 y R tal que hha, bi, ci ∈ R si y . s´olo si c = a+b 2 Si F y G son funciones inyectivas, entonces G ◦ F es inyectiva y (G ◦ F )−1 = F −1 ◦ G−1 . Constru´ır los conjuntos 3 2, 0 2, 0 0 . Probar que a b = ∅ si y s´olo si b = ∅ y a 6= ∅ . Probar que : (a) a b =b a implica que a = b . (b) a ⊆ b implica que c a ⊆c b . (c) Si existe una biyecci´on entre a y b , entonces existe una biyecci´on entre c a y c b . Sea F : a −→ a una funci´on. Sea m un entero positivo. Se define recursivamente F m por F 1 = F;

22. 23. 24. 25.

F m+1 = F ◦ F m . Supongamos que existe un entero positivo n tal que F n = Ia . Probar que F es biyecci´on. Sean a, b, c conjuntos tales que b ∩ c = ∅ . Probar que existe una biyecci´on entre b∪c a y b a ×c a. ¿Existe una biyecci´on entre c (b a) y b×c a? Probar que existe una biyecci´on entre c (a × b) y c a ×c b . Sean F : a −→ b y G : a −→ b funciones. (a) Sea c el conjunto de los x ∈ a tales que F (x) = G(x) . Probar que F ◦ Ia  c = G ◦ Ia  c . 36

26. 27. 28.

29. 30.

31.

32.

33. 34.

(b) Sea d ⊆ a tal que F ◦ Ia  d = G ◦ Ia  d . Probar que d⊆c. Sea a un conjunto y sea F = {hx, hx, xii : x ∈ a} . Probar que F es funci´on biyectiva entre a y Ia . Sea F : b ∪ c −→ a funci´on. Probar que F = F  b ∪ F  c. Sean F : a −→ b y G : c −→ d funciones biyectivas, donde a ∩ c = ∅ y b ∩ d = ∅ . Sea H = F ∪ G. Probar que H es biyecci´on entre a ∪ c y b ∪ d . Sea F : a −→ b funci´on. Probar que existe una funci´on biyectiva entre F y a . Sea F : a −→ b funci´on. Sean c ⊆ a y d ⊆ b . (a) Si F es inyectiva, probar que c = F −1∗ (F ∗ c) . (b) Si F es sobre, probar que d = F ∗ ( (F ∗ )−1 d) . Sea F : a −→ b funci´on. Probar que: (a) Si c ⊆ a y d ⊆ a y F inyectiva, entonces F ∗ c = F ∗ d implica que c = d . (b) Si c ⊆ b y d ⊆ b y F sobreyectiva, entonces F −1∗ c = F −1∗ d implica que c = d . Sea F : a −→ b funci´on y sean c ⊆ a y d ⊆ a . (a) Probar que F ∗ ( F −1∗ (F ∗ c) ) = F ∗ c . (b) Probar que F ∗ c − F ∗ d = F ∗ (c − d) si y s´olo si F es inyectiva. T Probar que F  a = F (a × Rec F ) . Sea F : Pa −→ Pa funci´on tal que si b ⊆ c y c ⊆ a , entonces F (b) ⊆ F (c). Sean \ d= {b ∈ Pa : F (b) ⊆ b} e=

[

{b ∈ Pa : b ⊆ F (b)}.

(a) Probar que F (d) = d y F (e) = e . (b) Probar que si F (b) = b , entonces d ⊆ b ⊆ e . 35. Dar un ejemplo de una funci´on F y un conjunto a tales que F ∩ (a × a) 6= F  a . 36. Si F y G son funciones inyectivas, probar o dar contraejemplo de: (a) F ∪ G es inyectiva. (b) F − G es inyectiva. (c) F S ◦ G es inyectiva. (d) F F −1 es inyectiva. (e) a ∩ b = ∅ implica que F  a ∪ G  b es inyectiva. (f) a ∩ b = ∅ implica que F ∗ a ∩ G∗ b = ∅ . 37

37. Determinar hai : i ∈ Ii,

[

ai ,

i∈I

\

ai ,

i∈I

Y

ai si:

i∈I

(a) I = 3 y a0 = 1, a1 = 2, a2 = 3 . (b) I = 3 y ai = i , para todo i en 3 . 38. Probar que existe una biyecci´on entre a0 × a1 × a2 y Y ai i∈3

39. ¿Existe una biyecci´on entre Y Y a ( bi ) y ( a bi ) ? i∈I

i∈I

Q [i,i+1) 40. Probar que existe una biyecci´on entre R y R R. i∈I 41. Sea hbi : i ∈ Ii una familia de subconjuntos de a . Probar que Y bi ⊆ I a. i∈I

42. Sean hai : i ∈ Ii y hbi : i ∈ Ii dos familias de conjuntos con el mismo conjunto de ´ındices I. (a) Probar que ai ⊆ bi , para todo i en I , si y s´olo si Y Y ai ⊆ bi . i∈I

i∈I

(b) Probar que Y Y Y ( ai ) ∩ ( bi ) = (ai ∩ bi ). i∈I

i∈I

i∈I

43. Sean hai : i ∈ Ii y hbj : j ∈ Ji dos familias de conjuntos. Probar que: (a) Y Y Y ( ai ) ∩ ( bj ) = (ai ∩ bj ) . i∈I

j∈J

hi,ji∈I×J

(b) (

Y

ai ) ∪ (

Y

bj ) =

[

ai ) ∩ (

[

bj ) =

i∈I

j∈J

Y

(ai ∪ bj ) .

[

(ai ∩ bj ) .

hi,ji∈I×J

(c) (

i∈I

j∈J

hi,ji∈I×J

38

(d) (

\ i∈I

ai ) ∪ (

\

bj ) =

j∈J

\

hi,ji∈I×J

(ai ∪ bj ) .

44. Sean hai : i ∈ Ii una familia de conjuntos y R una relaci´on. Probar que [ [ R∗ ( ai ) = R∗ ai . i∈I

i∈I

45. Sea hai : i ∈ Ii una familia de conjuntos tal que I = Probar que: (a) [ [ [ ai ). ( ai = i∈I

(b)

\

j∈J

ai =

i∈I

S

J .

i∈j

\ \ ( ai ).

j∈J

i∈j

46. Sean hai : i ∈ Ii una familia de conjuntos y F una funci´on con dominio adecuado. Probar que: (a) [ [ F∗ ( ai ) = F ∗ ai . i∈I

(b)

F −1∗ (

i∈I

[

ai ) =

\

ai ) ⊆

\

ai ) =

i∈I

(c) F∗ (

i∈I

[

F −1∗ ai .

\

F ∗ ai

\

F −1∗ ai .

i∈I

i∈I

y que si F es inyectiva se tiene la igualdad. (d) F −1∗ (

i∈I

47. Demuestre todas teorema 2.11. 48. Demuestre todas teorema 2.12. 49. Demuestre todas teorema 2.13. 50. Demuestre todas teorema 2.15.

i∈I

las afirmaciones que no se demostraron en el las afirmaciones que no se demostraron en el las afirmaciones que no se demostraron en el las afirmaciones que no se demostraron en el 39

4. Relaciones de Equivalencia En matem´atica es frecuente que nos interesen s´olo ciertas propiedades de los elementos de un conjunto y que queramos por consiguiente identificar a todos los que comparten dichas propiedades. Por ejemplo, al estudiar las rectas del plano podemos identificar a todas las rectas que son paralelas entre s´ı. Si definimos la relaci´on R como todos los pares de elementos que queremos identificar, R es lo que llamamos una relaci´on de equivalencia. Esta secci´on estudiar´a este concepto. ´ n 2.11. Sea R una relaci´on binaria. Definicio i) R es reflexiva sobre a si ∀x(x ∈ a → hx, xi ∈ R),

R es reflexiva si R es reflexiva sobre Dom R. ii) R es sim´etrica si ∀x∀y(hx, yi ∈ R → hy, xi ∈ R).

iii) R es transitiva si

∀x∀y∀z((hx, yi ∈ R ∧ hy, zi ∈ R) → hx, zi ∈ R).

iv) Una relaci´on R es una relaci´ on de equivalencia si y s´olo si R es reflexiva, sim´etrica y transitiva. Es f´acil demostrar que la reflexividad (sobre su propio campo) es consecuencia de la simetr´ıa y transitividad de la relaci´on (ver ejercicios). Sin embargo, la incluimos en la definici´on porque tradicionalmente se le define as´ı y para hacer hincapi´e en que una relaci´on de equivalencia verifica esta propiedad. Teorema 2.16. Sea R una relaci´ on. i) R es transitiva si y s´olo si R ◦ R ⊆ R. ii) R es sim´etrica si y s´olo si R−1 ⊆ R. iii) R es reflexiva sobre a si y s´olo si Ia ⊆ R. iv) R es de equivalencia si y s´olo si R−1 ◦ R = R. ´ n. Demostracio i) Supongamos que hx, yi ∈ R y hy, zi ∈ R. Entonces hx, zi ∈ R ◦ R = R, luego R es transitiva. ii) y iii), ejercicio. iv) (⇒) Supongamos que R es de equivalencia. Sea hx, yi ∈ R−1 ◦ R, es decir, existe z tal que hx, zi ∈ R−1 y hz, yi ∈ R. Entonces hz, xi ∈ R y por lo tanto, como R es sim´etrica, hx, zi ∈ R y tambi´en hz, yi ∈ R, y como R es transitiva, hx, yi ∈ R. Luego R−1 ◦ R ⊆ R. 40

Sea hx, yi ∈ R. Por simetr´ıa hy, xi ∈ R, luego hx, yi ∈ R−1 y por reflexividad, hy, yi ∈ R. Luego hx, yi ∈ R−1 ◦ R, o sea, R ⊆ R−1 ◦ R y por lo tanto, R = R−1 ◦ R. (⇐) Supongamos que R = R−1 ◦ R. Sea hx, yi ∈ R. Como R = R−1 ◦ R, existe z tal que hx, zi ∈ R−1 y hz, yi ∈ R. Entonces hy, zi ∈ R y hz, xi ∈ R−1 , luego hy, xi ∈ R−1 ◦ R = R. Esto prueba que R es sim´etrica. Por otra parte, como R−1 = (R−1 ◦ R)−1 = R−1 ◦ (R−1 )−1 = R−1 ◦ R = R,

tenemos que

R ◦ R = R−1 ◦ R = R, luego, por i), R es transitiva. Como se mencion´o antes la reflexividad es consecuencia de la simetr´ıa y transitividad. Ver ejercicios. ´ n 2.12. Sea R una relaci´on de equivalencia. Definicio i) Sea x ∈ Dom R. La clase de equivalencia de x se define por [x]R = {y ∈ Cam R : hx, yi ∈ R}.

La clase de equivalencia de x es el conjunto formado por todos los conjuntos relacionados con x . ii) P [R ] = {x ∈ P(Cam R) : ∃y(y ∈ Cam R ∧ x = [y]R )}.

o m´as informalmente

P [R ] = {[y]R : hx, yi ∈ R}.

P [R ] es el conjunto de todas las clases de equivalencia de R . Teorema 2.17. Sea R una relaci´ on de equivalencia y sean x, y ∈ Cam R. i) Dom R = Rec R = Cam R. ii) x ∈ [x]R . iii) hx, yi ∈ R si y s´olo si [x]R = [y]R . iv) Si [x]R ∩ [y]R 6= ∅, entonces [x]R = [y]R . v) Si x ∈ [y]R , entonces [x]R = [y]R . vi) Si x, y ∈ [z]R , entonces [x]R = [y]R . ´ n. Demostraremos s´olo [iii)], el resto del teorema se Demostracio deja como ejercicio. Supongamos que hx, yi ∈ R. 41

Sea z ∈ [x]R . Entonces hx, zi ∈ R, luego hz, xi ∈ R por simetr´ıa y hz, yi ∈ R por transitividad, o sea, z ∈ [y]R . Luego [x]R ⊆ [y]R . Analogamente, [y]R ⊆ [x]R , luego [x]R = [y]R . Supongamos que [x]R = [y]R . Como hy, yi ∈ R, y ∈ [y]R , luego y ∈ [x]R , es decir, hx, yi ∈ R. El teorema anterior nos da las principales propiedades de las clases de equivalencia. ii) nos dice que todo elemento del campo est´a en alguna clase y que toda clase es no vac´ıa. iv) nos dice que dos clases distintas son disjuntas. Estas tres propiedades definen otro importante concepto matem´atico, el de partici´on de un conjunto. ´ n 2.13. Un conjunto P es una partici´on de a si Definicio S i) a = P. ii) ∀x(x ∈ P → x 6= ∅). iii) ∀x∀y((x ∈ P ∧ y ∈ P ∧ x 6= y) → x ∩ y = ∅). Veremos en el pr´oximo teorema la estrecha relaci´on entre los conceptos de relaci´on de equivalencia y de partici´on, a saber, toda relaci´on de equivalencia sobre un conjunto da origen a una u ´nica partici´on de ese conjunto. A la inversa, toda partici´on da origen a una u ´nica relaci´on de equivalencia. Teorema 2.18. i) Sea R una relaci´ on de equivalencia con campo a . Entonces P [R ] es una partici´ on de a . Llamaremos a P [R ] la partici´on asociada a R . ii) Sea P una partici´ on de un conjunto a . Entonces la relaci´ on R[P ] = {hx, yi ∈ a × a : ∃z(z ∈ P ∧ {x, y} ⊆ z})

es una relaci´on de equivalencia en a . Llamaremos a R[P ] la relaci´on de equivalencia asociada a la partici´on P . iii) Dada una partici´on Q de a , P [R[Q ]] = Q. Dada una relaci´ on de equivalencia S , R[P [S ]] = S. ´ n. Demostracio i) Como lo hicimos notar, el teorema 2.17 ii) y iii) demuestra nuestra afirmaci´on. ii) Sea P una partici´on de a . S Para x ∈ a, como a = P , existe z ∈ P tal que x ∈ z, o sea, {x} ⊆ z, luego hx, xi ∈ R[P ] y R[P ] es reflexiva. Si para alg´ un z , {x, y} ⊆ z ∈ P , entonces {y, x} ⊆ z ∈ P , luego R[P ] es sim´etrica. Si existen u1 , u2 ∈ P tales que {x, y} ⊆ u1 y {y, z} ⊆ u2 , entonces u1 ∩ u2 6= ∅ luego u1 = u2 , por lo tanto, {x, z} ⊆ u1 , o sea, R[P ] es transitiva. 42

iii) Ejercicio. iv) Ejercicio.

Ejercicios. 1. Constru´ır todas las clases de equivalencia que pueden existir sobre el conjunto 3 . 2. Demuestre que una relaci´on sim´etrica y transitiva es tambi´en reflexiva (sobre su propio campo). 3. ¿Existe una relaci´on de equivalencia sobre el conjunto ∅ ? 4. Sea a un conjunto. Demostrar que la igualdad de conjuntos es relaci´on de equivalencia sobre Pa . 5. Sea A un conjunto no vac´ıo de relaciones de equivalencia sobre un conjunto a . T (a) Probar que ASes relaci´on de equivalencia sobre a . (b) ¿Lo es siempre A? S (c) Encuentre condiciones para que A sea relaci´on de equivalencia. 6. Sea R una relaci´on sobre a . Probar que si R es transitiva y refleja, entonces R ◦ R = R . ¿ Es cierto el rec´ıproco ? 7. Sean R y S relaciones de equivalencia sobrea a y b respectivamente. Definimos la relaci´on T sobre a × b por: hhc, di, he, f ii ∈ T si y s´olo si c ∈ a , e ∈ a , d ∈ b y f ∈ b , y hc, ei ∈ R y hd, f i ∈ S . Probar que T es de equivalencia. 8. Sean R y S relaciones de equivalencia sobre a . Probar que: (a) R ◦ S es relaci´on de equivalencia sobre a si y s´olo si R ◦ S = S ◦ R. (b) R ∪ S es relaci´on de equivalencia sobre a si y s´olo si R ◦ S ⊆ R ∪ S y S ◦ R ⊆ R ∪ S. (c) Si T y H son relaciones arbitrarias sobre a , entonces si R ⊆ T y R ⊆ H, entonces R ⊆ T ◦ H. 9. Sea F : a −→ b una funci´on y sea R una relaci´on de equivalencia sobre b. Sea c el conjunto {hd, ei ∈ a × a : hF (d), F (e)i ∈ R}. Probar que c es relaci´on de equivalencia sobre a . 10. Sean para cada entero n , los conjuntos bn = {m ∈ Z : ∃ q(m = n + 5q)}. Probar que P = {bn : n ∈ Z} es una partici´on de Z. Determinar una f´ormula para R[P ] . 43

11. Probar que las siguientes relaciones sobre R × R son de equivalencia; determinar la partici´on que determina cada una de ellas, y describir geom´etricamente los elementos de cada partici´on: (a) R = {hha, bi, hc, dii : a2 + b2 = c2 + d2 } . (b) S = {hha, bi, hc, dii : b − a = c − d} . (c) T = {hha, bi, hc, dii : a + b = c + d} . 12. Sea a un conjunto. Probar que Ia y a × a son relaciones de equivalencia sobre a, y describir las particiones correspondientes. 13. Sean P = {ai : i ∈ I} y Q = {bj : j ∈ J} particiones de a y b respectivamente. Probar que {ai × bj : hi, ji ∈ I × J} es una partici´on de a × b. 14. Sea F : a −→ b una funci´on, y sean {ai : i ∈ I} y {bj : j ∈ J} particiones de a y b respectivamente. Probar que: (a) Si F es sobre, entonces {F −1∗ bj : j ∈ J} es una partici´on de a . (b) Si F es inyectiva, entonces F ∗ ai : i ∈ I} es una partici´on de Rec F . 15. Sean R y S relaciones de equivalencia sobre a . Probar que: (a) [x]R∩S = [x]R ∩ [x]S , para todo x en a . (b) Si R ∪ S es de equivalencia, entonces [x]R∪S = [x]R ∪ [x]S , para todo x en a . 16. Si F : a −→ b es una funci´on, definamos la relaci´on R = {hc, di : F (c) = F (d)}. (a) Probar que R es de equivalencia sobre a . R se dice la relaci´on de equivalencia determinada por F y se denota por R [F ]. (b) Probar que R [F ] = F −1 ◦ F . (c) Si F : a −→ b y G : b −→ c son funciones, determinar R [G ◦ F ] usando R [G] y F . 17. Demuestre todas las afirmaciones que no se demostraron en el teorema 2.16. 18. Demuestre todas las afirmaciones que no se demostraron en el teorema 2.17. 19. Demuestre todas las afirmaciones que no se demostraron en el teorema 2.18. 5. Relaciones de Orden ´ n 2.14. Sea R una relaci´on binaria. Definicio i) R es antisim´etrica si ∀x∀y((xRy ∧ yRx) → x = y). 44

ii) R es conexa si ∀x∀y(xRy ∨ yRx ∨ x = y).

iii) R es un orden parcial si R es reflexiva, antisim´etrica y transitiva. iv) R es un orden total si R es un orden parcial conexo. v) Si Dom R = a decimos que R es un orden (parcial, total) sobre a . Decimos tambi´en que a est´a parcial o totalmente ordenado por R . vi) Si R es un orden, en lugar de escribir hx, yi ∈ R, escribiremos x R y. Habitualmente los ´ordenes se designan con los s´ımbolos ≤ o 4. Ejemplo. i) Los n´ umeros reales con su orden usual constituyen un conjunto totalmente ordenado. ii) Los n´ umeros naturales se pueden ordenar parcialmente de la siguiente manera, dados dos n´ umeros naturales n y m definimos. n4m

si y s´olo si

n|m.

A menudo representamos ´ordenes mediante diagramas que consisten de nodos unidos por l´ıneas. Los nodos representan conjuntos pertenecientes campo de la relaci´on R y las l´ıneas al orden mismo, as´ı, si ha, bi ∈ R, habr´a dos nodos unidos por una l´ınea (ver figura). Mientras m´as arriba aparezca un conjunto en el diagrama, m´as “grande” es.

Los diagramas de la figura representan a los ordenes

y

R = {ha, ai, hb, bi, ha, bi} S = {ha, ai, hb, bi, hc, ci, hd, di, he, ei, ha, bi, ha, ci, ha, di, ha, ei, hb, di, hc, di, hc, ei}, 45

´ n 2.15. Definicio i) Una relaci´on R es asim´etrica sobre a si y s´olo si ∀x∀y((x ∈ a ∧ y ∈ a ∧ xRy) → ¬ yRx). ii) Una relaci´on es un orden estricto si es transitiva y asim´etrica sobre su campo. Teorema 2.19. i) Si ≤ es un orden (parcial), entonces la relaci´on definida por x
si y s´olo si x ≤ y ∧ x 6= y

es un orden estricto cuyo campo es el mismo que el de ≤ . ii) Si R es un orden estricto, entonces la relaci´ on definida por xSy

si y s´olo si

xRy ∨ x = y,

es un orden parcial cuyo campo es el mismo que el de R . ´ n. Demostracio i) Ejercicio. ii) S es obviamente reflexiva. Supongamos que xSy, ySx pero x 6= y. Entonces xRy y yRx, una contradicci´on ya que R es asim´etrica. Por lo tanto si xSy y ySx, x = y, o sea, S es antisim´etrica. S es transitiva ya que R lo es.

El m´as t´ıpico ejemplo de orden parcial es la relaci´on de inclusi´on ⊆ definida sobre el conjunto potencia de alg´ un conjunto. Para ver hasta qu´e punto este es el ejemplo t´ıpico de orden necesitamos primero una definici´on. ´ n 2.16. Sean R y S dos relaciones. Una funci´on F : Definicio Cam R −→ Cam S es un isomorfismo entre R y S si y s´olo si F es biyectiva y para todo a, b ∈ Cam R aRb

si y s´olo si

F (a) S F (b).

Si tal F existe, decimos que R y S son relaciones isomorfas. Si R y S son ´ordenes decimos tambi´en que F es un isomorfismo de orden. Teorema 2.20. Sea ≤ una relaci´ on de orden. Entonces existe un conjunto a tal que ≤ es isomorfo con S = {hx, yi ∈ a × a : x ⊆ y}. 46

´ n. Sea b = Cam ≤. Para cualquier conjunto x Demostracio definimos yx = {z ∈ b : z ≤ x}. Notemos que ´esta es una f´ormula funcional. Luego por el axioma de reemplazo y dado que b es un conjunto a = {{z ∈ b : z ≤ x} : x ∈ b}, tambi´en es un conjunto. Consideremos la relaci´on S = {hx, yi ∈ a × a : x ⊆ y}. Entonces campo S = a. Definimos F : b −→ a x 7−→ {z ∈ b : z ≤ x}. Observemos que por reflexividad de ≤ , para todo x ∈ b, x ∈ F (x). Supongamos que x 6= y. Entonces por antisimetr´ıa de ≤ , o bien x 6≤ y o bien y 6≤ x, es decir, x ∈ / F (y) ´o y ∈ / F (x), lo que unido a la observaci´on anterior demuestra que F (x) 6= F (y), es decir, F es 1–1. Por otra parte, por definici´on, F es sobreyectiva, luego F es una biyecci´on. Si x, y ∈ b y x ≤ y, entonces por transitividad de ≤ , F (x) ⊆ F (y), es decir, F (x) S F (y). Si F (x) ⊆ F (y), entonces como x ∈ F (x), x ∈ F (y), o sea x ≤ y, por lo tanto xRy si y s´olo si F (x) S F (y), o lo que es lo mismo, F es un isomorfismo. A menudo nos encontramos con relaciones reflexivas y transitivas pero no antisim´etricas (tal tipo de relaci´on se llama un preorden). Podemos obtener una relaci´on de equivalencia a partir de un preorden y ordenar las clases de una manera coherente con el preorden de la manera indicada en el siguiente teorema. Esta construcci´on es bastante com´ un en matem´atica. Teorema 2.21. Sea 4 una relaci´ on transitiva y reflexiva con campo a . Sea S = {hx, yi ∈ a × a : x 4 y ∧ y 4 x}. Entonces S es una relaci´on de equivalencia. M´as a´ un, si definimos [x]S ≤ [y]S si y s´olo si x 4 y, entonces ≤ es un orden parcial sobre P [S ]. 47

´ n. S es obviamente reflexiva y sim´etrica. Demostracio Supongamos que xSy y ySz. Entonces x 4 y, y 4 x, y 4 z y z 4 y, y como 4 es transitiva, x 4 z y z 4 x, o sea, xSz, lo que demuestra que S es transitiva. Para demostrar que ≤ es un orden parcial, sean [x]S ≤ [y]S y [y]S ≤ [z]S . Entonces x 4 y y y 4 z y como 4 es transitiva x 4 z, luego [x]S ≤ [z]S . Supongamos [x]S ≤ [y]S y [y]S ≤ [x]S . Entonces x 4 y y y 4 x, es decir xSy. Luego [x]S = [y]S , o sea, ≤ es antisim´etrica. Por u ´ltimo es f´acil ver que ≤ es reflexiva ya que 4 lo es. ´ n 2.17. Sea ≤ un orden parcial con campo A. SupongaDefinicio mos que X ⊆ A y a ∈ A. i) a es una cota superior de X si ∀x(x ∈ X → x ≤ a). ii) a es una cota inferior de X si ∀x(x ∈ X → a ≤ x). iii) a es el supremo de X si a es la menor cota superior de X . iv) a es el ´ınfimo de X si a es la mayor cota inferior. v) a es un elemento minimal de X si a ∈ X ∧∀x(x ∈ X → x  a). vi) a es un elemento maximal de X si a ∈ X ∧∀x(x ∈ X → a  x). Los conceptos de cota superior, cota inferior, supremo e ´ınfimo son probablemente familiares para el lector. N´otese que si un conjunto tiene supremo o ´ınfimo, ´estos son u ´nicos. Tambi´en es interesante recalcar que los elementos minimales no tienen por qu´e ser el menor elemento del conjunto de hecho, este ni siquiera tiene que existir. En el ejemplo de la figura a y b son minimales

El siguiente teorema de punto fijo tiene muchas aplicaciones. El argumento usado en su demostraci´on se usa frecuentemente. Teorema 2.22. Sea ≤ un orden parcial con campo A y supon gamos que todo subconjunto de A tiene supremo. Sea F : A −→ A tal que x ≤ y → F (x) ≤ F (y). Entonces para alg´ un x ∈ A, F (x) = x. 48

´ n. Observemos primero que A tiene que tener un Demostracio menor elemento. En efecto, es obvio que todos los elementos de A son cota superior de ∅, pues si a ∈ A no lo fuera, existir´ıa x ∈ ∅ tal que x 6≤ a lo que es imposible. Como ∅ ⊆ A, por hip´otesis tiene un supremo s , este es la menor de las cotas superiores, luego tiene que ser el menor elemento de A . Sea B = {x ∈ A : x ≤ F (x)}. Entonces B ⊆ A y B tiene supremo. Llamemos a al supremo de B . Obs´ervese que B 6= ∅, ya que s ≤ F s, donde s es el menor elemento de A . Entonces para todo x ∈ B, x ≤ a y x ≤ F (x) ≤ F (a), luego F (a) es cota superior de B y tenemos a ≤ F (a). Por otra parte si a ≤ F (a), F (a) ≤ F F (a) y por lo tanto F (a) ∈ B, luego F (a) ≤ a, es decir, a = F (a). El concepto definido a continuaci´on es el origen de toda la teor´ıa de los n´ umeros ordinales que estudiaremos en el pr´oximo cap´ıtulo. Como veremos es una abstracci´on de la conocida propiedad del orden de los n´ umeros naturales: todo subconjunto no vac´ıo de n´ umeros naturales tiene un menor elemento. ´ n 2.18. Sea R una relaci´on. Definicio i) R es bien fundada si para todo ∅ 6= A ⊆ Cam R, existe a ∈ A tal que A ∩ {x ∈ Cam R : xRa} = ∅. ii) ≤ es un buen orden si < es un orden total bien fundado.

N´otese la similitud de la definici´on de relaci´on bien fundada con la formulaci´on del axioma de regularidad. De hecho el axioma de regularidad dice que la relaci´on {hx, yi ∈ a : x ∈ y} para cualquier conjunto a es bien fundada.

Teorema 2.23. Para un orden parcial ≤ las siguientes condiciones son equivalentes. i) ≤ es un buen orden. ii) ≤ es un orden total y todo subconjunto no vac´ıo del campo de ≤ tiene un menor elemento. iii) Todo subconjunto no vac´ıo del campo de ≤ tiene un menor elemento. ´ n.i)⇒ii) Sea A ⊆ Cam ≤. Escojemos a ∈ A tal Demostracio que A ∩ {x ∈ Cam ≤ : x < a} = ∅, es decir para todo x ∈ A, x 6≤ a y como el orden es total, a ≤ x, es decir a es el menor elemento de A . 49

ii)⇒iii) Obvio. iii)⇒i) Dados dos elementos x, y ∈ Cam ≤, consideramos {x, y}, ´este tiene un menor elemento luego x ≤ y o y ≤ x, o sea, ≤ es orden total. Sea A ⊆ Cam ≤ y sea a su menor elemento. Entonces es claro que A ∩ {x ∈ Cam ≤ : x < a} = ∅, es decir ≤ es bien fundado.

Ejercicios. 1. Sean a , b , c y d cuatro conjuntos distintos. ¿Cu´antos ordenes parciales existen sobre {a, b}? ¿Sobre {a, b, c}? ¿Sobre {a, b, c, d}? Haga los diagramas correspondientes. 2. Diga cu´ales de los ´ordenes del ejercicio anterior son isomorfos. 3. Sea a un conjunto con n elementos. Probar que un orden total sobre a contiene 12 n(n − 1) pares ordenados. 4. Probar que una relaci´on R sobre a es antisim´etrica si y s´olo si R ∩ R−1 ⊆ Ia . 5. Considere las siguientes relaciones sobre el conjunto 8 = {0, 1, 2, 3, 4, 5, 6, 7}: (a) x R1 y si y s´olo si y − x ∈ 8. (b) x R2 y si y s´olo si y − x ∈ 8 y y − x 6= 0. (c) x R3 y si y s´olo si y − x = 0. (d) x R4 y si y s´olo si y − x es un entero par. (e) x R6 y si y s´olo si y − x = 1. Determinar cu´ales de estas relaciones son antisim´etricas, asim´etricas, transitivas, conexas, reflejas, de equivalencia o de orden. 6. Si R y S son relaciones y a un conjunto, probar que: (a) Si R es asim´etrica, entonces R es antisim´etrica. (b) Ia es sim´etrica y antisim´etrica. (c) Si R , es sim´etrica y antisim´etrica, entonces existe un conjunto b tal que R = Ib . (d) Si R es asim´etrica, entonces R−1 , R ∩ S y R − S son asim´etricas. 50

7.

8. 9. 10.

11. 12.

13. 14.

15. 16.

(e) Si R es antisim´etrica, entonces R−1 , R ∩ S y R − S son antisim´etricas. (f) Si R es transitiva, entonces R−1 es transitiva. (g) Si R es conexa, entonces R−1 es conexa. (h) Si R es asim´etrica, entonces R ∪ ICam R es antisim´etrica. (i) Si R es antisim´etrica, entonces R − ICam R es asim´etrica. (j) Si R es transitiva y antisim´etrica, entonces R − ICam R es transitiva. Dar contraejemplos para las siguientes afirmaciones: (a) Si R y S son asim´etricas, entonces S ◦ R y R ∪ S son asim´etricas. (b) Si R y S son antisim´etricas, entonces R ∪ S es antisim´etrica. (c) Si R y S son transitivas, entonces R ∪ S y R − S y S ◦ R son transitivas. (d) Si R y S son conexas, entonces R ∪ S y R − S y S ◦ R son conexas. ¿ Es ∅ un orden ? Si a es un conjunto no vac´ıo de ´ordenes sobre un conjunto b , T probar que a es un orden sobre b. Si R es un orden sobre a y b ⊆ a, probar que R ∩ (b × b) es un orden sobre b y que si R es total, entonces R ∩ (b × b) tambi´en lo es. Probar que R−1 es un orden sobre a si y s´olo si R es un orden sobre a . Si R es un orden sobre a, probar que R −Ia es un orden estricto S sobre a y si R es un orden estricto sobre a , probar que R Ia es un orden (parcial) sobre a . ¿ Es ∅ un orden estricto ? Sean P1 y P2 particiones de a . Se dice que P1 es m´as fina que P2 si y s´olo si u ∈ P1 implica u ⊆ v para alg´ un v en P2 . Probar que la relaci´on “es m´as fina que” es un orden sobre el conjunto de todas las particiones de a . Dar un ejemplo de un S conjunto a y un conjunto S de ´ordenes sobre a , tales que S no es un orden sobre a . Determinar cu´ales de las siguientes relaciones sobre Z son ´ordenes y si lo es, de qu´e tipo de orden se trata: (a) R = {hx, yi : x + y < 3}. (b) R = {hx, yi : x divide a y}. (c) R = {hx, yi : x + y es par }. (d) R = {hx, yi : x + y es par y x es un m´ ultiplo de y }. (e) R = {hx, yi : y = x + 1}. 51

17. Sea R una relaci´on sobre a . Probar que R es de orden si y s´olo si R ∩ R−1 = Ia y R ◦ R = R. 18. Sea < un orden estricto sobre a y sea b ∈ / a . Definimos <1 sobre c = a ∪ {b} por: x <1 y si y s´olo si (x, y ∈ a ∧ x ≤ y) ∨ (y = b ∧ x ∈ a).

19. 20.

21.

22.

23.

24. 25.

26.

27.

Mostrar que <1 es un orden estricto sobre c y que la intersecci´on entre el orden <1 y a × a es el orden <. Dar un contraejemplo de: Si R − ICam R es un orden parcial estricto, entonces R es un orden parcial. Probar que si Ro es el conjunto de todos los ´ordenes sobre a y Re es el conjunto de todos los ´ordenes estrictos sobre a, entonces existe una biyecci´on entre Ro y Re . Sean x = {a, b, c, d, e} y S = {ha, ci, hb, ci, hd, ei}. Probar que S es un orden estricto para x , no es total y que x tiene tres elementos minimales y dos maximales. Sea a un conjunto ordenado tal que todo subconjunto no vac´ıo de a con alguna cota superior en a tiene supremo en a . Probar que todo subconjunto no vac´ıo de a con alguna cota inferior en a tiene ´ınfimo en a . Sea h≤i : i ∈ Ii una familia de ´ordenes sobre a totalmente S ordenada por inclusi´on. Probar que i∈I ≤i es un orden sobre a. Sea R un orden sobre a y sea b un subconjunto de a. Probar que c es el menor elemento de b si y s´olo si R∗ ( R ∩ ({c} × b)) = B. Consideremos ≤i orden sobre ai , con i ∈ {1, 2, 3}. Probar que: (a) Si F : a1 −→ a2 es isomorfismo, F −1 : a2 −→ a1 tambi´en es isomorfismo. (b) Si F : a1 −→ a2 y G : a2 −→ a3 son isomorfismos, entonces G ◦ F : a1 −→ a3 es isomorfismo. Sea ≤ un orden sobre a . Definamos Sb = {x ∈ a : a ≤ a}, para cada b en a . Probar que si hSb : b ∈ ai est´a ordenado por inclusi´on, entonces hSb : b ∈ ai es isomorfo a a . Sean ≤1 y ≤2 ´ordenes sobre a1 y a2 respectivamente. Sea F : a1 −→ a2 un isomorfismo entre ≤1 y ≤2 . Probar que: (a) a es un elemento maximal (resp. minimal) en a1 si y s´olo si F (a) es maximal (resp. minimal) en a2 . (b) Si b ⊆ a1 , entonces c es una cota superior (resp. inferior) de b en a si y s´olo si F (c) es una cota superior (resp. inferior) de F ∗ b en a2 . 52

(c) Si b ⊆ a1 , entonces c es el supremo (resp. ´ınfimo) de b en a si y s´olo si F (c) es el supremo (resp. ´ınfimo) de F ∗ b en a2 . 28. Sea a un conjunto ordenado. Probar que: (a) Si todo subconjunto de a tiene ´ınfimo, entonces a tiene un mayor elemento. (b) Todo subconjunto de a tiene supremo si y s´olo si todo subconjunto de a tiene ´ınfimo. 29. Sea 4 relaci´on sobre N × N dada por: hm, ni 4 hp, qi si y s´olo si m < n ´o m = p y n ≤ q, donde ≤ es el orden usual sobre N. (a) Probar que 4 es un orden sobre N × N. (b) Encontrar todos los elementos minimales de N×N . ¿Tiene N × N un menor elemento ? (c) Sea a = {1, 2} × {1, 2}. Encontrar todas las cotas de a . ¿ Tiene a supremo o ´ınfimo ? Encontrar todos los elementos minimales y maximales de a . 30. Sea 4 relaci´on sobre N × N dada por: hm, ni 4 hp, qi si y s´olo si m ≤ p y n ≤ q, donde ≤ es el orden usual sobre N. (a) Probar que 4 es un orden sobre N × N. (b) Si a es un subconjunto no vac´ıo de N × N que tiene alguna cota superior, entonces a tiene supremo. (c) Si a es un subconjunto no vac´ıo de N × N, entonces a tiene ´ınfimo. (d) Dar un ejemplo de un subconjunto no vac´ıo de N × N que tenga cotas superiores e inferiores pero que no tenga menor elemento ni mayor elemento. 31. Sea R un orden sobre a . Definimos una relaci´on S sobre Pa por: uS v si y s´olo si u = v o bien existe w ∈ v tal que u = {c : c ∈ v ∧ c R w}. Probar que: (a) S es un orden sobre Pa . S (b) Si S d ⊆ b tal que S es un orden sobre d, entonces d∈b y d es cota superior de d . 32. Sea R un orden sobre a y sea b ⊆ a. Probar que: 53

33.

34.

35. 36.

37.

38. 39. 40. 41.

42.

(a) c es el menor elemento de b respecto de R si y s´olo si es el mayor elemento de b respecto de R−1 . (b) An´alogo para elementos minimales y maximales, para cotas superiores e inferiores y para supremos e ´ınfimos. Dar ejemplos de ´ordenes sobre conjuntos finitos a y subconjuntos b de a tales que: (a) b tiene un mayor elemento pero no menor elemento. (b) b tiene un menor elemento pero no tiene mayor elemento. Sea Pb , con b 6= ∅ ordenado por inclusi´on y sea c ∈ Pb. Probar Sque: (a) T c es el supremo de c. (b) c es el ´ınfimo de c, si c 6= ∅. (c) El ´ınfimo de ∅ es Pb. Probar que todo subconjunto de un conjunto bien ordenado est´a bien ordenado. Sea ≤ un orden para a . Definimos el segmento inicial de b : Sb = {x ∈ a : x < b}. Dado b ∈ a , a bien ordenado, probar que todo segmento inicial de Sb es a su vez segmento inicial de a , y que todo segmento incial de a contiene a Sb o es segmento inicial de Sb . Sea a un conjunto totalmente ordenado. Probar que el orden de a es un buen orden si y s´olo si todo segmento inicial de a est´a un bien ordenado por (la restricci´on de) el orden de a . Si ≤ es buen orden sobre a y F es un isomorfismo entre a y un subconjunto de a , entonces x ≤ F (x) para todo x ∈ a. Probar que ning´ un conjunto con un buen orden es isomorfo a un segmento inicial de s´ı mismo. Probar que entre dos buenos ´ordenes hay, a lo m´as, un isomorfismo. Sean ≤1 y ≤2 buenos ´ordenes sobre a1 y a2 respectivamente. Probar que si a1 con ≤1 es isomorfo a un subconjunto de a2 con ≤2 , y a2 con ≤2 es isomorfo a un subconjunto de a1 con ≤1 , entonces ≤1 y ≤2 son isomorfos sobre a1 y a2 . Sea ≤A un orden total sobre A y ≤B un orden total sobre B . Definimos

ha1 , b1 i 4 ha2 , b2 i si y s´olo si a1 ≤A a2 ∨ a1 = a2 ∧ b1 ≤B b2 . Demuestre que la relaci´on as´ı definida es un orden total sobre A × B. Este orden se llama orden lexicogr´ afico. Demuestre que si ≤A y ≤B son buenos ordenes, el orden lexicogr´afico tambi´en es un buen orden. 54

43. Demuestre que la relaci´on definida sobre los n´ umeros naturales en 5 es efectivamente un orden. 44. Demuestre todas las afirmaciones que no se demostraron en el teorema 2.16. 45. Demuestre todas las afirmaciones que no se demostraron en el teorema 2.17. 46. Demuestre que la relaci´on ≤ definida en el teorema 2.21 es efectivamente un conjunto. 47. Demuestre que el supremo y el ´ınfimo, con respecto a cualquier orden, de un conjunto A , si existen, son u ´nicos.

55

56

CAPITULO 3

Ordinales En este cap´ıtulo estudiaremos un tema un poco m´as avanzado de teor´ıa de conjuntos. El lector est´a seguramente familiarizado con los n´ umeros naturales. Los n´ umeros naturales nos sirven para contar y para ordenar los conjuntos finitos. Es esta segunda propiedad la que trataremos de generalizar para conjuntos infinitos, empezaremos por construir dentro de nuestra teor´ıa el conjunto de los n´ umeros naturales. 1. N´ umeros Naturales Formalizaremos ahora el concepto intuitivo de n´ umero natural dentro de la teor´ıa ZF. ´ n 3.1. El sucesor de un conjunto x es el conjunto Definicio Sx = x ∪ {x}. Obs´ervese que si x es un conjunto, Sx tambi´en lo es (¿Por qu´e?). ´ n 3.2. Definicio 0 1 2 3

= = = = .. .

∅ S0 = {∅} S1 = {∅, {∅}} S2 = {∅, {∅}, {∅, {∅}}}

Cada uno de estos conjuntos es un n´ umero natural. La definici´on anterior introduce todos los n´ umeros naturales en forma bastante sencilla. Debemos destacar algunas caracter´ısticas de ´esta. En primer lugar 0 es un n´ umero natural. En segundo lugar, si n es un n´ umero natural, su sucesor tambi´en lo es. En tercer lugar todo n´ umero natural corresponde a una de esas dos posibilidades, o es 0 o es el sucesor de alg´ un otro n´ umero. Una segunda observaci´on en el plano intuitivo (y que formalizaremos en el cap´ıtulo 5), es que el n´ umero natural n contiene n elementos 57

i.e. 0 no tiene elementos, 1 tienen un elemento, 2 tiene dos elementos, etc. M´as a´ un, n´otese que 1 = {0} 2 = {0, 1} 3 = {0, 1, 2} .. . En general, Sn = {0, 1, . . . , n} , todo n´ umero natural esta formado por los naturales que lo preceden, salvo el 0 uqe no contiene ning´ un elemento. Hasta ahora hemos construido cada uno de los n´ umeros naturales. ¿Existe un conjunto que contenga a todos y solamente a los n´ umeros naturales? La respuesta es s´ı pero dista de ser obvia, de hecho se necesita el Axioma de Infinito para poder construir el conjunto de los n´ umeros naturales. ´ n 3.3. Decimos que X es inductivo si Definicio i) 0 ∈ X. ii) Si x ∈ X, entonces Sx ∈ X. El axioma de infinito nos dice precisamente que existe al menos un conjunto inductivo. Llamemoslo I. ´ n 3.4. El conjunto ω de los n´ Definicio umeros naturales se define como sigue: ω = ∩{x ∈ PI : x es inductivo} Obs´ervese ω es inductivo y que si X es inductivo, ω ⊆ X, es decir, ω es el m´as peque˜ no de los conjuntos inductivos. Por la manera en que definimos los n´ umeros naturales, es claro que todo conjunto inductivo, en particular ω , contiene a todos los n´ umeros naturales. Por otra parte, ning´ un conjunto que no sea un n´ umero natural pertenece a ω . Esto quedar´a m´as claro si demostramos primero el siguiente teorema, del que derivan las propiedades que m´as nos interesan de los n´ umeros naturales, conocido como Principio de Inducci´on. En adelante nos referiremos a el simplemente como P.I. Teorema 3.1. (Principio de Inducci´ on) Sea ϕ(x) una f´ormula con una variable libre x . Supongamos que i) ϕ(0) se verifica. 58

ii) Para todo n ∈ ω si ϕ(n) se verifica, entonces ϕ(Sn) tambi´en se verifica. Entonces ϕ(n) se verifica para todo n ∈ ω. El P.I. puede ser enunciado en t´erminos de la relaci´on de pertenencia. En este caso, resulta m´as evidente que P.I. simplemente afirma que ω es el menor conjunto inductivo. Las dos maneras de enunciar el principio son equivalentes, (ver ejercicios.) Teorema 3.2. (Principio de Inducci´ on) Sea B un conjunto tal que i) 0 ∈ B. ii) Para todo n , si n ∈ B , entonces Sn ∈ B. Entonces ω ⊆ B. Ejemplo Si x ∈ ω, entonces x = 0 o bien x es el sucesor de un n´ umero natural. ´ n. Sea Demostracio B = {x ∈ ω : x = 0 ´o x es el sucesor de un n´ umero natural}. Es claro que B es inductivo, luego ω ⊆ B ⊆ ω. Resulta interesante notar que 0 ∈ 1 ∈ 2 ∈ 3 ∈ · · · y tambi´en o ⊆ 1 ⊆ 2 ⊆ 3 · · · Esta observaci´on nos da la intuici´on de que la relaci´on de pertenencia entre naturales define una noci´on de orden apropiada. En estricto rigor, la verdad es todo lo contrario, los n´ umeros naturales se definen as´ı para que la relaci´on de pertenencia sea un orden con buenas propiedades. ´ n 3.5. La relaci´on ≤ se define en ω por: Definicio m≤n

ssi m ∈ n o bien m = n.

Diremos que m es menor o igual que n . Tambi´en usaremos el s´ımbolo < para denotar m
ssi m ≤ n y m 6= n.

ssi m ∈ n.

Debemos demostrar que esta relaci´on es un orden lineal, m´as a´ un, que es un buen orden. Lema 3.3. Para todo n, m ∈ ω, 59

i) ii) iii) iv)

0 ≤ n. Si x ∈ n, entonces x ∈ ω. m < Sn ssi m ≤ n. Si n < m, entonces Sn ≤ m.

´ n. Demostracio i) Por inducci´on con ϕ(x) = 0 ≤ x. – ϕ(0) se verifica. – Supongamos ahora que ϕ(n) se verifica. Es decir, 0 ≤ n, o sea 0 ∈ n ´o 0 = n. En cualquier caso 0 ∈ n ∪ {n} = Sn, o sea ϕ(Sn) se verifica. Luego, en virtud de P.I., para todo n ∈ ω, 0 ≤ n. ii) Por inducci´on sobre n . Sea ϕ(x) = ∀y(y < x → y ∈ ω)

– ϕ(0) se verifica trivialmente. – Supongamos ϕ(m) y sea y ∈ Sm. Entonces y ∈ m ´o y = m. Si y ∈ m, por hip´otesis de inducci´on, y ∈ ω. Si y = m, entonces y ∈ ω. En cualquier caso y ∈ ω. Luego por P.I., todo n ∈ ω verifica ϕ(x) iii) m < Sn ssi m ∈ Sn = n ∪ {n} sii m ≤ n. iv) Por inducci´on sobre m . Consideramos ϕ(x) = ∀y(y < x → Sy ≤ x).

– ϕ(0) se verifica trivialmente. – Supongamos ϕ(m), o sea, ∀y(y < m → Sy ≤ m). Supongamos pues que y < Sm y recordemos que esto ocurre si y s´olo si y ∈ m o y = m. Si y ∈ m, por hip´otesis de inducci´on, Sy ≤ m y luego Sy ≤ Sm. Si y = m, entonces Sy = Sm. En cualquier caso, si y < Sm, entonces Sy ≤ Sm, es decir, ϕ(Sm) se verifica. Luego por P.I., para todo m ∈ ω, ϕ(m) se verifica. Teorema 3.4. ≤ es un orden total sobre ω .

´ n. Demostracio i) ≤ es obviamente reflexiva. ii) ≤ es antisim´etrica. En efecto, supongamos que m ≤ n y n ≤ m, pero m 6= n. Entonces m ∈ n y n ∈ m lo que contradice el teorema 1.3. iii) ≤ es transitiva. Supongamos que k ≤ m y m ≤ n. Demostraremos que k ≤ n por inducci´on sobre n . Para ello sea ϕ(x) = ∀y∀z((z ≤ y ∧ y ≤ x) → z ≤ x). 60

– ϕ(0) se verifica ya que si k ≤ m y m ≤ 0, m = 0 luego k ≤ 0. – Si ϕ(n) se verifica, consideremos k ≤ m y m ≤ Sn. Entonces m < Sn ´o m = Sn. Si m < Sn, entonces por el lema 3.3 iii), m ≤ n y por hip´otesis de inducci´on k ≤ n. Es decir k ∈ n ´o k = n. En cualquier caso k ∈ Sn, o sea, k ≤ Sn. Si m = Sn, como k ∈ m ´o k = m tenemos k ∈ Sn ´o k = Sn, es decir, k ≤ Sn. Esto completa la inducci´on, luego todo n´ umero natural n verifica ϕ(n), o sea, ≤ es transitiva. iv) ≤es un orden total. Sean m y n dos n´ umeros naturales. Demostraremos por inducci´on sobre n que m < n ´o m = n ´o n < m. Para ello sea ϕ(x) = ∀y(y < x ∨ y = x ∨ x < y) – ϕ(0) se verifica por el lema 3.3 i). – Supongamos ϕ(n) se verifica. Entonces para todo m, m < n ´o m = n ´o n < m. Si m < n ´o m = n, entonces m ∈ Sn, luego m < Sn. Si n < m, entonces Sn ≤ m por el lema 3.3 iv). Luego por P.I., ≤ es un orden total sobre ω . Para verificar que ≤ es un buen orden, resulta m´as f´acil demostrar primero otra versi´on del Principio de Inducci´on. Para distinguirlo de P.I., lo llamaremos Principio de Inducci´on Completa. Debemos recordar siempre que este nuevo principio es equivalente con P.I. Demostraremos a continuaci´on una de las implicaciones, la otra se deja como ejercicio. Teorema 3.5. (Principio de Inducci´ on Completa). Sea ϕ(x) una f´ormula con una variable libre x . Supongamos que (∗ ) si ϕ(k) se verifica para todo k < n, entonces ϕ(n) tambi´en se verifica. Entonces para todo n ∈ ω, se verifica ϕ(n). ´ n. Demostramos primero por inducci´on que para Demostracio todo n ∈ ω se cumple ψ(n) donde ψ(x) = ∀y(y < x → ϕ(y)) i) ψ(0) se cumple trivialmente ya que no existe m < 0. 61

ii) Supongamos ψ(n) se verifica. Entonces por (∗), ϕ(n) tambi´en, pero por el lema 3.3 iii), para todo n y < Sn → (y < n ∨ y = n),

luego ∀y(y < Sn → ϕ(y)), es decir ψ(Sn) es cierta. Esto completa nuestra inducci´on, o sea para todo n ∈ ω, se verifica, en particular, ψ(Sn), y como n < Sn, esto garantiza que se verifica ϕ(n). El principio de Inducci´on Completa tambi´en puede plantearse en terminos de la relaci´on de pertenencia. Teorema 3.6. Sea B ⊆ ω tal que (∗ ) si {k ∈ ω : k < n} ⊆ B, entonces n ∈ B. Entonces B = ω. Teorema 3.7. ≤ es un buen orden. ´ n. Hemos visto que ≤ es un orden total. Debemos Demostracio demostrar que ≤ es bien fundado, es decir, que si X ⊆ ω, X 6= ∅, entonces X tiene un menor elemento. Para ello suponemos que X no tiene menor elemento y aplicamos el Principio de Inducci´on Completa 3.6 a X ∈ ω − X) Dado n , si para todo k < n , k ∈ ω − X , entonces n ∈ ω − X porque, si no, n es el menor elemento de X, luego ω −X = ω, es decir, X = ∅ , lo que es una contradicci´on. Por lo tanto todo subconjunto no vac´ıo de ω tiene un menor elemento y ≤ es un buen orden. Volveremos sobre estas propiedades en un contexto m´as general en las pr´oximas secciones. Teorema 3.8. Si un subconjunto de ω tiene una cota superior, entonces tiene un m´aximo elemento. ´ n. Sea X ⊆ ω, X 6= ∅, definimos Demostracio Y = {x ∈ ω : x es cota superior de X}.

Por hip´otesis Y 6= ∅. Sea m el menor elemento de Y . Por definici´on m es el supremo de X. Debemos demostrar que m ∈ X. Si m = 0, entonces para todo x ∈ X, x ≤ 0, o sea X = ∅ o bien X = {0}. El primer caso no ocurre por hip´otesis y en el segundo, 0 es el m´aximo de X. Si m 6= 0, entonces m = Sn para alg´ un n. Pero entonces si m∈ / X, n es cota superior de X y n < m, una contradicci´on. Luego m ∈ X y es el mayor elemento de X. 62

Ejercicios. 1. Demuestre la equivalencia de las dos maneras de enunciar el Principio de Inducci´on dadas en el texto, es decir los teoremas 3.1 y 3.2. 2. Demuestre el Principio de Inducci´on Completa a partir del teorema 3.7 3. Demuestre la equivalencia de las dos maneras de enunciar el Principio de Inducci´on Completa dados en el texto, es decir los teoremas 3.5 y 3.6. 4. Sea hai : i ∈ ωi una familia de conjuntos tal que para todo i ∈ ω, ai ⊂ aSi . Probar que a0 ⊂ an para todo n ∈ ω − 1. 5. Sea hai : i ∈ ωi una S familia de conjuntos tal que para todo i ∈ ω , ai ⊆ aSi y i∈ω ai ⊆ a0 . Probar que ai = a0 para todo i en ω. S S 6. Probar que si n ∈ ω, Sn = nS y que ω = ω. 7. Probar que si a ⊆ ω, a 6= ∅ y a = a , entonces a = ω. 8. Probar que si  m y n est´an en ω y m 6= n , entonces: m si n ∈ m, (a) m ∪ n = n si m ∈ n.  n si n ∈ m, (b) m ∩ n = m si m ∈ n. 9. Probar que si n ∈ m y n 6= 0 , entonces existe un mayor elemento en n . 10. Si a ⊆ b ⊆ ω son no vac´ıos, n es el menor elemento de a y m es el menor elemento de b , ¿cu´al es la relaci´on entre n y m ? Justificar y responder para los mayores elementos de a y de b si estos existen. 11. Probar que si n ∈ ω , entonces no existe k ∈ ω tal que n < k < Sn. 12. Probar que si n y m est´an en ω y n < m , entonces Sn < Sm. 13. Probar que no existe una funci´on F : ω −→ ω tal que para todo n ∈ ω, F (Sn) < F (n). 14. Probar que si ϕ(x) es una f´ormula con variable libre x y existe un k ∈ ω , tal que (a) ϕ(k) se verifica y (b) para todo n ∈ ω tal que k ≤ n, si se verifica ϕ(n) entonces se verifica ϕ(Sn). Entonces ϕ(n) se verifica para todo n ∈ ω − k. 15. Probar que si ϕ(x) es una f´ormula con variable libre x y existe un k ∈ ω tal que (a) ϕ(k) se verifica y 63

(b) para todo n ∈ ω tal que n > k, si se verifica ϕ(n) entonces se verifica ϕ(Sn). Entonces ϕ(n) se verifica para todo n ∈ ω − k. 2. Ordinales Los ordinales son conjuntos asociados con buenos ´ordenes, de hecho, son los ejemplos t´ıpicos de estos u ´ltimos en el sentido que todo buen orden es isomorfo a alg´ un ordinal. La definici´on de ordinal no hace sino extender las propiedades de los n´ umeros naturales estudiadas en la secci´on anterior sin embargo, esto no se podr´a apreciar sino hasta que el cap´ıtulo est´e bastante avanzado. ´ n 3.6. Definicio

i) a es ∈–transitivo si

∀x∀y((x ∈ y ∧ y ∈ a) → x ∈ a). ii) a es un ordinal si a es ∈–transitivo y todo elemento de a es ∈– transitivo. Si x es un ordinal escribiremos Ord (x). Obs´ervese que Ord (x) es una f´ormula de nuestro lenguaje en la que x aparece libre. Notaci´ on: Usaremos letras griegas min´ usculas para denotar ordinales. Nada en la definici´on indica que haya ordinales, ni siquiera que existan conjuntos ∈–transitivos. Tambi´en podr´ıa suceder que todo conjunto es un ordinal. A continuaci´on dilucidaremos estos problemas. De hecho, el siguiente teorema demuestra que todos los n´ umeros naturales son ordinales. Teorema 3.9. i) 0 es un ordinal. ii) Ord (x) → Ord (Sx). iii) ∀x(x ∈ ω → Ord (x)). iv) Ord (ω). ´ n. Demostracio i) Ord (0) trivialmente ya que 0 = ∅. ii) Supongamos que x es ordinal. Entonces x es ∈–transitivo y todo elemento de x es ∈–transitivo. Como Sx = x ∪ {x}, todo elemento de Sx es ∈–transitivo. Para ver que Sx es ∈–transitivo consideremos z , y tales que z ∈ y ∈ Sx. Si y ∈ x, entonces z ∈ x, ya que x es ∈–transitivo. Si y = x, entonces tambi´en z ∈ x, es decir, en cualquier caso, z ∈ x ⊆ Sx, o sea, Sx es ∈–transitivo. 64

iii) Consideramos la f´ormula ϕ(x) = Ord (x). Por i) y ii) y P.I., todo n´ umero natural es un ordinal. iv) El lema 3.3, ii) demuestra que ω es ∈–transitivo. Si n ∈ ω, iii) demuestra que n es ∈–transitivo. Luego Ord (ω). Ver que no todo conjunto es un ordinal es f´acil. De hecho, {{0}} no es ni siquiera ∈–transitivo. Tambi´en es f´acil ver que ning´ un par ordenado ha, bi es un ordinal. S Teorema 3.10. Si C es un conjunto de ordinales, entonces C es un ordinal. S ´ n. Para demostrar que C es ∈–transitivo, supongDemostraci So amos x ∈ y ∈ C. Entonces existe α ∈ C talque y ∈ α. Como x ∈ Sy ∈ α y esteSu ´ltimo es ∈–transitivo, x ∈ α y por lo tanto, x ∈ C, es decir, C es ∈–transitivo. S Sea x ∈ C. Entonces existe α ∈ C tal que x ∈ α, entonces, x tambi´en es ∈–transitivo. S Por lo tanto C es un ordinal. El siguiente teorema demuestra que todo ordinal est´a compuesto por ordinales. Teorema 3.11. Si α es un ordinal, entonces todos sus elementos son ordinales. ´ n. Supongamos que x ∈ α. Entonces x es ∈– Demostracio transitivo. Si y ∈ x, como α es ∈–transitivo, y ∈ α, luego y es ∈–transitivo, luego x es ordinal. Los ordinales nos proporcionan un nuevo ejemplo de clase propia. Teorema 3.12. No existe el conjunto de todos los ordinales. ´ n. Supongamos por el contrario que O es el conjunto Demostracio de todos los ordinales. Entonces es claro que O es ∈–transitivo y que todos sus elementos son ∈–transitivos, es decir, O es un ordinal, luego O ∈ O, contradicci´on. Teorema 3.13. Para todo par de ordinales α, β, α∈β

o ´

α=β

o ´

β ∈ α.

M´as a´ un, s´olo una de estas posibilidades se verifica. 65

´ n. Supongamos por el contrario que existen ordiDemostracio nales α y β tales que α 6∈ β, α 6= β y β 6∈ α. Sea A = {x ∈ Sα ∪ Sβ : ∃y(y ∈ Sα ∪ Sβ ∧ x 6∈ y ∧ x 6= y ∧ y 6∈ x)}.

Nuestra suposici´on implica que α, β ∈ A. Luego A 6= ∅. Por el axioma de regularidad, existe a ∈ A tal que A ∩ a = ∅. Definimos entonces el conjunto B = {x ∈ Sα ∪ Sβ : a 6∈ x ∧ a 6= x ∧ x 6∈ a}

B 6= ∅ ya que a ∈ A. Por el axioma de regularidad nuevamente sea b ∈ B tal que B ∩ b = ∅. Como a 6∈ B, a 6= b. La contradicci´on se obtiene probando que a = b. Sea x ∈ a, como a es ordinal, x tambi´en lo es. Como a ∩ A = ∅, x 6∈ A. Por u ´ltimo como x ∈ a ∈ Sα ∪ Sβ, x ∈ Sα ∪ Sβ, ya que este u ´ltimo, al ser uni´on de dos ordinales, es tambi´en un ordinal y, por lo tanto, es ∈–transitivo. Entonces ∀y(y ∈ Sα ∪ Sβ → (x ∈ y ∨ x = y ∨ y ∈ x))

en particular como b ∈ Sα ∪ Sβ,

x ∈ b ∨ x = b ∨ b ∈ x.

Si x = b, b ∈ a, luego b 6∈ B. Si b ∈ x, como a es ordinal b ∈ a, luego b 6∈ B. En ambos casos tenemos una contradicci´on. Por lo tanto la u ´nica posibilidad es x ∈ b, es decir, hemos demostrado que a ⊆ b. Supongamos ahora que x ∈ b. Como antes x ∈ Sα ∪ Sβ y x 6∈ B ya que B ∩ b = ∅. Luego a∈x ∨ a=x ∨ x∈a.

Si a ∈ x ´o a = x, entonces a ∈ b ya que b es ordinal. Luego x ∈ a. Hemos demostrado que b ⊆ a. Por lo tanto a = b lo que contradice nuestra suposici´on, luego α∈β ∨ α=β ∨ β∈α.

El teorema 1.3 garantiza que s´olo una de las tres posibilidades anteriores se verifica. Teorema 3.14. Si A es un T conjunto no vac´ıo de ordinales, enT tonces A esordinal. M´ as a´ un, A ∈ A. 66

T ´ n. Si x ∈ A, entonces para todo α ∈ A, x ∈ α, Demostracio luego x es ordinal, por loTtanto es ∈–transitivo. Supongamos x ∈ y ∈ A. Entonces para todo α ∈ A, x ∈ y ∈ α ∈T A, pero T α es ordinal, luego para todo α ∈ A, x ∈ α ∈ TA, o sea, x∈ A y A es ∈–transitivo. Hemos demostrado que A es un ordinal. T T T Por 3.13, para todo α ∈ A, A ∈ α ´o A = α ´o α ∈ A, pero esta u ´ltima posibilidad implica que,T en particular, α ∈ α. Las dos primeras posibilidades implican que A ∈ A. Teorema 3.15. Para cualquier α y β i) α ∈ β ssi α ⊂ β. S S ii) Si C S ⊆ α, entonces C=α ´ o C ∈ α. iii) α = Sα. iv) Si α ∈Sβ, entoncesSSα ∈ β ´ o Sα = β. v) α = S α ´o α = α.

´ n. Demostracio i) ⇒ Por ∈–transitividad de β , si x ∈ α, entonces x ∈ β, o sea, α ⊆ β. Como α ∈ β − α, α 6= β. ⇐ Si α ⊂ β, entonces α 6= β y β 6∈ α. Luego por el teorema 3.13, α ∈ β. S ii) C es un ordinal por el teorema 3.10. S Supongamos que α ∈ C, entonces α ∈ x para alg´ un x ∈ C y como hemos supuesto que C ⊆ α, x ∈ α. SO sea α ∈ xS∈ α, lo que contradice el teorema 1.3. Luego C ∈ α ´o CS= α. iii) Si x ∈ Sα, x ∈ y para alg´ un y ∈ Sα. Entonces y ∈ α ´o y = α; en cualquier caso x ∈ α. S Entonces x ∈ α ∈ Sα, luego x ∈ Sα. iv) Supongamos que β ∈ Sα, o sea, β ∈ α ´o β = α. Como por hip´otesis α ∈ β, tendriamos que β ∈ β, lo que contradice el teorema 1.3. Luego S por 3.13, Sα ∈ β ´o Sα S = β. v) S Sabemos que α es ordinal. Si α 6=S α, entonces por ii), S α ∈ α. Luego por iv), S α ∈ S S Sα ´o S α = α. Si suponemos S que S α ∈ α, como α ∈ S α, concluiriamos que α∈ S S α, lo que contradice el teorema 1.3. Luego S α = α ´ o α = S α. Observemos que iv) es una generalizaci´on del lema 3.3, iii). Tambi´en es importante notar que todo ordinal es o bien sucesor de alg´ un otro ordinal o bien la uni´on de s´ı mismo. 67

´ n 3.7. Sea α un ordinal. Definimos la relaci´on ≤ en Definicio α como sigue. Para x, y ∈ α x≤y

si y s´olo si

x∈y ∨ x=y.

N´otese que, en rigor, para distintos ordinales α el orden reci´en definido no es el mismo ya que su campo var´ıa. Sin embargo usaremos el mismo s´ımbolo ya que es claro dos de estos ´ordenes coinciden en la intersecci´on de sus campos. Tambi´en debemos notar que ´este coincide con el orden que definimos para los n´ umeros naturales. El siguiente teorema resume las principales propiedades de este orden. Teorema 3.16. Sea α un ordinal. i) ii) iii) iv) v) vi) vii) viii) ix) x) xi)

≤ es un buen orden en α. T Si A ⊆ α y A 6= ∅, entonces A es el menor elemento de A. 0 es el menor elemento de α . β < Sα si y s´olo si β ≤ α. α = {β ∈ α : β < α}. No existe un ordinal β tal que α < β < Sα. α ≤ β si y s´olo si S α ⊆ β. Si A ⊆ α, entonces A es el supremo de A . α < β si y s´olo si Sα ≤ β. Sα = Sβ si y s´olo si α = β. Sα < Sβ si y s´olo si α < β.

´ n. Demostracio i) ≤ es obviamente reflexiva. Es antisim´etrica por el teorema 1.3. Es transitiva por la ∈–transitividad de α . Es decir, ≤ es un orden. En virtud del teorema 3.13, ≤ es un orden total. Para ver que ≤ es un buen orden, consideremos T un subconjunto no vac´ıo A T ⊆ α. Por el teorema 3.14, A ∈ A. Supongamos x ∈ A ∩ ( A). Entonces para todo α ∈T A x ∈ α, en particular, x ∈ x, una contradicci´on. Luego A ∩ ( A) = ∅, o sea, ≤ es un buen orden. ii) Qued´o demostrado en (i), ∩A es el menor elemento de A iii) iv) y v) son obvios. vi) Supongamos existe β tal que α S< β < Sα, o lo que es lo mismo, α ∈ β ∈ Sα, es decir α ∈ Sα = α, por 3.15 iii), una contradicci´on. vii) Es consecuencia inmediata de la parte i) del teorema anterior. 68

S viii) Supongamos A ⊆S α, entonces A es un ordinal y para x S ∈A S es claro que x ⊆ A, o sea, por vii), x ≤ A, es decir, A es cota superior. S Sea β otra cota superior de A. Entonces para todo x ∈ A, como x ∈ α ∈ A y S β es cota superior de A , x ≤ α ≤ β, es decir, x ∈ β, o sea, A ⊆ β, por lo tanto ∪A es la menor de las cotas superiores de A . ix) Si α ∈ β, entonces por ∈–transitividad Sα ⊆ β, o sea, Sα ≤ β. Si Sα ≤ β, como α < Sα, α < β, por transitividad de < . x) Supongamos Sα = Sβ y α 6= β. Entonces como α ∈ Sα = Sβ, α ∈ Sβ. Pero entonces α ∈ β. An´alogamente β ∈ α lo que es imposible, luego, α = β. Es claro que si α = β, Sα = Sβ. xi) α < β si y s´olo si Sα ≤ β si y s´olo si Sα < Sβ por ix) y iv) respectivamente.

Observaci´ on. En viii) hay un peque˜ no abuso producido por el hecho de denotar S con el mismo s´ımbolo ordenes distintos. En efecto, si tenemos A = α, entonces ∪A no est´a en el campo de ≤, luego no puede ser una cota superior. Podemos sin embargo entender dicha proposici´on como expresada en un orden cuyo campo contiene a α , por ejemplo Sα o cualquier ordinal m´as grande. En este caso la proposici´on es totalmente correcta. Ejercicios. 1. Probar que: (a) α es un ordinal si y s´olo si ∈ es un buen orden sobre α y β ∈ α implica que β ⊆ α. (b) Si α es totalmente ordenado por ∈ y β ∈ α implica que β ⊆ α , entonces α es un ordinal. 2. Todo ordinal es segmento inicial de alg´ un otro ordinal. 3. Probar que bien α = 0 , o S α ∈ ω si y s´olo si α es ordinal y, o S bien α 6= α y para todo β ∈ α , β = 0 , o β 6= β. 4. Probar que α ∈ ω si ySs´olo si α es ordinal y para todo β ⊆ α tal que β 6= 0 se tiene β ∈ β. 5. Probar que α es ordinal si y s´olo si α es ∈–transitivo y ∈ es buen orden sobre α . 6. Probar que α ∈ ω si y s´olo si todo subconjunto no vac´ıo de α tiene mayor elemento. 69

7. Sea B un conjunto de ordinales . Probar S que si α es un ordinal y para todo β ∈ B, β ≤ α , entonces β ≤ α. Probar tambi´en que lo anterior no es necesariamente cierto si no se requiere que α sea ordinal. 8. Probar que si α ∈ ω y β es el mayor elemento de α , entonces α = Sβ. ¿Es esto cierto si α es ordinal arbitrario? 3. Inducci´ on Transfinita En esta secci´on generalizaremos el teorema de inducci´on de los n´ umeros naturales a los ordinales. De hecho, el primero es un caso particular del segundo. Teorema 3.17. (Principio de Inducci´ on Transfinita) Si ϕ(x) es una f´ormula con una variable libre y para todo ordinal α, (∗) si para todo β < α, ϕ(β) , entonces ϕ(α). Entonces para todo ordinal α, ϕ(α). ´ n. Observemos primero que como no existe ning´ Demostracio un β < 0, por ( ∗ ), ϕ(0) se verifica trivialmente. Supongamos que el teorema es falso para alg´ un ordinal α. Entonces el conjunto C = {β ∈ Sα : ¬ϕ(β)} es no vac´ıo, luego tiene un menor elemento γ. La observaci´on al comienzo de esta demostraci´on implica que γ 6= 0. Adem´as, como γ es el menor elemento de C, para todo β < γ, β 6∈ C, es decir, para todo β < γ, ϕ(β), pero entonces por la hip´otesis ( ∗ ), ϕ(γ), pero como γ ∈ C, se llega a una contradicci´on. Luego para todo ordinal α ϕ(α). N´otese que esta formulaci´on del teorema de inducci´on transfinita es similar a la del teorema de inducci´on completa de los n´ umeros naturales, A veces es u ´til usar una forma m´as parecida al principio de inducci´on “por casos”. Para ello recordemos que todo ordinal es o bien el sucesor de alg´ un otro o es la uni´on de s´ı mismo. La pr´oxima definici´on y el teorema que le sigue formaliza estas ideas. ´ n 3.8. Un ordinal α es un sucesor si existe : β tal que Definicio α = Sβ. Si α 6= 0 y α no es un ordinal sucesor, entonces α es un ordinal l´ımite l´ımite. Notemos que hay tres clases de ordinales, 0, sucesores y l´ımites. Teorema 3.18. Sea α un ordinal. S i) α es sucesor si y s´olo S α < α. ii) α es l´ımite si y s´olo α = α 6= 0. 70

iii) α es l´ımite si y s´olo α 6= 0 ∧ ∀β(β < α → ∃ γ(β < γ < α)). ´ n. Demostraci o i) Si α = Sβ, entonces por el teorema 3.15 S S iii), α = Sβ = β <Sα, S Reciprocamente, si α < α, S α ≤ α. Si suponemos que S S α < α, [ [ α ∈ S α ∈ α, S S S oSsea, α ∈ α, una contradicci´on. Luego α = S α y como α es un ordinal, α es sucesor. S ii) Sabemos por el teorema 3.15 ii), que α ≤ α. Entonces S S por i), α = α si y s´olo si α no es sucesor, luego α 6= 0 y α=α si y s´olo si α es l´ımite. S iii) Por ii), α es l´ımite si y s´olo si α 6= 0, α = α y esta u ´ltima es equivalente a que para todo β ∈ α, existe γ ∈ α tal que β ∈ γ ∈ α. Teorema 3.19. Sea ϕ(x) una f´ormula con una variable libre tal que i) ϕ(0), ii) para todo ordinal α , si ϕ(α) , entonces ϕ(Sα) y iii) para todo ordinal l´ımite α , si ϕ(β) para todo β < α, entonces ϕ(α). Entonces para todo ordinal α, ϕ(α). ´ n. Para demostrar este teorema, demostraremos las Demostracio hip´otesis del teorema 3.17 a partir de i), ii) y iii). Sea entonces α un ordinal y supongamos que ϕ(β) para todo β < α. Debemos demostrar que ϕ(α). Hay tres casos. Si α = 0, entonces ϕ(α) por hip´otesis i). Si α es un sucesor, entonces α = Sβ luego β < α y por lo tanto ϕ(β). Pero entonces por ii), ϕ(Sβ) o sea, ϕ(α). Si α es un l´ımite, como ϕ(β), para todo β < α, por iii) ϕ(α). En cualquier caso ϕ(α). Por lo tanto en virtud del teorema 3.17, para todo ordinal α, ϕ(α). Este teorema puede demostrarse sin recurrir al teorema 3.17 pero estimamos que la demostraci´on tiene cierto inter´es en s´ı misma. Ver ejercicios problema 2. Ejercicios. 71

1. Demuestre que el Principio de Inducci´on dado en el teorema 3.19 implica al Principio de Inducci´on del teorema 3.17. 2. Demuestre el Principio de Inducci´on 3.19 sin usar el teorema 3.17. 3. Demuestre el siguiente Principio de Inducci´on. Sean α un ordinal no nulo A ⊆ α tales que (a) 0 ∈ A, (b) si β ∈ A S y Sβ < α, entonces Sβ ∈ A, (c) si β = β < α y para todo γ < β, γ ∈ A. Entonces A = α. 4. Recursi´ on En esta secci´on estudiaremos un proceso, ´ıntimamente ligado a la inducci´on transfinita, que nos permite definir operaciones entre ordinales, este es el principio de recursi´on. En ´algebra elemental frecuentemente nos encontramos con sucesiones del tipo siguiente a0 = 1 an+1 = 2an + 1 Es claro que esta sucesi´on est´a bien definida ya que para cualquier n , con alg´ un trabajo, podemos obtener el valor de an . Por otra parte, es claro que esta definici´on difiere esencialmente de la de la sucesi´on bn = n2 + 1 . La diferencia reside en que para conocer el valor de an debemos primero determinar el valor de an−1 , y para conocer ´este, debemos determinar el valor de an−1 y as´ı sucesivamente. No es este el caso de bn . Decimos que {an }n∈ω est´a definida recursivamente. A continuaci´on formalizaremos estos conceptos. Recordemos que una f´ormula ϕ(x, y) tal que para todo a existe un u ´nico b tal que ϕ(a, b) define una operaci´on unaria y habitualmente escribimos b = F (a) si y s´olo si ϕ(a, b) . Obs´ervese que por el axioma de reemplazo, si a es un conjunto F (a) y {F (x) : x ∈ a} tambi´en lo son. El siguiente teorema nos permite definir una operaci´on unaria sobre un conjunto cualquiera conociendo todos los valores de la operaci´on sobre sus elementos. Una forma alternativa es definir la operaci´on por casos, para el 0, para ordinales sucesores, para ordinales l´ımites y para 72

conjuntos cualquira. Este u ´ltimo caso es necesario ya que la operaci´on debe estar definida para todos los conjuntos y no s´olo para los ordinales.

Teorema 3.20. i) Sea y = G(x) una operaci´ on unaria. Entonces existe una u ´nica operaci´ on unaria y = F (x) tal que ∀α(Ord (α) → F (α) = G({F (β) : β ∈ α})∧∀x(¬Ord (x) → F (x) = x) ii) Sean y = G(x), y = H(x) dos operaciones unarias, entonces existe una u ´nica operaci´ on unaria y = F (x) tal que para todo ordinal α F (Sα) = G(F (α)) ∧ (α = y si x no es ordinal,

[

α → F (α) = H{F (β) : β ∈ α})

F (x) = x). ´ n. Demostracio i) Demostraremos por inducci´on que para todo ordinal α existe una u ´nica funci´on fα tal que a) Domfα = Sα, b) fα (β) = G(fα∗ β), para todo β ∈ Sα y c) si β ∈ α, entonces fβ ⊂ fα . Sea entonces α un ordinal y supongamos que para todo β < α existe fβ con las propiedades a), b) y c). Entonces definimos fα (β) =



fβ (β) G(fα∗ (α))

, si β ∈ α, , si β = α.

Entonces fα es una funci´on, Dom fα = Sα y fα verifica b) y c). Observemos tambi´en que f0 (0) = G(0). Para probar la unicidad de fα supongamos que para alg´ un α existen dos funciones fα y gα con las caracter´ısticas anteriores. Sea α0 el menor tal ordinal. Entonces para β < α0 existe una u ´nica funci´on fβ como arriba. Pero entonces para todo β < α0 fα0 (β) = fβ (β) = gα0 (β), y por lo tanto 73

fα∗0 α0 = = = =

{fα0 (β) : β ∈ α0 } {fβ (β) : β ∈ α0 } {gα0 (β) : β ∈ α0 } gα∗ 0 α0 ,

luego fα0 (α0 ) = G(fα∗0 α0 ) = G(gα∗ 0 α0 ) = gα0 (α0 ), Es decir fα0 = gα0 lo que contradice nuestra suposici´on. Por lo tanto, por el teorema 3.17, para todo ordinal α existe una u ´nica funci´on fα que verifica a) y b). Podemos ahora definir nuestra operaci´on unaria y = F (x).  fx (x) si x es ordinal, F (x) = x si x no es ordinal.

Por construcci´on, y = F (x) verifica la tesis del teorema. ii) Demostraremos por inducci´on que para todo α existe una u ´nica funci´on fα tal que a) Dom fα = Sα, b) Si Sβ ∈SSα, entonces fα (Sβ) = G(fα (β)), c) Si β = β ∈ Sα, entonces fα (β) = H(fα∗ β). d) Si β ∈ α, entonces fβ ⊂ fαS. Si β = 0 , entonces β = β luego definimos f0 con dominio 1 como sigue: f0 (0) = H(f0∗ (0)) = H(0)

Si β = Sγ, suponemos que existe fγ con Dom fγ = Sγ y que satisface a), b), c) y d). Definimos entonces fβ de la siguiente manera  fγ (α) si α ∈ β = Sγ, fβ (α) = G(fγ (γ)) si α = β.

Es claro que fβ verifica a), b), c) y d). Si β = ∪β, suponemos por hip´otesis de inducci´on que para todo γ ∈ β existe fγ que verifica a), b), c) y d). Definimos fβ como sigue  fα (α) si α ∈ β = Sγ, fβ (α) = ∗ H(fβ (β)) si α = β. 74

fβ tambi´en verifica a), b), c) y d). Luego por inducci´on, para todo ordinal α , existe una funci´on fα con las caracter´ısticas indicadas. La unicidad de fα es obvia y se deja como ejercicio. Podemos definir la operaci´on unaria F como en i).

Ejercicios. 1. Definimos la clausura transitiva de a, que denotamos T (a), como el menor conjunto ∈–transitivo que contiene a a . Demuestre que existe la clausura transitiva de cualquier conjunto. Indicaci´on: Definir recursivamente una funci´on F sobre ω de tal manera que F (0) = a [ F (n + 1) = F (n) S y luego probar que T (a) = n∈ω F (n). Intuitivamente [ [[ [[[ T (a) = a ∪ a ∪ a∪ a··· ,

es decir contiene los elementos de a , los elementos de los elementos de a , etc. 5. Funciones Normales

En esta secci´on estudiaremos algunas propiedades de las funciones normales que nos ser´an u ´tiles en las secciones siguientes. ´ n 3.9. Sean A y B ordinales y µ : A → B una funci´on. Definicio i) µ es no-decreciente si ∀α∀β(α < β → µ(α) ≤ µ(β)).

ii) µ es estrictamente creciente si

∀α∀β(α < β → µ(α) < µ(β)).

iii) µ es continua si

∀α((α 6= 0 ∧

[

α = α ∈ A) → µ(α) =

[

µ(β)).

β∈α

iv) µ es normal si es continua y estrictamente creciente. Ejemplo. 75

1. La funci´on S es estrictamente creciente pero no continua, por S ejemplo SωS 6= ω = Sω. 2. La funci´on es continua S peroSno estrictamente creciente, por ejemplo, ω < Sω, pero ω = Sω. 3. Sea α un ordinal l´ımite. Definimos para β ∈ α  Sβ , si β es sucesor, f (β) = β , si no. F´acilmente podemos ver que f es normal. Teorema 3.21. Sean A, B ordinales µ : A → B una funci´ on. Si µ es estrictamente creciente, entonces para todo α ∈ A, α ≤ µ(α). ´ n. Por inducci´on. Demostracio Teorema 3.22. Sean A, B ordinales µ : A → B una funci´on continua tal que si Sβ ∈ A, µ(β) < µ(Sβ). Entonces µ es normal. ´ n. Tenemos que demostrar que µ es estrictamente Demostracio creciente. Lo haremos por inducci´on usando la siguiente f´ormula ϕ(x) = ∀β((β < x ∧ x ∈ A) → µ(β) < µ(x)) i) ϕ(0) se verifica trivialmente. ii) Si β = Sγ, supongamos que ϕ(γ) se verifica y que Sγ ∈ A. Entonces para δ < γ, µ(δ) ≤ µ(γ) por hip´otesis de inducci´on . Si δ = γ, µ(γ) < µ(Sγ), por hip´otesis, es decir luego ∀δ((δ < β = Sγ ∧ Sγ ∈ A) → µ(δ) < µ(beta)), es decir, ϕ(β). iii) Si β es l´ımite, entonces por la continuidad de µ , ϕ(β). Esto que completa muestra inducci´on. Luego µ es estrictamente creciente y por lo tanto normal. Teorema 3.23. Si µ es una funci´on normal y α ∈ Dom µ es un ordinal l´ımite, entonces µ(α) tambi´en es l´ımite. ´ n. Sea δ ≤ µ(α). Como Demostracio [ µ(α) = µ(β) , β<α

existe γ < α tal que δ ∈ µ(γ), o sea, 76

δ < µ(γ) < µ(α), ya que como µ es estrictamente creciente, µ(γ) < µ(α). Luego por teorema 3.18 iii), µ(α) es l´ımite. Teorema 3.24. Si α es un ordinal, β < α y µ es no decreciente, entonces [ [ µ(γ) = µ(γ). γ<α

β≤γ<α

´ n. Si γ < β , µ(γ) ≤ µ(β), luego Demostracio y por lo tanto [

µ(γ) =

γ<α

[

γ<β

µ(γ) ∪

[

µ(γ) =

β≤γ<α

[

[

γ<β

µ(γ) ≤ µ(β)

µ(γ).

β≤γ<α

Teorema 3.25. Sean µ, ν funciones normales tales que Rec µ ⊆ Dom ν. Entonces ν ◦ µ es una funci´on normal. ´ n. ν ◦ µ es estrictamente creciente ya que si α < Demostracio β, µ(α) < µ(β), luego ν(µ(α)) < ν(µ(β)), o sea, ν ◦ µ(α) < ν ◦ µ(β). Para ver que ν ◦ µ es continua, sea α 6= 0, α = ∪α. Por teorema 3.23, [ µ(β) es tambi´en un ordinal l´ımite. Luego como ν es µ(α) = β<α

continua

ν ◦ µ(α) = ν(µ(α)) = Pero si β < µ(α) =

[

[

ν(β).

β<µ(α)

µ(γ), entonces existe γ < α tal que β <

γ<α

µ(γ) < µ(α) luego

ν(β) < ν(µ(γ)) <

[

ν(µ(δ)).

δ<α

Por lo tanto ν ◦ µ(α) ≤

[

δ<α

ν(µ(δ)) ≤ ν(µ(α)) = ν ◦ µ(α) 77

o sea ν ◦ µ(α) =

[

δ<α

ν ◦ µ(δ),

es decir ν ◦ µ es continua y por lo tanto ν ◦ µ es normal. Teorema 3.26. Sea α un ordinal, µ una funci´on normal con dominio α . Supongamos que para alg´ un β ∈ α existen δ, γ ∈ α tal que µ(δ) ≤ β < µ(γ). Entonces existe un u ´nico γ ∈ α tal que µ(γ) ≤ β < µ(Sγ). ´ n. Sea ε el menor γ tal que β < µ(γ). Este debe Demostracio existir por hip´otesis. Supongamos ε = 0, entonces como ε ≤ β, µ(ε) ≤ µ(β) < µ(ε), una contradicci´on, luego ε 6= 0. [ Supongamos ε 6= 0, ε = ∪ε. Entonces β < µ(ε) = µ(δ) luego δ<ε

existe δ < ε tal que β < µ(δ) contradiciendo la minimalidad de ε. Por lo tanto ε es un sucesor, digamos ε = Sγ. Entonces µ(γ) ≤ β < µ(Sγ). Para probar la unicidad de γ, sea ξ 6= γ un ordinal. Entonces γ<ξ

´o

ξ<γ .

Si γ < ξ , Sγ ≤ ξ, luego β < µ(Sγ) ≤ µ(ξ); si ξ < γ, Sξ ≤ γ, luego µ(Sξ) ≤ µ(γ) < β. En cualquier caso, ξ no verifica que µ(ξ) ≤ β < µ(Sξ), luego γ es u ´nico. Ejercicios. 1. Demuestre que la funci´on definida en los ejemplos 5 es normal. 2. Demuestre el teorema 3.21. 3. Considere la topolog´ıa generado sobre el ordinal α por todos los intervalos (β), γ) = {δ : β < δ < γ}, donde β < γ ∈ α. Demuestre que µ : α −→ α es continua seg´ un la definici´on 3.9 si y s´olo si, µ es continua en esta topolog´ıa. 6. Ordinales y Buenos Ordenes Esta breve secci´on la dedicaremos a demostrar un resultado importante, a saber, que todo buen orden es isomorfo al orden de alg´ un ordinal. De esta manera, los ordinales sirven para representar a todos 78

los posibles buenos ordenes. Volveremos sobre este tema en el pr´oximo cap´ıtulo. Teorema 3.27. Todo buen orden es isomorfo con (el orden de) un ordinal. ´ n. Sea R un buen orden cuyo campo es A . DefiDemostracio namos la operaci´on unaria  R − menor elemento de A − F ∗ α si ´este es no vac´ıo, F (α) = A si no. (Para ser rigurosos, la operaci´on F debe estar definida para todo conjunto y no s´olo para los ordinales, sin embargo, siempre podemos definir F en forma arbitraria para un conjunto x que no es ordinal. Por ejemplo, podemos definir F (x) = A). Por el axioma de reemplazo, Γ = {α : F (α) ∈ A} es un conjunto de ordinales y por lo tanto existe alg´ un ordinal β tal que F (β) ∈ / A. Sea \ γ = {β : F (β) ∈ / A}.

Observemos que si F (β) ∈ / A, entonces F (β) = A y A − F ∗ β = ∅, luego si α > β, F (α) ∈ / A. Esto demuestra que Γ = γ. Si α < β < γ, entonces F ∗ α ⊂ F ∗ β, luego A − F ∗ β ⊆ A − F ∗ α, y por lo tanto R − menor elemento A − F ∗ α ≤ R − menor elemento A − F ∗ β, es decir, F (α) ≤ F (β). Por otra parte, si α < β, F (α) ∈ F ∗ β, luego F (α) ∈ / A − F ∗β y por lo tanto F (α) 6= F (β). Esto demuestra que si definimos f : γ −→ A α 7−→ F (α), f es una biyecci´on y α ≤ β si y s´olo si f (α)Rf (β), o sea, R y γ son isomorfos. 79

7. Aritm´ etica Ordinal A continuaci´on definiremos la suma, el producto y la exponenciaci´on de ordinales. Las dos primeras operaciones tienen una interpretaci´on bastante intuitiva en t´erminos de buenos ´ordenes. Como sabemos todo ordinal esta bien ordenado por ∈ , es m´as, como vimos en la secci´on anterior, todo buen orden est´a codificado o representado por alg´ un ordinal. Ahora bien, la suma de dos ordinales α y β representa al (buen) orden que resulta de ordenar α ∪ β poniendo todos los elementos de β despu´es de los de α , gr´aficamente − − − −− →} | − − − {z α

− | − −{z− − →} β

Por su parte α · β representa al (buen) orden lexicogr´afico sobre α × β (ver ejercicios). La exponenciaci´on no tiene una interpretaci´on intuitiva. 7.1. Suma de Ordinales. ´ n 3.10. Definimos la suma de ordinales como sigue. Si Definicio α es un ordinal cualquiera i) α + 0 = α ii) α + Sβ = S(α + β) iii) α + λ = ∪{α + β : β ∈ λ}, si 0 6= λ = ∪λ Obs´ervese que tal operaci´on est´a bien definida en virtud del teorema 3.20, ii), donde G(x) = Sx y H(x) = ∪x. Adem´as para todo α, β, α + β es un ordinal.

Teorema 3.28. Para todo par de ordinales α y β , la funci´on +α : β −→ α + β γ 7→ α + γ , es una funci´on normal. ´ n. +α es continua por definici´on. Demostracio Supongamos que γ ∈ β y Sγ ∈ β, entonces +α (γ) = α + γ < S(α + γ) = α + Sγ = +α (Sγ), luego por el teorema 3.22, +α es normal. 80

Formalizaremos ahora las ideas intuitivas sobre la suma de ordinales que dimos en la introducci´on de esta secci´on. Teorema 3.29. Dados α y β ordinales, definimos el orden R cuyo campo es {0} × α ∪ {1} × β como sigue: hx0 , y0 i R hx1 , y1 i si y solamente si se verifica una de las siguientes condiciones 1. x0 = x1 = 0 y y0 ≤ y1 < α, 2. x0 = 0 , x1 = 1, 3. x0 = x1 = 1 y y0 ≤ y1 < β. Entonces R es un buen orden isomorfo a α + β. ´ n. Es f´acil demostrar que R es un buen orden (ver Demostracio ejercicios). Definimos:  γ si x = 0 y γ < α, F (x, γ) = α + γ si x = 1 y γ < β. Entonces

Dom F = {i0, γh: γ ∈ α} ∪ {i1, γh: γ ∈ β} = Cam R . Tambi´en es claro que α ⊆ Rec F ⊆ α + β. Para ver que Rec F = α + β, sea δ ∈ α + β, δ 6∈ α. Luego α ≤ δ < α + β. Como +α es normal, por teorema 3.26, existe un u ´nico γ tal que +α (γ) ≤ δ < +α (γ), o bien α + γ ≤ δ < α + Sγ = S(α + γ). Por teorema 3.16, vi) , α + γ = δ. Luego, como γ tiene que ser menor que β , δ = α + γ = F (1, γ) , o sea, δ ∈ Rec F y por lo tanto α + β = Rec F . Por u ´ltimo como +α es normal, es f´acil verificar que xRy y que F es inyectiva.

ssi F (x) ≤ F (y)

Algunas de las propiedades m´as importantes de la suma de ordinales est´an resumidas en el siguiente teorema. Teorema 3.30. Sean α , β , γ ordinales. Entonces i) (α + β) + γ = α + (β + γ). ii) β ≤ α + β. 81

iii) iv) v) vi) vii)

α < β si y s´olo si existe γ > 0 tal que α + γ = β. Si α < β , entonces α + γ ≤ β + γ. Sα = α + 1. 0 + α = α. Si β < γ , entonces α + β < α + γ.

´ n. Demostracio – Si γ = 0

i) Por inducci´on sobre γ .

(α + β) + 0 = α + β = α + (β + 0). – Supongamos que (α + β) + γ = α + (β + γ). Entonces (α + β) + Sγ = = = =

S((α + β) + γ) S(α + (β + γ)) α + S(β + γ) α + (β + Sγ).

– Si 0 6= λ = ∪λ y para todo γ ∈ λ, α + (β + γ) = (α + β) + γ. Entonces como +β (x) = β + x es normal y λ es l´ımite, por 3.23, β + λ = ∪{β + γ : γ < λ} es l´ımite, y por 3.24 ∪{β + γ : γ < λ} = ∪{δ : δ < β + λ}. Similarmente, +α (x) = α + x es normal, luego α + (β + λ) = = = = = = =

α + ∪{β + γ : γ < λ} α + ∪{δ : δ < β + λ} ∪{α + δ : δ < β + λ} ∪{α + δ : β ≤ δ < β + λ} ∪{α + (β + γ) : γ < λ} ∪{(α + β) + γ : γ < λ} (α + β) + λ.

Esto completa la inducci´on y demuestra por lo tanto la asociatividad de + . ii) Por inducci´on sobre β . – Si β = 0 , obviamente 0 ≤ α + 0. – Supongamos β ≤ α + β. Entonces Sβ ≤ S(α + β) = α + Sβ. 82

– Si 0 6= λ = ∪λ y para todo γ ∈ λ γ ≤ α + γ. Entonces λ = ∪{γ : γ ∈ λ} ≤ ∪{α + γ : γ ∈ λ} = α + λ.

iii) Supongamos α < β. Como β ≤ α + β,

A = {δ ∈ Sβ : β ≤ α + δ}, es no vac´ıo, luego A tiene un menor elemento γ tal que β ≤ α + γ.

Supongamos que β < α + γ. Es claro que γ 6= 0 ya que α < β. Si γ es un sucesor, digamos γ = Sε, β < α + Sε = S(α + ε), luego β ≤ α + ε, lo que contradice la minimalidad de γ . Si γ = ∪γ, β < α + γ = ∪{α + δ : δ ∈ γ}, luego β ∈ α + δ para alg´ un δ < γ, lo que contradice la minimalidad de γ . Es decir γ no es 0 ni sucesor ni l´ımite lo que no es posible, luego β = α + γ. Rec´ıprocamente, si β = α + γ, como α + x es estrictamente creciente y 0 < γ α = α + 0 < α + γ = β. iv) Por inducci´on sobre γ . – Si γ = 0, α + 0 = α < β = β + 0. – Supongamos que α + γ < β + γ. Entonces α + Sγ = S(α + γ) < S(β + γ) = β + Sγ. – Si 0 6= λ = ∪λ y para γ < λ, Entonces

α + γ < β + γ.

α + λ = ∪{α + γ : γ ∈ λ} ⊆ ∪{β + γ : γ ∈ λ} = β + λ. La desigualdad estricta no se puede lograr ya que, por ejemplo, 1 + ω = 2 + ω. v) Obvio vi) 0 + α = α se demuestra por inducci´on sobre α. – Si α = 0, entonces 0 + α = 0 = α. 83

– 0 + Sα = S(0 + α) = Sα. – Si 0 6= α = ∪α y para todo γ ∈ α, 0 + γ = γ, 0 + α = ∪{0 + γ : γ ∈ α} = ∪{γ : γ ∈ α} = α, lo que completa la inducci´on. vii) Ya lo demostramos en el teorema 3.28. La suma de ordinales restringida a ω nos da la suma usual de los n´ umeros naturales, por ejemplo, 2 + 2 = 4. En efecto 2 + 2 = 2 + S1 = S(2 + 1) = S(2 + S0) = SS2 = S3 = 4. En el pr´oximo teorema se demuestran algunas propiedades de la suma de los n´ umeros naturales. Teorema 3.31. Sean m y n n´ umeros naturales. Entonces i) m + n es natural. ii) n + 1 = 1 + n. iii) m + n = n + m. ´ n. Demostracio i) Por inducci´on sobre n . – m + 0 = m es natural. – Si m + n es natural, su sucesor tambi´en lo es. Pero S(m + n) = m + Sn, luego m + Sn tambi´en es natural. Por el principio de inducci´on, 3.1, para todo natural n, m+ n es natural. ii) Por inducci´on sobre n . – 1 + 0 = 1 = 0 + 1, por 3.30, vi). – Supongamos que 1 + n = n + 1. Entonces 1 + Sn = S(1 + n) = S(n + 1) = SSn = Sn + 1, lo que completa la inducci´on. iii) Por inducci´on sobre n . – m + 0 = 0 + m por 3.30, vi). – Supongamos que m + n = n + m. Entonces m + Sn = = = =

m + (n + 1) = (m + n) + 1 (n + m) + 1 = n + (m + 1) n + (1 + m) , por ii), (n + 1) + m = Sn + m ,

lo que completa la inducci´on. 84

Notemos que la suma de ordinales no es general conmutativa, en efecto, 1 + ω = ∪{1 + n : n ∈ ω} =

[ {Sn : n ∈ ω} = ω 6= ω + 1 .

De hecho esta propiedad caracteriza a los ordinales que no son n´ umeros naturales. Teorema 3.32. ω ≤ α si y s´olo si 1 + α = α. ´ n. Ya vimos que 1 + ω = ω. Demostracio Si α ≥ ω, existe γ tal que α = ω + γ. Entonces 1 + α = 1 + (ω + γ) = (1 + ω) + γ = ω + γ = α. Si α < ω, entonces por 3.31 ii), 1 + α = α + 1 6= α. 7.2. Multiplicaci´ on de Ordinales. ´ n 3.11. Definimos por recursi´on el producto por α como Definicio sigue i) α · 0 = 0. ii) α · Sβ = α · β + α. iii) α · λ = ∪{α · β : β ∈ λ}, si 0 6= λ = ∪λ. Como en el caso de la suma, hemos definido la multiplicaci´on por recursi´on usando el teorema 3.20, donde G(x) = x + α

y

H(x) = ∪x.

Teorema 3.33. Para todo par de ordinales α y β, funci´on ×α : β −→ α · β es una funci´on normal. γ 7−→ α · γ ,

α 6= 0 la

´ n. ×α es continua por definici´on. Demostracio Para ver que ×α normal, por teorema 3.22, basta verificar que para todo γ ∈ β ×α (γ) < ×α (Sγ). ×α (γ) = < = =

α·γ α · γ + α, α · Sγ ×α (Sγ).

por teorema 3.30, iii),

85

Teorema 3.34. Dados α y β ordinales, definimos el orden R cuyo campo es α × β como sigue: hx0 , y0 i R hx1 , y1 i si y solamente si se verifica una de las siguientes condiciones 1. y0 ≤ y1 < β, 2. y0 = y1 y x0 ≤ x1 < β.

Entonces R es un buen orden isomorfo a α · β}. ´ n. Podemos suponer que α y β son distintos de 0. Demostracio Es f´acil demostrar que R es un buen orden (ver ejercicios). Para γ ∈ α, δ ∈ β, definimos F (hγ, δi) = α · δ + γ. Entonces Dom F = α × β = Cam R. F es una funci´on y para cada hγ, δi ∈ α × β, F (hγ, δi) = < = ≤

α·δ+γ α · δ + α, por teorema 3.30, vii), α · Sδ α · β, ya que ×α es creciente.

O sea, hemos demostrado que Rec F ⊆ α · β. Para demostrar que F es sobreyectiva, sea ε ∈ α · β. Entonces α · 0 = 0 ≤ ε < α · β. Como ×α es normal, por el teorema 3.26, existe un u ´nico δ tal que α · δ ≤ ε < α · Sδ = α · δ + α. Es claro que δ < β y que si β ≤ δ, ε < α · β ≤ α · δ ≤ ε. Ahora bien, como α · δ ≤ ε, por 3.30, iii) existe un u ´nico γ tal que α · δ + γ = ε. Evidentemente γ < α pues si no, ε < α · Sδ = α · δ + α ≤ α · δ + γ = ε. Por lo tanto, dado ε ∈ α · β, existe un u ´nico hγ, δi ∈ α × β tal que F (hγ, δi) = ε, o sea, F es sobreyectiva. Para probar que F es estrictamente creciente, supongamos que hγ, δiRhε, ξi, entonces o bien δ < ξ , en cuyo caso 86

F (hγ, δi) = α · δ + γ

< α·δ+α = α · Sδ ≤ α · ξ ≤ alpha · ξ + ε = F (hε, ξi),

o bien δ = ξ y γ < ε, entonces

F (hγ, δi) = α · δ + γ = α·ξ+γ < α · ξ + ε = F (hε, ξi), o sea F es estrictamente creciente, luego es inyectiva y por lo tanto es un isomorfismo.

Observaci´ on. El orden R reci´en introducido se llama orden antilexicogr´afico, corresponde a sustituir cada elemento de β por una copia de α . Las propiedades b´asicas de la multiplicaci´on ordinal est´an resumidas en el siguiente teorema. Teorema 3.35. i) α · (β + γ) = α · β + α · γ. ii) α · (β · γ) = (α · β) · γ. iii) α · 0 = 0 · α = 0. iv) α · 1 = 1 · α = α. v) α · 2 = α + α. vi) Si α 6= 0, entonces β ≤ α · β. vii) Si α 6= 0 y β < γ, entonces α · β < α · γ. viii) Si α 6= 0 y 1 < β, entonces α < α · β. ix) Si α < β, entonces α · γ ≤ β · γ. x) Si 1 < α, 1 < β, entonces α + β ≤ α · β. xi) Si α, β 6= 0, entonces α · β 6= 0. ´ n. Demostracio i) Por inducci´on sobre γ . – Si γ = 0, α · (β + 0) = α · β = α · β + 0 = α · β + α · 0 – Si α · (β + γ) = α · β + α · γ, 87

α · (β + Sγ) = = = = =

α · S(β + γ) α · (β + γ) + α (α · β + α · γ) + α α · β + (α · γ + α) α · β + α · Sγ.

– Si γ = ∪γ 6= 0 y para todo δ ∈ γ, α · (β + δ) = αβ + αδ y [ α · (β + γ) = α · {β + δ : δ ∈ γ}. S Como +β es normal, {β + δ : δ ∈ γ} es un ordinal l´ımite luego [ [ α · {β + δ : δ ∈ γ} = {α · (β + δ) : δ ∈ γ} [ = {α · β + α · δ : δ ∈ γ} = α · β + ∪{α · δ : δ ∈ γ},

ii) iii) v) vii)

ya que ×α es normal. Esto completa la inducci´on, por lo tanto α · (β + γ) = α · β + α · γ.

Por inducci´on sobre γ usando i). y iv) se demuestran por una sencilla inducci´on. Por definici´on. Por inducci´on sobre β . Sea 1 ≤ α. – Si β = 0, 0 ≤ α · 0 = 0. – Si β ≤ α · β, entonces Sβ ≤ = ≤ =

S(α · β) α·β+1 α·β+α α · Sβ.

– Si β = ∪β 6= 0 y para todo γ < β,

γ ≤ α · γ,

β = ∪{γ : γ ∈ β} ≤ ∪{α · γ : γ ∈ β} = α · β, lo que completa la inducci´on. ix) Por inducci´on sobre γ . x) Por inducci´on sobre β . 88

– Si β = 2, entonces como 2 ≤ α, α+β =α+2≤α+α=α·2=α·β – Si 1 < β y α + β ≤ α · β, α + Sβ = ≤ = ≤ =

S(α + β) S(α · β) α·β+1 α·β+α α · Sβ.

– Si β = ∪β 6= 0 y para todo γ ∈ β, 1 < γ, entonces α + γ ≤ α · γ, entonces [ [ α + β = {α + γ : γ ∈ β} ⊆ {α · γ : γ ∈ β} = α · β.

xi) Si no, existen α, β 6= 0 tales que α · β = 0 pero por vi), como α 6= 0, β ≤ α · β = 0, luego β = 0 , contradicci´on. El siguiente teorema demuestra que la multiplicaci´on de ordinales restringida a ω verifica las propiedades que esperamos que ´esta verifique, a saber, que sea conmutativa y que distribuya por la derecha sobre la suma. Cabe destacar que la multiplicaci´on ordinal en general no verifica estas propiedades. Por ejemplo, 2 · ω = ω 6= ω + ω = ω · 2 y por ende ω = (1 + 1) ω 6= ω + ω Teorema 3.36. Sean m , n y l n´ umeros naturales. Entonces i) m · n es natural. ii) m · n = n · m. iii (m + n) · l = m · l + n · l. ´ n. Demostracio i) Por inducci´on sobre n . ii) Por inducci´on sobre n . – Si n = 0, entonces m · n = n · m = 0 – Si m · k = k · m, demostraremos por inducci´on sobre m que para todo m, m · Sk = Sk m. – Si m = 0, m · Sk = Sk m = 0 89

– Si l · Sk = Sk · l, entonces Sl · Sk = = = = = = = = = =

Sl · k + Sl k · Sl + Sl, (k · l + k) + Sl (l · k + k) + Sl, (l · k + Sl) + k, (l · k + (l + 1)) + k (l · k + l) + (k + 1) l · Sk + Sk Sk · l + Sk, Sk · Sl.

por hip´otesis de inducci´on sobre m, por hip´otesis de inducci´on sobre, n por 3.30, i) y 3.31 iii),

por hip´otesis de inducci´on sobre, m

Esto completa ambas inducciones. N´otese que en la demostraci´on anterior se hizo una doble inducci´on, es decir, el paso de inducci´on se demostr´o, a su vez, por inducci´on. Teorema 3.37. (Algoritmo de la divisi´on). Si α y β son ordinales y β = 6 0, entonces existe un u ´nico γ y un u ´nico δ tales que α=β·γ+δ

,

γ≤α

y δ < β.

´ n. Como ×β es normal, en virtud de 3.26, existe un Demostracio u ´nico γ tal que β · γ ≤ α < β · Sγ = β · γ + β. Por 3.30, iii) existe un u ´nico δ tal que β·γ+δ =α. Por 3.35, vi), es claro que γ ≤ α. Adem´as, δ < β, pues si β ≤ δ, α < β · γ + β ≤ β · γ + δ = α. Teorema 3.38. Las siguientes afirmaciones son equivalentes. i) α es l´ımite. ii) α = ω · γ, para alg´ un γ 6= 0. iii) Para todo m ∈ ω − {0}, m · α = α y α 6= 0. ´ n. Demostracio i) ⇒ ii) Por el algoritmo de divisi´on, existen γ y δ tales que γ ≤ α, δ < ω y α = ω · γ + δ. 90

Si δ 6= 0 , δ = Sm, para alg´ un m ∈ ω, entonces α = ω · γ + Sm = S(ω · γ + m), o sea α no es l´ımite. Por lo tanto δ=0y α = ω · γ. Obviamente γ 6= 0 pues si no, α = 0. ii) ⇒iii) Primero verifiquemos que para todo m ∈ ω−{0} m·ω = ω. En efecto, por 3.35, vi), ω ≤ m · ω = ∪{m · n : n ∈ ω} ⊆ ω,

luego m · ω = ω. Entonces si m 6= 0 y α = ω · γ, para alg´ un γ 6= 0, m · α = m · (ω · γ) = (m · ω) · γ = ω · γ = α

iii) ⇒i) Supongamos m · α = α, α 6= 0 y α = Sβ para alg´ un β . Entonces α = 2 · α = 2 · Sβ = 2 · β + 2 ≥ β + 2 > β + 1 = α,

una contradicci´on, luego α es l´ımite. 7.3. Exponenciaci´ on de Ordinales.

´ n 3.12. Sean α y β ordinales. Definimos por recursi´on Definicio la exponenciaci´on de ordinales como sigue. i) α0 = 1. ii) αSβ = αβ · α. S iii) αβ = ∪{αγ : γ ∈ β}, si β = β 6= 0.

Como en el caso de la suma y la multiplicaci´on, hemos definido la exponenciaci´on por recursi´on usando el teorema 3.20, donde [ G(x) = x · α y H(x) = 1 ∪ x. Teorema 3.39. Para todo par de ordinales α > 1 y β , la funci´on expα : β −→ αβ γ 7→ αγ ,

es una funci´on normal.

´ n. Como expα es continua por definici´on, basta Demostracio demostrar que es estrictamente creciente. Para ello usamos el teorema 3.22. Por inducci´on podemos demostrar que αβ 6= 0 para todo ordinal β . Luego, expα (β) = αβ = αβ · 1 < αβ · α = αSβ = expα (Sβ). 91

Las propiedades de la exponenciaci´on de ordinales se resumen en el siguiente teorema. Teorema 3.40. i) α

0 =

ii) iii) iv) v) vi) vii) viii) ix) x)



0 1

, si α es sucesor, , si α es l´ımite o α = 0.

1α = 1. α0 = 1, α1 = α y α2 = α · α. Si α, β > 1, entonces α < αβ . Si α > 1, entonces β ≤ αβ . Si α > 1 y β < γ, entonces αβ < αγ . Si α 6= 0, entonces αβ+γ = αβ · αγ . Si α 6= 0, entonces (αβ )γ = αβ·γ . Si α > 1 y β 6= 0, entonces 1 < αβ . Si α, β > 1, entonces α · β ≤ αβ .

´ n. Demostracio i) y ii) se demuestran por inducci´on. iii) es obvio. iv) se verifica porque expα es estrictamente creciente y α1 = α. v) se puede demostrar por inducci´on sobre β o por 3.21 porque expα es normal para α > 1. vi) simplemente expresa que expα es creciente para α > 1. vii) Por inducci´on sobre γ . – Si γ = 0, entonces αβ+γ = αβ = αβ · 1 = αβ · α0 = αβ · αγ . – Si αβ+γ = αβ · αγ , entonces αβ+Sγ = αS(β+γ) = αβ+δ · α = (αβ · αγ ) · α

= αβ · (αγ · α) = αβ · αSγ . 92

– Si γ = ∪γ 6= 0 y para todo δ ∈ γ, αβ+δ = αβ · αδ , entonces como β + γ es l´ımite y usando el teorema 3.24 αβ+γ = = =

[

{αε : ε < β + γ}

[

{αβ+δ : δ ∈ γ}

[ [

{αε : β ≤ ε < γ}

{αβ · αδ : δ ∈ γ} [ = αβ · {αδ : δ ∈ γ} =

= αβ · αγ ,

lo que completa la inducci´on. viii) Por inducci´on sobre γ – Si γ = 0 , entonces (αβ )γ = (αβ )0 = 1 = α0 = αβ·0 = αβ·γ . – Si (αβ )γ = αβ·γ , entonces (αβ )Sγ = (αβ )γ · αβ

= αβ·γ · αβ , y por vii), = αβ·γ+β = αβ·Sγ .

– Si γ = ∪γ 6= 0 y para todo δ ∈ γ, entonces

(αβ )γ = = =

[

{(αβ )δ : δ ∈ γ}

[

{αε : ε ∈ β · γ}

[

(αβ )δ = αβ·δ ,

{αβ·δ : δ ∈ γ}.

= αβ·γ

,

ya que β · γ es l´ımite. Para demostrar el paso anterior, debe usarse un argumento similar al empleado en la demostraci´on de vii). Esto completa la inducci´on. ix) Si 1 < α y 0 < β, entonces por vi), 1 = α0 < αβ . x) Por inducci´on sobre β . – Si β = 2, entonces α · β = α · 2 = α + α ≤ α · α = α2 = αβ 93

– Si α · β ≤ αβ , entonces α · Sβ = ≤ ≤ =

α·β+α αβ + α αβ · α αSβ .

– Si β = ∪β 6= 0 y para todo γ ∈ β, α · γ ≤ αγ , entonces [ α·β = {α · γ : γ < β} [ ≤ {αγ : γ < β} = αβ .

Esto completa la inducci´on. El u ´ltimo teorema de esta secci´on nos dice que la exponenciaci´on de ordinales restringida a los n´ umeros naturales tiene las propiedades que esperamos que ´esta tenga. Teorema 3.41. Sean l , m y n n´ umeros naturales. Entonces n i) m es un n´ umero natural. ii) (l · m)n = ln · mn ´ n. Ambas se demuestran por inducci´on sobre n. Demostracio

Ejercicios. 1. Demuestre que los ´ordenes definidos en 3.34 y 3.29 son buenos ordenes. 2. Demuestre la asociatividad de la multiplicaci´on, 3.35, ii). 3. Demuestre tambi´en 3.35, iii), iv), v) y ix). 4. Demuestre el teorema 3.41. 5. Encontrar ordinales α, β, γ tales que α + γ = β + γ y α 6= β. 6. Probar que: (a) Si α ≤ β, entonces γ + α ≤ γ + β. (b) Si γ + α < γ + β, entonces α < β. (c) Si α + γ < β + γ, entonces α < β. (d) Si α < β, entonces para todo n ∈ ω se tiene α+n < β+n. (e) Si α + α = α, entonces α = 0. (f) Si α + α = β + β, entonces α = β. (g) Probar que si α + β = ω, entonces α ∈ ω y β = ω. (h) Si γ + α = γ + β, entonces α = β. 94

7. Probar que si β 6= 0, entonces α + β es ordinal l´ımite si y s´olo si β es ordinal l´ımite. 8. Probar que α + γ = α ∪ {α + β : β ∈ γ}. S 9. S Probar que si β es ordinal l´ımite, entonces {α + γ ; γ ∈ β} = {δ : δ ∈ α + β}. 10. Sea F una operaci´on tal que si αPes ordinal, entonces F (α) es ordinal. F sobre los ordinales por: P Definimos la operaci´on • F (0) = 0 ; P P • si α es ordinal, entonces = F (α) + (α) ; F (Sα)P S FP { F (β) : • si α es ordinal l´ımite, entonces F (α) = β ∈ α} ; P • si α no es ordinal, entonces F (α) = 0. ProbarPque: a bien definida sobre (a) F est´ P los ordinales. (b) Si α es ordinal, entonces P P F (α) es ordinal. (c) Definimos (β) = F (α). β∈α F P (i) Probar que n∈ω n = ω. (ii) Para cada n ∈ ω definimos fn por: (A) Dom (fn ) = ω + 1 ; (B) si m ∈ ω y m 6= n , entonces fn (m) = m ; (C) fn (n) = ω ; (D) fn (ω) =Pn. Probar que α∈ω+1 fn (α) = ω + ω + n. P (iii) Probar que si β < α , entonces γ∈β F (γ) ≤ P γ∈α F (γ). (iv) Sea α un ordinal. Probar que si G es una operaci´on que lleva ordinales en ordinales, entonces si para todo β que F (β) ≤ G(α) , entonces P β < α implica P β∈α F (β) ≤ β∈α G(β). Probar que “ ≤ ” se puede reemplazar por “ < ” si se agrega la condici´on de que si γ ∈ α , entonces F (γ) 6= 0 . (v) Si F es tal que P para todo β < α se tiene F (β) = 1 , entonces α = β∈α F (β). (vi) Probar que si α es ordinal l´ımite P y para todo β < α se tiene F (β) 6= 0 , entonces en β∈α F (β) es tambi´ ordinal l´ımite. 11. Probar que para todo ordinal α existe un ordinal l´ımite β y un n ∈ ω tales que α = β + n. 12. Probar que no existe un ordinal γ tal que para cualquier par de ordinales δ y β tales que δ < β se tenga α + δ < γ < α + β. 95

13. Probar que si α 6= 0 , entonces α + ω < ω + α. 14. Diremos que β es un residuo de γ si β 6= 0 y existe α tal que α + β = γ. Probar que si α > β y α y β son residuos de γ , entonces β es residuo de α . 15. Probar que: (a) Si α + β = ω, entonces α · β = ω. (b) Si γ · α < γ · β, entonces α < β . (c) Si γ 6= 0 y γ · α = γ · β , entonces α = β. (d) Si β · γ < α · γ, entonces β < α . (e) Si α · γ = β · γ y γ 6= 0 no es ordinal l´ımite, entonces α = β. 16. Bajo divisi´on por 2 un ordinal tiene por resto a 0 o a 1 , y se dir´a que tal ordinal es par o impar en los respectivos casos. Clasificar los siguientes ordinales en pares o impares: (a) ω ; (b) ω + 1 ; (c) (ω + 1)2 ; (d) (ω + 1) · 2. 17. Por vecindad de un ordinal entendemos un intervalo abierto (β, γ) = {δ : δ es ordinal y β < δ < γ} al que pertenece el ordinal. Una operaci´on F sobre el ordinal α que lleva ordinales en ordinales puede ser representada por (αi )i∈α , donde αi = F (i) , para todo i ∈ α. En tal caso hablamos de una sucesi´on de ordinales (es claro que si F es operacion arbitraria que lleva ordinales en ordinales, restringi´endola a un ordinal cualquiera la consideramos como sucesi´on de ordinales). Diremos que una sucesi´on de ordinales tiene l´ımite λ = limi∈α ai si y s´olo si dada una vecindad (β, γ) de λ , existe un ordinal δ ∈ α tal que si δ ≤ i < α se tiene αi ∈ (β, γ). (a) Probar que limi∈α αi es el supremo de {αi : i ∈ α} , si (αi )i∈α es una sucesi´on de ordinales estrictamente creciente. (b) Dar un ejemplo de dos sucesiones de ordinales estrictamente crecientes (αi )i∈α y (βi )i∈α , tales que limi∈α αi + limi∈α βi 6= limi∈α (αi + βi ). (c) Probar que α es l´ımite de cualquier sucesi´on de ordinales tal que (αi )i∈α ⊆ Sα , pero no existe una sucesi´on de ordinales (αi )i∈ω que simult´aneamente est´e contenida en Sα − {α} y que tengta a α como l´ımite. (d) Sea (αi )i∈α una sucesi´on estrictamente creciente de ordinales con λ como l´ımite. Probar que αi 6= λ para todo i ∈ α. Adem´as, probar que λ es ordinal l´ımite. 96

18. 19.

20. 21. 22.

(e) Sea (αi )i∈α una sucesi´on de ordinales no necesariamente creciente. Probar que si α es ordinal sucesor entonces existe limi∈α αi , pero si α es ordinal l´ımite no necesariamente existe tal l´ımite. (f) Si (αi )i∈α es un a sucesi´on estrictamente creciente de ordinales, probar que para todo ordinal λ se tiene λ + limi∈α αi = limi∈α (λ + αi ) , pero no necesariamente se tiene limi∈α αi + λ = limi∈α (αi + λ). Probar tambi´en que λ · (limi∈α αi ) = limi∈α (λ · αi ) , pero no necesarimente (limi∈α αi ) · λ = limi∈α (αi · λ). Sea (αi )i∈α una sucesi´ P on de ordinales tal que αi = β para todo i ∈ α. Probar que i∈α αi = β · α. (a) Probar que n · ω = ω si n ∈ ω. (b) Probar que α es ordinal l´ımite si y s´olo si n · α = α para todo n ∈ ω. Probar que si α 6= 0 es ordinal sucesor, entonces para todo γ 6= 0 se tiene (γ + 1) · α > γ · α. S Probar que si β es ordinal l´ ımite y α = 6 0 , entonces {α · γ : S γ ∈ β} = {δ : δ ∈ α · β}. Sea Q F una operaci´on que lleva ordinales en ordinales. Definimos F (α) Qpor: ; • QF (0) = 1 Q • F (Sα) = F (α) · F (α) ; • Si α es ordinal l´ımite y existe β ∈ α tal que F (β) = 0 , Q entonces F (α) = 0 ; • Si α es ordinal Q l´ımiteSy para todo β ∈ α se tiene F (β) 6= 0 {F (β) Q : β ∈ α} ; , entonces F (α) = • Si α no es ordinal, entonces F (α) = 0. Probar Qque: (a) QF est´a bien definida. (b) QF (α) es un ordinal si α lo es. (c) F (α) = 0Qsi y s´olo si existe Q β ∈ α tal que F (β) = 0. (d) Definimos β∈α F (β) := F (α). Para cada n ∈ ω definimos fn por: (i) Dom (f n) = ω + 1 ; (ii) si m ∈ ω y m 6= n , entonces fn (m) = m + 1 ; (iii) fn (n) = ω ; (iv) fn (ω)Q = n + 1. Entonces α∈ω+1 fn (α) = ω · ω · (n + 1). (e) Si para toda tiene F (γ) 6= 0 , entonces si β < α Q γ ∈ α se Q se tiene γ∈β F (γ) ≤ γ∈α F (γ). 97

23. 24. 25.

26. 27.

28. 29. 30. 31.

32. 33. 34. 35.

(f) Si G es una operaci´on que lleva ordinales en ordinales, entonces si para Q todo β ∈Qα se tiene F (β) ≤ G(β) , ello implica que β∈α F (β) ≤ β∈α G(β). Simplificar ω + ω · ω y (ω + 1) · ω · ω. Probar que si β > 1 es aditivamente indescomponible y α > 0 , entonces α · β es aditivamente indescomponible. Sean α y β ordinales. Probar que si F es una operaci´on sobre los ordinales tal que F (γ) = α para todo γ ∈ β , entonces Q F (γ) = αβ . γ∈β Encontrar la suma y el producto de la sucesi´on de ordinales (αi )i∈ω tal que αi = ω i , para todo i ∈ ω. Sea (αi )i∈ω la sucesi´on de ordinales tal que α0 = ω y αSβ = S (αβ )ω para β ∈ ω. Sea 0 = {αi : i ∈ ω}. Probar que 0 = ω 0 . (a) Probar que si α < 0 , entonces: (i) α + 0 = 0 . (ii) α · 0 = 0 . (iii) α0 = 0 .  (b) Probar que β ω 0 = β ω·0 para todo ordinal β Probar que si α es ordinal l´ımite y γ 6= 0 , entonces αγ es ordinal l´ımite. Probar que si n ∈ ω , entonces nω = ω. Probar que si α es ordinal l´ımite y p y q son naturales, entonces (α · p)q = αq · p. Sean α y β ordinales tales que α 6= 0 y β > 1. Probar que existen u ´nicos ordinales γ , δ y ρ tales que α = β γ · δ + ρ y 0 6= δ ∈ β y ρ ∈ β γ . Probar que si α 6= 0 y β 6= 0 , entonces α · ω β = Sα · ω β . Probar que si α < ω δ y β < ω δ , entonces α + β < ω δ . δ δ δ Probar que si α < ω ω y β < ω ω , entonces α · β < ω ω . Calcular: P (a) Pα∈ω 2ω . (b) Pα∈ω2 α2 . (c) Pn∈ω ω · n. (d) Q n∈ω ω n . (e) Qα∈ω2 (α + 1). (f) Qn∈ω ω n . (g) n∈ω (ω + n). (h) ω 1˙ + ω · 2 + ω · 3 + . . . + 1 + 2 + 3 + . . . (i) ω · ω 2 · ω 3 · . . . · 1 · 2 · 3 · . . . (j) ω · ω 2 · ω 3 · . . . · ω n−1 · ω n+1 · . . . · 2 · 3 · . . . 98

36. Expresar en la forma ω αn · an + ω αn−1 · an−1 + . . . + ω α1 · a1 + a0 , donde α1 < α2 < . . . < αn−1 < αn son ordinales , n ∈ ω , y ai ∈ ω − 1 para i ∈ Sn : (a) 3 · ω (b) (ω + 1)2 (c) ω · 2 · (ω + 1) (d) (ω + 1) · 2 (e) (ω 2 · 2 + ω · 4 + 3) · 5 (f) 2 + ω · 2 + ω 2 (g) (ω 2 · 3 + ω · 2) · (ω 3 · 2 + ω · 4 + 2) 37. Diremos que α > 1 es ordinal primo si no existen β y γ tales que 1 < β < α y 1 < γ < α y α = β · γ. (a) Probar que si n ∈ ω , esta definici´on coincide con la definici´on cl´asica de ser primo. (b) Probar que los siguientes ordinales son primos : ω, ω + 1, ω 2 + 1, ω 3 + 1, ω ω . (c) Probar que si α > 1 , entonces existe n ∈ ω tal que para todo m < n existe un ordinal primo αm , con los que se tiene : Y α= αm . m∈n

¿ Es u ´nica esta representaci´on ? ( ver ω 2 ). (d) Probar que si α es ordinal l´ımite , entonces α es primo si β y s´olo si existe un ordinal β tal que α = ω ω . (e) Probar que si α > ω es ordinal sucesor, entonces α es primo si y s´olo si existe β > 0 tal que α = ω β + 1. 38. Probar las siguientes factorizaciones en primos: (a) ω 2 + ω + 1 = (ω + 1)2 (b) ω 2 · 3 + 1 = (ω 2 + 1) · 3 (c) ω 2 + 2 = 2 · (ω 2 + 1) (d) ω 3 · 7 + ω 2 · 5 + 3 = 3 · (ω 2 + 1) · 5 · (ω + 1) · 7 (e) ω ω + ω + 1 = (ω + 1) · (ω ω + 1) (f) ω ω+1 + ω ω + ω 4 + ω 2 = ω · ω · (ω 2 + 1) · (ω ω + 1) · (ω + 1) 39. Expresar como producto de primos: (a) ω 4 + 24 (b) ω · 2 + 1 (c) ω 2 + ω · 2 + 1 (d) ω 3 · 3 + ω 2 · 7 + 6 (e) ω ω + ω 3 + ω 2 (f) ω ω+1 · 2 + ω ω · 3 + 2 (g) ω 6 · 2 + ω 5 · 5 + ω 3 + ω 2 · 7 2 (h) ω ω · 6 + ω ω+5 · 3 + ω ω+1 · 2 + ω ω · 4 99

40. Calcular los siguientes l´ımites: (a) limn∈ω (2n + n) (b) limn∈ω n · ω (c) limn∈ω ω · n (d) limβ∈ω2 β · ω (e) limβ∈ω·2 2β (f) limβ∈ω·2 β 2 41. Diremos que el ordinal α es un n´ umero ´epsilon si α = ω α . α+1 ω α+1 (a) Definimos E(α) := (α + 1) + ω α+1 + ω ω + ωω + ... Probar que E(α) es un n´ umero ´epsilon, que α < E(α) , que no existe un n´ umero ´epsilon β tal que α < β < E(α). Probar tambi´en que si α < β y no existe un n´ umero ´epsilon γ tal que α < γ ≤ β , entonces E(α) = E(β). (b) Probar que si definimos εα por: • ε0 = E(0); • εSα = E(εα ); • si α es ordinal l´ımite, entonces εα = limβ∈α εβ , entonces para todo ordinal α se tiene que εα es un n´ umero ´epsilon y que si β es un n´ umero ´epsilon, entonces existe un ordinal α tal que β = εα . (c) Probar que si β es un n´ umero ´epsilon, entonces dado un ordinal α , se tiene que si 2 ≤ α < β , entonces α+β = β y α · β = β y αβ = β. (d) Probar que si existe un ordinal α ≥ ω tal que αβ = β , entonces β es un n´ umero ´epsilon. (e) Probar que si αβ = β, entonces α · β = β. (f) Probar que si α · β = β, entonces α + β = β. β (g) Probar que si β es un n´ umero ´epsilon, entonces αω = (αω )β , para todo ordinal α . (h) Probar que si α es ordinal l´ımite y β es un n´ umero ´epsilon tales que α < β , entonces αβ·α = (β · α)α . 42. Encontrar un conjunto de racionales tales que bajo su orden usual sea isomorfo a: (a) ω + 1 (b) ω · 2 (c) ω · 3 (d) ω ω ( Por ejemplo, { n+1 : n, m ∈ N − {0}} es isomorfo a ω 2 ). m P Q 43. Si λ = γ∈δ βγ , entonces αλ = γ∈δ αβγ . 44. Probar que: P 3 (a) Si para γ ∈ ω se tiene αγ = ω 2 , entonces γ∈ω αγ = ω . 100

Q (b) Si para γ ∈ ω + ω se tiene αγ = ω , entonces γ∈ω+ω αγ = ω+ω ω . Q ω (c) Si para γ ∈ ω se tiene αγ = ω γ , entonces γ∈ω αγ = ω 45. Probar que para todo α , ω α es aditivamente indescomponible. 8. La Jerarqu´ıa Acumulativa de Conjuntos En esta secci´on construiremos recursivamente una clase de conjuntos que es de gran importancia en el estudio m´as avanzado de los fundamentos de la teor´ıa de conjuntos. Si bien estos temas caen fuera del alcance de este libro, esta construcci´on, llamada la jerarqu´ıa acumulativa de conjuntos, ayuda a entender la complejidad relativa de los conjuntos y el rol que juega el axioma de regularidad en la estructura de los mismos. ´ n 3.13. Para cada ordinal α definimos Definicio V0 = ∅ Vα+1 = PVα [ Vγ , si λ es l´ımite. Vλ = γ∈λ

La colecci´on de los Vα se llama la jerarqu´ıa acumulativa de conjuntos. Es usual definir tambi´en el universo de von Neumann a la clase propia [ V = {Vα : Ord(α)}.

Observemos que los Vα est´an bien definidos en virtud del teorema 3.20, ii). Las operaciones empleadas son G(x) = Px

y

H(x) =

[

x.

Debe tambien tenerse presente que V no es un objeto de nuestra teor´ıa y debe entenderse s´olo como una manera de abreviar un concepto correspondiente a la f´ormula ϕ(x) = ∃α(Ord(α) ∧ x ∈ Vα ). Como veremos, el axioma de regularidad es equivalente a decir que todo conjunto verifica varphi(x). Teorema 3.42. 1. Si α ≤ β, entonces Vα ⊆ Vβ . 2. Si α ∈ β, entonces Vα ∈ Vβ . 3. Para todo α, Vα es ∈–transitivo. 101

El pr´oximo lema es necesario para demostrar el principal teorema de esta secci´on. Lema. Sea a un conjunto, entonces ϕ(a) si y s´olo si para todo x ∈ a, ϕ(x). M´as informalmente, un conjunto pertenece a V si y s´olo si todos sus elementos tertenecen a V. ´ n. Si a pertenece a V , entonces a ∈ Vα para alg´ Demostracio un ordinal α. Pero como Vα es ∈–transitivo, todos los elementos de a pertenecen a Vα . Supongamos que todos los elementos de a pertenecen a V. Para cada x ∈ a, sea γ(x) el menor ordinal γ tal que x ∈ Vγ . Definamos [ α = {γ(x) : x ∈ a}, el que est´a bien definido en virtud del axioma de reemplazo. Entonces a ⊆ Vα y por lo tanto a ∈ PVα = Vα+1 , lo que termina nuestra demostraci´on.

Resulta sencillo verificar que la clase V es cerrada bajo uniones, pares, potencias productos cartesianos y dem´as construcciones que hemos estudiado en los cap´ıtulos precedentes. Esto implica que todos los conjuntos que aparecen en la pr´actica, pertenecen a V. ¿ Existir´a alg´ un conjunto que no est´a en V? El siguiente teorema, atrav´es de una aplicaci´on del axioma de regularidad, demuestra que este no es el caso. Teorema 3.43. Todo conjunto pertenece a alg´ un Vα . (M´as informalmente, para todo conjunto x , x ∈ V.) ´ n. Recordemos que la clausura transitiva de a , que Demostracio denotamos T (a), es el menor conjunto ∈–transitivo que contiene a a , ver ejercicio 1 y que intuitivamente [ [[ [[[ T (a) = a ∪ a ∪ a∪ a··· .

Supongamos que existe un conjunto a tal que a ∈ / V, o m´as formalmente, supongamos ¬ϕ(a), donde varphi(x) es la f´ormula de L1 que lo expresa. (Ver m´as arriba.) Entonces por el lema 8 b = {x ∈ T (a) : ¬ϕ(x)} 6= ∅. Tomemos cualquier elemento c ∈ b. Entonces por el mismo lema, existe x ∈ c talque ¬ϕ(x), y como adem´as x ∈ T (a), x ∈ b, es decir x ∈ c ∩ b, lo que contradice el axioma de regularidad. 102

Ejercicios. 1. 2. 3. 4.

Demuestre Demuestre Demuestre Demuestre

S que para todo α, Vα = {PVβ : β < α}. el teorema 3.42. α es el mayor ordinal que pertenece a Vα . el axioma de regularidad a partir del teorema 3.43.

103

104

CAPITULO 4

El Axioma de Elecci´ on El u ´ltimo axioma de la teor´ıa de conjuntos en cierta medida pertenece a una categor´ıa aparte debido a las importantes consecuencias que de ´el se desprenden. Estudiaremos varias formulaciones diferentes de ´este y enseguida algunas de sus aplicaciones. 1. Equivalencias del Axioma de Elecci´ on Axioma de Elecci´ on (AC): “Si A es un conjunto de conjuntos no vac´ıos, entonces existe una funci´on F cuyo dominio es A y tal que para todo x ∈ A, F x ∈ x ”. Tal funci´on se llama una funci´ on de elecci´ on para A . Observemos que [ F : A −→ A x 7−→ F x ∈ x

La existencia de una funci´on de elecci´on implica elegir simult´aneamente un elemento de cada conjunto que pertenece a A . Esto no representa ning´ un problema si A es finito, sin embargo si A es infinito, no es en absoluto intuitivo que se pueda hacer. N´otese tambi´en que el axioma no da ninguna idea de como construir tal funci´on. La siguiente es una lista de los principios m´as importantes que son equivalentes al axioma de elecci´on. 1. Principio Multiplicativo: Si A es una funci´on y Dom A = I y si Ai = A(i) 6= ∅, entonces Πi∈I Ai 6= ∅. 2. Principio de Zermelo: Si P es una partici´on de un conjunto A , entonces existe B ⊆ A tal que para todo M ∈ P , B ∩ M tiene un solo elemento. Recordemos que toda partici´on sobre A induce una relaci´on de equivalencia cuyo campo es A y cuyas clases de equivalencia son los elementos de P . El principio de Zermelo nos dice que podemos escoger un elemento de cada clase de equivalencia, es decir un sistema de representantes de las clases de equivalencia. 105

3. Principio de Enumeraci´ on: Para todo conjunto A existe un ordinal α y una funci´on biyectiva entre ellos. 4. Principio de Buen Orden: Todo conjunto puede bien ordenarse. 5. Lema de Zorn: Si A es un conjunto parcialmente ordenado por R y todo subconjunto de A totalmente ordenado por R tiene una cota superior en A , entonces A tiene un elemento maximal. Un subconjunto de A totalmente ordenado por R se llama una R-cadena. N´otese que la hip´otesis del lema de Zorn implica que A 6= ∅ ya que ∅ es una R-cadena luego tiene una cota superior en A . 6. Principio de Kuratowski: Si R es un orden parcial y S ⊆ R es un orden total, entonces hay un orden ⊆-maximal T tal que S ⊆ T ⊆ R. Dicho de otro modo, todo suborden total de un orden parcial puede extenderse a un orden total maximal. 7. Principio de Tricotom´ıa: Dados dos conjuntos A y B , existe una funci´on inyectiva de A en B o existe una funci´on inyectiva de B en A . 8. Principio de la Imagen Inversa: Dados dos conjuntos no vac´ıos A y B , existe una funci´on sobreyectiva de A en B o existe una funci´on sobreyectiva de B en A . Como veremos en el Cap´ıtulo 5 estos dos u ´ltimos principios son muy importantes en la teor´ıa de cardinalidad. Teorema 4.1. Todos los principios anteriores son equivalentes al axioma de elecci´on. ´ n. Primero demostraremos AC ⇒ 1) ⇒ 2) ⇒ AC. Demostracio AC ⇒ 1). Sea A una funci´on con Dom A = I tal que para todo i ∈ I, Ai 6= ∅, . Entonces, por el axioma de reemplazo, A = {Ai : i ∈ I} es un conjunto de conjuntos no vac´ıos. Por AC, existe F, Dom F = A y para todo i ∈ I, F (Ai ) ∈ Ai . G : I −→

[

Ai

i∈I

i 7−→ F (Ai ) 106

G ∈ Πi∈I Ai ,

o sea,

Πi∈I Ai 6= .

1) ⇒ 2). Sea P una partici´on de A . Entonces P ⊆ PA, luego P es un conjunto. Consideremos IP , la funci´on identidad sobre P . Por 1) ΠM ∈P IP (M ) = ΠM ∈P M 6= ∅, luego existe una funci´on G , tal que Dom G = P y para todo M ∈ P, G(M ) ∈ M . Como M ⊆ A para todo M ∈ P, Rec G ⊆ A. Adem´as, como los elementos de P son disjuntos, para cada M ∈ P , M ∩ Rec G = {G(M )}. 2) ⇒ AC. Sea A un conjunto no vac´ıo de conjuntos no vac´ıos. Definamos K = {hx, yi : y ∈ x ∈ A} y P = {{hx, yi : y ∈ x} : x ∈ A}. Es claro que K es un conjunto (¿por qu´e?) y que P es una partici´on de K . Escojamos B ⊆ K tal que para cada M ∈ P, B ∩ M tiene exactamente un elemento. Entonces B es una funci´on de elecci´on para A . En efecto, para cada x ∈ A, B ∩ {hx, yi : y ∈ x} = {yx }, para alg´ un yx ∈ x. Luego B es funci´on, Dom B = A y para cada x ∈ A, B(x) ∈ x. La equivalencia de los otros principios la demostramos dando un gran c´ırculo de implicaciones que comienza y termina en AC. AC ⇒ 3. Sea A un conjunto. Vamos a encontrar un ordinal α y una funci´on biyectiva de α en A . Podemos suponer que A 6= ∅. Consideremos PA−{∅}. Este es un conjunto no vac´ıo de conjuntos no vac´ıos, luego existe una funci´on de elecci´on F para ´el. Notemos que ´esta asigna a cada subconjunto no vac´ıo de A un elemento de si mismo. Definimos por recursi´on una operaci´on unaria H como sigue  F (A − H ∗ α) , si A − H ∗ α 6= ∅, H(α) = A , si A − H ∗ α = ∅. Si α < β, entonces H ∗α ⊆ H ∗β A − H ∗ β ⊆ A − H ∗ α, 107

luego, si A − H ∗ α = ∅, entonces tambi´en A − H ∗ β = ∅. Por lo tanto, si α < β; y H(α) = A, entonces Hβ = A. Si α < β y H(β) 6= A, entonces como H(α) ∈ H ∗ β y por ser F funci´on de elecci´on, H(β) ∈ A − H ∗ β, H(α) 6= H(β).

Demostraremos ahora que existe un ordinal β tal que H(β) = A. (i.e. A − H ∗ β = ∅). Supongamos por el contrario que no existe. Entonces como H es una operaci´on unaria (definimos Hx = x si x no es ordinal) y como para todo par de ordinales α 6= β, Hα 6= Hβ, por el axioma de reemplazo, B = {α : Hα ∈ PA − {∅}} es un conjunto. Pero por la suposici´on anterior, B contiene a todos los ordinales, luego no es un conjunto, contradicci´on. Por lo tanto existe β tal que H(β) = A. Sea \ α = {γ ∈ Sβ : H(γ = A)}, es decir α es el menor ordinal tal que H(α) = A, luego si β < α , Hβ 6= A. Definimos G : α −→ A β 7−→ H(β).

Entonces G es una funci´on biyectiva. 3) ⇒ 4). Sea A un conjunto y sean α y G como en 3). Entonces R = {hx, yi ∈ A × A : G−1 x ≤ G−1 y} es un buen orden. 4) ⇒ 5). Sea ≤ un orden parcial con campo A , tal que toda cadena tiene una cota superior. Sea S un buen orden cuyo campo es A . Definimos la siguiente operaci´on unaria.   S − menor elemento de {a ∈ A : ∀x(x ∈ F ∗ α → x < a} si ´este es no vac´ıo, F (α) =  A si no.

Intuitivamente, F (0) elije el S-menor elemento de A . F (1) elije el S-menor elemento de {a ∈ A : F (0) < a}, etc. En general F (α es el S-menor elemento de aquellos elementos de A que son ≤-mayores que aquellos elementos de A que ya han sido elejidos por F en una etapa anterior a α . 108

Si β < α y F (α) 6= A, entonces como F (β) ∈ F ∗ α,

F (β) < S − menor{a ∈ A : ∀x(x ∈ F ∗ α → x < a)} = F (α).

Como en la demostraci´on anterior, existe β tal que F (β) = A, pues si no, por el axioma de reemplazo, {α : F (α) ∈ A}

es un conjunto de ordinales que contiene a todos los ordinales, lo que es una contradicci´on. Sea α el menor ordinal tal que F (α) = A, es decir, {a ∈ A : ∀x(x ∈ F ∗ α → x < a)} = ∅.

Vimos antes que para β < γ ∈ α , F (β) < F (γ), es decir, F ∗ α es una <-cadena. Como F ∗ α ⊆ A, por el Lema de Zorn, existe c ∈ A que es <-cota superior de F ∗ α, es decir ∀x(x ∈ F ∗ (α) → x ≤ c).

Es claro que c es maximal pues si no, existe b ∈ A tal que b > c, pero entonces ∀x(x ∈ F ∗ α → x < b) o sea ∗ b ∈ {a ∈ A : ∀x(x ∈ F α → x < a)} = ∅, lo que es una contradicci´on, luego c es maximal. 5) ⇒ 6). Sea R un orden parcial y S ⊆ R un suborden total. Sea A = {T : S ⊆ T ⊆ R y T es un orden total.

Consideramos A ordenado por inclusi’on. Entonces toda cadena B S tiene una cota superior, a saber, B. Por el lema de Zorn, A tiene un elemento maximal el que obviamente verifica la tesis de 6). 6) ⇒ 7). Sean A , B conjuntos. Definimos R = {hf, gi : Dom f ⊆ Dom g ⊆ A ∧ Rec f ⊆ Rec g ⊆ B ∧ f ⊆ g ∧ f es inyectiva ∧ g es inyectiva}

Es claro que R es un orden parcial. Por el principio de Kuratowski con S = ∅, existe S un orden total maximal T ⊆ R. Sea F = Cam T , F es una funci´on inyectiva, Dom F ⊆ A y Rec F ⊆ B. Supongamos que Dom F 6= A y Rec F 6= B, entonces existe a ∈ A − Dom F y b ∈ B − Rec F . Definimos G = F ∪ {(a, b)}, 0 T = T ∪ {hf, Gi : f ∈ T } ∪ {hG, Gi}. 109

Entonces, como G es inyectiva, Dom G ⊆ A y Rec G ⊆ B, T ⊂ T 0 ⊆ R, o sea, T no es maximal, una contradicci’on. Por lo tanto Dom F = A o bien Rec F = B. En el primer caso F es inyectiva de A en B , en el segundo caso, F −1 es inyectiva de B en A . 7) ⇒ 8). Sean A y B conjuntos no vac´ıos. Supongamos sin p´erdida de generalidad que existe una funci´on inyectiva, f : A −→ B. Sea a ∈ A y definamos

g(x) =



g : B −→ A f −1 (x) , si x ∈ f ∗ A, a , si x ∈ B − f ∗ A.

Entonces g es sobreyectiva. 8) ⇒ AC. Para demostrar esta implicaci´on debemos demostrar un lema previo. Lema 4.2. Sea B un conjunto. Entonces Γ = {α : existe funci´ on inyectiva f : α −→ B} tambi´en es un conjunto. ´ n. Sea M = {R : R es un buen orden y campo Demostracio R ⊆ B}. M ⊆ P(PB × PB), por lo tanto M es un conjunto. Como sabemos, por el teorema 3.27, para todo buen orden R existe un u ´nico ordinal α tal que R y {hβ, γi : β ≤ γ < α}, es decir, el orden de α , son isomorfos. Entonces Γ = {α : existe R ∈ M α es isomorfo con R}. En efecto, si α ∈ Γ existe una funci´on inyectiva f : α −→ B, entonces R = {hf (β), f (γ)i : β ≤ γ < α} ∈ M, R y α son isomorfos y el isomorfismo es precisamente f . Supongamos ahora que α es isomorfo a un buen orden R ∈ M y sea g : α −→ R tal isomorfismo. Entonces por ser isomorfismo, g es inyectiva y g : α −→ Cam R ⊆ B, es decir α ∈ Γ. Como M es conjunto, por el axioma de reemplazo, Γ es un conjunto. Demostremos ahora el teorema. Sea A un conjunto no vac´ıo de conjuntos no vac´ıos. Queremos encontrar una funci´on de elecci´on para 110

A . Como A es conjunto, P demostrado,

S

A tambi´en lo es,luego or el lema reci´en

Γ = {α : existe funci´on inyectivaf : α −→ P

[

A

es un conjunto de ordinales. Sea β S= ∪Γ + 1. Es claro que no existe una funci´on inyectiva de β en P A ya que β 6∈ Γ. Por otro lado, tampoco existe una funci´on sobreyectiva S f : A −→ β, pues si existiera, podriamos definir [ g : β −→ P A α 7−→ f −1∗ {α} ,

S o sea, existir´ıa una funci´on inyectiva de β en P A, contradiciendo la u ´ltima afirmaci´on. S Entonces por 8), existe una funci´on sobreyectiva g : β −→ A. Definamos F : A −→

[

a 7−→ g(

A \

g −1∗ a) .

FS es una funci´on de elecci´on. En efecto, si x ∈ A, entonces −1∗ x ⊆ A y como g es sobreyectiva T g−1∗ x 6= ∅ es un conjunto de ordinales g x. Es claro entonces que T −1∗ cuyo menor elemento es g( g x) ∈ x. 2. Aplicaciones En todas las ramas de las matem´aticas hay importantes aplicaciones del axioma de elecci´on. A continuaci´on daremos una breve lista con algunas de ´estas. 1. Todo espacio vectorial tiene una base. 2. La uni´on enumerable de conjuntos enumerables es enumerable. 3. Existe un conjunto de n´ umeros reales que no es Lebesgue-medible. 4. El producto de espacios compactos es compacto. 5. Todo anillo con unidad tiene un ideal maximal. 6. Todo orden parcial puede extenderse a un orden total. 7. El teorema de Hahn-Banach. 8. El teorema de completud para la l´ogica de primer orden. 9. Toda ´algebra de Boole es isomorfa a un campo de conjuntos. 111

Demostraremos algunas de ´estas. Supondremos que el lector maneja los conceptos involucrados en cada caso. Teorema 4.3. Todo espacio vectorial tiene una base. ´ n. Sea V un espacio vectorial y sea A = {B ⊆ V : Demostracio B es linealmente independiente}. Consideremos a A parcialmente ordenado por inclusi´on. Sea entonces C = {BiS: i ∈ I} una cadena de elementos de A . S Entonces C ⊆ V y C contiene a todos los miembros de la cadena. S Veremos ahora que CSes linealmente independiente. Sean v0 , v1 , . . . , vn−1 ∈ C, luego existe B0 , . . . , Bn−1 ∈ C tales que vi ∈ Bi , i < n. Pero C es una cadena, luego Bi ⊆ Bn−1 , i < n, por lo tanto S v0 , . . . , vn−1 ∈ Bn−1 y como ´este es linealmente independiente, C es un S conjunto linealmente independiente. Por lo tanto C pertenece a A , luego toda cadena de A tiene una cota superior y por el lema de Zorn A tiene un elemento maximal. Probar que un conjunto linealmente independiente maximal es una base es un ejercicio elemental de algebra lineal. Teorema 4.4. La uni´on enumerable de conjuntos enumerables es enumerable. ´ n. Recordemos que un conjunto A se dice enumerDemostracio able si existe una biyecci´on entre A y ω. Sea C un conjunto enumerable de conjuntos enumerables. Por simplicidad podemos suponer que los elementos de C son todos disjuntos. Si C = {Ai : i ∈ ω}, sea fi : ω −→ Ai una biyecci´on. Definimos F : ω × ω −→ S

[

Ai

hn, mi 7−→ fn (m)

g : ω × ω −→ Ai como sigue g(n, m) = fn (m). g es inyectiva ya que si g(n, m) = g(p, q) entonces fn (m) = fp (q) ∈ An ∩ Ap , y como los Aj son disjuntos se tiene que n = p. Entonces como las fi son inyectivas, m = q, o sea, g es inyectiva. 112

S g es sobreyectiva ya que si a ∈ Ai existe n tal que a ∈ An y como fn es sobreyectiva, existe m tal que a = fn (m) = g(n, m).

S Es decir, existe una biyecci´on g de ω × ω en C. Por otra parte es bien sabido que existen biyecciones entre ω y ω × ω (ver el cap´ıtulo 5). Si tomamos cualesquiera de ellas, digamos, h : ω −→ ω × ω, S entonces f = g ◦ h es una biyecci’on entre ω y C , luego este u ´ltimo es enumerable. Observemos que en la demostraci´on anterior aparentemente no hemos usado el axioma de elecci´on. Sin embargo ´este se us´o cuando escogimos las funciones biyectivas fi , especificamente, si Bi = {f : ω −→ Ai , f biyectiva } A = {Bi : i ∈ ω} es un conjunto no vac´ıo de conjuntos no vac´ıos (´esto u ´ltimo por hip´otesis) luego por el axioma de elecci´on existe para cada i un elemento fi ∈ Bi . Este teorema es el ejemplo cl´asico de uso encubierto del axioma de elecci´on. Durante a˜ nos los matem´aticos hicieron uso de argumentos como el anterior sin darse cuenta de que estaban usando un principio especial. Teorema 4.5. Existe un conjunto de n´ umeros reales que no es Lebesgue-medible. ´ n. Definimos sobre [0, 1) la siguiente relaci´on de eDemostracio quivalencia. x ∼ y ssi x − y ∈ Q Entonces ∼ induce una partici´on de [0, 1). Por el principio de Zermelo, existe un subconjunto B ⊆ [0, 1) tal que B contiene exactamente un representante de cada clase de equivalencia. Sea {ri }i∈ω una enumeraci´on de los racionales entre 0 y 1 (ver cap´ıtulo 5) y sea Bi = B + ri = {x + ri : x ∈ B}, donde la suma es m´odulo 1 i.e.  x+y si x + y < 1 x+y = x + y − 1 si x + y ≥ 1 Es bien sabido que si A es un conjunto Lebesgue-medible, entonces A + a tambi´en lo es; m´as a´ un, m(A) = m(A + a). 113

Notemos que todo x ∈ [0, 1) pertenece a alg´ un Bi puesto que ∼ induce una partici´on de [0, 1). Por lo tanto [ [0, 1) = bi . i∈ω

Adem´as la uni´on es disjunta ya que Bi ∩ Bj = ∅ si i 6= j. En efecto, si x, y ∈ B y x + ri = y + rj entonces x − y = rj − ri ∈ Q , o sea, x ∼ y y como B contiene un solo representante de cada clase de equivalencia, x = y, entonces ri = rj , o sea, i = j, contradicci´on, luego i 6= j ⇒ Bi ∩ Bj = ∅. Por lo tanto m([0, 1) = m(

[

Bi ) =

i∈ω

X

m(Bi ).

i∈ω

Si B fuera medible, por la observaci´on hecha anteriormente, para S todo i ∈ ω, m(BiS ) = m(B), entonces si m(B) = 0, m( Bi ) = 0 y si m(B) 6= 0, m( Bi ) = ∞, pero m([0, 1)) = 1, por lo tanto B no puede ser medible. Teorema 4.6. Todo orden parcial puede extenderse a un orden total sobre el mismo campo. ´ n. Sea ≤ un orden parcial, B = Cam ≤. Demostracio Consideremos el conjunto de todos los ´ordenes totales que extienden a≤ A = {R ⊆ B × B : R es un orden total y ∀x, y(x ≤ y → x Ry), A est´a ordenado por inclusi´on. S Sea {Ri }, i ∈ I, una cadena de elementos de AS. Es claro que S Ri es un orden total y que si x ≤ y, entonces x Ri y, es decir Ri es una cota superior de la cadena que pertenece a A , luego, por el lema de Zorn, A tiene un elemento maximal. Llamemoslo M . Para demostrar nuestro teorema es suficiente probar que campo M = B. Supongamos que no es as´ı, entonces existe a ∈ B − Cam M . Definimos el nuevo orden R como sigue R = M ∪ {hx, ai : x ∈ Cam M, a ≤ x} ∪ {ha, xi : x ∈ Cam M, x ≤ a}. 114

Es f´acil verificar que R es un orden total que extiende a M , contradicci´on.

Ejercicios. 1. Demuestre sin usar el axioma de elecci´on que todo conjunto tiene una funci´on de elecci´on. (Indicaci´on: Use inducci´on sobre el n´ umero de elementos del conjunto). 2. Demuestre que el conjunto K definido el el teorema 4.1, 2) ⇒ AC es efectivamente un conjunto y que el conjunto P es una partici´on de K . 3. Complete los detalles de la demostraci´on de 4.1, 5) ⇒ 6). 4. Demuestre que la relaci´on R definida en la demostraci´on del teorema 4.1, 6) ⇒ 7), es efectivamente un orden parcial. 5. Demuestre que toda relaci´on binaria contiene una funci´o con el mismo domino.

115

116

CAPITULO 5

Cardinales En este cap´ıtulo investigaremos uno de los t´opicos m´as importantes de la teor´ıa de conjuntos, a saber, la teor´ıa de la cardinalidad o n´ umero de elementos que tiene un conjunto. Hasta el momento sabemos c´omo contar los elementos de los conjuntos finitos. En este cap´ıtulo formalizaremos estos conceptos intuitivos y los generalizaremos a conjuntos infinitos. La mayor parte de los teoremas de este cap´ıtulo dependen del axioma de elecci´on. Indicaremos ´estos mediante el s´ımbolo † . 1. Definiciones y Resultados B´ asicos ´ n 5.1. Definicio i) Dos conjuntos A y B son equinumerosos ssi existe una biyecci´on entre A y B . En tal caso escribimos A ∼ B. ii) Un ordinal α es un cardinal ssi α no es equinumeroso con ninguno de sus elementos. Si α es un cardinal escribimos Car (α). En general usaremos letras g´oticas min´ usculas m, n, p · · · para designar cardinales. Ejemplo. 1. Dos intervalos de n´ umeros reales son siempre equinumerosos. Para demostrar esto basta ver que f : [a, b] −→ [c, d] d−c cb − ad x 7−→ x+ b−a b−a es una biyecci´on. 2. Todo intervalo abierto es equinumeroso con el conjunto de los n´ umeros reales. Consid´erese la funci´on π π tan : (− , ) −→ R 2 2 Sabemos que tan x es una biyecci´on. Una funci´on similar a la del ejemplo anterior demuestra que cualquier intervalo abierto es equinumeroso con (− π2 , π2 ). 117

3. ω y ω × ω son equinumerosos. Consid´erese la funci´on f : ω × ω −→ ω hm, ni 7−→ 2m (2n + 1) − 1 .

f es una biyecci´on. Resulta claro que la relaci´on “ser equinumeroso” es reflexiva, sim´etrica y transitiva, pero no es una relaci´on dentro de nuestra teor´ıa ya que su campo es la clase de todos los conjuntos. Naturalmente, si nos restringimos a un conjunto particular, ´esta es una relaci´on de equivalencia. En el caso finito, la cantidad de elementos de un conjunto nos sirve como una noci´on de tama˜ no. Para ello se identifica todos aquellos conjuntos que tienen el mismo n´ umero de elementos, en otras palabras, todos aquellos que son equivalentes bajo la “relaci´on”anterior. Una posible idea es definir la cardinalidad de un conjunto como su “clase de equivalencia” bajo la relaci´on de equinumerosidad, sin embargo, es claro que la clase de equivalencia de cualquier conjunto no vac´ıo es una clase propia, por lo tanto no existen dentro de nuestra teor´ıa,luego no podemos usarlas como “cardinales”. Para conjuntos finitos, es f´acil ver que en cada “clase de equivalencia” habr´a un u ´nico n´ umero natural, ´este se conoce habitualmente como la cardinalidad o n´ umero de elementos del conjunto, vale decir, aquel u ´nico natural con el que es equinumeroso. Podemos tratar de generalizar la idea anterior a conjuntos infinitos, sin embargo, hay dos dificultades, la primera es que dado un conjunto infinito cualquiera, no podemos garantizar que exista alg´ un ordinal que es equinumeroso con ´el. De hecho tal afirmaci´on es ni m´as ni menos, el principio del buen orden, es decir, equivalente con el axioma de elecci´on. En segundo lugar, es f´acil ver que si existe un ordinal equinumeroso con un conjunto infinito dado, ´este no ser´a nunca u ´nico, como lo demuestra por ejemplo la funci´on que aparece en la demostraci´on del teorema 5.3, la que nos dice que α y α + 1 son siempre equinumerosos. Por estos motivos, la manera de extender la noci´on de cardinalidad de los conjuntos finitos a los infinitos es suponer el Axioma de Elecci´on y escoger un representante de cada una de las “clases de equivalencia”, a saber, el menor ordinal que pertenece a ella. Necesitamos antes un par de resultados. Teorema 5.1. Si m 6= n, entonces m y n no son equinumerosos. ´ n. Como m y n son ordinales distintos m ∈ n o Demostracio n ∈ m, luego m y n no son equinumerosos por definici´on de cardinal. 118

Teorema 5.2. † Para todo conjunto A existe un u ´nico cardinal n tal que A y n son equinumerosos. ´ n. Por el principio de enumeraci´on existe un ordinal Demostracio α tal que A es equinumeroso con α . Sea \ m = {β ∈ Sα : A ∼ β},

o sea, m es el menor elemento del conjunto no vac´ıo {β ∈ Sα : A ∼ β}, es claro entonces que A ∼ m. Por u ´ltimo, si existiera β ∈ m tal que β ∼ m, tendr´ıamos que β ∼ A, luego m no es el menor elemento del conjunto anterior, contradicci´on. Por lo tanto m es un cardinal. Resulta claro que m no depende del ordinal α usado en la definici´on. ´ n 5.2. La cardinalidad |A| de un conjunto A es el u Definicio ´nico cardinal m tal que A ∼ m. Decimos tambi´en que m es el cardinal de A. Teorema 5.3. Si A , B son conjuntos y α es un ordinal, i) A ∼ B ssi |A| = |B|. ii) A ∼ |A|. iii) |α| ≤ α. iv) Si α ∼ A, entonces |A| ≤ α. v) α es un cardinal ssi |α| = α. vi) Si ω ≤ α, entonces |α + 1| = α. ´ n. Demostracio vi) Si ω ≤ α, entonces α = ω + γ. Definimos f : α + 1 −→ α como sique  si x = α,  0 x + 1 si x ∈ ω, f (x) =  x si x 6∈ ω, x 6= α . Es claro que f es una biyecci´on.

El pr´oximo teorema es probablemente el resultado m´as importante sobre cardinalidad que puede demostrarse sin usar el axioma de elecci´on. Teorema 5.4. Cantor - Schroeder - Bernstein Si A y B son dos conjuntos tales que existen funciones inyectivas f : A −→ B y g : B −→ A, entonces |A| = |B|. 119

´ n. Notemos primero que si Demostracio A1 = g ∗ f ∗ A entonces A1 ∼ A

ya que g ◦ f : A −→ A1 es claramente inyectiva y sobreyectiva. Por otra parte, si D = g ∗ B, entonces D ∼ B. Sea h = g ◦ f y definamos

An+1

A0 = A , D0 = D = h∗ An , Dn+1 = h∗ Dn .. .

En el diagrama los An son los cuadrados y los Dn son los c´ırculos. Ahora podemos demostrar por inducci´on que para todo n ∈ ω, An+1 ⊆ Dn ⊆ An . Definimos F : A −→ D  S h(x) , si x ∈ (An − Dn ) F (x) = x , si no S Observe que (An − Dn ) es la zona sombreada en el dibujo. F es S inyectiva ya que paraSx, y ∈ A, tenemos tres S posibilidades x, y S ∈ (An − Dn ), x, y 6∈ (An − Dn ) ´o x ∈ (An − Dn ) y y 6∈ (An −Dn ). En los dos primeros casos es claro que si F (x) = F (y), entonces x = y. Nos queda la tercera posibilidad pero en este caso F (x) = h(x) y x ∈ An − Dn para alg´ un n , luego h(x) ∈ An+1 . Si suponemos que h(x) ∈ Dn+1 , entonces h(x) = h(z) para alg´ un z ∈ Dn (ya que Dn+1 = h∗ Dn ) pero como h es inyectiva, z = x, es decir x ∈ DnSpero x ∈ An − Dn , contradicci´on luego h(x) 6∈ An+1 , o sea, h(x) ∈ (An − Dn ) y por lo tanto 120

F (x) = h(x) 6= y = F (y). Para ver que F es sobreyectiva recordemos primero que para todo n 6= 0, An ⊆ D ⊆ A. Sea x ∈ D y n el menor natural tal que x 6∈ An , entonces x ∈ An−1 . Si x 6∈ Dn−1 , n − 1 6= 0 y entonces x ∈ An−1 − Dn−1 y por lo que vimos anteriormente, x ∈ h∗ (An−2 − Dn−2 ), S luego x = h(y) = F (y) para un y ∈ (An − Dn ). S alg´ Si x ∈ Dn−1 , x 6∈ (An − Dn ) pues x 6∈ An para m ≥ n y x ∈ Dm para m < n. Por lo tanto, x = F (x). En cualquier caso x ∈ F ∗ A luego F es sobreyectiva. Hemos demostrado que A ∼ D ∼ B, luego |A| = |B|. Teorema 5.5. Si A ⊆ B, entonces |A| ≤ |B|. ´ n. Supongamos por el contrario que |B| < |A| y Demostracio sean f, g biyecciones f

A

−→ |A|

j↓

↑i

B

−→ |B|

g

donde i y j son la funci´on identidad. Entonces j : A −→ B es inyectiva, f −1 ◦ i ◦ g : B −→ A es inyectiva, luego por el teorema 5.4, |A| = |B|, contradicci´on luego |A| ≤ |B|. Teorema 5.6. † Las siguientes tres condiciones son equivalentes. i) |A| ≤ |B|. ii) Hay una funci´on inyectiva f : A −→ B. iii) A = ∅ o hay una funci´on sobreyectiva g : B −→ A. ´ n. i) ⇒ ii) Demostracio Sean f : A −→ |A|, g : |B| −→ B biyecciones, entonces g ◦ f : A −→ B es inyectiva. ii) ⇒ iii) Sea A 6= ∅, a ∈ A y f : A −→ B inyectiva. Definimos g : B −→ A como sigue.  −1 f (x) , si x ∈ f ∗ A , g(x) = a , si no , entonces g es sobreyectiva.

121

iii) ⇒ i)† Supongamos A 6= 0 y sea g : B −→ A sobreyectiva. Entonces g −1∗ A induce una partici´on de B , a saber, {g −1∗ {a} : a ∈ A}. Por el axioma de elecci´on, escogemos un sistema de representantes para esta partici´on. Definimos f : A −→ B asignando a x ∈ A el representante de g −1∗ {x} anteriormente elegido. Es claro que f es inyectiva, luego, |A| ∼ |f ∗ A| y f ∗ A ⊆ B, luego por 5.5, |A| = |f ∗ A| ≤ |B|. Observemos que el axioma de elecci´on se usa solamente en la demostraci´on de iii) ⇒ i). Todas las otras implicaciones se pueden demostrar sin ese axioma. Todav´ıa no hemos dado ning´ un ejemplo de cardinal. Los siguientes dos teoremas remedian esta situaci´on. Teorema 5.7. Si n ∈ ω, entonces n es un cardinal. ´ n. Por inducci´on. Demostracio Es claro que 0 es un cardinal. Supongamos que n es un cardinal y n + 1 no lo es. Entonces existe m < n + 1 tal que m ∼ n + 1, es claro que m 6= 0. Sea f : n + 1 −→ m una biyecci´on. Podemos suponer que f (n) = m − 1, porque si no, mediante una permutaci´on apropiada lo podemos lograr. Entonces f  n : n −→ m − 1 es una biyecci´on, luego, por hip´otesis de inducci´on, m − 1 = n, o sea, m = n + 1, una contradicci´on. Por lo tanto n + 1 es cardinal, lo que completa nuestra inducci´on. Teorema 5.8. ω es cardinal. ´ n. Sabemos por 5.3, iii), que |ω| ≤ ω. Si |ω| < Demostracio ω, |ω| = m para alg´ un n´ umero natural m. Pero m ⊆ m + 1 ⊆ ω, luego |ω| = m = |m| ≤ |m + 1| = m + 1 ≤ |ω|

luego m = m + 1, contradicci´on. Luego |ω| = ω. Teorema 5.9. Cantor Para todo A, |A| < |PA|.

´ n. Es claro que |A| ≤ |PA| ya que la asignaci´on Demostracio a 7−→ {a} define una funci´on inyectiva de A en PA. Supongamos que existe una funci´on sobreyectiva f : A −→ PA y sea 122

B = {x ∈ A : x 6∈ f (x)}. Como B ⊆ A y f es sobreyectiva, existe a ∈ A tal que B = f (a). Entonces si a ∈ B, por definici´on a 6∈ f (a), luego a 6∈ B. Si a 6∈ B, entonces a 6∈ f (a), o sea, a ∈ B, es decir, a ∈ B si y s´olo si a 6∈ B, contradicci´on, luego tal funci´on sobreyectiva no puede existir y |A| = 6 |PA|. Corolario 5.10. Dado un ordinal α , existe un cardinal m > α. ´ n. Basta considerar Demostracio

m = |Pα|.

Corolario 5.11. No existe el conjunto de todos los cardinales. ´ n. Si existiera el conjunto C de todos los cardinales, Demostracio por el teorema reci´en demostrado, el conjunto [ {α ∈ n : α < n} n∈C

contendr´ıa a todos los ordinales y por lo tanto ´estos constituir´ıan tambi´en un conjunto. S Teorema 5.12. Si Γ es un conjunto de cardinales, entonces Γ es un cardinal. S ´ Demostraci o n. Supongamos S S S Γ no es un cardinal, entonces, | Γ| < Γ (recordemos que Γ es un ordinal). Luego, existe n∈Γ [ | Γ| ∈ n ∈ Γ , S pero n ⊆ Γ y [ [ | Γ| < n = |n| ≤ | Γ| . ´ n 5.3. Para todo ordinal α, α+ es el menor cardinal Definicio mayor que α . Definimos la operaci´on ℵ (aleph) recursivamente para todo ordinal. 123

ℵ0 = ω ℵα+1 = (ℵα )+ [ ℵλ = ℵα , si λ es l´ımite. α<λ

Ejercicios. 1. Demuestre que la relaci´on “ser equinumeroso” es refleja sim´etrica y transitiva. 2. Probar que: (a) PPP0 ∼ 4. (b) Si A ∼ B, entonces C A ∼ C B. (c) Si B ∩ C = ∅, entonces B∪C A ∼ B A × C A. (d) C (B A) ∼ B×C A. (e) C (A × B) ∼ C A × C B. (f) Si R1 es el conjunto de todos los ´ordenes estrictos sobre X y R2 es el conjunto de todos los ´ordenes sobre X, entonces R1 ∼ R2 . (g) Probar que si E es el conjunto de todas las clases de equivalencia sobre A y P es el conjunto de todas las particiones de A , entonces E ∼ P . 3. Sea A un conjunto. Probar que PA ∼ A 2. 4. Sea {Ij : j ∈ J} una partici´on de I. Probar que Y Y Y Ai ∼ ( Ai ). i∈I

j∈J i∈Ij

5. Si A1 ∼ A2 y B1 ∼ B2 y A1 ∩ B1 = A2 ∩ B2 = ∅, probar que A1 ∪ B1 ∼ A2 ∪ B2 . 6. Probar que si A ∼ C y B ∼ D, entonces A × B ∼ C × D. 7. Probar que si A ∼ B, entonces PA ∼ PB. 8. Probar que si (A − B) ∼ (B − A), entonces A ∼ B. 9. Probar que si A ∼ B y a ∈ A y b ∈ B, entonces (A − {a}) ∼ (B − {b}). 10. Probar que si A ∼ B y C ∼ D y C ⊆ A y D ⊆ B, entonces (A − C) ∼ (B − D). 11. Sean (Ai )i∈I y (Bi )i∈I dos familias, cada una de conjuntos disjuntos dos S S a dos. Si Ai ∼ Bi para todo i ∈ I, probar que A ∼ i i∈I i∈I Bi . 12. Sean (Ai )i∈I y (Bi )i∈I dos familias tales que Ai ∼ Q de conjuntos Q Bi para todo i ∈ I. Probar que i∈I Ai ∼ i∈I Bi . 124

13. Demuestre las partes del teorema 5.3 que no fueron demostradas en el texto. 14. Haga la inducci´on mencionada en la demostraci´on del teorema 5.4. 15. Demuestre directamente, sin usar el axioma de elecci´on, la equivalencia de las dos primeras afirmaciones del teorema 5.6. 16. Demuestre directamente, sin usar el axioma de elecci´on, la implicaci´on i) ⇒ iii) del teorema 5.6. 17. Probar que para intervalos de n´ umeros reales se tiene (a, b) ∼ [a, b]. 18. Probar que ω y | ω 2| son cardinales distintos. 19. Probar que |Q| = |Q[x]| = ω, donde Q[x] es el conjunto de polinomios en x con coeficientes en Q. 20. Sea R el conjunto de todas las ra´ıces reales de polinomios de Q[x]. Probar que |R| = ω. 21. Si B ⊆ A y ω ⊆ |B| < |A|, cual es la cardinalidad de A − B ?. 22. Probar que α es un cardinal tal que ω < α si y s´olo si α es ordinal l´ımite. 23. Para α y β ordinales, probar o dar contraejemplo de: (a) Si α y β son cardinales, entonces α + β es cardinal. (b) Si α y β son cardinales, entonces α · β es cardinal. (c) |α + β| = |α| + |β|. (d) |α · β| = |α| · |β|. (e) Si α < β, entonces |α| < |β|. 24. Sean A , B y C conjuntos. Probar que: (a) Si B 6= ∅, entonces |A| ≤ | B A|. (b) SI B ⊆ C, entonces | B A| ≤ | C A|. (c) Si |B| ≥ 2, entonces |A| ≤ | A B|. 25. Probar que para todo α , ℵα es un cardinal. 26. Probar que: (a) ℵα = ℵβ si y s´olo si α = β. (b) ℵα < ℵβ si y s´olo si α < β. 27. Probar que para todo cardinal α existe un ordinal β tal que α < ℵβ . 2. Conjuntos Finitos y Conjuntos Infinitos En esta secci´on daremos un marco formal a la nociones intuitivas de finitud e infinitud yveremos algunas diferencias entre estos dos tipos de conjuntos. ´ n 5.4. Definicio i) Un conjunto A es finito si |A| < ℵ0 . ii) A es infinito si |A| ≥ ℵ0 . 125

iii) A es enumerable si |A| = ℵ0 . Una consecuencia inmediata de esta definici´on es que los n´ umeros naturales son finitos, es m´as, la cardinalidad de un conjunto finito es siempre un n´ umero natural. As´ı por ejemplo |{x}| = 1 , |{x, y}| = 2 , si x 6= y, etc. Teorema 5.13. Si A ⊆ B o existe una funci´on sobreyectiva f : B −→ A, entonces: i) Si A es infinito, B es infinito, ii) † Si B es finito, A es finito. ´ n. Si A ⊆ B, use el teorema 5.5. Demostracio Si existe una funci´on sobreyectiva f : B −→ A, entonces como existe una biyecci´on g : |A| −→ A, tenemos que g ◦ f : |A| −→ B es una funci´on sobreyectiva, luego por el teorema 5.6, |A| ≤ |B|. (Aqu´ı es donde hemos usado el axioma de elecci´on.) La conclusi´on del teorema se sigue de esta afirmaci´on. Teorema 5.14. Si A es finito y B ⊂ A, entonces |B| < |A|. ´ n. Sea b ∈ A − B y f : A −→ m una biyecci´on. Demostracio Podemos suponer que f (b) = m − 1 pues si f (b) 6= m − 1 podemos permutar dos valores de f y la funci´on resultante sigue siendo biyectiva. Entonces f  B : B −→ m − 1 es inyectiva y por el teorema 5.6, |B| ≤ m − 1 < m = |A|. Recu´erdese que esta parte del teorema 5.6 no requiere del axioma de elecci´on. El teorema anterior caracteriza a los conjuntos finitos, de hecho, se puede definir conjunto infinito como un conjunto que es equinumeroso con uno de sus subconjuntos propios. Un conjunto que satisface esta propiedad se dice Dedekind–infinito. Se necesita el axioma de elecci´on para demostrar que ser infinito y ser Dedekind–infinito es equivalente. Teorema 5.15. † Un conjunto A es infinito si y s´olo si A es equinumeroso con uno de sus subconjuntos propios. 126

´ n. ⇐) Por el teorema anterior. Demostracio † ⇒) Como A es infinito, |A| ≥ ℵ0 = ω, luego existe una funci´on inyectiva f : ω −→ A. Definamos h : A −→ A − {f (0)} como sigue  f (f −1 (x) + 1) si x ∈ f ∗ ω, h(x) = x si x 6∈ f ∗ ω. es claro que h es biyectiva. Teorema 5.16. Si A y B son finitos, |A| = |B| y f : A −→ B, entonces f es inyectiva si y s´olo si f es sobreyectiva. ´ n. ⇒) Supongamos f es inyectiva. Si f no es Demostracio sobreyectiva, entonces como f ∗ A ⊆ B, por 5.14 |A| = |f ∗ A| < |B|,

contradicci´on. ⇐) Supongamos que f es sobreyectiva. Entonces f induce la siguiente partici´on sobre A : {f −1∗ {b} : b ∈ B}

Podemos seleccionar un representante de cada elemento de la partici´on y definir g : B −→ A b 7−→ el representante de f −1∗ {b} seleccionado. Obs´ervese que como B es finito, la partici´on indicada es finita y por lo tanto para seleccionar un representante de cada elemento de la partici´on no es necesario el axioma de elecci´on. Es claro que f (g(b)) = b y que g es inyectiva. Aplicando la primera parte de esta demostraci´on a g, ´esta es sobreyectiva, es decir, g es biyectiva. Por u ´ltimo f = g −1 , luego f es inyectiva.

Ejercicios. 1. Demuestre que un conjunto A es Dedekind–infinito si existe una funci´on inyectiva de A en A , que no es sobreyectiva. 2. Sea F una funci´on de A sobre B , con A enumerable. Probar que |B| ≤ ℵ0 . 127

3. Probar que, si A y B son finitos, entonces A ∪ B, A × B y A B son finitos. Si A o B son enumerables ¿es alguno de los conjuntos mencionados infinito no numerable?. 4. Probar que A es infinito si y s´olo si existe un subconjunto enumerable de A . 5. Probar que si A es infinito y B no es vac´ıo, entonces A × B es infinito. 6. Probar que si A es infinito y B ⊆ A es finito, entonces A − B es infinito. 7. Probar que A es infinito si y s´olo si para todo n ∈ ω existe B ⊆ A con B ∼ n. 8. Sean A infinito y B enumerable. Probar que A ∼ (A ∪ B). 9. Probar que si A es enumerable y x ∈ A, entonces A − {x} es enumerable. Probar que A es infinito si y s´olo si A ∼ (A − {x}). 10. Probar que si PA es infinito, entonces A es infinito. 11. Probar que todo subconjunto de un conjunto enumerable es finito o enumerable. 12. Probar que si A y B son enumerables, entonces A × B es enumerable. Probar lo mismo si B es finito no vac´ıo. 13. Sea S (Ai )i∈ω una familia de conjuntos enumerables. Probar que i∈ω Ai es enumerable. 14. Probar que si A es enumerable, entonces existe B ⊆ A enumerable tal que A − B es enumerable. 15. Probar que si n ∈ ω, entonces ω n es enumerable (exponenciaci´on ordinal). S 16. Probar que si I = ω, entonces i∈I ω i es enumerable. 17. Probar que el conjunto de todos los subconjuntos finitos de un conjunto enumerable es enumerable. 18. Probar que si A es infinito, entonces A es enumerable si y s´olo si A ∼ B para todo B ⊆ A infinito. 19. Probar que si A es el conjunto de los subconjuntos infinitos de ω, entonces |A| = | ω 2|. 20. Sea a = (an )n∈ω una familia de naturales. Entonces: (a) Diremos que a es eventualmente constante si existen n0 ∈ ω y s ∈ ω tales que an = s para todo n ≥ n0 . Probar que el conjunto de las familias eventualmente constantes de n´ umeros naturales es enumerable. (b) Diremos que a es eventualmente peri´ odica si existen n0 ∈ ω y p ∈ ω − 1 tales que an+p = an para todo n ≥ n0 . Probar que el conjunto de las familias eventualmente peri´odicas de n´ umeros naturales es enumerable. 128

21.

22.

23.

24.

25.

26.

(c) Diremos que a es progresi´ on aritm´etica si existe d ∈ ω tal que an+1 = an + d, para todo n ∈ ω. Probar que el conjunto de las progresiones aritm´eticas de n´ umeros naturales es enumerable. Probar que una partici´on de un conjunto enumerable tiene un conjunto de representantes, sin usar el Axioma de Elecci´on o alguno de sus equivalentes. Sea ϕ una f´ormula con variable libre x . Probar que si A es finito y se verifica ϕ(∅) y para todo x ∈ A y todo B ⊆ A si se verifica ϕ(B), tambi´en se verifica ϕ(B ∪ {x}), entonces se verifica ϕ(A). Probar que A es finito si y s´olo si A pertenece a todo conjunto K tal que ∅ ∈ K y para todo x ∈ A y todo B ⊆ A tal que B ∈ K, se tenga B ∪ {x} ∈ K. Probar que A es finito si y s´olo si A pertenece a todo conjunto K tal que ∅ ∈ K, y x ∈ A implica {x} ∈ K y, si B ∈ K y C ∈ K, entonces B ∪ C ∈ K. Probar que A es finito si y s´olo si PA es el u ´nico conjunto K tal que K ⊆ PA, ∅ ∈ K, x ∈ A implica {x} ∈ K, y si B ∈ K y C ∈ K, entonces B ∪ C ∈ K. Probar que, si A es enumerable, entonces existe una familia B de conjuntos tal que: (a) B es enumerable, (b) si C ∈ B, entonces C es enumerable, (c) Si S C y D est´an en B , y C 6= D, entonces C ∩ D = ∅ , y (d) B = A. Probar el rec´ıproco usando el Axioma de Elecci´on. 3. Aritm´ etica Cardinal

En esta secci´on definiremos suma, producto y exponenciaci´on de cardinales y algunas de sus propiedades. Tambi´en veremos que estas operaciones tienen una interpretaci´on intuitiva. 3.1. Suma de Cardinales. ´ n 5.5. Sea hmi : i ∈ Ii una familia de cardinales. La Definicio X suma cardinal de los mi denotada por mi es el cardinal del conjunto i∈I

[ i∈I

{hi, αi : α ∈ mi } 129

Si I = 2, escribimos

X

mi = m0 +c m1

i∈2

M´as generalmente si i = n, escribimos X mi = m0 +c · · · +c mn−1 . i∈n

La idea de la definici´on es que la suma de cardinales representa la cardinalidad de la uni´on de conjuntos disjuntos que tienen las cardinalidades indicadas, as´ı por ejemplo, [ m0 +c m1 = |{(0, α) : α ∈ m0 } {(1, α) : α ∈ m1 }| como

|{(0, α) : α ∈ m0 }| = m0 y |{(1, α) : α ∈ m1 }| = m1 , la finalidad de tomar estos conjuntos de pares ordenados es simplemente disjuntar los conjuntos (obviamente m0 y m1 no son disjuntos). El siguiente teorema nos dice que no importa qu´e conjuntos usemos para calcular la suma siempre que estos sean disjuntos y tengan las cardinalidades adecuadas. Teorema 5.17. † Si hAi : i ∈ Ii y hBi : i ∈ Ii son familias de conjuntos disjuntos dos a dos tales que para todo i ∈ I Ai ∼ Bi , entonces [ [ X Ai ∼ Bi ∼ |Ai | i∈I

i∈I

i∈I

´ n. Para i ∈ I, sea fi : Ai −→ Bi una biyecci´on. Demostracio Definimos f:

[ i∈I

Ai −→

[

Bi

a 7−→ fi (a) ,

si a ∈ Ai .

f est´a bien definida ya que los Ai son disjuntos a pares, luego a no puede pertenecer a dos de ellos al mismo tiempo. Es claro tambi´en que S f es biyectiva. Obs´ervese que f = i∈I fi . Teorema 5.18. |

[ i∈I

Ai | ≤

X

130

i∈I

|Ai |.

En particular

[ i∈I

mi ≤

X

mi .

i∈I

´ n. Si |Ai | = mi para cada i ∈ I, sea fi : mi −→ A Demostracio biyectiva y definamos: g:

[ [ {hi, αi : α ∈ mi } −→ Ai i∈I

hi, αi 7−→ fi (a).

P Es f´acil ver que g es sobreyectiva luego por 5.6, | i∈I |Ai |.

S

i∈I

Ai | ≤

Algunas propiedades elementales de la suma de cardinales est´an resumidas en el pr´oximo teorema. X Teorema 5.19. i) 0 = 0. i∈I X ii) mi = 0. i∈0 X X iii) Si I ⊆ J, entonces mi ≤ mi . i∈I i∈J X X iv) Si mi ≤ ni , para i ∈ I, entonces mi ≤ ni . i∈I i∈I X 1 = m. v) β<m

´ n. i) y ii) son obvias a partir de la definici´on. Demostracio iii) Basta notar que [ [ {hi, αi : α ∈ mi } ⊆ {hi, αi : α ∈ mi }, i∈I

i∈J

luego aplicar 5.5. iv) Idem iii) ya que [ [ {hi, αi : α ∈ mi } ⊆ {hi, αi : α ∈ ni } i∈I

i∈I

v) Obs´ervese que

f : m −→

[

β∈m

{hβ, αi : α ∈ 1}

β 7−→ hβ, 0i 131

es una biyecci´on.

Teorema 5.20. (Conmutatividad Generalizada) Si hmi : i ∈ Ii es una familia de cardinales y σ es una permutaci´ on de I (i.e. σ : I −→ I es una biyecci´ on), entonces X X mi = mσ(i) i∈I

i∈I

´ n. Consid´erese Demostracio f:

[ [ {hi, αi : α ∈ mi } −→ {hi, αi : α ∈ mσ(i) } i∈I

i∈I −1

hi, αi 7−→ hσ (i), αi.

Es claro que f es biyectiva, por ejemplo, para verificar que f es S sobreyectiva, sea hk, βi ∈ i∈I {hi, αi : α ∈ mσ(i) } es decir k ∈ I y β ∈ mσ(k) . Sea j = σ(k), entonces

con hj, βi ∈

S

f (hj, βi) = hσ −1 (j), βi = hk, βi,

i∈I {hi, αi

: α ∈ mi }, luego f es sobreyectiva.

Teorema 5.21. (Asociatividad generalizada) Sea {hmij : hi, ji ∈ I × Ji} una familia de cardinales. Entonces XX X mij = ( mij ). hi,ji∈I×J

i∈I

j∈J

´ n. Para cada hi, ji ∈ I × J definimos Demostracio Aij = {hhi, ji, αi : α ∈ mij }. Entonces los Aij sondisjuntos a pares y |Aij | = mij , para todo hi, ji ∈ I × J. Por el teorema 5.17, X [ mij = | Aij |. hi,ji∈I×J

Adem´as, para cada i ∈ I, |

[

j∈J

hi,ji∈I×J

Aij | = 132

X j∈J

mij .

S Pero h j∈J Aij : i ∈ Ii es tambi´en una familia de conjuntos disjuntos a pares luego X [ [ [ | Aij | = | ( Aij )|. i∈I

j∈J

i∈I j∈J

Para terminar basta con notar que [[ [ Aij , Aij = i∈I j∈J

hi,ji∈I×J

por asociatividad de la uni´on. Juntando los cuatro resultados anteriores, X X X mij = ( mij . hi,ji∈I×J

i∈I

j∈J

Para completar estos resultados sobre la suma cardinal veremos algunos teoremas sobre cardinales finitos. Teorema 5.22. Para todo par de n´ umeros naturales m, n, m +c n = m + n ´ n. Por inducci´on sobre n . Demostracio Si n = 0, es f´acil comprobar que m +c 0 = m y lo dejamos como ejercicio. Luego m +c 0 = m = m + 0 Antes de demostrar el paso inductivo demostraremos que m +c 1 = m + 1. En efecto, f : {h0, `i : ` ∈ m} ∪ {h1, 0i} −→ m + 1 h0, `i 7−→ ` h1, 0i 7−→ m es una biyecci´on, luego m +c 1 = m + 1. Supongamos ahora que m +c n = m + n entonces m +c Sn = m +c (n + 1) = m +c (n +c 1) , por lema, = (m +c n) +c 1 , por 5.21, = (m + n) + 1 , por hip´otesis y lema, = m + (n + 1) = m + Sn Esto completa la inducci´on. 133

Corolario 5.23. Si A y B son finitos, entonces A lo es.

S

B tambi´en

´ n. Por 5.17, |A∪B| ≤ |A|+c |B| = |A|+|B| < ω. Demostracio 3.2. Producto de Cardinales. ´ n 5.6. Sea hmi : i ∈ Ii una familia de cardinales. Definicio El producto cardinal de los mi es Y Xi∈I mi = | mi | i∈I

Si I = 2, Xi∈I mi se escribe m0 ×c m1 . En general si I = n, Xi∈I mi = m0 ×c m1 ×c · · · ×c mn−1 .

Como en el caso de la suma, el producto de cardinales no depende de los conjuntos que empleemos para calcularlo, s´olo de las cardinalidades de esos conjuntos. Teorema 5.24.

†

Si |Ai | = |Bi | para todo i ∈ I, entonces Y Y | Ai | = | Bi |. i∈I

i∈I

´ n. Sea fi : Ai −→ Bi una biyecci´on. Consideremos Demostracio Y Y f: Ai −→ Bi i∈I

i∈I

definida por

Q

f (a)(i) = fi (a(i)),

Para todo a ∈ i∈I Ai . Veamos que f es inyectiva. Si f (a) = f (b), entonces para todo i ∈ I decir

f (a)(i) = f (b)(i), es

fi (a(i)) = fi (b(i)), pero como para todo i ∈ I, las funciones fi son inyectivas, a(i) = b(i), es decir, a = b. Q Para verificar que f es sobreyectiva. Sea b ∈ i∈I Bi y sea a(i) = fi−1 (b(i)). Tal a(i) existe por ser fi biyectiva. Es claro que f (a) = b. Q Q Por lo tanto f es biyecci´on y i∈I Ai ∼ i∈I Bi . Q Corolario 5.25. | i∈I Ai | = Xi∈I |Ai | y en particular |A × B| = |A| ×c |B|. 134

El pr´oximo teorema resume algunas propiedades elementales de el producto cardinal. Teorema 5.26. i) Si Xi∈I mi = 0. ii) Xi∈∅ mi = 1. iii) X i∈I 1 = 1. X iv) m = |I| × m.

mi = 0 para alg´ un i ∈ I, entonces

i∈I

v) Si mi ≤ ni , para todo i ∈ I, entonces Xi∈I mi ≤ Xi∈I ni . Q ´ Demostraci o n. i) En este caso i∈I mi = ∅. Q ii) Qi∈∅ mi = {0} iii) i∈I 1 = {f }, donde f (i) = 0, para todo i ∈ I. iv) N´otese que [ I × m = {hi, αi : α ∈ m}, i∈I

luego por definici´on, X [ m = | {hi, αi : α ∈ m}| i∈I

v) En este caso

i∈I

= |I ×c m| = |I| ×c m. Y i∈I

mi ⊆

Y

ni .

i∈I

Teorema 5.27. (Conmutatividad Generalizada) Si σ es una permutaci´ on de I , entonces Xi∈I mi = Xi∈I mσ(i) . ´ n. Consid´erese la biyecci´on Demostracio Y Y f : mi −→ mσ(i) , i∈I

i∈I

definida por

f (a)(i) = a(σ(i)). Teorema 5.28. (Asociatividad Generalizada) Xhi,ji∈I×J mij = Xi∈I (Xj∈J mij ). 135

´ n. Por el teorema 5.24 Demostracio YY Xi∈I (Xj∈J mij ) = | ( mij )| i∈I j∈J

Xhi,ji∈I×J mij = | Definimos F :

Q

hi,ji∈I×J mij −→

Y

hi,ji∈I×J

mij |

Q ( j∈J mij ) i∈J

Q

F (f )(i)(j) = f (hi, ji).

Es claro que F es biyecci´on. Teorema 5.29. (Distributividad) Si para todo i ∈ I ni es un cardinal, X X n ×c ni = m ×c ni . i∈I

i∈I

´ n. Notemos primero que Demostracio X [ m ×c ni = | {hi, α, βi : α ∈ m, β ∈ ni }|, i∈I

i∈I

ya que para todo i ∈ I,

n ×c ni ∼ {hi, α, βi : α ∈ m, β ∈ ni }. Por otra parte n ×c Por u ´ltimo F : m ×c

[ i∈I

X i∈I

ni = |m ×c

[ {hi, βi : β ∈ ni }|. i∈I

{hi, βi : β ∈ ni } −→

[ {hi, α, βi : α ∈ m, β ∈ ni } i∈I

hα, hi, βii 7−→ hi, α, βi

es obviamente biyectiva. El siguiente teorema tiene por consecuencia el que las operaciones de suma y producto cardinal para el caso infinito son en alg´ un sentido triviales. Teorema 5.30. Sea m un cardinal infinito. Entonces m ×c m = m 136

´ n. Supongamos que esto es falso. Sea m el menor Demostracio cardinal tal que m ×c m 6= m. Definiremos un orden sobre el producto cartesiano m ×c m y demostraremos que ´este es un buen orden. Para α, β, γ, δ ∈ m definimos hα, βi 4 hγ, δi

si y s´olo si 1. α = γ y β = δ ´o 2. α ∪ β < γ ∪ δ ´o 3. α ∪ β = γ ∪ δ y α < γ ´o 4. α ∪ β = γ ∪ δ y α=γ y β ≤ δ. No demostraremos que 4 es un orden lineal sobre m ×c m pues su demostraci´on es rutinaria. Para ver que 4 es un buen orden, sea Γ ⊆ m ×c m no vac´ıo. Sea \ γ = {α ∪ β : hα, βi ∈ Γ}, es claro que γ existe pues es el menor elemento de un conjunto no vac´ıo de ordinales. Sea \ δ = {α : hα, βi ∈ Γ} para alg´ un β y α ∪ β = γ}. Finalmente sea

ε=

\ {β : hδ, βi ∈ Γ}

Es f´acil ver que hδ, εi es el menor elemento de Γ. Luego, 4 es un buen orden con campo m ×c m y por lo tanto es isomorfo a alg´ un ordinal α . Sea f : α −→ m ×c m el isomorfismo (i.e. si β < γ ∈ α, entonces f (β) 4 f (γ)). N´otese que en particular, α ∼ m ×c m. Supongamos que α ≤ m. Entonces m ×c m = |m ×c m| = |α| ≤ m = m ×c 1 ≤ m ×c mc donde para el u ´ltimo paso hemos usado 5.26, v) , o sea, m ×c m = m, una contradicci´on. Por lo tanto α > m, es decir m ∈ Dom f . Sean f (m) = hβ, γi ∈ m × m δ = (β ∪ γ) + 1. Como m es l´ımite, δ ∈ m y β ∪ γ < δ = δ ∪ δ por lo tanto (β, γ 4 (δ, δ). De hecho para todo ε < m 137

Por lo tanto

f (ε) 4 f (m) 4 hδ, δi y f (ε) 6= δ.

es inyectiva, luego,

f  m : m −→ δ × δ

m ≤ |δ × δ| = |δ| ×c |δ|. Como δ < m, o bien, δ es finito, o bien |δ| ×c |δ| = |δ|. En el primer caso m es finito. En el segundo m ≤ |δ| y δ < m lo que contradice el que m sea cardinal. Esto concluye la demostraci´on. Corolario 5.31. Si m ≥ ℵ0 ´ o n ≥ ℵ0 , entonces m +c n = m ∪ n. Si adem´as m 6= 0 y n 6= 0, m ×c n = m ∪ n. Si α, β son ordinales, entonces ℵα + ℵβ = ℵα∪β = ℵα ×c ℵβ . ´ n. Supongamos sin p´erdida de generalidad que m ≥ Demostracio ℵ0 y m ≥ n. Entonces

Luego

m +c n ≤ = ≤ = ≤

m +c m m ×c 2 por 5.26 iv), m ×c m m m +c n

m +c n = m = m ∪ n. Si adem´as suponemos n > 0,

Luego

m ×c n ≤ = = ≤

m ×c m m m ×c 1 m ×c n

m ×c n = m = m ∪ n. La observaci´on respecto de los ℵ ahora es obvia. Corolario 5.32. Sea mS un cardinal infinito, |Ai | ≤ m para todo i ∈ I y |I| ≤ m. Entonces | i∈I Ai | ≤ m. 138

´ n. Demostracio |

[ i∈I

Ai | ≤ ≤

X i∈I

X

|Ai | m

i∈I

= |I| ×c m ≤ m ×c m = m.

Corolario 5.33. La uni´on enumerable de conjuntos enumerables es enumerable. Teorema 5.34. † (Desigualdad de Zermelo) Si para todo i ∈ I mi < ni , X mi < Xi∈I ni . i∈I

´ n. Como ni − mi 6= ∅, existe f ∈ Demostracio Definimos ahora [ Y F : {hi, αi : α ∈ mi } −→ ni i∈i



Q

i∈I (ni

− mi ).

i∈I

f (j) si i 6= j, α si i = j. F es inyectiva. En efecto, supongamos que F (hi, αi)(j) =

F (hi, αi) = F (hj, βi), es decir, para todo k ∈ I,

F (hi, αi)(k) = F (hj, βi)(k).

Entonces, si i 6= j,

f (j) = F (hi, αi)(j) = F (hj, βi)(j) = β

pero f (j) 6∈ mj y β ∈ mj , contradicci´on. Luego, i = j. Pero entonces α = β y F es inyectiva. Por lo tanto, X mi ≤ Xi∈I ni . i∈I

Supongamos que son iguales. Entonces existe una biyecci´on [ Y h : {hi, αi : α ∈ mi } −→ ni . i∈I

i∈I

139

Para cada i ∈ I definimos hi : {hi, αi : α ∈ mi } −→ ni hi, αi 7−→ h(hi, αi)(i) . Es claro que hi es inyectiva porque h lo es. Entonces |h∗i {hi, αi : α ∈ mi }| ≤ |{hi, αi : α ∈ mi }| = mi < ni Podemos usar nuevamente el principio multiplicativo y encontrar Y `∈ (ni − ki∗ {hi, αi : α ∈ mi }). Como ` ∈

Q

i∈I

i∈I

ni y h es sobreyectiva, existe i ∈ I, α ∈ mi tal que

` = h(hi, αi, pero entonces `(i) = h(hi, αi)(i) = hi (hi, αi) ∈ ki∗ {hi, αi : α ∈ mi },

contradiciendo la definici´on de `.

Por u ´ltimo verificamos que el producto de cardinales finitos se comporta como lo deseamos. Teorema 5.35. Si m, n son naturales m ×c n = m · n ´ n. Por inducci´on Demostracio - m ×c 0 = 0 = m · 0 - Supongamos m ×c n = m · n. Entonces m ×c Sn = |m × (n ∪ {n})| = |m × n ∪ m × {n}| y como la uni´on es disjunta y m × {n} ∼ m, m ×c Sn = m ×c n +c m = m·n+m = m · Sn . Corolario 5.36. El producto finito de cardinales finitos es finito.

140

3.3. Exponenciaci´ on de Cardinales. Para terminar con esta secci´on definiremos la operaci´on de exponenciaci´on de cardinales. Debemos tener presente que al igual que en el caso de las sumas y los productos, la exponenciaci´on cardinal difiere radicalmente de la exponenciaci´on ordinal. Sin embargo, diferencia de las otras dos operaciones, no existe una buena manera de distinguir notacionalmente ambas exponenciaciones. Para no recargar a´ un m´as una notaci´on de suyo algo engorrosa, hemos optado por usar la misma notaci´on para las dos dejando al contexto como indicador de cu´al de las dos exponenciaciones se est´a usando. En general, como las letras g´oticas designan cardinales, no hay demasiada poibilidad de confusi´on. ´ n 5.7. Si m y n son cardinales, Definicio mn = |n m| Es decir la exponenciaci´on de m por n es la cardinalidad del conjunto de todas las funciones de m en n . Por simplicidad notacional, cuando el exponente sea un ℵ no lo subrayaremos. Teorema 5.37. Dados dos conjuntos A y B , |A B| = |B||A| ´ n. Basta probar que A B ∼|A| |B|. Consideremos las Demostracio biyecciones f y g como en el diagrama. A

x

−→

f↓

B ↑g

F (x)

|A| −→ |B| Definimos F :

A

B −→ |A| |B| x 7−→ g ◦ x ◦ f

F es una biyecci´on porque f y g lo son. Teorema 5.38. i) m0 = 1. ii) Si m 6= 0, entonces 0m = 0. iii) 1m = 1. iv) m1 = m. v) Xi∈I m = m|I| . 141

´ n. i)Q- iv) Son obvias. Demostracio v) Basta notar que i∈I m = I m. P

Teorema 5.39. i) m ii) (Xi∈I mi )n = Xi∈I mni .

ni

= Xi∈I mni .

i) Sea

´ n. Demostracio F :

i∈I

S

i∈I {hi,αi:α∈mi }

m −→

Y (ni m) i∈I

f 7−→ F ◦ f

donde F (f )(i) es la funci´on de ni en m definida por F (f )(i)(α) = f (hi, αi). ii) Sea n

F :

Y i∈I

mi −→

Y (n mi ) i∈I

donde F (f )(i) es la funci´on de n en mi definida por F (f )(i)(α) = f (α)(i) Tanto en i) como en ii) F es biyectiva. Teorema 5.40. (mn )p = mn×c p . ´ n. La funci´on Demostracio F : p (n m) −→

n×c p

m

definida por F (f )(hα, βi) = f (β)(α) es la biyecci´on requerida. El siguiente teorema es bastante u ´til. Teorema 5.41. Para cualquier conjunto A , |P(A)| = 2|A| 142

´ n. Asociamos a cada conjunto de A su funci´on carDemostracio acter´ıstica:

donde

χ : P(A) −→ A 2 B 7−→ χB , χB (x) =



Es claro que χ es biyectiva.

1 si x ∈ B, 0 si x 6∈ B .

Teorema 5.42. Sean 1 < m ≤ n dos cardinales y n > ℵ0 , entonces mn = 2n . ´ n. Demostracio mn ≤ = = ≤

(2m )n 2m×c n 2n mn ,

en donde hemos usado el hecho de que la exponenciaci´on es creciente (ver ejercicios) y dos teoremas anteriores. Luego mn = 2n . Ejercicios. 1. 2. 3. 4. 5.

¿D´onde usamos el axioma de elecci´on en el teorema 5.17? Probar que si m ≤ n, entonces m +c p ≤ n +c p. Probar que si m +c 1 = m, entonces m es infinito. Probar que si m es infinito, entonces ℵ0 +c m = m. Sea hmi : i ∈ Ii una familia de cardinales que no contiene a su mayor elemento. Probar que para todo j ∈ I se tiene P mj < i∈I mi . 6. Asumiendo que cada suma es de ℵ0 t´erminos, probar que: (a) 1 +c 2 +c 3 +c · · · = ℵ0 . (b) n +c n +c n +c · · · = ℵ0 . (c) ℵ0 +c ℵ0 +c ℵ0 +c . . . = ℵ0 . 7. Probar que m ≤ n si y s´olo si existe p tal que m +c p = n. 8. Probar Pque: (a) β≤α ℵβ = ℵα . P (b) Si α es ordinal l´ımite, entonces . β∈α ℵβ = ℵ Sα (c) Si (αi )i∈I es una familia de ordinales, con i∈I αi ⊆ α, P S entonces ℵα = i∈I ℵαi si y s´olo si α = i∈I αi . 143

9. Probar que si m ≤ n, entonces m ×c p ≤ n ×c p. 10. (a) Probar que si m ≤ n, entonces mp ≤ np . (b) Sea p 6= 0. Probar que si m < n, entonces pm ≤ pn . Probar tambi´en que si pm < pn , entonces m < n. (c) M´as generalmente, demuestre que si m ≤ n con m 6= 0 y p ≤ q, entonces mp ≤ nq . 11. Probar que si n ∈ ω y c = 2ℵ0 , entonces: (a) (n+c 2)ℵ0 = ℵℵ0 0 = n+c c = n×c c = cn = ℵ0 +c c = ℵ0 ×c c = cℵ0 = c +c c = c ×c c = c2 = c. (b) (n +c 2)c = ℵc0 = cc = 2c . (c) ℵ0 6= c 6= 2c . Q 12. Probar que si I = ω − 1, entonces i∈I i = c. 13. Probar que {m : mℵ0 = m} es infinito. 14. Probar que si m +c n = p, entonces (r +c s)p ≥ rm ×c sn . 15. Si m ≥ ℵ0 y m ≤ n ×c p, probar que m ≤ n o m ≤ p. 16. Un cardinal infinito m se dice dominante si n < m y p < m implica np < m. Probar que m es dominante si y s´olo si p < m implica 2p < m. 17. Probar que si m P Qi ≤ n paran todo i ∈ I, con |I| ≤ n, entonces i∈I mi ≤ n y i∈I mi ≤ 2 . 18. Probar que ℵ0 ≤ 2ℵ0 . 19. Probar que m2 = n2 implica m = Qn. 20. Probar que si mi = c, entonces i∈ω mi = c. Q |α| ımite, entonces 21. Probar que β≤α ℵβ = ℵα , y si α es ordinal l´ Q |α| β∈α ℵβ = ℵα . 22. Si α y β son ordinales tales que |α| ≤ ℵγ y |β| ≤ ℵγ , entonces |α + β| ≤ ℵγ y |α · β| ≤ ℵγ . 23. Si a es un subconjunto propio de ℵα , entonces |ℵα − a| = ℵα . ℵβ ℵ 24. Probar que ℵα+1 = ℵαβ ×c ℵα+1 . ℵ 25. Probar que si 2ℵβ ≥ ℵα , entonces ℵαβ = 2ℵβ . ℵβ 26. Probar que Q si n ∈ ω, entonces ℵn = ℵn ×c 2ℵβ . 27. Probar que n∈ω ℵn = ℵℵω0 . 28. Probar que ℵℵω1 = ℵℵω0 ×c 2ℵ1 . 4. Cardinales Regulares y Singulares ´ n 5.8. Decimos que el ordinal β es cofinal con el ordinal Definicio α si existe una funci´on estrictamente creciente f : β −→ α que no es acotada en α . La cofinalidad de α es el menor ordinal cofinal con α y se le denota cof (α). 144

Obs´ervese que si α = β + 1 es un sucesor, la funci´on f : 1 −→ α tal que f (0) = β no es acotada en α , lo que prueba que la cofinalidad de un sucesor es siempre 1, por lo que este concepto tiene inter´es solo para ordinales l´ımite. El siguiente lema es consecuencia inmediata de la definici´on y puede ser usado como definici´on alternativa. Lema. Si β es cofinal con α , entonces existe una funci´on f : β −→ α tal que

[

f (γ) = α.

γ<β

´ n 5.9. Un cardinal infinito se dice regular si es igual a Definicio su cofinalidad. En caso contrario diremos que el cardinal es singular. Ejemplos 1. ω es regular. 2. ℵω es singular ya que cof (ℵω ) = ℵ0 . 3. Mas generalmente, ℵα es singular si y s´olo si α es l´ımite. Esto lo demostraremos m´as adelante. Teorema 5.43. Un cardinal S m es regular si y s´olo si para todo X ⊆ m, si |X| < m, entonces X < m. ´ n. Supongamos Demostracio que m regular y sea X ⊆ m tal que S |X| < m. Veremos que X 6= m. Para ello sea h : |X| −→ X una biyecci´on y definamos recursivamente f : |X| −→ m como sigue \ f (β) = {γ ∈ X : f ∗ β ⊆ γ and h(β) ≤ γ}, es decir, f asigna a β el menor elemento de X que sea mayor o igual que h(β) y que todos los valores asignados previamente por f . Es f´acil ver por inducci´on que f es creciente y como para todo β < |X|, h(β) < f (β), [ [ [ X⊆ h(β) ≤ f (β). β<|X|

Pero por hip´otesis y lemma

[

β<|X|

f (β) < m,

β<|X|

que es lo que queriamos demostrar. Si m no es regular entonces cof (m) ⊆ m, |cof (m)| = cof (m) < m S y cof (m) = m, es decir, X = cof (m) es un contraejemplo para la condici´on del teorema. 145

Teorema 5.44.

†

Todo cardinal sucesor infinito es regular.

´ n. Consideremos el cardinal ℵα+1 y sea f : β −→ Demostracio ℵα+1 una funci´on creciente donde β < ℵα+1 . Para cada γ < β, f (γ) ≤ ℵα , luego |

[

γ<β

|≤

X γ<β

|f (γ)| ≤

X γ<β

ℵα = |β| ×c ℵα ≤ ℵα ×c ℵα = ℵα .

Luego f es acotada en ℵα+1 y por lo tanto ning´ un β menor que ℵα+1 puede ser cofinal con ´el. Por lo tanto cof (ℵα+1 ) = ℵα+1 y ´este es regular.

Ejercicios. ¿Cu´al es la cofinalidad de ω + ω, ω · ω, ω ω ? Demuestre que cof (α) es un cardinal. Demuestre que cof (cof S (α)) = cof (α). Si m es un cardinal, cof (m) = m. Demuestre que la funci´on f definida en el teorema 5.43 es efectivamente creciente. 6. Demuestre que cof (m) es el menor cardinal n tal que existe una partici´on de m en n conjuntos cada uno de los cuales tiene cardinalidad estrictamente menor que m. 1. 2. 3. 4. 5.

5. La Hip´ otesis del Continuo Por el teorema de Cantor 5.9 sabemos que ℵ0 < 2ℵ0 , es decir, el conjunto de todos los subconjuntos de ω tiene mayor cardinalidad que ω . Sin embargo no sabemos si existe alg´ un otro cardinal entre ℵ0 y 2ℵ0 . La afirmaci´on de que este no es el caso recibe el nombre de Hip´otesis del Continuo (HC), es decir 2ℵ0 = ℵ1 .

Tal nombre se debe a que, como sabemos, el conjunto R de los n´ umeros reales, o continuo, es equinumeroso con el conjunto potencia de ω . En otras palabras, HC dice que el segundo cardinal infinito es la cardinalidad de los n´ umeros reales. Como corolario se obtiene que todo subconjunto no enumerable de n´ umeros reales tiene la misma cardinalidad. 146

En la d´ecada del 30, K. G¨odel demostr´o que HC es compatible con ZFC, es decir, que si existe un modelo de ZFC, entonces existe un modelo en el cual HC tambi´en es v´alido. En otras palabras, es imposible demostrar a partir de ZFCque HC es falsa. En la d´ecada del 60, P. Cohen demostr´o que HC tampoco es demostrable a partir de ZFC. Estos dos resultados conjuntamente implican que HC es independiente de ZFCy que tanto ella como su negaci´on pueden ser agregadas como nuevo axioma de la teor´ıa obteni´endose resultados muy distintos. La Hip´otesis Generalizada del Continuo (HGC) es la afirmaci´on 2ℵα = ℵα+1 .

Los resultados de G¨odel y Cohen tambi´en se aplican a HGC. Es interesante tambi´en notar que con posterioridad a los trabajos de Cohen, se ha demostrado que es consistente con ZFCque 2ℵ0 = ℵ1 , ℵ2 , . . . , pero como veremos a continuaci´on, no puede tomar cualquier valor. Lema. ℵω < ℵℵω0 . ´ n. Como sabemos, ℵω = Demostracio dad de Zermelo 5.34, como ℵm < ℵω , ℵω <

Y

m∈ω

P

n∈ω

ℵm . Por la desigual-

= ℵℵω0 .

Corolario 5.45. 2ℵ0 6= ℵω . ´ n. Si 2ℵ0 = ℵω , entonces Demostracio

una contradicci´on.

2ℵ0 < (2ℵ0 )ℵ0 = 2ℵ0 ×c ℵ0 = ℵ0 ,

Suponiendo HGC resulta bastante f´acil calcular las exponenciales de cardinales. Teorema 5.46. Si n es un cardinal infinito, entonces ncof (n) > n. 147

´ n. Sea F : cof (n) −→ n be such that S Demostracio α
[

α
X

F (α) ≤

α
Teorema 5.47. Sean m que HGC es v´alida. Entonces   m n m+ m =  n+

|F (α)| <

Y

n = ncof (n) .

α
y n dos cardinales infinitos y suponga

si si si

n < cof (m), cof (m) ≤ n ≤ m, m
´ n. (i) Supongamos que n < cof (m). Sea f ∈n m Demostracio entonces f es acotada en n , luego f ∈n α, para alg´ un α ∈ m. luego m ≤ = |n m| n [ ≤ | α| α<m

≤ ≤ ≤ ≤

X

α<m

X

|α|n

(|α| ∪ n)|α|∪n

α<m

X

(|α| ∪ n)+ ,

por 5.42 y HGC,

α<m

X

α<m

m = m ×c m = m

(ii) Si cof (m) ≤ n ≤ m,

m < mcof (m) ≤ mn = m+ ,

por lo tanto mcof (m) = m+ . (iii) Es consecuencia directa de 5.42 y HGC.

Ejercicios. 1. Demuestre que HGC es equivalente con mcof (m) = m+ , para todo m infinito. 148

2. (Hausdorff) Demuestre que ℵ

ℵ

β ℵα+1 = ℵαβ ×c ℵα+1 .

3. Demuestre que dados dos cardinales m y n, m > 2 y n > ℵ0 , se tiene cof (mn ) > n. Concluya que 2ℵ0 6= ℵω .

149

150

Bibliograf´ıa [1] Chuaqui, R. B. Aximatic Set Theory. Impredicative Theories of Classes. North– Holland, 1981. [2] Di Prisco, C. A. Una Introducci´on a la Teor´ıa de Conjuntos y los Fundamentos de las Matem´aticas. IVIC., Venezuela, 1996. Notas de Clase. [3] Enderton, H. B. Introduction to Set Theory. Academic Press, 1977. [4] Hrbacek, K. y Jech, T. Introduction to Set Theoru. Marcel Dekker, 1984. [5] Kunen, K. Set Theory, an Introduction to independence proofs. North-Holland, 1980. [6] Kuratowski, K. y Mostowski, A. Set Theory, with an introduction to descriptive set theory. North–Holland, 1976. [7] Monk, J. D. Introduction to Set Theory, Mac Graw-Hill, New York, 1969. [8] Moore, G. H. Zermelo’s Axiom of Choice. Its origins, Development, and influence. Springer–Verlag, 1982.

151

152

Glosario funci´ on inversa 30 imagen de un conjunto por una funci´on 30 funci´ on de a en b 31 funci´ on inyectiva 31 funci´ on uno a uno 31 funci´ on sobreyectiva 31 funci´ on identidad 33 restricci´ on de una funci´on 33 relaci´ on reflexiva 40 relaci´ on sim´etrica 40 relaci´ on transitiva 40 relaci´ on de equivalencia 40 clase de equivalencia 41 partici´ on 42 partici´ on asociada a una relaci´on de equivalencia 42 relaci´ on asociada a una partici´on 42 relaci´ on antisim´etrica 44 relaci´ on conexa 45 orden parcial 45 orden total 45 relaci´ on asim´etrica 46 orden estricto 46 relaciones isomorfas 46 isomorfismo de orden 46 preorden 47 cota superior 48 cota inferior 48 supremo 48 ´ınfimo 48 elemento minimal 48 elemento maximal 48 relaci´ on bien fundada 49 buen orden 49 sucesor 57 conjunto Inductivo 58 n´ umeros naturales 58 Principio de Inducci´on 58

clase propia 6 pertenencia 8 Axioma de Extensionalidad 9 subconjunto 9 Axioma del Conjunto Vac´ıo 9 conjunto vac´ıo 10 ∅ 10 Axioma de Separaci´on 10 Axioma de Pares 11 par no-ordenado 11 singleton 11 Axioma de Uniones 11 uni´on 11 intersecci´on 12 conjuntos disjuntos 12 Axioma del Conjunto Potencia 13 conjunto potencia 13 Axioma de Regularidad 13 Axioma del Conjunto Infinito 14 funci´on proposicional 14 Axioma de Reemplazo 14 complemento relativo 17 diferencia de conjuntos 17 complemento 18 par ordenado 23 producto cartesiano 24 relaci´on 24 dominio de una relaci´on 24 recorrido de una relaci´on 24 campo de una relaci´on 25 composici´on de relaciones 25 inversa de una relaci´on 25 imagen de un conjunto por una relaci´on 27 funci´on 30 dominio de una funci´on 30 recorrido de una funci´on 30 campo de una funci´on 30 composici´on de funciones 30 153

Principio de Inducci´on Completa 61 ∈–transitivo 64 ordinal 64 Principio de Inducci´on Transfinita 70 ordinal sucesor 70 ordinal 70 clausura transitiva 75 funci´on no–decreciente 75 funci´on estrictamente creciente 75 funci´on continua 75 funci´on normal 75 jerarqu´ıa acumulativa 101 universo de von Neumann 101 funci´on de elecci´on 105 equinumerosos 117 cardinal 117 cardinalidad 119 cardinal de un conjunto 119 Teorema de Cantor, Schroeder y Bernstein 119 Teorema de Cantor 122 ℵ 123 conjunto finito 125 conjunto infinito 126 conjunto enumerable 126 suma cardinal 129 Teorema de Zermelo 139 cofinal 144 cofinalidad 144 Hip´otesis del Continuo 146 Hip´otesis Generalizada del Continuo 147

154