Inwieweit kann die Mathematik von Real auf berechenbare Real angewendet werden?

16

Gibt es einen allgemeinen Satz, der besagt, dass die bekanntesten Ergebnisse in Bezug auf die Verwendung reeller Zahlen tatsächlich verwendet werden können, wenn nur berechenbare reelle Zahlen betrachtet werden? Oder gibt es eine ordnungsgemäße Charakterisierung der Ergebnisse, die gültig bleiben, wenn nur die berechenbaren Realwerte berücksichtigt werden? Eine Nebenfrage ist, ob Ergebnisse in Bezug auf berechenbare reelle Zahlen bewiesen werden können, ohne dass alle reellen Zahlen berücksichtigt werden müssen, oder alles, was nicht berechenbar ist. Ich denke speziell an die Analysis und die mathematische Analyse, aber meine Frage ist in keiner Weise darauf beschränkt.

Ich nehme an, dass es eine Hierarchie von berechenbaren Reals gibt, die der Turing-Hierarchie entspricht (Ist das richtig?). Abstrahierter gibt es dann eine abstrakte Theorie des Real (ich bin nicht sicher, wie die Terminologie lauten soll), für die eine Reihe von Ergebnissen bewiesen werden konnte, die für die traditionellen reellen Zahlen, aber auch für berechenbare Realzahlen und gelten würden auf eine beliebige Ebene der Turing-Hierarchie berechenbarer Reals, falls vorhanden.

Dann könnte meine Frage möglicherweise lauten: Gibt es eine Charakterisierung von Ergebnissen, die in der abstrakten Realtheorie angewendet werden, wenn sie für traditionelle Realwerte bewiesen wurden? Und könnten diese Ergebnisse direkt in der abstrakten Theorie bewiesen werden, ohne die traditionellen Realitäten zu berücksichtigen?

Ich bin auch daran interessiert zu verstehen, wie und wann diese Theorien der Realitäten voneinander abweichen.

PS Ich weiß nicht, wo das in meine Frage passt. Ich erkannte, dass ein Großteil der Mathematik auf den Reals mit Topologie verallgemeinert wurde. So kann es sein, dass die Antwort auf meine Frage oder einen Teil davon dort zu finden ist. Möglicherweise steckt aber noch mehr dahinter.

babou
quelle

Antworten:

16

Die reellen Zahlen können auf verschiedene Arten charakterisiert werden. Arbeiten wir mit dem Cauchy-vollständigen archimedischen geordneten Feld . (Wir müssen etwas vorsichtig sein, wie genau wir dies sagen, siehe Definition 11.2.7 und Definition 11.2.10 des HoTT-Buches .)

Der folgende Satz gilt für alle Topos (ein Modell der übergeordneten intuitionistischen Logik):

Theorem: Es gibt ein Cauchy-vollständiges archimedisches geordnetes Feld, und tatsächlich sind zwei solcher Felder kanonisch isomorph.

Darüber hinaus können wir in der intuitionistischen Logik (nicht zu verwechseln mit Intuitionismus ) eine Menge realer Analysen durchführen (Sequenzen und Grenzen, Ableitungen, Integrale, Kontinuität, einheitliche Kontinuität usw.), die dann in jedem Topos gültig sind. Wenn wir die Topos von Mengen nehmen, erhalten wir die übliche reale Analyse. Durch die Aufnahme eines anderen Topos erhalten wir eine andere Art der reellen Analyse - und es gibt einen Topos, der genau die berechenbaren Reals und die berechenbaren reellen Analysen liefert.

Dies ist natürlich der effektive Topos , in dem die reellen Zahlen die berechenbaren reellen Zahlen sind (der Grund dafür ist vage gesagt, dass der effektive Topos so konstruiert ist, dass alles in ihm automatisch berechenbar ist). Die Antwort auf Ihre Frage lautet

Definitionen, Konstruktionen und Theoreme in der intuitionistischen Realanalyse werden automatisch in Definitionen, Konstruktionen und Theoreme über berechenbare Realitäten übersetzt, wenn wir sie in den effektiven Topos interpretieren.

Beispielsweise ist der Satz "jede gleichmäßig stetige Abbildung erreicht ihr Supremum" intuitionistisch gültig. Wenn wir es in den effektiven Topos interpretieren, erhalten wir die entsprechende Version für berechenbare Karten auf berechenbaren Reals, die berechenbar einheitlich fortlaufend sind.f:[0,1]R

Sie fragen auch nach der "Divergenz" zwischen der realen Analyse und ihrer berechenbaren Version. Die Antwort ist, dass Ergebnisse, die auf dem Gesetz der ausgeschlossenen Mitte oder dem Axiom der Wahl beruhen (obwohl die zählbare Wahl in Ordnung ist), nicht intuitiv sind und daher nicht in den effektiven Topos validiert werden können. Wir sollten jedoch beachten, dass (entgegen der allgemeinen Meinung) die meisten Analysen intuitiv durchgeführt werden können.

Der effektive Topos ist nur eine von vielen Realisierbarkeitstoposen . Wenn wir die intuitionistische Analyse in anderen Realisierbarkeitsthemen interpretieren, erhalten wir alternative Modelle für die Berechenbarkeit von reellen Zahlen, einschließlich der Berechnung mit Orakeln, auf die Sie anspielen. Die "relativen Kleene-Funktion-Realisierbarkeitstopos" (was auch immer das ist) geben die sogenannte Typ-II-Berechenbarkeit auf Reals, in denen berechenbare Karten auf allen Reals arbeiten, nicht nur auf den berechenbaren.

Ich habe dies einmal in den Anmerkungen "Realisierbarkeit als Verbindung zwischen berechenbarer und konstruktiver Mathematik" und vorher in meiner Doktorarbeit versucht zu erklären . These .

Andrej Bauer
quelle
[0,1]
3
[0,1][0,1][0,1]
Andrej Bauer
1
[0,1][0,1]
Ich habe eine Anmerkung hinzugefügt, dass intuitionistische Logik nicht dasselbe ist wie Intuitionismus. Auch die Wikipedia-Seite über intuitionistische Logik ist schrecklich.
Andrej Bauer
1
@ Kaveh: Ja, wir könnten uns eine bessere Terminologie wünschen ...
Andrej Bauer