Kompaktheit (Logik)

Kompaktheit ist eine Eigenschaft einer Ableitbarkeitsrelation bzw. einer Inferenzoperation und besagt, dass jede Folgerung aus einer unendlichen Menge von Aussagen auch bereits aus einer endlichen Teilmenge dieser Menge folgt.

Formale Definition

Sei ${}\vdash$ eine Ableitbarkeitsrelation. ${}\vdash$ ist kompakt gdw. gilt

Wenn $\Gamma \vdash \mathrm{A}$, dann gibt es eine endliche Menge Δ mit $\Delta \subseteq \Gamma$, so dass $\Delta \vdash \mathrm{A}$.

Alternativ: Sei Cn eine Inferenzoperation. Cn ist kompakt gdw. gilt

$Cn(\Gamma) = \cup \{ Cn(\Delta) \mid \Delta$ ist endlich und $\Delta \subseteq \Gamma \}$

Erläuterung

Die Eigenschaft der Kompaktheit besagt, dass, wenn eine bestimmte Aussage aus einer Menge von Annahmen ableitbar ist, diese Aussage auch aus einer endlichen Teilmenge der Annahmen ableitbar sein muss. Intuitiv lässt sich das Prinzip wie folgt rechtfertigen: Ableitungen, also Beweise müssen endliche Objekte sein, denn sie dienen Menschen dazu, sich und andere von der Wahrheit einer Aussage zu überzeugen. Kein Mensch kann aber einen unendlich langen Beweis in sich aufnehmen. Da Beweise endliche Objekte sind, kann in ihnen auch immer nur von endlich vielen Annahmen Gebrauch gemacht werden. Folgt eine Aussage aus unendlich vielen Annahmen, so ist in dem entsprechenden Beweis also nur von endlich vielen Annahmen Gebrauch gemacht worden. Es gibt also eine endliche Untermenge der Annahmenmenge, aus der die Aussage bereits folgt.

Obwohl die Eigenschaft der Kompaktheit sich solcherart rechtfertigen lässt, hat sie doch zuweilen unerwünschte Konsequenzen. Betrachten wir dazu ein Beispiel. Wir gehen davon aus, dass jede Zahl eine bestimmte Eigenschaft hat, wir wollen sie einfach "zahlig" nennen. Wir erkennen, dass die folgende, unendlich große Aussagenmenge aus wahren Aussagen besteht: {"1 ist zahlig", "2 ist zahlig", "3 ist zahlig", ...}. Aus der Menge scheint zu folgen, dass alle Zahlen zahlig sind, denn andernfalls müssten die Aussagen vereinbar sein mit dem Satz "Es gibt eine Zahl, die nicht zahlig ist". Aber welche Zahl sollte das sein? Im Widerspruch zu unserer Intuition gilt nun bei Kompaktheit tatsächlich, dass besagte Menge mit der angeführten Aussage vereinbar ist, denn eine Widerlegung müsste von all den unendlich vielen Prämissen Gebrauch machen.