Wir betrachten eine Signatur S und Ihre Erweiterung Sˆ := S ∪ {∼} um ein zweistelliges Relationssymbol ∼, das die
Gleichheit simulieren soll. Zu jeder FO(S)-Formel ϕ konstruieren wir eine FO6=(Sˆ)-Formel ϕ
∼, indem wir jede Teilformel
t1 = t2 von ϕ durch die Formel t1 ∼ t2 ersetzen. Wir wollen zeigen, dass ϕ erfüllbar ist (durch ein Modell mit mengentheoretischer
Gleichheit), wenn ϕ
∼ ein Modell hat, das die Gleichheitsaxiome für ∼ erfüllt. Sei dazu A eine Sˆ-Struktur,
die die Gleichheitsaxiome für ∼ erfüllt. Für jedes a ∈ A können wir dann die Äquivalenzklasse
[a] := [a]∼A := {b ∈ A| a ∼
A b}
betrachten (man beachte [a] = [b] ⇔ a ∼
A b). Wie in der Vorlesung definieren wir eine S-Struktur A0 durch
A0
:= {[a] | a ∈ A},
c
A0
:= [c
A ],
f
A0 [a1
] . . . [an
] := [ f
A a1
. . . an
],
([a1
], . . . , [an
]) ∈ R
A0
:⇔ (a1
, . . . , an
) ∈ R
A .
Da A die Gleichheitsaxiome erfüllt, ist dies wohldefiniert. Zu jeder Belegung β : V → A definieren wir eine Belegung
β
= : V → A0 durch
β
=
(x) := [β(x)].
Für I = (A ,β) schreiben wir I
= = (A0
,β
=). Beweisen Sie die folgenden Aussagen:
(a) Sei I = (A ,β) eine Interpretation über der Struktur A . Dann gilt t
I
=
= [t
I
] für jeden S-Term t.
(b) Sei β : V → A eine Belegung. Dann gilt β[x 7→ a]
= = β
=[x 7→ [a]] für jedes a ∈ A.
(c) Sei I = (A ,β) eine Interpretation über der Struktur A . Dann ist I ϕ
∼ äquivalent zu I
= 
