Signatur (Modelltheorie)

In der mathematischen Logik ist eine Signatur die Menge der Symbole, durch deren semantische Interpretation sich verschiedene Strukturen (insbesondere Modelle von Aussagen der Logik) unterscheiden können.

Inhaltsverzeichnis

1 Motivation
2 Einordnung und Abgrenzung
3 Formale Definition
4 Siehe auch

Motivation

Sollen Aussagen über ein bestimmtes Gebiet formalisiert werden, ist zunächst zu entscheiden, über welche Objekte und welche Beziehungen Aussagen getroffen werden sollen. Für jedes benennbare Objekt wird eine Konstante eingeführt und für jede Beziehung ein Relationssymbol. Beispielsweise, um über die Anordnung von natürlichen Zahlen zu sprechen, wird für jede Zahl eine Konstante eingeführt und Relationssymbole < und >.

Meistens braucht man darüber hinaus noch Funktionen, mit denen man über den Konstanten rechnen kann, z. B. ein Symbol (+) für die Addition der natürlichen Zahlen.

Somit gibt es drei Arten von Symbolen, die in Signaturen vorkommen:

Konstantensymbole: Sie stehen für genau einen Wert.
Funktionssymbole: Sie stehen für eine Zuordnungsvorschrift von Werten auf andere.
Relationssymbole (Prädikate): Sie stehen für Beziehungen von geordneten Mengen (Tupeln) von Werten, oft ausgedrückt als die Teilmenge aller Tupel, für die das Prädikat gilt.

Nicht zur Signatur gehören Variablensymbole, deren Wert in der Formel nicht interpretiert wird.

Einordnung und Abgrenzung

Die zur Bildung logischer Aussagen und Formeln erlaubten Zeichen kann man somit grob einteilen in

Zeichen, die die Struktur (den Aufbau) der Aussage bzw. Formel definieren:
- Junktorensymbole
- Quantorensymbole
Terminale Zeichen, die für Werte und deren Beziehungen stehen:
- Variablen
- Symbole der Signatur
  - Konstanten
  - Funktionssymbole
  - Relationssymbole (Prädikate)

Terme und Aussagen gehören nicht zur Signatur, aber aus den Funktions- und Konstantensymbolen der Signatur und aus Variablen können Terme gebildet werden.

Werden Terme als Argumente in die Relationssymbole eingesetzt, entstehen atomare Aussagen der Prädikatenlogik. Auch Vergleiche von Termen $t 1 = t 2$ gelten in der Prädikatenlogik als atomare Aussagen. Aus ihnen können durch Verknüpfungen zusammengesetzte Aussagen gebildet werden.

Eine Interpretation der Symbole der Signatur bestimmt die Struktur, über die Aussagen gemacht werden können.

Formale Definition

Prädikatenlogische Definition

Eine endliche Signatur $\sigma=\{R_1,\ldots,R_k,f_1,\ldots,f_l, c_1,\ldots,c_m, \}$ ist eine endliche Menge von

Relationssymbolen $R_1,\ldots,R_k$ , jedes mit einer gegebenen Stelligkeit $ar(R_i)\in\mathbb{N}$ , $1\leq i\leq k$ ,
Funktionssymbolen $f_1,\ldots,f_l$ , jedes mit einer gegebenen Stelligkeit $ar(f_i)\in\mathbb{N}$ , $1\leq i\leq l$
und Konstantensymbolen $c_1,\ldots,c_m$ .

Anmerkungen

Konstanten können auch als nullstellige Funktionen aufgefasst werden.
Eine Einstellige Relation nennt man monadisch.

Semantik einer Signatur

Die Bedeutung (Interpretation) dieser Symbole ergibt sich aus der Definition einer zugehörigen Struktur:

Ein Tupel $\mathcal{A}=(A,R_1^{\mathcal{A}},\ldots,R_k^{\mathcal{A}},f_1^{\mathcal{A}},\ldots,f_l^{\mathcal{A}}, c_1^{\mathcal{A}},\ldots,c_m^{\mathcal{A}})$ ist eine $σ$ -Struktur, falls gilt:

A ist eine Menge,
$R^{\mathcal{A}}\subseteq A^{ar(R)}$ für jedes Relationssymbol $R\in\sigma$
$f^{\mathcal{A}}: A^{ar(R)} \mapsto A$ für jedes Relationssymbol $f\in\sigma$
und $c^{\mathcal{A}}\in A$ für jedes Konstantensymbol $c\in\sigma$

$A$ heißt auch Universum oder Trägermenge von $\mathcal{A}$ . Ist $A$ endlich, so heißt $\mathcal{A}$ endliche Struktur.

Anmerkungen

Wenn eine Sprache keine Relationen, oder wenn sie keine Funktionen enthält, hat sie oft spezielle Eigenschaften. Bei der Wahl der Formalisierung kann man jede Funktion auch als Relation darstellen (mit dem Funktionswert an letzter Position).
Die Bedingung der Endlichkeit der Signatur wird oft weggelassen.