¿En qué medida se pueden aplicar las matemáticas de Reals a Reales Computables?

16

¿Existe un teorema general que establezca, con una desinfección adecuada, que los resultados más conocidos con respecto al uso de números reales se pueden usar cuando se consideran solo reales computables? ¿O hay una caracterización adecuada de los resultados que siguen siendo válidos cuando se consideran solo los reales computables? Una pregunta secundaria es si los resultados relativos a los reales computables se pueden probar sin tener que considerar todos los reales o cualquier cosa que no sea computable. Estoy pensando específicamente en el cálculo y el análisis matemático, pero mi pregunta no se limita de ninguna manera a eso.

En realidad, supongo que hay una jerarquía de reales computables correspondientes a la jerarquía de Turing (¿es eso correcto?). Entonces, más abstractamente, ¿existe una teoría abstracta de lo real (no estoy seguro de cuál debería ser la terminología), para la cual se podrían probar varios resultados, que se aplicarían a los números reales tradicionales, pero también a los reales computables, y a cualquier nivel de la jerarquía de Turing de reales computables, si existe.

Entonces, mi pregunta podría formularse como: ¿Existe una caracterización de los resultados que se aplicarán en la teoría abstracta de los reales cuando se hayan probado para los reales tradicionales? Y, ¿podrían demostrarse estos resultados directamente en la teoría abstracta, sin considerar los reales tradicionales?

También estoy interesado en comprender cómo y cuándo divergen estas teorías de los reales.

PD: No sé dónde encajar esto en mi pregunta. Me di cuenta de que una gran parte de las matemáticas en los reales se han generalizado con la topología. Entonces puede ser que la respuesta a mi pregunta, o parte de ella, se pueda encontrar allí. Pero también puede haber más.

babou
fuente

Respuestas:

16

Los números reales se pueden caracterizar de dos maneras, trabajemos con el campo ordenado arquidénico completo de Cauchy . (Necesitamos ser un poco cuidadosos de cómo exactamente decimos esto, ver la Definición 11.2.7 y la Definición 11.2.10 del libro HoTT ).

El siguiente teorema es válido en cualquier topos (un modelo de lógica intuicionista de orden superior):

Teorema: hay un campo ordenado archimedeano completo de Cauchy y, de hecho, cualquiera de estos dos campos es canónicamente isomorfo.

Además, en la lógica intuicionista (que no debe confundirse con el intuicionismo ) podemos hacer muchos análisis reales (secuencias y límites, derivadas, integrales, continuidad, continuidad uniforme, etc.) que luego es válido en cualquier topos. Si tomamos los topos de los conjuntos, obtenemos el análisis real habitual. Al tomar un topos diferente, obtenemos un tipo de análisis real diferente, y hay un topos que produce precisamente los reales computables y el análisis real computable.

Por supuesto, este es el topos efectivo , en el que los números reales son los reales computables (hablando vagamente, la razón de esto es que el topos efectivo está construido de tal manera que todo en él es automáticamente computable). La respuesta a tu pregunta es

Las definiciones, construcciones y teoremas en el análisis real intuicionista se traducen automáticamente en definiciones, construcciones y teoremas sobre reales computables cuando los interpretamos en los topos efectivos.

Por ejemplo, el teorema "cada mapa uniformemente continuo alcanza su supremum" es intuitivamente válido. Cuando lo interpretamos en los topos efectivos, obtenemos la versión correspondiente para mapas computables en reales computables que son computablemente continuos de manera uniforme.F:[0 0,1]R

También pregunta sobre la "divergencia" entre el análisis real y su versión computable. La respuesta es que los resultados que se basan en la ley del medio excluido o el axioma de elección (aunque la elección contable está bien) no son intuicionistas y, por lo tanto, no pueden validarse en los topos efectivos. Sin embargo, debemos tener en cuenta que (al contrario de la opinión popular) la mayoría de los análisis se pueden hacer intuitivamente.

El topos efectivo es solo uno de los muchos topos de realizabilidad . Cuando interpretamos el análisis intuicionista en otros propósitos de realizabilidad, obtenemos modelos alternativos de computabilidad de números reales, incluido el cálculo con oráculos a los que usted alude. La "relativa topos de realizabilidad de la función de Kleene" (sea lo que sea) da la llamada computabilidad de Tipo II en reales en los que los mapas computables operan en todos los reales, no solo en los computables.

Traté de explicar esto una vez en las notas "Realizabilidad como la conexión entre matemática computable y constructiva" , y antes de eso en mi Ph.D. tesis .

Andrej Bauer
fuente
[0 0,1]
3
[0 0,1][0 0,1][0 0,1]
Andrej Bauer
1
[0 0,1][0 0,1]
Agregué una nota sobre el hecho de que la lógica intuicionista no es lo mismo que el intuicionismo. Además, la página de Wikipedia sobre lógica intuicionista es horrible.
Andrej Bauer
1
@Kaveh: sí, podríamos desear una mejor terminología ...
Andrej Bauer