Die Philosophie der Mathematik

Die Geburt der modernen Logik

Die Vollständigkeit der Prädikatenlogik erster Ordnung

Die Prädikatenlogik erster Ordnung zeichnet sich dadurch aus, dass sie Verallgemeinerung, also Quantifizierung, nur über Objekte erlaubt: Die Logik zweiter Ordnung gestattet Verallgemeinerung oder Quantifizierung über Eigenschaften oder Arten von Objekten sowie über Relationen zwischen ihnen und über Funktionen, die auf ihnen definiert sind. Wenn ich zu jemandem sage „Du hast etwas von mir“, verwende ich das Wort „etwas“, um über Objekte zu verallgemeinern: Ich meine, dass er irgendein Objekt besitzt, zum Beispiel ein Tonbandgerät, das mir gehört. Sage ich hingegen „Du bist etwas, das ich nicht bin“, und er fragt „Was?“, antworte ich „Ein erfahrener Linguist“. In diesem Fall verwende ich „etwas“, um über Arten von Dingen oder Personen zu verallgemeinern: Es gibt etwas, das für ihn zutrifft, für mich jedoch nicht. Ähnlich, wenn ich sage „Du bist ihr etwas, das ich nicht bin“, verallgemeinere ich über Relationen: Auf die Frage „Was?“ könnte ich „Ein Cousin“ antworten. Ein Mischfall entsteht, wenn eine Person zu einer anderen sagt „Du besitzt etwas, das wir nicht besitzen“, wobei die Antwort auf „Was?“ ein CD-Player sein könnte. Die Aussage bedeutet „Du besitzt ein Objekt bestimmter Art, und wir besitzen kein Objekt dieser Art“. Die Prädikatenlogik erster Ordnung bezieht sich auf jene Schlussprinzipien, die nur Verallgemeinerung über Objekte enthalten; die Logik zweiter Ordnung umfasst auch Prinzipien, die Verallgemeinerung über Eigenschaften, Relationen und Funktionen von Objekten betreffen.

Eine formalisierte Theorie behandelt bestimmte Entitäten als ihre Grundobjekte: Eine formale Theorie der elementaren Arithmetik nimmt beispielsweise die natürlichen Zahlen als Objekte. Ist sie eine Theorie erster Ordnung, kann in der formalen Sprache nur Quantifizierung über die natürlichen Zahlen ausgedrückt werden: Sie kann Aussagen treffen wie „Alle natürlichen Zahlen haben eine bestimmte Eigenschaft“ oder „Es gibt einige natürliche Zahlen, die eine andere Eigenschaft besitzen“. Erst in einer Theorie zweiter Ordnung wird es möglich, zu sagen, dass eine Zahl jede Eigenschaft erfüllt, die eine bestimmte Bedingung erfüllt, dass sie zu einer anderen Zahl in einer bestimmten Relation steht, oder dass eine Funktion existiert, die jede natürliche Zahl auf Zahlen einer bestimmten Art abbildet. Frege unterschied nicht scharf zwischen erster und zweiter Ordnung und betrachtete beide als gleichermaßen zur Logik gehörend: Der letzte Teil seiner Begriffsschrift enthält weitreichende Untersuchungen der Logik zweiter Ordnung. Seit seiner Zeit ist es üblich geworden, streng zwischen stärkeren und schwächeren Logikarten zu unterscheiden, so streng, dass manche sogar die Berechtigung der Logik zweiter Ordnung als Logik infrage stellen.

Der Grund liegt in der zuvor genannten Bemerkung, dass Freges Begriffsschrift eine vollständige Formalisierung der Logik erster Ordnung enthielt. Vollständig zu sagen bedeutet, dass jede gültige logische Schlussfolgerung erster Ordnung in Freges formalem System durchgeführt werden kann; um das zu beweisen, benötigen wir jedoch eine unabhängige Charakterisierung gültiger Schlüsse. Angesichts der Art, wie Frege die Formalisierung durchführte, eine Methode, der alle nachfolgenden Logiker wie David Hilbert und Bertrand Russell bis zu Gerhard Gentzen folgten, genügt es, eine gültige einzelne Formel zu charakterisieren; wir benötigen jedoch immer noch ein Mittel, dies anders zu tun als durch Bezug auf die Formalisierung. Die Logik erster Ordnung erfordert die Verwendung schematischer Buchstaben, die als Stellvertreter für beliebige Ausdrücke eines gegebenen logischen Typs stehen. Standardmäßig gibt es Satzbuchstaben, die ganze Sätze repräsentieren, individuelle Konstanten, die einzelne Terme darstellen, einstellige Prädikatbuchstaben für Prädikate und zwei- oder mehrstellige Prädikatbuchstaben für relationale Ausdrücke. Ein einfaches Gesetz der klassischen Prädikatenlogik erster Ordnung lässt sich dann in Worten formulieren als „Alles ist entweder F oder nicht F“. Ein Gesetz mit Relationen lautet „Wenn es etwas gibt, auf das alles R zutrifft, dann trifft alles auf etwas R zu“. Im ersten Fall ist F ein schematischer einstelliger Prädikatbuchstabe, im zweiten R ein schematischer zweistelliger Prädikatbuchstabe. Die Gültigkeit der beiden Formeln besteht darin, dass unabhängig davon, welches Prädikat F ersetzt oder welche zweistellige Relation R ersetzt, ein wahrer Satz resultiert.

Eine gültige Formel ist eine, die unter jeder Interpretation ihrer schematischen Buchstaben wahr ist; wir definieren „Interpretation“ jedoch nicht über die Substitution durch Ausdrücke einer tatsächlichen Sprache, die in entscheidender Weise fehlerhaft sein könnte. Standardmäßig wird eine Interpretation einer Formel erster Ordnung wie folgt bestimmt: Zunächst wird eine nichtleere Menge als Definitionsbereich der Variablen festgelegt. Dann wird jeder individuellen Konstanten ein Element dieses Bereichs zugewiesen, und für jeden einstelligen Prädikatbuchstaben wird festgelegt, für welche Elemente er wahr ist; für zweistellige Prädikatbuchstaben wird bestimmt, zwischen welchen Elementen die Relation gilt, und ebenso für drei- oder mehrstellige Prädikatbuchstaben; schließlich wird jedem einstelligen Funktionsbuchstaben eine einstellige Funktion über den Bereich zugewiesen, jedem zweistelligen Funktionsbuchstaben eine zweistellige Funktion usw. Enthält die Formel Satzbuchstaben, werden diesen Wahrheitswerte zugewiesen. Auf offensichtliche Weise kann bestimmt werden, ob die gegebene Formel unter einer so bestimmten Interpretation wahr ist. Die Formel ist gültig, wenn sie unter jeder solchen Interpretation wahr ist. Ebenso ist ein Schluss gültig, wenn seine Konklusion unter jeder Interpretation wahr ist, unter der auch seine Prämissen wahr sind.

Eine Formel zweiter Ordnung muss keine schematischen Buchstaben enthalten: Hier wird eine Interpretation einfach dadurch bestimmt, dass der Definitionsbereich der Variablen festgelegt wird. Einstellige Prädikatvariablen erstrecken sich dann normalerweise über alle Eigenschaften der Elemente des Bereichs, zweistellige Prädikatvariablen über alle binären Relationen zwischen Elementen, einstellige Funktionsvariablen über alle einstelligen Funktionen auf diesen Elementen und so weiter.

Wir haben nun ein zweifaches Mittel zur Charakterisierung der intuitiven Vorstellungen eines logisch wahren Satzes und eines korrekten Schlusses. Auf der einen Seite steht die beweistheoretische oder syntaktische Charakterisierung, die auf der Formalisierung des relevanten Teils der Logik beruht: Eine Formel ist beweisbar, wenn die Formalisierung einen Beweis zulässt, und die Konklusion eines Schlusses ist ableitbar aus den Prämissen, wenn die Formalisierung ihre Ableitung erlaubt. Auf der anderen Seite steht die modelltheoretische oder semantische Charakterisierung: Eine Formel ist gültig, wenn sie unter jeder Interpretation wahr ist, und ein schematischer Schluss ist korrekt, wenn seine Konklusion unter jeder Interpretation, unter der die Prämissen wahr sind, ebenfalls wahr ist. Diese Unterscheidung ist grundlegend und eine der zentralen Errungenschaften der modernen Logik, klar herausgearbeitet zu sein; selbst Frege, der Begründer der modernen Logik, hatte sie nicht scharf formuliert.

Die semantische Vorstellung beurteilt jede versuchte Formulierung der syntaktischen Vorstellung. Eine Formalisierung eines Teils der Logik, wie der Prädikatenlogik erster Ordnung, ist korrekt, wenn jede darin beweisbare Formel gültig ist. Ist sie nicht korrekt, ist sie eindeutig fehlerhaft. Ist sie korrekt, sollte sie idealerweise auch vollständig sein. Sie ist vollständig, wenn jede gültige, in ihrer Sprache ausdrückbare Formel beweisbar ist. Die Vollständigkeit der Standardformalisationen der Prädikatenlogik erster Ordnung, einschließlich Freges Originalfassung, wurde erstmals von Kurt Gödel 1930 bewiesen. Es folgt jedoch aus seinem berühmten Unvollständigkeitssatz der Arithmetik, dass die Logik zweiter Ordnung unvollständig ist. Sie ist nicht zufällig unvollständig aufgrund fehlender Prinzipien; sie ist im Wesentlichen unvollständig, da keine vollständige Formalisierung möglich ist. Dies motiviert die heute übliche strenge Unterscheidung zwischen erster und zweiter Ordnung.

Es ist wichtig, die Vollständigkeit einer Formalisierung eines Logikteils nicht mit der Vollständigkeit einer formalisierten mathematischen Theorie zu verwechseln. Eine solche Theorie hat primitive Ausdrücke, speziell für den Gegenstand der Theorie, und Axiome, aus denen die Theoreme gemäß der Formalisierung des relevanten Logikteils abgeleitet werden. Von einer formalen Theorie verlangen wir zunächst Konsistenz: Es darf keinen Satz geben, der beweisbar ist und dessen Negation ebenfalls beweisbar ist, oder einfacher: Es muss mindestens ein Satz in der Sprache der Theorie existieren, der nicht beweisbar ist. Die Vollständigkeit einer formalen Logik bestand in der Übereinstimmung der beweistheoretischen Vorstellung von Beweisbarkeit mit der modelltheoretischen Vorstellung von Gültigkeit. Die Vollständigkeit einer formalen Theorie ist hingegen rein beweistheoretisch: Für jeden in der Sprache der Theorie ausgedrückten Satz ist entweder der Satz oder seine Negation beweisbar. Modelltheoretische Begriffe lassen sich für formale Theorien definieren, indem die primitiven Ausdrücke der Theorie, die intendierte Interpretationen haben, wie schematische Buchstaben behandelt werden. Ein Modell der Theorie ist dann eine Interpretation, unter der alle Axiome wahr sind. Das modelltheoretische Äquivalent zur Vollständigkeit ist die Kategorizität. Eine Theorie ist kategorisch, wenn sie im Wesentlichen nur ein Modell hat, genauer, wenn alle ihre Modelle isomorph sind. Ein Modell besteht aus einer Menge von Objekten, zusammen mit bestimmten Elementen, Eigenschaften, Relationen und Funktionen, die die Interpretation der Terme, Prädikate und Funktionssymbole der Theorie bilden; die Axiome und Theoreme der Theorie müssen im Modell wahr sein. Zwei Modelle sind isomorph, wenn sie exakt die gleiche abstrakte Struktur haben. Formal ausgedrückt, existiert eine Abbildung der Elemente des einen Modells auf die des anderen, die eindeutig ist und jede Eigenschaft, Relation und Funktion des einen Modells in die entsprechende des anderen überträgt. Ein trivialer Fall: Eine formale Theorie bezieht sich auf die Wahrheitswerte T und F; ihre Primitiven sind T, Q für die Relation zwischen T und F, und ein binärer Operator für die Funktion der Konjunktion. Ein anderes Modell könnte den Bereich aus den Zahlen i und o nehmen, T als i interpretieren, Q als Relation zwischen i und o, und den Operator als Multiplikation deuten. Unter der Abbildung, die T auf i und F auf o abbildet, wird die Konjunktion auf Multiplikation übertragen. Das intendierte Modell ist isomorph zum Modell mit i und o: Sie sind strukturell ununterscheidbar.