¿Por qué no se puede resolver la Paradoja de Russell con referencias a conjuntos en lugar de contención?

Question

Mi formación es en informática, y mantengo la Implementación de Java en mi mente como modelo. El lenguaje Java incluye la noción de establece .

Ahora entiendo que esto es diferente del modelo Russell y Whitehead tenían en su mente cuando escribían Principia Mathematica pero no entiendo del todo por qué es diferente.

Para mí, cuando dices "un conjunto que contiene un conjunto", tienes tres formas de "implementar" esto. Puedes decir que está "físicamente dentro" (y dibujarlo dentro). Puedes decir que "es sólo un concepto lógico" (que es a lo que creo que Russell quería llegar). Y puedes decir "es un concepto físico, pero no está físicamente dentro - los unimos con punteros" (como en la programación informática).

Si se profundiza en esta cuestión La paradoja de Russell : "El conjunto de todos los conjuntos que no se contienen a sí mismos", cuando se habla de programación informática, es un concepto relativamente fácil de aplicar (dentro del dominio de los conjuntos de un programa informático).

Supongo que hay una diferencia filosófica entre los conjuntos en Java y los conjuntos de Russell. (Imagino que debe haber un nombre para los conjuntos de Russell, pero no sé cómo se llaman).

Puedo ver que las matemáticas tienen otras teorías de conjuntos como Teoría de conjuntos de Zermelo-Fraenkel y Los nuevos fundamentos de Quine .

Mi pregunta es: ¿Por qué no se puede resolver la Paradoja de Russell con referencias a conjuntos en lugar de contención?

Answer 1

Por el contrario, el conjunto de Russell - interpretado en su modelo de programación informática- no es fácil de implementar (y mucho menos posible). La "contención" real no es un problema: en principio, los matemáticos estarían perfectamente satisfechos con un conjunto que se contenga a sí mismo.

La cuestión es la siguiente: considere un (Java) Set que contiene en él referencias a exactamente esos Set s actualmente en la memoria que no contienen referencias a sí mismos. Llame a este Set<Set> R. Supongamos que R contiene una referencia a sí mismo. Entonces R no cumple el requisito de ser referenciado por un miembro de R, por lo que R no puede ser referenciado por nada en R, contradiciendo nuestra suposición. Supongamos, pues, que R no contenga una referencia a sí mismo. Entonces R cumple el requisito de ser referenciado en R (es decir, es un Set que no contiene una referencia a sí mismo) por lo que debe tener una referencia en R, contradiciendo nuestra suposición.

Una vez más, que la contención signifique realmente "contención" no es relevante. De hecho, la teoría de conjuntos moderna trata formalmente la pertenencia de forma abstracta: el símbolo $\in$ no tiene ningún significado canónico, es sólo una relación arbitraria que obedece a ciertos axiomas. Es útil visualizarlo como una contención real o como un sistema de referencias tipo Java, porque esas visualizaciones obedecen a los axiomas, pero la implementación "física" no es relevante para nada de la lógica.

Answer 2

Permítanme presentar una perspectiva diferente. En lugar de modelar un conjunto utilizando un objeto contenedor formado por punteros/referencias, lo cual puede ser limitante, supongamos que elegimos modelar los conjuntos como una función que

• aceptará cualquier conjunto, y
• siempre devuelve un booleano.

La forma en que esto se implemente en un lenguaje específico, como Java, no es realmente relevante. Hay cuestiones estructurales que superar; Java presenta la dificultad de que una función no es un objeto, por ejemplo, y mi código no aborda esta cuestión. Sin embargo, esto no es un obstáculo serio para el concepto.

Lo importante es que, sin duda, podemos aplicar el conjunto universal:

bool Universe(Object X) { return true; }

y podemos implementar lo que aparentemente debería ser el conjunto de todas las cosas que no se contienen a sí mismas:

bool Russell(Object X) { return !X(X); }

¿Qué tiene de malo este conjunto, Russell? Bueno, si conectas Russell a sí mismo, entonces se llamará a sí mismo, creando un bucle recursivo infinito. Por lo tanto, Russell no devuelve nada cuando se conecta a sí mismo como parámetro, por lo que no puede ser un conjunto.

Answer 3

Mientras que las respuestas de Reese y Dustan han explicado la paradoja de la teoría de conjuntos en términos de Java, no responden a la parte de la pregunta sobre cómo exactamente las estructuras de datos de conjuntos (no sólo en Java) evitan la paradoja, ni muestran cómo la paradoja puede evitar de manera coherente con la programación.

En primer lugar, el sistema de tipos de los lenguajes de programación es diferente de las teorías de conjuntos y de tipos habituales en los fundamentos de las matemáticas. Incluso me atrevería a decir que un lenguaje de programación debería tener un tipo universal, y de hecho Java se acerca a ello (las únicas excepciones que conozco son los tipos de datos nativos, que están ahí por razones de rendimiento). Pero verás, la mayoría de los lenguajes de programación no tienen ningún "axioma de especificación", a diferencia de las teorías de conjuntos/tipos. En otras palabras, no puedes crear un tipo de datos o una clase que incluya como miembros a todos los objetos que satisfagan una determinada propiedad. Así que no se puede construir un tipo de datos como el de Russell en la mayoría de los lenguajes de programación.

Sin embargo, se podría decir que por qué no utilizar un programa ¿para especificar un tipo? A saber, un tipo es simplemente un programa $P$ (un procedimiento sin estado interno en la mayoría de los lenguajes de programación) y definir sus miembros como todas las entradas en las que $P$ paradas y salidas $true$ . En un lenguaje de programación moderno como Java, esto corresponde a decir que un tipo es una función (parcial) P con firma bool P(Object x) . Esta noción es extremadamente intuitiva (después de todo, ¿de qué otra manera clasificamos las cosas?) y también encaja perfectamente con las nociones intuitivas básicas, incluyendo el tipo universal (que es simplemente bool U(Object x) { return true; } ) y la existencia de complementos universales (el complemento de P es sólo bool notP(Object x) { return !P(x); } . En un marco más abstracto, esto podría denotarse como $U = ( obj\ x \mapsto true )$ y $P' = ( obj\ x \mapsto \neg P(x) )$ respectivamente.

Además, bajo este paradigma de programas-como-tipos podemos efectivamente construir el tipo Russell. Si el marco abstracto (lenguaje de programación) permite la coerción de tipos en tiempo de ejecución (como Javascript), entonces es simplemente $R = ( obj\ x \mapsto \neg x(x) )$ . Si no es así, necesitamos algún tipo de reflexión (como en Java) para definir $R = ( obj\ x \mapsto type(x) \ ? \ \neg x(x) : false )$ . De cualquier manera, podemos entonces demostrar que $R(R) = \neg R(R)$ en el sentido de que ambas expresiones tienen el mismo comportamiento de salida. En este caso, ambas no se detienen, por lo que la afirmación es verdadera y no causa contradicción.

Así que puedes ver que la idea de que un conjunto debe ser un indicador función en todo el universo es la característica clave de las teorías de conjuntos que se enfrentan a la paradoja de Russell, ya que la paradoja desaparece una vez que se permite una brecha de valor de verdad y no se permite que el sistema forme tipos basados en lo que cae en esa brecha. Véase este puesto para una posible manera de manejar tales construcciones. De hecho, Kripke describió una noción similar de fundamentación y también mostró que se puede eludir Teorema de indefinibilidad de Tarski en cierto sentido utilizando la lógica de 3 valores de Kleene en su teoría de la verdad .

Por último, me gustaría señalar que todo esto tiene poco que ver con el hecho de que los objetos se manejen por valor o por referencia. La cuestión principal es si se puede capturar meta-teórica propiedades en el propio sistema. En el caso de la teoría de conjuntos, se trata de la noción de que se puede construir un conjunto que divida con precisión el universo en dos partes sin ningún hueco, en función de alguna propiedad que sólo tiene sentido desde el "exterior". $\{ x : \neg x \in x \}$ depende de la evaluación de " $\neg x \in x$ " para cada objeto $x$ que puede responderse para cualquier modelo dado de teoría de conjuntos, pero la respuesta está en la metateoría y no siempre es captada por la propia teoría. Del mismo modo, el teorema de indefinibilidad de Tarski muestra que la verdad (una metapropiedad) no siempre puede ser captada por un sistema formal. El modelo de la teoría de la verdad de Kripke no responde afirmativamente sobre la verdad de todas las frases; algunas de estas cuestiones caen en la brecha del valor de la verdad.

Answer 4

Un conjunto matemático tiene un significado diferente al de un conjunto informático. Un conjunto matemático se define como un agregado o "lista" de elementos, ya sea mediante una enumeración explícita o mediante la caracterización de la propiedad de los elementos que están contenidos en el conjunto. Por ejemplo, podemos probar cualquier objeto del universo y determinar si forma parte del conjunto o no. Son extremadamente simples. Los conjuntos o listas informáticas añaden otras complejidades, como la asignación de memoria, etc.

El conjunto de todos los conjuntos es una estructura definida recursivamente y no puede representarse en su totalidad en un programa informático, pero puede ser imaginado en cierto sentido por la mente humana y representado por un conjunto finito de símbolos, ya sea en papel o en un ordenador. Es un conjunto que contiene todo lo que existe y que puede considerarse un conjunto de algo, también se incluye a sí mismo simplemente porque el conjunto de todos los conjuntos es un conjunto en sí mismo.

dejar $\mathcal{S} = \{X | X\mbox{ is a set}\}$

Entonces, por definición\construcción $\mathcal{S}$ es un conjunto mientras exista. La única forma de salir de la paradoja es asumir que $\mathcal{S}$ no existe, pero está claro que sí existen aproximaciones a ella y podemos escribir la propiedad de caracterización, por lo que "parece" que existe. No conozco ninguna "prueba" de que $\mathcal{S}$ existe realmente. Podemos escribir el conjunto y sus propiedades y parece que eso es suficiente para demostrar que tal conjunto existe, pero esto no es suficiente para garantizar que realmente existe.

En cualquier caso, si el conjunto existe entonces, debería estar claro que $\mathcal{S}$ debe ser un elemento de sí mismo. La razón es sencilla: $\mathcal{S}$ existe y es un conjunto, por suposición/deducción, y la propiedad de caracterización afirma que todo lo que existe y es un conjunto es un elemento de $\mathcal{S}$ . Por ello, $\mathcal{S} \in \mathcal{S}$ .

Para ser claros, vamos a simplificar:

dejar $\mathcal{B} = \{X | X\mbox{ is blue}\}$ . Dejando de lado la cuestión de cómo saber si algo es azul, podemos decir que el conjunto $\mathcal{B}$ es el conjunto de todas las cosas que son azules. Ahora, el conjunto $\mathcal{B}$ no es azul porque los conjuntos no tienen la propiedad del color (recuerda, tienen una forma de enumerar o describir sus elementos, nada más y nada menos).

Así que, $\mathcal{B} \notin \mathcal{B}$ . Sustituye azul por mesa y también debería estar claro. Ningún conjunto es una mesa y por tanto el conjunto de todas las mesas no puede estar "dentro" del conjunto.

Por ejemplo, supongamos que podemos enumerar todas las tablas por $table_1, ... table_n$ entonces este conjunto: $$\mathcal{T^*} = \{table_1, ..., table_n, \{table_1, ..., table_n, \{table_1, table_n, ... ... \}\}\}$$

No es el conjunto de todas las tablas. El conjunto de todas las mesas está dentro, pero una mesa no es un conjunto y un conjunto no es una mesa, así que hay una confusión porque nuestro conjunto contiene mesas y luego un conjunto. Por ejemplo, si fueras un fabricante de mesas y me pidieras que te trajera el conjunto de las mesas de fuera y te las trajera todas y además te trajera un conjunto de las mismas podrías mirarme raro y preguntarte por qué te he dado un "conjunto (matemático) de las mesas". Tú pediste sólo tablas pero yo te di un conjunto de tablas, que no es tabla, así que violé tu caracterización de lo que es una tabla.

PERO un conjunto es un conjunto! y eso hace que la situación sea muy singular. De nuevo, supongamos que podemos enumerar todos los conjuntos mediante algún esquema de indexación,

$\mathcal{S} = \{S_1, ..., S_n, \{S_1, ..., S_n, \{S_1, S_n, ... ... \}\}\} = \{S_1, ..., S_n, S\}$

Cada elemento de $\mathcal{S}$ es un conjunto, incluso el elemento $\mathcal{S}$ que es el propio conjunto en la definición de sí mismo.

Así, resulta que cuando uno escribe un conjunto de este tipo, es una definición recursiva que tiene una recursión infinita. Los programas de ordenador no pueden tratar ese caso, ya que requiere un nivel de abstracción que los ordenadores no pueden hacer. Los sistemas CAS pueden hacer un mejor trabajo y pueden tratar con algunos niveles infinitos pero no han progresado al nivel de abstracción que la mente humana puede realizar. (Un día, cuando los humanos descubran cómo codificar esas cosas, podrán manejar esos problemas, pero los humanos siempre tendrán que liderar hasta un punto en el que los ordenadores puedan pensar por sí mismos, en cuyo caso los humanos quedarán obsoletos).

Hay que tener claro que los ordenadores no tratan con conjuntos de conjuntos. No se puede ni siquiera empezar a construir adecuadamente algo así en un ordenador y hacer matemáticas con él. Cualquier "conjunto" en un ordenador no es un conjunto matemático. Es una lista de datos. Posiblemente se utilice una lista de punteros... así que tenemos un conjunto de punteros a "conjuntos" (que son en sí mismos datos y no conjuntos matemáticos reales). Un conjunto matemático no tiene ninguna estructura superficial. Es muy simple y muy directo y no oculta ningún detalle ni expone ninguna propiedad no esencial del tipo "conjunto". En realidad es más fácil de entender porque uno no tiene que saber cómo se construyen, usan o abusan los conjuntos como hay que hacer con los ordenadores. (por ejemplo, ¿es el conjunto concurrente?) Pero a la mayoría de la gente le resulta más difícil porque no puede desprenderse de sus propias nociones de lo que es un conjunto (le atribuyen un significado adicional en lugar de eliminar sus nociones "prácticas").

Ahora, el problema/paradoja ocurre cuando extendemos nuestra lógica sobre el conjunto de todos los conjuntos que no se contienen a sí mismos . Se trata de un subconjunto de $\mathcal{S}$ ya que tiene una condición extra:

dejar $\mathcal{S'} = \{X | X\mbox{ is a set and }X\notin X\}$

Esta condición extra crea una paradoja. Parece trivial, pero se abre toda una lata de gusanos. Seguimos la misma lógica que con let $\mathcal{S}$ pero esta vez descubrimos que si $\mathcal{S'} \in \mathcal{S '}$ terminamos con una contradicción PERO también si $\mathcal{S} \notin \mathcal{S'}$ terminamos con una contradicción. Pero no hay alternativa. Tenemos una contradicción más grande creada.

Es fácil de ver:

si $\mathcal{S'} \in \mathcal{S'}$ entonces esto significa que no podemos incluir $\mathcal{S'}$ en nuestro conjunto ya que no cumple la propiedad de caracterización. Pero eso nos lleva a $\mathcal{S'} \notin \mathcal{S'}$ lo que contradice nuestra hipótesis de partida.

Entonces, OTOH, si $\mathcal{S'} \notin \mathcal{S'}$ entonces $\mathcal{S'}$ pasa la prueba de caracterización y está en el conjunto, lo que significa que $\mathcal{S'} \in \mathcal{S'}$ lo que de nuevo contradice nuestra suposición.

No hay otras alternativas, así que ¿qué dice eso de $\mathcal{S'}$ ? ¿No existe? Puede tanto contenerse como no contenerse de alguna manera (lo que viola la prueba de caracterización general para todos los conjuntos).

Por ejemplo, supongamos que tenemos los dos conjuntos

$\mathcal{S*} = \{X | X\mbox{ is a set and }X\in X\}$ $\mathcal{S''} = \{X | X \neq \mathcal{S''}\mbox{ is a set and }X\notin X \}$

Los dos conjuntos son válidos en cierto sentido y no tienen problemas, pero han cambiado muy poco. El segundo ejemplo es un poco difícil sin embargo porque hacer ser capaz de saber si $X \in \mathcal{S''}$ tenemos que saber $\mathcal{S''}$ ... pero estamos construyendo $\mathcal{S''}$ en ese proceso, así que no sabemos $\mathcal{S''}$ todavía. Así que la "contradicción" que $\mathcal{S'}$ había realmente se arrastra a $\mathcal{S''}$ .

Lo que hay que tener en cuenta es que estas cuestiones forman parte de los fundamentos de las matemáticas. Lo que muestran es que el uso del lenguaje matemático que parece ser muy lógico y se aplica a muchas otras cosas... cosas que los matemáticos normales usan todos los días, resulta que, en casos muy especiales, produce contradicciones. Esto crea problemas fundamentales en las matemáticas porque sugiere que hay un "error" en alguna parte.

En realidad no tiene nada que ver con los ordenadores, salvo que los ordenadores se construyen sobre las matemáticas. No cambia mucho para la mayoría de la gente porque no utilizan las matemáticas que se derivan de tales nociones.

Es análogo a la paradoja EPR. Es una cosa que "existe" pero a nadie le afecta en la vida práctica. Los ingenieros de cohetes no tienen que preocuparse y no tienen que construir cohetes de forma diferente. Sin embargo, pone a prueba nuestra comprensión de la naturaleza de la realidad, y por eso es tan importante. Significa que algo falla en alguna parte. O bien nos equivocamos (un error), hay un error fundamental en la existencia (lo que significa que no es un error, sino simplemente la vida y tenemos que lidiar con ella), o hay un error fundamental en nuestra capacidad de entender la existencia (como el segundo caso, pero no creado por "dios").

Si quieres estudiar estas cosas usando ordenadores vas a tener que alejarte de las estructuras de datos que estás confundiendo con las "estructuras de datos" matemáticas. Un conjunto informático (que es un array) no es lo mismo que la versión matemática (aunque se solapan bastante).

La mejor manera de representar el conjunto de todos los conjuntos en un ordenador es utilizando la representación de cadena "X es el conjunto de todos los conjuntos". Se podría utilizar un booleano: "bool X = true;" Cuando X es falso no es el conjunto de todos los conjuntos.

Sea como sea que intentes representarlo, acabarás con el problema de intentar hacer algo con él. Tendrás que idear algún sistema lógico que no sea la programación estándar e implementar la lógica matemática. Será bastante difícil o posiblemente imposible. Los CAS son la única cosa conocida que se acerca a tales cosas y hacen trampa y son incompletos. Esencialmente tendrás que programar la mente humana en un ordenador para poder tener alguna posibilidad de averiguar estas cosas.

El problema es sencillo: Los ordenadores deben representar cosas en última instancia como 0's y 1's pero las matemáticas pueden representar cosas sin nada. Sólo tiene que tener un símbolo para ello y puede dejar que se desconozca. (por ejemplo, x en una expresión algebraica es una "incógnita" (aunque sea una incógnita restringida)... no requiere ningún almacenamiento excepto el símbolo) Por eso las matemáticas son tan poderosas, porque utilizan la manipulación simbólica para representar transformaciones de cosas que no necesitan ser representables de ninguna manera. Podemos simplemente establecer "Que X sea algo" y luego hacer algo con X. Siempre que tengamos claro cómo hacemos estas cosas, podemos crear una estructura. Por supuesto, "que X sea algo" es tan general que podemos hacer cualquier cosa/nada, así que tenemos que retroceder un poco, y esa es la naturaleza de la vida, según parece. Puede ser que el conjunto de todos los conjuntos que no se contenga a sí mismo esté cerca del límite del sinsentido y por eso tenemos una contradicción. Al igual que puedo decir que X es verdadero y falso a la vez y es imposible de demostrar/desmentir porque X es algo sin ninguna otra cosa que apoye o niegue mis afirmaciones. Hay que añadir restricciones a las ideas para darles forma y permitir que interactúen con otras cosas. Las matemáticas empujan tanto los límites que puede que estén en el punto en el que no puedan ir más allá, o que deba producirse algún nuevo avance que revolucione nuestra comprensión no sólo de las matemáticas sino de la vida.