Berechnungsfolgen von Friedmans (unbeweisbarem) Upper Shift Fixed Point-Theorem?

Harvey Friedman zeigte, dass es ein ordentliches Fixpunktergebnis gibt, das in ZFC nicht bewiesen werden kann (die übliche Zermelo-Frankel-Mengenlehre mit dem Axiom of Choice). Viele moderne Logiken basieren auf Fixpunktoperatoren, daher habe ich mich gefragt: Gibt es irgendwelche bekannten Konsequenzen des Upper Shift Fixed Point-Theorems für die theoretische Informatik?

Unbeweisbar Ober Shift - Fixpunktsatz
Für alle $R \in \text{SDOI}(Q^k,Q^k)$ , einige $A = \text{cube}(A,0) \setminus R[A]$ enthält $\text{us}(A)$ .

Das USFP-Theorem scheint eine $\Pi^1_1$ Aussage zu sein, daher könnte es der Berechenbarkeit "nahe genug" sein (z. B. die Überprüfung des Nichtisomorphismus automatischer Strukturen), um die theoretische Informatik zu beeinflussen.

Der Vollständigkeit halber hier die Definitionen aus Friedmans MIT-Vortrag vom November 2009 (siehe auch den Entwurf eines Buches zur "Booleschen Beziehungstheorie" ).

$Q$ ist die Menge der rationalen Zahlen. $x, y \in Q^k$ sindOrdnungsäquivalente,wenn immer dann, wenn$1 \le i,j \le k$ ist,$x_i \lt x_j \Leftrightarrow y_i \lt y_j$ . Wenn$x \in Q^k$ ist, wird die mit us ( x ) bezeichneteobere Verschiebungvon erhalten, indem zu jeder nicht negativen Koordinate von x 1 addiert wird. Eine Beziehung$x$$\text{us}(x)$$x$ istinvariant Ordnungwenn für jede Ordnunginvariantäquivalent x , y ∈ Q k giltdass x ∈ A ⇔ y ∈ A . Eine Beziehung R ⊆ Q k × Q k ist eine Ordnungsinvariante, wenn R als Teilmenge von Q 2 k eine Ordnungsinvariante ist, unddominiert streng,wenn für alle x , y ∈ Q k, wann immer R $A \subseteq Q^k$ $x,y \in Q^k$$x \in A \Leftrightarrow y \in A$$R \subseteq Q^k \times Q^k$$R$$Q^{2k}$$x,y \in Q^k$$R(x,y)$A Q k R [ A ] { y | ∃ x ∈ A R ( x , y ) } $\max(x) \lt \max(y)$$A$$Q^k$$R[A]$$\{ y | \exists x \in A R(x,y)\}$$A$Würfel ( A , 0 ) B k 0 ∈ B A B $\text{us}(A) = \{\text{us}(x) | x \in A\}$$\text{cube}(A,0)$$B^k$$0 \in B$$A$$B^k$R ≤ Q k × Q $\text{SDOI}(Q^k,Q^k)$$R \subseteq Q^k \times Q^k$

Edit: Wie Dömötör Pálvölgyi in Kommentaren ausführt, scheint es ein Gegenbeispiel zu sein , und als die übliche Reihenfolge für Rationals zu nehmen. Erstens kann die Menge nicht leer sein, da dann auch leer ist und dann durch die Würfelbedingung 0 enthalten müsste, ein Widerspruch. Wenn die nicht leere Menge ein Infimum hat, kann sie keine größeren Rationalen als diese enthalten, daher muss es sich um einen Singleton handeln, der der Bedingung der oberen Verschiebung widerspricht. Wenn andererseits kein Infimum hat, dann ist also muss leer sein, ein Widerspruch. R A R [ A ] A A A R [ A ] = Q $k=1$$R$$A$$R[A]$$A$$A$$A$$R[A] = Q$$A$Gibt es Kommentare dazu, ob es versteckte, nicht offensichtliche Definitionsprobleme gibt, wie zum Beispiel ein implizites, nicht standardmäßiges Modell der Rationalen?

Weitere Bearbeitung: Das obige Argument ist ungefähr richtig, aber bei der Anwendung der oberen Schicht falsch. Dieser Operator gilt nur für nicht negative Koordinaten. Wenn Sie also als negative Singleton-Menge festlegen, erhalten Sie wie gewünscht einen festen Punkt. Mit anderen Worten, wenn ist eine Lösung, und es gibt keine anderen Lösungen.m < 0 A = { m $A$$m < 0$$A = \{m\}$

Ich kenne keine Konsequenzen dieses speziellen Theorems, aber Normalisierungsbeweise für Lambda-Kalküle wie die Kalkulation induktiver Konstruktionen beruhen auf großen Kardinalaxiomen - obwohl die Menge der Lambda-Terme so zählbar ist, wie Sie möchten.

Ich denke, der beste Weg, um die rechnerische Bedeutung satztheoretischer Axiome zu verstehen, die die Existenz großer Kardinäle behaupten, besteht darin, die Mengenlehre als einen Weg zu betrachten, die Theorie der Graphen zu formulieren. Das heißt, ein Modell einer Menge ist eine Sammlung von Elementen, die mit einer binären Beziehung ausgestattet sind, die zur Interpretation der Zugehörigkeit verwendet wird. Dann sagen Ihnen die Axiome der Mengenlehre die Eigenschaften der Zugehörigkeitsbeziehung, einschließlich der Art und Weise, wie Sie aus alten neue Mengen bilden können. Insbesondere bedeutet das Axiom der Gründung, dass die Zugehörigkeitsbeziehung begründet ist (dh sie hat keine unendlichen absteigenden Ketten). Diese Begründetheit bedeutet wiederum, dass Sie einen Beendigungsnachweis haben, wenn Sie die Ausführungszustände eines Programms mit der transitiven Zugehörigkeit der Elemente einer Menge in Einklang bringen können.

Eine Behauptung, dass eine "große" Menge existiert, hat eine rechnerische Auszahlung als Behauptung, dass eine bestimmte Klasse von Schleifen in einer allgemeinen rekursiven Programmiersprache endet. Diese Interpretation funktioniert einheitlich, vom einfachen alten Axiom der Unendlichkeit (das die natürliche Iteration von Zahlen rechtfertigt) bis hin zu großen Kardinalaxiomen.

Sind diese Axiome wahr ? Wenn das Axiom falsch ist, können Sie in einer dieser Klassen ein Programm finden, das nicht beendet wird. Aber wenn es wahr ist, werden wir dank des Halting-Theorems niemals sicher sein. Alles von der natürlichen Zahleninduktion an ist eine Frage der wissenschaftlichen Induktion, die immer durch Experimente verfälscht werden kann - Edward Nelson hat bekanntlich gehofft, zu beweisen, dass Potenzierung eine Teilfunktion ist!