Algunas preguntas sobre la matemática intuicionista

Question

Tengo que escribir un trabajo sobre el Intuicionismo para mi clase de Filosofía de la Ciencia y estoy luchando con algunos conceptos que he encontrado en mi auto-estudio.

La caracterización (intuitiva) de las inferencias intuicionistas válidas que conozco viene dada por la Interpretación de BHK . Sea $\neg$ denota la negación fuerte definida en H4, y $\sim$ denotan la negación débil (es decir $\sim P$ significa que no hay pruebas de $P$ se ha encontrado). Probablemente sea mucho pedir en una sola pregunta, pero lo intentaré:

1. En este dice que Gödel demostró que todo teorema de PA que no involucra los símbolos " $\vee$ " o " $\exists$ " es también un teorema de HA y dado que todo enunciado de la lógica clásica es clásicamente equivalente a uno que no contenga esos dos símbolos, tenemos que todo teorema de PA tiene una versión que es aceptable para el intuicionista.

   • ¿No es esto cierto en general, por ejemplo cuando se trata de números reales?
   • ¿No es cierto que, en general, si una declaración $P$ es clásicamente válida, entonces $\neg \neg P$ ¿es intuitivamente válido?

2. También me preguntaba qué formulaciones del axioma de elección son aceptables en un marco intuicionista. El resultado principal en este contexto es Teorema de Diaconescu que afirma que en la teoría constructiva de conjuntos la versión completa de AC no puede sostenerse, ya que implicaría un medio excluido.

   • En primer lugar, no me siento cómodo con la demostración de dicho teorema: ¿cómo pueden los conjuntos $U$ y $V$ (definida en la página de Wikipedia) estar intuitivamente bien definida, si no podemos, en general, afirmar $P \vee \neg P$ ? En el mismo libro al que me refería antes dice que $$ b_n = \begin{cases} 0 \ \forall n \quad \text{if Goldbach's conjecture is true} \\ 1 \ \forall n \quad \text{if Goldbach's conjecture is false} \end{cases} $$ "no define una secuencia en absoluto, porque no nos dice cómo calcular sus términos" (página 126). Entonces, ¿cómo pueden los conjuntos $U$ y $V$ está bien definida si $P$ es una afirmación que no podemos demostrar ni refutar, como la conjetura de Goldbach?
   • Dice aquí que, aunque el AC completo no es intuitivamente aceptable "hay, sin embargo, ciertos axiomas de elección restringidos que son aceptables para el intuicionista", como el Axioma de Elección Contable o de Elección Dependiente. Pero la elección utilizada en el razonamiento de Diaconescu no sólo es contable, ¡es finita! Entonces, ¿cómo puede la cardinalidad de la familia de conjuntos entre los que elegimos tener algo que ver con la validez intuicionista de nuestro principio de elección?

Desgraciadamente, no tengo la formación en Lógica y Teoría de Conjuntos para profundizar en demasiados detalles técnicos, así que estoy obteniendo mi información de libros de filosofía no demasiado técnicos y de las entradas de la Wikipedia y la Enciclopedia Standford. Si alguien pudiera explicar en términos sencillos lo que estoy entendiendo mal, sería estupendo.

Esta pregunta me ha salido aún más larga de lo que tenía previsto y, por supuesto, también se agradecen mucho las respuestas parciales. Muchas gracias por cualquier ayuda.

21/05/12 Recibí dos respuestas muy útiles y, aunque voy a aceptar la de Kaveh ya que aborda tanto la 1 como la 2, la de Carl fue crucial para mi comprensión de la 2. Espero que estas respuestas reciban los votos positivos que merecen, ¡gracias a ambos!

Answer 1

Esta es una respuesta a algunas de las preguntas del OP.

• El conjunto $\{U,V\}$ construido en la demostración del teorema de Diaconescu parece finito desde una perspectiva clásica. Pero la definición de "finito" es que existe una biyección con algún número natural (esto es cierto tanto en el ámbito clásico como en el constructivo). Como los conjuntos $U$ y $V$ se construyen de tal manera que no se sabe si $U = V$ o $U \not = V$ No puede haber ninguna prueba constructiva de que esa biyección existe, porque la biyección te permitiría saber si los conjuntos son iguales. De hecho, el conjunto $\{U,V\}$ no es finito (constructivamente).

• El teorema de Diaconescu es particular de la teoría constructiva de conjuntos. En esa teoría, se permiten axiomas de comprensión incluso cuando la pertenencia al conjunto construido no es decidible. Así, por ejemplo, aceptarían $$W = \{ x \in \{1\} : \text{the Riemann hypothesis holds}\}$$ como una definición válida de un conjunto. Por supuesto, no tienen ni idea de si este conjunto está vacío, o si es $\{1\}$ porque la hipótesis de Riemann es una cuestión abierta. Hay otros entornos de la matemática constructiva en los que la relación de pertenencia de los conjuntos es siempre decidible; en esos entornos no es posible formar conjuntos como $W$ en primer lugar.

Answer 2

Gödel demostró que todo teorema de PA que no implique los símbolos " $\lor$ " o " $\exists$ " es también un teorema de HA

Creo que te refieres a La traducción negativa de Godel

¿No es esto cierto en general, por ejemplo cuando se trata de números reales?

El teorema es válida si la propia teoría es cerrada bajo la traslación y la doble negación de las fórmulas atómicas es equivalente a ellas, entonces la traslación es identidad sobre la parte que no contiene " $\lor$ " y " $\exists$ ".

¿No es cierto que, en general, si un enunciado P es clásicamente válido, entonces ¬¬P es intuitivamente válido?

No, hay que eliminar el contenido constructivo de todas las partes internas, no basta con hacerlo en el exterior. (Si conoces los modelos de Kripke, entonces una doble negación en el frente significa que la declaración en el interior será eventualmente forzada, es decir constructivamente correcto).

En primer lugar, no estoy cómodo con la demostración de dicho teorema: ¿cómo pueden los conjuntos U y V (definidos en la página de Wikipedia) estar intuitivamente bien definidos, si no podemos, en general, afirmar P∨¬P? [...] Entonces, ¿cómo pueden estar bien definidos los conjuntos U y V si P es una afirmación que no podemos demostrar ni refutar, como la Conjetura de Goldbach?

Supongo que su pregunta es "por qué aceptamos el axioma de la especificación como constructivo?". Este tipo de confusiones suelen surgir porque las personas que no están familiarizadas con los conceptos constructivos intentan interpretarlos de forma clásica. Diferentes teorías constructivas utilizan conceptos conceptualmente diferentes pero de apariencia similar y la diferencia no es visible cuando se miran como objetos clásicos. La mejor referencia que conozco que tiene un buen tratamiento de estas cuestiones y una explicación de lo que significa cada una de ellas es el libro de Beeson "Foundations of Constructive Mathematics", 1980.

En este caso estás utilizando un argumento sobre la no definición de un número (¡no de una secuencia!), $n$ no juega sobre el papel aquí) en la teoría constructiva de los números para argumentar en contra de la buena definición de un conjunto en una teoría de conjuntos particular.

Puede llegar a ser aún más confuso (para las personas que no están familiarizadas con el hecho de que estas teorías pueden utilizar conceptos conceptualmente diferentes), un axioma constructivo sobre algunos conceptos en una teoría constructiva puede destruir la constructividad de otra teoría. No hay nada malo en cada una, el problema es que los conceptos subyacentes son diferentes y cada uno satisface axiomas constructivos diferentes. Un buen ejemplo ilustrativo son las "funciones" y las "operaciones". Si quieres saber más sobre su diferencia consulta el libro de Beeson.

Aquí dice que, aunque el AC completo no es intuitivamente aceptable "hay, sin embargo, ciertos axiomas de elección restringidos que son aceptables para el intuicionista", como el Axioma de Elección Contable o de Elección Dependiente. Pero la elección utilizada en el razonamiento de Diaconescu no sólo es contable, ¡es finita! Entonces, ¿cómo puede la cardinalidad de la familia de conjuntos entre los que elegimos tener algo que ver con la validez intuicionista de nuestro principio de elección?

Cuidado con llamarlos finitos, $U$ y $V$ son finitos sólo si se tiene una prueba constructiva de ello, y aquí significaría dar un número natural y una biyección entre el conjunto y ese número. De nuevo estás mezclando los puntos de vista clásicos con los constructivos y eso puede causar confusión.

Lo segundo es que no tienes claro el contexto. Hay bastantes axiomas de elección, algunos de los cuales pueden destruir el contenido constructivo de una teoría constructiva si no se tiene cuidado de cuáles son los objetos subyacentes reales de los que hablan. El axioma de elección contable podría estar hablando de un "conjunto" contable de subconjuntos de números naturales no conjuntos generales.

En resumen,

• recuerda que no hay a matemática constructiva, hay un muchos matemática constructiva, y que no está de acuerdo sobre los axiomas,

• tener cuidado al combinar axiomas constructivos de diferentes teorías constructivas, entender qué tipo de objetos son realmente sobre (¿qué información se da cuando se da un objeto?) y entender cuál es la justificación de la constructividad del axioma sobre esos objetos, luego comprobar si esa justificación sigue siendo válida para los objetos de la teoría a la que se quiere añadir el axioma.