Book contents
- Frontmatter
- Contents
- Preface to the Fifth Edition
- COMPUTABILITY THEORY
- BASIC METALOGIC
- FURTHER TOPICS
- 19 Normal Forms
- 20 The Craig Interpolation Theorem
- 21 Monadic and Dyadic Logic
- 22 Second-Order Logic
- 23 Arithmetical Definability
- 24 Decidability of Arithmetic without Multiplication
- 25 Nonstandard Models
- 26 Ramsey's Theorem
- 27 Modal Logic and Provability
- Annotated Bibliography
- Index
20 - The Craig Interpolation Theorem
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface to the Fifth Edition
- COMPUTABILITY THEORY
- BASIC METALOGIC
- FURTHER TOPICS
- 19 Normal Forms
- 20 The Craig Interpolation Theorem
- 21 Monadic and Dyadic Logic
- 22 Second-Order Logic
- 23 Arithmetical Definability
- 24 Decidability of Arithmetic without Multiplication
- 25 Nonstandard Models
- 26 Ramsey's Theorem
- 27 Modal Logic and Provability
- Annotated Bibliography
- Index
Summary
Suppose that a sentence A implies a sentence C. The Craig interpolation theorem tells us that in that case there is a sentence B such that A implies B, B implies C, and B involves no nonlogical symbols but such as occur both in A and in B. This is one of the basic results of the theory of models, almost on a par with, say, the compactness theorem. The proof is presented in section 20.1. The proof for the special case where identity and function symbols are absent is an easy further application of the same lemmas that we have applied to prove the compactness theorem in Chapter 13, and could have been presented there. But the easiest proof for the general case is by reduction to this special case, using the machinery for the elimination of function symbols and identity developed in section 19.4. Sections 20.2 and 20.3, which are independent of each other, take up two significant corollaries of the interpolation theorem, Robinson's joint consistency theorem and Beth's definability theorem.
Craig's Theorem and Its Proof
We begin with a simple observation.
Proposition. If a sentence A implies a sentence C, then there is a sentence B that A implies, that implies C, and that contains only such constants as are contained in both of A and C.
- Type
- Chapter
- Information
- Computability and Logic , pp. 260 - 269Publisher: Cambridge University PressPrint publication year: 2007