Mathematik für Faule: Logik/Die Sätze von Löwenheim–Skolem

Satz (Unterstruktursatz von Löwenheim–Skolem):

Es sei $L^{S}$ eine Logiksprache und $\Phi$ eine Menge von Sätzen darin, welche eine belegte Struktur ${\mathfrak {M}}_{b}$ besitzen. Es sei $\kappa$ eine Mengengröße, welche mindestens so groß ist wie die Mengengröße von $L^{S}$ und $\Phi$, aber höchstens so groß wie die von ${\mathfrak {M}}_{b}$. Dann gibt es eine belegte Unterstruktur ${\mathfrak {N}}_{b}$ von ${\mathfrak {M}}_{b}$, deren Grundmenge die Mengengröße $\kappa$ hat.

Beweis: Es sei $N\subseteq |{\mathfrak {M}}|$ mit $\#N=\kappa$. Setze $N_{0}=N$. Falls $N_{k}$ gegeben ist, definiere $N_{k+1}$ wie folgt: Schließe zunächst $N_{k}$ ab bezüglich aller Operationen, und füge dann für alle Sätze $\varphi$ in $\Phi$ für alle Existenzquantoren in $\varphi$ und alle gebundenen Variablen entsprechende Elemente aus $|{\mathfrak {M}}|$ zu $N_{k+1}$ hinzu, welche den Satz $\varphi$ wahr machen. Die Arithmetik der Mengengrößen stellt sicher, dass die Mengengröße von $N_{k+1}$ sowie von

$|{\mathfrak {N}}|:=\bigcup _{k\in \mathbb {N} }N_{k}$

stets $\kappa$ ist. Als Belegung nehmen wir schlicht die Einschränkung von $b$, sodass wir eine belegte Unterstruktur erhalten. $\Box$

Beispiel (Primdivoid):

Es sei $K$ ein Divoid. Das kleinste Divoid, welches in $K$ enthalten ist, nennt man das Primdivoid. Es entsteht, indem man mit den Elementen $0,1\in K$ beginnt und dann den oben beschriebenen Prozess durchführt. Ist $\operatorname {ringchar} (K)=0$, so erhält man das abzählbare $\mathbb {Q}$; falls aber $\operatorname {ringchar} (K)=p$ für eine Primzahl $p$, so erhält man $\mathbb {F} _{p}$.

Satz (Oberstruktursatz von Löwenheim–Skolem):

Es sei $L^{S}$ eine Logiksprache und $\Phi$ eine Menge von Sätzen darin. Es sei ${\mathfrak {M}}_{b}$ eine unendliche belegte Struktur von $\Phi$. Es sei ferner $\kappa$ eine unendliche Mengengröße, welche größer oder gleich der Mengengröße von $L^{S}$ sowie der von $|{\mathfrak {M}}|$ ist. Dann hat $\Phi$ eine belegte Struktur, deren Mengengröße gleich $\kappa$ ist.

Beweis: $\Phi _{\mathfrak {M}}$,wobei $\Phi _{\mathfrak {M}}$ die Formelmenge aller wahren Aussagen in ${\mathfrak {M}}$ sei, ist konsistent und die Mengengröße dieser Formelmenge ist nicht größer als das Maximum von der von $L^{S}$ und der von $|{\mathfrak {M}}|$. Es sei nun $X$ eine Menge der Größe $\kappa$. Für jedes $x\in X$ fügen wir zu $L^{S}$ eine neue Variable $z_{x}$ hinzu. Hierdurch wächst die Mengengröße der Terme von $L^{S}$ genau auf $\kappa$ an, wie man aus dem Aufbau von $L^{S}$ ersieht. Betrachte des weiteren die erweiterte Satzmenge

$\Phi ':=\Phi _{\mathfrak {M}}\cup \{\neg z_{x}\equiv z_{y}|x,y\in X\And x\neq y\}$.

Diese Satzmenge ist konsistent, denn falls sie inkonsistent wäre, so hätte eine endliche Teilmenge $\Psi$ von $\Phi '$ keine belegte Struktur. Jedoch können wir $\Psi$ in ${\mathfrak {M}}$ interpretieren: Indem wir die Belegung $b$ so erweitern, dass jeder in $\Psi$ auftauchenden Variable der Form $z_{x}$ ein verschiedenes Element aus $|{\mathfrak {M}}|$ zugeordnet wird, erhalten wir eine Struktur von $\Psi$, Widerspruch.

Also liefert die entsprechende Termstruktur die gewünschte Erweiterung von ${\mathfrak {M}}$, denn es ist widerspruchsfrei und für jedes $x\in X$ gibt es ein anderes Element in der Termstruktur. $\Box$