Nombres réels constructifs vs calculables

Question

Je trouve déroutant que toutes les affirmations suivantes soient vraies:

1. Les nombres réels calculables sont dénombrables. $-\hspace{-3pt}-$ Alan Turing, «Sur les nombres calculables, avec une application au Entscheidungsproblem»
2. Dans une analyse constructive, les nombres réels sont indénombrables. $-\hspace{-3pt}-$Everett Bishop, Fondements de l'analyse constructive
3. "chaque énoncé mathématique [en analyse constructive] exprime en fin de compte le fait que si nous effectuons certains calculs dans l'ensemble des nombres entiers positifs, nous obtiendrons certains résultats" $-\hspace{-3pt}-$ Ibid.

Peut-être ai-je mal compris quelque chose.

Je suppose que j'ai vraiment deux questions. En analyse constructive :

1. Pourquoi tous les nombres réels ne sont-ils pas calculables?
2. Comment est-il possible de construire un ensemble indénombrable?

Answer 1

1. Il est cohérent avec l'analyse constructive que chaque réel est calculable. (En fait, il est cohérent avec ZF intuitionniste$\mathsf{IZF}$.) Cela découle de la cohérence de https://en.wikipedia.org/wiki/Church%27s_thesis_(constructive_mathematics), qui revendique chaque fonction totale de $\mathbb{N}$ à $\mathbb{N}$ est calculable.

   Cependant, cela ne signifie pas qu'une analyse constructive peut prouver que chaque réel est calculable. Nous savons que l'analyse classique est un sur-ensemble de l'analyse constructive (en tant que théorie), c'est-à-dire que tout énoncé prouvable à partir de l'analyse constructive est aussi un théorème de l'analyse classique. Et les mathématiques classiques prouvent que tous les réels ne sont pas calculables. Il serait donc exact de dire si tout réel est calculable est indépendant de l'analyse constructive.

   Pour ajouter un commentaire, je pense que cela ne signifie pas que Bishop a tout simplement tort. L'analyse constructive de Bishop est minimale en ce sens qu'elle est contenue dans l'analyse classique, les mathématiques intuitionnistes de Brouwer et l' analyse constructive récursive (également connue sous le nom de constructivisme russe). Cette dernière reflète le comportement des mathématiques récursives, donc l'affirmation de Bishop serait vraie en ce sens sens.

2. $\mathbb{R}$ est indénombrable en ce sens qu'il n'y a pas de bijection entre $\mathbb{N}$ et $\mathbb{R}$. La preuve est disponible à partir de l' analyse constructive de Bishop . (Théorème 2.19 de Bishop et Bridges.) Voici une preuve approximative:

   Théorème. Il n'y a pas de bijection de$\mathbb{N}$ à un intervalle $[x_0,y_0]=\{z\in\mathbb{R}\mid x_0\le z\le y_0\}$. (Mise en garde:$x\le y$n'est pas ($x< y$ ou $x=y$.))

   Preuve. La preuve utilise l'argument de diagonalisation. Suppose que$f:\mathbb{N}\to\mathbb{R}$est une fonction. Nous trouverons un réel Cauchy$x\in [x_0,y_0]$ tel que $f(n)\neq x$ pour tous $n$. Nous construirons des séquences de nombres naturels$(x_n)$ et $(y_n)$ récursivement de telle sorte 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)$ ou $y_n<f(n)$, et
   3. $y_n-x_n<1/n$.

   Suppose que $x_i$ et $y_i$ sont donnés pour tous $i<n$. Ensuite, nous avons soit$f(n)>x_{n-1}$ ou $f(n)<y_{n-1}$. (Cela découle du théorème constructivement valide suivant: si$x<y$ sont des réels, alors non plus $z<y$ ou $x<z$.)

   Supposons que nous ayons $f(n)>x_{n-1}$. (Le cas restant est analogue.) Choisissez un nombre rationnel$x_n$ et $y_n$ tel que $x_{n-1}<x_n<\min(a_n,y_{n-1})$ et $x_n<y_n<\min(a_n,y_{n-1},x_n+1/n)$. Ensuite, les inégalités mentionnées sont satisfaites.

   Par conséquent $(x_n)$forme une suite de Cauchy de nombres rationnels. Laisser$x$ être une limite de $(x_n)$, puis $x$ satisfait les propriétés souhaitées.

   Notez que la preuve ci-dessus utilise le choix comptable que Bishop a accepté. Autant que je sache, il est libre de savoir si$\mathbb{R}$est dénombrable ou non sans le choix dénombrable. Notez également que$\mathbb{R}$peut être sous- dénombrable , c'est-à-dire$\mathbb{R}$peut être une image d'un sous - ensemble de$\mathbb{N}$. (Malheureusement, j'ai oublié si la sous-dénombrement de$\mathbb{R}$ est compatible avec $\mathsf{IZF}$, même si je pense que c'est vrai.)