Definition

Unter einer Theorie versteht man eine echte Teilmenge ${\displaystyle T}$ von Sätzen einer Sprache ${\displaystyle L_{I}^{S}}$ der Prädikatenlogik erster Stufe, die bezüglich der Folgerungsrelation ${\displaystyle \vdash }$ (deduktiv) abgeschlossen ist, das heißt, aus ${\displaystyle T\vdash \alpha }$ folgt bereits ${\displaystyle \alpha \in T}$ für alle Sätze ${\displaystyle \alpha }$ der Sprache. Ist ${\displaystyle {\mathcal {A}}}$ ein Modell, so ist offenbar ${\displaystyle T=Th({\mathcal {A}}):=\{\alpha$ ;\,{\mathcal {A}}\vDash \alpha \}} eine Theorie. Man nennt eine Theorie vollständig, wenn sie für jeden Satz ${\displaystyle \alpha }$ entweder diesen oder seine Negation ${\displaystyle \neg \alpha }$ enthält. In diesem Sinne lässt eine vollständige Theorie keine Fragen der Form „gilt ${\displaystyle \alpha }$ oder ${\displaystyle \neg \alpha }$ in der Theorie ${\displaystyle T}$?“ offen.

Charakterisierung

Folgende Aussagen über einer Theorie ${\displaystyle T\varsubsetneq L_{I}^{S}}$ sind äquivalent:

• ${\displaystyle T}$ ist vollständig, das heißt für alle Sätze ${\displaystyle \alpha }$ gilt ${\displaystyle T\vDash \alpha }$ oder ${\displaystyle T\vDash \neg \alpha }$
• ${\displaystyle T}$ ist maximal, das heißt für alle Theorien ${\displaystyle T_{1}}$ mit ${\displaystyle T\subset T_{1}\varsubsetneq L_{I}^{S}}$ gilt ${\displaystyle T=T_{1}}$.
• Für jedes Modell ${\displaystyle {\mathcal {A}}}$ von ${\displaystyle T}$ gilt ${\displaystyle T=Th({\mathcal {A}})}$
• Je zwei Modelle von ${\displaystyle T}$ sind elementar äquivalent.

Beispiele

Es sei ${\displaystyle DO}$ die Theorie der dichten Ordnungen, das heißt die Signatur ist ${\displaystyle S=\{<\}}$ und ${\displaystyle DO}$ ist die Menge aller Sätze aus ${\displaystyle L_{I}^{S}}$, die aus folgenden vier Sätzen (Axiomen der dichten Ordnung) hergeleitet werden können.

• ${\displaystyle \forall x\,\neg (x<x)}$ (Irreflexivität)
• ${\displaystyle \forall x\,y\,z\,(x<y\land y<z\rightarrow x<z)}$ (Transitivität)
• ${\displaystyle \forall x\,y\,(x=y\lor x<y\lor y<x)}$ (Linearität der Ordnung)
• ${\displaystyle \forall x\,y\,(x<y\rightarrow \exists z\,(x<z\land z<y))}$ (Dichtheit)

Diese Theorie ist nicht vollständig, denn die Frage, ob es kleinste oder größte Elemente gibt, bleibt offen. Erweitert man ${\displaystyle DO}$ zur Theorie ${\displaystyle DO_{00}}$ aller Sätze, die aus obigen vier und den zwei Sätzen

• ${\displaystyle \forall x\,\exists y\,(y<x)}$ (es gibt kein kleinstes Element)
• ${\displaystyle \forall x\,\exists y\,(x<y)}$ (es gibt kein größtes Element),

so erhält man eine vollständige Theorie, denn mit Hilfe des Satzes von Fraïssé kann man die elementare Äquivalenz von je zwei Modellen nachweisen, wie dort ausgeführt ist. Dies hätte man auch leicht mit dem Kriterium von Vaught nachweisen können; dieses liefert weitere dort behandelte Beispiele wie die Theorie der algebraisch abgeschlossenen Körper. Die Quantorenelimination ist ein weiteres Verfahren, mit dem man Vollständigkeitsbeweise führen kann.

Entscheidbarkeit

Vollständige Theorien mit abzählbarer Signatur und einer rekursiv aufzählbaren Axiomatisierung sind entscheidbar. Um dies einzusehen, setze man eine Aufzählung sämtlicher Sätze der vorgegebenen Theorie in Gang, indem man systematisch alle Beweise erzeugt. Ist ${\displaystyle \alpha }$ ein Satz, so erscheint in dieser Aufzählung irgendwann ${\displaystyle \alpha }$ oder ${\displaystyle \neg \alpha }$, denn die Theorie ist ja vollständig. Dann breche man die Aufzählung ab und antworte ${\displaystyle \alpha \in T}$, falls ${\displaystyle \alpha }$ in der Aufzählung erschienen ist, anderenfalls antworte man ${\displaystyle \alpha \notin T}$. Dieser Algorithmus entscheidet offenbar die Frage, ob ${\displaystyle \alpha \in T}$.