Herbrand-Interpretation

In der mathematischen Logik ist eine Herbrand-Interpretation einer Sprache der Logik erster Stufe mit Signatur ${\mathcal {S}}$ eine ${\mathcal {S}}$-Interpretation ${\mathcal {I}}=(U,I)$, bei der das Universum $U$ das Herbrand-Universum über ${\mathcal {S}}$, d. h. die Menge aller Terme ohne Variablen, ist, und jeder Term „durch sich selbst“ interpretiert wird. Somit lässt sich eine Herbrand-Interpretation vollständig durch die Angabe der Interpretation der Relationssymbole beschreiben.

Formal wird jedes Funktionssymbol $f\in {\mathcal {S}}$ durch die Funktion $f^{I}\colon U\to U;\ t\mapsto f(t)$ interpretiert. Die Menge $HB$ der einfachen Aussagen heißt Herbrand-Basis zu ${\mathcal {S}}$. Die Interpretation der Relationssymbole ist nun vollständig spezifiziert durch eine Teilmenge ${\mathcal {A}}\subseteq HB$ der Herbrand-Basis, wobei jedes $n$-stellige Relationssymbol $R\in {\mathcal {S}}$ durch die Relation $R^{I}=\{(t_{1},\dotsc ,t_{n})\in U^{n}\mid R(t_{1},\dotsc ,t_{n})\in {\mathcal {A}}\}$ interpretiert wird.

Beispiel

Enthalte die Signatur $S$ nur das Konstantensymbol $a$ und das Funktionssymbol $f$. Das zugehörige Herbrand-Universum ist $D\left({\mathcal {S}}\right)=\{a,f(a),f(f(a)),...\}$. Dann lautet die Zuordnung zwischen Funktionssymbolen und Elementen aus dem Universum:

$f^{I}(a)=f(a)$

$f^{I}(f(a))=f(f(a))$

$f^{I}(f(f(a)))=f(f(f(a)))$

...