Satz von Henkin

Satz von Henkin

Der Satz von Henkin, benannt nach Leon Henkin, ist ein Satz aus der mathematischen Logik. Er beschäftigt sich mit der Frage, wann die Terminterpretation zu einer vorgegebenen Menge von Ausdrücken einer Prädikatenlogik erster Stufe ein Modell dieser Menge ist. Dieser Satz führt sowohl zu einem alternativen Beweis des Gödelschen Vollständigkeitssatzes als auch zu einem Beweis des Satzes von Löwenheim-Skolem.

Es sei Φ eine vorgegebene Menge von Ausdrücken einer Sprache L_I^S erster Stufe. Ist Φ widerspruchsfrei, das heißt, lässt sich kein Ausdruck der Form \varphi\land\neg\varphi daraus ableiten, so sichert der Gödelsche Vollständigkeitssatz die Existenz eines Modells. Auf Leon Henkin geht die Idee zurück, zur Konstruktion die Terminterpretation {\mathcal T}^\Phi heranzuziehen. Dazu ist zunächst zu klären, unter welchen Voraussetzungen die Terminterpretation ein Modell für die Ausdrucksmenge Φ ist. Zum Satz von Henkin, der genau diese Frage zum Gegenstand hat, sind zwei Definitionen erforderlich.

Eine Ausdrucksmenge Φ heißt negationstreu, wenn für jeden Ausdruck φ gilt, dass \Phi \vdash \varphi oder \Phi \vdash \neg\varphi, das heißt, ist ein Ausdruck nicht aus Φ ableitbar, so ist dessen Negation ableitbar.

Eine Ausdrucksmenge Φ hat Beispiele, wenn zu jedem Ausdruck der Form \exists x \varphi ein Term t der Sprache existiert, so dass (\exists x \varphi \rightarrow \varphi\frac{t}{x}) aus Φ ableitbar ist. Dabei steht \varphi\frac{t}{x} für denjenigen Ausdruck, der aus φ entsteht, wenn man die Variable x durch den Term t ersetzt. Die Ausdrucksmenge kann also zu jeder Existenzbehauptung ein Beispiel vorweisen.

  • Satz von Henkin: Ist Φ eine Ausdrucksmenge, die widerspruchsfrei und negationstreu ist und Beispiele enthält, so gilt für jeden Ausdruck φ:
{\mathcal T}^\Phi \vDash \varphi \quad \Leftrightarrow \quad \Phi \vdash \varphi.

Dabei bedeutet {\mathcal T}^\Phi \vDash \varphi, dass {\mathcal T}^\Phi ein Modell für φ ist. Insbesondere ist also die Terminterpretation zu Φ auch ein Modell von Φ, das heißt, es gilt {\mathcal T}^\Phi \vDash \Phi.

Widerspruchsfreie Mengen sind in der Regel weder negationstreu noch enthalten sie Beispiele. Um den Satz von Henkin zum Beweis der Existenz eines Modells in Anwendung zu bringen, muss man die Ausdrucksmenge Φ und die Symbolmenge S so erweitern, dass die Voraussetzungen für diese erweiterte Situation erfüllt sind. Das ist Henkins Beweis des Vollständigkeitssatzes. Ist die Symbolmenge von Anfang an höchstens abzählbar, so ist auch die erweiterte Symbolmenge höchstens abzählbar. Da dann auch die Menge der Terme höchstens abzählbar ist, stellt die Terminterpretation nach dem Satz von Henkin ein höchstens abzählbares Modell dar und man erhält leicht den Satz von Löwenheim-Skolem.

Literatur

  • H.-D. Ebbinghaus, J. Flum, W. Thomas: Einführung in die mathematische Logik, Spektrum Akademischer Verlag, ISBN, 3-8274-0130-5, insbesondere Kapitel V, §1.

Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

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

  • Henkin — ist der Name folgender Personen: Joseph Eliahu Henkin (1891–1973), orthodoxer Rabbiner Leon Henkin (1921–2006), US amerikanischer Logiker Siehe auch: Satz von Henkin, Satz aus der mathematischen Logik …   Deutsch Wikipedia

  • Leon Henkin — Leon Albert Henkin (* 19. April 1921 in Brooklyn; † 1. November 2006) war ein US amerikanischer Logiker. Leben und Wirken Henkin war der Sohn russisch jüdischer Einwanderer und studierte am Columbia College der Columbia University Mathematik und… …   Deutsch Wikipedia

  • 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 …   Deutsch Wikipedia

  • Gödel'scher Vollständigkeitssatz — Der Gödelsche Vollständigkeitssatz (benannt nach Kurt Gödel) ist der Hauptsatz der mathematischen Logik. Er zeigt für ein formales System der Prädikatenlogik erster Stufe die Korrektheit und Vollständigkeit: Jeder Satz, der semantisch aus einer… …   Deutsch Wikipedia

  • Gödelscher Vollständigkeitssatz — Der Gödelsche Vollständigkeitssatz (benannt nach Kurt Gödel) ist der Hauptsatz der mathematischen Logik. Er zeigt für ein formales System der Prädikatenlogik erster Stufe die Korrektheit und Vollständigkeit: Jeder Satz, der semantisch aus einer… …   Deutsch Wikipedia

  • Vollständigkeitsproblem — Der Gödelsche Vollständigkeitssatz (benannt nach Kurt Gödel) ist der Hauptsatz der mathematischen Logik. Er zeigt für ein formales System der Prädikatenlogik erster Stufe die Korrektheit und Vollständigkeit: Jeder Satz, der semantisch aus einer… …   Deutsch Wikipedia

  • Vollständigkeitssatz — Der Gödelsche Vollständigkeitssatz (benannt nach Kurt Gödel) ist der Hauptsatz der mathematischen Logik. Er zeigt für ein formales System der Prädikatenlogik erster Stufe die Korrektheit und Vollständigkeit: Jeder Satz, der semantisch aus einer… …   Deutsch Wikipedia

  • 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… …   Deutsch Wikipedia

  • Liste mathematischer Sätze — Inhaltsverzeichnis A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A Satz von Abel Ruffini: eine allgemeine Polynomgleichung vom …   Deutsch Wikipedia

  • Negationstreu — (engl.: negation complete) ist eine Eigenschaft von Folgen Φ von prädikatenlogischen Ausdrücken. Diese Eigenschaft wird in Verwechslungsgefahr zu andersgemeinten Begriffen der Vollständigkeit auch syntaktisch vollständig (in der… …   Deutsch Wikipedia

Share the article and excerpts

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