imported>R.Tm01: /* Literatur */ Z. nochmal

2025-10-26T20:54:58Z

Literatur: Z. nochmal

Neue Seite

Die '''Craig-Interpolation''' ist ein Ausdruck der [[Logik]]. Der zugrunde liegende Satz (''Craig’s Lemma'', ''Interpolationstheorem'') lautet folgendermaßen:

Es seien <math> T1</math> und <math> T2</math> zwei Theorien und der Satz <math> A \rightarrow C </math> sei ein in <math> T1 \cup T2 </math> ableitbarer Satz. Dann gilt: Es gibt ein <math> B</math>, sodass <math> A \rightarrow B </math> in <math> T1 </math> ableitbar ist, und <math> B \rightarrow C</math> ist in <math> T2 </math> ableitbar.

== Das Interpolationstheorem ==
Dieses Interpolationstheorem wurde zuerst von dem US-amerikanischen Logiker [[William Craig (Logiker)|William Craig]] (1918–2016) 1953 aufgestellt. Es wurde von S. Maehara und von [[Kurt Schütte]] (für [[Intuitionismus|intuitionistische]] Kalküle) bewiesen und hat zahlreiche Anwendungen in der [[Beweistheorie|Beweis-]] und [[Modelltheorie]].

== Algorithmus zur Bestimmung der Craig-Interpolante für die Aussagenlogik ==
Voraussetzung: Die Formel <math> A \rightarrow C</math> sei in einem korrekten Kalkül ableitbar, also tautologisch, oder, äquivalent, <math>A \models C</math>.

# Suche alle [[Elementarsatz|Atome]], die in <math>A</math>, aber nicht in <math>C</math> enthalten sind.
# Für jedes dieser Atome <math>p</math> ''ver-odere'' (Verknüpfung mit [[Disjunktion|oder]]) <math>A</math> mit sich selbst, wobei in jeder der beiden Kopien von <math>A</math> das Atom <math>p</math> einmal durch <math>\bot</math> und einmal durch <math>\top</math> ersetzt wird.
# Die resultierende Formel ist die Craig-Interpolante <math>B</math>.

Bei jedem Schritt wird eines der Atome, die nur in <math>A</math> vorkommen, eliminiert. Man beachte, dass die Formel dabei exponentiell wächst – beim Bearbeiten jedes einzelnen Atoms verdoppelt sich die Größe.

== Literatur ==
* [[William Craig]], ''On Axiomatizability Within a System''. In: ''The Journal of Symbolic Logic''. Vol. 8 (1), March 1953: 30–32.
* [[Kurt Schütte]]: ''Proof Theory.'' Springer, Berlin u. a. 1977, ISBN 3-540-07911-4 (''Grundlehren der mathematischen Wissenschaften'' 225).
* [[Joseph R. Shoenfield]]: ''Mathematical Logic.'' Addison-Wesley, Reading MA u. a. 1967, ISBN 0-201-07028-6 (''Addison-Wesley Series in Logic'').
* [[Christian Thiel]] / [[Gereon Wolters (Philosoph)|Gereon Wolters]]: ''Craig's Lemma.'' in: Jürgen Mittelstraß: ''Enzyklopädie Philosophie und Wissenschaftstheorie.'' Zweite Auflage. Band 2, Metzler 2005.

[[Kategorie:Mathematische Logik]]
[[Kategorie:Satz (Mathematik)]]
[[Kategorie:Berechenbarkeitstheorie]]

Craig-Interpolation - Versionsgeschichte

imported>R.Tm01: /* Literatur */ Z. nochmal