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. Die Signatur ist der spezifische Teil einer elementaren Sprache.

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 < (kleiner als) und > (größer als).

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 können:

• 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.

Eine Signatur ohne Relationssymbole wird als algebraische Signatur bezeichnet, und eine Signatur ohne Funktionssymbole als relationale Signatur.

Einordnung und Abgrenzung

Nicht zur Signatur gehören Variablensymbole, deren Wert in der Formel nicht interpretiert wird, und weitere Zeichen, die dem Aufbau einer Aussage bzw. Formel dienen. Alle diese Zeichen gemeinsam bilden die von der Signatur erzeugte elementare Sprache. Eine Sprache $L$ umfasst also mehr Zeichen als die zugehörige Signatur $\sigma(L)$.

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$.

Semantik einer Signatur

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

Eine $\sigma$-Struktur ist 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}})$, bestehend aus

• einer Menge A,
• Relationen $R_h^{\mathcal{A}}\subseteq A^{ar(R_h)}$ für alle Relationssymbole $R_h\in\sigma$,
• Funktionen $f_i^{\mathcal{A}}: A^{ar(f_i)} \mapsto A$ für alle Funktionssymbole $f_i\in\sigma$ und
• Konstanten $c_j^{\mathcal{A}}\in A$ für alle Konstantensymbole $c_j\in\sigma$.

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

Anmerkungen

1. Konstanten können auch als nullstellige Funktionen aufgefasst werden.
2. Eine einstellige Relation nennt man monadisch.
3. 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).
4. Die Bedingung der Endlichkeit der Signatur wird oft weggelassen.

Siehe auch

• Prädikatenlogik, Logische Aussage, Aussageform, Junktoren, Quantoren, Variablen, Terme