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

Beweis

(1). Es sei ein -stelliges Relationssymbol. Für ein -Tupel aus mit und ein weiteres dazu elementar-äquivalentes Tupel (es gelte also ) müssen wir zeigen. Es seien Ausdrücke in der einen freien (untereinander verschiedenen) Variablen , die die Äquivalenzklassen zu bzw. charakterisieren. Es gilt

wie ja die Belegung von durch zeigt. Ebenso gilt

wie die entsprechende Belegung zeigt. Dies ist jetzt ein Ausdruck in der einen freien Variablen . Wenn man statt mit durch ein anderes elementar äquivalentes Element belegt, so erhält man nach Definition der elementaren Äquivalenz

und damit

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

Einsetzen von für liefert also, da ja auf zutrifft,

und somit .

(2). Die Aussage für Funktionssymbole wird ähnlich bewiesen, siehe Aufgabe.