크레이그의 보간 정리

크레이그의 보간 정리(Craig's interpolation theorem, -補間 定理)는 증명 이론의 정리로, 미국의 철학자이자 논리학자인 윌리엄 크레이그가 제시하였다. 간단히 말해 다음과 같이 쓸 수 있다.

 어떤 논리식 a에서 다른 논리식 b를 추론할 수 있다고 하자. 그러면, c에서 나타나는 모든 비논리적 기호는 a와 b 각각에서도 나타나는 제3의 논리식 c가 존재하여 a에서 c를 추론할 수 있고, 다시 c에서 b를 추론할 수 있다. 이 c를 보간(interpolant)이라 한다.

크레이그는 1957년 이 정리를 일차 논리학에 대해 증명하였다. 미국 수학자 로저 린든이 일차 논리학에 대한 이 정리의 보다 강한 판본을 1959년 증명하였으므로 이 둘을 합쳐 크레이그-린든 정리라 부르기도 한다.

 사례 
명제 논리학에 대해 간단한 경우를 생각해 보자. 만약,

 φ = ~(P ∧ Q) → (~R ∧ Q)
 ψ = (T → P) ∨ (T → ~R).

라 한다면, φ는 ψ를 함의(동어반복적 함축)한다. 이는 φ를 논리곱 표준형으로 다음과 같이 쓰면 분명해진다.

 φ ≡ (P ∨ ~R) ∧ Q.

그런데 사실 (P ∨ ~R)에서도 ψ를 함의하게 된다. (P ∨ ~R)에 나타나는 명제 변수는 a와 b 각각에서도 나타나므로 (P ∨ ~R)는 하나의 보간이 된다.

 같이 보기 
 로빈슨의 정리
 시퀀트 계산
 온톨로지
 컷 제거 정리

 참고 문헌 
 John Harrison (2009). Handbook of Practical Logic and Automated Reasoning. Cambridge University Press. ISBN 0-521-89957-5.
 Hinman, P. (2005). Fundamentals of Mathematical Logic. A K Peters. ISBN 1-56881-262-0.
 Dov M. Gabbay and Larisa Maksimova (2006). Interpolation and Definability: Modal and Intuitionistic Logics (Oxford Logic Guides). Oxford science publications, Clarendon Press. ISBN 978-0-19-851174-8.
 Eva Hoogland, Definability and Interpolation. Model-theoretic investigations. PhD thesis, Amsterdam 2001.
 W. Craig, Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory, The Journal of Symbolic Logic 22 (1957), no. 3, 269–285.

분류:증명 이론
분류:수학기초론 정리
분류:보조정리