Das mathematikhistorische Kalenderblatt - Juni 2011

Zurück zur Übersicht des mathematikhistorischen Kalenderblatts

75 Jahre Endlichkeitssätze der mathematischen Logik

Ausnahmsweise soll ein nicht durch 50 Jahre teilbares mathematisches Jubiläum gewürdigt werden. Im Jahre 1936 veröffentlichte der damals 27-jährige russische Mathematiker Anatoly Ivanovich Mal’cev (auch als Maltsev o.ä. transkribiert) in der renommierten Zeitschrift Matematiceskij Sbornik seine erste Arbeit: „Untersuchungen aus dem Gebiete der mathematischen Logik“ (ja, wirklich auf Deutsch, das war damals in Russland gar nicht ungewöhnlich).

Sie enthält den sogenannten „Endlichkeitssatz für Modelle“, über dessen teils erstaunliche Konsequenzen noch zu reden sein wird. Mal’cev wurde später ein weltberühmter Algebraiker (Das hat die kuriose Folge, dass sein Endlichkeitssatz in der von Algebraikern verfassten Biographie in der bekannten Internet-Sammlung der Uni St. Andrews gar nicht erwähnt wird.) Die Kombination des Mal’cevschen Endlichkeitssatzes mit dem Gödelschen Vollständigkeitssatz (1930) dehnt diesen von endlichen auf beliebige Axiomensysteme aus. In dieser erweiterten Form wird er heute meist als „Gödel-Mal’cev-Theorem“ oder gar als „Hauptsatz der Prädikatenlogik“ bezeichnet.

A. I. Mal’cev (1909 – 1967)

Um diesen Satz zu verstehen, muss man die beiden Begriffe des „Folgerns“ und des „Beweisens“ für Aussagen, die in einer sogenannten elementaren Sprache (siehe unten) formulierbar sind, kennen. Eine Aussage H folgt aus einer Menge X von Voraussetzungen (einem Axiomensystem), wenn sie bei allen Interpretationen (Deutungen) der Sprachbestandteile, bei denen alle Aussagen von X erfüllt sind, ebenfalls wahr wird. Folgern ist also ein semantischer Begriff. Er nimmt Bezug auf die besonders in der Mathematik unverzichtbare Möglichkeit, Symbolen oder Wörtern unterschiedliche Bedeutungen zuzuordnen. Im Gegensatz dazu ist Beweisen ein syntaktischer Begriff. Er bezieht sich auf das rein formale „Herleiten“ von Aussagen aus Voraussetzungen mittels eines definierten Systems von Regeln.

Der Gödelsche Vollständigkeitssatz sagt (nach einer kleinen Verallgemeinerung): Es gibt Beweiskalküle, durch die man das Folgern aus endlichen Axiomensystemen vollständig ersetzen (und damit automatisieren) kann. Das Gödel-Mal’cev-Theorem sagt: Die Einschränkung auf endliche Axiomensysteme kann man dabei streichen. Folgern gleich Beweisen (durch einen angebbaren Kalkül) gilt für alle in elementaren Sprachen formulierbaren Theorien. (Elementar bedeutet dabei im Wesentlichen, dass beim Folgern alle mit der syntaktischen Struktur der Sprache verträglichen Interpretationen in Betracht gezogen werden müssen. Wie schon Hilbert im Zusammenhang mit den Grundlagen der Geometrie gesagt haben soll: Man muss statt Punkte, Geraden und Ebenen auch Tische, Bänke und Bierseidel sagen können.)

Der ursprüngliche Satz von Mal’cev lautet: Besitzt jede endliche Teilmenge eines unendlichen Axiomensystems ein Modell, so besitzt das gesamte Axiomensystem ein Modell. Er gestattet schon ohne seinen Zusammenhang mit dem Gödelschen Satz verschiedene äquivalente Umformulierungen und hat einige gewichtige Folgerungen: Er besagt auch, dass jede Folgerung aus einem Axiomensystem immer schon aus einem gewissen endlichen Teil des Axiomensystems folgt. (Aus der Sicht „Folgern gleich Beweisen“ ist das klar. Bei jedem Beweis hat man ja immer nur endlich viele Voraussetzungen tatsächlich benutzt.)

Eine besonders eindrucksvolle und eigentlich unerfreuliche Konsequenz ist die Unmöglichkeit, in der Mengenlehre den Begriff der endlichen Menge zu definieren: Sei E(M) irgendeine Formulierung der Mengenlehre, welche bedeuten soll, dass die Menge M endlich ist. Nun sei Mo der Name einer beliebigen speziellen Menge. Zusammen mit den anderen Axiomen A der Mengenlehre hat offenbar jedes der Axiomensysteme ein Modell, welches aus A und der Aussage besteht, dass E(M₀) gilt und M₀ mindestens n Elemente besitzt (n =1,2,3,…). (Für ein solches Modell muss man in einem Modell von A – wir setzen voraus, dass es ein solches gibt – als Deutung für das Symbol M₀ nur eine hinreichend große endliche Menge nehmen.) Aus dem Satz von Mal’cev ergibt sich dann, dass es ein Modell des Axiomensystems A gibt, in dem eine im Sinne der Definition E endliche Menge existiert, die mehr als 1,2,3,4,… Elemente besitzt.

Während der Gödelsche Vollständigkeitssatz und der Satz von Mal’cev bei ihrer ersten Publikation nach Inhalt und Anliegen anscheinend relativ weit voneinander entfernt waren, setzte mit der Arbeit „The completeness of the first order functional calculus“ (Journal of Symbolic Logic 1949) von L. Henkin eine Welle von direkten Beweisen des Hauptsatzes ein, deren Grundgedanke meist darin besteht, zu einer syntaktisch widerspruchsfreien Menge von Aussagen ein Modell zu konstruieren. Bei einem solchen Zugang fallen der Gödelsche Satz und der Satz von Mal’cev anschließend als Spezialfälle bzw. einfache Folgerungen an.

ps