2.10 Exkurs: Prädikatenlogik zweiter Stufe

© 1999 François Bry
Dieses Lehrmaterial wird ausschließlich zur privaten Verwendung angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht oder eine Veröffentlichung von Kopien oder Übersetzungen) dieses Lehrmaterials bedarf der Erlaubnis des Autors.

2.10 Exkurs: Prädikatenlogik zweiter Stufe

In der Prädikatenlogik erster Stufe beziehen sich Quantoren auf Objekte. Manche Aussagen, zum Beispiel in der Mathematik, quantifizieren aber nicht nur über Objekte, sondern über Eigenschaften von Objekten. Ein Beispiel dafür stellt der Satz 2.1.4 (Prinzip der strukturellen Induktion für aussagenlogische Formeln) dar:

Für jede Eigenschaft ε von -Formeln gilt: wenn ...

Andere Beispiele dieser Art sind

Zwei Objekte sind genau dann gleich, wenn sie sich durch keine Eigenschaft unterscheiden.
Es gibt keine zweistellige Beziehung, die zwischen a und b besteht und symmetrisch und antisymmetrisch ist.

Derartige Aussagen lassen sich nicht in der Prädikatenlogik erster Stufe formulieren. Dort werden Eigenschaften von Objekten und Beziehungen zwischen Objekten durch Relationssymbole repräsentiert. Rein syntaktisch kann aber an der Stelle eines Relationssymbols in einer Formel nie eine Variable stehen, und Quantoren kommen nur in Verbindung mit Variablen vor.

Die Prädikatenlogik zweiter Stufe (PL2S) ist eine Erweiterung der PL1S um Relations- und Funktionsvariablen, mit denen Quantifizierungen der obigen Art möglich sind. Damit ist die Prädikatenlogik zweiter Stufe ausdrucksstärker als die Prädikatenlogik erster Stufe.

Gegeben seien Mengen von Funktions- und von Relationsvariablen wie folgt. Die bisherigen Variablen entsprechen den nullstelligen Funktionsvariablen. Sprache [PL2S]

Definition 2.10.1 (Sprache [PL2S])
Eine Sprache

der Prädikatenlogik zweiter Stufe ist gegeben durch ihre Signatur. Zusätzlich gehören zu

die logischen Symbole der Prädikatenlogik zweiter Stufe.

Die logischen Symbole der Prädikatenlogik zweiter Stufe sind:
1. Die Menge der Hilfszeichen ) und , und (
2. Die Menge der nullstelligen Junktoren: {T, ⊥}.
  Die Menge der einstelligen Junktoren: {¬}.
  Die Menge der zweistelligen Junktoren: {∧, ∨, ⇒, ⇔}.
3. Die Menge der Quantoren: {∀, ∃}.
4. Für jede natürliche Zahl n ≥ 0 eine abzählbar unendliche Menge von n-stelligen Relationsvariablen, notiert X₁ⁿ,X₂ⁿ, ... mit oder ohne Indizes.
5. Für jede natürliche Zahl n ≥ 0 eine abzählbar unendliche Menge von n-stelligen Funktionsvariablen, notiert F₁ⁿ,F₂ⁿ, ... (für n = 0 auch u, v, w, x, y, z...) mit oder ohne Indizes.
6. Das Gleichheitsrelationssymbol falls vorhanden.
Die Signatur einer Sprache der Prädikatenlogik zweiter Stufe besteht aus folgenden Symbolmengen:
1. Für jede natürliche Zahl n ≥ 0 eine (eventuell leere) Menge Relⁿ von n-stelligen Relationssymbolen.
  0-stellige Relationssymbole heißen auch Aussagenvariablen.
  Enthält Rel ² das besondere zweistellige Relationssymbol , genannt Gleichheitsrelationssymbol, so heißt eine Sprache der Prädikatenlogik zweiter Stufe mit Gleichheit.
2. Für jede natürliche Zahl n ≥ 0 eine (eventuell leere) Menge Funⁿ von n-stelligen Funktionssymbolen.
  0-stellige Funktionssymbole heißen auch Konstanten.

Alle erwähnten Mengen sind abzählbar (üblicherweise sogar aufzählbar) und paarweise disjunkt, und kein Symbol einer dieser Mengen besteht aus einer Sequenz von Symbolen, in der ein Symbol aus einer der anderen Mengen vorkommt.
Es wird vorausgesetzt, dass

mindestens eine Konstante enthält.

Terme werden ähnlich wie für eine Sprache der Prädikatenlogik erster Stufe definiert. Der einzige Unterschied ist, dass auch Funktionsvariablen anstelle von Funktionssymbolen zum Termaufbau verwendet werden können.

Definition 2.10.2 (Term [PL2S])
Sei

eine Sprache der Prädikatenlogik zweiter Stufe. Die Menge

der

-Terme, kurz Terme, ist die kleinste Menge, die die folgenden Bedingungen erfüllt:

Jede nullstellige Funktionsvariable von ist ein -Term.
Jede Konstante von ist ein -Term.
Sind t₁,...t_n -Terme, n ≥ 1, und ist f ein n-stelliges Funktionssymbol von oder eine n-stellige Funktionsvariable von , so ist auch f(t₁,...t_n) ein -Term.

Bei den Formeln ist der Aufbau ebenfalls analog zur PL1S. Die Unterschiede sind zum einen, dass auch Relationsvariablen anstelle von Relationssymbolen zum Aufbau von atomaren Formeln verwendet werden können, zum anderen, dass Quantoren auch mit Relations- und Funktionsvariablen erlaubt sind.

Definition 2.10.3 (Formel [PL2S])
Sei

eine Sprache der Prädikatenlogik zweiter Stufe.

Jedes nullstellige Relationssymbol von ist eine atomare -Formel.
Jede nullstellige Relationsvariable von ist eine atomare -Formel.
Sind t₁,...t_n -Terme, n ≥ 1, und ist p ein n-stelliges Relationssymbol von , oder eine n-stellige Relationsvariable von , so ist p(t₁,...t_n) eine atomare -Formel.
Eine atomare -Formel nennt man auch kurz atomare Formel oder einfach Atom.
Die Menge der -Formeln, kurz Formeln, ist die kleinste Menge, die die folgenden Bedingungen erfüllt:
1. T und ⊥ und alle atomaren -Formeln sind in .
2. Ist F ∈ , so ist auch ¬ F ∈ .
3. Sind F ∈ und G ∈ und ist θ ein zweistelliger Junktor, so ist auch (F θ G) ∈ .
4. Ist F ∈ , x eine Variable, und Q ein Quantor, so ist auch QxF ∈ .

Die Eindeutigkeitssätze für Terme und Formeln gelten natürlich ebenfalls für Sprachen der Prädikatenlogik zweiter Stufe. Teilformeln und die Menge der in einem Term frei oder nicht frei vorkommenden Relationsvariablen und Funktionsvariablen werden ähnlich definiert wie für Sprachen der Aussagenlogik bzw. PL1S.

Das dritte der eingangs genannten Beispiele kann jetzt (mit vereinfachter Klammerung) folgendermaßen dargestellt werden.

¬∃X²(X²(a,b)
∧∀x∀y[X²(x,y) ⇒ X²(y,x)]
∧∀x∀y[X²(x,y) ∧ X²(y,x) ⇒ x

y])

Bemerkung: Es erscheint vielleicht naheliegend, anstelle der ausgeschriebenen Definitionen für symmetrisch und antisymmetrisch entsprechende Bezeichner einzuführen und etwa so zu definieren:

∀X² (symmetrisch(X²) ⇔ ∀x∀y[X²(x,y) ⇒ X²(y,x)])

Das wäre aber keine Formel der PL2S, weil X² kein Term und folglich symmetrisch(X²) keine Formel ist.

Die Logik ist bezüglich der Syntax erheblich strikter als zum Beispiel die Programmiersprache Prolog, deren Formalisierung zwar eigentlich nur auf einem Fragment der Prädikatenlogik erster Stufe beruht, die aber andererseits ähnliche Ausdrücke wie den obigen erlaubt, die über die Prädikatenlogik erster Stufe hinausgehen.

In dem unerlaubten Ausdruck symmetrisch(X²) steht symmetrisch für eine Relation über Relationen. Das ist erst in einer Sprache der dritten Stufe zugelassen. Sprachen höherer Stufen sind Sprachen, in denen Relationen über Relationen über Relationen usw. ausgedrückt werden können.