¿Qué es lo que impide que definamos el conjunto de todos los conjuntos que no son miembros de sí mismos en la teoría de conjuntos moderna?

Question

Podemos definir claramente un conjunto de conjuntos. Siento intuitivamente que deberíamos definir conjuntos que contengan a sí mismos; por ejemplo, el conjunto de todos los conjuntos que contienen conjuntos como elementos. ¿Ese conjunto produce una contradicción?

No tengo una comprensión muy sólida de lo que constituye un conjunto frente a lo que constituye una clase. Entiendo que todos los conjuntos son clases, pero que existen clases que no son conjuntos, y esto aparentemente resuelve la paradoja de Russell, pero no creo que vea exactamente cómo lo hace. ¿Las clases no pueden contener clases? ¿Puede una clase contenerse a sí misma? ¿Puede un conjunto?

Answer 1

Ya que los demás usuarios han respondido a la pregunta en el contexto de la teoría de conjuntos bien fundamentada, permítanme decir unas palabras sobre otras teorías de conjuntos.

Antes de poder responder realmente a esta pregunta, debemos pensar primero en qué es un "conjunto" en primer lugar. Intuitivamente, un conjunto es algo que tiene miembros y que está totalmente determinado por lo que son sus miembros. Esto se codifica en el axioma de la extensionalidad:

Extensión. Si $X$ y $Y$ son conjuntos, y para todo $z$ , $z \in X \iff z \in Y$ entonces $X = Y$ .

Sin embargo, hay que tener en cuenta que el cuantificador "para todos $z$ "es ilimitado, es decir, no hay ninguna restricción en el tipo de $z$ . Fijemos sin compromiso un universo de discurso $\mathbf{U}$ y decir que $z$ debe estar en $\mathbf{U}$ . Entonces, ¿puede un conjunto ser miembro de otro conjunto? Bueno, eso depende: ¿hay algún conjunto en $\mathbf{U}$ ? Si no es así, es evidente que un conjunto no puede ser miembro de ningún conjunto. Esto es bastante inaceptable para hacer matemáticas modernas, así que debemos rectificar esto de alguna manera.

La propia solución de Russell a su paradoja fue introducir la noción de tipo . (Lo que describo aquí es la sin clasificar teoría de tipos TST, no la teoría de tipos de Principia Mathematica .) Comenzamos con algunos tipos básicos $\mathbf{U}_0$ - digamos, los números naturales. Definimos conjuntos cuyos miembros son del tipo $\mathbf{U}_0$ - y este es un nuevo tipo $\mathbf{U}_1$ . Repetimos este procedimiento infinitamente, formando en cada etapa el tipo $\mathbf{U}_{n+1}$ correspondientes a conjuntos de cosas de tipo $\mathbf{U}_n$ . Así, obtenemos conjuntos cuyos miembros son otros conjuntos; por otra parte, es evidente que el universal "conjunto" no existe en esta ontología: si $X$ es un conjunto, entonces es del tipo $\mathbf{U}_{n+1}$ para algún número natural $n$ y sus miembros deben ser del tipo $\mathbf{U}_n$ - así que en particular, $X \notin X$ . Incluso podríamos desterrar por completo la fórmula " $X \in X$ " porque no hay ninguna asignación de tipos posible que la convierta en una fórmula bien formada.

Por desgracia, hemos tenido que introducir infinitos tipos de conjuntos, y parece bastante complicado seguir la pista de todos estos tipos en la práctica. La teoría de conjuntos moderna lo resuelve tomando $\mathbf{U}_0$ para ser el tipo vacío y colapsar todos los tipos superiores en un solo tipo $\mathbf{U}$ . Así, todo en el universo del discurso es un conjunto (pero eso no significa todo conjuntos están en $\mathbf{U}$ ), y tiene sentido preguntarse si $x \in y$ para cualquier $x$ y $y$ en $\mathbf{U}$ . En particular, la fórmula antes prohibida $x \in x$ está bien formada de nuevo - así que de nuevo tenemos que encontrar alguna otra solución a la paradoja de Russell.

Profundizando un poco más, descubrimos que uno de los supuestos de la paradoja es el axioma ingenuo de la comprensión: es decir, siempre que $\varphi (x)$ es una fórmula bien formada, entonces existe un conjunto $\{ x : \varphi (x) \}$ en $\mathbf{U}$ cuyos miembros son precisamente aquellos $x$ en $\mathbf{U}$ para lo cual $\varphi (x)$ se satisface. Por ello, debemos ser más cuidadosos con los conjuntos que suponemos que están en $\mathbf{U}$ . Este es de donde proviene la distinción conjunto-clase: en el lenguaje habitual, "conjunto" se refiere a conjuntos que están en $\mathbf{U}$ y "clase" se refiere a los conjuntos cuyos miembros están en $\mathbf{U}$ pero no están necesariamente en $\mathbf{U}$ a sí mismos. Para evitar confusiones, diré $\mathbf{U}$ -para el primero.

Entonces, ¿qué debemos asumir en lugar del ingenuo axioma de la comprensión? Los Nuevos Fundamentos (NF) de Quine ofrecen una opción:

Comprensión estratificada. Digamos que una fórmula bien formada $\varphi (x)$ es estratificado si hay una forma de asignar tipos a todo las variables que aparecen en $\varphi (x)$ para que siempre que $y \in z$ aparece en $\varphi (x)$ , $y$ es del tipo $\mathbf{U}_n$ y $z$ es del tipo $\mathbf{U}_{n+1}$ y siempre que $y = z$ aparece en $\varphi (x)$ , ambos $y$ y $z$ son del tipo $\mathbf{U}_n$ . Entonces, siempre que $\varphi (x)$ es una fórmula estratificada, la clase $\{ x : \varphi(x) \}$ es un $\mathbf{U}$ - conjunto.

A grandes rasgos, cualquier conjunto que existe bajo TST también existe bajo NF. En particular, la clase $\{ x : x = x \}$ es un $\mathbf{U}$ -bajo NF - por lo que NF admite un conjunto universal. Por otro lado, la clase paradójica $\{ x : x \notin x \}$ hace no existen en NF, porque $x \notin x$ no es una fórmula estratificada. Ahora bien, la consistencia relativa de NF no está bien entendida, pero la teoría relacionada NFU (obtenida permitiendo $\mathbf{U}_0$ para que no esté vacío) es se sabe que es consistente con la teoría de conjuntos ZF. Por lo tanto, si creemos que ZF es consistente, entonces también deberíamos creer que hay una teoría de conjuntos consistente en la que el conjunto universal existe - en particular, el conjunto universal no produce una contradicción por sí mismo .

Habiendo mencionado esto, supongo que también debería decir cómo se maneja la comprensión en ZF. Tenemos el siguiente axioma:

Separación. Para cualquier $\mathbf{U}$ -Ajustar $X$ Si $\varphi (x)$ es cualquier fórmula bien formada, la clase $\{ x \in X : \varphi (x) \}$ es un $\mathbf{U}$ - conjunto.

Evidentemente, en presencia de un conjunto universal, el axioma de separación es equivalente al axioma ingenuo de comprensión, así que más vale que hagamos algo al respecto.

Regularidad. Cualquier $\mathbf{U}$ -Ajustar $X$ tiene un miembro $Y$ de manera que cualquier miembro de $Y$ es no un miembro de $X$ . (Equivalentemente, $X \cap Y = \emptyset$ .)

En particular, no existe un conjunto universal. Es tentador decir que la relación de pertenencia $\in$ se fundamenta en $\mathbf{U}$ pero hay una sutileza aquí: sólo $\mathbf{U}$ -se garantiza que los conjuntos tienen un $\in$ -miembro mínimo. Sin embargo, todavía hay otros problemas que solucionar: hasta ahora no hay axiomas que garanticen que nuestro universo $\mathbf{U}$ no está vacía. Pero esa es una historia para otro día.

Por último, debemos discutir las teorías formales de conjuntos de clases, como la de von Neumann-Bernays-Gödel (NBG) o la de Morse-Kelley (MK). En estas teorías, el universo del discurso $\mathbf{U}$ se compone de "clases", y un "conjunto" se define como una clase que es miembro de algunos clase. Para evitar confusiones, digamos $\mathbf{V}$ -para los primeros y $\mathbf{V}$ -para este último. Un verdadero $\mathbf{V}$ -clase es un $\mathbf{V}$ -clase que es no también un $\mathbf{V}$ - conjunto.

Tenemos un axioma de comprensión de clase que rige la formación de $\mathbf{V}$ -clases:

Comprensión de la clase limitada. Si $\varphi (x)$ es una fórmula bien formada que no tiene ningún atado variables que van más allá de $\mathbf{V}$ -clases, entonces la clase $\{ x : x \text{ is a } \mathbf{V} \text{-set and } \varphi (x) \}$ es un $\mathbf{V}$ -clase.

Comprensión total de la clase. Si $\varphi (x)$ es cualquier fórmula bien formada, entonces la clase $\{ x : x \text{ is a } \mathbf{V} \text{-set and } \varphi (x) \}$ es un $\mathbf{V}$ -clase.

NBG utiliza el axioma de comprensión de clase limitada, mientras que MK utiliza el axioma de comprensión de clase completa. De cualquier manera, se garantiza la existencia de la $\mathbf{V}$ -clase $$\mathbf{V} = \{ x : x \text{ is a } \mathbf{V} \text{-set and } x = x \}$$ que contiene todo $\mathbf{V}$ -sets. Pero es $\mathbf{V}$ sí mismo un $\mathbf{V}$ -¿conjunto? Para responder a esto necesitamos un axioma que nos diga qué $\mathbf{V}$ -las clases son $\mathbf{V}$ -sets.

Limitación de tamaño. Digamos que una biyección es una $\mathbf{U}$ -si su gráfico existe en $\mathbf{U}$ es decir, si se puede definir mediante un $\mathbf{V}$ -función de clase. A $\mathbf{V}$ -clase $X$ es un $\mathbf{V}$ -set si y sólo si hay no existe un $\mathbf{U}$ -bición entre $X$ y $\mathbf{V}$ .

En particular, $\mathbf{V}$ debe ser un verdadero $\mathbf{V}$ -clase. Tenga en cuenta que por definición un adecuado $\mathbf{V}$ -La clase no puede contenerse a sí misma. Lamentablemente, esto no responde a la pregunta de si un $\mathbf{V}$ -set puede estar contenido en sí mismo. En NBG y MK, esta cuestión se resuelve mediante el axioma de regularidad aplicado a las clases:

Regularidad de la clase. Cualquier $\mathbf{V}$ -clase $X$ tiene un miembro $Y$ de manera que cualquier miembro de $Y$ es no un miembro de $X$ .

Por lo tanto, no $\mathbf{V}$ -set puede contenerse a sí mismo - al menos en NBG o MK.

Answer 2

No entiendo del todo, "Podemos definir claramente un conjunto de conjuntos. Siento intuitivamente que deberíamos definir conjuntos que sí se contengan a sí mismos"

Puedes definir la colección de todos los conjuntos. Se define mediante la fórmula $x = x$. $V = \{x : x = x\}$. De manera similar, puedes definir la colección de todos los conjuntos que no son miembros de sí mismos. La fórmula que hace esto es $x \notin x$. Sea $A = \{x : x \notin x\}$. En cualquier estructura en el lenguaje de la teoría de conjuntos, estas corresponderían a clases definibles.

Sin embargo, ninguno de estos conjuntos son sets. Te interesa el hecho de que $A$ no es un conjunto. Supongamos que $A$ es un conjunto. Entonces tienes que $A \in A$ o $A \notin A$. Si $A \in A$, entonces $A$ no satisface la fórmula que define a $A; por lo tanto, $A \notin A$. Contradicción. Ahora supongamos que $A \notin A$. Entonces $A$ satisface la fórmula definitoria para $A$. Así que $A \in A$. Contradicción. Dado que ninguna de esas cosas puede ocurrir, debes tener que $A$ no es un conjunto.

La paradoja de Russell se resuelve limitando el axioma de comprensión. En lugar de que todas las clases definibles sean conjuntos, el axioma de especificación afirma que la intersección de cualquier clase definible con un conjunto es un conjunto.

Answer 3

Hay mucha interacción entre la teoría de conjuntos y la lógica de primer orden. Un sistema de teoría de conjuntos es una lista de axiomas de primer orden (que 'viven fuera' del sistema de teoría de conjuntos!), por ejemplo, la teoría ingenua de conjuntos podría tener axiomas como:

1) si dos conjuntos $x$ e $y$ tienen los mismos elementos son los mismos conjuntos (el axioma de extensionalidad). en lenguaje de primer orden, esto podría escribirse como $(\forall x,y)(\forall z ((z \in x) \iff (z\in y)) \iff (x=y)$

2) para cualquier fórmula de primer orden con una variable libre existe un conjunto de objetos que satisface esa fórmula (comprensión ingenua).

Sin embargo, esto lleva al paradoxo de Russell, por lo que en cambio restringimos el número de conjuntos que consideramos para solo tener conjuntos bien fundamentados, es decir, conjuntos para los cuales $x \neq \{x\}$ (o conjuntos que no son miembros de sí mismos). Esto lleva a la teoría de conjuntos de Zermelo-Fraenkel, y lo importante aquí es que restringimos el esquema de axiomas de comprensión para que no podamos pedir un conjunto de todas las cosas que satisfacen una fórmula de primer orden.

(es interesante destacar que originalmente Zermelo intentó codificar $0$ como $\emptyset$, 1 como $\{\emptyset\}$, 2 como $\{\{\emptyset\}\}$ etc etc, y $\omega$ como $\{ \dots\{\emptyset\}\dots\}$, lo que hubiera violado el fundamento)

Sin embargo, podemos considerar una clase de todos los conjuntos que satisfacen una fórmula de primer orden. Así, por ejemplo, la fórmula $\varphi$ con una variable libre $x$ que establece $(x=x)$, y esto es satisfecho por todos los conjuntos, por lo que la clase correspondiente a $\varphi$ es la clase de todos los conjuntos. Hay que tener en cuenta que esto no es un conjunto, ya que no podemos alcanzarlo mediante los axiomas de ZFC - vive 'fuera de ZFC' por así decirlo. Por lo tanto, para resumir, una clase es una clase de equivalencia (¡esto no es circular!) de conjuntos que satisfacen una fórmula de primer orden, no necesariamente constructible dentro de nuestra teoría de conjuntos.

Answer 4

Aquí hay dos problemas entrelazados: primero, la paradoja de (Bertrand) Russell del "conjunto" de todos los conjuntos que no se contienen a sí mismos, sobre la cual trata el título de la pregunta. Esto se resuelve con la restricción del axioma de comprensión ingenua de Frege para permitir solo subconjuntos de conjuntos preexistentes.

Segundo, el cuerpo de tu pregunta parece estar más preocupado por el problema de los conjuntos que se contienen a sí mismos. El axioma de fundación AF (o regularidad), que prohíbe tales conjuntos, en realidad no es la solución de la paradoja de Russell: si mantenemos la comprensión ingenua y agregamos AF, el conjunto $S$ de todos los conjuntos que no se contienen a sí mismos simplemente se convertirá en el conjunto de todos los conjuntos. Por lo tanto, es evidente que $S \in S$, mientras que AF requiere que $S \notin S$, por lo que la teoría ingenua de conjuntos solo con AF es inconsistente.

Así que AF no es suficiente para corregir la teoría de conjuntos de Frege. Tampoco es necesario: si la teoría de conjuntos de Zermelo-Fraenkel es inconsistente con AF eliminado, entonces ZF en sí misma es inconsistente. Esto deja abierta la posibilidad de otras alternativas. Aczel hizo el trabajo canónico sobre esto con su axioma de anti-fundación AFA. En términos generales, esto define conjuntos como cosas que pueden descomponerse en conjuntos, en lugar de construirse a partir de conjuntos como con AF. La consecuencia es que existen conjuntos que se contienen a sí mismos, mientras que la teoría mantiene la misma fuerza de consistencia que ZF. Entonces, la respuesta a tu pregunta sobre si un conjunto puede contenerse a sí mismo es "no" en la teoría de conjuntos estándar, pero "sí" en general.

Answer 5

Paradoja de Russell

En la teoría de conjuntos de Zermelo, la demostración de la pregunta titular es directa:

• Supongamos que existe tal conjunto. Llamémoslo $R$.
  • Hecho: $x \notin x$ si y solo si $x \in R$. Esta es la propiedad definitoria de $R$.
  • Supongamos $R \in R$.
    • Según el hecho, esto significa que $R \notin R$.
    • ¡Contradicción!
  • Por lo tanto, $R \notin R$.
  • Según el hecho, esto significa que $R \in R$.
  • ¡Contradicción!
• Por lo tanto, no existe tal conjunto.

Hay una corolario inmediato: no existe un conjunto de todos los conjuntos.

• Supongamos que existe un conjunto de todos los conjuntos. Llamémoslo S.
  • Hay un subconjunto $R \subseteq S$ que contiene exactamente aquellos conjuntos $x$ para los cuales $x \notin x$.
  • ¡Contradicción!
• Por lo tanto, no existe un conjunto de todos los conjuntos.

Justificación de la teoría de conjuntos de Zermelo

Una de las características más importantes de una teoría de conjuntos es tener herramientas para realmente construir conjuntos. La teoría de conjuntos 'naïve' de Cantor tenía la regla más poderosa de todas: si podías nombrar alguna propiedad $P$, entonces había un conjunto de todos los conjuntos que tienen la propiedad $P$. ¡Esto te permitía construir cualquier conjunto que pudieras imaginar! Desafortunadamente, te permitía construir el conjunto de la paradoja de Russell, y por lo tanto la teoría de conjuntos de Cantor es contradictoria.

Zermelo tomó un enfoque más modesto*: buscó una colección más conservadora de construcciones que bastara para las matemáticas, pero que no fuera tan fuerte como para crear alguno de los conjuntos paradójicos conocidos. Fraenkel añadió otra construcción útil y nos dio el axioma de fundación que simplifica los argumentos técnicos.

Entre las construcciones de la teoría de conjuntos de Zermelo se encuentra la forma restringida del "principio de comprensión" de Cantor: si tenemos alguna propiedad $P$ y un conjunto $S$, entonces podemos formar el subconjunto de $S$ de las cosas que satisfacen la propiedad $P$.

El axioma de la comprensión restringida es exactamente la propiedad de un universo de conjuntos que se necesita para hacer el argumento de la sección inicial.

*: No sé si esto es históricamente preciso. Realmente, estoy expresando una observación a posteriori al respecto.

Clases

La notación de constructor de conjuntos es una notación muy útil para denotar conjuntos. Recordemos que cada una de las siguientes notaciones define conjuntos en ZFC:

$$ \{ x \in S \mid P(S) \} \qquad \qquad \{ f(x) \mid x \in S \} \qquad \qquad \{ a, b \} $$

donde $a, b, S$ son todos conjuntos, $P$ es un predicado unario cuyo dominio incluye a $S$, y $f$ es una función cuyo dominio incluye a $S$.

La misma notación resulta ser bastante útil para definir predicados. Por ejemplo, el predicado

P(x) = "x contiene al conjunto vacío"

se puede notar fácilmente como

$$ P = \{ x \mid \emptyset \in x \} $$

y la afirmación de que $x$ satisface el predicado $P$ se puede escribir como

$$ x \in P. $$

Esta notación, formalmente, no tiene nada que ver con conjuntos: es una notación alternativa para lógica. Cuando hacemos esto, llamamos a un predicado una "clase".

La forma en que se manipula la lógica en forma de clases es tan similar a la forma en que se manipulan los conjuntos que esta notación unificada es extremadamente útil.

Para responder a una pregunta que tenías, los únicos objetos siguen siendo conjuntos. La única cosa que puede ser miembro de un conjunto es un conjunto. La única cosa que puede ser miembro de una clase es un conjunto. Las clases no pueden ser miembros de nada, porque no son objetos: son lógica. (al menos, si nos ceñimos a la lógica de primer orden....)

Puede ser técnicamente incómodo cuando tienes que prestar atención a qué es un conjunto y qué es una clase, especialmente si quieres razonar en una versión 'simplificada' de la lógica formal.

Entonces, Von Neumann, Bernays y Gödel inventaron la teoría de conjuntos (NBG). Los objetos de la teoría de conjuntos NBG son clases. Puede ser un poco confuso usar la misma palabra que usamos para el punto de vista alternativo de la lógica anterior; sin embargo, en la práctica no es un problema.

La teoría de conjuntos NBG incluye una clase llamada $\mathbf{Set}$. $V$ es otro nombre común para esta clase. Hay un teorema/axioma que dice que si $x \in y$, entonces $x \in \mathbf{Set}$.

NBG también puede presentarse (y usualmente se presenta, creo) como una teoría con dos tipos: un tipo de conjuntos y un tipo de clases. Solo los conjuntos pueden ser elementos de cosas. Pero para cualquier conjunto hay una clase que tiene los mismos elementos, y es razonable identificar los dos.

*: Nuevamente, esto no pretende ser una presentación históricamente precisa.

Universos

Otro enfoque para tratar con clases es un universo de Grothendieck. Sin embargo, utilizarlos requiere asumir un axioma de los grandes cardinales.

Un universo de Grothendieck es, brevemente, un conjunto $U$ con la propiedad de que los elementos de $U$ colectivamente tienen propiedades lo suficientemente buenas como para poder ser llamados justificadamente un 'universo de conjuntos'. Llamamos "conjuntos pequeños" a los elementos de $U$. Las cosas que normalmente llamaríamos clases son todos subconjuntos de $U$.

De esta manera (además de tener que asumir un axioma de los grandes cardinales) no tenemos que hacer mucho que sea especial -- todo de lo que estamos hablando es un conjunto. Simplemente ocasionalmente tenemos que tomar nota de qué conjuntos son "pequeños" y cuáles no lo son.