5.1 Erfullungsrelation und modelltheoretische Konsequenz 229
Theorem 5-11. Erfullbarkeit Ubertragt sich auf Untermengen
Wenn X erfullbar ist, dann gilt fur alle Y ⊆ X: Y ist erfullbar.
Beweis: Ergibt sich direkt aus Definition 5-17 und Theorem 5-10. ■
Theorem 5-12. Konsequenzschaft und Erfullbarkeit
Wenn X ∪ {Γ} ⊆ GFORM, dann: X к Γ gdw X ∪ {r— Γ} ist nicht erfullbar.
Beweis: Sei X ∪ {Γ} ⊆ GFORM. Sei X к Γ. Also gilt fur alle D, I, b: Wenn D, I, b к
X, dann D, I, b к Γ. Angenommen X ∪ {r— Γ } ware erfullbar. Dann gibt es D, I, b, so
dass D, I, b к X ∪ {r—Γ}. Mit Definition 5-9 und Theorem 5-4-(ii) gilt dann D, I, b ≠
Γ und andererseits aber mit Theorem 5-10 D, I, b к X und damit nach Annahme D, I, b
к Γ. Widerspruch!
Sei umgekehrt X ∪ {r—Γ } nicht erfullbar. Also gibt es keine D, I, b, so dass D, I, b
к X ∪ {r—Γ }. Mit Definition 5-9 gibt es dann keine D, I, b, so dass D, I, b к X und
D, I, b к r—Γ. Gelte nun D, I, b к X. Dann ist (D, I) ein Modell und b eine Belegung
fur D und D, I, b ≠ r—Γ. Damit gilt nach Theorem 5-4-(ii) dann D, I, b к Γ. Also gilt
fur alle D, I, b: Wenn D, I, b кX, dann D, I, b к Γ. Also X к Γ. ■