Vollständigkeit (Logik) - LinkFang.de





Vollständigkeit (Logik)


Der Begriff Vollständigkeit hat in der Logik verschiedene Bedeutungen. Er bezeichnet zwei unterschiedliche Eigenschaften formaler Systeme bzw. Kalküle:

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

Daneben wird dieser Begriff auch im Sinne der

  • funktionalen Vollständigkeit von Junktorenmengen

benutzt.

Vollständigkeit von Theorien

Definition

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

Charakterisierung

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

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

Beispiele

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

  • [math]\forall x\,\neg(x\ltx)[/math] (Irreflexivität)
  • [math]\forall x\,y\,z\,(x\lty \land y\ltz \rightarrow x\ltz)[/math] (Transitivität)
  • [math]\forall x\,y\,(x=y \lor x\lty \lor y\ltx)[/math] (Linearität der Ordnung)
  • [math]\forall x\,y\,(x\lty \rightarrow \exists z\,(x\ltz \land z\lty))[/math] (Dichtheit)

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

  • [math]\forall x\,\exists y\,(y\ltx)[/math] (es gibt kein kleinstes Element)
  • [math]\forall x\,\exists y\,(x\lty)[/math] (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 und einer rekursiv aufzählbaren Axiomatisierung 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 [math]\alpha[/math] ein Satz, so erscheint in dieser Aufzählung irgendwann [math]\alpha[/math] oder [math]\neg\alpha[/math], denn die Theorie ist ja vollständig. Dann breche man die Aufzählung ab und antworte [math]\alpha\in T[/math], falls [math]\alpha[/math] in der Aufzählung erschienen ist, anderenfalls antworte man [math]\alpha\notin T[/math]. Dieser Algorithmus entscheidet offenbar die Frage, ob [math]\alpha\in T[/math].

Vollständigkeit von Kalkü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 [math]\vdash[/math] 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 der semantischen Folge [math]\models[/math], 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 [math]\vdash[/math] und (semantischer) Folgerung [math]\models[/math]: Semantische Vollständigkeit bedeutet, dass aus [math]\Sigma \models \psi[/math] stets [math]\Sigma \vdash \psi[/math] folgt.

Die Umkehrung, dass also aus [math]\Sigma \vdash \psi[/math] stets [math]\Sigma \models \psi[/math] 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.

Ein Kalkül heißt syntaktisch vollständig (Post-vollständig), wenn für eine beliebige Aussage [math] \hat{\alpha} [/math], die nicht im Kalkül beweisbar ist, die Hinzunahme dieser zum Kalkül (als Axiom), ihn explodieren lässt, d. h. alles in ihm beweisbar wird: Also aus [math]\nvdash\hat{\alpha} [/math] folgt unmittelbar [math] \vdash_\hat{\alpha} \alpha [/math] für jeden beliebigen Ausdruck [math]\alpha [/math] der behandelten Sprache.

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 [math]\{\and, \neg\}[/math] 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. Auch das aus einzig dem Junktor Peirce-Operator bestehende System ist vollständig.

Quellen

Hinweise

  1. W. Rautenberg (2008), Satz 5.2.1.
  2. W. Rautenberg (2008), Korollar 1.2.2.

Kategorien: Keine Kategorien vorhanden!

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Vollständigkeit (Logik) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.