Zum Inhalt springen

Mathematik für Faule: Logik/Die Vollständigkeit der Deduktionsregeln

Aus Wikibooks

Beweis: Wir führen eine iterative Deduktion über die Komplexitätszahl der Formel durch.

6. Es sei zunächst . Nach dem letzten Schritt gilt dann

,

und dann können wir einen Existenzquantor einführen. Umgekehrt sei . Da Zeugen enthält, folgt fast sofort, dass .

Proposition (Konsistente Erweiterung durch unbenutzte Variablen):

Es sei eine Logiksprache, eine Menge von Sätzen in dieser Sprache, ein beliebiger Satz und eine Variable, die in und nicht vorkommt. Dann ist

konsistent.

Beweis: Angenommen wäre inkonsistent, also . Dann

und ist ebenfalls inkonsistent, im Widerspruch zur Annahme.

Proposition (Existenz von Obermengen mit Zeugen):

Es sei eine Logiksprache und eine konsistente Menge von Sätzen. Dann kann man durch Variablen so zu einer größeren Sprache erweitern, dass es eine konsistente Obermenge von in der erweiterten Sprache gibt, welche zeugenangereichert ist. Des weiteren ist die Kardinalität sowohl von als auch von gleich der von .

Beweis: Wir definieren eine Folge von Logiksprachen und Satzmengen wie folgt:

und

und falls und schon definiert sind, dann definieren wir dadurch, dass wir für jeden Satz in eine neue Variable zu hinzufügen. Danach definieren wir dadurch, dass wir für jedes in den Satz zu hinzufügen.

Jedes ist konsistent, wie wir durch iterative Deduktion beweisen können: ist nach Annahme konsistent, und falls inkonsistent wäre, so gäbe es endlich viele Sätze der Form mit , aus denen man einen Widerspruch herleiten könnte. Aber mit iterativer Deduktion und dem vorhergehenden Satz kann man zeigen, dass vereinigt mit diesen Sätzen doch konsistent ist, ein Widerspruch.

Dann definieren wir

und .

Proposition (Existenz von Henkinobermengen):