Prädikatenlogik/Elementare Äquivalenz/Trennende Ausdrücke/Relationen und Funktionen wohldefiniert/Fakt/Beweis

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.

Zur bewiesenen Aussage