L-Struktur

aus Wikipedia, der freien Enzyklopädie

(Weitergeleitet von Struktur (Modelltheorie))

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 den 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 $M o d (Σ)$ 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 konsistenten Menge von Aussagen ein Modell definiert werden kann.

Inhaltsverzeichnis

1 Definition von L-Strukturen
- 1.1 Signatur
- 1.2 Interpretation einer Signatur in einer Struktur
2 Beispiele
3 Gültigkeit in L-Strukturen
4 Abbildungen zwischen L-Strukturen
5 Ausblick
- 5.1 Abgeleitete Strukturen
- 5.2 Verallgemeinerungen
6 Siehe auch
7 Quellen

[Bearbeiten] 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.

[Bearbeiten] 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)\$

[Bearbeiten] Interpretation einer Signatur in einer Struktur

Eine Struktur $M$ zu einer Signatur besteht aus

Grundbereich: $dom(M)=(x_0,x_1,...)\$ den Elementen der Struktur (auch Universum von M oder Domain von M).
Den Interpretationen der Symbole der Signatur:
- 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)$ .

[Bearbeiten] Beispiele

[Bearbeiten] 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 1$ :

$d o m (M 1) = {a, b, c}$
Die Interpretation von $Γ$ in $M 1$ : $\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 2$ :

$d o m (M 2) = {1,2,3,4,5,...}$
Die Interpretation von $Γ$ in $M 2$ : $\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 3$ :

$d o m (M 3) = {0,1}$
Die Interpretation von $Γ$ in $M 3$ : $\Gamma^{M_3}$ (Zweistellig)

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

[Bearbeiten] Signatur 2

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

2.1 Die Struktur der Natürliche Zahlen $M 4$ :

$d o m (M 4) = (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 5$ :

$d o m (M 5) = (..., - 3, - 2, - 1,0,1,2,3,...)$
Die Symbole werden im üblichen Sinne Interpretiert.

2.3 Die Struktur der Rationalen Zahlen $M 6$ :

$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.

[Bearbeiten] 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$	$+$	$-$
$+$	$+$	$-$
$-$	$-$	$+$

[Bearbeiten] 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.

[Bearbeiten] Wert von Termen in verschiedenen Strukturen

Struktur	$\underline{0\circ 1}$	$\underline{+\circ-}$	$\underline{1\circ 1}$
$M 7$	$1$	nicht def.	$0$
$M 8$	$1$	nicht def.	$1$
$M 9$	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

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

Wenn wir ein Formel $φ(x 1,..., x n)$ ist ein passendes Tupel $(a 1,..., a n)$ von Elementen aus M eine Belegung von $x 1,..., x n$ . Im folgenden Beispiele für Belegungen von $x 1, x 2$ 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)}$
$M 1$	falsch	wahr	nicht def.
$M 2$	falsch	falsch	nicht def.
$M 3$	wahr	nicht def.	falsch

Wenn in einer L Struktur M ein Formel $φ(x 1,..., x n)$ mit einer Belegung $(a 1,..., 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 1$ gilt nicht ...
$M_1\models\Gamma(3,2)$

[Bearbeiten] 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}$
$M 7$	wahr	falsch	nicht def.	wahr	falsch
$M 8$	wahr	falsch	nicht def.	falsch	wahr
$M 9$	nicht def.	nicht def.	wahr	nicht def.	nicht def.

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

[Bearbeiten] 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 1,..., x n)$ sei eine beliebige Formel aus L mit freien Variablen aus $x 1,..., 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	$d o m (M) = d o m (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