¿Es semicomputable cualquier secuencia de Cauchy para la terminación de racionales?

Question

Para la definición de un real semicomputable, véase Introducción a la complejidad de Kolmogorov y sus aplicaciones por Li y Vitanyi (1997). De hecho, no es cierto que toda secuencia de Cauchy para completar racionales sea semicomputable, no podemos completar racionales mediante secuencias de Cauchy semicomputables.

Mi pregunta:

1. ¿cómo podríamos, de una forma constructivista basada en las secuencias de Cauchy, completar el sistema de números racionales? Concretamente, ¿cómo superar el problema no computable de algunas (de hecho, incontables) secuencias de Cauchy con las que completar el sistema racional?

2. Dado que completamos el sistema de números racionales de varias formas como secuencias de Cauchy, cortes de Dedekind o incluso por fracciones continuas, ¿cuál es la idea común (de aproximación, etc) entre ellas?

Answer 1

Las construcciones de números reales se dividen a grandes rasgos en dos clases: Compleciones de tipo Dedekind mediante cortes ("reales de Dedekind"), y compleciones de tipo Cauchy mediante secuencias de Cauchy ("reales de Cauchy"). Existe una teoría bien entendida de estas dos clases en matemáticas constructivas, y las conexiones entre las distintas construcciones son bien conocidas.

En general, los reales de Cauchy forman un subcampo de los reales de Dedekind. Los reales de Dedekind y de Cauchy coinciden si elección contable o medio excluido pero puede ser diferente. Encontrará más información al respecto en la obra de Troelstra y van Dalen Constructivismo en matemáticas, Vol. 1 .

Preguntas concretamente por la terminación de Cauchy de los racionales y el "problema no computable". No existe tal problema. Cuando trabajamos en lógica intuicionista, simplemente construimos los reales de Cauchy como hacemos siempre:

1. Empezar con números racionales $\mathbb{Q}$ .
2. Utilice la definición habitual de Secuencia de Cauchy .
3. Sea $\mathcal{C}$ sea el conjunto de todas las sucesiones racionales de Cauchy.
4. Definir dos secuencias de Cauchy $(q_n)_n$ y $(r_n)_n$ ser equivalente , escrito $(q_n)_n \approx (r_n)_n$ cuando para cada $\epsilon > 0$ hay $n \in \mathbb{N}$ tal que para todo $m, k \geq n$ tenemos $|q_m - r_k| < \epsilon$ .
5. Sea $\mathbb{R}$ sea el cociente $\mathcal{C}/{\approx}$ .

Podemos demostrar, aún trabajando en lógica intuicionista, que $\mathbb{R}$ forma un campo ordenado arquimediano (aunque los axiomas de orden deben formularse con cuidado). Si tenemos elección contable (que es lo que suele ocurrir en las matemáticas constructivas), también podemos demostrar que $\mathbb{R}$ es Cauchy completo. Obtenemos toda la estructura habitual.

Lo importante es comprender que cuando trabajamos de forma constructiva no hablamos de objetos computables o no computables . Simplemente hacemos matemáticas como de costumbre, excepto que no asumimos la ley del medio excluido.

Las preguntas sobre la computabilidad y la no computabilidad se hacen posibles cuando consideramos modelos de las matemáticas constructivas. Examinemos varios modelos y veamos cómo funcionan en ellos los reales de Cauchy:

1. Teoría clásica de conjuntos: las matemáticas clásicas son un caso especial de las matemáticas constructivas, por lo que todo sigue igual. Hay reales no computables y secuencias de Cauchy no computables.

2. El topos efectivo En este modelo todo es computable. El objeto $\mathbb{R}$ consiste en reales computables, y sólo existen secuencias de Cauchy computables. Obsérvese que "secuencia de Cauchy computable" significa dos cosas : que la sucesión es computable y que "es Cauchy" también lo es.

3. El topos de la realizabilidad relativa $\mathrm{RT}(K_2, K_2^{\mathrm{eff}})$ sobre la segunda álgebra de Kleene y su subálgebra computable. No es importante cuáles son los detalles de este topos pero lo que obtenemos es: el objeto $\mathbb{R}$ consiste en todos reales, el objeto $\mathcal{C}$ de secuencias de Cauchy consiste en todas las secuencias de Cauchy, pero todas las operaciones del topos son computables. (¡Sí, es posible calcular con reales no computables!)

Hay muchos otros modelos, pero siempre ocurre lo mismo: lo que son los números reales depende de lo que son las secuencias de Cauchy, y eso depende de los detalles del modelo. En todos los casos, las cosas encajan: no se puede tener un modelo con secuencias de Cauchy no computables y sólo números reales computables.

Answer 2

Me pregunto si existen teorías constructivas de lo real que se basen en la secuencia de Cauchy, en concreto, cómo superar el problema no computable de algunas (de hecho, incontables) secuencias de Cauchy para completar el sistema racional.

Sí, hay teorías constructivas de la recta real que utilizan una forma de secuencias de Cauchy. En general, estas teorías no demostrarán que todo número real es computable. La suposición de que todo número real es computable es una forma de lo que se denomina La tesis de Church en ese contexto (no es exactamente lo mismo que la tesis habitual de Church-Turing).

Un ejemplo es el sistema constructivo utilizado por Bishop, denominado BISH en Variedades de las matemáticas constructivas de Bridges y Richman (1987). En BISH, un número real se toma como una secuencia de Cauchy de racionales con un módulo fijo de convergencia. Éstas se denominan "secuencias de Cauchy de convergencia rápida" en algunos contextos, como en el libro de Simpson sobre matemáticas inversas. Así que podríamos suponer, por ejemplo, que si tomamos $\epsilon = 1/m$ en la definición de una sucesión de Cauchy entonces podemos tomar $N$ ser simplemente $m+1$ .

BISH es compatible con la suposición de que todo número real es computable, pero al mismo tiempo su sistema no puede demostrar que todo número real sea computable. BISH puede demostrar que no existe una única secuencia $(x_1, x_2, \ldots)$ que contiene todos los números reales, y por lo tanto demuestra que los reales son incontables en ese sentido.

Quizá parte de la intuición sea que, aunque un sistema constructivo no pueda pruebe que "todo número real es computable", sigue siendo probable que si se construye un número real específico sin ninguna suposición, ese número real será computable (este tipo de metateorema puede demostrarse a menudo sobre un sistema constructivo formal utilizando el método " realizabilidad ").

Además, si un número real se genera en un sistema constructivo utilizando algunas suposiciones adicionales, a menudo se dará el caso de que si los objetos de la suposición son todos computables, entonces el número real que se está generando también será computable. Así pues, todos los números reales concretos que se encuentren en la práctica en estas teorías serán computables, aunque la teoría no pueda pruebe que todo número real es computable.

Uno de los puntos fuertes de no demostrar que todo número real es computable es que los sistemas constructivos como el de Bishop son compatibles con las matemáticas clásicas: cualquier demostración en el sistema de Bishop es también una demostración clásicamente correcta. Por supuesto, no existe ninguna prueba clásicamente correcta de que todos los números reales sean computables, por lo que cualquier sistema constructivo que pueda demostrarlo será incompatible en algunos casos con el razonamiento clásico.