Prädikatenlogik: Quantoren, Strukturen und Vollständigkeit

Aus „Alle Menschen sind sterblich“ und „Sokrates ist ein Mensch“ folgt „Sokrates ist sterblich“. Die Aussagenlogik kann dieses Argument nicht erfassen: Sie sieht nur drei Aussagen $A$, $B$, $C$ und kennt keinen Zusammenhang zwischen ihnen. Die Prädikatenlogik baut die Aussagen aus Teilen auf. Sie benutzt Variablen, Eigenschaften und Beziehungen und die Quantoren $\forall$ („für alle“) und $\exists$ („es gibt“). In ihr lassen sich die Axiome der Gruppen, der reellen Zahlen und der Mengenlehre formulieren.

Auf dieser Seite lernst du die Sprache der Logik erster Stufe, ihre Bedeutung in Strukturen, einen Beweiskalkül und den Satz, dass Kalkül und Bedeutung zusammenpassen. Die Grundlagen stehen auf der Seite Aussagenlogik, die Mengenschreibweise auf Mengenlehre.

Die Sprache der Logik erster Stufe

Eine Signatur besteht aus Symbolen: Konstanten ($0$, $1$), Funktionssymbolen ($+$, $·$) und Relationssymbolen ($<$, $\in$). Mit abzählbar vielen Variablen $x,y,z,\dots$ bildet man Terme, zum Beispiel $x+1$ oder $(x+y)·0$. Eine atomare Formel ist eine Gleichung $s=t$ zwischen Termen oder ein Relationssymbol mit Termen, etwa $x<y+1$. Aus Formeln $\phi ,\psi$ entstehen $\neg \phi$, $\phi \wedge \psi$, $\phi \vee \psi$, $\phi \to \psi$ und $\forall x\phi$ sowie $\exists x\phi$.

In $\forall x\phi$ ist $x$ durch den Quantor gebunden. Eine Variable, die nicht gebunden ist, heißt frei. In $\forall y(x<y)$ ist $y$ gebunden und $x$ frei. Eine Formel ohne freie Variablen heißt Satz. Der Satz $\forall x\exists y(x<y)$ sagt: „Zu jedem $x$ gibt es ein größeres $y$.“ Die Gruppenaxiome lassen sich mit der Signatur $(\circ ,e)$ als Sätze schreiben:

• Assoziativität: $\forall x\forall y\forall z((x\circ y)\circ z=x\circ (y\circ z))$,
• neutrales Element: $\forall x(x\circ e=x\wedge e\circ x=x)$,
• Inverse: $\forall x\exists y(x\circ y=e\wedge y\circ x=e)$.

Mit „erster Stufe“ ist gemeint, dass die Quantoren nur über Elemente laufen, nicht über Teilmengen oder Eigenschaften. Die Aussage „jede beschränkte nichtleere Teilmenge von $ℝ$ hat ein Supremum“ spricht über Teilmengen und lässt sich deshalb nicht direkt in erster Stufe schreiben.

Strukturen und Wahrheit

Eine Struktur $𝔄$ besteht aus einer nichtleeren Menge $A$ (dem Träger) und einer Bedeutung für jedes Symbol: eine Funktion für jedes Funktionssymbol, eine Relation für jedes Relationssymbol. Der Satz $\forall x\exists y(x+y=0)$ sagt in $(\mathbb{Z},+,0)$ etwas Wahres, denn zu $x$ ist $-x$ das gewünschte $y$. In $(\mathbb{N},+,0)$ ist er falsch: Zu $x=1$ gibt es keine natürliche Zahl $y$ mit $1+y=0$. Die Wahrheit einer Formel hängt also von der Struktur ab.

Die Wahrheit wird rekursiv erklärt. Ist $\beta$ eine Belegung der freien Variablen mit Elementen von $A$, dann gilt $𝔄\models \forall x\phi$, wenn $\phi$ für jede Änderung von $\beta$ an der Stelle $x$ wahr ist, und $𝔄\models \exists x\phi$, wenn es mindestens eine solche Änderung gibt. Die Junktoren behandelst du wie in der Aussagenlogik. Eine Struktur, in der alle Sätze einer Menge $\Gamma$ wahr sind, heißt Modell von $\Gamma$.

Rechenregeln für Quantoren

Aus den De Morganschen Regeln folgen die Verneinungsregeln: $\neg \forall x\phi \equiv \exists x\neg \phi$ und $\neg \exists x\phi \equiv \forall x\neg \phi$. Die Verneinung vertauscht also die Quantoren. Auf dieser Regel beruht jeder Beweis durch Gegenbeispiel. Die Reihenfolge verschiedener Quantoren darf man nicht vertauschen: In $(\mathbb{N},<)$ ist $\forall x\exists y(x<y)$ wahr (nimm $y=x+1$), aber $\exists y\forall x(x<y)$ falsch, denn es gibt keine größte Zahl. Allgemeingültig ist nur die eine Richtung: $\exists y\forall x\phi \to \forall x\exists y\phi$.

Der Beweiskalkül

Was ein Beweis ist, lässt sich in der Logik genau fassen: als endliche Folge von Formeln, die nach festen Regeln auseinander hervorgehen. Dafür gibt es mehrere gleichwertige Kalküle, etwa den Hilbert-Kalkül, das natürliche Schließen oder den Sequenzenkalkül. Beim natürlichen Schließen gibt es zu jedem Quantor Einführungs- und Beseitigungsregeln:

Das Argument vom Anfang lautet so: Aus $\forall x(M(x)\to S(x))$ („alle Menschen sind sterblich“) folgt mit $\forall$-Beseitigung $M(s)\to S(s)$ für den Namen $s$ (Sokrates), und mit $M(s)$ folgt $S(s)$ nach dem modus ponens. Die Schreibweise $\Gamma ⊢\phi$ bedeutet, dass $\phi$ im Kalkül aus $\Gamma$ ableitbar ist. Ein gut gebauter Kalkül ist korrekt: Aus $\Gamma ⊢\phi$ folgt $\Gamma \models \phi$. Man prüft das Regel für Regel.

Gödels Vollständigkeitssatz

Das ist bemerkenswert: Die Definition von $\models$ spricht über alle Strukturen, ein unüberschaubares Universum. Die Definition von $⊢$ spricht über endliche Ableitungen. Der Satz sagt, dass beide dasselbe meinen: Was in allen Modellen wahr ist, kann man auch beweisen. Beweisidee (nach Henkin, für die schwierige Richtung): Ist $\phi$ nicht aus $\Gamma$ ableitbar, dann ist $\Gamma \cup \{\neg \phi \}$ widerspruchsfrei. Man erweitert diese Menge zu einer maximal widerspruchsfreien Menge, die für jede Existenzaussage einen Zeugen enthält, und baut aus den Termen selbst eine Struktur, in der alles wahr ist. Das ist ein Modell von $\Gamma$, in dem $\phi$ falsch ist, also folgt $\phi$ nicht aus $\Gamma$.

Weil Ableitungen endlich sind, folgt der Kompaktheitssatz: Hat jede endliche Teilmenge von $\Gamma$ ein Modell, dann hat $\Gamma$ ein Modell. Denn gäbe es kein Modell, wäre ein Widerspruch ableitbar, und diese Ableitung benutzt nur endlich viele Formeln aus $\Gamma$.

Anwendung: Es gibt keine Formel für „endlich“. Angenommen, eine Menge von Sätzen $\Gamma$ hätte als Modelle genau die endlichen Gruppen. Füge für jedes $n$ den Satz „es gibt mindestens $n$ verschiedene Elemente“ hinzu. Jede endliche Teilmenge dieser Menge hat ein endliches Modell, also hat die ganze Menge ein Modell, das unendlich ist. Das widerspricht der Annahme. Ebenso gibt es Nichtstandardmodelle der Arithmetik mit „unendlich großen“ Zahlen, die alle Sätze der natürlichen Zahlen erfüllen.

Grenzen: Entscheidbarkeit und Unvollständigkeit

Die Aussagenlogik ist entscheidbar: Mit einer Wahrheitstafel lässt sich jede Formel prüfen. In der Prädikatenlogik ist das nicht mehr so. David Hilbert stellte 1928 die Frage, ob es ein mechanisches Verfahren gibt, das für jede Formel entscheidet, ob sie allgemeingültig ist (das Entscheidungsproblem). Alonzo Church und Alan Turing zeigten 1936 unabhängig voneinander, dass es ein solches Verfahren nicht gibt. Man kann aber alle allgemeingültigen Formeln systematisch aufzählen, indem man alle Ableitungen durchprobiert. Die Allgemeingültigkeit ist daher semientscheidbar. Die Hintergründe stehen auf der Seite Komplexität und Berechenbarkeit.

Vollständigkeit der Logik darf nicht mit Vollständigkeit von Theorien verwechselt werden. Kurt Gödel bewies 1931 mit den Unvollständigkeitssätzen: Jedes widerspruchsfreie, hinreichend starke und aufzählbare Axiomensystem, das die Arithmetik enthält, enthält Sätze, die weder beweisbar noch widerlegbar sind. Die Prädikatenlogik ist also vollständig (jede allgemeingültige Formel ist beweisbar), aber die Peano-Arithmetik ist es nicht.

Übungen

Geschichte: von der Begriffsschrift zu Gödel

Die Quantorenlogik schuf Gottlob Frege in seiner „Begriffsschrift“ von 1879: Er zerlegte Aussagen in Funktion und Argument und führte Quantoren in einer zweidimensionalen Schreibweise ein. Das Werk wurde zunächst kaum beachtet. Die heutige Schreibweise mit $\forall$ und $\exists$ und die klare Trennung von Syntax und Semantik entstanden später. David Hilbert und Wilhelm Ackermann beschrieben 1928 in ihren „Grundzügen der theoretischen Logik“ den Kalkül der Logik erster Stufe und stellten die Frage nach der Vollständigkeit und nach dem Entscheidungsproblem. Kurt Gödel beantwortete die erste Frage 1929 in seiner Dissertation bei Hans Hahn in Wien („Über die Vollständigkeit des Logikkalküls“). Church und Turing beantworteten 1936 die zweite negativ, Gödel zeigte 1931 die Unvollständigkeit der Arithmetik.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Prädikatenlogik
• Wikipedia: Gödelscher Vollständigkeitssatz
• Wikipedia: Entscheidungsproblem
• Stanford Encyclopedia of Philosophy: Frege’s Logic
• Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik, Springer, Berlin.