Números reales constructivos vs computables

Question

Me resulta confuso que todas las siguientes afirmaciones sean verdaderas:

1. Los números reales computables son contables. $-\hspace{-3pt}-$ Alan Turing, "Sobre números computables, con una aplicación al problema Entscheidungs"
2. En el análisis constructivo, los números reales son incontables. $-\hspace{-3pt}-$Everett Bishop, Fundamentos del análisis constructivo
3. "cada enunciado matemático [en el análisis constructivo] expresa en última instancia el hecho de que si realizamos ciertos cálculos dentro del conjunto de números enteros positivos, obtendremos ciertos resultados" $-\hspace{-3pt}-$ Ibídem.

Quizás estoy malinterpretando algo.

Supongo que realmente tengo dos preguntas. En análisis constructivo :

1. ¿Por qué no se pueden calcular todos los números reales?
2. ¿Cómo es posible construir un conjunto incontable?

Answer 1

1. Es consistente con el análisis constructivo que todo real es computable. (De hecho, es consistente con el intuicionista ZF$\mathsf{IZF}$.) Esto se sigue de que la consistencia de https://en.wikipedia.org/wiki/Church%27s_thesis_(constructive_mathematics), que reclama cada función total de $\mathbb{N}$ a $\mathbb{N}$ es computable.

   Sin embargo, no significa que el análisis constructivo pueda probar que todo real es computable. Sabemos que el análisis clásico es un superconjunto de análisis constructivo (como teoría), es decir, todo enunciado que puede demostrarse a partir del análisis constructivo es también un teorema del análisis clásico. Y las matemáticas clásicas demuestran que no todo lo real es computable. Por tanto, sería exacto decir que si todo real es computable es independiente del análisis constructivo.

   Para agregar algún comentario, creo que no significa que Bishop esté simplemente equivocado. El análisis constructivo de Bishop es mínimo en el sentido de que está contenido en el análisis clásico, las matemáticas intuicionistas de Brouwer y el análisis constructivo recursivo (también conocido como constructivismo ruso). El último refleja el comportamiento de las matemáticas recursivas, por lo que la afirmación de Bishop sería cierta en que sentido.

2. $\mathbb{R}$ es incontable en el sentido de que no hay biyección entre $\mathbb{N}$ y $\mathbb{R}$. La prueba está disponible en el análisis constructivo de Bishop . (Teorema 2.19 de Bishop y Bridges.) Aquí hay una prueba aproximada:

   Teorema. No hay biyección de$\mathbb{N}$ a un intervalo $[x_0,y_0]=\{z\in\mathbb{R}\mid x_0\le z\le y_0\}$. (Precaución:$x\le y$es no ($x< y$ o $x=y$.))

   Prueba. La prueba usa un argumento de diagonalización. Asumir que$f:\mathbb{N}\to\mathbb{R}$es una función. Encontraremos un Cauchy real$x\in [x_0,y_0]$ tal que $f(n)\neq x$ para todos $n$. Construiremos secuencias de números naturales$(x_n)$ y $(y_n)$ recursivamente tal que

   1. $x_0\le x_n\le x_m<y_m\le y_n\le y_0$ Si $1\le n\le m$,
   2. $x_n>f(n)$ o $y_n<f(n)$y
   3. $y_n-x_n<1/n$.

   Asumir que $x_i$ y $y_i$ se dan para todos $i<n$. Entonces tenemos$f(n)>x_{n-1}$ o $f(n)<y_{n-1}$. (Esto se sigue del siguiente teorema constructivamente válido: si$x<y$ son reales, entonces tampoco $z<y$ o $x<z$.)

   Supongamos que tenemos $f(n)>x_{n-1}$. (El caso restante es análogo.) Elija un número racional$x_n$ y $y_n$ tal que $x_{n-1}<x_n<\min(a_n,y_{n-1})$ y $x_n<y_n<\min(a_n,y_{n-1},x_n+1/n)$. Entonces se satisfacen las desigualdades mencionadas.

   Por lo tanto $(x_n)$forma una secuencia de Cauchy de números racionales. Dejar$x$ ser un límite de $(x_n)$, entonces $x$ satisface las propiedades deseadas.

   Tenga en cuenta que la prueba anterior hace uso de la opción contable que Bishop aceptó. Hasta donde yo sé, está abierto si$\mathbb{R}$es contable o no sin la opción contable. Además, tenga en cuenta que$\mathbb{R}$puede ser contable , es decir$\mathbb{R}$puede ser una imagen de un subconjunto de$\mathbb{N}$. (Desafortunadamente, olvidé si la subresponsabilidad de$\mathbb{R}$ es compatible con $\mathsf{IZF}$, aunque creo que es cierto.)