Teora de Conjuntos

Antonia Huertas Sanchez Mara Manzano Arjonamara@usal.es

Febrero 2002

ii

ndice general

0.1. Prefacio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v

I TEORA BSICA DE CONJUNTOS1

1. Introduccin 31.1. Pinceladas histricas . . . . . . . . . . . . . . . . . . . . . . . . . 31.2. Teora intuitiva de conjuntos . . . . . . . . . . . . . . . . . . . . 4

1.2.1. La selva de Cantor . . . . . . . . . . . . . . . . . . . . . . 4

1.2.2. Problemas en la teora intuitiva de conjuntos: la paradojade Russell . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.2.3. Solucin de las paradojas . . . . . . . . . . . . . . . . . . 61.3. El Universo matemtico . . . . . . . . . . . . . . . . . . . . . . . 71.4. Teora axiomtica de conjuntos . . . . . . . . . . . . . . . . . . . 7

2. lgebra de Conjuntos 92.1. El lenguaje de la Teora de Conjuntos . . . . . . . . . . . . . . . 92.2. Igualdad, inclusin y conjunto vaco . . . . . . . . . . . . . . . . 102.3. Operaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3. Relaciones y Funciones 133.1. Clases unitarias, pares y dadas . . . . . . . . . . . . . . . . . . . 133.2. Conjunto potencia (o conjunto de las partes de un conjunto) . . 133.3. Gran unin y gran interseccin . . . . . . . . . . . . . . . . . . . 143.4. Producto cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . 143.5. Relaciones binarias . . . . . . . . . . . . . . . . . . . . . . . . . . 153.6. Relacin inversa, producto relativo y restriccin . . . . . . . . . . 153.7. Imagen bajo una relacin y relacin identidad. . . . . . . . . . . 163.8. Propiedades de ciertas relaciones . . . . . . . . . . . . . . . . . . 163.9. Relaciones de equivalencia . . . . . . . . . . . . . . . . . . . . . . 173.10. Relaciones de Orden . . . . . . . . . . . . . . . . . . . . . . . . . 183.11. Funciones, composicin . . . . . . . . . . . . . . . . . . . . . . . 193.12. Funciones de A en B . . . . . . . . . . . . . . . . . . . . . . . . . 19

iii

iv NDICE GENERAL

II Teora de Conjuntos Axiomtica21

4. Primeros Axiomas 234.1. Axiomas de Extensionalidad y de Separacin . . . . . . . . . . . 234.2. Axiomas del Par, de la Unin y de las Partes . . . . . . . . . . . 234.3. Axioma de Reemplazamiento . . . . . . . . . . . . . . . . . . . . 24

5. Construccin de los Ordinales 255.1. Buenos rdenes e induccin . . . . . . . . . . . . . . . . . . . . . 25

5.1.1. Induccin en un conjunto bien ordenado . . . . . . . . . . 265.1.2. Induccin en el conjunto de los nmeros naturales . . . . 26

5.2. Buenos rdenes y ordinales . . . . . . . . . . . . . . . . . . . . . 275.2.1. Comparacin de conjuntos bien ordenados: Isomorfismos . 275.2.2. Segmento . . . . . . . . . . . . . . . . . . . . . . . . . . . 275.2.3. Ordinal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

5.3. Observaciones acerca de los ordinales . . . . . . . . . . . . . . . . 28

6. La Jerarqua de Zermelo 316.1. Construccin de la Jerarqua . . . . . . . . . . . . . . . . . . . . 316.2. Axiomas involucrados en la construccin de la jerarqua . . . . . 32

7. Los Axiomas de Eleccin y Constructibilidad 357.1. Axioma de la eleccin . . . . . . . . . . . . . . . . . . . . . . . . 35

7.1.1. Otras formulaciones del axioma de eleccin . . . . . . . . 367.1.2. Importancia del Axioma de Eleccin . . . . . . . . . . . . 36

7.2. Axioma de Constructibilidad . . . . . . . . . . . . . . . . . . . . 36

8. Ejercicios 398.1. Igualdad, Inclusin y Conjunto vaco . . . . . . . . . . . . . . . . 398.2. Operaciones: Algebra de conjuntos . . . . . . . . . . . . . . . . . 398.3. Clases Unitarias, Pares y Dadas . . . . . . . . . . . . . . . . . . 408.4. Conjunto Potencia (o Conjunto de las Partes de un Conjunto) . . 408.5. Gran Unin y Gran Interseccin . . . . . . . . . . . . . . . . . . 408.6. Producto Cartesiano . . . . . . . . . . . . . . . . . . . . . . . . . 418.7. Relaciones Binarias . . . . . . . . . . . . . . . . . . . . . . . . . . 418.8. Relacin Inversa, Producto Relativo y Restriccin . . . . . . . . . 428.9. Imagen bajo una Relacin y Relacin de Identidad . . . . . . . . 428.10. Propiedades de ciertas relaciones . . . . . . . . . . . . . . . . . . 438.11. Relaciones de Equivalencia . . . . . . . . . . . . . . . . . . . . . . 438.12. Relaciones de Orden . . . . . . . . . . . . . . . . . . . . . . . . . 438.13. Funciones, Composicin . . . . . . . . . . . . . . . . . . . . . . . 438.14. Funciones de A en B . . . . . . . . . . . . . . . . . . . . . . . . . 448.15. Induccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

9. Bibliografa 49

0.1. PREFACIO v

0.1. PrefacioLas notas que siguen constituyen una gua para un curso bsico de teora de

conjuntos. La primera parte, formada por tres captulos, se podran insertar enun curso de introduccin de lgica, entre la lgica proposicional y la de primerorden. Si el curso se piensa dar en Facultades de Letras, se puede complementarcon una serie de ejercicios an ms elementales (que estamos elaborando) cuyoobjetivo es que el alumno sepa trasegar con conjuntos y relaciones concretas. Nose incluyen las demostraciones, que son la parte fundamental del curso, ya quelas hacemos en la pizarra. Esto no es un libro, son unos apuntes que esperamosos sean de alguna ayuda.El bloque completo de estas notas constituye un curso de 20 horas para

alumnos de primer ciclo. Por tratarse de una asignatura de las denominadasde LIBRE CONFIGURACIN (esto quiere decir que no es de ninguna carreraen particular, que la pueden elegir alumnos de cualquier titulacin) no se puedesuponer un conocimiento previo homogneo, de ah proviene su estilo mestizo.

vi NDICE GENERAL

Parte I

TEORA BSICA DECONJUNTOS

1

Captulo 1

Introduccin

1.1. Pinceladas histricas

En el ltimo cuarto del siglo XIX se vivi un episodio apasionante de la his-toria de las matemticas que las ligara desde entonces a la historia de la lgica.Primero, Georg Boole (1815-1864) en su Mathematical Analysis of Logic tratde presentar la lgica como parte de las matemticas. Poco despus GottlobFrege (1848-1925) intent mostrar que la aritmtica era parte de la lgica en suDie Grundlagen der Arithmetik. Pero, dando un gran paso tanto en la historiade las matemticas como en la historia de la lgica, G. Cantor se haba ade-lantado a Frege con una fundamentacin lgica de la aritmtica. Cantor habademostrado que la totalidad de los nmeros naturales comprendidos en el inter-valo de extremos 0 y 1 no es numerable, en el sentido de que su infinitud no esla de los nmeros naturales. Como una consecuencia de esa situacin, Cantorcre una nueva disciplina matemtica entre 1874 y 1897: la teora de conjuntos.Su obra fue admirada y condenada simultneamente por sus contemporneos.Desde entonces los debates en el seno de la teora de conjuntos han sido siempreapasionados, sin duda por hallarse estrechamente conectados con importantescuestiones lgicas.Segn la definicin de conjunto de Cantor, ste es una coleccin en un todo

de determinados y distintos objetos de nuestra percepcin o nuestro pensamien-to, llamados los elementos del conjunto. Frege fue uno de los admiradores dela nueva teora de Cantor, y dio una definicin de conjunto similar.En 1903 B. Russell demostrara que la teora de conjuntos de Cantor era

inconsistente y cuestionara la definicin de conjunto en la teora de Cantor.Pero pronto la teora axiomtica de Zermelo (1908) y refinamientos de stadebidos a Fraenkel (1922), Skolem (1923), von Newman (1925) y otros sentaronlas bases para la teora de conjuntos actual.Es indiscutible el hecho de que la teora de conjuntos es una parte de las

matemticas, es adems, la teora matemtica dnde fundamentar la aritmtica

3

4 CAPTULO 1. INTRODUCCIN

y el resto de teoras matemticas. Es tambin indiscutible que es una parte dela lgica y en particular una parte de la lgica de predicados.En esta historia cruzada de las matemticas, la lgica y los fundamentos de

ambas, la teora de conjuntos permitira por un lado una fundacin logicistade las matemticas; pero por otro lado la teora de conjuntos mirada comoparte de las matemticas proporciona el metalenguaje, el contexto o sustratode las teoras lgicas. Finalmente, puede ser completamente expresada en unlenguaje de primer orden y sus axiomas y teoremas constituyen una teora deprimer orden a la que pueden aplicarse los resultados generales que se aplicana cualquier teora de primer orden.En los captulos que siguen se presenta primero la teora intuitiva de con-

juntos, basada en la original de Cantor, para seguir con sus problemas de incon-sistencia y la solucin axiomtica final como la teora de conjuntos de Zermelo-Fraenkel.

1.2. Teora intuitiva de conjuntos

1.2.1. La selva de Cantor

La definicin inicial de Cantor es totalmente intuitiva: un conjunto es cualquiercoleccin C de objetos determinados y bien distintos x de nuestra percepcin onuestro pensamiento (que se denominan elementos de C), reunidos en un todo.Igual que en Frege su idea de lo que es un conjunto coincide con la extensin deun predicado (la coleccin de objetos que satisface el predicado).Esta idea sencilla y tan intuitiva resulta ser tambin ingenua porque produce

enormes contradicciones de inmediato, como por ejemplo la paradoja de Russell.Para poder mostrarlo es necesario empezar por formalizar esta teora intuitivaque, aparte de los smbolos para los conjuntos y sus elementos (x,C, etc.), tendrlos smbolos de pertenencia e igualdad = (de los objetos del lenguaje formal).Que x es un elemento del conjunto C se expresa x pertenece a C o bien x C.Que x no es un elemento de C se expresa x no pertenece a C (x / C).Tendremos en cuenta que no es necesario denotar siempre con maysculas

a los conjuntos y con minsculas a sus elementos, ya que un conjunto puedeser a su vez un elemento de otro conjunto e incluso podemos considerar que ennuestra teora no hay objetos que no sean conjuntos.Cmo se determina una coleccin?

Listar los objetos. De acuerdo con la definicin intuitiva de Cantor un con-junto queda definido si es posible describir completamente sus elementos.El procedimiento ms sencillo de descripcin es nombrar cada uno de suselementos, se llama definicin por extensin; es conocida la notacin deencerrar entre llaves los elementos del conjunto.

Ejemplo:

A = {a, b, c}. Donde A es el conjunto formado por la coleccin de objetos

1.2. TEORA INTUITIVA DE CONJUNTOS 5

a, b y c.

B = {,,,,}. Donde B es el conjunto formado exactamente poresos cinco crculos.

Entonces es cierto que b A y que b / B.El inconveniente para este mtodo de listado o enumeracin de los elemen-tos del conjunto es que stos deben poseer un nmero finito de elementosy, en la prctica, un nmero muy pequeo

Qu hacer cuando la coleccin es infinita, o cuando es finita pero nu-merosa?

Describir los objetos. Cuando el nmero de elementos del conjunto es in-finito (como el de los nmero impares) o demasiado numeroso (como el detodas las palabras que pueden formarse con el alfabeto latino) se utilizael mtodo de definicin por intensin, que consiste en la descripcin deun conjunto como la extensin de un predicado, esto es, mediante una ovarias propiedades (el predicado) que caracterizan a los elementos de eseconjunto.

En principio podra tomarse cualquier lengua natural para describir los ob-jetos (espaol, ingls, italiano, vasco, cataln, etc), sin embargo es preferibleutilizar un lenguaje formal que ofrezca rigor y precisin. Dicho lenguaje debeser suficientemente rico; esto es, lo suficientemente expresivo como para poderdescribir todas las colecciones matemticas. Pero tambin lo suficientemente re-strictivo como para limitarse a slo las colecciones de objetos matemticos. Paraexpresar predicados utilizaremos el lenguaje formal de la la lgica de predica-dos de primer orden (el lenguaje de la lgica de proposiciones con los smboloslgicos de las conectivas ,,,, ms los cuantificadores universal y exis-tencial ) al que se aade variables, igualdad y el relator binario de pertenencia.Este lenguaje puede ser ampliado con los smbolos propios de las operaciones,relaciones o funciones del lenguaje especfico de teora de conjuntos.En la primera parte, al presentar la Teora bsica de conjuntos, utilizaremos

con frecuencia el lenguaje natural para describir propiedades. Estas propiedadespueden ser aritmticas (

6 CAPTULO 1. INTRODUCCIN

1.2.2. Problemas en la teora intuitiva de conjuntos: laparadoja de Russell

Pero la definicin intuitiva de conjunto como el de una coleccin de objetosdescribible por un predicado conduce inevitablemente a ciertas contradiccionesque se llaman paradojas, la ms clebre es la conocida como paradoja de Russell:Consideremos el conjunto A = {x : x / x}, descrito mediante el predicado

del lenguaje formal x / x . Obviamente, para cualquier B, B A si y slo siB / B. Es decir, est en A cuando verifica las condiciones que definen a A. Pero,qu sucede con el propio A? Evidentemente, A A si y slo si A / A. Pero esteresultado es contradictorio. En vano se debe intentar descubrir un error en elrazonamiento, ms bien parece que el problema proviene de admitir expresionescomo A A (o conjuntos como el conjunto de todos los conjuntos que producetambin paradojas).Se ha visto claramente que el concepto de conjunto no es tan sencillo y que

identificarlo sin mayor investigacin con el de coleccin resulta problemtico.Para evitar la paradoja de Russell, y otras de esta naturaleza, es necesariotener ms cuidado en la definicin de conjunto, lo veremos en lo que sigue.Otras paradojas, de hecho las primeras en descubrirse, afectaban a coleccionesgrandes, como por ejemplo la de los ordinales, o la de todos los conjuntos. Estascolecciones no podrn ser conjuntos.

1.2.3. Solucin de las paradojas

Una solucin radical al problema de las paradojas es la propuesta en 1903por Russell, su Teora de Tipos. Observa que en todas las paradojas conocidashay una componente de reflexividad, de circularidad. Tcnicamente se evitanlas paradojas al eliminar del lenguaje las formaciones circulares. Se reconoceque nuestro universo matemtico no es plano, sino jerarquizado, por niveles, yque el lenguaje ms adecuado para hablar de un universo ?? debe tener diversostipos de variables que correspondan a cada nivel; en particular, la relacin depertenencia se d entre objetos de distinto nivel.En 1908 Zermelo da como solucin la definicin axiomtica de la Teora de

Conjuntos, refinada ms tarde por Fraenkel, Skolem, von Neumann y otros. Enesta teora se evita que las colecciones que llevaban a las paradojas puedan serconjuntos. De hecho, en la solucin de Zermelo-Fraenkel, una coleccin de obje-tos ser un conjunto si los axiomas la respaldan. Dichos axiomas permiten formarconjuntos a partir de conjuntos previamente construdos y postulan la existenciadel y de al menos un conjunto infinito. Sin embargo, en la solucin de vonNeumann se admiten colecciones que no son conjuntos, las denominadas clasesltimas. Se definen clases mediante propiedades, sin restriccin, pero habr quemostrar que se trata de conjuntos viendo que pertenecen a alguna clase. Lasclases ltimas, como la clase universal o la de los ordinales, no pertenecen aninguna otra clase.

1.3. EL UNIVERSO MATEMTICO 7

1.3. El Universo matemtico

La idea intuitivamente ms fructfera y tambin la ms extendida es quenuestro universo matemtico, -esto es, el que contiene todas las colecciones deobjetos matemticos, pero solamente los objetos matemticos- constituye unajerarqua de conjuntos, la denominada Jerarqua de Zermelo.En la construccin de los conjuntos que formarn la jerarqua se parte de

una coleccin inicial M0 de objetos dados y a continuacin se construye unacoleccin M1 de conjuntos de elementos de M0, despus una coleccin M2 deconjuntos de objetos de M0 y M1, etc.??, el universo de conjuntos construdos es una jerarqua. Para proporcionar

mayor precisin debemos responder a las preguntas siguientes:

1. Cal ser nuestra coleccin de partida, M0?

2. Qu conjuntos de objetos de niveles inferiores se toman para formarnuevos niveles en la jerarqua?

3. Hasta dnde se extiende esta jerarqua?.

Para responder a la primera pregunta debemos considerar si nos interesatomar objetos que no sean conjuntos o si nos basta con partir de un primernivel que sea sencillamente el conjunto . Est claro que ??se toman slo objetosmatemticos, pero habr que ver que es suficiente y que podremos finalmentecontar en la jerarqua con todos los objetos matemticos.Una respuesta a la segunda pregunta que parece razonable es, al ir tomando

nuevos conjuntos, que stos se puedan describir con nuestro lenguaje. Al tomaresta opcin formamos la Jerarqua de conjuntos constructibles. Otra posibilidades tomar como objetos de un nuevo nivel a todos los posibles. Veremos que estaes la opcin de Zermelo.Finalmente, la tercera de las preguntas es hasta donde se extiende la jer-

arqua. La respuesta es que la jerarqua de conjuntos no tiene fin, siempre sepueden construir nuevos niveles.Para precisar un poco ms esta imagen intuitiva de nuestro Universo matemti-

co es conveniente contar con algunas nociones de teora de conjuntos bsica ycon el concepto de ordinal. Por ello volveremos sobre este tema cuando tengamosel equipamiento necesario.

1.4. Teora axiomtica de conjuntos

Recordemos los componentes de una teora axiomtica:

1. El lenguaje o smbolos formales de la teora.

2. Los axiomas, que son proposiciones acerca de los objetos de la teora yque imponen el funcionamiento de dichos objetos.

8 CAPTULO 1. INTRODUCCIN

3. Los teoremas, que son todas las proposiciones demostrables con herramien-tas lgicas a partir de los axiomas.

En la teora de conjuntos axiomtica de Zermelo Fraenkel se usar el lenguajeformal de la lgica de predicados de primer orden. Las variables de dicho lenguajeformal se referirn a conjuntos; es decir, en la interpretacin usual todos losobjetos son conjuntos. Es decir, existir ser sinnimo de ser un conjunto. Ellenguaje bsico slo tiene el relator binario de pertenencia, pero se extiende,mediante definiciones pertinentes, para dar cabida a operaciones.Los conceptos primitivos de esta teora son el de conjunto y el de pertenencia.

En realidad la mayora de los axiomas sirven para garantizar la existencia delos conjuntos que nos interesa tener. Por ello la idea de construccin es esencialen la teora axiomtica de Zermelo-Fraenkel (que notaremos ZF).En la teora axiomtica de conjuntos se respeta la idea fundamental de acep-

tar que una coleccin de objetos pueda ser un conjunto, pero se impone la condi-cin de que todos los objetos de una coleccin deben haberse formado antes dedefinir dicha coleccin, y de esta manera se evitarn los problemas que conducena las paradojas. Uno de los axiomas de la teora (se ver ms adelante) impon-dr esta restriccin: Si X es un conjunto ya construido existe un conjunto Yformado por los elementos de X que satisfacen un predicado P que los describe(o lo que es lo mismo, una frmula con al menos una variable libre). As unpredicado describir un conjunto slo si los objetos han sido ya construidos (sonde otro conjunto X) y adems satisfacen el predicado.Con esta restriccin a la definicin de conjunto de Cantor desaparece la

paradoja de Rusell ya que para que A = {x : x / x} sea un conjunto se deberatener un conjunto X a partir del cual construirse; es decir, A = {x X : x / x}.Cmo se resuelve la paradoja? Al construirse a partir de un conjunto ya

construido desaparece el problema. Ahora, para cualquier B se verifica: B Asi y slo si B X y B / B. En realidad, puesto que la condicin B / B lacumplen todos, A ser el propio X. Adems, es imposible que exista el conjuntode todos los conjuntos.Los teoremas de ZF se derivan de los axiomas, pero para que tengan inters

deben mediar definiciones de conceptos y operaciones nuevas. Aunque en prin-cipio podra usarse un clculo deductivo de primer orden, en la prctica resultadesaconsejable pues en l cualquier demostracin se alargara en exceso.

Captulo 2

lgebra de Conjuntos

2.1. El lenguaje de la Teora de Conjuntos

A continuacin presentamos el lenguaje de primer orden L en el que es-cribiremos la Teora de Conjuntos. Puede entenderse de dos maneras distintas:como lenguaje formal y como abreviaturas de expresiones en espaol. Esta se-gunda interpretacin ser posiblemente la conveniente en un curso introductorio,antes de conocer la lgica de primer orden.Los smbolos del lenguaje formal de la teora de conjuntos sern:

Los smbolos de conjuntos sern las letras del alfabeto, maysculas yminsculas.

El smbolo de la relacin de pertenencia entre conjuntos es .

Los smbolos lgicos de la lgica de predicados: (negacin), (conjuncin), (disyuncin), (implicacin), (equivalencia), (cuantificador univer-sal) y (cuantificador existencial) y (, ) (parntesis).

Con estos signos bsicos se generan todas las frmulas de la teora de con-juntos. Las reglas de formacin de frmulas son las habituales en la lgica deprimer orden. A saber:

1. x y y x = y son frmulas. Para cualesquiera variables x, y.

2. Si y son frmulas, tambin lo son: , , , y

3. Si es una frmula, x y x tambien lo son.

FORM(L) se generan mediante las reglas precedentes:

9

10 CAPTULO 2. LGEBRA DE CONJUNTOS

2.2. Igualdad, inclusin y conjunto vaco

Definiciones:

A / B es la abreviacin de no pertenencia (A B)

Igualdad (Axioma de extensionalidad). x(x A x B) A = BSi todo elemento lo es de A si y slo si lo es tambin de B entonces A yB coinciden.

Inclusin, subconjunto: A B A est incluido en B (A es subconjuntode B), es una abreviatura de x(x A x B)) (todo elemento de Aes elemento de B).

Inclusin estricta: A B es una abreviatura de (A B) (A 6= B).

Conjunto vaco: es el nico conjunto tal que x(x / ) para todo x,x no pertenece a (ningn elemento pertenece a )

Teoremas: Los resultados siguientes son teoremas que se deducen de maneradirecta de las definiciones anteriores

1. A( A)

2. A (A A)

3. AB ((A B) (B A) (A = B))

4. ABC ((A B) (B C) (A C))

2.3. Operaciones

Definiciones

Unin. A B = {x/ (x A) (x B))} A unin B est formado porlos elementos que estn en A o en B. Se verifica: x(x A B (x A) (x B))

Interseccin A B = {x/ (x A) (x B)} A interseccin B estformado por los elementos que estn en A y tambin en B. Se verifica:x(x A B (x A) (x B))

Diferencia AB = {x/ (x A) (x / B)} Amenos B est formado porlos elementos que estn en A pero no en B. Se verifica: x(x AB (x A) (x B))

2.3. OPERACIONES 11

Teoremas

1. AB (A A B)2. AB (A B A)3. AB ((A B) (A B = B))4. AB ((A B) (A B = A))5. A (A A = A). Idempotencia.6. A (A A = A). Idempotencia.7. AB (A (A B) = A). Absorcin.8. AB (A (A B) = A). Absorcin.9. AB (A B = B A). Commutatividad.10. AB (A B = B A). Commutatividad.11. AB (AB = B A)12. A ( A = )13. A (A = A)14. A (A = )15. ABC ((A B) C = A (B C)). Asociatividad.16. ABC ((A B) C = A (B C)). Asociatividad.

12 CAPTULO 2. LGEBRA DE CONJUNTOS

Captulo 3

Relaciones y Funciones

3.1. Clases unitarias, pares y dadas

Definiciones

Par desordenado. {x, y} = {z/ (z = x) (z = y)}) ; es el conjunto forma-do por los elementos x, y.

Clase unitaria. {x} = {x, x}

Notacin: {x, y, z} = {x, y} {z} .

Par ordenado. hx, yi = {{x} , {x, y}}

Teoremas

1. xyzv (({x, y} = {z, v}) ((x = z y = v) (x = v y = z)))

2. xy (x = y hx, yi = {{x}})

3. xyzv (hx, yi = hz, vi (x = z y = v))

3.2. Conjunto potencia (o conjunto de las partesde un conjunto)

Definicin

Partes de un conjunto. PA = {C/ C A} , partes de A est formado porlos subconjuntos de A.

13

14 CAPTULO 3. RELACIONES Y FUNCIONES

Teoremas

1. A ( PA)2. A (A PA)3. AB ((PA PB) P(A B))4. AB (PA PB = P(A B))

3.3. Gran unin y gran interseccinDefiniciones

Gran unin.[A = {x | A (A A x A)} . La gran unin del con-

junto A est formado por los objetos que son elementos de algn elementode A.

Gran interseccin.\A = {x | A (A A x A)} . La gran inter-

seccin del conjunto A est formado por los objetos que son elementos detodos los elemento de A.

Convencin:\ =

Teoremas

1. AB ([{A,B} = A B)

2. AB (\{A,B} = A B)

3. AA ((A A) (A [A))

4. A ([PA = A)

3.4. Producto cartesianoDefinicin Producto cartesiano de dos conjuntos. A B = {z | uv(z =hu, vi u A v B)}Est formado por los pares ordenados cuyos primera componente es de A y

la segunda de B.

Teoremas

1. ABC (A (B C) = (AB) (A C))2. ABCD ((A B) (C D) = (A C) (B D))3. ABC ((AB) C = (A C) (B C))4. AB (AB PP(A B))

3.5. RELACIONES BINARIAS 15

3.5. Relaciones binariasDefiniciones

Relacin binaria. Una relacin binaria es una clase de pares ordenados.R(R es una relacin yz (x = hy, zi).La llamaremos simplemente relacin.

Dominio. Dom R = {x | y hx, yi R}Rango. Rang R = {x | y hy, xi R}Campo. Camp R = Rang R Dom R

Teoremas Los resultados siguientes son teoremas que se deducen de maneradirecta de las definiciones anteriores.

1. es un relacin2. R ((R es una relacin) (R (Dom RRang R)))3. RS ((R es una relacin S R) (S es un relacin))4. RS ((R es una relacin S es una relacin) ((RS es una relacin) (R S es una relacin) (R S es una relacin)))

5. RS (Dom (R S) = (Dom R Dom S))6. RS (Dom (R S) (Dom R Dom S))7. RS (Dom (R S) (Dom RDom S))8. A((A(A A A es relacin)) (

\A es relacin

[A es relacin))

3.6. Relacin inversa, producto relativo y re-striccin

Definiciones

Relacin inversa. R1 = {hx, yi | hy, xi R}Producro relativo. R/S = {hx, yi | z (hx, zi R hz, yi S}Restriccin de una relacin a un conjunto. R A = {hx, yi | hx, yi R x A}

Teoremas

1. xy (hx, yi R1 hy, xi R)2. R (R1 es una relacin)3. R ( (R1)1 R )4. R ( R es una relacin R = (R1)1)

16 CAPTULO 3. RELACIONES Y FUNCIONES

3.7. Imagen bajo una relacin y relacin identi-dad.

Definiciones

Imagen de A bajo R. R [A] = Rang R A

Identidad sobre A. IA = {hx, xi | x A}

Teoremas

1. x ((x R [A]) (y (hy, xi R y A)))2. RAB (R [A B] = R [A] R [B])3. RAB ((R [A B]) (R [A] R [B]))4. RAB (R [A B] = R [A] R [B])5. RAB ((R[AB] (R [A]R [B])6. RAB (R [A B] 6= R [A] R [B])

3.8. Propiedades de ciertas relacionesDefiniciones

R es reflexiva si y slo si x ((x Camp R) (hx, xi R))R es simtrica si y slo si xy ((hx, yi R) (hy, xi R))R es transitiva si y slo si xyz ((hx, yi R hy, zi R) (hx, zi R))R es irreflexiva si y slo si x ((x Camp R) (hx, xi / R))R es asimtrica si y slo si xy ((hx, yi R) (hy, xi / R))R es intransitiva si y slo si xyz ((hx, yi R hy, zi R) (hx, zi /R))

R es antisimtrica si y slo sixy ((hx, yi R hy, xi R) (x = y))R est conectada syss xy ((x, y Camp R) x 6= y) (hx, yi R hy, xi R))R est fuertemente conectada syss xy((x, y Camp) (hx, yi R hy, xi R))R es eucldea syss xyz ((hx, yi R hx, zi R) (hy, zi R))R es incestuosa syss xyz((hx, yi R hx, zi R) (u(hy, ui R hz, ui R)))

3.9. RELACIONES DE EQUIVALENCIA 17

Teoremas

1. R ((R es asimtrica ) (R es antisimtrica))

2. R ((R esta fuertemente conectada ) (R esta conectada))

3.9. Relaciones de equivalencia

Definiciones

R es una relacin de equivalencia si y slo si R es una relacin y R esreflexiva, simtrica y transitiva

R es una relacin de equivalencia sobre A si y slo si Camp R = A y R esuna relacin de equivalencia

Clase de equivalencia de x Camp R segn R : [x]R = {y | hy, xi R}

Cociente. Si R una equivalencia sobre A , el cociente de A por R es A/R ={[x]R | x A}

Particiones. H es una particin de A si y slo si

x (x H x 6= ) xy (x, y H x 6= y x y = ) [

H = A

Relacin de equivalencia asociada a una particin. Si H es una particinse define la relacin de equivalencia:

RH = {hx, yi | B (B H x B y B)}

Teoremas Los resultados siguientes son teoremas que se deducen de maneradirecta de las definiciones anteriores.

1. R ((R es una relacin de equivalencia ) (xy(x, y CampR ((hx, yi R) ([x]R = [y]R)))

2. R ((R es una relacin de equivalencia sobre A) ([A]/R es unaparticin de A))

3. H ((H es una particin de A) (RH es una relacin de equivalenciasobre A))

4. A(R(((R A) (R es de equivalencia) ) (\A es de equivalencia))

18 CAPTULO 3. RELACIONES Y FUNCIONES

3.10. Relaciones de OrdenDefiniciones

R es una relacin de orden (parcial) si y slo si R es una relacin y R esreflexiva y antisimtrica y transitiva

R es un orden (parcial) sobre A si y slo si Camp R = A y R es unarelacin de orden

R es un orden lineal si y slo si R es una relacin de orden y R estaconectada

R es un orden lineal sobre A si y slo si Camp R = A y R es una relacinde orden lineal

Un conjunto parcialmente ordenado es un par hA,Ri formado por un con-junto A y un orden parcial sobre A.

Un conjunto linealmente ordenado es un par hA,Ri formado por un con-junto A y un orden lineal sobre A.

Sea hA,Ri un conjunto parcialmente ordenado y sea Y A.Un elemento a Y es un elemento minimal de Y si y slo si x(x

Y hx, ai R).Un elemento a Y es primer elemento de Y (mnimo de Y ) si y slo si

x(x Y ha, xi R).Un conjunto parcialmente ordenado hA,Ri , est bien fundado si cadasubconjunto no vacio de A posee elemento minima.

Cuando hA,Ri est linealmente ordenado y bien fundado decimos que estbien ordenado.

Notacin: Habitualmente escribiremos en vez de R para relaciones de orden,y hA,i para conjuntos ordenados tanto parcial como linealmente.

Teoremas

1. R ((R es un orden lineal ) (R es un orden parcial))2. Si hA,i esta linealmente ordenado y Y A entonces (a es elemento

minimal de Y si y slo si a es primer elemento de Y )

3. hA,i est bien ordenado syss (para cada Y A se cumple x(x Y xes primer elemento de Y ))

4. Sea hA,i un conjunto parcialmente ordenado. hA,i esta bien fundadosyss no hay ninguna sucesion {an}n=0 de elementos de A tal que an+1 < anpara cada n (no hay a0 > a1 > a2 > ...)

3.11. FUNCIONES, COMPOSICIN 19

3.11. Funciones, composicin

Definiciones

Funcin. f es una funcin si y slo si f es una relacin y (xyz(((hx, yi f) (hx, zi f)) (y = z)))Composicin: f g = g/f

Notacin: Si f es una funcin notaremos f(x) = y para indicar hx, yi f

Teoremas

1. Af ( (f es una funcin A f) ( A es una funcin))2. Af ( (f es una funcin ) (f A es una funcin))3. fg ( (f es una funcin g es una funcin ) (f g es una funcin))4. fg ( (f es una funcin g es una funcin ) (f/g es una funcion))5. fg ( (f es funcin g es funcin Dom f Dom g = ) (f g es

funcin))

6. f ( (f es funcin z (z Rang f hx, zi f hy, zi f x =y)) f1 es una funcin)

7. fg ( (f es funcin g es funcin) (f g es funcin))8. fgx ((f es funcin g es funcin x Dom(f g)) ((f g)(x) =

f(g(x))))

3.12. Funciones de A en B

Definiciones

f es una funcin de A en B si y slo si f es una funcin y Dom f =A y Rang f B

Notacion: para indicar que f es una funcion de A en B escribiremos f : A B

f es una funcion inyectiva si y slo si f es una funcin y (xyz (hx, yi f hz, yi f x = z))f : A B es exhaustiva si y slo si Rang f = Af : A B es biyectiva si y slo si f es inyectiva & exhaustiva

Notacion: AB denotar el conjunto de todas las funciones de B en A

20 CAPTULO 3. RELACIONES Y FUNCIONES

Teoremas

1. f ((f es inyectiva ) (f es una funcin f1 es una funcin))2. fxy (((f es inyectiva) (x, y Dom f)) ((f(x) = f(y) (x = y)))3. fg ((f es inyectiva g es inyectiva ) (f g es inyectiva))

Parte II

Teora de ConjuntosAxiomtica

21

Captulo 4

Primeros Axiomas

Los axiomas de la teora ZF son propiedades indemostrales que se aceptancomo verdaderas y que tienen por objeto garantizar que en la Jerarqua deConjuntos ZF todo lo construdo son conjuntos y as evitar las paradojas.

4.1. Axiomas de Extensionalidad y de Separacin

Definicin

Axioma de Extensionalidad: AB (A = B x(x A x B). Esteaxioma asegura que el smbolo lgico = para la igualdad de objetos de lateora coincide con la intuicin de que dos conjuntos son iguales si tienenlos mismos elementos.

Axioma de Separacin: AB(x B (x A (x)) . Expresa quesi (x) es una frmula del lenguaje de la teora de conjuntos, con a losumo la variable x libre y A es un conjunto, entonces la clase (coleccin){x/x A (x)} es un conjunto. El axioma de separacin obliga a quelos conjuntos estn formados de elementos de conjuntos ya construdos.Hay que observar que ms que un slo axioma es un esquema de axiomas,ya que tenemos un axioma para cada predicado.

4.2. Axiomas del Par, de la Unin y de las Partes

Definicin

Axioma del Par: ABC(x(x C x = A x = B) . Expresa quesi A y B son conjuntos entonces la clase {A,B} es un conjunto.

En particular, si A es un conjunto entonces la clase {A} es un conjunto (porextensionalidad). Este axioma asegura que las colecciones de conjuntos son con-juntos.

23

24 CAPTULO 4. PRIMEROS AXIOMAS

Axioma de la Unin: AB(x(x B y(y A x y))). Expresaque si A es un conjunto la reunin de A,

[A, es un conjunto.

Axioma de las Partes: AB(x(x B x A)) . Si A es un conjunto,entonces las partes de A, PA, es un conjunto.

Teorema A partir de los cinco primeros axiomas se obtienen los resultadossiguientes que nos garantizan que las clases definidas con anteridad son conjun-tos.

1. Si A y B son conjuntos entonces AB, AB, AB, {A,B} , PA,[

A,\A son conjuntos. Es consecuencia inmediata de los axiomas.

2. Si A y B son conjuntos entonces A B es un conjunto. Es consecuenciade que AB P(P(AB) y de los axiomas de Reunin y de las Partes.

3. Como consecuencia de 2 las relaciones obtenidas a partir de productoscartesianos tambin sern conjuntos.

Lo que no se puede deducir a partir de los axiomas anteriores es que laimagen por una funcin de un conjunto sea un conjunto. Necesitamos un nuevoaxioma para ello.

4.3. Axioma de ReemplazamientoAxioma de Reemplazamiento:

x!y(x, y) ABy(y B x(x A (x, y))

Expresa que la imagen de un conjunto por una funcin es un conjunto.

Captulo 5

Construccin de losOrdinales

5.1. Buenos rdenes e induccin

Se ha visto que en un conjunto bien ordenado todos los subconjuntos novacos tienen un primer elemento. El teorema de induccin es una consecuenciade esta importante propiedad, a continuacin lo enunciaremos para conjuntosbien ordenados arbitrarios y veremos tambin versiones del teorema de induccinpara el conjunto de los nmeros naturales.Lo que hace que funcione el principio de induccin matemtica

[P(0)&n(P(n) P(n+ 1)) nP(n)]

es el buen orden de los naturales.Supongamos que no todos los naturales tienen la propiedad P;es decir,

{n | P(n)} 6= .

Por el buen orden de los naturales habra un primer elemento de este con-junto; es decir habra un m para el que valdra P(m) pero tambin, por ser mel primer elemento, valdra P(m 1).Esto es justamente lo que queda excludo en la prueba por induccin; por

ello demostramos

n(P(n) P(n+ 1))

Se puede extender este mtodo para que sirva no slo con los conjuntosnumerables, sino tambin con los transfinitos (supernumerables)? La respuestaes afirmativa, lo veremos ahora.

25

26 CAPTULO 5. CONSTRUCCIN DE LOS ORDINALES

5.1.1. Induccin en un conjunto bien ordenado

Teorema de Induccin Sea hX,i un conjunto bien ordenado. Y sea E Xtal que:

1. el primer elemento de X es elemento de E.

2. para cada x X, si y(y < x y E), entonces x E.

entonces E = X

5.1.2. Induccin en el conjunto de los nmeros naturales

Llamamos al conjunto de los nmeros naturales con su ordenacin habit-ual. es un conjunto bien ordenado y por tanto vale el teorema de induccin

Teorema de Induccin para (1) Induccin fuerte.Sea X tal que (n )(n X n X), entonces X = (2) Induccin dbil.Sea X tal que(i) 0 X(ii) (n )(n X (n+ 1) X)

entonces X =

(3) Expresin de la induccin dbil mediante frmulas.Sea P(x) un predicado o propiedad del lenguaje de la teora de conjuntos es-pecfica para los nmeros naturales . Si se satisface:(i) P(0)(ii) (n )(P(n) P(n+ 1))

entonces (n )(P(n))

(4) Expresin generalizada de la induccin dbil mediante frmulas.Sea P(x) un predicado o propiedad del lenguaje de la teora de conjuntos es-pecfica para los nmeros naturales . Si se satisface:(i) P(n0) para un cierto nmero natural n0.(ii) (n n0)(P(n) P(n+ 1))

entonces (n n0)P(n)

Demostracin de (4): (4) Es consecuencia directa del teorema de induccinen conjuntos bien ordenados y el hecho de que {n/ n < n0} es un conjuntobien ordenado cuyo primer elemento es n0.

5.2. BUENOS RDENES Y ORDINALES 27

5.2. Buenos rdenes y ordinales

5.2.1. Comparacin de conjuntos bien ordenados: Isomor-fismos

Definicin Sean hX,i y hX 0,0i dos conjuntos bien ordenados. f : X X 0 es un isomorfismo de rdenes si y slo si(i) f es biyectiva(ii) x < y f(x)

28 CAPTULO 5. CONSTRUCCIN DE LOS ORDINALES

3. Sea X un ordinal. Sea Y X. Si Y es un ordinal, entonces Y = Xa, paraalgn a X.

4. Si X e Y son ordinales, entonces X Y es un ordinal.5. Sean X e Y ordinales. Si X 6= Y , entonces uno es un segmento del otro.6. Si X e Y son ordinales isomorfos, entonces X = Y

7. Sea hX,i un conjunto bien ordenado tal que para cada a X, Xa esisomorfo a un ordinal. Entonces X es isomorfo a un ordinal.

8. Cada conjunto bien ordenado es isomorfo a un nico ordinal.

5.3. Observaciones acerca de los ordinalesLos Ordinales miden la longitud de los conjuntos bien ordenados

Teorema Si hX,i es un conjunto bien ordenado, Ord(X) es el nico ordinalisomorfo a X.Por otra parte, si X e Y son conjuntos bien ordenados, X = Y syss Ord(X) =Ord(Y )

Esta unicidad nos permite usar a los ordinales como vara de medir con-juntos bien ordenados; es decir, Ord(X) es la longitud de X.

Inclusin (y pertenencia) bien-ordena a los ordinales

Orden lineal Hemos demostrado que ordena linealmente a los ordinales.De hecho, tambin , pues si X e Y son ordinales,

X Y si y slo si X = Ya(para algn a Y )

si y slo si X = a (pues Ya = a)

si y slo si X Y (pues a Y )Por consiguiente, la relacin coincide en los ordinales con la relacin

Nota importante: No decimos que x y y x y se den por las mismasrazones, ni tan siquiera en los ordinales. Lo que sucede es que siempre tenemossituaciones como sta:

x = {, {}}y = {, {} , {, {}}}

5.3. OBSERVACIONES ACERCA DE LOS ORDINALES 29

Aqu x y porque

{, {}} {, {} , {, {}}}

Mientras que x y porque

{, {} , {, {}}}{} {, {} , {, {}}}

Buen orden La relacin sobre los ordinales no slo es un orden lineal,tambin es un buen orden.

Demostracin: Supongamos que los ordinales no estuvieran bien ordenadosmediante , habiendo una sucesin

{X(n)}n=0tal que

X(0) X(1) X(2) ...

Luego, para cada n > 0 se cumple, X(n) X(0).Por lo tanto, para cada n > 0 se cumple, X(n) X(0).As que

{X(n+ 1)}n=0

es una sucesin decreciente infinita de elementos de X(0).

Pero X(0) es un ordinal, est bien ordenado mediante y por lo tanto nopuede haber tales cadenas descendentes infinitas.

Cmo son los ordinales por dentro?

30 CAPTULO 5. CONSTRUCCIN DE LOS ORDINALES

Usaremos letras griegas minsculas para denotar ordinales. Puesto que el or-den es siempre no hace falta especificarlo. Sin embargo, recordaremos siempreque un ordinal no es slo un conjunto, sino un conjunto y un orden.Para denotar el orden de los ordinales se usa indistintamente < ,

o .Puesto que los ordinales miden conjuntos bien ordenados, en particular

medirn conjuntos finitos. Definiremos a los naturales como ordinales finitos.

Cmo es un ordinal?Si es un ordinal, entonces = { | < }

Ordinales finitos

Primer ordinal Denotacin 0{0} = {} Segundo ordinal Denotacin 1{0, 1} = {, {}} Tercer ordinal Denotacin 2...

......

...{0, 1, 2, ..., n 1} Ordinal ensimo+1 Denotacin n...

......

...

Cal es el primer ordinal infinito? El primer ordinal infinito es el de losnaturales {0, 1, 2, ..., n, n+ 1, ...} =

Y luego? Se forma su siguiente {0, 1, 2, ..., n 1, ..., } = + 1

Procedimiento general (i) Si es un ordinal, su siguiente es {} =+1. Un ordinal que es el siguiente de otro ordinal se denomina ordinal sucesor

(ii) Si 0, 1, 2, ..., n, n+ 1, ..., , + 1, ..., , + 1, ...son los elementos de un segmento inicial de un ordinal, sin elemento ltimo

se forma el ordinal

{0, 1, 2, ..., n, n+ 1, ..., , + 1, ..., , + 1, ...}Puesto que un ordinal de esta ndole carece de elemento ltimo, se le llama

ordinal lmite. As que es un ordinal lmite.

Captulo 6

La Jerarqua de Zermelo

6.1. Construccin de la Jerarqua

Ahora podemos presentar con rigor la jerarqua de conjuntos de ZermeloFraenkel, y responder a las preguntas que nos hicimos cuando hablbamos delUniverso matemtico y se propona la construccin de los conjuntos de la teorapartiendo de una coleccin inicial M0 de objetos dados y construyendo a con-tinuacin una coleccin M1 de objetos de M0, despus M2 de objetos de M0 yde M1 y as sucesivamente.

1. Cal ser nuestra coleccin de partida, M0?.Partimos de M0 = , el nivel inicial. Lo llamamos V0 =

2. Qu conjuntos de objetos de niveles inferiores se toman para formarnuevos niveles en la jerarqua?Supngase que hemos definido ya V. Qu conjuntos de miembros de Vtomaremos para formar V+1?. Consideraremos P(V) el conjunto poten-cia o de las partes de V, cuyos elementos son los subconjuntos de V. Portanto, dado el nivel V (siendo ordinal sucesor) formamos

V+1 = P(V)

Y cundo es un ordinal lmite:

V =[

32 CAPTULO 6. LA JERARQUA DE ZERMELO

conjuntos. Para cada ordinal debe haber un nivel V. Sus miembros sonconjuntos cuyos elementos estn en los niveles previos; en

[

6.2. AXIOMAS INVOLUCRADOS EN LACONSTRUCCINDE LA JERARQUA33

1. Tomamos como operacin bsica la de partes, Px. El axioma de las partesde un conjunto

AB(x(x B y(y x y A))

permite formar un conjunto con todos los subconjuntos de uno dado, A.Este axioma nos permite pasar de V a V+1, haciendo V+1 = P(V).

Qu sucede cuando es un ordinal lmite?

2. Debemos poder formar la unin de colecciones de conjuntos. El axioma dela unin,

AB(x(x B y(y A x y))

dice que dado un conjunto A hay un conjunto cuyos elementos son los el-ementos de los elementos de A. El axioma de la unin nos permite formarV, cuando es un ordinal lmite, haciendo

V =[

34 CAPTULO 6. LA JERARQUA DE ZERMELO

Los dos ltimos axiomas, afirman la existencia de ciertos conjuntos. Estocontrasta con el resto de los axiomas, que proporcionan reglas mediante lascuales se forman conjuntos a partir de conjuntos existentes. En realidad,el axioma del conjunto vaco no es necesario, pues es demostrable a partirde infinitud y de separacin.Faltan ms axiomas?

6. El axioma de extensionalidad, que usbamos desde el principio en la teorabsica, expresa el criterio fundamental de la teora de conjuntos que diceque identificamos los conjuntos que tienen los mismos elementos. No es-tamos interesados en los predicados que definen a los conjuntos, sino enlos que finalmente caen bajo ellos, los que los cumplen. Por otra parte,el principio de extensionalidad nos permite demostrar la unicidad de losconjuntos cuya existencia garantizan otros axiomas.

AB(x(x A x B) A = B)

Hemos expresado ya que el universo de conjuntos est formado exclusi-vamente por los elementos de los distintos niveles?

V =[

OrdV

En realidad, cuando se tiene el resto de los axiomas (1)-(6) y el axiomade separacin, se puede demostrar que el principio as expresado equivaleal siguiente

7. Axioma de fundacin. Dicho principio dice que es una relacin bien fun-dada. Lo expresamos as:

x(x 6= y(y x y x = ))

Captulo 7

Los Axiomas de Eleccin yConstructibilidad

Los axiomas presentados anteriormente permiten justificar que todos loselementos utilizados en la construccin de la Jerarqua de Conjuntos de ZermeloFraenquel son conjuntos. Esos axiomas y la teora de conjuntos que se deriva deellos se conoce como teora ZF.Existen extensiones de la teora ZF consistentes en aadir uno o varios ax-

iomas a los de esa teora. Entre todas las extensiones slo nos ocuparemos ahorade las que se obtienen con dos axiomas en particular. El axioma de la elecciny el axioma de constructibilidad.

7.1. Axioma de la eleccin

Axioma de la eleccin: A( / A xy(x A y A x 6= y x y =) Bz(z A !v(v z B)))

Este axioma asegura la existencia de un conjunto B obtenido a partir de unacoleccin cualquiera A de conjuntos no vacos y disjuntos dos a dos. De cadaconjunto de A elije un nico conjunto para poner en B.Este axioma no se puede demostrar en la teora ZF, y si queremos asegurar

la existencia de las llamadas funciones de eleccin o de la buena ordenacin decualquier conjunto debe aadirse a los dems axiomas. La teora de conjuntosaxiomtica resultante se conoce con las siglas ZFC (C del ingls Choice), y esla que en realidad se conoce como teora de Zermelo Fraenkel.Si ZFC es consistente todo lo que se demuestre en esta teora ser verdadero.

Sin embargo, como consecuencia del teorema de Gdel no hay esperanza depoder demostrar la consistencia de la teora ZFC, ya que para demostrar suconsistencia tendramos que hacer la prueba en una teora ms fuerte que ZFC,cuya consistencia sera an ms difcil de demostrar. Otro teorema de Gdel

35

36CAPTULO 7. LOS AXIOMAS DE ELECCIN Y CONSTRUCTIBILIDAD

muestra que si ZFC fuera inconsistente tambin lo sera ZF. Por tanto slo esnecesario suponer que ZF es consistente para asegurar tambin que ZFC lo es.

7.1.1. Otras formulaciones del axioma de eleccin

De entre las numerosas formulaciones del axioma de eleccin, cabe destacarlas siguientes:

1. Para cada relacin R hay una funcin f tal que f R y Dom(f) =Dom(R).Esta formuacin la usamos para demostrar el criterio de exhaustividadpara funciones. A saber, que una funcin f : A B es exhaustiva si yslo si hay una funcin g : B A que compuesta con ella produce laidentidad sobre B.

2. El producto cartesiano de conjuntos no vacos es no vaco.

3. Para cada conjunto A hay una funcin f (llamada funcin de eleccin) talque el dominio de f es el conjunto de los subconjuntos no vacos de A ytal que f(B) B para cada B A.

4. Dado un conjunto A de conjuntos no vacos y disjuntos, hay un conjuntoque tiene un elemento de cada conjunto de A. (Russell pone el famoso ejem-plo de los calcetines. Dada una coleccin infinita de pares de calcetines,el axioma de eleccin nos permite elegir uno de cada par. El problemase plantea con los calcetines, pero no con los zapatos, podemos elegir elizquierdo de cada par.)

7.1.2. Importancia del Axioma de Eleccin

1. Equivale al principio del buen orden. AR(R bien ordena A).Este axioma asegura que es posible definir un buen orden en todo conjunto,y como todo conjunto bien ordenado es isomorfo a un ordinal, ser posiblemedir los conjuntos usando los ordinales.

2. Implica el Lema de Zorn. Todo conjunto ordenado en el que cada cadenaposea cota superior, tiene elemento maximal.

3. El Lema de Zorn implica el Principio de Hausdorff. En todo conjuntoordenado cada cadena puede extenderse a una cadena maximal

7.2. Axioma de Constructibilidad

Cuando se defini la jerarqua de conjuntos de Zermelo Fraenkel {Va/ Ord}usamos como nocin base la del conjunto de las partes de un conjunto

7.2. AXIOMA DE CONSTRUCTIBILIDAD 37

V+1 = P(V)

esto es, V+1 es el conjunto de todos los subconjuntos de V. Sin embargola nocin de subconjunto no fue definida en realidad y cuando nos hacemospreguntas como qu es un subconjunto arbitrario del conjunto de los nmerosnaturales y cuntos de ellos hay, no es posible responder sin determinar lo quese entiende por subconjunto. Podemos tomar como nocin de conjunto la deuna coleccin descriptible por una frmula expresada en el lenguaje formal dela tera de conjuntos. De esta manera obtendremos los conjuntos necesariosen matemticas, excepto quizs los conjuntos indescriptibles provenientes delaxioma de eleccin. ?? se puede redefinir la jerarqua de conjuntos substituyendola nocin de conjunto de las partes de un conjunto por la de conjunto descriptiblede las partes de un conjunto. Indicaremos el nivel Ord de la jerarqua porla nueva notacin L.

L0 = L+1 =todas las colecciones de elementos de L que son describibles con

frmulas del lenguaje de la teora de conjuntos)Y cundo es un ordinal lmite:

L+1 =[

38CAPTULO 7. LOS AXIOMAS DE ELECCIN Y CONSTRUCTIBILIDAD

lo hacen, aunque la jerarqua de conjuntos ms aceptada es V y el axioma deConstructibidad muy discutido, como tambin lo sigue siendo el de la Eleccinen muchos autores.

Captulo 8

Ejercicios

8.1. Igualdad, Inclusin y Conjunto vacoDemustrese los siguientes teoremas de ZF.

1. AB ((A B) (B A))2. A ((A ) (A = ))3. AB ((A B) (B A))4. AB ((A B) ((B A)))5. ABC (((A B) (B C)) (A C))6. A ((A A))

8.2. Operaciones: Algebra de conjuntosPrubese las siguientes propiedades en ZF.

1. ABC (((A C) (B C)) ((A B) C)))2. ABC (((C A) (C B)) (C (A B)))3. ABC ((A B) C = (A C) (B C))4. ABC ((A B) C = (A C) (B C))5. AB ((AB) B = A B = A (B A))6. AB ((AB) B = )7. ABC (A (B C) = (AB) (A C))8. ABC ((A B) C = (A C) (B C))

39

40 CAPTULO 8. EJERCICIOS

9. AB ((A B) (A (B A) = B))10. AB (A B = A (AB))

8.3. Clases Unitarias, Pares y DadasDemustrese que los siguientes axiomas se derivan de los axiomas.

1. xy (({x} {x, y}) ({x} = y))2. Definamos h[x, y]i = {{x, } , {y, {}}}. Demostrad lo siguiente: xyzv(h[x, y]i =

h[z, v]i (x = z) (y = v))3. Es siempre verdad que si {x, y, z} = {x, y.v} entonces z = v?

8.4. Conjunto Potencia (o Conjunto de las Partesde un Conjunto)

1. AB ((A B) (PA PB))2. P = {}3. P {} = { {}}4. PP = { {}}5. AB (P(AB) ((PAPB) {}))6. A ({, {}} PPPA)7. AB ((PA = PB) (A = B))8. xyA ((x A y A) (hx, yi PPA))

8.5. Gran Unin y Gran InterseccinDemustrese los siguientes teoremas.

1. Axy (({{x} , {x, y}} A) (({x} , {x, y} [A) (x, y

[[A)))

2. xy (\{{x} , {x, y}} = {x})

3. xy ([\

{{x} , {x, y}} = x)

4. xy (\[

{{x} , {x, y}} = x y)

5. xy (\hx, yi = {x})

8.6. PRODUCTO CARTESIANO 41

6. xy ([\

hx, yi = x)

7. xy (\S hx, yi = x y)

8. AB ((A B) ([

A [

B))

9. AB ((A ((A A) (A B)) ([A B))

10. A (A P([

A))

11. AB ((A B) (PA PP[

B))

12. AB ((B 6= ) (A (\B) =

\{A x | x B}))

8.6. Producto Cartesiano

Prubese que son verdaderas las propiedades siguientes en la teora ZF.

1. ABC (A (B C) 6= (AB) (A C))2. ABC (((AB = A C) (A 6= )) (B = C))

3. AB (A[B =

[{A z | z B})

4. AB (AB = B A A = B A = B = )

5. AB (A\B =

\{A z | z B})

6. AB ((\(AB) 6= ) (x (A = {x})))

8.7. Relaciones Binarias

Demustrese que las siguientes propiedades sobre relaciones son teoremas deZF.

1. R (((R es una relacin)) (R * Dom RRang R)))2. RS (Dom (R S) 6= (Dom R Dom S))3. RS (Rang (R S) (Rang R Rang S))4. RS (Rang (R S) 6= Rang R Rang S)5. RS (Rang (R S) 6= Rang RRang S)6. RS (Rang (R S) (Rang RRang S))

42 CAPTULO 8. EJERCICIOS

7. RS ((R es relacin S es relacin xy(hx, yi R hx, yi S)) R = S)

8. RS (R es relacin S es relacin xy(hx, yi R hx, yi S)) R S)

8.8. Relacin Inversa, Producto Relativo y Re-striccin

1. AB ((A B)1 = A1 B1)2. AB ((A B)1 = A1 B1)3. AB ((AB)1 = B A)4. AB (A/B es una relacin)5. AB (Dom(A/B) Dom A)6. ABCD ( ((A B) (C D)) (A/C B/D))7. ABC (A/(B C) = (A/B) (A/C))8. ABC (A/(B C) (A/B) (A/C))9. ABC (A/(B C) 6= (A/B) (A/C))10. ABC ( (A/(B C)) ((A/B) (A/C)) )11. AR (R A = (R (ARec R)) )12. ABR ( (A B) ((R A) (R B)) )13. ABR ( R (A B) = ((R A) (R B)) )14. ABR ( R (A B) = ((R A) (R B)) )15. RSA ( (R/S) A = ((R A)/S) )16. ABR ( ((R A) (R B)) (A B) )

8.9. Imagen bajo una Relacin y Relacin deIdentidad

1. RAB ((A B) (R [A] R [B]))2. RAB ((R [A] B) (R A R1 [B])3. RA (R1 [A] = Dom (R (Dom (RA)))4. R ( (R es una relacin ) ((IDom R)/R = R))5. Dom (IA = A = Rang IA = Camp IA)

8.10. PROPIEDADES DE CIERTAS RELACIONES 43

8.10. Propiedades de ciertas relaciones1. R ((R es reflexiva ) (ICamp R R))2. R ((R es simtrica ) ((R1)1 = R1))3. R ((R es transitiva ) (R/R R))4. R ((R es irreflexiva ) (R ICamp R = ))5. R ((R es asimtrica ) (R R1 = ))6. R ((R es antisimtrica ) (R R1 IDom R))7. R ((R esta conectada ) ( ((Camp R Camp R) ICamp R)

(R R1) ) )8. R ((R esta fuertemente conectada ) ( (Camp R Camp R)

(R R1) ) )9. R ((R es euclidea ) ((R1/R) R))10. R ((R es incestuosa ) ((R1/R) (R/R1)))

8.11. Relaciones de EquivalenciaPrubese que las siguientes propiedades sobre relaciones de equivalencia son

teoremas de ZF:

1. R ((R es una relacin de equivalencia) ((xy(x, y CampR) (([x]R = [y]R) ([x]R [y]R = ))))

2. R ((R es una relacin de equivalencia ) ((R/R1) = R))

8.12. Relaciones de Orden1. R ((R es un orden lineal ) (R1 es un orden lineal))2. Sea hA,i un conjunto parcialmente ordenado. Existe un conjunto Y de

subconjuntos de A tal que hA,i = hY,i

8.13. Funciones, ComposicinDemustrese los siguientes teoremas sobre funcciones en ZF.

1. es una funcin2. fg ((f es funcin g es funcin Domf = Domg x((x

Domf) (f(x) = g(x))) f = g)

44 CAPTULO 8. EJERCICIOS

3. fgA (((f g) A) = (f (g A)))4. f ( (f es funcin f1 es funcin ) (f f1 = IDom f1))5. f ( (f es funcin f1 es funcin ) ((x((x Domf))

((f1 f)(x) = x)))6. fgh ((f g) h = f (g h))7. fg ((f es inyectiva g f) (g es inyectiva))8. fg ((f es inyectiva g es inyectiva Dom f Dom g = Rang f

Rang g = ) (f g es inyectiva))9. fg ((f es inyectiva g es inyectiva ) (f g es inyectiva))

8.14. Funciones de A en BDemostrad lo siguiente:

1. f ((f es funcin A Domf) (f A es funcin f : A f [A] esexhaustiva))

2. f ((f : A B A 6= ) ( (f es inyectiva ) (g (g : B A g f = IA))))

3. f ((f : A B A 6= ) ( (f es exhaustiva ) (g (g : B A f g = IB))))

8.15. InduccinResulvanse los siguients ejercicios sobre induccun:

Ejercicio 1. Hgase una conjetura para responder a las siguientes preguntas eintntese demostrarla por induccin.(a) Qu nmero es mayor : 2n1 o n! ?(b) Qu nmero es mayor: 2n o n2 ?(c) Cuntos subconjuntos de 2 elementos tiene un conjunto de n 2 ele-

mentos?(d) Cuntos subconjuntos de 3 elementos tiene un conjunto de n 3 ele-

mentos?(e) Cuntos subconjuntos de k elementos tiene un conjunto de n k ele-

mentos?

Indicacin: Comprubese para cada conjetura cul es la situcin para n=1,n=2, n=3, n=4, n=5, n=6 o incluso para algn valor ms si fuera necesario.Una vez establecida la conjuetura la demostracin por induccin tiene dos fases:

8.15. INDUCCIN 45

(i) probar que la conjetura es vlida para el menor de los nmeros naturales n0 aque hace referencia (en (a) n0 = 1,(b) y (c) n0 = 0, pero en (c) n0 = 2, en (d) esn0 = 3 y en (e) es n0 = k), esta fase habr sido ya probada en las comprobacionespara enunciar la conjetura; (ii) suponiendo que la conjetura es cierta para unnmero natural arbitrario p n0 probar que tambin lo es para p+ 1.

Ejemplo: (a) Primero comprobamos para los valores de n menores cul es lasituacin respecto a la pregunta que nos hacemos:Para n = 1 : por un lado 2n1 = 20 = 1 por otro lado n! = 1! = 1.Para n = 2 : por un lado 2n1 = 21 = 2 por otro lado n! = 2! = 2 1 = 2.Para n = 3 : por un lado 2n1 = 22 = 4 por otro lado n! = 3! = 3 2 1 = 6Para n = 4 : por un lado 2n1 = 23 = 2 por otro lado n! = 4! = 4321 = 24Por tanto nuestra conjetura es P(n) = 2n1 n! para todo n 1.Ahora la demostramos por induccin:(i) La conjetura se cumple para n0 = 1, esto es P(1) es cierta.(ii) Suponemos que la conjeura es cierta para un cierto p 1, esto es P(p) =

2p1 p! es cierta (hiptesis de induccin). Ahora demostraremos que tambinse debe cumplir para p+1 esto es, que P(p+1) = 2(p+1)1 (p+1)! es cierta.Demostracin: 2(p+1)1 = 2p = 2p1 2 p! 2 (usamos que 2p1 p!,

la hiptesis de induccin). Por otro lado p 1 y por tanto p + 1 2, ?? quep! 2 p! (p+ 1) = (p+ 1)!. Como se quera demostrar.Ahora, aplicando el principio de induccin para los nmeros naturales: 2n1

n! para todo n 1

Soluciones: las soluciones a las conjeturas del ejercicio 1 son:(b) 2n n2 para todo nmero natural excepto para n = 3. Aqu podemosdemostrar los casos particulares n = 0, n = 1, n = 2, n = 4 y de mostrar que laconjetura es vlida para n 4 por induccin.(c) Un conjunto de n 2 elementos tiene n(n 1)

2subconjuntos de 2 elementos.

(d) Un conjunto de n 3 elementos tiene n(n 1)(n 2)3!

subconjuntos de 3

elementos.

(e) Un conjunto de n k elementos tiene n(n 1)(n 2) (n k + 1)k!

sub-

conjuntos de k elementos.

Ejercicio 2. Los siguientes resultados de la aritmtica natural son ciertos paratodo n N. Demustrese por induccin.(a) 22n 1 es mltiplo de 3.(b) n2 n es par.(c) n3 n es mltiplo de 6.(d) n5 n es mltiplo de 30.

46 CAPTULO 8. EJERCICIOS

(e) npn es mltiplo de p para todo nmero primo p (Teorema pequeo deFermat).

Ejercicio 3. Demustrese que la expresin de la induccin dbil mediante fr-mulas generalizada (4) es equivalente a:

Sea P(x) un predicado o propiedad del lenguaje de la teora de conjuntos es-pecfica para los nmeros naturales . Si se satisface:(i) P(n0)(ii) (k n0)(P(n0) P(n0 + 1) P(k 1) P(k))

entonces (n n0)P(n).

Indicacin: considrese Q(k) = P(n0) P(n0 + 1) P(k).

Ejercicio 3. Utilcese la forma alternativa del principio de induccin del ejerci-cio anterior para demostrar que todo rbol formado por n aristas y m vrticesverifica: m = n + 1 (tmese n0 = 1). (Un rbol es un conjunto de puntos (losvrtices) unidos por segmentos (las aristas) que no tiene ciclos y de manera quesiempre hay un camino entre dos vrtices).

Solucin: Consideremos P(n) : si un rbol tiene n aristas entonces tiene n+1vrtices. Queremos demostrar que P(n) es cierta para todo n .(i) P(1) es cierto: un rbol con una arista tiene dos vrtices.(ii) Supongamos que P(1),P(2), . . . ,P(k1) son ciertas (hiptesis de induc-

cin). Queremos probar que entonces P(k) tambin es cierta. Consideremos unrbol con k aristas. Si le quitamos una arista cualquiera, obtenemos dos rbolescon k1 y k2 aristas tal que k1 + k2 = k 1 (por tanto con k1, k2 k 1).Aplicando la hiptesis de induccin, los dos rboles ms pequeos tienen k1+1y k2 + 1 vrtices respectivamente. Como al quitar una arista no se ha variadoel nmero de vrtices, el arbol inicial tena k1 +1+ k2 +1 = k+1 vrtices. Portanto P(k) es cierta.Por el principio d induccin, P(n) es cierta para todo n 1.

Ejercicio 5. Considrese la siguiente utilizacin del principio de induccin:Demostraremos por induccin que todo ser humano tiene el mismo nombre.

En particular, probaremos que dada una coleccin de n personas, para cualquiern , todas las personas tienen el mismo nombre.La primera etapa es trivial, porque si n = 1 cualquier persona tiene el mismo

nombre que ella misma.La hiptesis de induccin es que en toda coleccin de k personas, todas tienen

el mismo nombre.Ahora consideremos una coleccin de k + 1 personas. Hacemos que marche

una de estas personas. Por la hiptesis de induccin, las otras k personas tienentodas el mismo nombre. Ahora cambiamos la persona que est fuera por una

8.15. INDUCCIN 47

de estas k personas. Volvemos a obtener un grupo de k personas, que por lahiptesis de induccin, tienen el mismo nombre. Por tanto la persona que acabade entrar se llama igual que el resto. ?? las k + 1 personas tienen el mismonombre.Dnde falla la demostracin?

Solucin: Consideremos la afirmacin P(n) = en toda coleccin de n personas,todas tienen el mismo nombre.- P(1) es cierto (a menos que consideremos que no iene sentido, pero eso no

cambia nada).- Se puede ver fcilmente que P(2) no es cierta.- Tambin escierto que, para k 2, si P(k) es cierta entonces P(k + 1) es

cierta. Esta parte del razonamiento no tiene ningn error. Pero se est suponien-do que hay 2 o ms personas en la sala (es decir que k 2). Por tanto, aunqueP(1) sea cierta, no sirve de nada, poque la induccin debera comenzar a partirde P(2) que no es cierta.

48 CAPTULO 8. EJERCICIOS

Captulo 9

Bibliografa

1. Devlin, K. The Joy of Sets. Springer-Verlag. New York. 1993.

2. Enderton, H. Elements of Set Theory. Academic Press. New York.1977

3. Halmos, P. Naive Set Theory. Springer-Verlag. New York. 1974.

4. Suppes, P. Axiomatic Set Theory. Dover. New York. 1972.

49