Prädikatenlogik erster Stufe

Die Prädikatenlogik erster Stufe ist ein Teilgebiet der mathematischen Logik. Sie befasst sich mit der Struktur gewisser mathematischer Ausdrücke und dem logischen Schließen, mit dem man von derartigen Ausdrücken zu anderen gelangt. Dabei gelingt es, sowohl die Sprache als auch das Schließen rein syntaktisch, das heißt ohne Bezug zu mathematischen Bedeutungen, zu definieren. Das dadurch ermöglichte Zusammenspiel von rein syntaktischen Überlegungen einerseits und semantischen Betrachtungen andererseits führt zu wichtigen Erkenntnissen, die Bedeutung für die gesamte Mathematik haben, denn diese lässt sich mittels der Zermelo-Fraenkel-Mengenlehre in der Prädikatenlogik erster Stufe formulieren. Im Unterschied zur Aussagenlogik macht die Prädikatenlogik von Quantoren Gebrauch.

Ein motivierendes Beispiel Die unten aufzustellenden Definitionen sollen am Beispiel der Theorie der geordneten abelschen Gruppen motiviert werden. Eine geordnete abelsche Gruppe besteht zunächst aus einer abelschen Gruppe , das heißt, man hat folgende Eigenschaften Assoziativgesetz: Für alle gilt: . Kommutativgesetz: Für alle gilt: . Neutrales Element 0: Für alle gilt: . Inverses Element: Für alle gibt es ein , sodass gilt: . In mathematischer Kurzschreibweise kann man das auch als

wiedergeben. Dabei schreiben wir an Stelle des oft verwendeten , da wir hier ohnehin über nichts anderes als die Elemente der Gruppe etwas aussagen wollen. Ferner haben wir eine -Relation für die Ordnung auf der Gruppe, die den folgenden Axiomen genügen muss, die hier gleich in Kurzschreibweise angegeben werden: Reflexivität: Transitivität: Gruppenverträglichkeit:

Beispiele für geordnete abelsche Gruppen sind etwa oder .

Insgesamt haben wir einige der sogenannten logischen Symbole verwendet, Klammern als Hilfssymbole, ferner das Gleichheitszeichen und Variablen für die Elemente. Die für die Theorie der geordneten abelschen Gruppen charakteristischen Symbole sind die Konstante 0, die Funktionen + und − sowie die Relation , wobei die in der Mathematik üblichen Schreibweisen benutzt wurden, das heißt statt bzw. statt . Die beiden Funktionen haben unterschiedliche Stelligkeit, + ist zweistellig, die Inversenbildung − ist einstellig, die betrachtete Ordnungsrelation ist zweistellig. Damit sind die Symbole einer ganz bestimmten Sprache beschrieben, in der man die Theorie der geordneten abelschen Gruppen formulieren kann. Manche der aus den Symbolen gebildeten Zeichenketten sind „vernünftig“, d. h. nach gewissen Gesetzmäßigkeiten gebildet, und manche von diesen drücken darüber hinaus „wahre Aussagen“ aus. Dies wird im Folgenden verallgemeinert, insbesondere werden der Unterschied zwischen den nach Regeln gebildeten „vernünftigen“ Zeichenketten und einem möglichen „Wahrheitsgehalt“ solcher Zeichenketten herausgearbeitet sowie sich daraus ergebende Konsequenzen. Diese haben für die gesamte Mathematik Bedeutung.

Die Sprache der Prädikatenlogik erster Stufe Wir beschreiben hier die verwendete Sprache auf rein syntaktische Weise, das heißt, wir legen die betrachteten Zeichenketten, die wir Ausdrücke der Sprache nennen wollen, ohne Bezug auf ihre Bedeutung fest.

Symbole Eine Sprache erster Stufe wird aus folgenden Symbolen aufgebaut:Das Kommazeichen „,“ wird hier nur als Trennzeichen für die Aufzählung der Symbole benutzt, es ist nicht Symbol der Sprache.Zur aussagenlogischen Entsprechung siehe Aussagenlogik §Bausteine der aussagenlogischen Sprache. logische Symbole: Quantoren:  , Junktoren:  , technische Zeichen:  , Variablensymbole:  , eine (möglicherweise leere) Menge von Konstantensymbolen, eine (möglicherweise leere) Menge von Funktionssymbolen, eine (möglicherweise leere) Menge von Relationssymbolen.

Terme Die nach folgenden Regeln aufgebauten Zeichenketten heißen Terme:H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, II, Definition 3.1Zur aussagenlogischen Entsprechung siehe Aussagenlogik §Formationsregeln.   Ist ein Variablensymbol, so ist ein Term. Ist ein Konstantensymbol, so ist ein Term. Ist ein einstelliges Funktionssymbol und ist ein Term, so ist ein Term. Ist ein zweistelliges Funktionssymbol und sind Terme, so ist ein Term. und so weiter für 3-, 4-, 5-,…-stellige Funktionssymbole.

Anmerkungen Ist zum Beispiel eine Konstante und sind und ein- bzw. zweistellige Funktionssymbole, so ist ein Term, da er sich durch Anwendung obiger Regeln erstellen lässt: ist ein Term, daher auch ; und sind Terme, daher auch und damit schließlich auch .

Wir verzichten hier auf Klammern und Kommata als Trennzeichen, das heißt, wir schreiben und nicht . Wir setzen damit implizit voraus, dass unsere Symbole derart beschaffen sind, dass eine eindeutige Lesbarkeit gewährleistet ist. Siehe Polnische Notation. Konstanten werden manchmal als nullstellige Funktionen aufgefasst, was in dieser Notation besonders naheliegend ist.

Die Regeln für die Funktionssymbole fasst man oft so zusammen: o  Ist ein n-stelliges Funktionssymbol und sind Terme, so ist ein Term. Damit ist nichts anderes als die oben angedeutete unendliche Folge von Regeln gemeint, denn die drei Punkte gehören nicht zu den vereinbarten Symbolen. Dennoch wird manchmal von dieser Schreibweise Gebrauch gemacht.

Über den Aufbau der Terme lassen sich weitere Eigenschaften definieren. So ist zunächst die Menge der in einem Term vorkommenden Variablen durch die folgenden drei Regeln rekursiv definiert: Ist ein Variablensymbol, so sei . Ist ein Konstantensymbol, so sei . Ist ein n-stelliges Funktionssymbol und sind Terme, so sei .

Ausdrücke Wir erklären nun durch Bildungsgesetze, welche Zeichenketten wir als Ausdrücke der Sprache ansehen wollen.H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, II, Definition 3.2Es findet sich auch die Bezeichnung Formel, siehe Elementare Sprache §Formeln und Logische Formel. Entsprechend steht dann Atomformel für Atomaren Ausdruck 

Atomare Ausdrücke

Sind und Terme, so ist ein Ausdruck. Ist ein einstelliges Relationssymbol und ist ein Term, so ist ein Ausdruck. Ist ein zweistelliges Relationssymbol und sind Terme, so ist ein Ausdruck. und so weiter für 3-, 4-, 5-,…-stellige Relationssymbole.Gelegentlich werden nullstellige Relationen zugelassen, dies treten dann als logische Konstanten (im Prinzip Bezeichner für wahr oder falsch) auf. Als alternativer Ausdruck für die Relationssymbole findet man auch Prädikate. Siehe

Dabei gelten die oben zur Schreibweise bei Termen gemachten Bemerkungen.

Zusammengesetzte Ausdrücke

Wir beschreiben hier, wie sich aus Ausdrücken weitere gewinnen lassen.Auch als Aussagenlogische Verknüpfungen bezeichnet. Ist ein Ausdruck, so ist auch ein Ausdruck. Sind und Ausdrücke, so sind auch , , und Ausdrücke. Ist ein Ausdruck und ist eine Variable, so sind auch und Ausdrücke.

Damit sind alle Ausdrücke unserer Sprache festgelegt. Ist zum Beispiel ein einstelliges Funktionssymbol und ein 2-stelliges Relationssymbol, so ist

ein Ausdruck, da er sich durch Anwendung obiger Regeln aufbauen lässt. Es sei noch einmal darauf hingewiesen, dass wir die Ausdrücke mittels der genannten Regeln rein mechanisch erstellen, ohne dass die Ausdrücke zwangsläufig irgendetwas bezeichnen müssten.

1. Stufe Unterschiedliche Sprachen erster Stufe unterscheiden sich lediglich in den Mengen , und , die man üblicherweise zur Symbolmenge zusammenfasst und auch die Signatur der Sprache nennt. Man spricht dann auch genauer von -Termen bzw. -Ausdrücken. Die Sprache, das heißt die Gesamtheit aller nach obigen Regeln gebildeten Ausdrücke, wird mit , oder bezeichnet. Bei letzterem steht die römische für die erste Stufe. Dies bezieht sich auf den Umstand, dass gemäß letzter Erzeugungsregel für zusammengesetzte Ausdrücke nur über Variablen quantifiziert werden kann. sieht nicht vor, über alle Teilmengen einer Menge, über Relationenmit dem Spezialfall einstelliger Relationen = Teilmengen oder über Funktionen zu quantifizieren. So lassen sich die üblichen Peano-Axiome nicht in ausdrücken, da das Induktionsaxiom eine Aussage über alle Teilmengen der natürlichen Zahlen macht. Das kann als Schwäche dieser Sprache angesehen werden, allerdings sind die Axiome der Zermelo-Fraenkel-Mengenlehre sämtlich in der ersten Stufe mit dem einzigen Symbol formulierbar, so dass die erste Stufe prinzipiell für die Mathematik ausreicht.H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, VII: Zur Tragweite der ersten Stufe

Freie Variablen Weitere Eigenschaften von Ausdrücken der Sprache lassen sich ebenfalls rein syntaktisch definieren. Gemäß dem oben beschriebenen Aufbau durch Bildungsregeln wird die Menge der im Ausdruck frei vorkommenden Variablen wie folgt rekursiv definiert:H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, II, Definition 5.1 

und genauso für

Nicht-freie Variable heißen gebundene Variable. Ausdrücke ohne freie Variable, das heißt solche mit , nennt man Sätze. Sämtliche in obigem motivierenden Beispiel angegebenen Axiome der geordneten abelschen Gruppen sind bei entsprechender Übersetzung in die Sprache Sätze, so zum Beispiel für das Kommutativgesetz.

Metasprachliche Ausdrücke Das gerade gegebene Beispiel als Symbolisierung des Kommutativgesetzes in der Sprache zeigt, dass die entstehenden Ausdrücke oft schwer lesbar sind. Daher kehrt der Mathematiker, und oft auch der Logiker, gern zur klassischen Schreibweise zurück. Letzteres ist aber kein Ausdruck der Sprache , sondern nur eine Mitteilung eines solchen Ausdrucks unter Verwendung anderer Symbole einer anderen Sprache, hier der sogenannten Metasprache, das heißt derjenigen Sprache, in der man über spricht. Aus Gründen der besseren Lesbarkeit lässt man auch gern überflüssige Klammern weg. Das führt nicht zu Problemen, solange klar bleibt, dass man die leichter lesbaren Zeichenketten jederzeit zurückübersetzen könnte.

Substitutionen Häufig werden in der Mathematik Variablen durch Terme ersetzt. Auch das lässt sich hier rein syntaktisch auf Basis unserer Symbole erklären. Durch folgende Regeln legen wir fest, was es bedeuten soll, den Term für eine Variable einzusetzen. Die Substitution wird für Terme als und für Ausdrücke als gleichermaßen durch eckige Klammern notiert. Die eckigen Klammern dürfen auch weggelassen werden.

Für Terme wird die Substitution wie folgt definiert: Ist ein Variablensymbol, so ist gleich , falls , und sonst. Ist ein Konstantensymbol, so ist . Sind ein n-stelliges Funktionssymbol und Terme, so ist .

Für Ausdrücke legen wir fest:

analog für die Junktoren , dabei sei eine Variable, die nicht in oder vorkommt, zum Beispiel die erste der Variablen , die diese Bedingung erfüllt. Bei dieser Definition wurde darauf geachtet, dass Variablen nicht unbeabsichtigt in den Einflussbereich eines Quantors geraten. Falls die gebundene Variable im Term auftritt, so wird diese zuvor durch eine andere ersetzt, um so die Variablenkollision zu vermeiden. analog für den Quantor .

Schlussbemerkung zur Syntax