# Section 3.1: Problem 1 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
Let $A_{S}^{∗}$ be the set of sentences consisting of S1, S2, and all sentences of the form where $\phi$ is a wff (in the language of $\mathfrak{N}_{S}$ ) in which no variable except $v_{1}$ occurs free. Show that $A_{S}\subseteq\mbox{Cn}A_{S}^{∗}$ . Conclude that $\mbox{Cn}A_{S}^{∗}=\mbox{Th}\mathfrak{N}_{S}$ . (Here $\phi(t)$ is by definition $\phi_{t}^{v_{1}}$ . The sentence displayed above is called the induction axiom for $\phi$ .)
Axioms S1 and S2 of $A_{S}$ belong to $A_{S}^{*}$ . Axiom S3, $\forall y(y\neq0\rightarrow\exists xy=\mathbb{S}x)$ , can be derived as follows. Consider $\phi=v_{1}\neq0\rightarrow\exists xv_{1}=\mathbb{S}x$ . Then, $\phi(0)=0\neq0\rightarrow\exists x0=\mathbb{S}x$ is true as the left-hand side is false. Further, $\forall v_{1}(\phi(v_{1})\rightarrow\phi(\mathbb{S}v_{1}))=\forall v_{1}((v_{1}\neq0\rightarrow\exists xv_{1}=\mathbb{S}x)\rightarrow(\mathbb{S}v_{1}\neq0\rightarrow\exists x\mathbb{S}v_{1}=\mathbb{S}x))$ is true as the right-hand side is true. Therefore, using the induction axiom, we can deduce Axiom S3. Axiom S4, $\forall x\mathbb{S}^{n}x\neq x$ , can be derived similarly. Consider $\phi=\mathbb{S}^{n}v_{1}\neq v_{1}$ . Then, $\phi(0)=\mathbb{S}^{n}0\neq0$ is true due to Axiom S1, and $\forall v_{1}(\phi(v_{1})\rightarrow\phi(\mathbb{S}v_{1}))=\forall v_{1}(\mathbb{S}^{n}v_{1}\neq v_{1}\rightarrow\mathbb{S}^{n+1}v_{1}\neq\mathbb{S}v_{1})$ is true due to Axiom S2 (using deduction axiom group 2, contraposition, substitution and generalization). Therefore, using the induction axiom again, we can deduce Axiom S4. Overall, we conclude that every axiom S1-S4 is logically implied by $A_{S}^{*}$ , i.e. $A_{S}\subseteq\mbox{Cn}A_{S}^{∗}$ , and $\mbox{Cn}A_{S}\subseteq\mbox{Cn}A_{S}^{*}\subseteq\mbox{Th}\mathfrak{N}_{S}$ , whence the equality holds.