Hauptmenü öffnen

Prädikatenlogik erster Stufe

Familie logischer Systeme

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.

Inhaltsverzeichnis

Ein motivierendes BeispielBearbeiten

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 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 wird 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 StufeBearbeiten

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.

SymboleBearbeiten

Eine Sprache erster Stufe wird aus folgenden Symbolen aufgebaut:[1][2][3]:S. 45

  • 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.

TermeBearbeiten

Die nach folgenden Regeln aufgebauten Zeichenketten heißen Terme:[4][5][3]:S. 45 [6]:S. 3 [7]:S. 4

  • 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.
  • Ist   ein dreistelliges Funktionssymbol und sind   Terme, so ist   ein Term.
  • und so weiter für 4,5,6,…-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 Relationen 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ückeBearbeiten

Wir erklären nun durch Bildungsgesetze, welche Zeichenketten wir als Ausdrücke der Sprache ansehen wollen.[8][9][3]:S. 46 f [7]:S. 4

Atomare Ausdrücke [6]:S. 5

  • 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.[10]

Dabei gelten die oben zur Schreibweise bei Termen gemachten Bemerkungen.

Zusammengesetzte Ausdrücke[6]:S. 6

Wir beschreiben hier, wie sich aus Ausdrücken weitere gewinnen lassen.[11]

  • 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. StufeBearbeiten

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 nur über (einfache) Variablen quantifiziert werden kann.   sieht nicht vor, über alle Teilmengen einer Menge, über Relationen[12] 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.[13]

Freie VariablenBearbeiten

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:[14][3]:S. 48 f [7]:S. 6

  •  
  •  
  •  
  •   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ückeBearbeiten

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.

SubstitutionenBearbeiten

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. Wir folgen dabei wieder dem regelhaften Aufbau von Termen und Ausdrücken. Die Ersetzung wird als   notiert, wobei die eckigen Klammern weggelassen werden dürfen.

Für Terme   wird die Einsetzung   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 schreiben wir eckige Klammern um den Ausdruck, in dem die Substitution vorgenommen werden soll. Wir legen fest:

  •  
  •  
  •  
  •   und genauso für  
  •  ; analog für den Quantor  
  •   falls   und  ; analog für den Quantor  
  •   falls   und  , wobei   eine Variable sei, die nicht in   oder   vorkommt, zum Beispiel die erste der Variablen  , die diese Bedingung erfüllt. Die analoge Festlegung wird für   getroffen.

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.

Schlussbemerkung zur SyntaxBearbeiten

Es sei noch einmal betont, dass alles bisher Gesagte nur den Aufbau beziehungsweise die Manipulation gewisser Zeichenketten beschreibt, es handelt sich um rein syntaktische Begriffe. Weder den Zeichenketten noch ihren Manipulationen sind irgendwelche Bedeutungsinhalte zugeordnet. Selbstverständlich liest man unwillkürlich die „Bedeutungen“, die durch obiges Beispiel suggeriert sind, mit, das heißt man liest ein   als „für alle“ und ein   als „und“ und kann sich nur schwer von ihren „umgangssprachlichen Bedeutungen“ frei machen. Man sollte sich aber darüber im Klaren sein, dass eine solche „Bedeutung“ für die vorgestellten Begriffsbildungen nicht erforderlich ist und an keiner Stelle verwendet wird. Es ist ein wesentlicher Punkt, dass die intendierte Bedeutung dieser Zeichenketten, ihre Semantik, erst in einem im Folgenden vorgestellten Schritt hinzugefügt wird.

SemantikBearbeiten

Wir gehen von einer Sprache   aus. Die nach obigen Regeln in dieser Sprache gebildeten Ausdrücke sollen nun mit mathematischen Strukturen in Verbindung gebracht werden. In diesen Strukturen kann man die Ausdrücke dann auf ihren Wahrheitsgehalt hin untersuchen, was im Folgenden präzisiert wird.

StrukturenBearbeiten

Eine Struktur   über einer Signatur   ist eine nicht-leere Menge   zusammen mit

  • einem Element   für jedes Konstantensymbol  ,
  • einer Funktion   für jedes  -stellige Funktionssymbol  ,
  • einer Relation   für jedes  -stellige Relationssymbol  .

Im eingangs gegebenen Beispiel geordneter abelscher Gruppen ist   eine  -Struktur. Durch  -Strukturen werden also die Symbole aus   mit „echten“ Konstanten, Funktionen und Relationen in Zusammenhang gebracht.

InterpretationenBearbeiten

Eine Interpretation von   ist ein Paar   bestehend aus einer  -Struktur   und einer Abbildung  .

Man verbindet damit die Vorstellung, dass die Struktur das mathematische Objekt ist, das mit der Sprache beschrieben werden soll, während   die Variablen mit Werten aus der Grundmenge   belegt, weshalb man diese Abbildung auch Belegung nennt. Die Belegung einer Interpretation kann leicht auf Terme ausgedehnt werden, diese Ausdehnung hängt von der Interpretation der Konstantensymbole und Funktionssymbole ab und wird daher ebenfalls mit   bezeichnet; man legt fest:

  • Ist   eine Variable, so sei  .
  • Ist   ein Konstantensymbol, so sei  .
  • Ist   ein n-stelliges Funktionssymbol und sind   Terme, so sei  .

Setzt man etwa  , so ist   eine solche Interpretation. Dann gilt  .

Ändern wir eine Belegung nur an der Stelle   ab und bilden dieses   auf   ab, so schreiben wir   für die so abgeänderte Belegung und  . Oft ist die Belegung der Variablen klar oder unwichtig; dann nennen wir, etwas unsauber aber praktisch, auch die Struktur   eine Interpretation.

ModelleBearbeiten

Wir wollen sagen, dass eine Interpretation   ein Modell für einen   Ausdruck   ist und dafür   schreiben, wenn sich dies auf Grund folgender Regeln ergibt:[15]
 

Diese Definition orientiert sich wieder am regelhaften Aufbau der Ausdrücke der Sprache  . Die Pünktchenschreibweise in der zweiten Regel steht hier wieder für eine Liste von Regeln, für jede Stelligkeit eine.

Durch den Begriff der Interpretation wurden die Variablen und die Symbole aus   mit einer Bedeutung versehen. Durch die gerade definierte Modellbeziehung werden erstmals auch die logischen Symbole interpretiert.

Für eine Menge   von Ausdrücken schreiben wir  , wenn   für alle   gilt, und sagen   sei ein Modell von  . Bezeichnet   etwa die oben genannten Axiome der geordneten abelschen Gruppen, so gilt   genau dann, wenn   eine geordnete abelsche Gruppe ist. Dabei scheint die Belegung   keine Rolle zu spielen, da   nur aus Sätzen besteht, also keine freien Variablen enthält. Das ist tatsächlich der Fall, wie das sogenannte Koinzidenzlemma aussagt. In einem solchen Fall kann man   weglassen und einfach   schreiben. Damit ist dann ausgesagt, dass   für jede Belegung   ein Modell aller Ausdrücke aus   ist.

GleichheitBearbeiten

Zur Verwendung der Gleichheit ist anzumerken, dass wir in der Sprache erster Stufe das Symbol   eingeführt haben. Ein Ausdruck der Form   ist kein Ausdruck der Sprache erster Stufe, sondern die metasprachliche Behauptung der Gleichheit der beiden Ausdrücke   und  . Letzteres lässt sich in der Sprache erster Stufe gar nicht symbolisieren, dort können nur Terme gleich sein. Parallel zum hier betrachteten Aufbau gibt es auch die Prädikatenlogik erster Stufe ohne Gleichheit, dazu entfernt man das Symbol   und die es betreffende Bildungsregel. Zwar kann man die Gleichheit dann über eine Relation wieder ins Spiel bringen, setzt diese dann aber Interpretationen aus, so dass man nicht dasselbe erhält wie eine Logik mit Gleichheit. Die logische Gleichheit   hingegen bedeutet in jeder Interpretation Gleichheit von Individuen, und das ist der Grund, warum man Logiken mit Gleichheit betrachtet.[16]

Mathematisches SchließenBearbeiten

FolgerungenBearbeiten

Es sei   eine gegebene Menge von Ausdrücken, zum Beispiel obige Axiome der geordneten abelschen Gruppen. Der Mathematiker interessiert sich dafür, welche Folgerungen aus ihnen gezogen werden können. Wir sagen, der Ausdruck   folge aus   und schreiben dafür  , wenn jedes Modell von   auch Modell von   ist. Das ist die sogenannte semantische Schlussweise, da sie Bezug auf alle möglichen Interpretationen der Symbole nimmt.

SequenzenkalkülBearbeiten

In der Regel schließt der Mathematiker nicht semantisch, sondern er wendet gewisse Schlussregeln an, mit denen er sich von einer Aussage zur nächsten bis zur Behauptung vorarbeitet. Ausgehend von einer gegebenen Folge   von Ausdrücken geht er zu neuen Folgen   über, um am Ende mit einer Folge   „bewiesen“ zu haben, dass   aus   folgt. Der „Beweis“ ist dabei eine endliche Liste solcher Folgen. Hier werden einige solcher Schlussregeln vorgestellt, ihr inhaltlicher Hintergrund beleuchtet und anschließend mit der semantischen Schlussweise verglichen. In   nennt man   das Antezedens und die nachfolgenden Ausdrücke das Sukzedens.

Voraussetzungsregel:   ist eine erlaubte Folge, wenn  . Dahinter steckt der einfache Tatbestand, dass man jederzeit eine der Voraussetzungen aus   verwenden darf.

Antezedensregel: Falls man   bereits hat, so kann man zu   übergehen, falls  . Wenn man nämlich von   auf   schließen kann, so kann man das erst recht unter noch stärkeren Voraussetzungen tun.

Fallunterscheidung: Falls man   und   bereits hat, so kann man zu   übergehen. Man kann im Falle   von   auf   schließen, und auch im Falle von  . Daher kann man in jedem Fall von   auf   schließen.

Widerspruch: Falls man   und   bereits hat, so kann man zu   übergehen. Nimmt man nämlich im Sinne eines Widerspruchsbeweises an, dass   gilt, so ergibt sich aus den Voraussetzungen sowohl   als auch  , insgesamt also ein Widerspruch. Daher war die Annahme   falsch und man kann auf   schließen.

Odereinführung im Antezedens: Falls man   und   bereits hat, so kann man zu   übergehen. Unter den Voraussetzungen   ergibt sich   sowohl aus   als auch aus  . Daher ergibt sich   bereits, wenn   oder   gilt.

Odereinführung im Sukzedens: Falls man   bereits hat, so kann man zu   übergehen. Das ist klar, da mit   erst recht   gilt. Entsprechend kann man auch zu   übergehen.

Gleichheit: Man kann jederzeit den Ausdruck   hinschreiben, wobei   ein beliebiger Term ist. Diese Regel bedarf keiner Erläuterung.

Die noch folgenden drei Schlussregeln verwenden die oben definierte Substitution von Variablen durch Terme:

Substitution: Falls man   bereits hat, so kann man zu   übergehen. Wenn man aus   auf  , das heißt auf   mit der Ersetzung   an Stelle von  , schließen kann, so auch auf   mit der Ersetzung   an Stelle von  , falls   gleich   ist.

Existenzeinführung im Antezedens: Falls man   bereits hat, so kann man zu   übergehen. Um mit der Existenzvoraussetzung   arbeiten zu können, darf man ein   verwenden, für das   gilt. In Beweisen, die diese Regel verwenden, heißt dann nach der Existenzvoraussetzung: Sei   so ein ...

Existenzeinführung im Sukzendens: Falls man   bereits hat, so kann man zu   übergehen. Auch diese Regel ist einsichtig, denn wenn man mit   ein Beispiel für   gefunden hat, so kann man auf die Existenzaussage schließen und das Beispiel dabei nicht mehr erwähnen.

Die hier vorgestellten Regeln, die den sogenannten Sequenzenkalkül bilden, sind logisch schlüssig, wie als Zusatz zu jeder Regelnennung ausgeführt wurde. Mathematiker verwenden noch einige andere Schlussregeln, von denen aber gezeigt werden kann, dass sie alle aus den oben genannten hergeleitet werden können, das heißt, ihre Anwendung kann durch eine endliche Kette obiger Regeln ersetzt werden. Wenn man ausgehend von   nach endlich vielen Anwendungen dieser Regeln zu   gelangt ist, so ist damit   aus   logisch schlüssig abgeleitet, wir schreiben dafür  .

Im Gegensatz zur oben erklärten semantischen Schlussweise sind die „Beweise“   rein syntaktischer Natur, man kann sie als Manipulation von Zeichenketten der betrachteten Sprache ansehen. Um die Schlussregeln anwenden zu können, muss man nicht wissen, was die Symbole bedeuten.

Vollständigkeit und KorrektheitBearbeiten

Ist die Interpretation   ein Modell für eine Menge   von Ausdrücken der Sprache   und ist  , so ist   auch ein Modell für  , denn der mit   einhergehende Beweis lässt sich ja ohne Weiteres direkt im Modell ausführen. Es gilt also der sogenannte Korrektheitssatz, dass aus   stets   folgt.

Umgekehrt wäre es durchaus denkbar, dass es zu einer Ausdrucksmenge   nur einige wenige Modelle gibt, die zufällig eine in der Sprache erster Stufe ausdrückbare Eigenschaft   gemeinsam haben, ohne dass es dazu eine Möglichkeit gäbe, sie durch obige syntaktische Zeichenkettenoperationen aus   ableiten zu können. Dass dies nicht der Fall ist, sondern dass semantische und syntaktische Schlussweisen gleichwertig sind, ist als Gödelscher Vollständigkeitssatz bekannt und ein zentrales Ergebnis der Prädikatenlogik erster Stufe. Man kann zeigen, dass sich zu einer Prädikatenlogik zweiter Stufe, in der man Quantifizierungen über Relationen zulässt, kein zur semantischen Schlussweise gleichwertiger Sequenzenkalkül finden lässt.

EigenschaftenBearbeiten

ErfüllbarkeitssatzBearbeiten

Eine Menge   von Ausdrücken der Sprache   heißt widerspruchsfrei, wenn sich kein Ausdruck der Form   aus   ableiten lässt. Damit ist Widerspruchsfreiheit ein rein syntaktischer Begriff. Es gilt folgender Erfüllbarkeitssatz, der sich aus dem Satz von Henkin herleiten lässt und eng mit dem Gödelschen Vollständigkeitssatz verbunden ist:

  • Zu jeder widerspruchsfreien Menge   gibt es ein Modell.

KompaktheitssatzBearbeiten

  • Kompaktheitssatz: Ist   eine Menge von Ausdrücken der Sprache   und gibt es zu jeder endlichen Teilmenge von   ein Modell, so gibt es auch ein Modell für  [17].

Gäbe es nämlich kein Modell für  , so wäre   nach dem Erfüllbarkeitssatz nicht widerspruchsfrei, und es gäbe dann eine Ableitung  . Da ein Beweis aber nur eine endliche Länge hat und daher auch nur endlich viele der Ausdrücke aus   involvieren kann, muss es bereits eine endliche Teilmenge   geben mit  . Nach dem Vollständigkeitssatz folgt  , das heißt, es kann für   kein Modell geben, im Widerspruch zur Voraussetzung.

Der Endlichkeitssatz wird auch Kompaktheitssatz genannt: Man wähle zu jeder widerspruchsfreien Menge   von Sätzen ein Modell   und fasse die so gefundenen Modelle zu einer Menge   zusammen. Für einen Satz   sei  . Dann bilden die Mengen   die Basis einer Topologie auf   und der Endlichkeitssatz ist zur Kompaktheit dieses Raums äquivalent.

IsomorphienBearbeiten

Aus dem Endlichkeitssatz folgt:

  • Gibt es zu einer Menge   von Ausdrücken der Sprache   ein unendliches Modell, so gibt es Modelle beliebig hoher Mächtigkeit.

Ist nämlich   gegeben und ist   eine Kardinalzahl, so sei   eine Menge von nicht in   enthaltenen Konstantensymbolen. Jede endliche Teilmenge von   hat dann ein Modell in der Sprache  , wobei   die um die neuen Konstantensymbole erweiterte Symbolmenge sei. Wegen des Endlichkeitssatzes gibt es dann ein Modell für  , und das hat mindestens die Mächtigkeit  . Mit etwas genauerer Argumentation kann man sogar ein Modell der Mächtigkeit   finden, falls die Mächtigkeit von   kleiner gleich   ist.

Hier zeigt sich eine Schwäche der Prädikatenlogik erster Stufe. Mittels der Sprache der ersten Stufe kann für Ausdrucksmengen mit unendlichen Modellen niemals eine Charakterisierung bis auf Isomorphie gelingen, denn die Klasse aller Modelle zu einer solchen widerspruchsfreien Menge von Ausdrücken enthält stets Modelle beliebig hoher Mächtigkeit, also auch nicht isomorphe Modelle. Man nennt zwei Modelle elementar äquivalent, wenn die Mengen der Ausdrücke, für die sie Modelle sind, übereinstimmen. Die Sprachen erster Stufe können daher unendliche Strukturen bzw. Modelle nur bis auf elementare Äquivalenz charakterisieren.

Satz von Löwenheim-SkolemBearbeiten

Ebenfalls aus dem Satz von Henkin lässt sich der Satz von Löwenheim-Skolem ableiten:

  • Gibt es zu einer höchstens abzählbaren Menge   von Ausdrücken der Sprache   ein unendliches Modell, so gibt es auch ein abzählbares Modell.

Im einleitenden Beispiel ist   ein abzählbares Modell. In vielen mathematischen Theorien lassen sich diese sehr leicht finden, in der Modelltheorie hat das Löwenheim-Skolem-Theorem aber tiefgehende Anwendungen.

Satz von LindströmBearbeiten

Wegen oben genannter Schwächen der Sprache erster Stufe kann man nach geeigneten Erweiterungen suchen. Wenn man auf diese Weise echt ausdrucksstärkere Sprachen findet, was natürlich noch zu präzisieren wäre, so zeigen die Sätze von Lindström, dass man dann auf den Endlichkeitssatz oder auf den Satz von Löwenheim-Skolem verzichten muss. Will man beide Sätze beibehalten, so ist die Prädikatenlogik erster Stufe also „das Beste“, was man erreichen kann.

Siehe auchBearbeiten

LiteraturBearbeiten

Einzelnachweise und AnmerkungenBearbeiten

  1. Das Kommazeichen „,“ wird hier nur als Trennzeichen für die Aufzählung der Symbole benutzt, es ist nicht Symbol der Sprache.
  2. Zur aussagenlogischen Entsprechung siehe Aussagenlogik §Bausteine der aussagenlogischen Sprache.
  3. a b c d Erich Grädel: Mathematische Logik. Mathematische Grundlagen der Informatik, SS 2009. RWTH, Aachen, S. 129 (uni-dortmund.de [PDF]).
  4. H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, II, Definition 3.1
  5. Zur aussagenlogischen Entsprechung siehe Aussagenlogik §Formationsregeln.
  6. a b c W. Vogler: Logik für Informatiker. WS 2007/2008. Univ. Augsburg, Institut für Informatik, Augsburg, S. 49 (uni-augsburg.de [PDF]).
  7. a b c R. Kruse, C. Borgelt: Grundbegriffe der Prädikatenlogik. Computational Intelligence. Otto-von-Guericke Universität, Magdeburg 2008, S. 14 (fuzzy.cs.ovgu.de [PDF]).
  8. H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, II, Definition 3.2
  9. Es findet sich auch die Bezeichnung Formel, siehe Elementare Sprache §Formeln und Logische Formel. Entsprechend steht dann Atomformel für Atomaren Ausdruck
  10. 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 Stefan Brass: Mathematische Logik mit Datenbank-Anwendungen. Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, Halle 2005, S. 176, hier S. 19 (uni-halle.de [PDF]).
  11. Auch als Aussagenlogische Verknüpfungen bezeichnet.
  12. mit dem Spezialfall einstelliger Relationen = Teilmengen
  13. 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
  14. 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
  15. H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, III, Definition 3.2
  16. Philipp Rothmaler: Einführung in die Modelltheorie, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5, Ende des Absatzes 3.1.
  17. H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN 3-8274-0130-5, VI.2.1