Prädikatenlogik zweiter Stufe

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Prädikatenlogik zweiter Stufe ist ein Teilgebiet der mathematischen Logik. Sie erweitert die Prädikatenlogik erster Stufe um die Möglichkeit, über alle Relationen zu quantifizieren. Die Prädikatenlogik der zweiten Stufe ist daher echt ausdrucksstärker als die der ersten Stufe, hat jedoch den Verlust wichtiger Sätze zu beklagen, wie etwa den des Kompaktheitssatzes.

Die Sprache der Prädikatenlogik zweiter Stufe[Bearbeiten]

Dieser Artikel benutzt die im Artikel Prädikatenlogik erster Stufe eingeführten Begriffe und Bezeichnungen.

Symbole[Bearbeiten]

Die Symbole der Prädikatenlogik zweiter Stufe enthalten neben denjenigen der ersten Stufe

  • logische Symbole \forall, \exists, \land, \lor, \rightarrow, \leftrightarrow, \neg, (, ), \equiv
  • Variablensymbole v_0,v_1,v_2,\ldots,
  • eine (möglicherweise leere) Menge \mathcal C von Konstantensymbolen,
  • eine (möglicherweise leere) Menge \mathcal F von Funktionssymbolen,
  • eine (möglicherweise leere) Menge \mathcal R von Relationssymbolen

zusätzlich noch

  • Relationsvariablensymbole V_0, V_1, V_2\ldots,

deren Stelligkeit nötigenfalls als oberer Index notiert wird. Sie treten neben die Variablensymbole v_0, v_1, v_2, \ldots. Auch wenn die intendierte Anwendung, nämlich die Quantifizierung über alle Relationen, schon im Namen steckt, wollen wir an dieser Stelle wie in der Prädikatenlogik erster Ordnung davon absehen und die Symbole und die nachfolgenden Bildungsgesetze zunächst rein syntaktisch sehen. Die Konstanten-, Funktions- und Relationssymbole \mathcal{C}, \mathcal{F} und \mathcal{R} werden wieder zu einer Menge S zusammengefasst, die man dann die Signatur der Sprache nennt. Man beachte, dass die Relationssymbole zur Signatur gehören, die Relationsvariablensymbole hingegen nicht.

Terme und Ausdrücke[Bearbeiten]

Terme, genauer S-Terme, werden wie in der Prädikatenlogik erster Stufe durch die dort angegebenen Bildungsgesetze erklärt. Damit wurden mittels weiterer Bildungsgesetze S-Ausdrücke definiert. Wir ergänzen diese durch zwei weitere Regeln:

  • Ist X eine n-stelliges Relationsvariablensymbol und sind t_1,\ldots, t_n Terme, so ist Xt_1\ldots t_n ein S-Ausdruck.
  • Sind \varphi ein S-Ausdruck und X ein Relationsvariablensymbol, so sind \exists X\varphi und \forall X\varphi ebenfalls S-Ausdrücke.

2. Stufe[Bearbeiten]

Alle S-Ausdrücke, die sich nach oben angegebenen Regeln erstellen lassen, bilden die mit L_{II}^S bezeichnete Sprache, wobei die römische II für die zweite Stufe steht. Damit wird zum Ausdruck gebracht, dass man hier nicht nur über alle Variablen quantifizieren kann, sondern gemäß dem oben angegebenen zweiten Bildungsgesetz auch über alle Relationsvariablen. Damit können wir mehr Ausdrücke als in der Prädikatenlogik erster Stufe bilden, während zum Beispiel die Peano-Axiome in der Prädikatenlogik erster Stufe nicht formulierbar sind, werden wir unten sehen, dass die zweite Stufe über eine hinreichende Ausdrucksstärke verfügt.

Metasprachliche Ausdrücke[Bearbeiten]

Im Folgenden werden wir metasprachliche Ausdrücke für Formeln aus L_{II}^S verwenden, das heißt wir werden in unseren Formeln Schreibweisen einsetzen, die nicht durch oben angegebene Regeln gedeckt sind. An Stelle von v_0,v_1,\ldots verwenden wir kleine Buchstaben wie x,y,z und statt V_0,V_1,\ldots große Buchstaben wie X,Y,Z und achten darauf, dass keine Konflikte mit den Elementen der Signatur entstehen. Ferner erlauben wir uns suggestive Abkürzungen wie zum Beispiel \forall xyz für \forall x \forall y \forall z. Der einzige Grund dafür ist die bessere Lesbarkeit der auftretenden Formeln; es ist in jedem Fall klar, welcher syntaktisch korrekte Ausdruck mit einer solchen Formel gemeint ist.

Semantik[Bearbeiten]

Strukturen und Interpretationen[Bearbeiten]

Wir gehen von einer Sprache L_{II}^S aus und werden jetzt den oben eingeführten Symbolen eine Bedeutung zuweisen. Wir gehen wie in der Prädikatenlogik erster Stufe vor und definieren wie dort Strukturen über der Signatur S, um unseren Symbolen darin Konstanten, Funktionen, Relationen zuordnen zu können. Eine Interpretation ist ein Paar (\mathcal{A},\beta) bestehend aus einer S-Struktur \mathcal{A} über einer Menge A und einer sogenannten Belegungsfunktion \beta die jeder Variablen v_i ein Element aus A und jeder Relationsvariablen V_i eine Relation gleicher Stelligkeit über A zuordnet. Ist \beta eine solche Belegung, x eine Variable und a\in A, so sei \beta \frac{a}{x} wieder diejenige Belegung, die mit Ausnahme von x an allen Stellen mit \beta übereinstimmt und lediglich an der Stelle x den möglicherweise abweichenden Wert a hat. Ist analog X eine Relationsvariable und B eine Relation auf A, so sei \beta \frac{B}{X} diejenige Belegung, die mit Ausnahme von X an allen Stellen mit \beta übereinstimmt, lediglich an der Stelle X den möglicherweise abweichenden Wert B hat. Man schreibt \mathcal{I}\frac{a}{x}:= (\mathcal{A},\beta \frac{a}{x}) und \mathcal{I}\frac{B}{X}:= (\mathcal{A},\beta \frac{B}{X})

Modelle[Bearbeiten]

Wir sagen, dass eine Interpretation \mathcal{I}=(\mathcal{A},\beta) ein Modell für einen Ausdruck \varphi ist, und schreiben dafür \mathcal{I}\vDash \varphi, wenn sich dies auf Grund folgender Regeln ergibt, wobei der regelhafte Aufbau der Sprache L_{II}^S verwendet wird:

\begin{matrix}
{\mathcal I} \vDash t_1\equiv t_2 & :\Leftrightarrow & {\mathcal I}(t_1) = {\mathcal I}(t_2) \\
{\mathcal I} \vDash Xt_1\ldots t_n & :\Leftrightarrow & \beta(X) \text{ trifft auf } ({\mathcal I}(t_1),\ldots, {\mathcal I}(t_n)) \text{ zu.}\\
{\mathcal I} \vDash Rt_1\ldots t_n & :\Leftrightarrow & R^{\mathcal A} \text{ trifft auf } ({\mathcal I}(t_1),\ldots, {\mathcal I}(t_n)) \text{ zu.}\\
{\mathcal I} \vDash \neg\varphi & :\Leftrightarrow & \text{nicht }{\mathcal I} \vDash \varphi\\
{\mathcal I} \vDash (\varphi\land \psi) & :\Leftrightarrow & {\mathcal I} \vDash \varphi \text{ und }{\mathcal I} \vDash \psi\\
{\mathcal I} \vDash (\varphi\lor \psi) & :\Leftrightarrow & {\mathcal I} \vDash \varphi \text{ oder }{\mathcal I} \vDash \psi\\
{\mathcal I} \vDash (\varphi\rightarrow \psi) & :\Leftrightarrow & \text{wenn }{\mathcal I} \vDash \varphi \text{ dann auch }{\mathcal I} \vDash \psi\\
{\mathcal I} \vDash (\varphi\leftrightarrow \psi) & :\Leftrightarrow & {\mathcal I} \vDash \varphi \text{ genau dann, wenn }{\mathcal I} \vDash \psi\\
{\mathcal I} \vDash \forall x\varphi & :\Leftrightarrow & {\mathcal I}\frac{a}{x} \vDash \varphi \mbox{ für alle } a\in A\\
{\mathcal I} \vDash \exists x\varphi & :\Leftrightarrow & \text{es gibt ein }a\in A \text{ mit }{\mathcal I}\frac{a}{x} \vDash \varphi\\
{\mathcal I} \vDash \forall X\varphi & :\Leftrightarrow & {\mathcal I}\frac{B}{X} \vDash \varphi \mbox{ für alle Relationen } B \text { auf } A\\
{\mathcal I} \vDash \exists X\varphi & :\Leftrightarrow & \text{es gibt eine Relation } B \text{ auf } A \text{ mit }{\mathcal I}\frac{B}{X} \vDash \varphi
\end{matrix}

Damit ist den Symbolen eine inhaltliche Bedeutung zugewiesen. Ist \Phi eine Menge von Ausdrücken der betrachteten Sprache und ist \mathcal{I}\vDash \varphi für alle \varphi\in \Phi, so schreiben wir abkürzend wieder \mathcal{I}\vDash \Phi. Ist \Phi eine Menge von Sätzen, das heißt die \varphi \in \Phi enthalten keine freien Variablen, so sagt man auch, dass \mathcal{A} ein Modell ist, denn die Modellbeziehung hängt in diesem Fall gar nicht von der konkreten Belegung ab.

Peano-Axiome[Bearbeiten]

Bekanntlich lassen sich die Peano-Axiome nicht in der Prädikatenlogik erster Stufe formulieren, da das Induktionsaxiom eine Aussage über alle Teilmengen der betrachteten Grundmenge trifft, aber nicht über alle Teilmengen quantifiziert werden kann. Da Teilmengen aber nichts anderes als einstellige Relationen sind, kann man mit der Signatur S=\{0,\sigma\}, wobei 0 ein Konstantensymbol ist, genannt Nullelement, und \sigma ein einstelliges Funktionssymbol, genannt Nachfolgerfunktion, folgende Ausdrücke bilden:

  • \forall x\,\neg\sigma x\equiv 0
  • \forall x\forall y\,(\sigma x\equiv \sigma y \rightarrow x\equiv y)
  • \forall X((X0 \land \forall x(Xx\rightarrow X\sigma x)) \rightarrow \forall x\,Xx)

Betrachten wir Interpretationen, also S-Strukturen, in denen das Symbol 0 dann Element einer Menge ist und \sigma eine auf dieser definierte Funktion, so sagt der erste Ausdruck, dass 0 kein Nachfolger ist, denn 0 ist von allen Bildern \sigma x verschieden. Die zweite Zeile drückt die Injektivität der Nachfolgerfunktion aus. Die dritte Zeile schließlich besagt, dass jede einstellige Relation X (das heißt Teilmenge des betrachteten Grundbereichs), die auf 0 zutrifft und mit jedem x, auf das sie zutrifft, auch auf den Nachfolger \sigma x zutrifft, für alle Variablen x gilt, womit das Induktionsaxiom formuliert ist. Damit ist die Prädikatenlogik zweiter Stufe echt ausdrucksstärker als diejenige erster Stufe.

Schließlich kann man zeigen, dass je zwei S-Strukturen, die Modelle obiger L_{II}^S-Ausdrücke sind, isomorph sind. In der Prädikatenlogik zweiter Stufe gibt also keine Nichtstandardmodelle der natürlichen Zahlen.

Reelle Zahlen[Bearbeiten]

Die Theorie der geordneten Körper, die sich mit der Signatur S=\{0,1,+,\cdot,<\} in der Sprache L_I^S formulieren lässt, erlaubt keine eindeutige Kennzeichnung der reellen Zahlen bis auf Isomorphie, denn das Vollständigkeitsaxiom, nach dem jede nicht-leere, nach oben beschränkte Menge ein Supremum besitzt, lässt sich in L_I^S nicht formulieren. Dieser Mangel an Ausdrucksstärke der Prädikatenlogik erster Stufe führt zur Nichtstandardanalysis. In der hier behandelten Prädikatenlogik zweiter Stufe gelingt folgende Symbolisierung der Vollständigkeit:

\forall X:((\exists x\,Xx\land \exists y\forall z(Xz\rightarrow z<y)) \rightarrow 
\exists y(\forall z(Xz \rightarrow (z<y\lor z\equiv y))\land \forall x(x<y\rightarrow \exists z\,(x<z\land Xz))))

Zur Erläuterung dieser Formel beachte man, dass die einstellige Relation X wieder für Teilmengen der Grundgesamtheit einer Interpretation steht. Für alle Teilmengen soll also gelten: Wenn diese nicht leer ist, \exists x\,Xx, und wenn diese nach oben beschränkt ist, \exists y\forall z(Xz\rightarrow z<y), dann gibt es ein y, so dass dieses obere Schranke der Menge ist, \forall z(Xz \rightarrow (z<y\lor z\equiv y)), und jedes kleinere Element nicht mehr obere Schranke ist, \forall x(x<y\rightarrow \exists z\,(x<z\land Xz)). Damit ist das Vollständigkeitsaxiom in L_{II}^S formuliert.

Mächtigkeiten[Bearbeiten]

Die Prädikatenlogik zweiter Stufe bietet Möglichkeiten über Mächtigkeiten von Mengen zu reden, die weit über die Prädikatenlogik erster Stufe hinausgehen. Im Folgenden verwenden wir die Abkürzung

\exists^1x\,\varphi für \exists x\,(\varphi\,\land\, \forall y\,(\varphi\frac{y}{x}\rightarrow y\equiv x)),

was in jeder Interpretation offenbar bedeutet, dass es genau ein x mit \varphi gibt.

Endliche Mengen[Bearbeiten]

Bekanntlich kann man in der Prädikatenlogik erster Stufe nicht ausdrücken, dass eine Menge endlich ist. Man kann lediglich mittels Sätzen der Art

\varphi_{\ge n} = \exists v_1\ldots \exists v_n\,(\neg v_1\equiv v_2\land \neg v_1\equiv v_3 \land \ldots \land \neg v_{n-1}\equiv v_n)

sagen, dass eine Menge (das heißt der Grundbereich einer Interpretation) mindestens n Elemente hat. \varphi_{\ge n}\land\neg\varphi_{\ge n+1} trifft dann nur auf Mengen mit genau n Elementen zu. Die Endlichkeit einer Menge wäre dann eine unendliche Disjunktion

\neg \varphi_{\ge 1}\lor \neg\varphi_{\ge 2} \lor \neg \varphi_{\ge 3} \lor\ldots,

die man weder in der ersten noch in der zweiten Stufe bilden kann. In der Prädikatenlogik zweiter Stufe hat man aber

\varphi_{endl} = \forall X\,((\forall x\,\exists^1 y\,Xxy\,\land\, \forall xyz\,(Xxz\land Xyz\rightarrow x\equiv y)) \rightarrow \forall y\,\exists x\,Xxy).

In jedem Modell dieses Satzes bedeutet \forall x\,\exists^1 y\,Xxy, dass die zweistellige Relation X eine Funktion des Grundbereichs in sich ist, \forall xyz\,(Xxz\land Xyz\rightarrow x\equiv y) sagt, dass diese injektiv ist, und  \forall y\,\exists x\,Xxy, dass sie surjektiv ist. Obige Formel sagt also aus, dass jede injektive Funktion des Grundbereichs in sich automatisch surjektiv ist, eine Aussage, die bekanntlich genau auf endliche Mengen zutrifft. Daher bedeutet die Formel \varphi_{endl} tatsächlich, dass alle sie erfüllende Modelle endlich sind. Dies zeigt erneut, dass die Prädikatenlogik zweiter Stufe echt ausdrucksstärker ist als die erster Stufe.

Abzählbare Mengen[Bearbeiten]

Man kann in der Prädikatenlogik zweiter Stufe sogar ausdrücken, dass eine Menge höchstens abzählbar ist, denn eine Menge ist genau dann höchstens abzählbar, wenn es eine lineare Ordnungsrelation auf ihr gibt, in der jeder Anfangsabschnitt endlich ist. Dass X eine lineare Ordnung ist, wird offenbar durch

\varphi_{ord} = \forall x\,\neg Xxx \land \forall xyz\,((Xxy\land Xyz)\rightarrow Xxz)\land \forall xy\,(Xxy\lor x\equiv y \lor Xyx)

beschrieben, denn diese Formel bedeutet von links nach rechts, dass die zweistellige Relation irreflexiv, transitiv und linear ist. Eine einstellige Relation Y, die für eine Teilmenge des Grundbereichs steht, ist genau dann endlich, wenn jede injektive Funktion dieser Teilmenge in sich schon surjektiv ist, was sich in Analogie zu obigem \varphi_{endl} wie folgt symbolisieren lässt:

\psi_{endl} = \forall X\,(\forall xy\,(Xxy\rightarrow Yx\land Yy) \land \forall x\,(Yx \rightarrow \exists^1 y\,Xxy \land \forall xyz\,(Xxz\land Xyz\rightarrow x\equiv y)) \rightarrow \forall y\,(Yy\rightarrow \exists x\,Xxy)).

Die folgende Formel symbolisiert dann, dass es auf einer Menge eine lineare Ordnung gibt, in der jeder Anfangsabschnitt endlich ist, und das ist äquivalent dazu, dass die Menge höchstens abzählbar ist:

\varphi_{\le abz} = \exists X\,(\varphi_{ord}\land (\forall Y(\exists x\,(Yy\leftrightarrow Xyx)\rightarrow \psi_{endl})))

Mängel der Prädikatenlogik zweiter Stufe[Bearbeiten]

Wie die folgenden Ausführungen zeigen, führt die größere Ausdrucksstärke der Prädikatenlogik zweiter Stufe dazu, dass viele wichtige Sätze der Prädikatenlogik erster Stufe nicht mehr gelten.

Ungültigkeit des Kompaktheitssatzes[Bearbeiten]

Mit den oben eingeführten Formeln \varphi_{\ge n} und \varphi_{endl} lässt sich leicht zeigen, dass für die Prädikatenlogik zweiter Stufe kein Kompaktheitssatz gelten kann. Offenbar ist jede endliche Teilmenge der Formelmenge

\{\varphi_{endl}\}\cup \{\varphi_{\ge n}|\,n\in \N\}

erfüllbar, das heißt sie hat ein Modell, denn eine endliche Teilmenge dieser Formelmenge ist für geeignetes m\in \N in

\{\varphi_{endl}\}\cup \{\varphi_{\ge n}|\,n \le m\}

enthalten, weshalb jede endliche Menge mit mindestens m Elementen ein Modell ist. Dagegen gibt es kein Modell für die gesamte Formelmenge, denn ein Modell von \varphi_{endl} muss eine endliche Menge sein und kann daher nicht alle \varphi_{\ge n} erfüllen.

Da der Kompaktheitssatz aber für die Prädikatenlogik erster Stufe gilt, zeigt diese Überlegung noch einmal, dass \varphi_{endl} in der Prädikatenlogik erster Stufe nicht formulierbar sein kann.

Ungültigkeit des Satzes von Löwenheim-Skolem[Bearbeiten]

Im Abschnitt Mächtigkeit hatten wir eine L_{II}^{\emptyset}-Formel \varphi_{\le abz} erstellt, deren Modelle genau die höchstens abzählbaren Mengen sind. Würde der Satz von Löwenheim-Skolem auch für die Prädikatenlogik zweiter Stufe gelten, so müsste es zur Formelmenge \{\neg \varphi_{\le abz}\} ein abzählbares Modell geben, was aber nicht sein kann, denn jedes Modell von \neg \varphi_{\le abz} ist notwendigerweise überabzählbar.

Unvollständigkeit der Prädikatenlogik zweiter Stufe[Bearbeiten]

In der Prädikatenlogik erster Stufe kann man einen Sequenzenkalkül aufstellen und von diesem nachweisen, dass er für alle Herleitungen in einer Sprache der Prädikatenlogik erster Stufe ausreichend ist, das ist der sogenannte Gödelsche Vollständigkeitssatz. Man könnte nun versuchen, einen solchen Sequenzenkalkül um Elemente, die den Umgang mit Relationsvariablensymbolen festlegen, zu erweitern, um auch für die Prädikatenlogik zweiter Stufe alle Herleitungen auf rein syntaktische Weise in einem solchen Kalkül ausführen zu können. Ein solcher Versuch muss scheitern, denn mit einem vollständigen Sequenzenkalkül für die Prädikatenlogik zweiter Stufe könnte man den Beweis, der in der Prädikatenlogik erster Stufe daraus auf den Kompaktheitssatz schließt, auf die Prädikatenlogik zweiter Stufe übertragen, aber wir wissen ja schon, dass der Kompaktheitssatz hier nicht gilt.

Bezeichnet man das Schließen in einem solchen Sequenzenkalkül K mit \vdash_K, so bedeutet \Phi \vdash_K \varphi, dass sich der Ausdruck \varphi durch Anwendungen der Regeln des Sequenzenkalküls aus der Formelmenge \Phi herleiten lässt. Die Schreibweise \Phi \vDash \varphi bedeute wie oben, dass jedes Modell, das \Phi erfüllt, auch \varphi erfüllen muss. Die gerade ausgeführte Überlegung zeigt also, dass es keinen Sequenzenkalkül K gibt, so dass für alle Formelmengen \Phi und Ausdrücke \varphi die Äquivalenz

\Phi \vDash \varphi genau dann, wenn \Phi \vdash_K \varphi

gilt. Das schließt nicht aus, dass es einen Sequenzenkalkül geben könnte, der diese Äquivalenz für \Phi = \emptyset erfüllt, dann hätte man immerhin einen Sequenzenkalkül für allgemeingültige Aussagen, aber auch das ist nicht der Fall, wie Kurt Gödel zeigen konnte. Diese Aussage nennt man die Unvollständigkeit der Prädikatenlogik zweiter Stufe. Es sei darauf hingewiesen, dass dies nicht der Gödelsche Unvollständigkeitssatz ist.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

  • H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag 1996, ISBN 3-8274-0130-5