Signatur (Modelltheorie)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

In der mathematischen Logik besteht eine Signatur (auch: Sprache) aus der Menge der Symbole, die in der betrachteten Sprache zu den üblichen, rein logischen Symbolen hinzukommt, und einer Abbildung, die jedem Symbol der Signatur eine Stelligkeit eindeutig zuordnet. Während die logischen Symbole wie \forall, \exists, \land, \lor, \rightarrow, \leftrightarrow, \neg stets als „für alle“, „es gibt ein“, „und“, „oder“, „folgt“, „äquivalent zu“ bzw. „nicht“ interpretiert werden, können durch die semantische Interpretation der Symbole der Signatur verschiedene Strukturen (insbesondere Modelle von Aussagen der Logik) unterschieden werden. Die Signatur ist der spezifische Teil einer elementaren Sprache.

Beispielsweise lässt sich die gesamte Zermelo-Fraenkel-Mengenlehre in der Sprache der Prädikatenlogik erster Stufe und dem einzigen Symbol \in (neben den rein logischen Symbolen) formulieren; in diesem Fall ist die Symbolmenge der Signatur gleich \{\in\}.

Motivation[Bearbeiten]

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 jeweils für eine eindeutige Zuordnung von Werten auf andere.
  • Relationssymbole (Prädikate): Sie stehen jeweils für eine Beziehung, also für eine Zuordnung von Werten zueinander, die nicht eindeutig sein muss. Eine Beziehung wird oft ausgedrückt als die Teilmenge aller Tupel (geordnete Mengen), für die das Prädikat gilt.

Einordnung und Abgrenzung[Bearbeiten]

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 \boldsymbol S(L).

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

  • Zeichen, die die Struktur (den Aufbau) der Aussage oder Formel definieren:
  • Terminale Zeichen, die für Werte und deren Beziehungen stehen:
    • Variablen, zum Beispiel x_0, x_1, x_2, \ldots
    • Symbole der Signatur
      • Konstantensymbole, zum Beispiel 0, 1, e
      • Funktionssymbole, zum Beispiel +, {}^{-1}, f
      • Relationssymbole (Prädikate), zum Beispiel \sim, <, \in

Terme gehören nicht zur Signatur, diese werden aber aus den logischen Symbolen, den Variablen und den Funktionen- und Konstantensymbolen der Signatur und aus Variablen nach festen Bildungsregeln aufgebaut.

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.

Definition[Bearbeiten]

Es seien \mathcal C, \mathcal F und \mathcal R paarweise disjunkte Mengen von nichtlogischen Zeichen. Man nennt dann jedes Zeichen in \mathcal S := \mathcal C \cup \mathcal F \cup \mathcal R ein Symbol und \mathcal S eine Symbolmenge, wenn durch eine Abbildung \sigma\colon \mathcal S \to \N_0 jedem Zeichen in \mathcal S wie folgt eine Stelligkeit genannte Zahl eindeutig zuordnet wird:

  • \sigma(c) = 0 für alle c \in \mathcal C,
  • \sigma(f) \in \N für alle f \in \mathcal F und
  • \sigma(R) \in \N für alle R \in \mathcal R.

\boldsymbol S := (\mathcal S, \sigma) heißt dann eine Signatur und jedes c \in \mathcal C wird als ein Konstantensymbol, jedes f \in \mathcal F als ein Funktionssymbol und jedes R \in \mathcal R als ein Relationssymbol bezeichnet.

Eine Signatur \boldsymbol S = (\mathcal S, \sigma) heißt endlich, falls \mathcal S eine endliche Menge ist. Wenn eine Signatur keine Relationssymbole hat, wird sie eine algebraische Signatur genannt, wenn sie dagegen keine Konstanten- und keine Funktionssymbole besitzt, eine relationale Signatur.

Anmerkungen[Bearbeiten]

  1. Die Konstantensymbole können auch zu den Funktionssymbolen gezählt werden, sodass sich \mathcal S = \mathcal F_0 \cup \mathcal R mit \mathcal F_0 := \mathcal C \cup \mathcal F ergibt.
  2. In der Literatur wird häufig nicht zwischen einer Signatur und ihrer Symbolmenge unterschieden, die Stelligkeitsabbildung wird dann nicht als solche angegeben.

Semantik einer Signatur[Bearbeiten]

Strukturen[Bearbeiten]

\boldsymbol S = (\mathcal S, \sigma) sei eine Signatur und es bestehe die Menge \mathcal C aus allen Konstantensymbolen c \in \mathcal S, die Menge \mathcal F aus allen Funktionssymbolen f \in \mathcal S sowie die Menge \mathcal R aus allen Relationssymbolen R \in \mathcal S. Weiterhin bezeichne A eine nichtleere Menge und \mathcal A := A \cup \{B \mid B \subseteq A^n \text{ für ein } n \in \N\}. Ist dann \alpha\colon \mathcal S \to \mathcal A eine Abbildung, sodass

so nennt man \boldsymbol A := (A, \alpha) = \bigl(A, (\alpha(c))_{c \in \mathcal C} \cup (\alpha(f))_{f \in \mathcal F} \cup (\alpha(R))_{R \in \mathcal R}\bigr)[1] eine Struktur der Signatur \boldsymbol S oder kurz eine \boldsymbol S-Struktur. A ist dann die Grundmenge, die Trägermenge oder kurz der Träger von \boldsymbol A,[2] und falls A eine endliche Menge ist, so heißt ebenso \boldsymbol A endlich, sonst unendlich.

Anmerkungen[Bearbeiten]

  1. Eine Konstante \alpha(c) lässt sich als die nullstellige Funktion 0 \mapsto \alpha(c) auffassen, sodass für \mathcal F_0 := \mathcal C \cup \mathcal F gilt:
    \boldsymbol A = \bigl(A, (\alpha(f_0))_{f_0 \in \mathcal F_0} \cup (\alpha(R))_{R \in \mathcal R}\bigr) mit Funktionen \alpha(f_0) und mit Relationen \alpha(R).
  2. Jede n-1-stellige Funktion (n \in \N) ist auch stets eine n-stellige Relation (mit dem Funktionswert an letzter Position). Daher kann jede \boldsymbol S-Struktur dargestellt werden als
    \boldsymbol A = \bigl(A, (\alpha(S))_{S \in \mathcal S}\bigr) mit Relationen \alpha(S).
  3. Wenn eine Struktur nur Funktionen (algebraische Struktur) oder keine Funktionen (relationale Struktur) enthält, dann hat sie oft spezielle Eigenschaften.

Interpretationen[Bearbeiten]

Die Signatur \boldsymbol S erhält durch eine \boldsymbol S-Struktur \boldsymbol A = (A, \alpha) und eine Deutung oder Interpretation von Variablen eine bestimmte semantische Bedeutung:

Eine Abbildung \beta\colon \mathcal V \to A mit \mathcal V := \{x \mid x \text{ ist eine Variable}\} wird eine Belegung der \boldsymbol S-Struktur \boldsymbol A genannt. \boldsymbol I := (\boldsymbol A, \beta) heißt dann eine Interpretation der Signatur \boldsymbol S oder kurz eine \boldsymbol S-Interpretation.

Literatur[Bearbeiten]

  • Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. 3., völlst. überarb. u. erw. Aufl., Bibliographisches Institut, Mannheim u. a. 1992, ISBN 3-411-15603-1. Kapitel II: Syntax der Sprachen erster Stufe, Kapitel III: Semantik der Sprachen erster Stufe.
  • Walter Gellert, Herbert Küstner, Manfred Hellwich, Herbert Kästner (Hrsg.): Kleine Enzyklopädie Mathematik. 10. Aufl. (Nachdruck der 2., völlig überarb. Aufl.), Harri Deutsch, Thun/Frankfurt a. M. 1984, ISBN 3-87144-323-9, S. 361–363.
  • Philipp Rothmaler: Einführung in die Modelltheorie. Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5.

Einzelnachweise und Anmerkungen[Bearbeiten]

  1. \alpha ist hier als Familie geschrieben.
  2. Manchmal spricht man auch von einem Bereich, z. B. wenn es sich um einen Zahlbereich handelt.