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)1.

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 (todos los cuervos son negros) 2.

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 o existe ). 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 que escribiremos 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
  2. Simetría
  3. Transitividad
  4. Sustitución Si es una fórmula y es la fórmula que resulta de sustituir todas las ocurrencias libres de por se verifica:

Una nota sobre los cuantificadores

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

que leemos para todo en se verifica y existe un en tal que 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 , si pertenece a entonces y existe un tal que pertenece a y . En este caso es ahora cualquier conjunto.3

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 ) 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 hereditarios4.

Un conjunto se dice hereditario si todos sus elementos son conjuntos hereditarios. Como verdad vacua podemos demostrar que el conjunto vacío es un conjunto hereditario y por tanto (como veremos a continuación) también lo serán . 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 naturales5. 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 puede verse como una 3-upla con 6.

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 ) 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 es una clase definida por una propiedad introducimos el símbolo 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 . Entonces si y sólo si

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 7.

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:

Definir y probar que es una relación de orden

Definimos

  • Es reflexiva porque es reflexiva
  • Es transitiva porque es transitiva
  • Es antisimétrica por el axioma de extensionalidad

Comprensión

Si es una fórmula en la que 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órmulas8.

Obtenemos así una cantidad infinita (pero computable) de axiomas9. Estos axiomas nos indican que para cada y cada propiedad los elementos de que cumplen forman un conjunto. Esto justifica la notación . Tienen sentido entonces definiciones como , pero no (no hay ) o conjuntos autorreferentes como ( es una variable libre en ).

Probar que existe el conjunto vacío:

Por el axioma de existencia existe un conjunto .

Definimos entonces . Por el axioma de reflexividad de la igualdad, ningún elemento pertenece a .

Probar que no existe el conjunto universal:

Supongamos que existe .

Definimos entonces . En tal caso podemos aplicar la paradoja de Russell () y tenemos una contradicción.

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 :

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 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.

Prueba que este esquema genera un número de axiomas numerable.

El conjunto de axiomas que genera el esquema de axioma de comprensión es equipotente al conjunto de fórmulas.

Sea . Es claro que es numerable. El conjunto de fórmulas es un subconjunto de:

Este conjunto es una unión numerable de conjuntos numerables (el producto finito de numerables es numerable), por lo que es numerable.

Define la intersección y la diferencia. ¿Puedes definir la unión?

  • Si es un conjunto de conjuntos a los que queremos hacer la intersección y :

  • Aunque el predicado es válido no podemos definir la unión porque no conocemos un conjunto más grande que los conjuntos que queremos unir.

Par

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

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 . Con el axioma del par podemos formar una cantidad infinita de conjuntos: aunque no podemos justificar aún la existencia de ningún conjunto infinito (no sabemos por ejemplo si es un conjunto).

Probar que

Puedes leer la solución en Wikipedia.

Con el axioma de unión podemos generalizar esta definición para definir para cualquier .

Extra: ¿Cómo puedes generalizarla para tuplas con una cantidad infinita arbitraria de posiciones?

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 existe un conjunto , que tiene todos los elementos de los (es decir, si , entonces ). 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 (basta tomar )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 (la función sucesor)10. Con esta notación el axioma queda:

Con lo que tenemos nuestro primer conjunto infinito. Podemos demostrar que tiene un subconjunto que verifica los axiomas de Peano, tomando y 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 . El axioma queda:

Este axioma afirma la existencia, para cada conjunto de un conjunto que habitualmente llamamos conjunto potencia notado que es el conjunto de todos los subconjuntos de . Este axioma nos permite crear conjuntos de cardinalidad arbitrariamente grande (ya que por el teorema de Cantor, ) 11.

Define

Queremos un conjunto que tenga todas las parejas con , .

Es claro que . Por tanto:

También podemos hacerlo con el esquema de axioma de reemplazamiento y el axioma del par.

Extra: ¿Cómo podemos definir un producto cartesiano de una cantidad arbitaria de conjuntos?

Reemplazamiento

Si es una fórmula en la que no es una variable libre, es un conjunto y se tiene 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 , útiles en la teoría de los ordinales12. 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 que asocia a cada un único . De esta forma el axioma nos permite reemplazar los por su correspondiente . Esto justifica la notación ocasionalmente utilizada

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: no puede expresarse como función en ZFC.

Prueba que reemplazamiento implica comprensión

Puedes encontrar la respuesta en Math StackExchange.

¿Existe el conjunto de todos los espacios topológicos?

Supongamos que exista el conjunto de todos los espacios topológicos. Definimos el predicado funcional .

Como todo conjunto es un espacio topológico con la topología trivial tenemos que: , el conjunto universal, que como ya probamos no existe. Por tanto no, no existe el conjunto de todos los espacios topológicos.

Demostraciones similares pueden utilizarse para probar que no existe el conjunto de todos lo grupos o el conjunto de todas las categorías.

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 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 es infinito existe una aplicación inyectiva

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 o secuencias infinitas de la forma . 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:

  1. Algunos ejemplos de teorías fundacionales alternativas son las teorías de conjuntos estructurales, las teorías de tipos o la teoría de categorías. La equivalencia entre estas tres teorías fundacionales se expone en From Sets to Types to Categories to Sets 

  2. Un ejemplo clásico de paradoja en la filosofía de la ciencia. 

  3. Uno puede preguntarse a qué se refieren las en . Después de todo, como veremos en la sección de los axiomas ¡el dominio de discurso estándar de la teoría de conjuntos no puede verse como un conjunto! Existen diferentes formas de tratar con este problema: podemos adoptar una postura formalista y ver la lógica como unas reglas de manipulación de símbolos o utilizar cuantificación plural (ver también esta pregunta de SE). Nótese que (si expresamos ZFC en lógica de primer orden) sí existen modelos de ZFC   que pueden expresarse en ZFC, pero estos no son el modelo estándar. 

  4. Bueno, casi exclusivamente, también necesitamos clases y conglomerados como veremos a continuación. 

  5. No son la única definición posible: podríamos utilizar (esta es la definición que adoptó Zermelo). Sin embargo con la definición dada en este post tenemos algunas propiedades interesantes: por ejemplo lo que nos permite un tratamiento más sencillo de la teoría de los ordinales. La teoría estructural de conjuntos no distingue entre las distintas posibles construcciones de los números naturales u otros objetos sino que los define según sus propiedades. 

  6. Nótese que si cualquier gráfica es una función estamos considerando la función vacía, que algunos autores excluyen. 

  7. Incluso no asumiendo un dominio de discurso no vacío el axioma de infinito también nos indica que existe un conjunto pero para reducir la complejidad de la exposición de ZFC es interesante añadir este axioma. 

  8. Si expresáramos ZFC en lógica de segundo orden los esquemas de axioma incluidos podrían simplemente expresarse como axiomas añadiendo un cuantificador sobre el predicado correspondiente. La demostración de que ZF(C) no es finitamente axiomatizable puede encontrarse en Kunen (1980) página 138. Sin embargo NBG es finitamente axiomatizable y es una extensión conservativa de ZFC (es decir, todo teorema en ZFC es teorema en NBG). 

  9. Es decir, el lenguaje de los axiomas debe ser recursivamente enumerable. Esto nos permite verificar que una prueba es correcta en una cantidad finita de tiempo y nos impide tener como axiomas todos los teoremas. 

  10. no es una función si no la restringimos a algún dominio, sino simplemente notación: su dominio y codominio deberían ser el conjunto universal que no existe. 

  11. Algunos autores defienden que no necesitamos conjuntos de cardinalidad arbitrariamente grande ya que la mayor parte de las matemáticas suceden en conjuntos numerables o equipotentes a los números reales. La teoría de conjuntos de bolsillo propone una alternativa en la que sólo existen conjuntos infinitos de estas dos cardinalidades. 

  12. Además es necesario para demostrar el teorema de determinación de Borel

(sin etiquetas)