Der arithmetisierte Vollständigkeitssatz
In Kikuchis Aufsatz Kolmogorovs Komplexität und dem zweiten Unvollständigkeitssatz gibt er den "arithmetisierten Vollständigkeitssatz" wie folgt an:
Lassen $T$ eine rekursiv axiomatisierbare Theorie in einer Sprache sein $\mathcal{L}$, $C$ eine Menge neuer Konstanten sein und $\overline{\mathcal{L}}=\mathcal{L}\cup C$. Wir sagen eine Formel$\phi(x)$ im $\mathcal{L}_{A}$ definiert ein Modell von $T$ in einer Theorie $S$ im $\mathcal{L}_{A}$ wenn wir innerhalb beweisen können $S$ dass das Set
$$ \{ \sigma : \text{$\ sigma$ is a sentence in $\ overline {\ mathcal {L}}$ that satisfies $\ phi (\ ulcorner \ sigma \ urcorner)$} \} $$
bildet ein elementares Diagramm eines Modells von $T$ mit einem Universum aus $C$.
Satz 4.1. (Der arithmetisierte Vollständigkeitssatz). Es gibt eine Formel$\text{Tr}_{T}({\ulcorner}x{\urcorner})$ im $\mathcal{L}_{A}$ [die Sprache der Arithmetik], die ein Modell von definiert $T$ im $\text{PA} + \text{Con}(T)$ , wo $\text{Con}(T)$ ist ein Satz in $\mathcal{L}_{A}$ das bedeutet $T$ ist konsistent.
Es gibt mehrere Aspekte dieses Satzes, die ich nicht verstehe:
Der Begriff einer Formel, die ein Modell von definiert $T$ im $\text{PA} + \text{Con}(T)$ beinhaltet das Set $ \{ \sigma : \text{$\ sigma$ is a sentence in $\ overline {\ mathcal {L}}$ that satisfies $\ phi (\ ulcorner \ sigma \ urcorner)$} \} $. Ich weiß nicht, wie ich das formalisieren soll$\text{PA}$, geschweige denn etwas darüber zu beweisen.
Das gleiche gilt für das Gespräch über Modelle von $T$. Sagen$T = \text{ZFC}$Wie kann man dann überhaupt in der Sprache der Arithmetik sagen, dass es ein Modell von gibt? $T$ mit so und so Eigenschaft (sein elementares Diagramm ist die obige Menge und sein Universum)?
Eine andere Art von Frage: Wozu dient dieser Satz (allgemein über das erwähnte Papier hinaus)? Warum heißt es arithmetisierter Vollständigkeitssatz?
Antworten
Re: $(1)$Hier gibt es weniger als man denkt. Der entscheidende Punkt ist, dass wir eine Formel erstellen können$\theta$ welches die Menge der Godel-Zahlen von definiert $\overline{\mathcal{L}}$-Sätze; Mit dieser Hand schauen wir uns nur an$$S=\{x: \theta(x)\wedge\phi(x)\}.$$ Das ist ziemlich langweilig definierbar.
Nun, wenn wir das sagen $S$ ist das Elementardiagramm einer Struktur mit Domäne $C$das meinen wir $S$ erfüllt die üblichen Eigenschaften eines Elementardiagramms - und da dies syntaktische Eigenschaften sind, können wir dies über die Godel-Nummerierung ausdrücken $S$hat oder hat sie nicht. Zum Beispiel wollen wir Folgendes:
Wenn $\ulcorner\sigma_0\urcorner$, $\ulcorner\sigma_1\urcorner\in S$ dann $\ulcorner\sigma_0\wedge\sigma_1\urcorner\in S$.
Wenn $\ulcorner \exists x\sigma(x)\urcorner\in S$ dann für einige $c\in C$ wir haben $\ulcorner\sigma(c)\urcorner\in S$. (Dies spricht das "mit Universum aus$C$" bisschen.)
$\ulcorner\perp\urcorner\not\in S$.
Etwas genauer haben wir primitive rekursive Funktionen, die z. B. der Konjunktion und der existenziellen Quantifizierung in Bezug auf eine feste Variable entsprechen, und die ersten beiden obigen Aufzählungspunkte entsprechen geeigneten Abschluss- / Existenzbedingungen für $S$in Bezug auf diese Funktionen. Der dritte Aufzählungspunkt verhindert inzwischen Trivialität.
Grundsätzlich ist der Punkt, dass die Eigenschaft, das Elementardiagramm einer Struktur mit Domäne zu sein $\mathbb{N}$ ist ausdrucksfähig erster Ordnung (weil es sich um "lokale Schließungs- / Existenz- / Nichtexistenzbedingungen" gemäß den obigen Angaben handelt).
Re: $(2)$intuitiv geht es darum, dass es sich nicht um willkürliche Modelle von z $\mathsf{ZFC}$, aber nur diejenigen mit Domain $\mathbb{N}$. Eine Struktur mit Domain$\mathbb{N}$ wird vollständig durch einen einzigen Satz natürlicher Zahlen beschrieben $X$, und "$X$ ist das Atomdiagramm eines Modells von $\mathsf{ZFC}$"ist nach obiger erster Ordnung ausdrückbar: wir sagen nur"$X$ hat die oben genannten grundlegenden syntaktischen Eigenschaften und jeweils $\mathsf{ZFC}$-axiome ist in $X$. "
Ich denke, dies könnte mysteriöser werden, weil wir normalerweise an Modelle von denken $\mathsf{ZFC}$als sehr kompliziert und definitiv ohne Domain$\mathbb{N}$. Aber per Abwärts Lowenheim-Skolem,$\mathsf{ZFC}$(vorausgesetzt , es überhaupt konsistent ist) auch hat viele Modelle mit Domain$\mathbb{N}$. Dies sind die Modelle, die wir bei diesem Ansatz berücksichtigen können.
Re: $(3)$Der Punkt ist, dass die übliche Formulierung des Vollständigkeitssatzes
Jede konsistente Theorie hat ein Modell
ist im Kontext der Arithmetik total verrückt. Grundsätzlich können wir nur direkt über endliche Mengen in der Sprache der Arithmetik sprechen. Wenn wir also den Satz "Presburger-Arithmetik hat keine Modelle" naiv "arithmetisch ausdrücken", erhalten wir etwas Wahres.
(Siehe zum Beispiel die Ackermann-Interpretation . Wir können von (sagen wir)$\mathsf{PA}$ zu einer angemessen äquivalenten Mengenlehre, aber diese Theorie beweist "Jede Menge ist endlich".)
Wenn wir also wollen, dass eine Version des Vollständigkeitssatzes in einer Theorie der Arithmetik enthalten ist, müssen ihre "Modelle" aus Beziehungen über das gesamte Universum bestehen; und natürlich müssen sie aus definierbaren Beziehungen bestehen, da wir intern nicht über undefinierbare Beziehungen sprechen können.
Eine andere Möglichkeit wäre die Verwendung konservativer Erweiterungen, die direkt über unendliche Mengen sprechen können. Dies ist zum Beispiel der Ansatz hier . In allen Kontexten, in denen ich mit diesem Ansatz gespielt habe, funktioniert er und deshalb bevorzuge ich ihn im Allgemeinen. Das gesagt,$(i)$ Wenn ich mich richtig erinnere, gibt es Situationen, in denen dieser Ansatz entweder ärgerlich böse ist oder wertvolle Informationen verdeckt (ich denke, dies tritt bei sehr schwachen Theorien der Arithmetik auf) und $(ii)$ Die Tatsache, dass wir einen Vollständigkeitssatz nur in der Sprache der Arithmetik erster Ordnung erhalten können, ist an sich schon interessant.