TEORIA AXIOMATICA DE CONJUNTOS VersioŽn Preliminar


Indice
CAPITULO 1. IntroducciŽon. Los Axiomas de Zermelo Fraenkel 5 1. El Lenguaje Formalizado L 7 2. Los Axiomas de la TeorŽA±a ZF. Conceptos Fundamentales 9 CAPITULO 2. TeorŽA±a Elemental 17 1. Operaciones 17 2. Relaciones 23 3. Funciones 30 4. Relaciones de Equivalencia 40 5. Relaciones de Orden 44
CAPITULO 3. Ordinales 57 1. NuŽmeros Naturales 57 2. Ordinales 64 3. InducciŽon Transfinita 70 4. RecursiŽon 72 5. Funciones Normales 75 6. Ordinales y Buenos Ordenes 78 7. AritmŽetica Ordinal 80 8. La JerarquŽA±a Acumulativa de Conjuntos 101
CAPITULO 4. El Axioma de ElecciŽon 105 1. Equivalencias del Axioma de ElecciŽon 105 2. Aplicaciones 111
CAPITULO 5. Cardinales 117 1. Definiciones y Resultados BŽasicos 117 2. Conjuntos Finitos y Conjuntos Infinitos 125 3. AritmŽetica Cardinal 129 4. Cardinales Regulares y Singulares 144 5. La HipŽotesis del Continuo 146

BibliografŽA±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±a axiomŽatica debemos partir de tŽerminos que no podemos definir para no correr el riesgo de caer en un cŽA±rculo vicioso. Tal es el caso de los conceptos de conjunto y pertenencia dentro de la TeorŽA±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±a no es necesario contar con estas intuiciones. Una teorŽA±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ŽA±sticas y propiedades esenciales de los objetos que estamos tratando de describir en nuestro modelo. El ideal serŽA±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ŽA±as axiomŽaticas de conjuntos han logrado en mayor o menor grado el segundo deestos 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±a de Conjuntos. Lo mismo es cierto de otras teorŽA±as matemŽaticas como la teorŽA±a de nuŽmeros. Lo anterior parece condenar nuestro proyecto al fracaso, sin em- bargo Žesto no es asŽA±, sŽolo nos advierte que el ideal es imposible. De he- cho numerosos matemŽaticos han logrado establecer teorŽA±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±a de Zermelo–Fraenckel, ZF, desarrollada a partir del
5
trabajo de E. Zermelo el primero en proponer una teorŽA±a en los primeros an˜os 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 nuŽmeros 1,2, ,99, le corresponde la propiedad “ser nuŽmero entero mayor que cero y menor que cien”. A la inversa, a todapropiedad le debe corresponder un conjunto, la colecciŽon de todos los objetos que verifican dicha propiedad. Temprano en el desarrollo de la teorŽA±a de conjuntos se descubriŽo que esta intuiciŽon conducŽA±a a contradicciones y que debŽA±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ŽA±mbolos1
R = . La pregunta entonces es spertenece R a R?, o en sŽA±mbolos, sR 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 “pro- piedad”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±a. Sin embargo, la nociŽon de que a cada propiedad deberŽA±a correspon- der la colecciŽon de objetos que la verifican o “extensiŽon”de la propiedad, tiene fuerte arraigo en nuestra intuicioŽn. Algunos matemŽaticos no han queridodeshacerse de ella y han elaborado teorŽA±as bastante complejas, que incluyen dos tipos de objetos, conjuntos y clases propias. Deci- amos 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 ca- paz de determinar exactamente cuales son los elementos de dicho con- junto. Las clases son las extensiones de propiedades. Si Žesta pertenece a otra clase, entonces decimos que es un conjunto, si no, hablamos de
1Supondremos que el lector estŽa familiarizado con la terminologŽA±a y simbologŽA±a conjuntista pero lo prevenimos de que estos tendrŽan un sentido muy preciso en nuestra teorŽA±a y el que, a veces, difiere del popularizado en la ensen˜anza 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±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ŽA±, aunque no podemos afirmar “a R00 (porque R no existe dentro de la teorŽA±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 continuacioŽn a definir este concepto. Como dijimos, una teorŽA±a axiomŽatica se desarrolla a partir de cier- tos 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±a y repre- sentaran 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 nece- saria 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. ElLenguaje Formalizado L Un lenguaje formalizado estŽa constituido por un conjunto de sŽA±mbolos bŽasicos y por reglas que nos permiten formar expresiones mŽas compli- cadas a partir de esos sŽA±mbolos originales. Los sŽA±mbolos de L serŽan: 1. Variables: x,y,z,X,Y,Z,x1,x2, , en general, las uŽltimas le- tras del alfabeto latino, minuŽsculas o mayuŽsculas, con o sin subŽA±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ŽA±ï¬cos.
7
3. SŽA±mbolo de pertenencia: 4. SŽA±mbolo de igualdad: = 5. Conectivos lŽogicos: ¬, , →, ↔, es decir, los sŽA±mbolos ha- bituales 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 puntuacioŽn.
Cualquier cadena finita formada por estos sŽA±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 selee 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ŽA±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 nuŽmero 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 aparecenligadas 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 (tpero 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ŽA± estare- mos 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 enZF. Sin embargo, la expresiŽon en L de conceptos bastante sencillos puede resultar increiblemente complicada. AsŽA±, aceptaremos abreviaciones que faciliten la lectura. Por ejemplo el concepto de subconjunto se denota x y se puede expresar en terminos de los sŽA±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 lenguajeL, permitiremos el sŽA±mbolo en nuestras fŽormulas. Lo mismo sucederŽa con otros sŽA±mbolos. MŽas auŽn, en general usaremos expresiones del castellano y no su formalizaciŽon en L para trabajar con el concepto intuitivo y nocon 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±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 ). DefiniciŽon 1.1. Decimos que X es subconjunto de Y , en sŽA±mbolos, 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ŽA±o: “Existe un conjunto que no contiene ninguŽn 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 ninguŽn ele- mento.
DemostraciŽon. Supongamos que existen dos conjuntos distintos a y b ambos sin elementos. Por A1 x((x a x 6 b) (x b x 6 a)), una contradiccioŽn.Luego hay un uŽnico conjunto vacŽA±o.
DefiniciŽon 1.2. El (uŽnico) conjunto que no tiene elementos se llama el conjunto vacŽA±o y se le denota . ObsŽervese que el sŽA±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. DefiniciŽon 1.3. Si ϕ(x) es una fŽormula de L y A un conjunto, el conjunto cuya existencia estŽa garantizada por A3 se denotarŽa con el sŽA±mbolo y se lee “el conjunto de los elementos de A tales que ϕ(x)”.
Recordemos que la paradoja de Russell se produce al tratar de cons- truir 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 = . 10
En este caso tenemos que si R R, entonces R A y R 6 R, lo cual es una contradiccioŽn, 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.
DemostraciŽon. Supongamos que si existe y llamemoslo V . En- tonces en virtud de A3 podemos construir el conjunto de Russell R = , contradiccioŽn.
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 . 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 = , el que a menudo recibe el nombre de singleton X .
A5. Axioma de Uniones: “Si X es un conjunto, entonces existe un conjunto cuyoselementos son los elementos de los elementos de X ”. En L escribimos X Y z(z Y ↔ u(z u u X)). Nuevamente por A1, este conjunto es uŽnico, se llama la uniŽon de X y se le denota SX. 11
Un caso particular que merece una notaciŽon especial es el siguiente. Si X e Y son conjuntos, entonces existe S. (sPor quŽe ?) Entonces x [↔ (x X x Y ).S 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 =[.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 = y, en general, iterando el proceso, podemos definir n–tuplasno–ordenadas . Otra generalizaciŽon de un concepto familiar es el de intersecciŽon de un conjunto no–vacŽA±o X , en sŽA±mbolos, TX, definida por X = . Observemos que en virtud de A5 y de A3, TX es efectivamente un conjunto. sPor quŽe debemos exijir que X sea no–vacŽA±o? La interseccioŽn de dos conjuntos X e Y , X ∩Y , se define por X ∩Y =y en general X1 ∩X2 ∩···∩Xn =.En rigor, para definir x∩y no necesitamos A5. sCŽomo podrŽA±amoshacerlo? 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ŽA±mbolos lŽogicos, preferimos la escritura abreviada). Creemos que este axioma se explica por sŽA± mismo. El (uŽnico) 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ŽA±o contiene un elemento con el que no com- parte ninguŽn elemento.” En L escribimos x(x 6= y(y x y ∩x = )). A pesar de que noresulta 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 nuŽmeros naturales, Žesta es, que todo conjunto no vacŽA±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. DemostraciŽon. i) Supongamos que existe a tal que a a , entonces A = contradice a A7. ii) Idem i) con A = iii) Idem i) con A = . iv) Supongamos que existe el conjunto cuyos elementos son precisa- mente a1,a2,a3, . Llamemoslo A . Entonces A contradice a
13
A7 ya que para cualquier y A, digamos y = am para alguŽn 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 puededesarrollarse 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 X). Es claro que el conjunto asŽA± formado es intuitivamente infinito, basta verificar que contiene a los siguientes conjuntos , }}, por supuesto que habrŽA±a que demostrar ademŽas que todos estos con- juntos 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 = x, y = Px, y = x , y = 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 alguŽn 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] = , es tambiŽen un conjunto. El problema se suscita cuando vemos que en nuestra teorŽA±a la “funciŽon” x 7−→Px no es, como veremos formalmente mŽas adelante, un objeto de nuestra teorŽA±a, es decir, no es un conjunto, sino que corresponde a lo que lla- mamos una clase propia. Como ya hemos dicho antes, nuestro lenguaje nos permite referirnos a dichos objetos mediante la fŽormula que los de- fine, lo que para los efectos prŽacticos es casi lo mismo. AsŽA±, ϕ(x,y) no es una funciŽon dentro de nuestra teorŽA±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ŽA± 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ŽA±tulo 3, son suficientes para desar- rollar casi toda la matemŽatica. Inmediatamente se nos ocurren varias preguntas sson estos axiomas independientes entre sŽA± ? Es decir, sno pueden obtenerse unos de otros? Larespuesta 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ŽA±o puede obtenerse a partir del axioma de especificaciŽon y del axioma del conjunto infinito (habrŽA±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 auŽn es el problema de la consistencia, es decir, ses 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 de- scubierto ninguna contradiccioŽn (de no ser asŽA±, no tendrŽA±a sentido el estudio de esta teorŽA±a) y se estima que sŽA± son consistentes. El otro problema que surge naturalmente es el de la completud de este sistema de axiomas. Es decir, sson suficientes estos para deducir todos los teoremas posibles sobre conjuntos? La respuesta es tambiŽen no. Mas auŽn, 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 aZF, seguirŽa siendo incompleto, es decir, siempre existirŽa unafŽormula ϕ tal que ni ϕ ni ¬Ï• puede demostrarse a partir de esa lista. Todos estos problemas requieren de conocimientos de LŽogica Mate- mŽatica y estŽan fuera del alcance de esta obra. Nos parece interesante eso sŽA± 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 con- tiene a todos los elementos de los elementos de X ”. 3. Demuestre que el axioma del conjunto potencia puede ser reem- plazado por el axioma mŽas dŽebil: “Si X es un conjunto, entonces existe un conjunto que con- tiene 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ŽA±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 de- mostrar que el conjunto A definido en la demostraciŽon del teo- rema 1.3 existe.
16
CAPITULO 2
TeorŽA±aElemental
En este capŽA±tulo formalizaremos y profundizaremos las nociones de la teorŽA±a intuitiva de conjuntos que el lector probablemente ha estudi- ado en cursos de Algebra, GeometrŽA±a u otros. Por tratarse de material familiar, la mayorŽA±a de las demostraciones se dejarŽan como ejercicio. Debemos cuidarnos eso sŽA± 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±a A- xiomŽatica de Conjuntos es precisamente ese conocimiento intuitivo del tema. En nuestra teorŽA±a todo es un conjunto, asŽA± 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ŽA±as distintas. AsŽA±, 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ŽA±tulo anterior hemos definido las operaciones x y yx ∩y.Definiremos ahora una tercera operaciŽon DefiniciŽon 2.1. Dados dos conjuntos a y b definimos el comple- mento relativo de b con respecto a a , o su diferencia como sigue a−b = . Notese que en virtud de A3, a−b es un conjunto. Como lo demuestra la siguiente proposiciŽon, la nociŽon de comple- mento 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 ninguŽn conjunto.
DemostraciŽon. Sea a un conjunto. Si existiera su complemento llamŽemoslo a0, entonces en virtud de A5, a a0 serŽA±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 opera- ciones.
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) DemostraciŽon. Ejercicio La relaciŽon a b se relaciona con las otras operacionescomo 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) Si a c y b d, entonces a∩b c∩d. v) a a b y b a b. vi) Si a c y b c, entonces a b c. vii) a b si y sŽolo si a b = b. viii) Si a c y b d, entonces a b c d. DemostraciŽon. Ejercicio.
Algunas propiedades del conjunto potencia de un conjunto son in- teresantes.
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)) . DemostraciŽon. A modo de ejemplo demostraremos vi). El resto 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 ay 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} , (b) a , (c) ∩a , (d) −{} , (e) a , (f) .2. Sea a un conjunto. Si para todo conjunto b se tiene a b = b, probar que a = . 19
3. Demostrar que : (a) S,,} = . (b) T,,} = . (c) S = a =T , para todo conjunto a . (d)(Ta)∩(Tb) 6=T(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 = . 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ŽA±mbolos “ ” , “ ” y “ , ” . (c) Decidir si son ciertas o falsas las afirmaciones siguientes: (i) 1 2 (ii) 1∩2 = 0 (iii) (0∩2) 1 (iv) 1 2 (v) 1 2 = 2 (vi) S3 3 (vii) T4 4 (d) Expresar los siguientes conjuntos usando los conjuntos 0, 1, 2, 3 y 4. Simplifique. S , P ,SS , PP ,SSS , PPP .(e) Si a = ,4,} , encontrar T(Sa −4) .(f) Construir TS(P2 −2) .(g) Si a = ,,} , construir: Sa ,Ta ,SSa ,TTa ,STa ,TSa.6. Dar contraejemplo de P(a b) = Pa Pb .7. Probar que: (a) SPa = a . (b) a PSa . (c) No es cierto que si a b, entonces Pa Pb . (d) Si a b, entonces Pa PPSa . (e) S PSa. (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) a + (b + c) = (a + b) + c (d) a∩(b+ c) = (a∩b) + (a∩c) (e) a−b a + b (f) a = b si y sŽolo si a + b = (g) Si a + c = b + c , entonces a = b (h) a c = b c si y sŽolo si a + b c (i) (a c) + (b c) = (a + b)−c9. Sean a = b = c = (a) Describir a∩b∩c . (b) Sean n , m Z. Si d = e = , describa d∩e . s QuŽe pasa si m y n son nuŽmeros primos? s 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 con- traejemplo: (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±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 “ x0 ” . Probar o dar contraejemplo de: (a) b c si y sŽolo si b∩c0 = (b) b c si y sŽolo si b0∩c = (c) b c si y sŽolo si b0 c = a (d) b c si y sŽolo si b∩c0 b0 (e) b c si y sŽolo si b∩c0 c (f) b c si y sŽolo si b∩c0 d∩d0 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 para todo c a existe d b tal que c d, entonces Sa Sb(b) T{c : c = −b y x a} = (T{c : c = y x a})−b(c) [ x a x =[a (d) x a x =a (e) a∩([b) =[ c b (a∩c) (f) Si d 6= , entonces a b = c b (a c). 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 famil- iares, como par ordenado, relaciŽon, funciŽon, etc. Debemos tener espe- cial cuidado de que estos sean conjuntos en virtud de alguŽn axioma de ZF. Por otra parte, tambiŽen queremos que estos conjuntos se com- porten como los objetos con que trabaja el matemŽatico a quien no preocupan los problemasde fundamento.
DefiniciŽon 2.2. Dados dos conjuntos a y b llamamos par ordenado a, b al siguiente conjunto. ha,bi = {,}. a y b se llaman la primera y segunda coordenada de ha,bi , respec- tivamente. Notemos que ha,bi es efectivamente un conjunto. Para justificarlo, basta usar dos veces el axioma de pares. En el par no ordenado no podemos distinguir ambos ele- mentos ya que = (spor 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. DemostraciŽon. Supongamos que ha,bi = hc,di , Žesto es, {,} = ,}. Si a = b, tenemos {} = ,}, entonces = = , o sea a = b = c = d. (sQuŽe axiomas hemos usado?). Si a 6= b, = o = . En el primer caso, tenemos a = c y como ,} ya 6 = b, = luego a = c y b = d. En el segundo caso, a = c = d , luego {}, 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 or- denadas. ha,b,ci = hha,bi,ci ha,b,c,di =hha,b,c,i,di ha1,a2, ,ani = hha1, ,an−1i,ani. 23
Lema 2.6. Si a A y b A, ha,bi PPA. DemostraciŽon. Ejercicio.
DefiniciŽon 2.3. Llamaremos producto cartesiano de los conjuntos a y b al conjunto a×b = . 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 = . Podemos tambiŽen introducir productos cartesianos triples y cuadru- ples etc., de la manera obvia, por ejemplo a×b×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 DemostraciŽon. Ejercicio.
DefiniciŽon 2.4. Un conjunto R es una relaciŽon si todos sus ele- mentos son pares ordenados. Definimos tambiŽen el dominio de R Dom R = ,el recorrido de R Rec R = y el campo de R , Cam R = Dom R Rec R. Si Dom R A y Rec R B, decimos que R es una relaciŽonentre A y B o una relaciŽon de A en B .