Zum Inhalt springen
Topos Uranos
Deutsch

Der Kompaktheitssatz

Zusammenfassung

Eine Ableitung ist eine endliche Folge und verwendet nur endlich viele Prämissen; die Erfüllung einer unendlichen Formelmenge dagegen verlangt eine einzige Belegung, die den Wert 11 an unendlich viele Formeln zugleich vergibt, und nichts in ihrer Definition besagt, dass es genügt, endliche Teile zu prüfen. Der Kompaktheitssatz behauptet, dass es genügt: Eine Formelmenge ist genau dann erfüllbar, wenn jede ihrer endlichen Teilmengen es ist. Diese Lektion beweist ihn durch ein direktes semantisches Argument, ohne den Umweg über die Ableitung: Die Werte der Variablen v1,v2,…v_1, v_2, \ldots werden einer nach dem anderen festgelegt, wobei in jedem Schritt die Invariante erhalten bleibt, dass jede endliche Teilmenge der Menge weiterhin von einer Belegung erfüllbar ist, die das bereits Festgelegte respektiert; würde keine der beiden möglichen Wahlen sie erhalten, so widerspräche die Vereinigung der beiden endlichen Zeugen dieses Scheiterns der vorigen Invariante, und am Ende ist jede Formel nach dem Koinzidenzlemma erfüllt, weil sie endlich viele Variablen hat. Da die Variablen nummeriert sind, braucht die Konstruktion das Auswahlaxiom nicht. Aus der Kompaktheit ergeben sich ihre äquivalenten Formen (eine Menge ist genau dann unerfüllbar, wenn ein endlicher Teil von ihr es ist; eine Formel ist genau dann Folgerung aus einer Menge, wenn sie Folgerung aus einem endlichen Teil ist) und, mit der Vollständigkeit für endliche Prämissenmengen aus der vorigen Lektion, die starke Vollständigkeit: Γ⊨φ\Gamma \models \varphi impliziert Γ⊢φ\Gamma \vdash \varphi für jede Menge Γ\Gamma, woraus sich ergibt, dass Ableitung und semantische Folgerung stets übereinstimmen. Die Lektion schließt mit kombinatorischen Anwendungen: der Färbung unendlicher Graphen aus den Färbungen ihrer endlichen Teile, den endlichen Schranken, die sich in unendlichen Aussagen verbergen, und den Grenzen dessen, was eine Formelmenge ausdrücken kann.

Lernziele

  1. Endlich erfüllbare Mengen definieren und den Kompaktheitssatz durch schrittweises Festlegen der Werte der Variablen beweisen, wobei die Rolle der Invariante, des Arguments der zwei Zeugen und des Koinzidenzlemmas erklärt wird, ebenso, warum die Konstruktion das Auswahlaxiom nicht braucht.
  2. Die äquivalenten Formen der Kompaktheit, die Unerfüllbarkeitsform und die Folgerungsform, formulieren, beweisen und anwenden und von jeder zu den anderen übergehen.
  3. Die starke Vollständigkeit aus der Kompaktheit, der Vollständigkeit für endliche Prämissenmengen und der Monotonie herleiten und aus ihr die Übereinstimmung der Ableitung mit der semantischen Folgerung und der Widerspruchsfreiheit mit der Erfüllbarkeit gewinnen.
  4. Kombinatorische Probleme über unendliche Mengen (Färbungen, Ordnungen, Paarungen) in Formelmengen kodieren und mit der Kompaktheit lösen, wobei unterschieden wird, was der Satz sichert und was nicht.

Was aus den vorigen Lektionen verwendet wird

Diese Lektion arbeitet fast ganz in der Semantik und verwendet aus ihr Folgendes. Eine Belegung ist eine Funktion v ⁣:V→{0,1}v\colon V \to \{0, 1\} auf der Menge VV der Variablen v1,v2,v3,…v_1, v_2, v_3, \ldots, die sich auf eindeutige Weise auf alle Formeln fortsetzt; eine Belegung erfüllt eine Menge Γ\Gamma von Formeln, v⊨Γv \models \Gamma, wenn sie jeder von ihnen den Wert 11 gibt, und Γ\Gamma ist erfüllbar, wenn irgendeine Belegung sie erfüllt, und andernfalls unerfüllbar. All das steht in der Lektion über die Semantik der Aussagenlogik, zusammen mit dem zentralen Werkzeug dieser Lektion, dem Koinzidenzlemma: Stimmen zwei Belegungen auf den Variablen von φ\varphi überein, die eine endliche Menge V(φ)V(\varphi) bilden, so geben sie φ\varphi denselben Wert.

Aus der Lektion über semantische Folgerung und Äquivalenz werden verwendet: die Definition von Γ⊨φ\Gamma \models \varphi (jede Belegung, die Γ\Gamma erfüllt, erfüllt φ\varphi), die strukturellen Eigenschaften der Folgerung, insbesondere die Monotonie (wenn Γ⊆Δ\Gamma \subseteq \Delta und Γ⊨φ\Gamma \models \varphi, dann Δ⊨φ\Delta \models \varphi) und die fünfte (eine unerfüllbare Menge hat jede Formel als Folgerung), und der Satz über Folgerung und Unerfüllbarkeit: Γ⊨φ\Gamma \models \varphi genau dann, wenn Γ∪{¬φ}\Gamma \cup \{\neg\varphi\} unerfüllbar ist. Aus der Lektion über die verallgemeinerten De-Morgan- und Distributivgesetze wird das Wertlemma verwendet: ⋀i=1nφi\bigwedge_{i=1}^{n} \varphi_i hat genau dann den Wert 11, wenn alle ihre Glieder den Wert 11 haben, und ⋁i=1nφi\bigvee_{i=1}^{n} \varphi_i genau dann, wenn irgendein Glied den Wert 11 hat. Schließlich ist ⊤:=(v1→v1)\top := (v_1 \rightarrow v_1) eine Tautologie und ⊥:=¬⊤\bot := \neg\top eine Kontradiktion.

Auf der Seite der Ableitung hat die Lektion über formale Deduktionssysteme die Monotonie (Mon: wenn Γ⊆Δ\Gamma \subseteq \Delta und Γ⊢φ\Gamma \vdash \varphi, dann Δ⊢φ\Delta \vdash \varphi) und die Endlichkeit (Fin: wenn Γ⊢φ\Gamma \vdash \varphi, dann gibt es eine endliche Teilmenge Γ0\Gamma_0 von Γ\Gamma mit Γ0⊢φ\Gamma_0 \vdash \varphi) bewiesen, und die Lektion über die vier Ableitungstechniken hat geprüft, dass beide im Kalkül des Kurses gelten (den Schemata A1, A2 und A3, dem Modus ponens und der Ersetzung der doppelten Negation, EDN), auf den sich von nun an das Zeichen ⊢\vdash bezieht. Schließlich hat die Lektion über Korrektheit und Vollständigkeit den Korrektheitssatz (Γ⊢φ\Gamma \vdash \varphi impliziert Γ⊨φ\Gamma \models \varphi, für jedes Γ\Gamma) und die Vollständigkeit für endliche Prämissenmengen bewiesen: Wenn {γ1,…,γk}⊨φ\{\gamma_1, \ldots, \gamma_k\} \models \varphi, dann {γ1,…,γk}⊢φ\{\gamma_1, \ldots, \gamma_k\} \vdash \varphi.