Zum Inhalt springen

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

Aus Wikibooks

Satz (Unterstruktursatz von Löwenheim–Skolem):

Es sei eine Logiksprache und eine Menge von Sätzen darin, welche eine belegte Struktur besitzen. Es sei eine Mengengröße, welche mindestens so groß ist wie die Mengengröße von und , aber höchstens so groß wie die von . Dann gibt es eine belegte Unterstruktur von , deren Grundmenge die Mengengröße hat.

Beweis: Es sei mit . Setze . Falls gegeben ist, definiere wie folgt: Schließe zunächst ab bezüglich aller Operationen, und füge dann für alle Sätze in für alle Existenzquantoren in und alle gebundenen Variablen entsprechende Elemente aus zu hinzu, welche den Satz wahr machen. Die Arithmetik der Mengengrößen stellt sicher, dass die Mengengröße von sowie von

stets ist. Als Belegung nehmen wir schlicht die Einschränkung von , sodass wir eine belegte Unterstruktur erhalten.

Beispiel (Primdivoid):

Es sei ein Divoid. Das kleinste Divoid, welches in enthalten ist, nennt man das Primdivoid. Es entsteht, indem man mit den Elementen beginnt und dann den oben beschriebenen Prozess durchführt. Ist , so erhält man das abzählbare ; falls aber für eine Primzahl , so erhält man .

Satz (Oberstruktursatz von Löwenheim–Skolem):

Es sei eine Logiksprache und eine Menge von Sätzen darin. Es sei eine unendliche belegte Struktur von . Es sei ferner eine unendliche Mengengröße, welche größer oder gleich der Mengengröße von sowie der von ist. Dann hat eine belegte Struktur, deren Mengengröße gleich ist.

Beweis: ,wobei die Formelmenge aller wahren Aussagen in sei, ist konsistent und die Mengengröße dieser Formelmenge ist nicht größer als das Maximum von der von und der von . Es sei nun eine Menge der Größe . Für jedes fügen wir zu eine neue Variable hinzu. Hierdurch wächst die Mengengröße der Terme von genau auf an, wie man aus dem Aufbau von ersieht. Betrachte des weiteren die erweiterte Satzmenge

.

Diese Satzmenge ist konsistent, denn falls sie inkonsistent wäre, so hätte eine endliche Teilmenge von keine belegte Struktur. Jedoch können wir in interpretieren: Indem wir die Belegung so erweitern, dass jeder in auftauchenden Variable der Form ein verschiedenes Element aus zugeordnet wird, erhalten wir eine Struktur von , Widerspruch.

Also liefert die entsprechende Termstruktur die gewünschte Erweiterung von , denn es ist widerspruchsfrei und für jedes gibt es ein anderes Element in der Termstruktur.