Kurs:Einführung in die mathematische Logik (Osnabrück 2018)/Vorlesung 16/kontrolle

${}S$-Homomorphismen und elementare Äquivalenz

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

Definition Referenznummer erstellen

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

$\varphi \colon M\longrightarrow N$

heißt 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, ein Ringhomomorphismus, eine lineare Abbildung zwischen Vektorräumen, eine monotone Abbildung zwischen geordneten Mengen, fallen unter diesen abstrakten Homomorphiebegriff.

Definition Referenznummer erstellen

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

$\varphi \colon M\longrightarrow N$

heißt 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 Referenznummer erstellen

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   Referenznummer erstellen

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 16.3. 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 Satz 12.3 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, siehe Fakt *****. 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 Lemma 16.5 ändern

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 16.10.

$\Box$

Elementare Äquivalenz und Isomorphiesatz

Definition Referenznummer erstellen

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. Die folgende Aussage heißt Isomorphiesatz (oder Isomorphielemma).

Satz Satz 16.7 ändern

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 Lemma 16.5 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.

Elementare Äquivalenz für Elemente

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 Definition 16.8 ändern

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 Satz 16.7 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 Referenznummer erstellen

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 Referenznummer erstellen

Wenn man in der Definition 16.8 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 Lemma 16.11 ändern

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 Referenznummer erstellen

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 Referenznummer erstellen

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 16.24.

Lemma Lemma 16.14 ändern

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 16.30.

$\Box$