Prädikatenlogik/Elementare Äquivalenz/Textabschnitt

Definition

Zwei ${}S$-Strukturen ${}M$ und ${}N$ über einem erststufigen Symbolalphabet ${}S$ heißen elementar äquivalent, wenn jeder ${}S$-Satz, der in ${}M$ gilt, auch in ${}N$ gilt.

Dies bedeutet, dass in den beiden Strukturen überhaupt die gleichen Sätze gelten.

In der Mathematik spielen strukturerhaltende Abbildungen eine herausragende Rolle. Eine erststufige Version dieses Konzeptes kommt in folgender Definition zum Ausdruck.

Definition

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}M$ und ${}N$ seien ${}S$-Strukturen. Eine Abbildung

$\varphi \colon M\longrightarrow N$

heißt ${}S$-Homomorphismus, wenn folgende Eigenschaften gelten.

1. Für jede Konstante ${}c\in S$ ist

   ${}\varphi {\left(c^{M}\right)}=c^{N}\,.$

2. Für jedes ${}n$-stellige Funktionssymbol ${}f\in S$ ist

   ${}\varphi {\left(f^{M}{\left(m_{1},\ldots ,m_{n}\right)}\right)}=f^{N}{\left(\varphi (m_{1}),\ldots ,\varphi (m_{n})\right)}\,$

   für alle ${}m_{1},\ldots ,m_{n}\in M$.

3. Für jedes ${}n$-stellige Relationsymbol ${}R\in S$ impliziert die Gültigkeit von

   $R^{M}(m_{1},\ldots ,m_{n})$

   die Gültigkeit von

   $R^{N}{\left(\varphi (m_{1}),\ldots ,\varphi (m_{n})\right)}.$

Die üblichen Begriffe der Mathematik, beispielsweise ein Gruppenhomomorphismus, eine Ringhomomorphismus, eine lineare Abbildung zwischen Vektorräumen, eine monotone Abbildung zwischen geordneten Mengen, fallen unter diesen abstrakten Homomorphiebegriff.

Definition

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}M$ und ${}N$ seien ${}S$-Strukturen. Eine bijektive Abbildung

$\varphi \colon M\longrightarrow N$

heißt ${}S$-Isomorphismus, wenn sowohl ${}\varphi$ als auch die Umkehrabbildung ${}\varphi ^{-1}$ ein ${}S$-Homomorphismus ist.

Zwei ${}S$-Strukturen heißen ${}S$-isomorph, wenn es einen ${}S$-Isomorphismus zwischen ihnen gibt. Bei ${}M=N$ spricht man auch von einem Automorphismus.

Beispiel

Es sei ${}S$ ein erststufiges Symbolalphabet, das nur aus einer Variablenmenge besteht, die Konstantenmenge und die Mengen der Funktionssymbole und der Relationssymbole seien also leer. Dann ist jede (nichtleere) Menge ${}M$ unmittelbar eine ${}S$-Struktur und jede Abbildung

$\varphi \colon M\longrightarrow N$

ist ein ${}S$-Homomorphismus. Insbesondere ist jede bijektive Abbildung

$\varphi \colon M\longrightarrow N$

ein ${}S$-Isomorphismus.

Bemerkung  

Es sei ${}S$ ein erststufiges Symbolalphabet und ${}M$ und ${}N$ seien ${}S$-Strukturen. Eine bijektive Abbildung

$\varphi \colon M\longrightarrow N,$

die ein ${}S$-Homomorphismus ist, muss kein ${}S$-Isomorphismus sein, da die Umkehrabbildung ${}\varphi ^{-1}$ im Allgemeinen kein Homomorphismus sein muss. Deshalb fordert man in der Definition eines Isomorphismus explizit die Homomorphie der Umkehrabbildung. Wenn allerdings das Symbolalphabet ${}S$ keine Relationssymbole enthält, so ist die Umkehrabbildung automatisch ein Homomorphismus, siehe Aufgabe. Ein Extremfall liegt, vor, wenn ein Relationssymbol ${}R$ in ${}M$ als die leere Relation interpretiert wird. Dann verhält sich ${}\varphi \colon M\rightarrow N$ bezüglich dieses Relationssymbols ${}S$-homomorph, unabhängig von der Interpretation von ${}R$ auf ${}N$.

Wir haben in Fakt gesehen, dass je zwei Modelle der (allerdings nicht erststufig formulierten) Dedekind-Peano-Axiome zueinander isomorph sind. Dabei war ${}0$ die einzige Konstante und die Nachfolgerabbildung die einzige (einstellige) Funktion. Auch zwei Modelle der reellen Zahlen sind isomorph, was schwieriger zu beweisen ist. Die zugehörigen Axiomensysteme legen also das intendierte Modell bis auf Isomorphie fest, und zwar ist sogar jeweils der Isomorphismus eindeutig bestimmt. Letzteres gilt beispielsweise für die komplexen Zahlen nicht. Die komplexen Zahlen können als algebraischer Abschluss von ${}\mathbb {R}$ eingeführt werden. Je zwei solche algebraische Abschlüsse sind untereinander isomorph, allerdings ist die Isomorphie nicht eindeutig bestimmt. Beispielsweise ist die komplexe Konjugation ein nichttrivialer Automorphismus auf ${}{\mathbb {C} }$.

Lemma

Es sei ${}S$ ein erststufiges Symbolalphabet, ${}M$ und ${}N$ seien ${}S$-Strukturen und

$\varphi \colon M\longrightarrow N$

ein ${}S$-Homomorphismus. Es sei ${}\lambda$ eine Variablenbelegung in ${}M$ und ${}\varphi \circ \lambda$ die nach ${}N$ übertragene Variablenbelegung. Es seien ${}I$ und ${}J$ die zugehörigen Interpretationen.

Dann ist

${}\varphi (I(t))=J(t)\,$

für alle ${}S$-Terme ${}t$.

Beweis

Siehe Aufgabe.

$\Box$

Die folgende Aussage heißt Isomorphiesatz (oder Isomorphielemma).

Satz

Es seien ${}M$ und ${}N$ isomorphe ${}S$-Strukturen über einem Symbolalphabet ${}S$.

Dann sind ${}M$ und ${}N$ elementar äquivalent.

Genauer: Zu einem Isomorphismus

$\varphi \colon M\longrightarrow N$

und einer Variablenbelegung ${}\lambda$ auf ${}M$ und der zugehörigen Variablenbelegung ${}\varphi \circ \lambda$ auf ${}N$ mit den zugehörigen Interpretationen ${}I$ und ${}J$ gilt für jeden ${}S$-Ausdruck ${}\alpha$ die Äquivalenz

$I\vDash \alpha {\text{ genau dann, wenn }}J\vDash \alpha .$

Beweis

Wir beweisen den Zusatz durch Induktion über den Aufbau der Ausdrücke, woraus sich dann die Hauptaussage, die unabhängig von Belegungen ist, ergibt. Es sei ein Isomorphismus

$\varphi \colon M\longrightarrow N$

fixiert. Nach Fakt respektiert der Isomorphismus die Interpretation aller Terme. Da die Situation symmetrisch ist, müssen wir lediglich zeigen, dass aus der Gültigkeit von ${}I\vDash \alpha$ die Gültigkeit von ${}J\vDash \alpha$ folgt. Für einen Ausdruck der Form

${}s=t\,$

mit Termen ${}s,t$ bedeutet

$I\vDash s=t$

einfach

${}I(s)=I(t)\,.$

Daher ist

${}J(s)=\varphi (I(s))=\varphi (I(t))=J(t)\,$

und somit

$J\vDash s=t.$

Für ein ${}n$-stelliges Relationssymbol ${}R$ und ${}n$ Terme ${}t_{1},\ldots ,t_{n}$ bedeutet

$I\vDash Rt_{1}\ldots t_{n},$

dass ${}R^{M}$ auf ${}\left(I(t_{1}),\,\ldots ,\,I(t_{n})\right)$ zutrifft. Dann trifft aufgrund der Homomorphie von ${}\varphi$ auch ${}R^{N}$ auf

${}\left(\varphi (I(t_{1})),\,\ldots ,\,\varphi (I(t_{n}))\right)=\left(J(t_{1}),\,\ldots ,\,J(t_{n})\right)\,$

zu. Also ist

$J\vDash Rt_{1}\ldots t_{n}.$

Wir kommen zum Induktionsschluss. Bei ${}\alpha =\neg \beta$, ${}\alpha =\beta \wedge \gamma$ und ${}\alpha =\beta \rightarrow \gamma$ folgt die Aussage aus der Induktionsvoraussetzung, wobei man bei der Negation und der Implikation verwendet, dass eine Äquivalenz bewiesen wird.

Für eine Existenzaussage ${}\exists x\beta$ bedeutet

$I\vDash \exists x\beta ,$

dass es ein ${}m\in M$ derart gibt, dass

$I{\frac {m}{x}}\vDash \beta$

gilt. Es sei

${}n=\varphi (m)\,.$

Nach der Induktionsvoraussetzung, angewendet auf ${}\beta$ und die Interpretation ${}J{\frac {n}{x}}$, die zu ${}I{\frac {m}{x}}$ in der gleichen Beziehung steht wie ${}J$ zu ${}I$ (d.h. die Variablenbelegungen sind durch ${}\varphi$ miteinander verbunden) gilt

$J{\frac {n}{x}}\vDash \beta .$

Dies impliziert

$J\vDash \exists x\beta .$

$\Box$

Für die meisten Axiomensysteme in der Mathematik gibt es natürlich verschiedene nicht isomorphe und im Allgemeinen auch nicht elementar äquivalente Modelle. Es gibt beispielsweise eine Vielzahl an Gruppen, die - nach Definition - alle die Gruppenaxiome erfüllen, die aber ansonsten wenig miteinander zu tun haben. Interessanter ist die Frage, ob es, wenn man ein Axiomensystem für ein bestimmtes intendiertes Modell aufstellt, es dieses bis auf Isomorphie festlegt (oder ob es nichtisomorphe Modelle gibt) oder ob es die Menge aller gültigen elementaren Aussagen vollständig festlegt, also ob alle im intendierten Modell gültigen Sätze aus dem Axiomensystem ableitbar sind.