Kurs:Einführung in die mathematische Logik (Osnabrück 2016)/Vorlesung 16/latex
\setcounter{section}{16}
\zwischenueberschrift{ $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.
\inputdefinition
{}
{
Es sei $S$ ein
\definitionsverweis {erststufiges Symbolalphabet}{}{}
und
\mathkor {} {M} {und} {N} {}
seien
$S$-\definitionsverweis {Strukturen}{}{.}
Eine Abbildung
\maabbdisp {\varphi} {M} {N
} {}
heißt
\definitionswortpraemath {S}{ Homomorphismus }{,}
wenn folgende Eigenschaften gelten.
\aufzaehlungdrei{Für jede Konstante
\mavergleichskette
{\vergleichskette
{c
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{\varphi { \left( c^M \right) }
}
{ =} { c^N
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
}{Für jedes $n$-stellige Funktionssymbol
\mavergleichskette
{\vergleichskette
{f
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ist
\mavergleichskettedisp
{\vergleichskette
{ \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
\mavergleichskette
{\vergleichskette
{ m_1 , \ldots , m_n
}
{ \in }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}{Für jedes $n$-stellige Relationsymbol
\mavergleichskette
{\vergleichskette
{R
}
{ \in }{S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
impliziert die Gültigkeit von
\mathdisp {R^M (m_1 , \ldots , m_n )} { }
die Gültigkeit von
\mathdisp {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.
\inputdefinition
{}
{
Es sei $S$ ein \definitionsverweis {erststufiges Symbolalphabet}{}{} und \mathkor {} {M} {und} {N} {} seien $S$-\definitionsverweis {Strukturen}{}{.} Eine \definitionsverweis {bijektive Abbildung}{}{} \maabbdisp {\varphi} {M} {N } {} heißt \definitionswortpraemath {S}{ Isomorphismus }{,} wenn sowohl $\varphi$ als auch die \definitionsverweis {Umkehrabbildung}{}{} $\varphi^{-1}$ ein $S$-\definitionsverweis {Homomorphismus}{}{} ist.
}
Zwei $S$-Strukturen heißen $S$-\stichwort {isomorph} {,} wenn es einen $S$-Isomorphismus zwischen ihnen gibt. Bei
\mavergleichskette
{\vergleichskette
{M
}
{ = }{N
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
spricht man auch von einem \stichwort {Automorphismus} {.}
\inputbeispiel{}
{
Es sei $S$ ein \definitionsverweis {erststufiges Symbolalphabet}{}{,} das nur aus einer Variablenmenge besteht, die Konstantenmenge und die Mengen der Funktionssymbole und der Relationssymbole seien also leer. Dann ist jede \zusatzklammer {nichtleere} {} {} Menge $M$ unmittelbar eine $S$-\definitionsverweis {Struktur}{}{} und jede Abbildung \maabbdisp {\varphi} {M} {N } {} ist ein $S$-\definitionsverweis {Homomorphismus}{}{.} Insbesondere ist jede bijektive Abbildung \maabbdisp {\varphi} {M} {N } {} ein $S$-\definitionsverweis {Isomorphismus}{}{.}
}
\inputbemerkung
{}
{
Es sei $S$ ein \definitionsverweis {erststufiges Symbolalphabet}{}{} und \mathkor {} {M} {und} {N} {} seien $S$-\definitionsverweis {Strukturen}{}{.} Eine \definitionsverweis {bijektive Abbildung}{}{} \maabbdisp {\varphi} {M} {N } {,} die ein $S$-\definitionsverweis {Homomorphismus}{}{} ist, muss kein $S$-\definitionsverweis {Isomorphismus}{}{} sein, da die Umkehrabbildung $\varphi^{-1}$ im Allgemeinen kein Homomorphismus sein muss. Deshalb fordert man in der Definition eines \definitionsverweis {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 \maabb {\varphi} {M} {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 \zusatzklammer {allerdings nicht erststufig formulierten} {} {} \definitionsverweis {Dedekind-Peano-Axiome}{}{} zueinander isomorph sind. Dabei war $0$ die einzige Konstante und die Nachfolgerabbildung die einzige \zusatzklammer {einstellige} {} {} Funktion. Auch zwei Modelle der reellen Zahlen sind isomorph, was schwieriger zu beweisen ist, siehe Satz 47.1 (Grundkurs Mathematik (Osnabrück 2022-2023)). 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 $\R$ eingeführt werden. Je zwei solche algebraische Abschlüsse sind untereinander isomorph, allerdings ist die Isomorphie nicht eindeutig bestimmt. Beispielsweise ist die \definitionsverweis {komplexe Konjugation}{}{} ein nichttrivialer Automorphismus auf ${\mathbb C}$.
{Homomorphielemma/Term/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $S$ ein
\definitionsverweis {erststufiges Sym\-bolalphabet}{}{,}
\mathkor {} {M} {und} {N} {}
seien
$S$-\definitionsverweis {Strukturen}{}{}
und
\maabbdisp {\varphi} {M} {N
} {}
ein
$S$-\definitionsverweis {Homomorphismus}{}{.}
Es sei $\lambda$ eine
\definitionsverweis {Variablenbelegung}{}{}
in $M$ und
\mathl{\varphi \circ \lambda}{} die nach $N$ übertragene Variablenbelegung. Es seien
\mathkor {} {I} {und} {J} {}
die zugehörigen Interpretationen.}
\faktfolgerung {Dann ist
\mavergleichskettedisp
{\vergleichskette
{\varphi(I(t))
}
{ =} {J(t)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
für alle
$S$-\definitionsverweis {Terme}{}{}
$t$.}
\faktzusatz {}
\faktzusatz {}
{ Siehe Aufgabe 16.6. }
\zwischenueberschrift{Elementare Äquivalenz und Isomorphiesatz}
\inputdefinition
{}
{
Zwei $S$-\definitionsverweis {Strukturen}{}{} $M$ und $N$ über einem \definitionsverweis {erststufigen Symbolalphabet}{}{} $S$ heißen \definitionswort {elementar äquivalent}{,} wenn jeder $S$-\definitionsverweis {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 \stichwort {Isomorphiesatz} {} \zusatzklammer {oder \stichwort {Isomorphielemma} {}} {} {.}
\inputfaktbeweis
{Isomorphielemma/Elementare Äquivalenz/Fakt}
{Satz}
{}
{
\faktsituation {Es seien
\mathkor {} {M} {und} {N} {}}
\faktvoraussetzung {\definitionsverweis {isomorphe}{}{}
$S$-\definitionsverweis {Strukturen}{}{}
über einem
\definitionsverweis {Symbolalphabet}{}{}
$S$.}
\faktfolgerung {Dann sind
\mathkor {} {M} {und} {N} {}
\definitionsverweis {elementar äquivalent}{}{.}}
\faktzusatz {Genauer: Zu einem Isomorphismus
\maabbdisp {\varphi} {M} {N
} {}
und einer Variablenbelegung $\lambda$ auf $M$ und der zugehörigen Variablenbelegung
\mathl{\varphi \circ \lambda}{} auf $N$ mit den zugehörigen Interpretationen
\mathkor {} {I} {und} {J} {}
gilt für jeden
$S$-\definitionsverweis {Ausdruck}{}{}
$\alpha$ die Äquivalenz
\mathdisp {I \vDash \alpha \text{ genau dann, wenn } J \vDash \alpha} { . }
}
\faktzusatz {}
}
{
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
\maabbdisp {\varphi} {M} {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
\mathl{I \vDash \alpha}{} die Gültigkeit von
\mathl{J \vDash \alpha}{} folgt. Für einen Ausdruck der Form
\mavergleichskettedisp
{\vergleichskette
{s
}
{ =} {t
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
mit Termen
\mathl{s,t}{} bedeutet
\mathdisp {I \vDash s=t} { }
einfach
\mavergleichskettedisp
{\vergleichskette
{I(s)
}
{ =} {I(t)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Daher ist
\mavergleichskettedisp
{\vergleichskette
{J(s)
}
{ =} {\varphi(I(s))
}
{ =} {\varphi(I(t))
}
{ =} {J(t)
}
{ } {
}
}
{}{}{}
und somit
\mathdisp {J \vDash s=t} { . }
Für ein $n$-stelliges Relationssymbol $R$ und $n$ Terme
\mathl{t_1 , \ldots , t_n}{} bedeutet
\mathdisp {I \vDash R t_1 \ldots t_n} { , }
dass $R^M$ auf
\mathl{\left( I(t_1) , \, \ldots , \, I(t_n) \right)}{} zutrifft. Dann trifft aufgrund der Homomorphie von $\varphi$ auch $R^N$ auf
\mavergleichskettedisp
{\vergleichskette
{ \left( \varphi (I(t_1)) , \, \ldots , \, \varphi (I(t_n)) \right)
}
{ =} { \left( J(t_1) , \, \ldots , \, J(t_n) \right)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
zu. Also ist
\mathdisp {J \vDash R t_1 \ldots t_n} { . }
Wir kommen zum Induktionsschluss. Bei
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ \neg \beta
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ = }{ \beta \wedge \gamma
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und
\mavergleichskette
{\vergleichskette
{ \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
\mathl{\exists x \beta}{} bedeutet
\mathdisp {I \vDash \exists x \beta} { , }
dass es ein
\mavergleichskette
{\vergleichskette
{m
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
derart gibt, dass
\mathdisp {I { \frac{ m }{ x } } \vDash \beta} { }
gilt. Es sei
\mavergleichskettedisp
{\vergleichskette
{n
}
{ =} {\varphi(m)
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Nach der Induktionsvoraussetzung, angewendet auf $\beta$ und die Interpretation
\mathl{J { \frac{ n }{ x } }}{,} die zu
\mathl{I { \frac{ m }{ x } }}{} in der gleichen Beziehung steht wie $J$ zu $I$
\zusatzklammer {d.h. die Variablenbelegungen sind durch $\varphi$ miteinander verbunden} {} {}
gilt
\mathdisp {J { \frac{ n }{ x } } \vDash \beta} { . }
Dies impliziert
\mathdisp {J \vDash \exists x \beta} { . }
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
\zusatzgs {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
\zusatzklammer {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.
\zwischenueberschrift{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.
\inputdefinition
{}
{
Es sei $S$ ein
\definitionsverweis {erststufiges Symbolalphabet}{}{}
und $M$ eine
$S$-\definitionsverweis {Struktur}{}{.}
Wir nennen zwei Elemente
\mavergleichskette
{\vergleichskette
{m,n
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
\definitionswort {elementar äquivalent}{,}
wenn für jeden Ausdruck
\mavergleichskette
{\vergleichskette
{ \alpha
}
{ \in }{ L_1^ S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
in der einen freien Variablen $x$ und jede Variablenbelegung $\lambda$ auf $M$ die Beziehung
\mathdisp {I \frac{m}{x} \vDash \alpha \text{ genau dann, wenn } I \frac{n}{x} \vDash \alpha} { }
gilt.
}
Die elementare Äquivalenz drücken wir durch
\mavergleichskette
{\vergleichskette
{m
}
{ \sim }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
aus. Dabei handelt es sich offenbar um eine Äquivalenzrelation auf der Menge $M$. Wenn
\maabbdisp {\varphi} {M} {M
} {}
ein $S$-Isomorphismus
\zusatzklammer {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
\mathkor {} {I= \tilde{I} { \frac{ m }{ x } }} {und} {J= \tilde{I} { \frac{ n }{ x } }} {}
folgt. Zu zwei nicht elementaar äquivalenten Elementen
\mavergleichskette
{\vergleichskette
{m,n
}
{ \in }{M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
nennen wir einen Ausdruck $\alpha$ mit
\mathkor {} {I \frac{m}{x} \vDash \alpha} {und} {I \frac{n}{x} \vDash \neg \alpha} {}
einen \stichwort {trennenden Ausdruck} {.}
\inputbeispiel{}
{
Es sei $S$ ein Symbolalphabet, das neben Variablen aus einem einzigen einstelligen Funktionssymbol $f$ besteht und es sei
\mavergleichskette
{\vergleichskette
{M
}
{ = }{ \{1 , \ldots , 6 \}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
eine
$S$-\definitionsverweis {Struktur}{}{,}
wobei $f$ als die
\definitionsverweis {Permutation}{}{}
$\pi$ mit
\wertetabellesechsausteilzeilen { $x$ }
{\mazeileundfuenf {1} {2} {3} {4} {5} }
{ {6} }
{ $\pi(x)$ }
{\mazeileundfuenf {3} {5} {1} {4} {6} }
{ {2} }
interpretiert werde. Hier sind die Äquivalenzklassen zur
\definitionsverweis {elementaren Äquivalenz}{}{}
gleich der sogenannten Zykelzerlegung, nämlich gleich
\mathl{\{1,3\}}{,}
\mathl{\{2,5,6\}}{} und
\mathl{\{4\}}{.} Die Ordnung der Elemente kann man in der Sprache zu $S$ ausdrücken und erhält dadurch trennende Ausdrücke, beispielsweise ist
\mavergleichskette
{\vergleichskette
{fx
}
{ = }{x
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein Ausdruck in der einen freien Variablen $x$, der genau dann wahr wird, wenn $x$ durch $4$ belegt wird. Der Ausdruck
\mathdisp {{ \left( ffx = x \right) } \wedge \neg { \left( fx = x \right) }} { }
ist ein Ausdruck, der genau dann wahr wird, wenn $x$ durch
\mathkor {} {1} {oder} {3} {}
belegt wird, u.s.w. Dass
\mathkor {} {1} {oder} {3} {}
zueinander elementar äquivalent sind, sieht man am einfachsten, wenn man den Automorphismus betrachtet, der durch die Transposition
\mathl{1 \leftrightarrow 3}{} gegeben ist. Dieser ist nämlich ein
$S$-\definitionsverweis {Automorphismus}{}{}
und daher können wir
den Isomorphiesatz
anwenden.
}
\inputbeispiel{}
{
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
\mavergleichskette
{\vergleichskette
{x
}
{ = }{y
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
den wir $\alpha$ nennen, und zwei Elemente
\mavergleichskette
{\vergleichskette
{m
}
{ \neq }{n
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
aus $M$. In der Interpretation $I$ sei $y$ durch $m$ belegt. Dann gilt
\mathl{I { \frac{ m }{ x } } \vDash \alpha}{,} denn dies bedeutet
\mavergleichskette
{\vergleichskette
{m
}
{ = }{m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
aber
\mathl{I { \frac{ n }{ x } } \not\vDash \alpha}{,} denn dies bedeuet
\mavergleichskette
{\vergleichskette
{n
}
{ = }{m
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
}
Für eine Konstante in
\mavergleichskette
{\vergleichskette
{c
}
{ \in }{ S
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
die in $M$ als das Element
\mavergleichskette
{\vergleichskette
{m
}
{ = }{c^M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
interpretiert wird, ist die zugehörige Äquivalenzklasse einelementig: Sie wird durch den Ausdruck
\mavergleichskette
{\vergleichskette
{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 \stichwort {charakterisierenden Ausdruck} {} in einer freien Variablen gibt.
\inputfaktbeweis
{Prädikatenlogik/Elementare Äquivalenz/Endlich viele Klassen/Trennende Ausdrücke/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $S$ ein
\definitionsverweis {Symbolalphabet erster Stufe}{}{}
und $M$ eine
$S$-\definitionsverweis {Struktur}{}{}}
\faktvoraussetzung {mit der Eigenschaft, dass es in $M$ nur endlich viele Klassen zur
\definitionsverweis {elementaren Äquivalenz}{}{}
gibt.}
\faktfolgerung {Dann gibt es zu jeder Äquivalenzklasse
\mavergleichskette
{\vergleichskette
{ [m]
}
{ \subseteq }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
einen $S$-Ausdruck
\mathl{\alpha_{[m]}}{} in einer freien Variablen $x$, der die Klasse $[m]$ beschreibt, für den also
\mathdisp {n \in [m] \text{ genau dann, wenn } I { \frac{ n }{ x } } \vDash \alpha_{[m]}} { }
gilt.}
\faktzusatz {}
\faktzusatz {}
}
{
Es seien
\mathl{M_1 , \ldots , M_k}{} die Äquivalenzklassen der elementaren Äquivalenzrelation und sei
\mavergleichskette
{\vergleichskette
{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
\mavergleichskette
{\vergleichskette
{i
}
{ = }{ 2 , \ldots , k
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gibt es einen Ausdruck $\beta_i$ in der freien Variablen $x$ mit
\mathl{I \frac{m_1}{x} \vDash \beta_i}{,} aber
\mathl{I \frac{m_i}{x} \not\vDash \beta_i}{,} da ja
\mathkor {} {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
\mavergleichskettedisp
{\vergleichskette
{ \alpha_{1}
}
{ =} { \beta_2 \wedge \ldots \wedge \beta_k
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{}
ist in einer Interpretation
\zusatzklammer {zur
$S$-\definitionsverweis {Struktur}{}{}
$M$} {} {}
genau dann wahr, wenn die Variable $x$ durch ein Element aus $M_1$ belegt wird.
\inputbeispiel{}
{
Für das Symbolalphabet
\mathl{\{0, ' \}}{} und die natürlichen Zahlen $\N$ mit der kanonischen Interpretation sind sämtliche Klassen zur
\definitionsverweis {elementaren Äquivalenz}{}{}
einelementig und können auch durch Ausdrücke charakterisiert werden, und zwar wird die Zahl $n$ durch den Ausdruck
\mavergleichskette
{\vergleichskette
{x
}
{ = }{ 0^{\prime \prime \ldots \prime}
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
mit $n$ Strichen eindeutig beschrieben.
}
\inputbeispiel{}
{
Es sei $S$ das Symbolalphabet, das außer Variablen für jedes
\mavergleichskette
{\vergleichskette
{k
}
{ \in }{ \N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
ein einstelliges Relationssymbol $R_k$ enthält, und es sei
\mavergleichskettedisp
{\vergleichskette
{ \alpha_k
}
{ =} { R_k x
}
{ } {
}
{ } {
}
{ } {
}
}
{}{}{.}
Wir betrachten die Menge
\mavergleichskette
{\vergleichskette
{M
}
{ = }{\N_+
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{,}
wobei wir das Relationssymbol $R_k$ durch
\mathdisp {R_k^M (n) \text{ genau dann, wenn } n \text{ ein Vielfaches von } k \text{ ist }} { }
interpretieren. Zwei Elemente
\mavergleichskettedisp
{\vergleichskette
{m
}
{ \neq} {n
}
{ \in} { \N
}
{ } {
}
{ } {
}
}
{}{}{}
können dann nicht
\definitionsverweis {elementar äquivalent}{}{}
sein, da sie sich nicht gegenseitig teilen können und daher beispielsweise
\mathl{R_m^M (m)}{,} also
\mathl{I { \frac{ m }{ x } } \vDash \alpha_m}{,} aber nicht
\mathl{R_m^M (n)}{,} also
\mathl{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.16.
}
\inputfaktbeweis
{Prädikatenlogik/Elementare Äquivalenz/Trennende Ausdrücke/Relationen und Funktionen wohldefiniert/Fakt}
{Lemma}
{}
{
\faktsituation {Es sei $S$ ein
\definitionsverweis {Symbolalphabet erster Stufe}{}{}
und $M$ eine
$S$-\definitionsverweis {Struktur}{}{.}}
\faktvoraussetzung {Für jede
\definitionsverweis {elementare Äquivalenzklasse}{}{}
\mavergleichskette
{\vergleichskette
{ [m]
}
{ \subseteq }{ M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
gebe es einen $S$-Ausdruck
\mathl{\alpha_{[m]}}{} in einer freien Variablen $x$, der die Klasse
\mathl{[m]}{} beschreibt, für den also
\mathdisp {n \in [m] \text{ genau dann, wenn } I { \frac{ n }{ x } } \vDash \alpha_{[m]}} { }
gilt.}
\faktfolgerung {Dann gelten folgende Aussagen.
\aufzaehlungzwei {Für jedes $k$-stellige Relationssymbol $R$ ist $R^M$ auf den Äquivalenzklassen wohldefiniert.
} {Für jedes $k$-stellige Funktionssymbol $f$ ist $f^M$ auf den Äquivalenzklassen wohldefiniert
\zusatzklammer {und zwar in dem Sinn, dass aus
\mathl{m_1 \sim m_1' , \ldots , m_k \sim m_k'}{} die elementare Äquivalenz
\mavergleichskette
{\vergleichskette
{ f^M(m_1 , \ldots , m_k)
}
{ \sim }{ f^M( m'_1 , \ldots , m'_k)
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
folgt} {} {.}
}}
\faktzusatz {}
\faktzusatz {}
}
{
(1). Es sei $R$ ein $k$-stelliges Relationssymbol. Für ein $k$-Tupel
\mathl{(m_1 , \ldots , m_k)}{} aus $M$ mit
\mavergleichskette
{\vergleichskette
{ (m_1 , \ldots , m_k)
}
{ \in }{ R^M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
und ein weiteres dazu elementar-äquivalentes Tupel
\mathl{(n_1 , \ldots , n_k)}{}
\zusatzklammer {es gelte also
\mathlk{m_1 \sim n_1,\, m_2 \sim n_2 , \ldots , m_k \sim n_k}{}} {} {}
müssen wir
\mavergleichskette
{\vergleichskette
{ (n_1 , \ldots , n_k)
}
{ \in }{ R^M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{}
zeigen. Es seien
\mathl{\alpha_{ 1} , \ldots , \alpha_{k}}{} Ausdrücke in der einen freien
\zusatzklammer {untereinander verschiedenen} {} {}
Variablen $x_i$, die die Äquivalenzklassen zu
\mathkor {} {m_i} {bzw.} {n_i} {}
charakterisieren. Es gilt
\mathdisp {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
\mathdisp {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
\mathdisp {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
\mathdisp {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
\mathdisp {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,
\mathdisp {I { \frac{ n_1 , \ldots , n_k }{ x_1 , \ldots , x_k } } \vDash Rx_1 x_2 \ldots x_k} { }
und somit
\mavergleichskette
{\vergleichskette
{ (n_1 , \ldots , n_k)
}
{ \in }{ R^M
}
{ }{
}
{ }{
}
{ }{
}
}
{}{}{.}
(2). Die Aussage für Funktionssymbole wird ähnlich bewiesen, siehe Aufgabe 16.21.