Struktur (erste Stufe)

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 $\Sigma$ aus L die Klasse $Mod(\Sigma )$ der L-Strukturen, die sogenannten Modelle von $\Sigma$, angeben werden, aus denen $\Sigma$ 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_{1}$:

• $dom(M_{1})=\{a,b,c\}$
• Die Interpration von $\Gamma$ 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}$:

• $dom(M_{2})=\{1,2,3,4,5,...\}$
• Die Interpration von $\Gamma$ 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}$:

• $dom(M_{3})=\{0,1\}$
• Die Interpretation von $\Gamma$ in $M_{3}$: $\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_{4}$:

• $dom(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}$:

• $dom(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.

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

Beispiel Atomformeln aus Relationssymbol gebildet

Wenn wir ein Formel $\phi (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 $\phi (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)$

Beispiel Atomformeln aus Termen gebildet

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
nicht def.	nicht def.	wahr	nicht def.	nicht def.

• $M_{7}\models 0\circ 1=0$
• $M_{7}\neg models0\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.