Prädikatenlogik/Interpretationen/Grundsymbole/Einführung/Textabschnitt

Definition

Es sei ${}S$ das Symbolalphabet einer Sprache erster Stufe. Unter einer ${}S$-Struktur versteht man eine nichtleere Menge ${}M$ mit den folgenden Festlegungen.

1. Für jede Konstante ${}c\in K$ ist ein Element ${}c^{M}\in M$ festgelegt.
2. Zu jedem ${}n$-stelligen Funktionssymbol ${}f$ (aus ${}S$) ist eine ${}n$-stellige Funktion

   $f^{M}\colon M^{n}\longrightarrow M$

   festgelegt.

3. Zu jedem ${}n$-stelligen Relationssymbol ${}R$ (aus ${}S$) ist eine ${}n$-stellige Relation

   ${}R^{M}\subseteq M^{n}\,$

   festgelegt.

Unter einer ${}S$-(Variablen)belegung in ${}M$ versteht man eine Festlegung ${}x^{M}\in M$ für jede Variable ${}x\in V$.

Unter einer ${}S$-Interpretation versteht man eine ${}S$-Struktur zusammen mit einer ${}S$-Belegung.

Die Menge ${}M$ heißt auch Grundmenge der ${}S$-Struktur bzw. der ${}S$-Interpretation. Die Festlegung für die Konstanten und die Variablen ist einfach eine Abbildung von ${}K$ bzw. von der Variablenmenge in die Menge ${}M$. Statt ${}c^{M},x^{M},F^{M},R^{M}$ schreibt man auch ${}I(c),I(x),F^{I},R^{I}$, wobei ${}I$ eine Interpretation bezeichnet. Die Strukturen sind die üblichen Gegenstände der Mathematik (die Belegung von freien Variablen ist der mathematischen Praxis eigentlich fremd; durch sie wird sichergestellt, dass bei einer Interpretation jeder Ausdruck wahr oder falsch wird).

Beispiel

Es sei ${}S$ ein Symbolalphabet, das außer einer Variablenmenge ${}V$ aus einem einzigen einstelligen Funktionssymbol ${}F$ bestehe (die Konstantenmenge und die Relationssymbolmengen seien also leer). Eine ${}S$-Struktur besteht dann aus einer nichtleeren Menge ${}M$ zusammen mit einer Abbildung

$f=F^{M}\colon M\longrightarrow M,\,a\longmapsto f(a).$

Beispiele sind ${}M=\mathbb {N}$ mit der Nachfolgerfunktion, ${}M=\mathbb {R}$ mit dem Quadrieren ${}x\mapsto x^{2}$ oder der Sinusfunktion oder der Exponentialfunktion, oder eine beliebige Menge mit der Identität, eine endliche Menge mit einer Permutation, u.s.w.

Beispiel

Es sei ${}S$ ein Symbolalphabet, das außer einer Variablenmenge ${}V$ aus einem einzigen zweistelligen Funktionssymbol ${}F$ bestehe (die Konstantenmenge und die Relationssymbolmengen seien also leer). Eine ${}S$-Struktur besteht dann aus einer nichtleeren Menge ${}M$ zusammen mit einer Abbildung

$f=F^{M}\colon M\times M\longrightarrow M,\,(a,b)\longmapsto f(a,b).$

Eine solche Abbildung nennt man auch eine Verknüpfung auf ${}M$; sie ordnet (einem geordneten Paar aus) zwei Elementen der Menge ein weiteres Element der Menge zu. Die Addition oder die Multiplikation auf den natürlichen Zahlen sind jeweils eine solche Verknüpfung. Weitere Beispiele sind die Verknüpfung in einer Gruppe, die Vektorraumaddition, das Maximum von zwei reellen Zahlen, u.s.w.

Beispiel

Es sei ${}S$ ein Symbolalphabet, das außer einer Variablenmenge ${}V$ aus einem einzigen einstelligen Relationssymbol ${}R$ bestehe (die Konstantenmenge und die Funktionssymbolmengen seien also leer). Eine ${}S$-Struktur besteht dann aus einer nichtleeren Menge ${}M$ zusammen mit einer fixierten Teilmenge ${}U\subseteq M$. Beispiele sind ${}M=\mathbb {N}$ mit der Teilmenge der Primzahlen, oder der Teilmenge der Quadratzahlen, oder ${}M=\mathbb {R}$ mit der Teilmenge der positiven Zahlen, oder der Teilmenge der rationalen Zahlen, u.s.w.