Section 1.5: Problem 11 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

(Interpolation theorem) If $\alpha\vDash\beta$ , then there is some $\gamma$ all of whose sentence symbols occur both in $\alpha$ and in $\beta$ and such that $\alpha\vDash\gamma\vDash\beta$ . Suggestion: Use the preceding exercise.

Remarks: There is an analogue of Exercise 11 that holds for first-order logic. But the proof in that case is very different, because there is no analogue of Exercise 10.

Consider all sentence symbols $A_{i_{1}},\ldots A_{i_{m}}$ that are used in $\alpha$ but not used in $\beta$ . Define $\alpha_{0}=\alpha$ , and $\alpha_{k}=(\alpha_{k-1})_{*}^{A_{i_{k}}}$ , $k=1,\ldots,m$ . Then, according to Exercise 10, $\alpha=\alpha_{0}\vDash\alpha_{1}\vDash\ldots\vDash\alpha_{m}$ , and since no sentence symbol $A_{i_{k}}$ is used in $\beta$ , $\alpha_{k-1}\vDash\beta$ implies $\alpha_{k}\vDash\beta$ . Therefore, $\gamma=\alpha_{m}\vDash\beta$ and $\gamma$ uses only those sentence symbols in $\alpha$ that are also in $\beta$ .

There might still be some sentence symbols in $\beta$ that are not in $\alpha$ , and, hence, not in $\gamma$ , but we don’t care. For example, $A\wedge B\vDash C\rightarrow B$ , therefore, $A\wedge B\vDash B\vDash C\rightarrow B$ , where $B$ is tautologically equivalent to $\gamma$ constructed.

Subpages

Section 1.5: Problem 11 Solution

Section 1.5: Problem 11 Solution