Introducción a ZFC

Este post fue publicado originalmente en el blog de libreim el 25 de marzo de 2017.

A principios del siglo XX las matemáticas sufrieron una crisis fundacional: los principios que se consideraban básicos para la deducción de las teorías matemáticas daban lugar a paradojas y los matemáticos de la época se embarcaron en la creación de un sistema axiomático que pudiera formalizar todos los teoremas de la época sin dar lugar a estas paradojas.

Una de las posibles soluciones son las teorías axiomáticas de conjuntos, de entre las cuales la más utilizada actualmente es ZFC (la teoría de Zermelo-Fraenkel junto con el axioma de elección)¹.

En este artículo exponemos los axiomas de esta teoría y la comparamos con otras teorías de conjuntos (y de clases). Se incluyen también algunos ejercicios.

El lenguaje

Second order logic is just set theory in disguise - W.V.O. Quine

Para formalizar una teoría axiomática de cualquier tipo necesitamos un lenguaje en el cual expresar los axiomas, pero el lenguaje natural produce paradojas. Para solucionar este problema utilizaremos un lenguaje lógico.

Hay muchas otras posibles elecciones con respecto a qué lógica utilizar: por ejemplo algunas teorías axiomáticas de conjuntos utilizan lógicas no clásicas. Podríamos también considerar las lógicas de orden superior pero por razones históricas y filosóficas y por sus propiedades metalógicas formularemos la teoría en lógica de primer orden.

La lógica de primer orden

La lógica de primer orden consta de dos tipos de símbolos: los símbolos lógicos y los no-lógicos, que forman fórmulas a partir de una serie de reglas. No es el objetivo de este post explicar en detalle la lógica de primer orden y basta con que seas capaz de leer fórmulas como \(\forall x \operatorname{Cuervo}(x) \implies \operatorname{Negro}(x)\) (todos los cuervos son negros) ².

Los símbolos lógicos de nuestra teoría pueden reducirse a una colección de conectivas lógicas funcionalmente completas (cómo mínimo la operación NAND o más comúnmente la conjunción, disyunción, negación, implicación y bicondicional) así como al menos un cuantificador (para todo \(\forall\) o existe \(\exists\)). Contamos además con una cantidad infinita de variables (basta con una cantidad numerable) para escribir nuestras fórmulas.

Contaremos además como único símbolo no-lógico a la relación de pertenencia \(\in(\cdot,\cdot)\) que escribiremos \(A \in B\) y leemos A pertenece a B.

Nuestra lógica también incluye el símbolo de igualdad \(=\) y sus axiomas, que incluimos a continuación por completitud. Los 3 primeros axiomas nos indican que la igualdad es una relación de equivalencia. El último es un esquema de axioma (una colección infinita de axiomas que depende de una fórmula) que caracteriza la igualdad (conocido como identidad de los indiscernibles).

1. Reflexividad \(\forall x \; x = x\)
2. Simetría \(\forall x \forall y \; x = y \implies y = x\)
3. Transitividad \(\forall x \forall y \forall z \; x = y \wedge y = z \implies x = z\)
4. Sustitución Si \(\varphi\) es una fórmula y \(\varphi'\) es la fórmula que resulta de sustituir todas las ocurrencias libres de \(x\) por \(y\) se verifica: \(\forall x \forall y \; x = y \implies (\varphi \implies \varphi')\)

Una nota sobre los cuantificadores

Cuando se escriben fórmulas matemáticas habitualmente omitimos los cuantificadores o utilizamos cuantificadores delimitados:

que leemos para todo \(x\) en \(A\) se verifica \(\varphi(x)\) y existe un \(x\) en \(A\) tal que \(\varphi(x)\) respectivamente.

En los axiomas de la teoría de conjuntos sin embargo los cuantificadores no están delimitados, por lo que debemos expresarlo con una fórmula equivalente:

es decir para todo \(x\), si \(x\) pertenece a \(A\) entonces \(\varphi(x)\) y existe un \(x\) tal que \(x\) pertenece a \(A\) y \(\varphi(x)\). En este caso \(x\) es ahora cualquier conjunto.³

El dominio de discurso

In every discourse, whether of the mind conversing with its own thoughts, or of the individual in his intercourse with others, there is an assumed or expressed limit within which the subjects of its operation are confined. - Boole, 1854

Las matemáticas tratan de objetos muy dispares como pueden ser los números, las funciones, los espacios topológicos, las máquinas de Turing o las categorías. Una teoría fundacional debería ser capaz de expresar todos estos objetos utilizando las mismas piezas. En algunos casos la transformación a conjuntos es clara (los espacios topológicos o las máquinas de Turing suelen definirse de forma explícita como conjuntos) pero en otros casos (los números o las funciones) esa transformación no suele realizarse de forma explícita cuando trabajamos con estos. ¿Es posible expresar cualquier objeto matemático en forma de conjuntos o necesitamos además otros tipos de objetos?

En esta sección realizamos construcciones explícitas de estos objetos matemáticos y discutimos los límites de ZFC para describir todas las matemáticas.

Los números son conjuntos

Algunas teorías como NFU o KPU admiten urelementos: elementos que no son conjuntos pero pueden ser elementos de conjuntos (esto es, sólo pueden aparecer en el lado izquierdo de \(\in\)) y así lo hacía la teoría de Zermelo de 1908 en la que se basa ZFC. Esta podría ser una opción para incluir los números en nuestra teoría, sin embargo las matemáticas pueden basarse exclusivamente en conjuntos hereditarios⁴.

Un conjunto se dice hereditario si todos sus elementos son conjuntos hereditarios. Como verdad vacua podemos demostrar que el conjunto vacío \(\varnothing\) es un conjunto hereditario y por tanto (como veremos a continuación) también lo serán \(\{\varnothing\}, \{\varnothing, \{\varnothing\}\},\{\{\varnothing\}\}, \dots\). Combinando conjuntos hereditarios a partir de los axiomas podemos crear una cantidad arbitrariamente grande de conjuntos y por tanto nos basta nombrar de forma especial algunos de estos conjuntos para obtener nuestra teoría.

La forma habitual de proceder es definir primero los números naturales siguiendo los ordinales de Von Neumann:

De esta forma obtenemos los números naturales⁵. A continuación para obtener los enteros, racionales, reales y complejos podemos definirlos mediante relaciones de equivalencia adecuadas. Puedes encontrar una posible construcción explícita en esta pregunta de Stack Exchange.

Las funciones son conjuntos

Una función es una operación que relaciona un elemento o tupla de elementos de su dominio con un único elemento de su codominio. Para formalizar este concepto podemos identificar (casi) todas las funciones como un conjunto: su grafo.

De esta forma una aplicación \(f: A \to B\) puede verse como una 3-upla \((A,B,G)\) con \(G = \{(a,b) \in A \times B \;:\; b = f(a) \}\) ⁶.

No todas las funciones pueden expresarse como conjuntos: las operaciones clásicas sobre conjuntos (unión, intersección, conjunto potencia) así como la aplicación que devuelve la cardinalidad de un conjunto son aplicaciones que tienen como dominio todos los conjuntos, pero en ZFC no existe el conjunto de todos los conjuntos. Podemos ver a estas “funciones” simplemente como notación.

Algunas cosas que no son conjuntos

En algunas partes de las matemáticas como la teoría de categorías resulta útil con frecuencia hablar de todos los conjuntos a la vez (por ejemplo cuando queremos hablar de los objetos de la categoría \(\texttt{Set}\)) pero se nos presenta el problema de que (en ZFC) no existe el conjunto universal (el conjunto de todos los conjuntos). Para resolver este problema existen 3 opciones.

En primer lugar podríamos utilizar una teoría axiomática distinta que incluyera la clase de todos los conjuntos como NBG. Esta teoría nos permite utilizar todo lo que conocemos de ZFC añadiendo además nuevos objetos que nos permiten hablar de colecciones más grandes sin inducir paradojas.

Otra opción es utilizar una teoría como la teoría de Tarski-Grothendieck que incluye conjuntos que, si bien no son el conjunto de todos los conjuntos sí que comparten muchas de sus propiedades.

Por último si queremos mantenernos en ZFC podemos introducir una nueva notación para hablar de clases: si \(C\) es una clase definida por una propiedad \(P\) introducimos el símbolo \(\in C\) como un predicado que indica … tiene la propiedad P. De esta forma podemos utilizar una notación parecida a la de los conjuntos para hablar de una cantidad reducida de clases (aquellas definibles mediante una propiedad).

Los axiomas

La teoría axiomática de conjuntos de ZFC es una extensión de la teoría de conjuntos de Zermelo, descrita a principios del siglo XX como respuesta a las paradojas de la teoría de conjuntos informal. Aunque existen corrientes filosóficas y lógicas que permiten la existencia de contradicciones, las reglas de inferencia de la lógica clásica hacen que si un sistema axiomático no es consistente (tiene contradicciones) entonces podamos demostrar cualquier cosa. Por tanto necesitamos establecer una teoría que no tenga esas contradicciones.

La más famosa de las paradojas de la teoría de conjuntos informal es la paradoja de Russell: Si un barbero afeita a todos los que no se afeitan a sí mismos, ¿se afeita a sí mismo?. En términos de la teoría de conjuntos informal se traduce en:

Sea \(R = \{x \;:\; x \notin x\}\). Entonces \(R \in R\) si y sólo si \(R \notin R\)

Otras paradojas que impulsaron la creación de esta teoría son la paradoja de Cantor (no existe el conjunto de todos los cardinales) y la paradoja de Burali-Fort (no existe el conjunto de todos los ordinales).

Para resolver estas paradojas necesitamos especificar las reglas de formación de los conjuntos de tal manera que sean suficientemente fuertes para describir todas las matemáticas pero no lleven a contradicción. En el caso de ZFC estas reglas son iterativas: construiremos conjuntos más complejos a partir del conjunto vacío formando el universo de von Neumann. A continuación presentamos estas reglas (los axiomas) siguiendo la descripción de Kunen (1980).

Existencia

En la mayor parte de las definiciones de la lógica de primer orden se asume que el dominio de discurso no es vacío: si lo fuera muchas de las reglas de inferencia y teoremas lógicos que se utilizan normalmente no serían válidos en general. Por completitud añadimos este axioma que nos indica que existe un conjunto ⁷.

Extensionalidad

El axioma de extensionalidad nos indica que dos conjuntos son iguales si tienen los mismos elementos. Es decir, al definir un conjunto sólo importan sus elementos, pero no el orden o el número de repeticiones de cada elemento: \(\{2,2,3,1\} = \{1,2,3\}\)

Comprensión

Si \(\varphi(x)\) es una fórmula en la que \(y\) no es una variable libre se verifica

Como vimos en la primera sección la lógica empleada para describir ZFC es la lógica de primer orden, que sólo permite utilizar cuantificadores sobre nuestro dominio de discurso: los conjuntos. Por esta razón cuando queremos hablar de algo que se cumple para todas las fórmulas necesitamos incluir esquemas de axioma: un conjunto de axiomas parametrizados por las fórmulas⁸.

Obtenemos así una cantidad infinita (pero computable) de axiomas⁹. Estos axiomas nos indican que para cada \(z\) y cada propiedad \(\varphi\) los elementos de \(z\) que cumplen \(\varphi\) forman un conjunto. Esto justifica la notación \(\{x \in z \;:\; \varphi(x)\}\). Tienen sentido entonces definiciones como \(\mathbb{R}^+ = \{x \in \mathbb{R} \;:\; x > 0\}\), pero no \(\{x : x = x\}\) (no hay \(z\)) o conjuntos autorreferentes como \(Y = \{x : x \notin Y\}\) (\(y\) es una variable libre en \(\varphi\)).

Diferentes teorías axiomáticas de conjuntos han tenido históricamente esquemas de axioma de comprensión con distintas restricciones: el primero de ellos, propuesto por Frege, es el esquema de axioma de comprensión no restringido: Para cualquier fórmula \(\varphi\):

Este axioma lleva a la paradoja de Russell y por esta razón se restringe el esquema de axioma para definir sólo subconjuntos. Otra opción es restringir la forma de la fórmula \(\varphi\) de manera que esté estratificada. Esta es la opción que adopta NF y que permite la construcción del conjunto universal (pero NF tiene otras propiedades poco deseables: es incompatible con el axioma de elección). Puedes leer más sobre otras posibles formas del esquema de axioma de comprensión (como la de la teoría de conjuntos constructiva, que sólo utiliza cuantificadores delimitados) en nLab.

Par

Este axioma justifica la expresión de conjuntos por enumeración: si \(a\) y \(b\) son dos conjuntos también lo será \(\{a,b\}\) (y el axioma de extensionalidad nos asegura además que esta expresión se refiere a un único conjunto). Además, tomando \(a = b\) tenemos que si \(a\) es un conjunto también lo será \(\{a,a\} = \{a\}\) (donde la igualdad se da por el axioma de extensionalidad). Podemos además construir pares definiendo \((a,b) = \{\{a\},\{a,b\}\}\).

El conjunto vacío es el único conjunto cuya existencia podíamos probar hasta el momento: los axiomas de existencia, extensionalidad y comprensión son consistentes con \(\forall y (y = \varnothing)\). Con el axioma del par podemos formar una cantidad infinita de conjuntos: \(\varnothing,\{\varnothing\}, \{\{\varnothing\}\},\dots\) aunque no podemos justificar aún la existencia de ningún conjunto infinito (no sabemos por ejemplo si \(\{\varnothing,\{\varnothing\}, \{\{\varnothing\}\},\dots\}\) es un conjunto).

Unión

Como vimos en la sección del esquema de axioma de comprensión no podemos definir la unión a partir de un predicado ya que necesitaríamos de la existencia del conjunto universal.

Para solucionarlo introducimos entonces el axioma de unión: dada cualquier colección de conjuntos \(\mathcal{F} = \{A_{\lambda}\}\_{\Lambda}\) existe un conjunto \(A\), que tiene todos los elementos de los \(A\_\lambda\) (es decir, si \(x \in A\_\lambda\), entonces \(x \in A\)). Definimos a partir de este conjunto la unión de una cantidad arbitaria de estos:

Obteniendo así justificación para las expresiones de la forma \(A \cup B\) (basta tomar \(\mathcal{F} = \{A,B\}\))y uniones de una cantidad arbitraria de conjuntos en general.

Utilizando el axioma de par y el axioma de unión podemos formar conjuntos de cardinalidad finita arbitraria, pero no de cardinalidad infinita.

Infinito

Para este axioma introducimos notación adicional para facilitar su expresión: definimos \(S(x) = x \cup \{x\}\) (la función sucesor)¹⁰. Con esta notación el axioma queda:

Con lo que tenemos nuestro primer conjunto infinito. Podemos demostrar que \(X\) tiene un subconjunto \(\mathbb{N} \subseteq X\) que verifica los axiomas de Peano, tomando \(0 = \varnothing\) y \(S\) la función sucesor.

En sus orígenes este axioma fue controvertido ya que no era considerado una verdad evidente. Aceptar los axiomas de grandes cardinales para nosotros es como aceptar el axioma de infinito para los finitistas.

Potencia

Como hemos hecho en anteriores axiomas definimos nueva notación para simplificar la expresión de los axiomas. En este caso definimos \(x \subseteq y := \forall z (z \in x \implies z \in y)\). El axioma queda:

Este axioma afirma la existencia, para cada conjunto \(x\) de un conjunto \(y\) que habitualmente llamamos conjunto potencia notado \(\mathcal{P}(x)\) que es el conjunto de todos los subconjuntos de \(x\). Este axioma nos permite crear conjuntos de cardinalidad arbitrariamente grande (ya que por el teorema de Cantor, \(|A| < |\mathcal{P}(A)|\)) ¹¹.

Reemplazamiento

Si \(\varphi(x,y)\) es una fórmula en la que \(w\) no es una variable libre, \(z\) es un conjunto y se tiene \(\forall x \; x \in z \implies \exists ! y \; \varphi(x,y)\) se verifica:

La teoría original de Zermelo no incluía este esquema de axioma, que fue incluido por Fraenkel para justificar la existencia de conjuntos como \(\{\mathbb{N}, \mathcal{P}(\mathbb{N}), \mathcal{P}(\mathcal{P}(\mathbb{N})),\dots\}\), útiles en la teoría de los ordinales¹². Este esquema de axioma implica el esquema de axioma de comprensión y el axioma del par. Es poco utilizado: la mayor parte de las matemáticas pueden construirse sin utilizar este axioma. La idea del axioma es que la única cualidad que define si una colección es o no un conjunto es su tamaño.

Este axioma necesita el concepto de predicado funcional: una fórmula \(\varphi(x,y)\) que asocia a cada \(x\) un único \(y\). De esta forma el axioma nos permite reemplazar los \(x\) por su correspondiente \(y\). Esto justifica la notación ocasionalmente utilizada \(\{F(x) \; : \; x \in A\}\)

Cabe destacar que las funciones no son predicados funcionales: los predicados son numerables mientras que las funciones no lo son. De la misma forma los predicados funcionales no son funciones: \(\varphi(x,y) := y = \mathcal{P}(x)\) no puede expresarse como función en ZFC.

Elección

La introducción del axioma de infinito presenta un problema ya que no todas las propiedades que podríamos deducir del resto de axiomas sobre cualquier conjunto finito pueden generalizarse a los conjuntos infinitos. Es el caso del axioma de elección. Para simplificar su exposición asumimos bien definido el concepto de función.

Es decir: Dada una familia de conjuntos no vacios \(\mathcal{F}\) podemos elegir un conjunto de cada uno de ellos. Equivalentemente, el producto cartesiano de una familia de conjuntos no vacíos es no vacío.

El axioma de elección es controvertido para los matemáticos constructivistas porque permite demostrar la existencia de ciertos objetos sin dar una construcción explícita de los mismos. Además permite demostrar resultados chocantes como la paradoja de Banach-Tarski. No obstante es un axioma esencial para la justificación de muchas propiedades matemáticas básicas. Son equivalentes al axioma de elección:

• Toda función sobreyectiva tiene inversa por la derecha
• Todo espacio vectorial tiene una base
• El producto de espacios topológicos compactos es compacto

También es necesario para la demostración de algunos teoremas básicos (aunque no es equivalente a estos):

• La unión de una cantidad numerable de conjuntos numerables es numerable
• Existe un conjunto que no es medible Lebesgue
• Si \(A\) es infinito existe una aplicación inyectiva \(f:\mathbb{N} \to A\)

Fundación

The Axiom of Foundation is, as always in mathematics, totally irrelevant - Kunen (1980)

El axioma de fundación es un axioma poco utilizado que elimina conjuntos de la forma \(x = \{x\}\) o secuencias infinitas de la forma \(\dots \in x_3 \in x_2 \in x_1\). La mayor parte de las matemáticas pueden construirse sin utilizar este axioma, que nos sirve para excluir estos casos patológicos. Es el segundo de los axiomas introducidos por Fraenkel.

Lecturas adicionales

Algunos textos clásicos sobre el tema y páginas en las que puedes leer más sobre el tema son:

• Set Theory: An Introduction to Independence Proofs - Kenneth Kunen
• Foundations of Mathematics - Kenneth Kunen
• Zermelo-Fraenkel set theory
• Von Neumann–Bernays–Gödel set theory
• Naive Set Theory - Halmos