Section 2.5: Problem 9 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

In Section 2.4 we used a certain set $\Lambda$ of logical axioms. That set can be altered, within limits.

(a) Suppose we add to $\Lambda$ some formula $\psi$ that is not valid. Show that the soundness theorem now fails.

(b) At the other extreme, suppose we take no logical axioms at all: $\Lambda=\emptyset$ . Show that the completeness theorem now fails.

(c) Suppose we modify $\Lambda$ by adding one new valid formula. Explain why both the soundness theorem and the completeness theorem still hold.

(a) In this case, for example, we can prove $\vdash\psi$ , which does not imply $\vDash\psi$ . Or, for any structure $\mathfrak{A}$ and $s:V\rightarrow|\mathfrak{A}|$ such that $\not\vDash_{\mathfrak{A}}\psi[s]$ and $\vDash_{\mathfrak{A}}\Gamma[s]$ for some $\Gamma$ , $\Gamma\vdash\psi$ , but $\Gamma\not\vDash\psi$ .

(b) In this case, if $\Gamma=\emptyset$ , then $\Gamma$ cannot prove anything, yet there are valid formulas for which $\emptyset\vDash\phi$ but $\emptyset\not\vdash\phi$ .

(c) The completeness theorem holds just because we can use the same deduction that is constructed without the new formula. The soundness theorem holds because in its proof by induction the validity of every logical axiom still holds (the only property of logical axioms used in the proof).

Subpages

Section 2.5: Problem 9 Solution

Section 2.5: Problem 9 Solution