Prädikatenlogik/Elementare Äquivalenz für Elemente/Endlicher Fall/Textabschnitt

Inwiefern kann man die einzelnen Elemente in einer gegebenen ${}S$-Struktur ${}M$ mit der durch ${}S$ gegebenen Sprache einzeln adressieren bzw. voneinander unterscheiden? Zur Präzisierung dieser Fragestellung dient das Konzept der elementaren Äquivalenz für Elemente.

Definition

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}M$ eine ${}S$-Struktur. Wir nennen zwei Elemente ${}m,n\in M$ elementar äquivalent, wenn für jeden Ausdruck ${}\alpha \in L_{1}^{S}$ in der einen freien Variablen ${}x$ und jede Variablenbelegung ${}\lambda$ auf ${}M$ die Beziehung

$I{\frac {m}{x}}\vDash \alpha {\text{ genau dann, wenn }}I{\frac {n}{x}}\vDash \alpha$

gilt.

Die elementare Äquivalenz drücken wir durch ${}m\sim n$ aus. Dabei handelt es sich offenbar um eine Äquivalenzrelation auf der Menge ${}M$. Wenn

$\varphi \colon M\longrightarrow M$

ein ${}S$-Isomorphismus (also ein Automorphismus) ist, der ${}m$ auf ${}n$ abbildet, so müssen die beiden Elemente elementar äquivalent sein, wie aus Fakt für eine beliebige Interpretation ${}{\tilde {I}}$ mit ${}I={\tilde {I}}{\frac {m}{x}}$ und ${}J={\tilde {I}}{\frac {n}{x}}$ folgt. Zu zwei nicht elementaar äquivalenten Elementen ${}m,n\in M$ nennen wir einen Ausdruck ${}\alpha$ mit ${}I{\frac {m}{x}}\vDash \alpha$ und ${}I{\frac {n}{x}}\vDash \neg \alpha$ einen trennenden Ausdruck.

Beispiel

Es sei ${}S$ ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Funktionssymbol ${}f$ besteht und es sei ${}M=\{1,\ldots ,6\}$ eine ${}S$-Struktur, wobei ${}f$ als die Permutation ${}\pi$ mit

${}x$	${}1$	${}2$	${}3$	${}4$	${}5$	${}6$
${}\pi (x)$	${}3$	${}5$	${}1$	${}4$	${}6$	${}2$

interpretiert werde. Hier sind die Äquivalenzklassen zur elementaren Äquivalenz gleich der sogenannten Zykelzerlegung, nämlich gleich ${}\{1,3\}$, ${}\{2,5,6\}$ und ${}\{4\}$. Die Ordnung der Elemente kann man in der Sprache zu ${}S$ ausdrücken und erhält dadurch trennende Ausdrücke, beispielsweise ist ${}fx=x$ ein Ausdruck in der einen freien Variablen ${}x$, der genau dann wahr wird, wenn ${}x$ durch ${}4$ belegt wird. Der Ausdruck

${\left(ffx=x\right)}\wedge \neg {\left(fx=x\right)}$

ist ein Ausdruck, der genau dann wahr wird, wenn ${}x$ durch ${}1$ oder ${}3$ belegt wird, u.s.w. Dass ${}1$ oder ${}3$ zueinander elementar äquivalent sind, sieht man am einfachsten, wenn man den Automorphismus betrachtet, der durch die Transposition ${}1\leftrightarrow 3$ gegeben ist. Dieser ist nämlich ein ${}S$-Automorphismus und daher können wir den Isomorphiesatz anwenden.

Beispiel

Wenn man in der Definition auch Ausdrücke in mehreren freien Variablen zulassen würde, so wären Elemente nur mit sich selbst äquivalent. Betrachten wir dazu den Ausdruck ${}x=y$, den wir ${}\alpha$ nennen, und zwei Elemente ${}m\neq n$ aus ${}M$. In der Interpretation ${}I$ sei ${}y$ durch ${}m$ belegt. Dann gilt ${}I{\frac {m}{x}}\vDash \alpha$, denn dies bedeutet ${}m=m$, aber ${}I{\frac {n}{x}}\not \vDash \alpha$, denn dies bedeuet ${}n=m$.

Für eine Konstante in ${}c\in S$, die in ${}M$ als das Element ${}m=c^{M}$ interpretiert wird, ist die zugehörige Äquivalenzklasse einelementig: Sie wird durch den Ausdruck ${}x=c$ in der einen freien Variablen ${}x$ charakterisiert, der offenbar nur bei der Belegung von ${}x$ durch ${}m$ wahr wird. Wir fragen uns, ob es für jede Äquivalenzklasse zur elementaren Äquivalenz einen solchen charakterisierenden Ausdruck in einer freien Variablen gibt.

Lemma

Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}M$ eine ${}S$-Struktur mit der Eigenschaft, dass es in ${}M$ nur endlich viele Klassen zur elementaren Äquivalenz gibt.

Dann gibt es zu jeder Äquivalenzklasse ${}[m]\subseteq M$ einen ${}S$-Ausdruck ${}\alpha _{[m]}$ in einer freien Variablen ${}x$, der die Klasse ${}[m]$ beschreibt, für den also

$n\in [m]{\text{ genau dann, wenn }}I{\frac {n}{x}}\vDash \alpha _{[m]}$

gilt.

Beweis

Es seien ${}M_{1},\ldots ,M_{k}$ die Äquivalenzklassen der elementaren Äquivalenzrelation und sei ${}m_{i}\in M_{i}$ ein fest gewählter Repräsentant. Wir zeigen, dass es für ${}M_{1}$ einen solchen charakterisierenden Ausdruck gibt. Zu jedem ${}i=2,\ldots ,k$ gibt es einen Ausdruck ${}\beta _{i}$ in der freien Variablen ${}x$ mit ${}I{\frac {m_{1}}{x}}\vDash \beta _{i}$, aber ${}I{\frac {m_{i}}{x}}\not \vDash \beta _{i}$, da ja ${}m_{1}$ und ${}m_{i}$ nicht elementar äquivalent sind. Wir können annehmen, dass die relevante Variable in jedem dieser Ausdrücke die gleiche ist. Der konjugierte Ausdruck

${}\alpha _{1}=\beta _{2}\wedge \ldots \wedge \beta _{k}\,$

ist in einer Interpretation (zur ${}S$-Struktur ${}M$) genau dann wahr, wenn die Variable ${}x$ durch ein Element aus ${}M_{1}$ belegt wird.

$\Box$

Beispiel

Für das Symbolalphabet ${}\{0,'\}$ und die natürlichen Zahlen ${}\mathbb {N}$ mit der kanonischen Interpretation sind sämtliche Klassen zur elementaren Äquivalenz einelementig und können auch durch Ausdrücke charakterisiert werden, und zwar wird die Zahl ${}n$ durch den Ausdruck ${}x=0^{\prime \prime \ldots \prime }$ mit ${}n$ Strichen eindeutig beschrieben.

Beispiel

Es sei ${}S$ das Symbolalphabet, das außer Variablen für jedes ${}k\in \mathbb {N} _{+}$ ein einstelliges Relationssymbol ${}R_{k}$ enthält, und es sei

${}\alpha _{k}=R_{k}x\,.$

Wir betrachten die Menge ${}M=\mathbb {N} _{+}$, wobei wir das Relationssymbol ${}R_{k}$ durch

$R_{k}^{M}(n){\text{ genau dann, wenn }}n{\text{ ein Vielfaches von }}k{\text{ ist }}$

interpretieren. Zwei Elemente

${}m\neq n\in \mathbb {N} \,$

können dann nicht elementar äquivalent sein, da sie sich nicht gegenseitig teilen können und daher beispielsweise ${}R_{m}^{M}(m)$, also ${}I{\frac {m}{x}}\vDash \alpha _{m}$, aber nicht ${}R_{m}^{M}(n)$, also ${}I{\frac {n}{x}}\vDash \neg \alpha _{m}$, gilt. Die Äquivalenzklassen sind also einelementig. Es ist aber nicht möglich, diese Klassen durch einen Ausdruck in dieser Sprache zu charakterisieren, da die Gültigkeitsmengen zu jedem Ausdruck entweder leer sind oder unendlich viele Elemente enthalten, siehe Aufgabe.

Lemma

Es sei ${}S$ ein Symbolalphabet erster Stufe und ${}M$ eine ${}S$-Struktur. Für jede elementare Äquivalenzklasse ${}[m]\subseteq M$ gebe es einen ${}S$-Ausdruck ${}\alpha _{[m]}$ in einer freien Variablen ${}x$, der die Klasse ${}[m]$ beschreibt, für den also

$n\in [m]{\text{ genau dann, wenn }}I{\frac {n}{x}}\vDash \alpha _{[m]}$

gilt.

Dann gelten folgende Aussagen.

1. Für jedes ${}k$-stellige Relationssymbol ${}R$ ist ${}R^{M}$ auf den Äquivalenzklassen wohldefiniert.
2. Für jedes ${}k$-stellige Funktionssymbol ${}f$ ist ${}f^{M}$ auf den Äquivalenzklassen wohldefiniert (und zwar in dem Sinn, dass aus ${}m_{1}\sim m_{1}',\ldots ,m_{k}\sim m_{k}'$ die elementare Äquivalenz ${}f^{M}(m_{1},\ldots ,m_{k})\sim f^{M}(m'_{1},\ldots ,m'_{k})$ folgt).

Beweis

(1). Es sei ${}R$ ein ${}k$-stelliges Relationssymbol. Für ein ${}k$-Tupel ${}(m_{1},\ldots ,m_{k})$ aus ${}M$ mit ${}(m_{1},\ldots ,m_{k})\in R^{M}$ und ein weiteres dazu elementar-äquivalentes Tupel ${}(n_{1},\ldots ,n_{k})$ (es gelte also $m_{1}\sim n_{1},\,m_{2}\sim n_{2},\ldots ,m_{k}\sim n_{k}$) müssen wir ${}(n_{1},\ldots ,n_{k})\in R^{M}$ zeigen. Es seien ${}\alpha _{1},\ldots ,\alpha _{k}$ Ausdrücke in der einen freien (untereinander verschiedenen) Variablen ${}x_{i}$, die die Äquivalenzklassen zu ${}m_{i}$ bzw. ${}n_{i}$ charakterisieren. Es gilt

$I\vDash \exists x_{1}\ldots \exists x_{k}{\left(\alpha _{1}\wedge \ldots \wedge \alpha _{k}\rightarrow Rx_{1}\ldots x_{k}\right)},$

wie ja die Belegung von ${}x_{j}$ durch ${}m_{j}$ zeigt. Ebenso gilt

$I{\frac {m_{1}}{x_{1}}}\vDash \exists x_{2}\ldots \exists x_{k}{\left(\alpha _{1}\wedge \alpha _{2}\wedge \ldots \wedge \alpha _{k}\rightarrow Rx_{1}x_{2}\ldots x_{k}\right)},$

wie die entsprechende Belegung zeigt. Dies ist jetzt ein Ausdruck in der einen freien Variablen ${}x_{1}$. Wenn man ${}x_{1}$ statt mit ${}m_{1}$ durch ein anderes elementar äquivalentes Element ${}n_{1}$ belegt, so erhält man nach Definition der elementaren Äquivalenz

$I{\frac {n_{1}}{x_{1}}}\vDash \exists x_{2}\ldots \exists x_{k}{\left(\alpha _{1}\wedge \alpha _{2}\wedge \ldots \wedge \alpha _{k}\rightarrow Rx_{1}x_{2}\ldots x_{k}\right)}$

und damit

$I\vDash \forall x_{1}\exists x_{2}\ldots \exists x_{k}{\left(\alpha _{1}\wedge \alpha _{2}\wedge \ldots \wedge \alpha _{k}\rightarrow Rx_{1}x_{2}\ldots x_{k}\right)}.$

Somit hat man den ersten Existenzquantor durch einen Allquantor ersetzt. In dieser Weise fährt man mit den anderen Existenzquantoren fort und erhält schließlich

$I\vDash \forall x_{1}\forall x_{2}\ldots \forall x_{k}{\left(\alpha _{1}\wedge \alpha _{2}\wedge \ldots \wedge \alpha _{k}\rightarrow Rx_{1}x_{2}\ldots x_{k}\right)}.$

Einsetzen von ${}n_{j}$ für ${}x_{j}$ liefert also, da ja ${}\alpha _{j}$ auf ${}n_{j}$ zutrifft,

$I{\frac {n_{1},\ldots ,n_{k}}{x_{1},\ldots ,x_{k}}}\vDash Rx_{1}x_{2}\ldots x_{k}$

und somit ${}(n_{1},\ldots ,n_{k})\in R^{M}$.

(2). Die Aussage für Funktionssymbole wird ähnlich bewiesen, siehe Aufgabe.

$\Box$