Vergleich der Komplexität der Kolmogorov-Theorien

Chaitins Unvollständigkeitssatz besagt, dass keine hinreichend starke Theorie der Arithmetik beweisen kann, $K(s) > L$wobei $K(s)$ die Kolmogorov-Komplexität der Zeichenkette und eine hinreichend große Konstante ist. ist ausreichend groß, wenn es größer ist als die Größe in Bits einer Prüfmaschine (PCM). Ein PCM für Theorie T verwendet eine als Ganzzahl codierte Zeichenfolge als Eingabe und gibt eine 1 aus, wenn die Zeichenfolge ein gültiger Beweis in der Sprache von T ist .L $s$$L$$L$$T$$T$

Es sei angenommen , dass $L(T) > |PCM_T|$für Theorie $T$ ist eine obere für die Komplexität der gebundenen $T$ . Betrachten Sie die folgende Theorienhierarchie: Die Basistheorie sei Robinson-Arithmetik ( $Q$ ). Augmentiere $Q$ mit zunehmend stärkeren Axiomen der polynombedingten Induktion. Sei $Q^*$ die mit $Q$ und einem dieser beschränkten Induktionsaxiome beweisbare Theorie der Theoreme . Angenommen, wir können $L(Q)$ und durch Definieren von PCMs für jede Theorie.$L({Q^*})$

Ich möchte einen EPCM (Enhanced Proof Checking Machine) für in Betracht ziehen . Diese EPCM nimmt einen String als Eingabe wie ein ECM und hat einen zweiten Eingang, der den Rang und die Ebene einer Untertheorie definiert Q * . Wenn die Eingabezeichenfolge in Q ∗ ein gültiger Beweis ist, durchläuft das EPCM die Schritte des Beweises, um den höchsten Rang und die höchste verwendete Induktionsstufe zu bestimmen. Dieser EPCM schreibt dann eine 1, wenn der Eingabesatz ein gültiger Beweis in der angegebenen Untertheorie von Q ∗ ist .$Q^*$$Q^*$$Q^*$$Q^*$

Ist der von mir beschriebene Enhanced Proof Checker machbar? Wenn ja, wäre die Größe dieses EPCM nicht nur eine Obergrenze für die Komplexität von , sondern auch eine Obergrenze für die Komplexität einer Subtheorie von Q ∗ ?$Q^*$$Q^*$

Ist es vernünftig zu sagen, dass es eine konstante Obergrenze für die Komplexität von und all seinen Untertheorien gibt?$Q^*$

---

Diese Frage wurde von Nelsons fehlgeschlagenem Beweis für die Inkonsistenz der Arithmetik gestellt. Ich habe das vorher nicht erwähnt, weil manche Leute diesen Beweis als störend empfinden. Meine Motivation ist es, eine interessante Frage zu stellen. CSTheory scheint das richtige Forum für diese Frage zu sein. Die Komplexität von und all seinen Untertheorien ist entweder durch eine Konstante begrenzt oder unbegrenzt. Jede Antwort führt zu weiteren Fragen.$Q^*$

Wenn die Komplexität der Unter Theorien unbegrenzt ist , können wir Fragen wie fragen , was ist das schwächste Unter Theorie von komplexer als Q * ? Oder komplexer als PA und ZFC? Das Nachdenken über diese Frage hat mir bereits gezeigt, dass es eine strenge Grenze dafür gibt, wie viel eine Theorie über die Komplexität von Kolmogorov-Strings beweisen kann. Wenn Q ∗ konsistent ist, kann keine seiner Untertheorien K ( s ) > L ( Q ∗ ) für eine beliebige Zeichenkette beweisen . Dies bedeutet, dass selbst wirklich starke Untertheorien nicht beweisen können, dass es komplexere Zeichenfolgen gibt als eine viel schwächere Untertheorie, bei der die schwächere Theorie komplexer ist als $Q^*$$Q^*$$Q^*$$K(s) > L(Q^*)$ .$Q^*$

Ich werde versuchen, eine Antwort auf diese Frage zu geben und einige Unklarheiten hinsichtlich der genauen Form der Frage zu beseitigen.

Der erste Punkt , den ich machen will: die in der Mitteilung der Chaitinsche Konstante ist in der Tat eine Funktion von T . Im absoluten Sinne ist es monoton in der Aussagekraft von T : Wenn L ( T ) die kleinste natürliche Zahl ist, für die T ⊬ K ( s ) ≥ L ( T ) für eine beliebige Zeichenkette s ist , dann ist T ' eine konsistente Theorie stärker als T ( T ⊢ φ impliziert T $L$$T$$T$$L(T)$

$$T\not\vdash K(s)\geq L(T)$$ $s$$T'$$T$$T\vdash\varphi$ für einen beliebigen arithmetischen Satz φ ) dann L ( T ′ ) ≥ L ( T ) . Das Argument ist sehr einfach: Wenn es gibt s , so dass T ⊢ K ( s ) ≥ L dann T ' ⊢ K ( s ) ≥ L durch Hypothese.$T'\vdash\varphi$$\varphi$$L(T')\geq L(T)$$s$$T\vdash K(s)\geq L$$T'\vdash K(s)\geq L$

Dies gilt jedoch nur, wenn die absolute Chaitin-Konstante ist. Insbesondere dann , wenn T ' beweist C o n ( T ) , dann T ' ⊢ ∃ L ∀ s ⌈ T ⊬ K ( ¯ s ) ≥ ¯ L$L(T)$$T'$$\mathrm{Con}(T)$

$$T'\vdash \exists L\forall s\ \lceil T\not\vdash K(\overline{s})\geq \overline{L}\rceil$$

durch Verinnerlichung Chaitins Argument. Jedoch wird ein Beton , für die$l$

$$T'\vdash\forall s\ \lceil T\not\vdash K(\overline{s})\geq\overline{l}\rceil$$

wird im Allgemeinen nicht gleich $L(T)$ . Insbesondere kann es viel größer ist , in der Regel proportional zu der Größe des Beweises von in T $\mathrm{Con}(T)$$T'$ . Dies kann leicht im Beweis des Satzes selbst gesehen werden, der entscheidend von der Konsistenz von abhängt .$T$

So , während Konsistenz des Systems mit beschränkter Induktion nachweisen kann, die Länge dieser Beweise wird immer länger , je näher Sie bekommen Q * in Ausdruckskraft (eine Möglichkeit , die Unvollständigkeitssätze zu verstehen ist , dass die Länge unendlich wird , wenn Sie erreichen Q * , es gibt also keinen endlichen Konsistenzbeweis in Q ∗ selbst). Dies gilt auch für die verschiedenen Obergrenzen der internen L ( T ) s, die Q ∗ für jede Untertheorie beschreiben kann.$Q^*$$Q^*$$Q^*$$Q^*$ $L(T)$$Q^*$

Hier ist die kurze Antwort auf Ihre Frage: ist für alle Untertheorien von Q ∗ einheitlich begrenzt , aber Q ∗ selbst kann nicht zeigen, dass diese Grenze für alle derartigen Untertheorien gilt. Dies war der entscheidende Fehler, den Nelson (unter mehreren Ebenen des Formalismus begraben) begangen hatte und auf den Tao hier hinwies .$L(T)$$Q^*$$Q^*$