Die drei ??? (Axiomatisierbarkeit und Isomorphie)

Die Drei ???

Ich habe auf den Titel gewartet... Hier wirds schwer.

Aber fangen wir mal wieder bei den Grundlagen an.

Axiomatisierbarkeit

1. Eine Klasse: Wichtiger Begriff ist nur etwas wie eine Menge. Sie umgeht aber dabei Sachen von Mengen die Problematisch sind (Menge aller Mengen etc.). Trotzdem behandelt Klassen einfach so als ob sie Mengen sind.

Z.B. sei ($\tau$) die Klasse aller $\tau$ Strukturen.

2. $\text{Mod}(\Phi)$ (Modellklasse): Beschreibt die Klasse die $\Phi$ beschreibt. Also sie besteht aus allen $\tau$-Strukturen $\mathfrak{A}$ mit $\mathfrak{A} \models \Phi$ Also noch simpler: Die Sammlung aus den $\tau$-Strukturen wo $\Phi$ unter allen Belegungen gilt.

3. Eine Klasse $K$ wird von $\Phi$ axiomatisiert, wenn $K=\text{Mod}(\Phi)$ also relativ klar alle Strukturen in $K$ erfüllen $\Phi$ aber keine anderen.

4. Eine Klasse $K$ ist endlich/elementar axiomatisiert wenn $\Phi$ endlich ist

All diese Sachen gelten ob Strukturen/Strukturklassen axiomatisierbar sind. Aber auch in einer Struktur können Teilmengen (elementar) definiert werden

Eine Relation $R \subseteq A^r$ wird definert wenn eine Formel $\varphi$ existiert mit $R=\varphi^\mathfrak{A}$ (Hierbei ist zu erkennen, dass eine Formel $\varphi(x_1, ..., x_r)$ einige Tupel als Wahr (also in $\varphi^\mathfrak{A}$) und manche als Falsch erkennt.

Dies gilt genauso für Konstanten $a \in A$, wenn eine Formel $\varphi(x) \in FO(\tau)$ existiert mit $\mathfrak(A) \models \varphi(a)$ aber kein anderes $b \in A$

Isomorphie

Ohoh. Ich erkenne den Unterscheid nichtmehr. 😨

Ok ja also. Zwei Sachen sind isomorph wenn sie außer Unbennung nicht unterscheidbar sind. Also Formal: Es gibt einen Isomorphismus $\pi: A \to B$ so dass:

• Jede Relation $(a_1, ..., a_r) \in R^\mathfrak{A}$ gdw. $(\pi a_1, ..., \pi a_r) \in R^\mathfrak{B}$
• Das für jede Funktion $\pi F^\mathfrak{A}(a_1, ..., a_n) = f^\mathfrak{B}(\pi a_1, ..., \pi a_n)$

Kurzschreibweise für isomorphie: $\mathfrak{A} \cong \mathfrak{B}$. Ein Isomorphismus $\pi : \mathfrak{A} \overset{\sim}{\to} \mathfrak{A}$ heißt Automorphismus (wie Autobiographie und so)

Eine Struktur heißt Starr, wenn alle Automorphismen $\text{Aut}(\mathfrak{A})$ nur die triviale $1_\mathfrak{A}$ enthält.

Und nun zu den wichtigen Sätzen:

Isomorphielemma: Sei $\pi$ Isomorphismus, dann gilt für alle $\varphi(x_1, ..., x_n) \in FO(\tau)$ und alle $a_1, ..., a_n \in A$:
$\mathfrak{A} \models \varphi(a_1, ..., a_n)$ gdw. $\mathfrak{B} \models \varphi(\pi a_1, ..., \pi a_n)$

Also lassen sich Isomorphe Strukturen nicht durch die Prädikatenlogik unterscheiden und somit sind Modellklassen unter Isomorphie abgeschlossen und wenn $\mathfrak{A} \cong \mathfrak{B}$ dann $\mathfrak{A} \in K$ gdw. $\mathfrak{B} \in K$

Theorie

Dummer Name aber es ist einfach eine Menge von Sätzen $T \subseteq FO(\tau)$, die unter $\models$ abgeschlossen sind. Heißt alle Sätze $\psi \in FO(\tau)$ mit $T \models \psi$ (das ist die Folgerungsbeziehung [Wenn T gilt gilt auch psi]), dann ist $\psi \in T$.

Eine Theorie ist vollständig wenn entweder $\psi \in T$ oder $\lnot \psi \in T$ gilt.

Die Theorie einer Struktur ($\text{Th}(\mathfrak{A} := \{\psi \mid \mathfrak{A} \models \psi\}$)) ist auch ziemlich ergibig. $\text{Th}(K)$ für Modellklassen ist analog definiert.

Hierbei ist hilfreich: Wenn $\Phi, K$ axiomatisiert, dann ist $\text{Th}(K) = \{\psi \mid \Phi \models \psi\}$

Jede Theorie lässt sich zu einer vollständigen erweitern

Wie kann ich sagen ob es eine Theorie ist oder nicht?

Es müssen immmer alle Tautologien drin sein, da die ja aus allem folgen. Endliche Sachen sind also schonmal sus. Dann sucht man einfach nur noch eine Formel die nicht in der Menge drin ist aber auch wahr ist, wenn alle in der Menge war ist.

Elementare Äquivalenz

Zwei Strukturen $\mathfrak{A}, \mathfrak{B}$ sind elementar äquivalent, wenn $\text{Th}(\mathfrak{A}) = \text{Th}(\mathfrak{B})$ bzw. wenn für alle Sätze $\psi \in FO(\tau)$ gilt:

$\mathfrak{A} \models \psi$ gdw. $\mathfrak{B} \models \psi$

Zwei Strukturen sind m-äquivalent, wenn

$\mathfrak{A} \models \psi$ gdw. $\mathfrak{B} \models \psi$

für alle Sätze $\psi \in FO(\tau)$ mit $qr(\psi) \le m$ (Quantorenrang)

Eine Theorie ist dann vollständig, wenn alle Modelle elementar äquivalent sind.