Números reais construtivos vs computáveis

Question

Acho confuso que todas as seguintes afirmações sejam verdadeiras:

1. Os números reais computáveis ​​são contáveis. $-\hspace{-3pt}-$ Alan Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem"
2. Na análise construtiva, os números reais são incontáveis. $-\hspace{-3pt}-$Everett Bishop, Fundamentos da Análise Construtiva
3. "cada declaração matemática [em análise construtiva] expressa em última análise o fato de que, se realizarmos certos cálculos dentro do conjunto de inteiros positivos, obteremos certos resultados" $-\hspace{-3pt}-$ Ibid.

Talvez eu esteja entendendo mal alguma coisa.

Suponho que realmente tenho duas perguntas. Em análise construtiva :

1. Por que nem todo número real é computável?
2. Como é possível construir um conjunto incontável?

Answer 1

1. É consistente com a análise construtiva que todo real é computável. (Na verdade, é consistente com ZF intuicionista$\mathsf{IZF}$.) Segue-se daí a consistência de https://en.wikipedia.org/wiki/Church%27s_thesis_(constructive_mathematics), que reivindica todas as funções totais de $\mathbb{N}$ para $\mathbb{N}$ é computável.

   No entanto, isso não significa que a análise construtiva pode provar que todo real é computável. Sabemos que a análise clássica é um superconjunto da análise construtiva (como uma teoria), ou seja, toda afirmação que pode ser demonstrada a partir da análise construtiva é também um teorema da análise clássica. E a matemática clássica prova que nem todo real é computável. Portanto, seria correto dizer que se todo real é computável é independente da análise construtiva.

   Para adicionar algum comentário, acho que isso não significa que Bishop está simplesmente errado. A análise construtiva de Bishop é mínima no sentido de que está contida na análise clássica, na matemática intuicionista de Brouwer e na análise construtiva recursiva (também conhecida como construtivismo russo). A última reflete o comportamento da matemática recursiva, então a afirmação de Bishop seria verdadeira nisso sentido.

2. $\mathbb{R}$ é incontável no sentido de que não há bijeção entre $\mathbb{N}$ e $\mathbb{R}$. A prova está disponível na análise construtiva de Bishop . (Teorema 2.19 de Bishop e Bridges). Aqui está uma prova grosseira:

   Teorema. Não há bijeção de$\mathbb{N}$ a um intervalo $[x_0,y_0]=\{z\in\mathbb{R}\mid x_0\le z\le y_0\}$. (Cuidado:$x\le y$não é ($x< y$ ou $x=y$.))

   Prova. A prova usa o argumento da diagonalização. Assuma isso$f:\mathbb{N}\to\mathbb{R}$é uma função. Encontraremos um verdadeiro Cauchy$x\in [x_0,y_0]$ de tal modo que $f(n)\neq x$ para todos $n$. Vamos construir sequências de números naturais$(x_n)$ e $(y_n)$ recursivamente tal que

   1. $x_0\le x_n\le x_m<y_m\le y_n\le y_0$ E se $1\le n\le m$,
   2. $x_n>f(n)$ ou $y_n<f(n)$, e
   3. $y_n-x_n<1/n$.

   Assuma isso $x_i$ e $y_i$ são dados para todos $i<n$. Então nós temos também$f(n)>x_{n-1}$ ou $f(n)<y_{n-1}$. (Isso segue do seguinte teorema construtivamente válido: se$x<y$ são reais, então $z<y$ ou $x<z$.)

   Suponha que temos $f(n)>x_{n-1}$. (O caso restante é análogo.) Escolha um número racional$x_n$ e $y_n$ de tal modo que $x_{n-1}<x_n<\min(a_n,y_{n-1})$ e $x_n<y_n<\min(a_n,y_{n-1},x_n+1/n)$. Então, as desigualdades mencionadas são satisfeitas.

   Conseqüentemente $(x_n)$forma uma sequência de Cauchy de números racionais. Deixei$x$ ser um limite de $(x_n)$, então $x$ satisfaz as propriedades desejadas.

   Observe que a prova acima faz uso da escolha contável que o bispo aceitou. Tanto quanto eu sei, está em aberto se$\mathbb{R}$é contável ou não sem a escolha contável. Além disso, observe que$\mathbb{R}$pode ser subcontável , ou seja$\mathbb{R}$pode ser uma imagem de um subconjunto de$\mathbb{N}$. (Infelizmente, esqueci se a subcontabilidade de$\mathbb{R}$ é compatível com $\mathsf{IZF}$, embora eu acredite que seja verdade.)