Direkt zum Inhalt

Lexikon der Mathematik: mathematische Logik

Weiterentwicklung und Mathematisierung der traditionellen Logik mit Hilfe mathematischer Kalküle.

Die moderne Entwicklung der Logik zu einer mathematischen Disziplin beginnt im 19. Jahrhundert. Auslösend für diese Entwicklung war die Ausweitung naturwissenschaftlichen Denkens und das dadurch verursachte schärfere Hervortreten unbewältigter Probleme in der Grundlagenforschung der Mathematik. Dabei zutagegekommene Widersprüche insbesondere in der Mengenlehre erforderten eine gründliche Analyse der verwendeten mathematischen Ausdrucksmittel und Methoden.

In der mathematischen Logik wird, wenn es erforderlich erscheint, die benutzte Sprache streng formalisiert. Dadurch sind grundlegende Begriffsbildungen in der Mathematik, wie „beweisbar, widerspruchsfrei, Vollständigkeit eines Axiomensystems, Unabhängigkeit von Aussagen, … “ überhaupt erst präzise formulierbar. Die in diesem Zusammenhang gewonnenen Erkenntnisse über die Rolle der Sprache waren nicht nur für die Fundierung der Mathematik von Bedeutung, sondern gleichermaßen förderlich für die Entwicklung „intelligenter“ Maschinen. Erst eine gründliche Analyse des logischen Schließens erbrachte das notwendige Verständnis der Denkvorgänge, das für den Bau von leistungsfähigen Computern erforderlich ist.

Wesentliche Impulse bei der Entwicklung der Logik zu einer mathematischen Disziplin kamen aus der Mathematik selbst. Insbesondere die um die Jahrhundertwende 1900 in der Cantorschen Mengenlehre aufgetretenen Widersprüche lösten umfangreiche grundlagentheoretische Analysen innerhalb der Mathematik aus, die zu einer strengen Überprüfung der logischen und mathematischen Hilfsmittel führten. Hieraus entstanden verschiedenartige neue Ansätze für logische Kalküle mit streng formalisierten Sprachen, möglichst schwachen logischen Voraussetzungen und präzise formulierten zulässigen Beweisregeln; siehe hierzu auch Beweistheorie und Logik.

Spätestens nachdem K.Gödel 1930 seinen Vollständigkeitssatz für die Prädikatenlogik veröffentlicht hatte (Gödelscher Vollständigkeitssatz), war gesichert, daß der Prädikatenkalkül als logisches System eine hervorragende Grundlage für Untersuchungen in der klassischen Mathematik darstellt. Sowohl das Prinzip der Zweiwertigkeit (klassische Logik), das die Grundlage für indirekte Beweise (Beweismethoden) bildet, als auch der Gebrauch beliebiger unendlicher – insbesondere auch überabzählbarer – Mengen als existierende mathematische Objekte lösten bei manchen Mathematikern Zweifel über die Korrektheit der klassischen Mathematik aus.

In der intuitionistischen Logik, die von L.E.G. Brower initiiert wurde, werden als existierende Objekte zunächst nur beliebig große natürliche Zahlen anerkannt (schon die Menge der natürlichen Zahlen ist nicht ad hoc existent). In dieser Theorie wird ein mathematisches Objekt nur dann als existent angesehen, wenn es sich mit finiten Mitteln aus den schon zuvor vorhandenen Objekten konstruieren oder sich seine Existenz beweisen läßt, wobei die Beweismittel gegenüber der klassischen Logik erheblich eingeschränkt sind. Indirekte Beweise z. B. werden damit ausgeschlossen.

Die in diesem eingeschränkten Rahmen entwickelte Mathematik wird auch konstruktive oder intuitionistische Mathematik genannt. Der wichtigste Beitrag des Intuitionismus zur Grundlagenforschung besteht vor allem in der strengen Abgrenzung der konstruktiven von der nicht-konstruktiven Mathematik, denn wirklich rechnen (d. h. Probleme algorithmisch zu lösen) kann man nur im Rahmen der konstruktiven Mathematik.

Wer das Prinzip der Zweiwertigkeit ablehnt, kommt zu einer anderen Art von Logik, in der es mehr als zwei Wahrheitswerte gibt. In diesem Zusammenhang sind die Modallogik, die mehrwertige Logik und die Fuzzy-Logik entstanden.

Das Bestreben, den intuitiven Begriff der Berechenbarkeit zu präzisieren bzw. mathematisch exakt zu definieren, führte schließlich zum Begriff der rekursiven Funktionen, die aufgrund ihrer Definition offenbar im naiven Sinne berechenbar sind. Da so grundlegende Begriffe wie „berechenbar, entscheidbar, konstruierbar“ eng mit dem Begriff der rekursiven Funktion verbunden sind und viele Probleme einer algorithmischen Lösung bedurften, entstand hieraus im Rahmen der mathematischen Logik eine neue Theorie, die sog. Rekursionstheorie. Sie befaßt sich im weitesten Sinne mit den Eigenschaften der rekursiven Funktionen. Obwohl vielfältige Anstrengungen unternommen worden sind, den Berechenbarkeitsbegriff vollständig zu charakterisieren, ist dies bisher nicht in vollem Umfang gelungen. Klar ist nur, daß alle rekursiven Funktionen berechenbar sind, die Umkehrung konnte nur hypothetisch angenommen werden. Die Churchsche (Hypo-)These, die heute allgemein anerkannt wird, besagt, daß die berechenbaren Funktionen genau die rekursiven sind. Unter dieser zwar unbewiesenen, aber doch sehr vernünftig erscheinenden Hypothese werden häufig weitere Untersuchungen angestellt.

Hilbert versuchte mit seinem Programm einer finiten Begründung der klassischen Mathematik einen anderen Weg bei der Überwindung der Grundlagenkrise zu gehen. Er setzte sich entschieden für die Beibehaltung der Cantorschen Ideen zur Mengenlehre, jedoch unter modifizierten Bedingungen, ein. Ihm schwebte eine umfassende Axiomatisierung der Geometrie, der Zahlentheorie, der Analysis, der Cantorschen Mengenlehre und weiterer grundlegender Teilgebiete der Mathematik vor. Aus dieser Grundidee, die gewisse Axiome an den Anfang stellt, die Beweismittel präzisiert und nur auf dieser Basis Schlußfolgerungen zuläßt, entstand eine neue Richtung in der mathematischen Logik, die Beweistheorie. Das Hilbertsche Programm, die Mathematik in wesentlichen Teilen vollständig zu axiomatisieren, erwies sich mit dem Erscheinen der Gödelschen Resultate zur Unvollständigkeit der Arithmetik (Gödelscher Unvollständigkeitssatz) als nicht realistisch. Als Folgerung aus dem Unvollständigkeitssatz ergibt sich sofort die wichtige Erkenntnis: Ist L die Sprache der Arithmetik, ℕ = ⟨N, +, o, < , 0, 1⟩ das Standardmodell der Arithmetik und T die Menge aller in ℕ gültigen Aussagen aus L, dann ist T offenbar vollständig. Folglich ist T nicht rekursiv axiomatisierbar. Anders ausgedrückt: Ist Σ eine beliebige rekursive Teilmenge von T, dann gibt es stets eine Aussage ϕ in L so, daß weder ϕ noch ¬ϕ aus £ beweisbar sind. Jedes solche System ist also unvollständig, und damit ist schon eine so grundlegende Theorie wie die Arithmetik nicht axiomatisierbar. Analoge Überlegungen gelten erst recht für jedes axiomatische System der Mengenlehre, in dem die Arithmetik interpretierbar ist.

Die von Hilbert entwickelten Methoden der Beweistheorie leben aber fort und haben ihren festen Platz in der Mathematik. Ebenso gewann die axiomatische Methode an Einfluß. Die Mengenlehre z. B. wurde mit Erfolg axiomatisch begründet (Axiomatische Mengenlehre). Die aus heutiger Sicht am besten geeignete Axiomatisierung geht auf Zermelo und Fraenkel zurück, so daß sie häufig ZF-Mengenlehre genannt wird. Mit Hilfe verschiedenartiger Mengen-Modelle wurden Abhängigkeitsund Unabhängigkeitsuntersuchungen vorgenommen. Die bekanntesten Resultate in diesem Zusammenhang sind die Ergebnisse von Gödel und P.J. Cohen zur Unabhängigkeit des Auswahlaxioms und der Kontinuumhypothese von den ZF-Axiomen.

Im Zuge der Axiomatisierung weiterer mathematischer Theorien und der Ausnutzung von Methoden und Ergebnissen der klassischen Prädikatenlogik zur Untersuchung von Klassen algebraischer Strukturen entstand die Modelltheorie, die manchmal auf die verkürzende Formel Modelltheorie = Algebra + Logik gebracht wird. Dies stimmte nur in der Anfangsphase der modelltheoretischen Entwicklung. Heute bearbeitet die Modelltheorie mit den Hilfsmitteln der mathematischen Logik Fragestellungen aus praktisch allen Teilgebieten der Mathematik. Beispiele hierfür sind sog. Nichtstandard-Modelle der Arithmetik und der Analysis. Für die Analysis hat sich hieraus ein neuer Zweig, die Nichtstandard-Analysis, gebildet. Die Modelle sind nichtarchimedisch geordnete Körper, in denen es infinitesimale Elemente gibt, sodaß hiermit die Grundidee von Leibniz zur Begründung der Infinitesimalrechnung mit „unendlich kleinen Größen“ tatsächlich realisiert wurde. Die Modelle der Nichtstandard-Analysis enthalten die reellen Zahlen als Unterstruktur, und die Ergebnisse der klassischen Analysis erscheinen als Spezialfälle.

Obwohl der Prädikatenkalkül, bei dem nur Variablen für Elemente, nicht aber gleichzeitig für Elemente und für Mengen von Elementen quantifiziert werden dürfen, als hinreichende Basis für grundlagentheoretische Untersuchungen dient, können in derartigen Sprachen gewisse mathematische Sachverhalte nicht ausgedrückt werden, wie z. B. Isomorphie von Strukturen oder Endlichkeit bzw. Unendlichkeit von Mengen. Aus dem Bedürfnis, nicht nur sog. elementare Eigenschaften formulieren und untersuchen zu können, ergaben sich verschiedenartige Versuche, die Ausdrucksfähigkeit der elementaren Sprachen zu erweitern, indem neue Ausdrucksmittel hinzugenommen wurden.

Läßt man nicht nur die Quantifizierung von Elementen (bzw. für Variablen von Elementen) zu, sondern auch die von Mengen oder Relationen und Funktionen, dann spricht man von Prädikatenkalkülen zweiter oder höherer Stufe, im Gegensatz zum üblichen Prädikatenkalkül, der auch „Prädikatenkalkül der ersten Stufe“ genannt wird.

Eine andere Erweiterung der elementaren Sprachen erhält man durch Hinzunahme neuartiger Quantoren, wie z.B.: „Es gibt höchstens endlich viele … “, „es gibt unendlich viele … “, „es gibt κ (viele) … “, wobei κ eine fixierte unendliche Kardinalzahl ist, „es gibt gleich-viele Elemente … “ (mit bestimmten in der Sprache ausdrückbaren Eigenschaften).

Die Benutzung von infinitären Sprachen (infinitäre Logik) bilden einen weiteren Versuch, die für manche Belange nicht hinreichende Ausdrucksfähigkeit der elementaren Sprachen zu umgehen. Für alle diese Fälle gilt aber, daß die verbesserten Ausdrucksmöglichkeiten „erkauft“ werden müssen durch den Verlust leistungsfähiger Hilfsmittel, so-daß die Nachteile der erweiterten Sprachen gegenüber den elementaren dominieren und ihre Verwendung daher begrenzt blieb.

Insgesamt kann die mathematische Logik aus heutiger Sicht in vier große Teilgebiete untergliedert werden, die sich in starkem Maße gegenseitig befruchten und ineinandergreifen bzw. sich überlappen (die Reihenfolge stellt keine Wertung dar):

  • Logik-Kalküle im weitesten Sinne.
  • Modelltheorie.
  • Axiomatische Mengenlehre.
  • Rekursionstheorie.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos