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 zweiter Stufe ist daher echt ausdrucksstärker als die der ersten Stufe, bestimmte wichtige Sätze gelten jedoch nicht mehr, wie etwa der Kompaktheitssatz.

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

Symbole Die Symbole der Prädikatenlogik zweiter Stufe enthalten neben den folgenden der ersten Stufe: logische Symbole: Quantoren:  , Junktoren:  , technische Zeichen:  , Variablensymbole: , , , …, eine (möglicherweise leere) Menge von Konstantensymbolen, eine (möglicherweise leere) Menge von Funktionssymbolen, eine (möglicherweise leere) Menge von Relationssymbolen, zusätzlich noch Relationsvariablensymbole , , , …Ramharter, Eder (2015/16) lassen zusätzlich noch Funktionsvariablen zu, sie könnten z. B. mit bezeichnet werden. Relationsvariablen der Stelligkeit 0 stellen Aussagevariablen dar; Funktionsvariablen der Stelligkeit 0 entsprechen gewöhnlichen Variablen. deren Stelligkeit nötigenfalls als oberer Index notiert wird. Sie treten neben die Variablensymbole Auch wenn die intendierte Anwendung, nämlich die Quantifizierung über alle Relationen, schon im Namen steckt, soll an dieser Stelle wie in der Prädikatenlogik erster Ordnung davon abgesehen und die Symbole und die nachfolgenden Bildungsgesetze zunächst rein syntaktisch gesehen werden. Die Konstanten-, Funktions- und Relationssymbole , und werden wieder zu einer Menge 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 Terme, genauer -Terme, werden wie in der Prädikatenlogik erster Stufe durch die dort angegebenen Bildungsgesetze erklärt.Wenn Funktionsvariablen zugelassen sind (Ramharter, Eder 2015/16), dann kommt zu den Bildungsgesetzen für Terme noch das folgende hinzu: Ist ein n-stelliges Funktionsvariablensymbol und sind Terme, so ist ein -Term. Damit wurden mittels weiterer Bildungsgesetze -Ausdrücke definiert. Dies wird durch zwei weitere Regeln ergänzt: Ist ein n-stelliges Relationsvariablensymbol und sind Terme, so ist ein -Ausdruck. Sind ein -Ausdruck und ein Relationsvariablensymbol, so sind und ebenfalls -Ausdrücke.

2. Stufe Alle -Ausdrücke, die sich nach oben angegebenen Regeln erstellen lassen, bilden die mit bezeichnete Sprache, wobei die römische 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 mehr Ausdrücke als in der Prädikatenlogik erster Stufe gebildet werden. Während zum Beispiel die Peano-Axiome in der Prädikatenlogik erster Stufe nicht formulierbar sind, verfügt die zweite Stufe über eine hinreichende Ausdrucksstärke.

Metasprachliche Ausdrücke Im Folgenden werden metasprachliche Ausdrücke für Formeln aus verwendet, d. h., es werden in den Formeln Schreibweisen eingesetzt, die nicht durch oben angegebene Regeln gedeckt sind. An Stelle von verwendet man kleine Buchstaben wie und statt große Buchstaben wie und achtet darauf, dass keine Konflikte mit den Elementen der Signatur entstehen.Dazu wird gewöhnlich für jede Stelligkeit eine eigene Menge an n-stelligen Relationsvariablensymbolen vorgesehen. Beispiele dafür finden sich bei F. Bry (1999) Def. 2.10.1, C. Lutz (2010) S. 6 und 8, und Ramharter, Eder (2015/16) S. 17 (letztere kennzeichnen die feste Stelligkeit von Relationsvariablen mit einem Index). Eine andere Möglichkeit besteht darin (wie in der mehrsortigen Logik erster Stufe) mit einem einzigen Vorrat an Relationssymbolen zu arbeiten, und den benutzten Relationsvariablensymbolen eine Stelligkeit über eine (partieller) Abbildung (Variablendeklaration) zuzuweisen. Ferner ist der Gebrauch suggestiver Abkürzungen wie zum Beispiel für zulässig. 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

Strukturen und Interpretationen Ausgehend von einer Sprache werden jetzt den oben eingeführten Symbolen eine Bedeutung zugewiesen. Wie in der Prädikatenlogik erster Stufe werden Strukturen über der Signatur definiert, um den Symbolen, Konstanten, Funktionen und Relationen der Objektwelt zuzuordnen. Eine Interpretation ist ein Paar bestehend aus einer -Struktur über einer Menge und einer sogenannten Belegungsfunktion , die jeder Variablen ein Element aus und jeder Relationsvariablen eine Relation gleicher Stelligkeit über zuordnet. Ist eine solche Belegung, eine Variable und , so sei genau diejenige Belegung, die mit Ausnahme von an allen Stellen mit übereinstimmt und lediglich an der Stelle den möglicherweise abweichenden Wert hat.Mit beliebigen (Menge der Variablensymbole), (Wertebereich) ist die lokal modifizierte Variablenbelegung (auch genannt) eine (ggf. nur partiellen) Abbildung von nach mit

Alternative Schreibweisen für sind – Carsten Lutz (2010) S. 8, – Stefan Brass (2005) S. 56, dort angegeben für eine Variablendeklaration statt -belegung und (oder ) – Klaus Grue (1995), S. 11, dort allgemeine Maplet-Notation angegeben. Ramharter, Eder (2015/16) S. 17 bezeichnen die Variablenbelegung mit statt . Für den Fall, dass bereits dem Definitionsbereich von angehört, wird der ursprüngliche Bildwert überschrieben. Ist analog eine Relationsvariable der Stelligkeit und eine n-stellige Relation auf , d. h. , so sei analog diejenige Belegung, die mit Ausnahme von an allen Stellen mit übereinstimmt, lediglich an der Stelle den möglicherweise abweichenden Wert hat. Man beachte, dass das Variablensymbol und die Relation als Objekt dieselbe Stelligkeit aufweisen müssen, wenn die Relationssymbole an feste Stelligkeiten gebunden sind. Wird alternativ ein gemeinsamer Pool von Relationssymbolen für alle Stelligkeiten vorgesehen und den benutzten Symbolen per Deklaration (einer partiellen Abbildung) eine Stelligkeit zugewiesen, dann kann diese Einschränkung entfallen. Die Belegungsvariante ist dann mit einer Deklarationsvariante assoziiert (die auch lokale Deklaration genannt wird), wobei dann gelten muss: Das Relationssymbol wird lokal auf die möglicherweise andere Stelligkeit umdeklariert.Eine entsprechende Vorgehensweise in der mehrsortigen Prädikatenlogik erster Stufe (d. h. mit Sorten statt Stelligkeiten) findet sich bei S. Brass (2005) S. 54–56. Man schreibt und .

Modelle Eine Interpretation heißt ein Modell für einen Ausdruck , geschrieben , wenn sich dies auf Grund folgender Regeln ergibt, wobei der regelhafte Aufbau der Sprache verwendet wird:

Dabei wird bei den letzten beiden Zeilen gewöhnlich eine beliebige feste Stelligkeit der Relationssymbole und der Relationen vorausgesetzt: , was gelegentlich durch einen Index n der Art angedeutet wird.Wird alternativ mit einer einzigen Menge an Relationssymbolen und einer Stelligkeitsdeklaration gearbeitet, dann konnten die letzten beiden Zeilen so lauten:

Dabei ist für im Wirkungsbereich (Skopus) der Quantoren eine lokale Variante der Stelligkeitsdeklaration wirksam.

Im vielsortigen Fall ist lediglich die Stelligkeit zu erweitern auf einen Argumenttyp mit den Sorten , wobei die Sorten Symbole für die Objektbereiche sind – für einsortige Logik siehe Brass (2005).

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

Peano-Axiome 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 , wobei 0 ein Konstantensymbol ist, genannt Nullelement, und ein einstelliges Funktionssymbol, genannt Nachfolgerfunktion, folgende Ausdrücke bilden:

Betrachtet man Interpretationen, also -Strukturen, in denen das Symbol 0 dann Element einer Menge ist und eine auf dieser definierte Funktion, so sagt der erste Ausdruck, dass 0 kein Nachfolger ist, denn 0 ist von allen Bildern verschieden. Die zweite Zeile drückt die Injektivität der Nachfolgerfunktion aus. Die dritte Zeile schließlich besagt, dass jede einstellige Relation (das heißt Teilmenge des betrachteten Grundbereichs), die auf 0 zutrifft und mit jedem , auf das sie zutrifft, auch auf den Nachfolger zutrifft, für alle Variablen 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 -Strukturen, die Modelle obiger -Ausdrücke sind, isomorph sind. In der Prädikatenlogik zweiter Stufe gibt es also keine Nichtstandardmodelle der natürlichen Zahlen.

Reelle Zahlen Die Theorie der geordneten Körper, die sich mit der Signatur in der Sprache 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 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:

Zur Erläuterung dieser Formel beachte man, dass die einstellige Relation wieder für Teilmengen der Grundgesamtheit einer Interpretation steht. Für alle Teilmengen soll also gelten: Wenn diese nicht leer ist, , und wenn diese nach oben beschränkt ist, , dann gibt es ein , so dass dieses obere Schranke der Menge ist, , und jedes kleinere Element nicht mehr obere Schranke ist, . Damit ist das Vollständigkeitsaxiom in formuliert.

Mächtigkeiten 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 wird die Abkürzung für verwendet, was in jeder Interpretation offenbar bedeutet, dass es genau ein mit gibt.

Endliche Mengen 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

sagen, dass eine Menge (das heißt der Grundbereich einer Interpretation) mindestens Elemente hat. trifft dann nur auf Mengen mit genau Elementen zu. Die Endlichkeit einer Menge wäre dann eine unendliche Disjunktion

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

In jedem Modell dieses Satzes bedeutet , dass die zweistellige Relation eine Funktion des Grundbereichs in sich ist, sagt, dass diese injektiv ist, und , 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 tatsächlich, dass alle sie erfüllenden Modelle endlich sind. Dies zeigt erneut, dass die Prädikatenlogik zweiter Stufe echt ausdrucksstärker ist als die erste Stufe.

Abzählbare Mengen