Funktionsinterpretation

Funktionsinterpretation bezeichnet in der Logik und der Modelltheorie die Zuweisung einer konkreten Bedeutung zu Funktionensymbolen eines formalen Sprachsystems innerhalb einer Struktur. In einem Signaturensystem Sigma enthält man Funktionssymbole unterschiedlicher Arity, Relationensymbole und Konstanten. Eine Struktur A für Sigma ordnet jedem Konstantensymbol c ein Element c^A aus der Domäne D von A zu; jedem n-stelligem Funktionssymbol f gibt sie eine tatsächliche Funktion f^A: D^n → D; jedem Relationenssymbol R ordnet sie eineRelation R^A ⊆ D^n zu.

Term- und Formeldinterpretation: Aus den Symbolen und der Struktur ergibt sich die Interpretation von Begriffen (Termen) durch rekursive Anwendung der Funktionsinterpretationen. Haben T = f(t1,…,tn), dann gilt T^A = f^A(t1^A,…,tn^A). Die Wahrheit von Formeln wird im Modell durch eine Belegung (Substitution von Variablen) bewertet, wodurch Aussagen über die Domäne D in A sinnvoll geprüft werden.

Beispiele: In der reellen Zahlstruktur R mit Signatur {+, ·, 0, 1} wird +^R als gewöhnliche Addition, ·^R als Multiplikation, 0^R als Null und 1^R als Eins interpretiert. Andere Strukturen können dieselben Symbolen unterschiedliche Interpretationen zuordnen, was unterschiedliche Modelle derselben Signatur ermöglicht.

Bedeutung: Die Funktionsinterpretation ist zentral für die Semantik erster Ordnungen. Sie bestimmt, wie Terme ausgewertet und wie Formeln in Strukturen wahr werden. Sie ermöglicht Konzepte wie Homomorphismen, isomorphe Strukturen und elementare Äquivalenz sowie Anwendungen in Mathematik, Informatik und Beweistheorie.