Craig-Interpolation

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

Es seien  T 1 {\displaystyle T1} und  T 2 {\displaystyle T2} zwei Theorien und der Satz  A → C {\displaystyle A\rightarrow C} sei ein in  T 1 ∪ T 2 {\displaystyle T1\cup T2} ableitbarer Satz. Dann gilt: Es gibt ein  B {\displaystyle B} , sodass  A → B {\displaystyle A\rightarrow B} in  T 1 {\displaystyle T1} ableitbar ist, und  B → C {\displaystyle B\rightarrow C} ist in  T 2 {\displaystyle T2} ableitbar.

## Das Interpolationstheorem

[Bearbeiten | Quelltext bearbeiten]

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

## Algorithmus zur Bestimmung der Craig-Interpolante für die Aussagenlogik

[Bearbeiten | Quelltext bearbeiten]

Voraussetzung: Die Formel  A → C {\displaystyle A\rightarrow C} sei in einem korrekten Kalkül ableitbar, also tautologisch, oder, äquivalent,  A ⊨ C {\displaystyle A\models C} .

1. Suche alle Atome, die in  A {\displaystyle A} , aber nicht in  C {\displaystyle C} enthalten sind.
2. Für jedes dieser Atome  p {\displaystyle p} ver-odere (Verknüpfung mit oder)  A {\displaystyle A} mit sich selbst, wobei in jeder der beiden Kopien von  A {\displaystyle A} das Atom  p {\displaystyle p} einmal durch  ⊥ {\displaystyle \bot } und einmal durch  ⊤ {\displaystyle \top } ersetzt wird.
3. Die resultierende Formel ist die Craig-Interpolante  B {\displaystyle B} .

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

## Literatur

[Bearbeiten | Quelltext bearbeiten]

* 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: Craig's Lemma. in: Jürgen Mittelstraß: Enzyklopädie Philosophie und Wissenschaftstheorie. Zweite Auflage. Band 2, Metzler 2005.