Kompaktheit (Logik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Racine carrée bleue.svg
Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen.

Bitte hilf mit, die Mängel dieses Artikels zu beseitigen, und beteilige dich bitte an der Diskussion! (Artikel eintragen)

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.

Dies heißt, dass die Inferenzoperation ein algebraischer Hüllenoperator ist.

Formale Definition[Bearbeiten]

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

Wenn \Gamma \vdash \mathrm{A}, dann gibt es eine endliche Menge \Delta 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[Bearbeiten]

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.