Struktur (erste Stufe)

Der Begriff der Struktur (englisch (first order) structures) ist ein Grundbegriff der mathematischen Teilgebiete der Modelltheorie und der universellen Algebra[1]. Eine Struktur ist dabei eine Menge, genannt Universum der Struktur, versehen mit Operationen auf dieser Menge. Eine Vielzahl 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ürlichen Zahlen versehen mit der Addition, der Multiplikation und dem Vergleich ${\displaystyle <}$. In der Modelltheorie werden Strukturen mitunter auch Modelle genannt.

Definition

Eine Struktur ${\displaystyle {\mathfrak {A}}}$ ist eine Menge ${\displaystyle A}$ (genannt Universum, Grundbereich oder Träger von ${\displaystyle {\mathfrak {A}}}$) versehen mit

• Funktionen ${\displaystyle f_{i}\colon A^{n_{i}}\to A}$ für eine beliebige natürliche Zahl ${\displaystyle n_{i}\geq 0}$, zu jedem ${\displaystyle i}$ aus einer Indexmenge ${\displaystyle I}$
• und ${\displaystyle m_{j}}$-stellige Relationen ${\displaystyle R_{j}\subseteq A^{m_{j}}}$ für eine beliebige natürliche Zahl ${\displaystyle m_{j}\geq 0}$, zu jedem ${\displaystyle j}$ aus einer Indexmenge ${\displaystyle J}$,

kann also als Tripel ${\displaystyle {\mathfrak {A}}=\left(A,(f_{i})_{i\in I},(R_{j})_{j\in J}\right)}$ definiert werden. Eine nullstellige Funktion ist eine Konstante aus ${\displaystyle {\mathfrak {A}}}$. Eine nullstellige Relation ist entweder ${\displaystyle 1=\{\emptyset \}=A^{0}}$ oder ${\displaystyle 0=\emptyset }$ und kann als Wahrheitswert gedeutet werden, Verum ${\displaystyle \top$ :=1} oder Falsum ${\displaystyle \bot$ :=0.}

Die jeweiligen Funktionen und Relationen können durch die Symbole einer geeigneten Symbolmenge bzw. Signatur ${\displaystyle {\mathcal {S}}}$ dargestellt werden. Der Ähnlichkeitstyp oder Typ der Struktur ist dann gegeben durch eine Funktion ${\displaystyle \sigma \colon {\mathcal {S}}\to \mathbb {N} _{0},}$ die jedem Zeichen in ${\displaystyle {\mathcal {S}}}$ die Stelligkeit der zugehörigen Funktionen sowie Relationen eindeutig zuordnet. Der Typ kann aber auch einfach durch die Familie ${\displaystyle (\sigma (s))_{s\in {\mathcal {S}}}}$ aller Stelligkeiten angegeben werden. Eine Struktur mit der Signatur ${\displaystyle {\mathcal {S}}}$ wird kurz ${\displaystyle {\mathcal {S}}}$-Struktur genannt. Enthält eine Struktur keinerlei Relationen, so wird sie algebraische Struktur genannt, enthält sie keinerlei Funktionen, dagegen relationale Struktur oder Relationensystem.

Varianten

Mitunter w​ird die Definition a​uf folgende Weisen modifiziert:

• Es wird gefordert, dass das Universum nicht leer ist.
• Es werden Konstanten ${\displaystyle c_{k}\in A}$ explizit hinzugezählt.
• Nullstellige Relationen werden ausgeschlossen oder explizit hinzugezählt.
• Die Indexmengen müssen wohlgeordnet, also Ordinalzahlen sein.

Eine weitere Variante sind vielsortige Strukturen (englisch: many-sorted structures).
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 ${\displaystyle A=(A_{k})_{k\in {K}}}$. Deren Indizes ${\displaystyle k}$ 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 Algebren.

Bezug zur Logik

→ Hauptartikel: Interpretation (Logik)

Die Modelltheorie untersucht d​ie Beziehung zwischen logischen Formeln u​nd Strukturen, für d​ie solche Formeln i​n einem gewissen z​u definierenden Sinne gelten. Die h​ier dargestellten Strukturen werden insbesondere i​n Bezug z​ur Prädikatenlogik erster Stufe untersucht. Prädikatenlogische Formeln werden a​ls Elemente e​iner elementaren Sprache aufgefasst, welche d​ie Verwendung gewisser Funktions- u​nd Relationssymbole festgelegter Stelligkeit i​n den Formeln erlaubt. Diese Information w​ird als Signatur d​er Sprache bezeichnet. Stimmt d​iese mit d​er Signatur e​iner Struktur überein, s​o lässt s​ich die Struktur a​ls Interpretation d​er Formel auffassen. Unter dieser Interpretation erhält d​ie Formel n​ach bestimmten Regeln e​inen Wahrheitswert (informell gesprochen werden d​ie jeweiligen Funktionen bzw. Relationen für d​ie Funktions- bzw. Relationssymbole eingesetzt). Ist dieser d​as Verum, s​o heißt d​ie Interpretation Modell d​er Formel.

Spezialfälle

In vielen Fällen ist eine Beschränkung auf relationale Strukturen möglich. Jede ${\displaystyle n}$-stellige Funktion lässt sich als ${\displaystyle n+1}$-stellige Relation auffassen. Dasselbe gilt für partielle Funktionen. Auch 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 Axiomatisierbarkeit, elementarer Äquivalenz, Erfüllbarkeit oder Entscheidbarkeit auf relationale Strukturen beschränken. Der Begriff der 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 ${\displaystyle I=\{+,\cdot ,0,1\}}$ und einer Indexmenge ${\displaystyle J=\{\leq \}}$ . ${\displaystyle +}$ und ${\displaystyle \cdot }$ mögen die Stelligkeit ${\displaystyle 2}$ besitzen, ${\displaystyle 0}$ und ${\displaystyle 1}$ dagegen die Stelligkeit ${\displaystyle 0}$. ${\displaystyle \leq }$ habe die Stelligkeit ${\displaystyle 2}$.

Die Struktur ${\displaystyle {\mathfrak {N}}}$ der natürlichen Zahlen besteht aus der Menge ${\displaystyle \mathbb {N} }$ der natürlichen Zahlen, wobei dem Index bzw. Symbol ${\displaystyle +}$ die Addition auf den natürlichen Zahlen ${\displaystyle +^{\mathbb {N} }\colon \mathbb {N} \times \mathbb {N} \to \mathbb {N} }$ zugeordnet wird, ${\displaystyle \cdot }$ die Multiplikation auf den natürlichen Zahlen ${\displaystyle \cdot ^{\mathbb {N} }\colon \mathbb {N} \times \mathbb {N} \to \mathbb {N} }$, ${\displaystyle 0}$ die Konstante ${\displaystyle 0^{\mathbb {N} }\in \mathbb {N} }$, ${\displaystyle 1}$ die Konstante ${\displaystyle 1^{\mathbb {N} }\in \mathbb {N} }$ und ${\displaystyle \leq }$ der Vergleich ${\displaystyle {\leq ^{\mathbb {N} }}\subseteq \mathbb {N} \times \mathbb {N} }$.

Analog lassen s​ich auf derselben Signatur e​twa die Strukturen d​er ganzen Zahlen o​der der rationalen Zahlen m​it 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 ${\displaystyle {\mathfrak {A}}}$ eine Struktur mit Signatur ${\displaystyle S}$ und ${\displaystyle T\subseteq S}$, so existiert genau eine Struktur ${\displaystyle {\mathfrak {B}}}$ mit Signatur ${\displaystyle T}$ mit demselben Universum wie ${\displaystyle {\mathfrak {A}}}$, die auf ${\displaystyle T}$ mit ${\displaystyle {\mathfrak {A}}}$ übereinstimmt, genannt Redukt von ${\displaystyle {\mathfrak {A}}}$. Umgekehrt lassen sich Strukturen um zusätzliche Relationen oder Funktionen expandieren. Ist ${\displaystyle {\mathfrak {B}}}$ ein Redukt von ${\displaystyle {\mathfrak {A}}}$, so heißt ${\displaystyle {\mathfrak {A}}}$ Expansion von ${\displaystyle {\mathfrak {B}}}$. Ein in der Modelltheorie häufig auftretender Spezialfall ist die Expansion um Konstanten.

Unterstrukturen

Eine Unterstruktur oder Substruktur ${\displaystyle {\mathfrak {B}}}$ mit Universum ${\displaystyle B}$ einer Struktur ${\displaystyle {\mathfrak {A}}}$ mit Universum ${\displaystyle A}$ ist eine Struktur mit derselben Signatur wie ${\displaystyle {\mathfrak {A}}}$, sodass ${\displaystyle B\subset A}$ sich die Relationen und Funktionen in ${\displaystyle {\mathfrak {B}}}$ durch Einschränkung der Relationen und Funktionen in ${\displaystyle {\mathfrak {A}}}$ auf das Universum ${\displaystyle B}$ ergeben. Für relationale Strukturen existiert zu jeder Teilmenge ${\displaystyle B\subset A}$ 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 d​er Modelltheorie spielen a​ls Spezialfall elementare Unterstrukturen e​ine zentrale Rolle.

Produkte, Vereinigungen und Quotienten

Aus einer Familie von Strukturen ${\displaystyle ({\mathfrak {A}}_{i})_{i\in I}}$ lässt sich das direkte Produkt (kartesisches Produkt) ${\displaystyle \prod _{i}{\mathfrak {A}}_{i}}$ (hier kurz ${\displaystyle P}$) bilden als Struktur über dem kartesischen Produkt ${\displaystyle \prod _{i}A_{i}}$ der Universen als Universum, sodass für Relationssymbole ${\displaystyle R}$ gilt: ${\displaystyle (x_{1},\ldots ,x_{n})\in R^{P}\Leftrightarrow \forall i\in I(x_{1}(i),\ldots ,x_{n}(i))\in R^{A_{i}}}$ (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.[2]

Für relationale Strukturen lässt s​ich eine disjunkte Vereinigung e​iner Familie definieren, i​ndem man d​ie mengentheoretischen disjunkten Vereinigungen d​er Universen u​nd der jeweiligen Relationen bildet, w​obei die disjunkte Vereinigung v​on Relationen a​uf offensichtliche Weise m​it einer Relation a​uf der disjunkten Vereinigung d​er Universen identifiziert wird.[3] Dies liefert e​in Koprodukt i​n oben genannter Kategorie.

Auch lässt sich ein Quotient ${\displaystyle {\mathfrak {A}}/{\sim }}$ einer relationalen Struktur ${\displaystyle {\mathfrak {A}}}$ bezüglich einer Äquivalenzrelation ${\displaystyle \sim }$ bilden. Universum bilden dabei die Äquivalenzklassen von ${\displaystyle \sim }$, die Relationen seien definiert durch ${\displaystyle (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}}}$. Die kanonische Surjektion liefert einen Homomorphismus ${\displaystyle {\mathfrak {A}}\to {\mathfrak {A}}/{\sim }}$. Umgekehrt liefert jeder Homomorphismus ${\displaystyle {\mathfrak {A}}\to {\mathfrak {B}}}$ als Kern eine Äquivalenzrelation auf ${\displaystyle {\mathfrak {A}}}$. 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.[4]

Als spezielle Quotienten v​on direkten Produkten ergeben s​ich Ultraprodukte.

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.
• Wolfgang Rautenberg: Einführung in die Mathematische Logik. 3. Auflage. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2, doi:10.1007/978-3-8348-9530-1.

Einzelnachweise

1. Bjarni Jónsson: Topics in Universal Algebra. Springer, Berlin 1972, ISBN 3-540-05722-6.
2. Hodges: Model Theory, S. 413.
3. Ebbinghaus, Flum: Finite Model Theory, S. 4.
4. 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.