Los conjuntos en lógica matemática

Question

Es bien sabido que la teoría intuitiva de conjuntos (o teoría ingenua de conjuntos) se caracteriza por tener paradojas, por ejemplo, la paradoja de Russell, la paradoja de Cantor, etc. Para evitar éstas y cualquier otra paradoja potencial descubierta o por descubrir, los axiomas ZFC imponen restricciones a la existencia de un conjunto. Pero la teoría de conjuntos ZFC se basa en la lógica matemática, es decir, en el lenguaje de primer orden. Por ejemplo, el axioma de extensionalidad es el wff $\forall A B(\forall x(x\in A\leftrightarrow x\in B)\rightarrow A=B)$ . Pero la lógica matemática también utiliza el concepto de conjuntos, por ejemplo, el conjunto del alfabeto, el conjunto de variables, el conjunto de fórmulas, el conjunto de términos, así como funciones y relaciones que son en esencia conjuntos. Sin embargo, he encontrado que estos conjuntos se utilizan libremente sin preocuparse por la existencia o las paradojas que se producen en la teoría intuitiva de conjuntos. Es decir, la lógica matemática está utilizando la teoría intuitiva de conjuntos. Entonces, ¿existe alguna paradoja en la lógica matemática? Si no, ¿por qué no? y ¿con qué razonamiento podemos excluir esta posibilidad? Este razonamiento no debería ser ZFC (o cualquier otro análogo) y debería estar más allá de la lógica matemática actual porque, de lo contrario, ZFC depende de la lógica matemática mientras que la lógica matemática depende de ZFC, constituyendo un razonamiento en círculo. En caso afirmativo, ¿qué deberíamos hacer? puesto que no podemos tolerar paradojas en la teoría intuitiva de conjuntos, tampoco deberíamos tolerar paradojas en la lógica matemática, que se considera el fundamento mismo de toda la matemática. Por supuesto, tenemos la tercera respuesta: No sabemos si sí o si no, hasta que un día un genio encuentre una paradoja en la teoría intuitiva de conjuntos utilizada a voluntad en la lógica matemática y entonces todo el edificio de las matemáticas se derrumbe. Este problema me desconcertó durante mucho tiempo, y agradeceré cualquier respuesta que pueda disipar mi aprensión, ¡Gracias!

Answer 1

Me han hecho esta pregunta varias veces en mis clases de lógica o teoría de conjuntos. La conclusión a la que he llegado es que hay que suponer que sabemos tratar con cadenas finitas sobre un alfabeto finito. Esto es suficiente para codificar las variables que solemos usar en lógica de primer orden (y un número finito o contable de símbolos de constantes, relación y símbolos de función).

Así que básicamente tienes que asumir que puedes escribir cosas. Tienes que empezar en alguna parte, y esto es, supongo, un punto de partida que la mayoría de los matemáticos estarían contentos. ¿Teme que aparezcan contradicciones al manipular cadenas finitas sobre un alfabeto finito? finito?

Lo que hace la lógica matemática es analizar el concepto de prueba utilizando métodos matemáticos. Así, tenemos cierta comprensión intuitiva de cómo hacer matemáticas, y luego desarrollamos la lógica matemática y volvemos a considerar lo que hemos aprendido. lógica matemática y volvemos y consideramos lo que realmente estamos haciendo cuando hacemos matemáticas. Este es el círculo hermenéutico por el que tenemos que pasar, ya que no podemos construir algo a partir de la nada.

Creemos firmemente que si hubiera algún problema serio con los fundamentos de las matemáticas (más sustancial que simplemente asumir una colección de axiomas demasiado fuerte), los problemas aparecerían en el análisis lógico de las matemáticas descrito anteriormente.

Answer 2

La respuesta corta es que no hay forma de estar absolutamente seguros de que las matemáticas estén libres de contradicciones.

Para empezar con un caso extremo, todos damos por sentada una cierta cantidad de estabilidad en nuestra experiencia consciente. Tomemos la ecuación $7\times 8 = 56$ . Creo que sé lo que esto significa, y que si decido reflexionar sobre ello durante un tiempo, mi mente no encontrará de algún modo la manera de concluir firmemente que $7\times 8 \ne 56$ . Esto puede parecer una tontería, pero no es una suposición totalmente trivial, porque he tenido sueños en los que me he visto incapaz de contar un pequeño número de objetos y llegar a una respuesta coherente. ¿Hay alguna forma de descartar definitivamente la posibilidad de que el mundo llegue de algún modo a un consenso que $7\times 8 = 56$ et $7\times 8 \ne 56$ ¿Simultáneamente? Yo diría que no. Damos por sentadas algunas cosas y no hay forma de descartar la posibilidad de que esas suposiciones sean fundamentalmente erróneas.

Supongamos que lo aceptamos y retrocedemos a un caso ligeramente menos extremo. Digamos que aceptamos finitario razonamiento matemático sin duda alguna. La gente puede estar en desacuerdo sobre la definición precisa de "finitario", pero una norma comúnmente aceptada es aritmética recursiva primitiva (PRA). En PRA, aceptamos ciertos tipos de razonamiento elemental sobre números enteros. (Si desconfías de los números enteros, entonces puedes sustituir ARP por algún tipo de sistema de razonamiento sobre símbolos y cadenas, por ejemplo, el sistema de "protosintaxis" de Quine; viene a ser más o menos lo mismo). Ahora podemos reformular su pregunta de la siguiente manera: ¿podemos demostrar, basándonos en la ARP, que ZFC es consistente?

Este era, en esencia, el programa de Hilbert. Si pudiéramos demostrar por medios finitos que todo ese complicado razonamiento sobre conjuntos infinitos nunca llevaría a una contradicción, entonces podríamos usar ese razonamiento infinito "con seguridad". Suena como lo que estás pidiendo, ¿no?

Desgraciadamente, los teoremas de Goedel demostraron que el programa de Hilbert no puede llevarse a cabo en la forma prevista. Incluso si permitimos no sólo PRA, sino todo ZFC, nos todavía no puede demostrar que ZFC es consistente. Por lo tanto, no es sólo que todos hayamos sido demasiado estúpidos hasta ahora para averiguar cómo demostrar que ZFC no conduce a contradicciones. Aquí hay un obstáculo intrínseco que es insuperable.

Así que no se puede descartar tu hipótesis de que alguien pueda encontrar algún día una contradicción en ZFC, incluso si damos por sentado el "razonamiento matemático ordinario". Sin embargo, esto no es tan malo como podría parecer. ZFC no es el único sistema posible en el que pueden basarse las matemáticas. Hay muchos otros sistemas de menor fuerza lógica. Si se encontrara una contradicción en ZFC, simplemente volveríamos a algún sistema más débil. Para más información sobre este punto, véase esta pregunta MO .

Answer 3

Parece que tienes algunos problemas. En primer lugar, la afirmación "la lógica matemática depende de ZFC" no tiene sentido.

Como lógicos matemáticos, cuando estudiamos sistemas formales, debemos imaginarnos colocando ese sistema formal en una caja. La caja está llena de fórmulas y deducciones en el lenguaje objeto. Por ejemplo, ZFC es una teoría de primer orden con un símbolo de predicado binario y un montón de axiomas. Ocupa una posición privilegiada, ya que tendemos a pensar en ella como "la" teoría formal de conjuntos, pero no hay ninguna razón por la que no podamos utilizar MK o NF u otras teorías de conjuntos para los mismos fines.

La lógica matemática es el acto de estudiar sistemas formales utilizando métodos matemáticos (no necesariamente formales), y ZFC es sólo un sistema formal en particular. El punto importante es que la lógica matemática no es un sistema formal, y aunque la afirmación "ZFC es consistente" está bien formada, la afirmación "la lógica matemática es consistente" no lo es. Afirmar que una teoría es inconsistente es afirmar que existe una prueba formal de falso en algún sistema formal. La paradoja de Russel, por ejemplo, puede plantearse como una prueba formal de falso en ZFC con comprensión no restringida.

Sin el contexto de la lógica de primer orden y las colecciones de variables y símbolos que se necesitan para escribir fórmulas y pruebas formales, la afirmación "_ es (in)coherente" no tiene sentido. El espacio en blanco debe rellenarse con una teoría de primer orden o, más en general, con algún sistema formal que tenga una noción de prueba formal. Se puede preguntar "¿está justificado que formemos y manipulemos estas colecciones?". Pero esa es una pregunta informal. Como han señalado otros usuarios, tiene muy buenas respuestas informales, por ejemplo, el hecho de que los ordenadores funcionen nos da la seguridad de que no debemos preocuparnos por hacer aritmética y manipular cadenas informalmente.

Para responder afirmativa o negativamente a la pregunta "¿es consistente la teoría informal de conjuntos que utilizamos para formular la lógica de primer orden?", debemos definir la noción de consistencia y, al hacerlo, utilizar la teoría informal de conjuntos en cuestión. La cuestión, de nuevo, es que la consistencia sólo se define en el contexto de la lógica de primer orden, donde tomamos estas colecciones como primitivas y definimos la consistencia a partir de ahí. Del mismo modo que no podemos hablar de un grupo simple fuera del contexto de los grupos, no podemos hablar de consistencia formal fuera del contexto de las teorías formales.

En resumen: ¡no se puede aportar una prueba formal de nada sin definir primero la prueba formal! Por lo tanto, debemos empezar por algún sitio y tomar las colecciones de símbolos de la lógica de primer orden como primitivas, o convencernos informalmente de que está justificado formar tales colecciones.

Answer 4

Es decir, la lógica matemática es utilizar la teoría intuitiva de conjuntos. Entonces, ¿hay alguna paradoja en la lógica matemática?

Sí, en la teoría de conjuntos cuya lógica se basa en la teoría ingenua de conjuntos hay La paradoja de Berry .

Considera la expresión:

"El menor número entero positivo no definible en menos de once palabras".

Supongamos que define un número entero positivo $n$ . Entonces $n$ ha sido definida por las diez palabras entrecomilladas. Pero por su definición, $n$ no se puede definir en menos de once palabras. Esto es una contradicción.

Una versión de la paradoja de Berry se llama La paradoja de Richard . No veo una diferencia esencial entre las dos paradojas (salvo que la paradoja de Richard fue planteada por Poincaré, que se ocupaba de las definiciones impredicativas, y la paradoja de Berry por Russell, que se ocupaba de los tipos). Pero los dos artículos de Wikipedia ofrecen explicaciones muy diferentes.

La explicación de la paradoja de Berry es esencialmente por la teoría de tipos (aunque no se nombre); y la explicación más específica dada por la teoría de la recursividad también parece encajar en el marco de la teoría constructiva de tipos.

La paradoja de Richard se resuelve en el marco de la ZFC (y, lo que es más importante, de la lógica de primer orden). A grandes rasgos, la resolución consiste en que no todo lo que tiene sentido en la teoría de conjuntos cuya lógica se basa en la teoría ingenua de conjuntos debería tener sentido en la ZFC; de ahí que, en cierto sentido, la paradoja sólo se resuelva realmente en "la metateoría utilizada para formalizar la ZFC". No conozco ningún libro de texto sobre tal meta-ZFC, lo que me hace sentir incómodo sobre esta resolución; pero también lo hicieron Poincaré y Russell, según entiendo de sus escritos.

Para este propósito concreto, creo que una ZFC de segundo orden funcionaría igual de bien que una "meta-ZFC". Pero entonces una versión superior de la misma paradoja sólo se explicaría realmente mediante una ZFC de tercer orden, etc. Pero, de nuevo, no conozco ningún libro de texto sobre ZFC de tercer orden. Por suerte, hay bastantes libros de texto sobre lógica de orden superior / teoría de tipos y según tengo entendido no hay problemas de este tipo (paradojas tipo Richard/Berry) en un moderno tipo teoría porque sirve como su propia lógica en esencia.

Por otra parte, una teoría de tipos se dice para seguir necesitando una metateoría. ¿Significa esto que debe haber paradojas más profundas que no se resolverían con la teoría de tipos?

Añadido más tarde. Me divierte un poco este hilo, que sigue creciendo con respuestas "ortodoxas" y con su animada discusión en los comentarios, mientras que la respuesta "herética" que estás leyendo ahora no ha sido cuestionada (ni siquiera votada a la baja) todavía.

Quizá debería resumir mis puntos para que sea más fácil objetar si a alguien le interesa.

1) La pregunta de la OP puede ser un poco informal o vaga, pero tiene sentido como las paradojas de Berry y Richard demuestran inequívocamente. Uno puede tener diferentes puntos de vista sobre estas paradojas y su resolución, pero uno posible (que creo haber tomado de los escritos de Poincare) es que, efectivamente, están causados por la dependencia mutua de hecho entre la teoría de conjuntos y la lógica a la que se hace referencia en la OP. ("Teoría de conjuntos" y "lógica" se entienden aquí en sentido coloquial, sin referirse a una formalización específica). No se pueden ignorar estas paradojas, ¿verdad?

2) Las teorías de tipos pueden tener muchas desventajas en comparación con ZFC con lógica de primer orden (incluida la falta de una formulación canónica y de un equivalente de Bourbaki), pero rompen la circularidad entre la teoría de conjuntos y la lógica y, por tanto, resuelven adecuadamente las paradojas. ZFC es perfectamente capaz de defenderse de estas paradojas pero no intenta explique Para ello, se remite al metanivel, que termina con especulaciones informales sobre los ordenadores y la propia experiencia con cadenas finitas de símbolos. (Por supuesto, estas especulaciones plantean problemas, como qué cadenas son finitas exactamente, los problemas de parada de los ordenadores idealizados y la memoria finita de los ordenadores físicos, por no hablar de los problemas de memoria finita de los ordenadores físicos). finitud potencial de la información en el universo físico y el software de comprobación de pruebas de uno ya implica potencialmente la lógica de orden superior). Así que en este caso veo que la teoría de tipos proporciona una matemáticas solución, y ZFC, en el mejor de los casos, una metafísica uno.

3) Lo que no entiendo es si podría existir un tipo de teoría de tipos que no necesitara ninguna metateoría (es decir, que sirviera como su propia metateoría). Tal vez alguien diciendo "No se puede sacar nada de la nada" o "No se puede tener ninguna teoría sin metateoría" o "por algún sitio hay que empezar" o "por algún sitio hay que empezar", ¿podría explicar también por qué es imposible? Si efectivamente es imposible, ¿puede esta imposibilidad ser atestiguada por una paradoja específica para aclarar completamente las cosas?

Answer 5

No se puede sacar nada de la nada :-) Pero no se preocupe.

Las matemáticas existían mucho antes de que se formulara la ZFC, y mucho antes de que el "razonamiento formal" se convirtiera en una especie de religión. Matemáticamente, no hay nada más formal en un "razonamiento formal" que en cualquier otro razonamiento "lógicamente justificado" (es decir, comúnmente aceptado). La verdadera razón de codificar las matemáticas en una única teoría es reunir todas las dudas en un único lugar, ganar confianza en que nuestra nueva teoría es consistente (siempre que los fundamentos lo sean) y ayudar a comunicarnos con otros matemáticos.

Volviendo a su pregunta. Permítanme distinguir entre cuatro casos - de acuerdo con su terminología - una teoría puede ser:

• ingenua y formal - esto significa que utilizando el razonamiento formal podemos demostrar que existe una inconsistencia en la teoría (por ejemplo: ZFC con comprensión no restringida)
• ingenuo e informal - esto significa que vemos que hay una inconsistencia en el razonamiento dentro de la teoría, pero una prueba de este hecho está fuera de nuestras matemáticas (el mismo ejemplo)
• no ingenua y formal: significa que creemos que la teoría es coherente y (a veces) podemos demostrar "formalmente" su coherencia en relación con otra teoría (formal o informal) comúnmente aceptada.
• no ingenuo e informal - igual que el anterior, con la última parte de la frase omitida.

Así que, como puede ver, ser formal no puede hacer que una teoría sea consistente/inconsistente, pero puede proporcionar argumentos adicionales a favor/en contra de la teoría - simplemente - la corrección es invariable bajo cambios de formalidad. Para la mayoría de las situaciones, la imagen de la formalidad es la siguiente:

• existe un concepto informal como "lógica de primer orden"
• existe una teoría formal de conjuntos expresable en lógica de primer orden

Si quisiéramos investigar las propias fundaciones, podríamos ampliar el panorama introduciendo uno (o más) niveles adicionales:

• existe una teoría informal de conjuntos (metateoría; tiene que ser un poco más fuerte que la teoría "interna" de conjuntos para demostrar que la teoría "interna" de conjuntos es consistente, pero puede ser mucho más débil para expresar la teoría "interna")
• existe una lógica formal de primer orden expresable en la metateoría
• existe una teoría formal de conjuntos expresable en lógica de primer orden