Prädikatenlogik zweiter Stufe

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 StufeBearbeiten

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

SymboleBearbeiten

Die Symbole der Prädikatenlogik zweiter Stufe enthalten neben denjenigen 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  ,  ,  , …[1]

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, 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  ,   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ückeBearbeiten

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

  • 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. StufeBearbeiten

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 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ückeBearbeiten

Im Folgenden werden wir metasprachliche Ausdrücke für Formeln aus   verwenden, 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.[3] Ferner erlauben wir uns suggestive Abkürzungen wie zum Beispiel   für  . 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.

SemantikBearbeiten

Strukturen und InterpretationenBearbeiten

Ausgehend von einer Sprache   werden jetzt den oben eingeführten Symbolen eine Bedeutung zuwgewiesen. Wie in der Prädikatenlogik erster Stufe vor werden Strukturen über der Signatur   definiert, um den Symbolen dann Konstanten, Funktionen, 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.[4] 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 vorhgesehen 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.[5]
Man schreibt   und  .

ModelleBearbeiten

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.[6]

Damit ist den Symbolen eine inhaltliche Bedeutung zugewiesen. Ist   eine Menge von Ausdrücken der betrachteten Sprache und ist   für alle  , so schreiben wir 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-AxiomeBearbeiten

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:

  •  
  •  
  •  

Betrachten wir 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 ZahlenBearbeiten

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ächtigkeitenBearbeiten

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

  für  

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

Endliche MengenBearbeiten

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 MengenBearbeiten

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   eine lineare Ordnung ist, wird offenbar durch

 

beschrieben, denn diese Formel bedeutet von links nach rechts, dass die zweistellige Relation irreflexiv, transitiv und linear ist. Eine einstellige Relation  , 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   wie folgt symbolisieren lässt:

    .

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:

 

Mängel der Prädikatenlogik zweiter StufeBearbeiten

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 KompaktheitssatzesBearbeiten

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

 

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

 

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

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

Ungültigkeit des Satzes von Löwenheim-SkolemBearbeiten

Im Abschnitt Mächtigkeit hatten wir eine  -Formel   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   ein abzählbares Modell geben, was aber nicht sein kann, denn jedes Modell von   ist notwendigerweise überabzählbar.

Unvollständigkeit der Prädikatenlogik zweiter StufeBearbeiten

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   mit  , so bedeutet  , dass sich der Ausdruck   durch Anwendungen der Regeln des Sequenzenkalküls aus der Formelmenge   herleiten lässt. Die Schreibweise   bedeute wie oben, dass jedes Modell, das   erfüllt, auch   erfüllen muss. Die gerade ausgeführte Überlegung zeigt also, dass es keinen Sequenzenkalkül   gibt, so dass für alle Formelmengen   und Ausdrücke   die Äquivalenz

  genau dann, wenn  

gilt. Das schließt nicht aus, dass es einen Sequenzenkalkül geben könnte, der diese Äquivalenz für   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.

Fragmente der Prädikatenlogik zweiter StufeBearbeiten

Für Anwendungen werden gewisse Beschränkungen der Ausdrücke der Prädikatenlogik zweiter Stufe betrachtet, man spricht von Fragmenten der Prädikatenlogik zweiter Stufe und interessiert sich für deren Ausdrucksstärke.

∃SO und ∀SOBearbeiten

In der existentiellen Prädikatenlogik zweiter Stufe beschränkt man sich auf Ausdrücke der Form

 ,

wobei   ein Ausdruck der Prädikatenlogik erster Stufe in einer um   erweiterten Signatur ist. Insbesondere sind keine Allquantoren über Relationensymbole erlaubt. Wegen der englischen Bezeichnung existential second order logic wird dieses Fragment mit ∃SO bezeichnet. Die Klasse der mittels ∃SO-Ausdrücken definierbaren Strukturen ist über den Satz von Fagin eng mit den Sprachen der Komplexitätsklasse NP verbunden, so dass sich bei geeigneter Codierung ∃SO mit NP identifizieren lassen.

Analog besteht die universelle Prädikatenlogik zweiter Stufe aus Ausdrücken der Form

 ,

mit einem Ausdruck   der Prädikatenlogik erster Stufe wie oben. Dieses Fragment wird mit ∀SO bezeichnet. In der Komplexitätstheorie gehört ∀SO zur Komplexitätsklasse coNP, denn die ∀SO-Ausdrücke sind genau die Negationen der ∃SO-Ausdrücke und umgekehrt.

Allgemeiner lassen sich Fragmente   als Menge von Ausdrücken der Form

 

definieren und analog   als Menge der Negationen von  . Damit ist   und  . Die Fragmente   und   beschreiben dann die Komplexitätsklassen der polynomialen Hierarchie.[7]

MSOBearbeiten

Ein weiteres wichtiges Fragment erhält man, wenn man die Quantifizierung über Relationen auf einstellige Relationen, das heißt in jeder Interpretation auf Teilmengen des Universums, einschränkt. Man nennt dies die monadische Prädikatenlogik zweiter Stufe oder kurz, nach dem englischen monadic second order logic, MSO. Auch hier interessiert man sich für die Ausdrucksstärke und geht dazu auch auf kleinere Fragmente über wie etwa ∃MSO, was aus Ausdrücken besteht, die in MSO und in ∃SO liegen. Auch das lässt sich auf naheliegende Weise zu mit   und   bezeichneten Hierarchien erweitern.[8]

Siehe auchBearbeiten

LiteraturBearbeiten

  • H.-D. Ebbinghaus, J. Flum, W. Thomas: Finite Model Theory. Springer Verlag, 1995, ISBN 3-540-28787-6.
  • H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik. Spektrum Akademischer Verlag, 1996, ISBN 3-8274-0130-5.
  • Leonid Libkin: Elements of Finite Model Theory. Springer-Verlag, 2004, ISBN 3-540-21202-7.
  • Stefan Brass: Mathematische Logik mit Datenbank-Anwendungen. Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, Halle 2005, S. 176 (informatik.uni-halle.de [PDF]).
    Alternative Notation für eine lokal modifizierte Variablendeklaration und -belegung.
  • Klaus Grue: Object Oriented Mathematics. Universität Kopenhagen, Department of Computer Science (Datalogisk Institut), 1995, S. 21 (diku.dk [PDF]).
    Generelle Maplet-Notation, ebenfalls eine Notation für lokal modifizierte Variablendeklaration und -belegung.
  • Carsten Lutz: Logik Teil 4: Prädikatenlogik zweiter Stufe. Universität Bremen, AG Theorie der künstlichen Intelligenz, 2010, S. 65 (informatik.uni-bremen.de [PDF] Vorlesung im Wintersemester 2010).
  • François Bry: 2.10 Exkurs: Prädikatenlogik zweiter Stufe. LMU, Institut für Informatik, Lehr- und Forschungseinheit für Programmier- und Modellierungssprachen, München 1999 (en.pms.ifi.lmu.de).
  • Esther Ramharter, Günther Eder: Prädikatenlogik zweiter Stufe. SE Modallogik und andere philosophisch relevante Logiken. WS 2015/2016. Universität Wien, S. 22 (homepage.univie.ac.at [PDF]).

Anmerkungen und EinzelnachweiseBearbeiten

  1. 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.
  2. 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.
  3. 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.
  4. Mit beliebigen   (Menge der Variablensymbole),   (Wertebereich) ist die lokal modifizierte Variablenbelegung (auch ( -)Variante 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.
  5. 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.
  6. Wird alternativ mit einer einzigen Menge an Relationssymbolen und einer Stelligeitsdeklaration gearbeitet, dann konnten die letzten beiden Zeilen so lauten:   Dabei ist für   im Wirkungsbereich (Skopus) der Quantoren eine lokale Variante der Stelligkeitsdeklaation   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).
  7. Leonid Libkin (2004), S. 173
  8. H.-D. Ebbinghaus, J. Flum, W. Thomas (1995), S. 40.