Monadische Prädikatenlogik zweiter Stufe

Jeder Ausdruck der Prädikatenlogik erster Stufe ist ein MSO-Ausdruck, denn ein solcher enthält überhaupt keine Relationsvariablen, insbesondere also keine mehrstelligen.

Die Peano-Arithmetik kann bekanntlich mit der Signatur ${\displaystyle \sigma =\{0,s\}}$ beschrieben werden, wobei 0 eine Konstante und ${\displaystyle s}$ ein Funktionssymbol ist. Die Konstante wird als Nullelement und s als Nachfolger-Funktion interpretiert. Das sogenannte Induktionsaxiom

${\displaystyle \forall X((X0\land \forall x(Xx\rightarrow Xsx))\rightarrow \forall x\,Xx)}$

ist offenbar ein MSO-Satz.

Ist ${\displaystyle \sigma =\{E\}}$ für ein zweistelliges Relationssymbol ${\displaystyle E}$, so ist jede ${\displaystyle \sigma }$-Struktur ein Graph ${\displaystyle G}$, wobei das ${\displaystyle G}$ das Universum, das heißt die Grundmenge, der Struktur ist und die Interpretation ${\displaystyle E^{G}}$ von ${\displaystyle E}$ die Kantenrelation auf ${\displaystyle G}$ ist. Dann ist

${\displaystyle \forall X((\exists x\,Xx\land \exists x\,\neg Xx)\rightarrow \exists x\exists y\,(Xx\land \neg Xy\land Exy))}$

ein syntaktisch korrekter MSO-Ausdruck, denn die einzige vorkommende Relationsvariable ${\displaystyle X}$ ist einstellig. Das zweistellige Relationssymbol ${\displaystyle E}$ gehört zur Signatur und ist daher keine Relationsvariable. Die Semantik dieses Ausdrucks lautet: Für jede Teilmenge (${\displaystyle \forall X}$) gilt: wenn die Teilmenge nicht leer ist (${\displaystyle \exists x\,Xx}$) und auch ihr Komplement nicht leer ist (${\displaystyle \exists x\,\neg Xx}$), dann gibt es zwischen ihr und ihrem Komplement eine Kante (${\displaystyle \exists x\exists y(Xx\land \neg Xy\land Exy))}$). Das ist offenbar äquivalent zum Zusammenhang des Graphen und wir halten fest, dass man in der MSO den Zusammenhang von Graphen beschreiben kann.[2] In der Prädikatenlogik erster Stufe ist das nicht möglich, siehe Lokalität (Logik), so dass sich MSO durch dieses Beispiel als echt ausdrucksstärker erweist.

Für ${\displaystyle \sigma =\emptyset }$ gibt es keinen MSO-Satz, der auf einer als endlich vorausgesetzten Menge ausdrückt, dass diese geradzahlig ist.[3] In der Prädikatenlogik zweiter Stufe ist das aber möglich, indem man zum Beispiel ausdrückt, dass es eine Teilmenge ${\displaystyle X}$ gibt und eine bijektive Funktion von ${\displaystyle X}$ auf ihr Komplement:

${\displaystyle \exists X\,\exists Y\,(''Y{\text{ ist Funktion}}''\,\land \,''X{\text{ ist Definitionsbereich von }}Y''\,\land \,''\neg X{\text{ ist Wertebereich von }}Y''\,\land \,''Y{\text{ ist bijektiv}}''\}}$,

wobei klar ist, dass die in Apostrophen eingeschlossenen Teilsätze sogar in der Prädikatenlogik erster Stufe formulierbar sind. Da hier die zweistellige Relationsvariable ${\displaystyle Y}$ verwendet wird, handelt es sich nicht um einen MSO-Satz. Dieses Beispiel zeigt, dass die Prädikatenlogik zweiter Stufe echt ausdrucksstärker als MSO ist.

Die monadische Prädikatenlogik zweiter Stufe eignet sich zur Formulierung von Aussagen über Wörtern über einem endlichen Alphabet ${\displaystyle \Sigma }$. Dazu verwenden wir als Signatur ${\displaystyle \sigma =\{<,P_{a},P_{b},\ldots \}}$, wobei ${\displaystyle a,b,\ldots }$ die Zeichen des Alphabets sind und wir formulieren, dass < eine lineare Ordnung auf dem Universum ist und die ${\displaystyle P_{a},P_{b}\ldots }$ eine Partition des Universums bilden.

${\displaystyle \forall x\,\neg (x<x)\,\land \,\forall x\forall y\forall z\,(((x<y)\land (y<z))\rightarrow (x<z))\,\land \,\forall x\forall y\,((x=y)\lor (x<y)\lor (y<x))}$

drückt die lineare Ordnung aus, und

${\displaystyle \forall x\,((P_{a}x\lor P_{b}x\lor P_{c}x)\land \neg (P_{a}x\land P_{b}x)\land \neg (P_{a}x\land P_{c}x)\land \neg (P_{b}x\land P_{c}x))}$

drückt die Partitionseigenschaft aus.

Ein endliches Universum können wir dann als isomorph zu ${\displaystyle \{1,2,\ldots ,n\}}$ annehmen, wobei < als die natürliche Ordnung interpretiert wird und ${\displaystyle P_{a}i}$ als an ${\displaystyle i}$-ter Stelle steht ein a, entsprechend für ${\displaystyle P_{b}i}$ und so weiter.

Ist etwa ${\displaystyle \Sigma =\{a,b,c\}}$, so definiert das Wort ${\displaystyle s=aabcbca}$ eine ${\displaystyle \{<,P_{a},P_{b},P_{c}\}}$-Struktur ${\displaystyle M_{s}}$ auf dem Universum ${\displaystyle \{1,2,3,4,5,6,7\}}$ mit den Interpretationen ${\displaystyle \{1,2,7\}}$ für ${\displaystyle P_{a}}$, ${\displaystyle \{3,5\}}$ für ${\displaystyle P_{b}}$, ${\displaystyle \{2,4\}}$ für ${\displaystyle P_{c}}$ und der natürlichen Ordnung für <. Die Wörter aus ${\displaystyle \Sigma ^{*}}$, das heißt die endlichen Zeichenketten über dem Alphabet ${\displaystyle \Sigma }$, sind in diesem Sinne genau die ${\displaystyle L_{II}^{\sigma }}$-Modelle.

Man kann nun mittels MSO-Ausdrücken Teilmengen solcher Zeichenketten beschreiben. Ist ${\displaystyle \Phi }$ ein MSO-Satz, das heißt eine MSO-Formel ohne freie Variablen, so ist

${\displaystyle L(\Phi ):=\{s\in \Sigma ^{*}|\,M_{s}\vDash \Phi \}}$

die Menge (Sprache) aller Wörter, die Modell für ${\displaystyle \Phi }$ sind, das heißt die ${\displaystyle \Phi }$ erfüllen. Eine Sprache dieser Form heißt MSO-definierbar.

So können wir zum Beispiel die Sprache aller Zeichenketten über ${\displaystyle \Sigma =\{a,b,c\}}$, die eine gerade Anzahl ${\displaystyle a}$'s enthält, wie folgt beschreiben:

${\displaystyle \Phi =\exists X\exists Y\,{\big (}\forall x((P_{a}x\leftrightarrow (Xx\lor Yx))\land \neg (Xx\land Yx))}$

${\displaystyle \land \exists x(Xx\land \forall y\,(y<x\rightarrow \neg P_{a}x))}$

${\displaystyle \land \exists x(Yx\land \forall y\,(x<y\rightarrow \neg P_{a}x))}$

${\displaystyle \land \forall x\forall y\,((Xx\land Xy\land x<y)\rightarrow \exists z(Yz\land x<z\land z<y))}$

${\displaystyle \land \forall x\forall y\,((Yx\land Yy\land x<y)\rightarrow \exists z(Xz\land x<z\land z<y)){\big )}}$

In Worten bedeutet das

Die ${\displaystyle a}$'s verteilen sich auf zwei Mengen ${\displaystyle X}$ und ${\displaystyle Y}$, die disjunkt sind,

und das erste ${\displaystyle a}$ liegt in ${\displaystyle X}$

und das letzte ${\displaystyle a}$ liegt in ${\displaystyle Y}$

und zwischen zwei verschiedenen Elementen aus ${\displaystyle X}$ liegt eines aus ${\displaystyle Y}$

und zwischen zwei verschiedenen Elementen aus ${\displaystyle Y}$ liegt eines aus ${\displaystyle X}$.

Damit ist dann klar, dass ${\displaystyle L(\Phi )}$ genau die die Menge der Zeichenketten ist, die eine gerade Anzahl von ${\displaystyle a}$'s enthält, das heißt diese Sprache ist MSO-definierbar.

Der Satz von Büchi, benannt nach Julius Richard Büchi, gibt Auskunft darüber, welche Sprachen MSO-definierbar sind:

• Eine Sprache ist genau dann MSO-definierbar, wenn sie regulär ist.[4][5]

Dieser aus dem Jahre 1960 stammende Satz stellt somit eine sehr frühe Verbindung zwischen mathematischer Logik und theoretischer Informatik her, er gilt als erstes Resultat der deskriptiven Komplexitätstheorie. Der Satz wurde unabhängig auch von Boris Trakhtenbrot gefunden.[6]

Eine Analyse des Beweises zeigt, dass man sogar mit MSO-Ausdrücken der Art

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

auskommt, wobei ${\displaystyle \varphi }$ ein Ausdruck der Prädikatenlogik erster Stufe in einer um ${\displaystyle X_{1},\ldots ,X_{n}}$ erweiterten Signatur ist. Die Menge dieser Ausdrücke nennt man ${\displaystyle M\Sigma _{1}^{1}}$. Für Sprachen sind daher Regularität, MSO-Definierbarkeit und ${\displaystyle M\Sigma _{1}^{1}}$-Definierbarkeit äquivalent.[7]