Quelltext der Seite Signatur (Modelltheorie)

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

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

== 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 [[Relation (Mathematik)|Relationssymbol]].

Beispielsweise, um über die Anordnung von natürlichen Zahlen zu sprechen, wird für jede Zahl eine Konstante eingeführt und Relationssymbole <math><</math> (kleiner als) und <math>></math> (größer als).

Meistens braucht man darüber hinaus noch Funktionen, mit denen man über den Konstanten rechnen kann, z.&nbsp;B. ein Symbol <math>(+)</math> für die Addition der natürlichen Zahlen.<ref>Die Argumente der Relationen und Funktionen sind ''Stellungsparameter'' (auch ''Positionsparameter'' genannt). In der Informationstechnologie weit verbreitete Logiken, in denen den Argumenten Namen gegeben werden (''[[Schlüsselwort (Programmierung)|Schlüsselwortparameter]]''), nennt man [[Feature-Logik]]en, siehe auch: [[Parameter (Informatik)#Unterschiedliche Parameter-Begriffe|Parameter (Informatik) §Unterschiedliche Parameter-Begriffe]] und Steimann (1992), S.&nbsp;4.</ref>

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]], für die das Prädikat gilt.

== 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 <math>L</math> umfasst also mehr Zeichen als die zugehörige Signatur <math>\boldsymbol S(L).</math>

Die zur Bildung [[Logische Aussage|logischer Aussagen]] und [[Aussageform|Formeln]] erlaubten Zeichen kann man somit grob einteilen in<ref>Siehe E. Grädel (2009) S. 45.</ref>
* Zeichen, die die Struktur (den Aufbau) der Aussage oder Formel definieren:
** ''[[Junktor]]ensymbole'', zum Beispiel <math>\land, \lor, \rightarrow, \leftrightarrow, \neg</math>
** ''[[Quantor]]ensymbole'', zum Beispiel <math>\forall, \exists, \exists^1</math>
* Terminale Zeichen, die für Werte und deren Beziehungen stehen:
** ''[[Variable (Logik)|Variablen]]'', zum Beispiel <math>x_0, x_1, x_2, \ldots</math>
** ''Symbole der Signatur''
*** [[Konstante (Logik)|Konstantensymbole]], zum Beispiel <math>0, 1, e</math>
*** Funktionssymbole, zum Beispiel <math>+, {}^{-1}, f</math>
*** Relationssymbole (Prädikate), zum Beispiel <math>\sim, <, \in </math>
* Technische Zeichen
** Gliederungszeichen,<ref>siehe [[Aussagenlogik#Bausteine der aussagenlogischen Sprache|Aussagenlogik §Bausteine der aussagenlogischen Sprache]]</ref> wie die Klammern <math>(, )</math>
** andere, wie <math>\boldsymbol ,</math> (Komma) <math>\dots</math>

Manche Autoren verzichten auf einen Teil der Junktoren und Quantoren, z.&nbsp;B. kann <math>\exists^1</math> mit Hilfe der anderen dieser Zeichen erklärt werden. Unter Ausnutzung der Dualität können <math>\land, \forall</math> (oder umgekehrt <math>\lor, \exists</math>) entfallen.<ref>Zum Beispiel Kruse, Borgelt (2008) S. 3</ref>

[[Term#Formale Definition|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.<ref>Siehe E. Grädel (2009) S. 45&nbsp;f</ref>

Werden Terme als Argumente in die Relationssymbole eingesetzt, entstehen ''atomare Aussagen'' der [[Prädikatenlogik]]. Auch Vergleiche von Termen <math>t_1 = t_2</math> gelten in der Prädikatenlogik als atomare Aussagen. Aus ihnen können durch Verknüpfungen (Junktoren und Quantoren) zusammengesetzte Aussagen gebildet werden, siehe [[Prädikatenlogik erster Stufe#Ausdrücke|Prädikatenlogik erster Stufe §Ausdrücke]].<ref>E. Grädel (2009) S. 46&nbsp;f</ref>

== Definition ==
Es seien <math>\mathcal C, \mathcal F</math> und <math>\mathcal R</math> [[paarweise disjunkt]]e [[Menge (Mathematik)|Mengen]] von nichtlogischen Zeichen. Man nennt dann jedes Zeichen in <math>\mathcal S := \mathcal C \cup \mathcal F \cup \mathcal R</math> ein ''Symbol'' und <math>\mathcal S</math> eine ''Symbolmenge'', wenn durch eine [[Funktion (Mathematik)|Abbildung]] <math>\sigma\colon \mathcal S \to \N_0</math> jedem Zeichen in <math>\mathcal S</math> wie folgt eine ''[[Stelligkeit]]'' genannte Zahl eindeutig zugeordnet wird:<ref>In der englischsprachigen Literatur findet sich auch die Bezeichnung <math>\operatorname{ar}</math> (von ''arity'', Stelligkeit) anstelle von <math>\sigma</math>.</ref>
* <math>\sigma(c) = 0</math> für alle <math>c \in \mathcal C,</math>
* <math>\sigma(f) \in \N</math> für alle <math>f \in \mathcal F</math> und
* <math>\sigma(R) \in \N</math> für alle <math>R \in \mathcal R.</math>
<math>\boldsymbol S := (\mathcal S, \sigma)</math> heißt dann eine ''Signatur'' und jedes <math>c \in \mathcal C</math> wird als ein ''Konstantensymbol'', jedes <math>f \in \mathcal F</math> als ein ''Funktionssymbol'' und jedes <math>R \in \mathcal R</math> als ein ''Relationssymbol'' bezeichnet.

Eine Signatur <math>\boldsymbol S = (\mathcal S, \sigma)</math> heißt ''endlich'', falls <math>\mathcal S</math> 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 ===
# Die Konstantensymbole können auch zu den Funktionssymbolen gezählt werden, so dass sich <math>\mathcal S = \mathcal F_0 \cup \mathcal R</math> mit <math>\mathcal F_0 := \mathcal C \cup \mathcal F</math> ergibt.
# Gelegentlich werden auch Symbole für nullstellige Relationen zugelassen, diese entsprechen aussagenlogischen (booleschen) Konstanten (siehe [[Relation (Mathematik)#Relationen und Funktionen|Relationen §Relationen und Funktionen]] sowie Brass (2005), S. 19). Mit der Menge dieser Symbole <math>\mathcal B</math> erweitert sich <math>\mathcal R</math> zu <math>\mathcal R_0 := \mathcal B \cup \mathcal R</math> und die komplette Symbolmenge ist dann <math>\mathcal S = \mathcal F_0 \cup \mathcal R_0</math>.
# Manche Autoren betrachten statt der Abbildung <math>\sigma</math>, die jedem Symbol seine Stelligkeit zuordnet, deren [[Urbild (Mathematik)#Definition|Urbildfasern]], konkret die [[Folge (Mathematik)|Folgen]] <math>\boldsymbol{\mathcal R}: \N_0 \to \mathcal R_0</math> und <math>\boldsymbol{\mathcal F}: \N_0 \to \mathcal F_0</math>, die jeder natürlichen Zahl die Relations- bzw. Funktionssymbole der betreffenden Stelligkeit zuweisen. Für die Kennzeichnung der Signatur genügt dann die Angabe dieser beiden Folgen <math>\boldsymbol{\mathcal S} = (\boldsymbol{\mathcal R},\boldsymbol{\mathcal F})</math>.<ref>Die beiden Folgen definieren sich als die Urbildfasern der [[Einschränkung]]en von <math>\alpha</math> auf die beiden Symbolmengen <math>\mathcal R_0</math> und <math>\mathcal F_0</math>: &nbsp;<math>\boldsymbol{\mathcal R}_n = (\alpha|_{\mathcal R_0})^{-1}(\{n\}),\;\boldsymbol{\mathcal F}_n = (\alpha|_{\mathcal F_0})^{-1}(\{n\})</math>. Siehe W. Vogler (2007/2008) S. 3.</ref><ref>Stefan Brass (2005) S. 16. Die dortigen Ausführungen für mehrsortige Signaturen wurden hier vereinfacht. An die Stelle der [[Kleenesche Hülle|Kleeneschen Hülle]] <math>\mathcal S</math> über den Sorten tritt hier die Menge der natürlichen Zahlen <math>\N_0</math>. Konstanten sind als nullstellige Funktionen aufgefasst, nullstellige Relationen zugelassen. Der Autor verwendet den Ausdruck ''Prädikatsymbole'' mit Bezeichnungen <math>\mathcal P</math>, <math>\mathcal F</math> und <math>\Sigma</math> statt <math>\boldsymbol{\mathcal R}</math>, <math>\boldsymbol{\mathcal F}</math> und <math>\boldsymbol{\mathcal S}</math>.</ref>
# Das gleiche Relationssymbol kann für Relationen unterschiedlicher Stelligkeit, und das gleiche Funktionssymbol kann für Funktionen unterschiedlicher Stelligkeit verwendet werden. Man nennt das Symbol dann ''[[überladen]]''<ref name="Brass2005_S20">Stefan Brass (2005), S. 20</ref><!--, generisch? --> oder ''[[Polymorphie (Programmierung)|polymorph]]''.<ref>Cremers et al., (1994), Seite&nbsp;148; siehe auch [[Polymorphie (Programmierung)]].</ref> Die Mengen der Relationssymbole <math>\boldsymbol{\mathcal R}_n</math> für die verschiedenen Stelligkeiten ''n'' einerseits, und die Mengen der Funktionssymbole <math>\boldsymbol{\mathcal F}_n</math> andererseits sind dann jeweils unter sich nicht mehr notwendig disjunkt, die Menge aller Relationssymbole <math>\mathcal R_0</math> ist aber weiterhin von der aller Funktionssymbole <math>\mathcal F_0</math> disjunkt.<ref name="Brass2005_S20" /><br />Die Stelligkeitsabbildung <math>\sigma</math> ist in diesem Fall eine [[Funktion (Mathematik)#Multifunktionen|Multifunktion]] (<math>\sigma: \mathcal S \multimap \N_0</math> statt <math>\sigma: \mathcal S \to \N_0</math>);<ref name="Korrespondenz">Siehe auch [[Korrespondenz (Mathematik)|Korrespondenz]]</ref> die [[Einschränkung]]en auf eine bestimmte Stelligkeit (<math>\sigma_n := \sigma|_{\boldsymbol{\mathcal R}_n \cup \boldsymbol{\mathcal F}_n}</math>) sind jedoch eindeutig.<br />Ein Beispiel sind die Funktionen max und min, die jeweils für alle ''n''-Tupel mit <math>n \in \N</math> als Argument definiert sind, d.&nbsp;h. <math>\operatorname{max},\operatorname{min}: \R^+ \to \R</math>; sowie [[Kleinstes gemeinsames Vielfaches|kgV]], [[Größter gemeinsamer Teiler|ggT]]: <math>{\N_0}^+ \to \N_0</math>.<ref>Das oben angehängte Sternchen meint hier die [[Kleenesche und positive Hülle|positive Hülle]].</ref>
# 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 ==
=== Strukturen ===
<math>\boldsymbol S = (\mathcal S, \sigma)</math> sei eine Signatur und es bestehe die Menge <math>\mathcal C</math> aus allen Konstantensymbolen <math>c \in \mathcal S,</math> die Menge <math>\mathcal F</math> aus allen Funktionssymbolen <math>f \in \mathcal S</math> sowie die Menge <math>\mathcal R</math> aus allen Relationssymbolen <math>R \in \mathcal S.</math> Weiterhin bezeichne <math>A</math> eine nichtleere Menge und {{nowrap|<math>\boldsymbol A := A \cup \{B \mid B \subseteq A^n \text{ für ein } n \in \N\} = A \cup \textstyle\bigcup_{n \in \N}</math>&nbsp;[[Potenzmenge|<math>\mathcal P(A^n)</math>]].}} Ist dann <math>\alpha\colon \mathcal S \to \boldsymbol A</math> eine Abbildung, sodass
* <math>\alpha(c) \in A</math> eine [[Algebraische Struktur#Definition|Konstante]] ist für jedes <math>c \in \mathcal C,</math>
* <math>\alpha(f)\colon\, A^{\sigma(f)} \to A</math> eine [[Funktion (Mathematik)|Funktion]] ist für jedes <math>f \in \mathcal F</math>&nbsp;<ref>Mengentheoretisch ausgedrückt sind Funktionen spezielle Relationen: <math>\alpha(f) \in [A^{\sigma(f)} \to A] \sube \mathcal P(A^{\sigma(f)} \times A) = \mathcal P(A^{\sigma(f)+1}) \sube \boldsymbol A</math>, wobei <math>\mathcal P</math> die [[Potenzmenge]] (Menge aller Teilmengen) bezeichnet.</ref> und
* <math>\alpha(R) \subseteq A^{\sigma(R))}</math> eine [[Relation (Mathematik)|Relation]] ist für jedes <math>R \in \mathcal R,</math><ref>Mengentheoretisch äquivalent: <math>\alpha(R) \in \mathcal P(A^{\sigma(R)})</math>, insbesondere ist für einstellige Relationen <math>\alpha(R) \sube A</math> (Teilmengen) oder äquivalent <math>\alpha(R) \in \mathcal P(A) \sube \boldsymbol A</math>. Falls nullstellige Relationen (logische Konstanten) zugelassen sind, ist für diese <math>\alpha(R) \sube A^0 = \{\emptyset\}</math> bzw. <math>\alpha(R) \in \mathcal P(\{\emptyset\}) = \{\emptyset,\{\emptyset\}\}</math>.</ref>
so nennt man <math>\alpha</math> ''Interpretationsfunktion''<ref>R. Letz (2004) S. 6. Der Autor benutzt für die Interpretationsfunktion die Notation <math>\iota</math> anstelle von <math>\alpha</math>.</ref> und <math>\mathcal A := (A, \alpha) = \bigl(A, (\alpha(s))_{s \in S}\bigr) = \bigl(A, (\alpha(c))_{c \in \mathcal C} \cup (\alpha(f))_{f \in \mathcal F} \cup (\alpha(R))_{R \in \mathcal R}\bigr)</math><ref><math>\alpha</math> ist hier als [[Familie (Mathematik)|Familie]] geschrieben. Diese entsteht durch [[disjunkte Vereinigung]] der drei Teile, so dass man äquivalent auch mit Hilfe der Einschränkungen <math>\mathcal A := (A, \alpha|_{\mathcal C}, \alpha|_{\mathcal F}, \alpha|_{\mathcal R},) = \bigl(A, (\alpha(c))_{c \in \mathcal C}, (\alpha(f))_{f \in \mathcal F}, (\alpha(R))_{R \in \mathcal R}\bigr)</math> definieren kann.</ref> eine ''[[Struktur (erste Stufe)|Struktur]] der Signatur <math>\boldsymbol S</math>'' oder kurz eine ''{{nowrap|<math>\boldsymbol S</math>-Struktur}}''. Man findet dann auch die Bezeichnungsweisen <math>c^{\mathcal A} = \alpha(c), R^{\mathcal A} = \alpha(R), f^{\mathcal A} = \alpha(f)</math>.<ref>Siehe [[Prädikatenlogik erster Stufe#Semantik|Prädikatenlogik erster Stufe §Semantik]]</ref> <math>A</math> ist dann die ''Grundmenge'', die [[Trägermenge]] oder kurz der ''Träger'' von <math>\mathcal A.</math> <ref>Manchmal spricht man auch von einem ''Bereich'' (''Werte-'' oder ''Objektbereich''), z.&nbsp;B. wenn es sich um einen [[Zahlbereich]] handelt.</ref> Falls <math>A</math> eine endliche Menge ist, so heißt ebenso <math>\mathcal A</math> ''endlich'', sonst ''unendlich''.

=== Anmerkungen ===
# Eine Konstante <math>\alpha(c)</math> lässt sich als die [[Stelligkeit|nullstellige Funktion]] <math>0 \mapsto \alpha(c)</math> auffassen, sodass für <math>\mathcal F_0 := \mathcal C \cup \mathcal F</math> gilt:
#: <math>\mathcal A = \bigl(A, (\alpha(f_0))_{f_0 \in \mathcal F_0} \cup (\alpha(R))_{R \in \mathcal R}\bigr)</math> mit Funktionen <math>\alpha(f_0)</math> und mit Relationen <math>\alpha(R).</math><ref>Für die Interpretationsfunktion auf der Menge der Konstanten bedeutet dies, dass ihr Bildbereich <math>A</math> durch die [[Einermenge]]n <math>\{\{a\}|a\in A\} \sube \mathcal P(A)</math> ersetzt wird, wodurch sich der Wertebereich zu <math>\boldsymbol A = = A \cup \textstyle\bigcup_{n \in \N} \mathcal P(A^n)</math> vereinfacht.<br />Manchmal werden nullstellige Relationen zugelassen. Diese lassen sich als logische Konstanten auffassen. <math>\mathcal R_0</math> bezeichnet dann alle Relationssymbole einschließlich der nullstelligen. In der obigen Beziehung für die Signatur <math>\mathcal A</math> ist entsprechend <math>\mathcal R</math> durch <math>\mathcal R_0</math> zu ersetzen; der Wertebereich wird mit nullstelligen Funktionen und Relationen zu <math>\boldsymbol A = \textstyle\bigcup_{n \in \N_0} \mathcal P(A^n).</math></ref>
# Jede <math>n</math>-stellige Funktion <math>(n \in \N)</math> ist auch stets eine <math>n+1</math>-stellige Relation (mit dem Funktionswert an letzter Position). Daher kann jede <math>\boldsymbol S</math>-Struktur dargestellt werden als
#: <math>\mathcal A = \bigl(A, (\alpha(S))_{S \in \mathcal S}\bigr)</math> mit Relationen <math>\alpha(S).</math><ref>A. Oberschelp (1962), S.&nbsp;298</ref>
# Wenn eine Struktur nur Funktionen ([[algebraische Struktur]]) oder nur Relationen ([[relationale Struktur]], insbesondere [[Ordnungsrelation|Ordnungsstruktur]]) enthält, dann hat sie oft spezielle Eigenschaften.
# Die Definition kann auf [[partielle Funktion]]en <math>\alpha(f): A^{\sigma(f)} \not\to A</math> ausgedehnt werden, um z. B. [[Universelle Algebra#Verallgemeinerungen|partielle Algebren]] zu erfassen.
# Im Fall von Überladung der Relations- und/oder Funktionssymbole wird Eindeutigkeit hergestellt, indem zum jeweiligen Symbol noch die Stelligkeit angegeben wird:
#* <math>\alpha_n(f)\colon\, A^n \to A</math> und
#* <math>\alpha_n(R) \subseteq A^n</math>.
::Es handelt sich um partielle Abbildungen, nur für Stelligkeiten <math>R \in \boldsymbol{\mathcal R}_n</math> bzw. <math>f \in \boldsymbol{\mathcal F}_n</math> kann es überhaupt Zuweisungen der Symbole zu Relationen bzw. Funktionen gegeben.

=== Interpretationen ===
Die Signatur <math>\boldsymbol S</math> erhält durch eine <math>\boldsymbol S</math>-Struktur <math>\mathcal A = (A, \alpha)</math> und eine ''Deutung'' oder ''[[Interpretation (Logik)|Interpretation]]'' von Variablen eine bestimmte [[Semantik|semantische Bedeutung]]:

Sei <math>\mathcal V = \{x_0, x_1, x_2, \dots\}</math> die Menge der Variablensymbole. Eine ''Variablenbelegung'' ist dann eine (eventuell auch nur [[Funktion (Mathematik)#Partielle Funktionen|partielle]]) Abbildung <math>\beta\colon \mathcal V \not\to A</math>.<ref>Die Menge der Variablensymbole <math>\mathcal V</math> kann endlich oder [[Abzählbare Menge|abzählbar]] unendlich sein (siehe Stefan Brass (2005) S. 13), im zweiten Fall werden aus mehreren Zeichen zusammengesetzte Variablennamen benutzt, die gewissen Regenl unterworfen sind, damit sie als Variablennamen erkennbar sind, informationstheoretisch handelt es sich bei <math>\mathcal V</math> in diesem Fall um eine [[formale Sprache]]. Partielle Abbildungen als Belegung lässt man dann zu, wenn  <math>\mathcal V</math> unendlich ist.</ref> wird eine ''Belegung'' der <math>\boldsymbol S</math>-Struktur <math>\mathcal A</math> genannt. <math>\boldsymbol I := (\mathcal A, \beta)</math> heißt dann eine ''Interpretation der Signatur <math>\boldsymbol S</math>'' oder kurz eine ''<math>\boldsymbol S</math>-Interpretation''.

== Vielsortige Signaturen ==
{{Hauptartikel|Sortenlogik#Vielsortige Signaturen|titel1=Sortenlogik §Vielsortige Signaturen}}
Für die Beschreibung [[Struktur (erste Stufe)|vielsortiger Strukturen]], wie z.&nbsp;B. [[Heterogene Algebra|heterogener Algebren]] ([[Modul (Mathematik)|Moduln]], [[Vektorraum|Vektorräume]], [[Algebra über einem Körper|K-Algebren]], [[Lie-Algebra|Lie-Algebren]] etc.) mit mehreren Trägermengen kann man ''mehr-'' oder ''vielsortige Signaturen'' einführen. Bei diesen kommen zu den Funktions- und Relationssymbolen noch die ''Sorten'', Bezeichnungen für die Trägermengen, hinzu. Eine n-stellige [[Relation (Mathematik)#n-stellige Relation|Relation]] ist eine Teilmenge des n-fachen [[Kartesisches Produkt|kartesischen Produktes]] einer Sequenz der Trägermengen. Der Argumentbereich einer n-stelligen [[Funktion (Mathematik)#Stelligkeit|Funktion]] ist ein ebensolches Produkt, dazu kommt noch eine der Trägermengen für den Wertebereich.

Mehrsortigkeit kann zwar immer auf Einsortigkeit zurückgeführt werden, indem man die Sortenzugehörigkeit für jede Sorte als einstellige Relation (''Sortenprädikat'') hinzunimmt. Im Gegensatz zur [[Prädikatenlogik zweiter Stufe]] mit Relationsvariablen bedeutet Vielsortigkeit keine Steigerung der Mächtigkeit der Theorie, etwa in Bezug auf Fragen nach Beweisbarkeit. Dafür genügt es, den einsortigen Fall zu betrachten.<ref>Näheres siehe A. Oberschelp (1962) S.&nbsp;297f</ref> Falsche Sortenzuordnungen (wie <math>a = \overrightarrow{b}</math>, wenn <math>a</math> und <math>\overrightarrow{b}</math> verschiedenen Sorten zugehören, z.&nbsp;B. Skalar und Vektor) erscheinen dann aber nicht mehr als syntaktische Fehler. Mehrsortige Strukturen bilden ein mengentheoretisches Modell für die [[Datentyp]]en in der [[Informationstechnologie]], insbesondere bei [[Datenbank]]en, weshalb ihnen eine erheblich praktische Bedeutung zukommt.<ref>Beispielsweise können Fehler bei Datentyp-Zuweisungen schnell (zur [[Compiler|Compilezeit]]) als Syntaxfehler erkannt werden.</ref> Darüber hinaus ist Mehrsortigkeit eine Möglichkeit, den mit [[Typentheorie]]n verbundenen Belangen auf mengentheoretischer Basis Rechnung zu tragen.

Zu den Mengen <math>\mathcal F_0</math>  für die Funktions- und <math>\mathcal R_0</math> für die Relationssymbole<ref>Konstanten seien hier als nullstellige Funktionen aufgefasst, logische Konstantem ggf. als nullstellige Relationen</ref> kommt noch eine weitere endliche, nichtleere ''Sortenmenge'' <math>T</math> nichtlogischer Zeichen hinzu. Die Signatur eines Funktions- oder Relationssymbols ist jetzt nicht mehr einfach eine Zahl von Argumenten aus <math>\N_0</math>, sondern hat deren Sorten zu respektieren.
Die ''Argumentsorten'' bilden daher ''n''-[[Tupel]] mit der Stelligkeit ''n''. Für Funktionen kommt noch die ''Bildsorte'' hinzu, so dass sich insgesamt ein (''n''+1)-Tupel ergibt. Die Tupel können als [[Wort (Theoretische Informatik)|Wörter]] über dem Sorten[[Alphabet (Informatik)|alphabet]] <math>T</math> verstanden werden, d.&nbsp;h. als Elemente der ''[[Kleenesche Hülle|Kleeneschen Hülle]]'' <math>T^*</math>.<ref><math>T^* = \bigcup \{T^n|n \in \N_0\}</math>. Im Fall der Funktionssymbole, wo eine weitere Sorte für den Wertebereich benötigt wird, liegen die Werte von <math>\sigma</math> in der ''positiven Hülle'' <math>T^+ = T^* \setminus \{\emptyset\} = T^* \setminus \epsilon</math>. Die Stelligkeit ist die Wortlänge des Typs (minus 1 bei Funktionssymbolen).</ref> Sie werden als ''Typ'' des Relations- bzw. Funktionssymbols bezeichnet: <math>\tau(R), \tau(S)</math>. Die Signatur setzt sich dann aus der Sortenmenge, der Symbolmenge <math>\mathcal S = \mathcal F_0 \cup \mathcal R_0</math>, und der Typ-Abbildung <math>\tau</math> zusammen: <math>\boldsymbol S := (T, \mathcal S, \tau)</math>.

== Literatur ==
* {{Literatur
   |Autor=Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas
   |Titel=Einführung in die mathematische Logik
   |Band=Band 1: ''Grundlagen, Algebra und Geometrie''
   |Auflage=3., vollst. überarb. u. erw.
   |Verlag=Bibliographisches Institut
   |Ort=Mannheim u.&nbsp;a.
   |Datum=1992
   |ISBN=3-411-15603-1
   |Kapitel=Kapitel II: Syntax der Sprachen erster Stufe, Kapitel III: Semantik der Sprachen erster Stufe.}}
* {{Literatur
   |Hrsg=Walter Gellert, Herbert Küstner, Manfred Hellwich, [[Herbert Kästner]]
   |Titel=Kleine Enzyklopädie Mathematik
   |Auflage=10. (völlig überarb. 2.)
   |Verlag=Harri Deutsch
   |Ort=Thun / Frankfurt a.&nbsp;M.
   |Datum=1984
   |ISBN=3-87144-323-9
   |Seiten=361–363}}
* {{Literatur
   |Autor=Philipp Rothmaler
   |Titel=Einführung in die Modelltheorie
   |Verlag=Spektrum Akademischer Verlag
   |Datum=1995
   |ISBN=978-3-86025-461-5}}
* {{Literatur
   |Autor=Erich Grädel
   |Titel=Mathematische Logik
   |Band=Mathematische Grundlagen der Informatik, SS 2009
   |Verlag=RWTH
   |Ort=Aachen
   |Datum=
   |Seiten=129
   |Online=[https://fldit-www.cs.uni-dortmund.de/~peter/LogikGraedel.pdf fldit-www.cs.uni-dortmund.de]
   |Format=PDF
   |KBytes=}}<!--Definition der Signatur vergleichsweise informell/weniger formal-->
* {{Literatur
   |Autor=W. Vogler
   |Titel=Logik für Informatiker
   |Band=WS 2007/2008
   |Verlag=Univ. Augsburg, Institut für Informatik
   |Ort=Augsburg
   |Datum=
   |Seiten=49
   |Online=[https://www.informatik.uni-augsburg.de/lehrstuehle/swt/ti/lehre/ws0708/logik/Skript/logik-stud.pdf informatik.uni-augsburg.de]
   |Format=PDF
   |KBytes=}}<!-- Formale Definition mit Mengen zur jeweiligen Stelligkeit statt Abbildung nach <math>\N_m</math>-->

* {{Literatur
   |Autor=Uwe Kastens
   |Titel=Prädikatenlogik
   |Verlag=Universität Paderborn, Institut für Informatik
   |Ort=Paderborn
   |Datum=2008
   |Seiten=31
   |Online=[http://www2.cs.uni-paderborn.de/cs/ag-klbue/de/courses/ws09/model/folien/kb-pred-logic.pdf www2.cs.uni-paderborn.de]
   |Format=PDF
   |KBytes=}}<!-- Signatur ohne explizite Notation der Stelligkeit-->

* {{Literatur
   |Autor=Thomas Worsch
   |Titel=Prädikatenlogik
   |Band=Einheit 18: Logik, WS 2008/2009
   |Verlag=Universität Karlsruhe, Fakultät für Informatik
   |Ort=Karlsruhe
   |Datum=
   |Seiten=35
   |Online=[http://www2.cs.uni-paderborn.de/cs/ag-klbue/de/courses/ws09/model/folien/kb-pred-logic.pdf www2.cs.uni-paderborn.de]
   |Format=PDF
   |KBytes=}}<!-- Signatur ohne explizite Notation der Stelligkeit-->
* {{Literatur
   |Autor=Armin B. Cremers, Ulrike Griefahn, Ralf Hinze
   |Titel=Typsysteme.
   |Sammelwerk=Deduktive Datenbanken. Artificial Intelligence
   |Verlag=Vieweg+Teubner
   |Ort=Wiesbaden
   |Datum=1994
   |ISBN=978-3-528-04700-9
   |Kapitel=Kapitel 5: Typsysteme
   |Seiten=147–182
   |DOI=10.1007/978-3-663-09572-9_5}}<!-- überladene = polymorphe Funktionssymbole-->
Der mehr- oder vielsortige Fall wird in den folgenden Quellen behandelt:
* {{Literatur
   |Autor=[[Arnold Oberschelp]]
   |Titel=Untersuchungen zur mehrsortigen Quantorenlogik
   |Sammelwerk=[[Mathematische Annalen]]
   |Band=145
   |Nummer=4
   |Auflage=
   |Verlag=Springer
   |Datum=1962
   |Seiten=297–333
   |Online=[https://eudml.org/doc/160913 eudml.org]
   |DOI=10.1007/BF01396685}}
* {{Literatur
   |Autor=Arnold Oberschelp; Hrsg.: Karl Hans Bläsius,Ulrich Hedtstück,Claus-Rainer Rollinger
   |Titel=Order Sorted Predicate Logic
   |Band=Lecture Notes in Computer Science (LNCS), Band 418: Sorts and Types in Artificial Intelligence, Workshop, Eringerfeld, FRG, April 24–26, 1989 Proceedings
   |Verlag=Springer-Verlag
   |Ort=Berlin Heidelberg
   |Datum=1990
   |ISBN=978-3-540-52337-6
   |Seiten=307
   |DOI=10.1007/3-540-52337-6}}<!--Sorten mit festern Varablen-Symbolmengen, ohne Deklaration -->
* {{Literatur
   |Autor=François Bry
   |Titel=Exkurs: Mehrsortige Prädikatenlogik erster Stufe
   |Band=2.9
   |Verlag=LMU, Institut für Informatik, pms
   |Ort=München
   |Datum=1999
   |Online=[http://www.en.pms.ifi.lmu.de/publications/projektarbeiten/Claudia.Plant_Alije.Ristemi/node14.html en.pms.ifi.lmu.de]}}
* {{Literatur
   |Autor=Stefan Brass
   |Titel=Mathematische Logik mit Datenbank-Anwendungen
   |Verlag=Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik
   |Ort=Halle
   |Datum=2005
   |Seiten=176
   |Online=[http://users.informatik.uni-halle.de/~brass/db07/d2_logic.pdf users.informatik.uni-halle.de]
   |Format=PDF
   |KBytes=}}<!-- Formale Definition mit Mengen zur jeweiligen (komplexen) Stelligkeit statt Abbildung nach <math>S^*</math> -->
* {{Literatur
   |Autor=R. Kruse, C. Borgelt
   |Titel=Grundbegriffe der Prädikatenlogik
   |Band=Computational Intelligence
   |Verlag=Otto-von-Guericke Universität
   |Ort=Magdeburg
   |Datum=2008
   |Seiten=14
   |Online=[http://fuzzy.cs.ovgu.de/studium/ise/txt_05/logic.pdf fuzzy.cs.ovgu.de]
   |Format=PDF
   |KBytes=}}<!-- Signatur ohne explizite Notation der Stelligkeit-->
* {{Literatur
   |Autor=R. Hartwig
   |Titel=Syntax Semantik Spezifikation – Grundlagen de Informatik
   |Band=WS 2009/2010
   |Verlag=Universität Leipzig, Institut für Informatik
   |Ort=Leipzig
   |Datum=
   |Seiten=219
   |Online=[https://www.informatik.uni-leipzig.de/~rhartwig/SynSemSpez/SSS200910-Folien.pdf informatik.uni-leipzig.de]
   |Format=PDF
   |KBytes=}}
* {{Literatur
   |Autor=Reinhold Letz
   |Titel=Prädikatenlogik
   |Band=WS 2004/2005
   |Verlag=Technische Universität München, Fakultät für Informatik, Lehrstuhl Informatik IV
   |Ort=München
   |Datum=
   |Seiten=47
   |Online=[http://www2.tcs.ifi.lmu.de/~letz/TU/PRAKTIKUM/pl-ws04.pdf www2.tcs.ifi.lmu.de]
   |Format=PDF
   |KBytes=}}
* {{Literatur
   |Autor=Friedrich Steimann
   |Titel=Ordnungssortierte Feature-Logik und Dependenzgrammatiken in der Computerlinguistik
   |Band=Monographien
   |Verlag=FernUni, Fakultät Mathematik und Informatik, LG Programmiersysteme
   |Ort=Hagen
   |Datum=2011-01-31
   |Seiten=104
   |Kommentar=Diplomarbeit
   |Online=[https://www.fernuni-hagen.de/ps/veroeffentlichungen/monogr_46106.shtml fernuni-hagen.de]}}, bei: FernUni Hagen, [https://www.fernuni-hagen.de/ps/pubs/DiplomarbeitSteimann.pdf fernuni-hagen.de] (PDF; 6,3&nbsp;MB). Original bei: Universität Karlsruhe 1992, Institut für Logik, Komplexität und Deduktionssysteme

== Einzelnachweise und Anmerkungen ==
<references />

[[Kategorie:Mathematische Logik]]
[[Kategorie:Universelle Algebra]]