L-Struktur

Zu jeder Elementaren Sprache L können zugehörige Strukturen definiert werden. Eine L-Struktur M besteht aus einem Grundbereich, den Elementen von M, ausgezeichneten Elementen, den Konstanten von M, und aus Beziehungen zwischen der Elementen, die durch Relationen und Funktionen über dem Grundbereich beschrieben werden. Die Konstanten, Relationen und Funktionen der Struktur sind die Interpretationen der Symbole die zu der Signatur der Sprache gehören. Mit einer L-Struktur M kann der Wert $t^M\$ bzw. $M\models \phi$ von beliebigen Termen $t\$ und Formeln $\phi\$ der Elementaren Sprache gefolgert werden. Die Menge der Aussagen, die aus einer Struktur folgt, wird als Theorie von M Th(M) bezeichnet. Umgekehrt können zu einer Aussagenmenge Σ aus L die Klasse Mod(Σ) der L-Strukturen, die sogenannten Modelle von Σ, angeben werden, aus denen Σ gefolgert werden kann. Im Beweis des Gödelschen 1. Vollständigkeitssatzes wird auch beschrieben, wie zu jeder konsistenen Mengen von Aussagen ein Modell definiert werden kann.

Definition von L-Strukturen

Jeder Elementaren Sprache L kann eine Klasse von L-Strukturen zugeordnet werden. Zur Definition von L-Strukturen wird von der Sprache L nur die Signatur $\sigma(L)\$ der Sprache benötigt.

Signatur

Sei eine Signatur $\sigma(L)=(c_0,c_1,c_2,...,R_0,R_1,R_2,...,f_0,f_1,f_2,...)\$ aus Konstanten-, Relations- und Funktionssymbolen gegeben.

• Beispiele
  1. $(\Gamma)\$, zweistellige Relation
  2. $(0,1,\leq,+,\cdot)\$, wobei die Relationen und Funktionen zweistellig
  3. $(e,\circ)\$

Interpretation einer Signatur in einer Struktur

Eine Struktur zu einer Signatur besteht aus

1. Grundbereich: $dom(M)=(x_0,x_1,...)\$ den Elementen der Struktur (auch Universum von M oder Domain von M).
2. Den Interpretationen der Symbole der Signatur: $(c_0^M,c_1^M,c_2^M,...,R_0^M,R_1^M,R_2^M,...,f_0^M,f_1^M,f_2^M,...)\$
   • Jedem Konstantensymbol $c\in\sigma(L)\$ wird ein Element zugeordnet, also $c^M=x\$ für ein $x\in dom(M)$.
   • Jedem n-stelligem Relationssymbol $R\in\sigma(L)\$ wird eine n-stellige Relation über $dom(M)\$ zugeordnet. Also $R^M\subseteq dom(M)^n$.
   • Jedem n-stelligen Funktionssymbol $f\in\sigma(L)$ wird eine n-stellige Funktion über $dom(M)\$ zugeordnet. Also $f^M: dom(M)^n\rightarrow dom(M)$.

Beispiele

Signatur 1

Zu der Signatur $(\Gamma)\$, wobei die Relation zweistellig, können wir folgende L-Strukturen definieren, die allesamt gerichtete Graphen sind:

1.1 Die Struktur M₁:

• dom(M₁) = {a,b,c}
• Die Interpretation von Γ in M₁: $\Gamma^{M_1}$ (Zweistellig)

$\Gamma^{M_1}$	1	2	3
1	f	w	w
2	w	f	w
3	w	w	f

1.2 Die Struktur M₂:

• dom(M₂) = {1,2,3,4,5,...}
• Die Interpretation von Γ in M₂: $\Gamma^{M_2}$ (Zweistellig)

$\Gamma^{M_2}$	1	2	3	4	...
1	f	w	f	f	...
2	f	f	w	f	...
3	f	f	f	w	...
...

1.3 Die Struktur M₃:

• dom(M₃) = {0,1}
• Die Interpretation von Γ in M₃: $\Gamma^{M_3}$ (Zweistellig)

$\Gamma^{M_3}$	0	1
0	w	f
1	f	w

Signatur 2

Zu der Signatur $(0,1,\leq,+,\cdot)\$, wobei die Relationen und Funktionen zweistellig, können folgende L-Strukturen definiert werden:

2.1 Die Struktur der Natürliche Zahlen M₄:

• dom(M₄) = (0,1,2,3,...) (Alternativ kann bei 1 begonnen werden)
• Die Symbole werden im üblichen Sinne Interpretiert.

2.2 Die Struktur der Ganzen Zahlen M₅:

• dom(M₅) = (..., − 3, − 2, − 1,0,1,2,3,...)
• Die Symbole werden im üblichen Sinne Interpretiert.

2.3 Die Struktur der Rationalen Zahlen M₆:

• $dom(M_6)=(...,-\frac{1}{3},-\frac{1}{2},-\frac{1}{1},0,\frac{1}{1},\frac{1}{2},\frac{1}{3},...)$
• Die Symbole werden im üblichen Sinne Interpretiert.

Signatur 3

Zur Signatur $(e,\circ)\$ gibt es folgende Beispiele:

3.1. $M_7\$ sei die Additive Gruppe von $F_2\$:

• $\underline{dom(M_7)=(0,1)}$
• $\underline{e^{M_7}:=0}$
• Die Interpretation der zweistelligen Verknüpfung $\underline{\circ^{M_7}:=+}$

$\circ$	0	1
0	0	1
1	1	0

3.2. $M_8\$ sei die Multiplikative Gruppe von $F_2\$:

• $\underline{dom(M_8)=(0,1)}$
• $\underline{e^{M_8}:=1}$
• Die Interpretation der zweistelligen Verknüpfung $\underline{\circ^{M_8}:=\cdot}$

$\circ$	0	1
0	0	0
1	0	1

3.3. $M_9\$ soll das Multiplizieren von Vorzeichen modellieren (minus mal minus ist plus):

• $\underline{dom(M_9)=(+,-)}$
• $\underline{e^{M_9}:=+}$
• Die Interpretation der zweistelligen Verknüpfung $\underline{\circ^{M_9}:=\cdot}$

$\circ$	+	−
+	+	−
−	−	+

Gültigkeit in L-Strukturen

Für jede L-Struktur kann der Wert eines Termes und der Wert oder die Gültigkeit einer Formel aus der Elementaren Sprache L bestimmt werden.

Wert von Termen in verschiedenen Strukturen

Struktur	$\underline{0\circ 1}$	$\underline{+\circ-}$	$\underline{1\circ 1}$
M7	1	nicht def.	0
M8	1	nicht def.	1
M9	nicht def.	−	nicht def.

Wir schreiben allgemein für eine beliebige L-Struktur M und einen Term t aus der zugehörigen elementaren Sprache t^M = a wenn t in M den Wert a hat.

• $(1\circ 1)^{M_7}=0$, hier bedeutet $\circ$ plus im Körper mit zwei Elementen
• $(1\circ 1)^{M_8}=1$, hier bedeutet $\circ$ mal im Körper mit zwei Elementen

Beispiel: Gültigkeit von einer Atomformel, die mit einem Relationssymbol gebildet wurde

Wenn wir ein Formel φ(x₁,...,x_n) ist ein passendes Tupel (a₁,...,a_n) von Elementen aus M eine Belegung von x₁,...,x_n. Im folgenden Beispiele für Belegungen von x₁,x₂ in $\phi(x_1,x_2)\equiv\Gamma(x_1,x_2)$ und ihre Gültigkeit in verschiedenen Strukturen.

Struktur	$\underline{\Gamma(1,1)}$	$\underline{\Gamma(3,2)}$	$\underline{\Gamma(0,1)}$
M1	falsch	wahr	nicht def.
M2	falsch	falsch	nicht def.
M3	wahr	nicht def.	falsch

Wenn in einer L Struktur M ein Formel φ(x₁,...,x_n) mit einer Belegung (a₁,...,a_n) gilt, schreiben wir $M\models\phi(a_1,...,a_n)$ und sagen In M ist gültig ...

• $M_1\not\models\Gamma(1,1)$ gesprochen In M₁ gilt nicht ...
• $M_1\models\Gamma(3,2)$

Beispiel: Gültigkeit von einer Atomformel, die mit einem Funktionssymbol gebildet wurde

Nun Beispiele für die Belegung von $\phi(x_1,x_2,x_3)\equiv x_1\circ x_2=x_3$ in verschiedenen Strukturen.

Struktur	$\underline{0\circ 1=0}$	$\underline{0\circ 1=1}$	$\underline{+\circ-=-}$	$\underline{1\circ 1=0}$	$\underline{1\circ 1=1}$
M7	wahr	falsch	nicht def.	wahr	falsch
M8	wahr	falsch	nicht def.	falsch	wahr
M9	nicht def.	nicht def.	wahr	nicht def.	nicht def.

• $M_7\models 0\circ 1=0$
• $M_7\not \models 0\circ 1=1$

Abbildungen zwischen L-Strukturen

L-Strukturen können nun mehr oder wenig ähnlich sein. Die Ähnlichkeit wird durch besondere Abbildungen zwischen den Grundbereichen ausgedrückt. Die Besonderheit drückt sich in Eigenschaften aus, die für mit den Strukturen verbundenen Ausdrücken, wie die Interpretation der Symbole der Signatur, den Wert von Termen in der Struktur oder die Gültigkeit von Formeln gelten.

• Seien nun M und N zwei Strukturen zur selben Sprache L.
• c, R und f seien beliebige Konstanten-, Relations- und Funktionssymbole aus der Signatur.
• $\bar{a}=a_1,...,a_n$ bzw. a seien beliebige Elemente aus dom(M).
• φ sei eine beliebige Aussage aus L (d.h. eine Formel ohne freie Variablen.
• φ(x₁,...,x_n) sei eine beliebige Formel aus L mit freien Variablen aus x₁,...,x_n.

Beziehung der Strukturen	Abbildung	Eigenschaft der Abbildung
$M \longrightarrow N$	$h: M \longrightarrow N$ L-Homomorphismus h	$h:dom(M)\rightarrow dom(N)$ $h(c^M)=c^N\$ $R^M(\bar{a})\Rightarrow R^N(h(\bar{a}))$ $h(f^M(\bar{a}))=f^N(h(\bar{a}))$
$M \hookrightarrow N$	$i: M \hookrightarrow N$ L-Einbettung/Monomorphismus i	i ist L-Homomorphismus i ist injektiv $R^M(\bar{a})\Leftrightarrow R^N(h(\bar{a}))$
M und N sind isomorph $M \cong N$	$i: M \cong N$ L-Isomorphismus i	i ist bijektive L-Einbettung
$M \subseteq N$ N ist L-Erweiterung von M		$dom(M)\subseteq dom(N)$ $c^M=c^N\$ $R^M(\bar{a})\Rightarrow R^N(\bar{a})$ $f^M(\bar{a})=f^N(\bar{a})$
	$a: M \stackrel{Aut}{\rightarrow}N$ Automorphismus a	dom(M) = dom(N) a ist Isomorphismus
N und M sind elementar äquivalent $M\equiv N$	$i: M \stackrel{\equiv}{\hookrightarrow} N$ Elementare Einbettung i	$M\models\phi(a_1,...,a_n)\Rightarrow N\models\phi(i(a_1),...,i(a_n))$
N ist elementare Erweiterung von M $M\le N$		$id_M:dom(M)\rightarrow dom(N)$ ist elem.Einbettung

Ausblick

Abgeleitete Strukturen

Aus vorhandenen Strukturen können neue Strukturen definiert werden

• Quotientenstrukturen
• Unterstrukturen, Oberstrukturen
• Direkte (Kartesische) Produkte
• Redukte, Expansionen

Verallgemeinerungen

Zu den L-Strukturen existieren Verallgemeinerungen

• Many-sorted Structures
• Many-valued Structures

Siehe auch

• Algebraische Strukturen
• Kategorientheorie
• Morphismus
• Erlanger Programm
• Endlichkeitssatz

Quellen

• David Marker, Model Theory: An Introduction.
• Heinz-Dieter Ebbinghaus, Jörg Flum und Wolfgang Thomas, Einführung in die mathematische Logik.