Quelltext der Seite Struktur (erste Stufe)

Der Begriff der '''Struktur''' ({{enS|''(first order) structures''}}) ist ein Grundbegriff der [[Teilgebiete der Mathematik|mathematischen Teilgebiete]] der [[Modelltheorie]] und der [[Universelle Algebra|universellen Algebra]].<ref>{{Literatur |Autor=[[Bjarni Jónsson (Mathematiker)|Bjarni Jónsson]] |Titel=Topics in Universal Algebra |Verlag=[[Springer Science+Business Media|Springer]] |Ort=Berlin |Datum=1972 |ISBN=3-540-05722-6}}</ref> Eine Struktur ist dabei eine [[Menge (Mathematik)|Menge]], genannt ''Universum'' der Struktur, versehen mit Operationen auf dieser Menge. Eine Vielzahl [[Mathematische Struktur|mathematischer Strukturen]] (als informeller Begriff) lässt sich als eine solche Struktur auffassen, insbesondere jede [[algebraische Struktur]] und jede [[Ordnungsstruktur]]. Ein Beispiel für eine Struktur sind die [[Natürliche Zahl|natürlichen Zahlen]] versehen mit der [[Addition]], der [[Multiplikation]] und dem Vergleich <math><</math>. In der Modelltheorie werden Strukturen mitunter auch '''Modelle''' genannt.

== Definition ==
Eine Struktur <math>\mathfrak{A}</math> ist eine Menge <math>A</math> (genannt ''Universum, Grundbereich'' oder ''Träger'' von <math>\mathfrak{A}</math>), versehen mit
* [[Funktion (Mathematik)|Funktionen]] <math>f_i\colon A^{n_i}\to A</math> für eine beliebige natürliche Zahl <math>n_i\geq 0</math>, zu jedem <math>i</math> aus einer Indexmenge <math>I</math>
* und <math>m_j</math>-stelligen [[Relation (Mathematik)|Relationen]] <math>R_j\subseteq A^{m_j}</math> für eine beliebige natürliche Zahl <math>m_j\geq 0</math>, zu jedem <math>j</math> aus einer Indexmenge <math>J</math>,

kann also als [[Tupel|Tripel]] <math>\mathfrak{A}=\left(A,(f_i)_{i\in I},(R_j)_{j\in J}\right)</math> definiert werden. Eine nullstellige Funktion ist eine [[Verknüpfung (Mathematik)#Nullstellige Verknüpfungen|Konstante]] aus <math>\mathfrak{A}</math>. Eine nullstellige Relation ist entweder <math>1 = \{\emptyset\} = A^0</math> oder <math>0 = \emptyset</math> und kann als [[Wahrheitswert]] gedeutet werden, [[Tautologie (Logik)|Verum]] <math>\top := 1</math> oder [[Falsum]] <math>\bot := 0.</math>

Die jeweiligen Funktionen und Relationen können durch die Symbole einer geeigneten Symbolmenge bzw. [[Signatur (Modelltheorie)|Signatur]] <math>\mathcal S</math> dargestellt werden. Der ''Ähnlichkeitstyp'' oder ''Typ'' der Struktur ist dann gegeben durch eine [[Funktion (Mathematik)|Funktion]] <math>\sigma\colon \mathcal S \to \N_0,</math> die jedem Zeichen in <math>\mathcal S</math> die [[Stelligkeit]] der zugehörigen Funktionen sowie Relationen eindeutig zuordnet. Der Typ kann aber auch einfach durch die Familie <math>(\sigma(s))_{s \in \mathcal S}</math> aller Stelligkeiten angegeben werden. Eine Struktur mit der Signatur <math>\mathcal S</math> wird kurz <math>\mathcal S</math>-Struktur genannt. Enthält eine Struktur keinerlei Relationen, so wird sie ''[[algebraische Struktur]]'' genannt&nbsp;– enthält sie keinerlei Funktionen, dagegen ''relationale Struktur'' oder ''Relationensystem.''

Eine Struktur wird endlich genannt, wenn ihr Universum <math>A</math> eine endliche Menge ist.<ref>{{Literatur |Autor=Leonid Libkin |Titel=Elements of finite model theory |Verlag=Springer |Ort=Berlin / Heidelberg |Datum=2004 |Sprache=en-CA |Reihe=Texts in Theoretical Computer Science |ISBN=978-3-540-21202-7 |Seiten=13 |Abruf= }}</ref>

=== Varianten ===
Mitunter wird die Definition auf folgende Weisen modifiziert:
* Es wird gefordert, dass das Universum nicht [[Leere Menge|leer]] ist.
* Es werden Konstanten <math>c_k\in A</math> explizit hinzugezählt.
* Nullstellige Relationen werden ausgeschlossen oder explizit hinzugezählt.
* Die Indexmengen müssen [[Wohlordnung|wohlgeordnet]], also [[Ordinalzahl]]en sein.

Eine weitere Variante sind ''vielsortige Strukturen'' (englisch: many-sorted structures).<br />
Die oben definierten Strukturen werden manchmal als einsortige Strukturen bezeichnet, um sie von den allgemeineren vielsortigen Strukturen zu unterscheiden: Eine vielsortige Struktur kann eine beliebige endliche Anzahl von Trägermengen haben, zusammengefasst in einer Familie <math>A=(A_k)_{k\in{K}}</math>. Deren Indizes <math>k</math> werden ''Sorten'' genannt und bezeichnen die verschiedenen Trägermengen. Funktionen (ggf. auch partielle) und Relationen werden nicht mehr einfach durch ihre Gesamtstelligkeit (Anzahl der Argumente) beschrieben, sondern durch die Familie der Sorten all ihrer Argumente, bei den (partiellen) Funktionen kommt noch die Sorte des Funktionswerts (Bildbereich) hinzu. Diese Angaben definieren dann eine (komplexe) mehrsortige Signatur. Ein Beispiel dafür sind [[Heterogene Algebra|heterogene Algebren]].

== Bezug zur Logik ==
{{Hauptartikel|Interpretation (Logik)}}
Die Modelltheorie untersucht die Beziehung zwischen [[Logische Formel|logischen Formeln]] und Strukturen, für die solche Formeln in einem gewissen zu definierenden Sinne ''gelten.'' Die hier dargestellten Strukturen werden insbesondere in Bezug zur [[Prädikatenlogik erster Stufe]] untersucht. Prädikatenlogische Formeln werden als Elemente einer [[Elementare Sprache|elementaren Sprache]] aufgefasst, welche die Verwendung gewisser Funktions- und Relationssymbole von festgelegter Stelligkeit in den Formeln erlaubt. Diese Information wird als ''Signatur'' der Sprache bezeichnet. Stimmt diese mit der Signatur einer Struktur überein, so lässt sich die Struktur als ''Interpretation'' der Formel auffassen. Unter dieser Interpretation erhält die Formel nach bestimmten Regeln einen Wahrheitswert (informell gesprochen werden die jeweiligen Funktionen bzw. Relationen für die Funktions- bzw. Relationssymbole eingesetzt). Ist dieser das Verum, so heißt die Interpretation ''Modell'' der Formel.

== Spezialfälle ==
In vielen Fällen ist eine Beschränkung auf relationale Strukturen möglich. Jede <math>n</math>-stellige Funktion lässt sich als <math>n+1</math>-stellige Relation auffassen. Dasselbe gilt für partielle Funktionen. Auch [[Heterogene Algebra|heterogene Algebren]] lassen sich als relationale Strukturen auffassen: Jede [[Grundmenge]] wird als einstellige Relation auf der Vereinigung der Grundmengen aufgefasst. Dabei ändern sich jedoch die Homomorphie- und Substrukturbegriffe. Jedoch sind die jeweiligen Eigenschaften (Funktion, partielle Funktion etc.) in der Prädikatenlogik erster Stufe definierbar. Somit lassen sich Überlegungen etwa bezüglich [[Elementare Klasse|Axiomatisierbarkeit]], [[Elementare Äquivalenz|elementarer Äquivalenz]], [[Erfüllbarkeit]] oder [[Entscheidbarkeit]] auf relationale Strukturen beschränken. Der Begriff der [[Elementare Substruktur|elementaren Substruktur]] ändert sich nicht. Algebraische Strukturen dagegen bilden einen wichtigen Spezialfall, der insbesondere in der universellen Algebra untersucht wird. Über durch [[Gleichungslogik]] definierte Klassen algebraischer Strukturen lassen sich hier weitreichendere Aussagen machen als in der allgemeinen Modelltheorie der Prädikatenlogik erster Stufe. Falls eine Struktur nur nullstellige Relationen enthält, so heißt sie ''aussagenlogische Interpretation.'' Solche Strukturen erlauben eine modelltheoretische Betrachtung der [[Aussagenlogik]].

== Beispiele ==
Man betrachte eine Signatur bestehend aus einer Indexmenge <math>I = \{+, \cdot, 0, 1\}</math> und einer Indexmenge <math>J = \{\leq\}</math>.<br /><math>+</math> und <math>\cdot</math> mögen die Stelligkeit <math>2</math> besitzen, <math>0</math> und <math>1</math> dagegen die Stelligkeit <math>0</math>, <math>\leq</math> habe die Stelligkeit <math>2</math>.

Die Struktur <math>\mathfrak N</math> der [[Natürliche Zahl|natürlichen Zahlen]] besteht aus der Menge <math>\N</math> der natürlichen Zahlen, wobei dem Index bzw. Symbol <math>+</math> die Addition auf den natürlichen Zahlen <math>+^\N\colon \N\times\N\to\N</math> zugeordnet wird, <math>\cdot</math> die Multiplikation auf den natürlichen Zahlen <math>\cdot^\N\colon \N\times\N\to\N</math>, <math>0</math> die Konstante <math>0^\N\in\N</math>, <math>1</math> die Konstante <math>1^\N\in\N</math> und <math>\leq</math> der [[Vergleich (Zahlen)|Vergleich]] <math>{\leq^\N}\subseteq \N\times\N</math>.

Analog lassen sich auf derselben Signatur etwa die Strukturen der [[Ganze Zahl|ganzen Zahlen]] oder der [[Rationale Zahl|rationalen Zahlen]] mit ihren bekannten Verknüpfungen definieren.

== Homomorphismen ==
{{Hauptartikel|Homomorphismus}}

== Konstruktion abgeleiteter Strukturen ==
=== Redukte und Expansionen ===
Durch Weglassen von Relationen oder Funktionen lässt sich aus einer Struktur eine neue Struktur bilden: Ist <math>\mathfrak{A}</math> eine Struktur mit Signatur <math>S</math> und <math>T\subseteq S</math>, so existiert genau eine Struktur <math>\mathfrak{B}</math> mit Signatur <math>T</math> mit demselben Universum wie <math>\mathfrak{A}</math>, die auf <math>T</math> mit <math>\mathfrak{A}</math> übereinstimmt, genannt '''Redukt''' von <math>\mathfrak{A}</math>. Umgekehrt lassen sich Strukturen um zusätzliche Relationen oder Funktionen ''expandieren.'' Ist <math>\mathfrak{B}</math> ein Redukt von <math>\mathfrak{A}</math>, so heißt <math>\mathfrak{A}</math> '''Expansion''' von <math>\mathfrak{B}</math>. Ein in der Modelltheorie häufig auftretender Spezialfall ist die [[Konstantenexpansion|Expansion um Konstanten]].

=== Unterstrukturen ===
Eine '''Unterstruktur''' oder '''Substruktur''' <math>\mathfrak{B}</math> mit Universum <math>B</math> einer Struktur <math>\mathfrak{A}</math> mit Universum <math>A</math> ist eine Struktur mit derselben Signatur wie <math>\mathfrak{A}</math>, sodass <math>B\subset A</math> gilt und sich die Relationen und Funktionen in <math>\mathfrak{B}</math> durch Einschränkung der Relationen und Funktionen in <math>\mathfrak{A}</math> auf das Universum <math>B</math> ergeben. Für relationale Strukturen existiert zu jeder Teilmenge <math>B\subset A</math> eine eindeutige induzierte Unterstruktur mit diesem Universum. Für allgemeine Strukturen ist dies nicht unbedingt der Fall, da nicht jede Teilmenge des Universums abgeschlossen unter den Funktionen der Struktur sein muss. Die Unterstrukturen einer Struktur bilden ein [[algebraisches Hüllensystem]].

In der Modelltheorie spielen als Spezialfall [[elementare Unterstruktur]]en eine zentrale Rolle.

=== Produkte, Vereinigungen und Quotienten ===
Aus einer Familie von Strukturen <math>(\mathfrak{A}_i)_{i\in I}</math> lässt sich das [[Direktes Produkt|direkte Produkt]] (kartesisches Produkt) <math>\prod_i \mathfrak{A}_i</math> (hier kurz <math>P</math>) bilden als Struktur über dem [[Kartesisches Produkt|kartesischen Produkt]] <math>\prod_i A_i</math> der Universen als Universum, sodass für Relationssymbole <math>R</math> gilt: <math>(x_1, \ldots, x_n)\in R^P \Leftrightarrow \forall i\in I (x_1(i), \ldots, x_n(i))\in R^{A_i}</math> (Funktionen seien als Relationen aufgefasst, dieses Produkt ist jedoch in diesem Fall wiederum eine Funktion). Diese Konstruktion liefert ein Produkt im Sinne der [[Kategorientheorie]] in der Kategorie der Strukturen über der gegebenen Signatur mit beliebigen Homomorphismen als Morphismen.<ref>Hodges: ''Model Theory.'' S. 413.</ref>

Für relationale Strukturen lässt sich eine '''disjunkte Vereinigung''' einer Familie definieren, indem man die mengentheoretischen [[Disjunkte Vereinigung|disjunkten Vereinigungen]] der Universen und der jeweiligen Relationen bildet, wobei die disjunkte Vereinigung von Relationen auf offensichtliche Weise mit einer Relation auf der disjunkten Vereinigung der Universen identifiziert wird.<ref>Ebbinghaus, Flum: ''Finite Model Theory.'' S. 4.</ref> Dies liefert ein [[Koprodukt]] in oben genannter Kategorie.

Auch lässt sich ein Quotient <math>\mathfrak{A}/{\sim}</math> einer relationalen Struktur <math>\mathfrak{A}</math> bezüglich einer [[Äquivalenzrelation]] <math>\sim</math> bilden. Das Universum bilden dabei die [[Äquivalenzklasse]]n von <math>\sim</math>, die Relationen seien definiert durch <math>(x_1, \ldots, x_n)\in R^{\mathfrak{A}/{\sim}}\Leftrightarrow \exists a_1\in x_1, \ldots, a_n\in x_n, (a_1, \ldots, a_n)\in R^{\mathfrak{A}}</math>. Die kanonische Surjektion liefert einen Homomorphismus <math>\mathfrak{A}\to\mathfrak{A}/{\sim}</math>. Umgekehrt liefert jeder Homomorphismus <math>\mathfrak{A}\to\mathfrak{B}</math> als Kern eine Äquivalenzrelation auf <math>\mathfrak{A}</math>. Forderungen an den Homomorphismus, etwa, dass es sich um einen starken Homomorphismus handelt, lassen sich in Forderungen an die zugehörige Äquivalenzrelation übersetzen. Vergleiche hierzu auch die stärkere Forderung nach einer [[Kongruenzrelation]] im algebraischen Fall.<ref>Michał Walicki, Marcin Białasik: ''Categories of relational structures''. Recent Trends in Algebraic Development Techniques, Volume 1376 of the series Lecture Notes in Computer Science, S. 418–433. {{DOI|10.1007/3-540-64299-4_48}}.</ref>

Als spezielle Quotienten von direkten Produkten ergeben sich [[Ultraprodukt]]e.

== Literatur ==
* Heinz-Dieter Ebbinghaus, Jörg Flum und Wolfgang Thomas: ''Einführung in die mathematische Logik.'' Vierte Auflage. Spektrum Akademischer Verlag, Heidelberg 1996, ISBN 3-8274-1691-4.
* {{Literatur |Autor=[[Wolfgang Rautenberg]] |Titel=Einführung in die Mathematische Logik |Auflage=3 |Verlag=[[Vieweg+Teubner Verlag|Vieweg+Teubner]] |Ort=Wiesbaden |Datum=2008 |ISBN=978-3-8348-0578-2 |DOI=10.1007/978-3-8348-9530-1}}

== Einzelnachweise ==
<references />

[[Kategorie:Modelltheorie]]
[[Kategorie:Universelle Algebra]]