Symbole

Die Symbole der Prädikatenlogik zweiter Stufe enthalten neben den folgenden der ersten Stufe:

• logische Symbole:
  • Quantoren: ${\displaystyle \forall ,\exists }$ ,
  • Junktoren: ${\displaystyle \land ,\lor ,\rightarrow ,\leftrightarrow ,\neg }$ ,
  • technische Zeichen: ${\displaystyle (,),\equiv }$ ,
• Variablensymbole: ${\displaystyle v_{0}}$, ${\displaystyle v_{1}}$, ${\displaystyle v_{2}}$, …,
• eine (möglicherweise leere) Menge ${\displaystyle {\mathcal {C}}}$ von Konstantensymbolen,
• eine (möglicherweise leere) Menge ${\displaystyle {\mathcal {F}}}$ von Funktionssymbolen,
• eine (möglicherweise leere) Menge ${\displaystyle {\mathcal {R}}}$ von Relationssymbolen,

zusätzlich noch

• Relationsvariablensymbole ${\displaystyle V_{0}}$, ${\displaystyle V_{1}}$, ${\displaystyle V_{2}}$, …

deren Stelligkeit nötigenfalls als oberer Index notiert wird. Sie treten neben die Variablensymbole ${\displaystyle v_{0},v_{1},v_{2},\ldots }$ 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 ${\displaystyle {\mathcal {C}}}$, ${\displaystyle {\mathcal {F}}}$ und ${\displaystyle {\mathcal {R}}}$ werden wieder zu einer Menge ${\displaystyle 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

Terme, genauer ${\displaystyle S}$-Terme, werden wie in der Prädikatenlogik erster Stufe durch die dort angegebenen Bildungsgesetze erklärt. Damit wurden mittels weiterer Bildungsgesetze ${\displaystyle S}$-Ausdrücke definiert. Dies wird durch zwei weitere Regeln ergänzt:

• Ist ${\displaystyle X}$ ein n-stelliges Relationsvariablensymbol und sind ${\displaystyle t_{1},\ldots ,t_{n}}$ Terme, so ist ${\displaystyle Xt_{1}\ldots t_{n}}$ ein ${\displaystyle S}$-Ausdruck.
• Sind ${\displaystyle \varphi }$ ein ${\displaystyle S}$-Ausdruck und ${\displaystyle X}$ ein Relationsvariablensymbol, so sind ${\displaystyle \exists X\varphi }$ und ${\displaystyle \forall X\varphi }$ ebenfalls ${\displaystyle S}$-Ausdrücke.

2. Stufe

Alle ${\displaystyle S}$-Ausdrücke, die sich nach oben angegebenen Regeln erstellen lassen, bilden die mit ${\displaystyle L_{II}^{S}}$ bezeichnete Sprache, wobei die römische ${\displaystyle 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 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 ${\displaystyle L_{II}^{S}}$ verwendet, d. h., es werden in den Formeln Schreibweisen eingesetzt, die nicht durch oben angegebene Regeln gedeckt sind. An Stelle von ${\displaystyle v_{0},v_{1},\ldots }$ verwendet man kleine Buchstaben wie ${\displaystyle x,y,z}$ und statt ${\displaystyle V_{0},V_{1},\ldots }$ große Buchstaben wie ${\displaystyle X,Y,Z}$ und achtet darauf, dass keine Konflikte mit den Elementen der Signatur entstehen. Ferner ist der Gebrauch suggestiver Abkürzungen wie zum Beispiel ${\displaystyle \forall xyz}$ für ${\displaystyle \forall x\forall y\forall z}$ 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.

Strukturen und Interpretationen

Ausgehend von einer Sprache ${\displaystyle L_{II}^{S}}$ werden jetzt den oben eingeführten Symbolen eine Bedeutung zugewiesen. Wie in der Prädikatenlogik erster Stufe werden Strukturen über der Signatur ${\displaystyle S}$ definiert, um den Symbolen, Konstanten, Funktionen und Relationen der Objektwelt zuzuordnen. Eine Interpretation ist ein Paar ${\displaystyle ({\mathcal {A}},\beta )}$ bestehend aus einer ${\displaystyle S}$-Struktur ${\displaystyle {\mathcal {A}}}$ über einer Menge ${\displaystyle A}$ und einer sogenannten Belegungsfunktion ${\displaystyle \beta }$, die jeder Variablen ${\displaystyle v_{i}}$ ein Element aus ${\displaystyle A}$ und jeder Relationsvariablen ${\displaystyle V_{i}}$ eine Relation gleicher Stelligkeit über ${\displaystyle A}$ zuordnet. Ist ${\displaystyle \beta }$ eine solche Belegung, ${\displaystyle x}$ eine Variable und ${\displaystyle a\in A}$, so sei ${\displaystyle \beta '=\beta {\frac {a}{x}}}$ genau diejenige Belegung, die mit Ausnahme von ${\displaystyle x}$ an allen Stellen mit ${\displaystyle \beta }$ übereinstimmt und lediglich an der Stelle ${\displaystyle x}$ den möglicherweise abweichenden Wert ${\displaystyle a}$ hat. Ist analog ${\displaystyle X}$ eine Relationsvariable der Stelligkeit ${\displaystyle n}$ und ${\displaystyle B}$ eine n-stellige Relation auf ${\displaystyle A}$, d. h. ${\displaystyle R\subseteq A^{n}}$, so sei analog ${\displaystyle \beta {\frac {B}{X}}}$ diejenige Belegung, die mit Ausnahme von ${\displaystyle X}$ an allen Stellen mit ${\displaystyle \beta }$ übereinstimmt, lediglich an der Stelle ${\displaystyle X}$ den möglicherweise abweichenden Wert ${\displaystyle B}$ hat. Man beachte, dass das Variablensymbol ${\displaystyle X}$ und die Relation ${\displaystyle R}$ als Objekt dieselbe Stelligkeit ${\displaystyle n}$ aufweisen müssen, wenn die Relationssymbole an feste Stelligkeiten gebunden sind.
Wird alternativ ein gemeinsamer Pool ${\displaystyle {\mathrel {Rel}}}$ von Relationssymbolen für alle Stelligkeiten vorgesehen und den benutzten Symbolen per Deklaration (einer partiellen Abbildung) ${\displaystyle \nu$ :{\mathrel {Rel}}\not \to \mathbb {N} _{0}} eine Stelligkeit zugewiesen, dann kann diese Einschränkung entfallen. Die Belegungsvariante ${\displaystyle \beta {\frac {R}{X}}}$ ist dann mit einer Deklarationsvariante ${\displaystyle \nu {\frac {n}{X}}}$ assoziiert (die auch lokale Deklaration genannt wird), wobei dann ${\displaystyle R\subseteq A^{n}}$ gelten muss: Das Relationssymbol ${\displaystyle X}$ wird lokal auf die möglicherweise andere Stelligkeit ${\displaystyle n}$ umdeklariert.
Man schreibt ${\displaystyle {\mathcal {I}}{\frac {a}{x}}:=({\mathcal {A}},\beta {\frac {a}{x}})}$ und ${\displaystyle {\mathcal {I}}{\frac {B}{X}}:=({\mathcal {A}},\beta {\frac {B}{X}})}$.

Modelle

Eine Interpretation ${\displaystyle {\mathcal {I}}=({\mathcal {A}},\beta )}$ heißt ein Modell für einen Ausdruck ${\displaystyle \varphi }$, geschrieben ${\displaystyle {\mathcal {I}}\vDash \varphi }$, wenn sich dies auf Grund folgender Regeln ergibt, wobei der regelhafte Aufbau der Sprache ${\displaystyle L_{II}^{S}}$ verwendet wird:

${\displaystyle {\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 &{\text{für alle Relationen }}B{\text{ auf }}A{\text{ gilt }}{\mathcal {I}}{\frac {B}{X}}\vDash \varphi \\{\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}}}$

Dabei wird bei den letzten beiden Zeilen gewöhnlich eine beliebige feste Stelligkeit ${\displaystyle n}$ der Relationssymbole und der Relationen vorausgesetzt: ${\displaystyle X\in {\mathrel {Rel}}_{n},R\subseteq A^{n}}$, was gelegentlich durch einen Index n der Art ${\displaystyle X_{n}}$ angedeutet wird.

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

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

${\displaystyle \varphi _{\geq 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 ${\displaystyle n}$ Elemente hat. ${\displaystyle \varphi _{\geq n}\land \neg \varphi _{\geq n+1}}$ trifft dann nur auf Mengen mit genau ${\displaystyle n}$ Elementen zu. Die Endlichkeit einer Menge wäre dann eine unendliche Disjunktion

${\displaystyle \neg \varphi _{\geq 1}\lor \neg \varphi _{\geq 2}\lor \neg \varphi _{\geq 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

${\displaystyle \varphi _{\text{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 ${\displaystyle \forall x\,\exists ^{1}y\,Xxy}$, dass die zweistellige Relation ${\displaystyle X}$ eine Funktion des Grundbereichs in sich ist, ${\displaystyle \forall xyz\,(Xxz\land Xyz\rightarrow x\equiv y)}$ sagt, dass diese injektiv ist, und ${\displaystyle \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 ${\displaystyle \varphi _{\text{endl}}}$ 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

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 ${\displaystyle X}$ eine lineare Ordnung ist, wird offenbar durch

${\displaystyle \varphi _{\text{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 ${\displaystyle 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 ${\displaystyle \varphi _{\text{endl}}}$ wie folgt symbolisieren lässt:

${\displaystyle \psi _{\text{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 }$  ${\displaystyle \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:

${\displaystyle \varphi _{\leq abz}=\exists X\,(\varphi _{\text{ord}}\land (\forall Y(\exists x\,(Yy\leftrightarrow Xyx)\rightarrow \psi _{\text{endl}})))}$

Ungültigkeit des Kompaktheitssatzes

Mit den oben eingeführten Formeln ${\displaystyle \varphi _{\geq n}}$ und ${\displaystyle \varphi _{\text{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

${\displaystyle \{\varphi _{\text{endl}}\}\cup \{\varphi _{\geq n}|\,n\in \mathbb {N} \}}$

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

${\displaystyle \{\varphi _{\text{endl}}\}\cup \{\varphi _{\geq n}|\,n\leq m\}}$

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

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

Ungültigkeit des Satzes von Löwenheim-Skolem

Im Abschnitt Mächtigkeit wurde eine ${\displaystyle L_{II}^{\emptyset }}$-Formel ${\displaystyle \varphi _{\leq 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 ${\displaystyle \{\neg \varphi _{\leq abz}\}}$ ein abzählbares Modell geben, was aber nicht sein kann, denn jedes Modell von ${\displaystyle \neg \varphi _{\leq abz}}$ ist notwendigerweise überabzählbar.

Unvollständigkeit der Prädikatenlogik zweiter Stufe

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 es ist ja bereits bekannt, dass der Kompaktheitssatz hier nicht gilt.

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

${\displaystyle \Phi \vDash \varphi }$ genau dann, wenn ${\displaystyle \Phi \vdash _{K}\varphi }$

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

∃SO und ∀SO

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

${\displaystyle \exists X_{1}\ldots \exists X_{n}\varphi }$,

wobei ${\displaystyle \varphi }$ ein Ausdruck der Prädikatenlogik erster Stufe in einer um ${\displaystyle X_{1},\ldots ,X_{n}}$ 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

${\displaystyle \forall X_{1}\ldots \forall X_{n}\varphi }$,

mit einem Ausdruck ${\displaystyle \varphi }$ 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 ${\displaystyle \Sigma _{k}^{1}}$ als Menge von Ausdrücken der Form

${\displaystyle \underbrace {(\exists \ldots \exists )(\forall \ldots \forall )(\exists \ldots \exists )\ldots } _{k{\text{ Blöcke}}}\varphi }$

definieren und analog ${\displaystyle \Pi _{k}^{1}}$ als Menge der Negationen von ${\displaystyle \Sigma _{k}^{1}}$. Damit ist ${\displaystyle \exists SO=\Sigma _{1}^{1}}$ und ${\displaystyle \forall SO=\Pi _{1}^{1}}$. Die Fragmente ${\displaystyle \Sigma _{k}^{1}}$ und ${\displaystyle \Pi _{k}^{1}}$ beschreiben dann die Komplexitätsklassen der polynomialen Hierarchie.

MSO

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 ${\displaystyle M\Sigma _{k}^{1}}$ und ${\displaystyle M\Pi _{k}^{1}}$ bezeichneten Hierarchien erweitern.