Seien c ein Konstantensymbol, f ein zweistelliges Funktionssymbol und R ein einstelliges Relationssymbol. In der erststufigen
Logik ohne Gleichheit betrachten wir die Theorie T = {¬Rc,Rf (f (c,c),c)} und die Formel
ϕ = ∃x∃yψ(x, y) = ∃x∃y(¬Rx ∧ ¬Ry ∧ Rf (x, y)}.
(a) Zeigen Sie T ϕ.
(b) Was sagt der Satz von Herbrand in dieser Situation voraus?
(c) Geben Sie Terme ti j für 1 ≤ i, j ≤ 2 an, sodass T ψ(t11, t12) ∨ ψ(t21, t22) gilt.
(d) Zeigen Sie: Es gibt keine Terme t11, t12 mit T ψ(t11, t12).
(e) Interpretieren Sie Ihre Ergebnisse über der Struktur
A = (A,cA , fA ,RA ) = (R,p2,(x, y) 7→ xy
, {x ∈ R| “x is rational”}).
