Endliches Modell/Elementar äquivalent und isomorph/Fakt/Beweis

Beweis

Dass eine Isomorphie elementare Äquivalenz impliziert, wurde in Fakt bewiesen. Für die Umkehrung seien also die beiden Strukturen elementar äquivalent, und ${}M$ habe ${}r$ Elemente. Dann gilt in ${}M$ die Aussage

$\exists x_{1}\exists x_{2}\ldots \exists x_{r}{\left(x_{1}\neq x_{2}\wedge x_{1}\neq x_{3}\wedge \ldots \wedge x_{1}\neq x_{r}\wedge x_{2}\neq x_{3}\wedge \ldots \wedge x_{2}\neq x_{r}\wedge \ldots \wedge x_{r-1}\neq x_{r}\right)}$

und die entsprechende Aussage für ${}r+1$ gilt nicht. Aufgrund der elementaren Äquivalenz gilt diese Aussage (bzw. die entsprechende Aussage) auch (nicht) in ${}N$. D.h. ${}N$ ist ebenfalls endlich mit ${}r$ Elementen.

Wir konstruieren nun sukzessive Teilmengen ${}S_{j}\subset S_{j+1}\subseteq M$, wobei die ${}S_{j}$ funktional abgeschlossen sind, und Abbildungen

$\psi _{j}\colon S_{j}\longrightarrow N$

mit ${}\psi _{j+1}{|}_{S_{j}}=\psi _{j}$ und derart, dass die ${}\psi _{j}$ für jedes ${}j$ Isomorphismen zwischen ${}S_{j}$ und ${}T_{j}=\operatorname {bild} \psi _{j}$ sind.

Wir wählen ${}m_{1}\in M$ beliebig und setzen ${}S_{1}$ als die kleinste, funktional abgeschlossene Teilmenge in ${}M$ an, die ${}m_{1}$ enthält. Nach Fakt gibt es einen Ausdruck ${}\alpha$ in einer freien Variablen, der die elementare Äquivalenzklasse ${}[m_{1}]$ beschreibt. Wir wählen ein Element ${}n_{1}\in N$ aus der ${}\alpha$ entsprechenden Äquivalenzklasse in ${}N$ (und diese ist nicht leer wegen der elementaren Äquivalenz zwischen ${}M$ und ${}N$) und setzen

${}\psi _{1}(m_{1}):=n_{1}\,.$

Für jedes formal-zusammengesetzte Funktionssymbol ${}F$ definieren wir (hierbei wird überall ${}m_{1}$ bzw. ${}n_{1}$ eingesetzt)

${}\psi _{1}(F^{M}(m_{1})):=F^{N}(\psi _{1}(m_{1}))=F^{N}(n_{1})\,.$

Diese Abbildung ist wohldefiniert. Ist nämlich

${}m=F^{M}(m_{1})=G^{M}(m_{1})\,,$

so gilt in ${}M$

$\forall x{\left(\alpha \rightarrow F(x)=G(x)\right)},$

da dies für ${}m_{1}$ gilt und daher auch für alle dazu elementar äquivalenten Elemente, und da für die dazu nicht elementar äquivalenten Elemente der Vordersatz nicht gilt. Diese Aussage gilt dann auch bei Interpretation über ${}N$. Daher ist

${}F^{N}(n_{1})=G^{N}(n_{1})\,.$

Wir müssen zeigen, dass ein Homomorphismus vorliegt. Die Verträglichkeit mit den Funktionssymbolen folgt unmittelbar aus der Definition der Abbildung. Ferner wird jedes Element zu einem Element aus der entsprechenden Äquivalenzklasse abgebildet. Nach (dem Beweis zu) Fakt und wegen der elementaren Äquivalenz berücksichtigt ${}\psi$ daher die Relationen. Dies gilt in beide Richtungen, d.h. eine Relation trifft auf ein Tupel genau dann zu, wenn dies auf das Bildtupel zutrifft. Die Abbildung ist injektiv: Zu zwei Elementen ${}m,m'\in S_{1}$ gibt es zusammengesetzte Funktionssymbole ${}F$ und ${}G$ mit ${}m=F^{M}(m_{1})$ und ${}m'=G^{M}(m_{1})$ Bei ${}m\neq m'$ gilt

$\vDash \forall x{\left(\alpha \rightarrow Fx\neq Gx\right)},$

da dies bei Interpretation von ${}x$ durch ${}m_{1}$ gilt, und diese Aussage gilt auch in ${}N$. Die Abbildung ist surjektiv auf das Bild, also liegt wegen der Äquivalenz bei den Relationen insgesamt ein Isomorphismus vor.

Es seien nun ${}S_{j}$ und ${}\psi _{j}$ schon konstruiert und ${}S_{j}\neq M$. Wir wählen ${}m_{j+1}\in M\setminus S_{j}$ und setzen ${}S_{j+1}$ als die funktionale Hülle von ${}S_{j}\cup \{m_{j+1}\}$ an. Wir betrachten die Menge aller Tupel ${}(\beta ,a_{1},\ldots ,a_{k})$, wobei ${}\beta \in L^{S}$ ein Ausdruck in den freien Variablen ${}x_{1},\ldots ,x_{k}$ und ${}y$ ist und wobei ${}a_{1},\ldots ,a_{k}\in S_{j}$ mit der Eigenschaft, dass

$I{\frac {a_{1},\ldots ,a_{k}}{x_{1},\ldots ,x_{k}}}{\frac {m_{j+1}}{y}}\vDash \beta$

gilt. Dabei sei ${}I$ eine fixierte Interpretation auf ${}M$ und ${}J$ entsprechend eine Interpretation auf ${}N$. Es gilt dann insbesondere

$I{\frac {a_{1},\ldots ,a_{k}}{x_{1},\ldots ,x_{k}}}\vDash \exists y\beta .$

Daher gilt nach Fakt (angewendet auf den Isomorphismus ${}\psi _{j}$ mit ${}b_{i}=\psi _{j}(a_{i})$) auch

$J{\frac {b_{1},\ldots ,b_{k}}{x_{1},\ldots ,x_{k}}}\vDash \exists y\beta ,$

und insbesondere gibt es ein (zunächst von ${}\beta$ abhängiges) ${}n\in N$ mit

$J{\frac {b_{1},\ldots ,b_{k}}{x_{1},\ldots ,x_{k}}}{\frac {n}{y}}\vDash \beta .$

Dann gibt es auch ein ${}n\in N$, das man für alle ${}\beta$ nehmen kann. Für jedes einzelne ${}\beta$ ist nämlich die erfüllende Elementmenge nicht leer, und wenn der Durchschnitt über alle ${}\beta$ leer wäre, dann schon für eine endliche Teilmenge und dann auch für die endliche Konjunktion darüber. Es sei ${}n_{j+1}$ ein solches Element. Wir setzen nun

${}\psi _{j+1}(m_{j+1}):=n_{j+1}\,$

und definieren

${}\psi _{j+1}(F^{M}(a_{1},\ldots ,a_{k},m_{j+1})):=F^{N}(b_{1},\ldots ,b_{k},n_{j+1})\,$

für jedes ${}k+1$-stellige formal zusammengesetzte Funktionssymbol ${}F$. Die Wohldefiniertheit von ${}\psi _{j+1}$, die Verträglichkeit mit den Funktionssymbolen und mit den Relationssymbolen (in beide Richtungen) sowie die Bijektivität und damit die Isomorphieeigenschaft folgt wie oben.

Da ${}M$ endlich ist, erhalten wir, wenn wir diesen Konstruktionsschritt iterieren, insgesamt eine injektive Abbildung

$\psi \colon M\longrightarrow N.$

Da ${}M$ und ${}N$ gleich viele Elemente besitzen, ist diese auch surjektiv und insgesamt erhalten wir einen Isomorphismus.

Zur bewiesenen Aussage