Vollständigkeit (Logik)

Vollständigkeit (Logik)

Man bezeichnet ganz unterschiedliche Eigenschaften formaler Systeme bzw. Kalküle mit dem Begriff Vollständigkeit. Zur Unterscheidung werden die Begriffe

  • Vollständigkeit von Theorien
  • Vollständigkeit von Sequenzenkalkülen

verwendet. Daneben wird dieser Begriff auch im Sinne der

  • funktionalen Vollständigkeit von Junktorenmengen

benutzt.

Inhaltsverzeichnis

Vollständigkeit von Theorien

Definition

Unter einer Theorie versteht man eine echte Teilmenge T von Sätzen einer Sprache L_I^S der Prädikatenlogik erster Stufe, die bezüglich der Folgerungsrelation \vDash abgeschlossen ist, das heißt, aus T\vDash \alpha folgt bereits \alpha \in T für alle Sätze α der Sprache. Ist \mathcal A ein Modell, so ist offenbar T = Th(\mathcal{A}) := \{\alpha;\, \mathcal{A}\vDash\alpha\} eine Theorie. Man nennt eine Theorie vollständig, wenn sie für jeden Satz α entweder diesen oder seine Negation \neg\alpha enthält. In diesem Sinne lässt eine vollständige Theorie keine Fragen der Form „gilt α oder \neg\alpha in der Theorie T?“ offen.

Charakterisierung

Folgende Aussagen über einer Theorie T\varsubsetneq L_I^S sind äquivalent[1]:

  • T ist vollständig, das heißt für alle Sätze α gilt T\vDash \alpha oder T\vDash \neg\alpha
  • T ist maximal, das heißt für alle Theorien T1 mit T\subset T_1 \varsubsetneq L_I^S gilt T = T1.
  • Für jedes Modell \mathcal{A} von T gilt T=Th(\mathcal{A})
  • Je zwei Modelle von T sind elementar äquivalent.

Beispiele

Es sei DO die Theorie der dichten Ordnungen, das heißt die Signatur ist S = { < } und DO ist die Menge aller Sätze aus L_I^S, die aus folgenden vier Sätzen (Axiomen der dichten Ordnung) hergeleitet werden können.

  • \forall x\,(x<x) (Irreflexivität)
  • \forall x\,y\,z\,(x<y \land y<z \rightarrow x<z) (Transitivität)
  • \forall x\,y\,(x=y \lor x<y \lor y<x) (Linearität der Ordnung)
  • \forall x\,y\,z\,(x<y \rightarrow \exists z\,(x<z \land z<y)) (Dichtheit)

Diese Theorie ist nicht vollständig, denn die Frage, ob es kleinste oder größte Elemente gibt, bleibt offen. Erweitert man DO zur Theorie DO00 aller Sätze, die aus obigen vier und den zwei Sätzen

  • \forall x\,\exists y\,(y<x) (es gibt kein kleinstes Element)
  • \forall x\,\exists y\,(x<y) (es gibt kein größtes Element),

so erhält man eine vollständige Theorie, denn mit Hilfe des Satzes von Fraïssé kann man die elementare Äquivalenz von je zwei Modellen nachweisen, wie dort ausgeführt ist. Dies hätte man auch leicht mit dem Kriterium von Vaught nachweisen können; dieses liefert weitere dort behandelte Beispiele wie die Theorie der algebraisch abgeschlossenen Körper. Die Quantorenelimination ist ein weiteres Verfahren, mit dem man Vollständigkeitsbeweise führen kann.

Entscheidbarkeit

Vollständige Theorien mit abzählbarer Signatur sind entscheidbar. Um dies einzusehen, setze man eine Aufzählung sämtlicher Sätze der vorgegebenen Theorie in Gang, indem man systematisch alle Beweise erzeugt. Ist α ein Satz, so erscheint in dieser Aufzählung irgendwann α oder \neg\alpha, denn die Theorie ist ja vollständig. Dann breche man die Aufzählung ab und antworte \alpha\in T, falls α in der Aufzählung erschienen ist, anderenfalls antworte man \alpha\notin T. Diese Algorithmus entscheidet offenbar die Frage, ob \alpha\in T.

Vollständigkeit von Sequenzenkalkülen

Umgangssprachlich ausgedrückt heißt ein formales System (ein Kalkül) semantisch vollständig, wenn jedes richtige Theorem auch abgeleitet werden kann. Präziser kann man das wie folgt beschreiben. Sei \vdash die Ableitungsrelation; sie wird rein syntaktisch mit Hilfe der Regeln des formalen Systems definiert, im Falle der Prädikatenlogik z.B. durch den Sequenzenkalkül. Hierbei handelt es sich um Regeln für die Zeichenmanipulation.

Dazu gibt es die Ebene der Semantik und des in diesen Bereich gehörenden Begriffs der logischen Folgerung, ausgedrückt durch das Symbol \models, das z.B. in der Semantik der Aussagenlogik oder der Semantik der Prädikatenlogik erklärt wird. Die formale Semantik ist Gegenstand der auf Alfred Tarski zurückgehenden Modelltheorie.

Von zentralem Interesse in der formalen Logik ist nun das Verhältnis zwischen (syntaktischer) Ableitung \vdash und (semantischer) Folgerung \models: Semantische Vollständigkeit bedeutet, dass aus \Sigma \models \psi stets \Sigma \vdash \psi folgt.

Die Umkehrung, dass also aus \Sigma \vdash \psi stets \Sigma \models \psi folgt, bezeichnet man als Korrektheit (auch semantische Korrektheit) eines formalen Systems.

Für konkrete formale Systeme ist die Korrektheit meist einfach zu beweisen, denn man achtet schon bei der Konstruktion des formalen Systems darauf, dass jede einzelne Regel in diesem Sinne korrekt ist. Ein Vollständigkeitsbeweis erfordert meist tiefliegendere Untersuchungen. Der Vollständigkeitssatz für die Prädikatenlogik erster Stufe wurde 1928 von Kurt Gödel bewiesen (Gödelscher Vollständigkeitssatz). Eine wichtige Beweismethode stammt von Leon Henkin aus dem Jahre 1949, siehe Satz von Henkin.

Funktionale Vollständigkeit von Junktorenmengen

Mit funktionaler Vollständigkeit bezeichnet man die Eigenschaft einer Menge von Junktoren eines logischen Systems, alle Junktoren des Systems darstellen zu können. In der klassischen Aussagenlogik ist zum Beispiel die Junktorenmenge \{\and, \neg\} funktional vollständig, d. h. es lassen sich alle denkbaren Junktoren alleine aus Konjunktion und Negation ausdrücken[2].

Ein weiteres vollständiges System von Junktoren besteht allein aus dem Shefferschen Strich.

Quellen

  • H.D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik. Mannheim-Leipzig-Wien-Zürich; BI-Wiss. Verlag, 1992, ISBN 3-411-15603-1
  • Hans-Peter Tuschik, Helmut Wolter: Mathematische Logik - kurzgefasst. Grundlagen, Modelltheorie, Entscheidbarkeit, Mengenlehre. Mannheim-Leipzig-Wien-Zürich; BI-Wiss. Verlag, 1994, ISBN 3-411-16731-9

Hinweise

  1. Wolfgang Rautenberg: Einführung in die Mathematische Logik. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2., Satz 5.2.1
  2. Wolfgang Rautenberg: Einführung in die mathematische Logik, Friedr. Vieweg & Sohn 2002, ISBN 3-528-16754-8, Kapitel 1, Korollar 2.2.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Vollständigkeit — (abgeleitet vom Ausdruck vollen Bestand haben) bezeichnet: allgemein die Eigenschaft einer Zusammenstellung oder Aufzählung, alle zu einer Gesamtheit gehörenden Bestandteile zu umfassen fachsprachlich eine mathematische Eigenschaft, siehe Glossar …   Deutsch Wikipedia

  • Logik — (von altgriechisch λογική τέχνη logiké téchnē „denkende Kunst“, „Vorgehensweise“) ist die Lehre des vernünftigen (Schluss)Folgerns. Die Logik untersucht die Gültigkeit von Argumenten hinsichtlich ihrer Struktur unabhängig vom konkreten Inhalt der …   Deutsch Wikipedia

  • Vollständigkeit — Vollzähligkeit; Lückenlosigkeit * * * Vọll|stän|dig|keit 〈f. 20; unz.〉 vollständige Beschaffenheit, Ganzheit, Beisammensein aller dazugehörenden Teile ● der Vollständigkeit halber nur um die Sache zu vervollständigen (nicht weil es unbedingt… …   Universal-Lexikon

  • Aristotelische Logik — Gregor Reisch, „Die Logik präsentiert ihre zentralen Themen“, Margarita Philosophica, 1503/08 (?). Die beiden Hunde veritas und falsitas jagen de …   Deutsch Wikipedia

  • Funktionale Vollständigkeit — Junktoren (von lat. iungere „verknüpfen, verbinden“) sind Verknüpfungen zwischen Aussagen innerhalb der Aussagenlogik, also logische Operatoren. Sie werden auch Konnektive, Konnektoren, Satzoperatoren, Satzverknüpfungen, Aussagenverknüpfer,… …   Deutsch Wikipedia

  • Geschichte der Logik — Die Geschichte der Logik behandelt die Logik als Ganzes in ihrer Entstehung und Entwicklung zur formalen Logik, wobei auch andere Entwicklungen berücksichtigt werden. Die europäisch westliche Logik hat ihren Anfang im antiken Griechenland.… …   Deutsch Wikipedia

  • Kombinatorische Logik — (Abgekürzt CL für engl. Combinatory Logic) ist eine Notation, die von Moses Schönfinkel und Haskell Brooks Curry eingeführt wurde, um die Verwendung von Variablen in der Mathematischen Logik zu vermeiden. Sie wird besonders in der Informatik als… …   Deutsch Wikipedia

  • Mathematische Logik — Die Mathematische Logik ist ein Teilgebiet der Mathematik. Oft wird sie in die Teilgebiete Modelltheorie, Beweistheorie, Mengenlehre und Rekursionstheorie aufgeteilt. Forschung im Bereich der mathematischen Logik hat zum Studium der Grundlagen… …   Deutsch Wikipedia

  • Intuitionismus (Logik und Mathematik) — Der Intuitionismus ist eine von L. E. J. Brouwer begründete Richtung der Philosophie der Mathematik, bei der die Mathematik als Tätigkeit des exakten Denkens angesehen wird, die ihre eigenen Objekte hervorbringt und nicht voraussetzt. Wahrheit… …   Deutsch Wikipedia

  • mathematische Logik — mathematische Logik,   im weiteren Sinn die formale Logik, wobei unterstellt wird, dass formales Operieren immer mathematischer Natur sei; im engeren Sinn diejenigen Teilgebiete der formalen Logik, die sich mit für die Mathematik methodologisch… …   Universal-Lexikon

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”