Teoría de conjuntos positivos, antifundación y el "conjunto co-Russell"

Question

Una versión más enfocada de esta pregunta ha sido hecha en MO.

Versión Tl;dr: ¿existen teorías "razonables" que prueben/refuten "el conjunto de todos los conjuntos que se contienen a sí mismos, se contiene a sí mismo"?

---

Inspirado por esta pregunta, me gustaría hacer una pregunta que ha estado vagamente en mi mente por un tiempo pero que nunca he explorado.

Trabajando ingenuamente por un momento, sea $S=\{x: x\in x\}$ el "dual" al conjunto paradójico de Russell $R$. No parece haber un argumento inmediato que muestre que $S$ es o no es un elemento de sí mismo, de manera que refleje la situación de que sí hay argumentos tanto para que $R$ contenga como para que no se contenga a sí mismo (eso es precisamente lo que es la paradoja, por supuesto).

Sin embargo, es un poco prematuro concluir que efectivamente no hay tales argumentos. Es decir, si observamos la situación de Gödel, vemos algo bastante diferente: mientras que la frase de Gödel "Soy indecidible (en $T$)" no es demostrable ni refutable (en $T$), la frase "Soy demostrable (en $T$)" es demostrable (en $T$) (si expresamos "es demostrable" de manera razonable)! Por lo tanto, se rompe cierta simetría intuitiva. Esto plantea la posibilidad de que la pregunta

$$\mbox{¿Contiene $S$ a sí mismo?}$$

en realidad podría ser contestada, al menos desde axiomas "razonables".

Ahora ZFC la responde, aunque de manera trivial: en ZFC tenemos $S=\emptyset$. Por lo tanto, idealmente estamos buscando una teoría de conjuntos que permita conjuntos que se contienen a sí mismos, de manera que $S$ sea no trivial. Además, para mantener la simetría con la paradoja de Russell, es razonable desear una teoría de conjuntos que se asemeje más a la comprensión ingenua.

Todo esto sugiere examinar alguna teoría de conjuntos positiva - que pruebe que $S$ existe, ya que "$x\in x$" es una fórmula positiva, pero no sea susceptible a la paradoja de Russell ya que "$x\not\in x$" no es una fórmula positiva - posiblemente complementada por algún tipo de axioma de antifundación.

Para ser específico:

¿Existe una teoría de conjuntos positiva "natural" (por ejemplo, $GPK_\infty^+$), o extensión de la misma por un axioma de antifundación "natural" (por ejemplo, el de Boffa), que decida si $S\in S$?

En general, me interesa el estatus de "$S\in S$" en teorías de conjuntos positivas. Especialmente me emocionan aquellas que prueban que $S\in S$; ten en cuenta que tendrían que probar la existencia de conjuntos que se contienen a sí mismos, ya que de lo contrario $S=\emptyset\not\in S$.

Answer 1

Encontré un artículo de Cantini que contiene un argumento que se puede usar para establecer que $S \in S$ bajo supuestos bastante débiles (tanto en la cantidad de comprensión como en la lógica subyacente). En última instancia, la prueba es un argumento de punto fijo al estilo del teorema de Löb. Este argumento es lo suficientemente fuerte como para establecer que $S \in S$ en $\mathsf{GPK}$. Aunque Cantini se preocupa por una lógica sin contracciones, me gustaría evitar escribir el cálculo de secuentes en esta respuesta, así que enunciaré y demostraré un resultado más débil en lógica clásica de primer orden.

EDIT: Recientemente descubrí que agregar un operador de abstracción (es decir, notación de construcción de conjuntos) es mucho menos inocuo de lo que me había dado cuenta. (Esto es discutido por Forti y Hinnion en la introducción de este artículo. Mi comprensión del problema es que te permite codificar la negación con igualdad.) Sospecho que la versión antigua de mi respuesta solo era verdadera de manera vacua en que la teoría resultante es inconsistente, así que la he corregido, aunque he especializado el argumento al caso particular. También he pulido un poco el argumento, principalmente para asegurarme de que realmente lo entendía.

Necesitamos asumir que nuestra teoría $T$ tiene suficiente maquinaria para lo siguiente:

• $T$ implica extensionalidad.
• Existe una función de emparejamiento definible $(x,y) \mapsto \langle x,y\rangle$.
• Para cualquier $a$ y $f$, hay un conjunto $f[a]$ tal que $x \in f[a]$ si y solo si $\langle a,x\rangle \in f$. Observa que $(f,a) \mapsto f[a]$ es una función definible por extensionalidad.
• Existe un conjunto $D$ tal que cada elemento de $D$ es un par ordenado $\langle x,y\rangle$ y $\langle x,y\rangle \in D$ si y solo si $y \in y$ o $y = x[x]$.

(Es fácil comprobar que $\mathsf{GPK}$ satisface todos estos.)

Ahora sea $I = D[D]$. Desempaquetando, tenemos que $x \in I$ si y solo si $\langle D,x\rangle \in D$ si y solo si $x \in x$ o $x = D[D] = I$. Por lo tanto, $I$ contiene precisamente los elementos de la clase co-Russell $S$ y el propio $I$, pero dado que $I \in I$, $I \in S$ y por lo tanto $I = S$, de donde $S \in S$.

(Por cierto, un argumento similar también resuelve una pregunta en mi respuesta anterior a tu pregunta relacionada. En particular, $\mathsf{GPK}$ implica la existencia de un átomo de Quine por el argumento anterior si simplemente decimos que $\langle x,y\rangle \in D$ si y solo si $y = x[x]$.)

A la luz de esto, me pregunto si incluso hay una teoría de conjuntos 'razonable' en la que $S$ sea no trivial y $S \notin S$ sea consistente.

Answer 2

Esta no es una respuesta directa a tu pregunta específica, pero podría arrojar una idea sobre una posible solución dentro del ámbito de $\mathsf{GPK}_\infty^+$ en el cual tu pregunta es decidible y ¡positiva!

Hace aproximadamente tres meses le pregunté a Olivier Esser si añadir la siguiente condición es consistente con $\mathsf{GPK}_\infty^+$:

$``$ si $\phi$ es pura positiva sin variables libres aparte de $y,A$, y sin usar la fórmula falsa, entonces: $$\exists A \forall y (y \in A \iff \phi)"$$ Con este principio podemos construir átomos de Quine y conjuntos similares, que no son constructibles meramente en $\mathsf{GPK}_\infty^+$

Sin embargo, Olivier Esser ve que es inconcreto si tal adición es consistente o no. ¿Entonces este principio es discutible en sí mismo?

La idea es que todo depende de lo que sea "razonable". Si el principio anterior se considera más o menos razonable y, de encontrarse consistente, ¡entonces ahí está la respuesta! Sin embargo, aún no hemos llegado a eso.