# Section 3.3: Problem 3 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
A theory $T$ (in a language with $0$ and $\mathbb{S}$ ) is called $\omega$ -complete iff for any formula $\phi$ and variable $x$ , if $\phi_{\mathbb{S}^{n}0}^{x}$ belongs to $T$ for every natural number $n$ , then $\forall x\phi$ belongs to $T$ . Show that if $T$ is a consistent $\omega$ -complete theory in the language of $\mathfrak{N}$ and if $A_{E}\subseteq T$ , then $T=\mbox{Th}\mathfrak{N}$ .
Let $\sigma$ be a sentence (in the language of $\mathfrak{N}$ ) in the prenex normal form (Section 2.6). We use induction on the number of quantifiers in $\sigma$ to show that $T\vDash\sigma$ iff $\sigma$ is true in $\mathfrak{A}$ . We already know by the preceding exercise that for every quantifier-free sentence $\sigma$ , if $\sigma$ is true in $\mathfrak{A}$ , then $A_{E}\vdash\sigma$ , hence, $T\vDash\sigma$ , and if $\sigma$ is false in $\mathfrak{A}$ , then $A_{E}\vdash\neg\sigma$ , hence, $T\vDash\neg\sigma$ . If $\sigma=\forall x\phi$ is true in $\mathfrak{N}$ , where $x$ is the only free variable in $\phi$ , then for all $n\in\mathbb{N}$ , $\vDash_{\mathfrak{A}}\phi[s(x|n)]$ , and, by hypothesis, $T\vDash\phi_{\mathbb{S}^{n}0}^{x}$ , but then, since $T$ is $\omega$ -complete, . If $\sigma=\exists x\phi$ is true in $\mathfrak{N}$ , then for some $n\in\mathbb{N}$ , $\vDash_{\mathfrak{A}}\phi[s(x|n)]$ , and, by hypothesis, $T\vDash\phi_{\mathbb{S}^{n}0}^{x}$ , but then $T\vDash\exists x\phi=\sigma$ . Now, if $\sigma=\forall x\phi$ or $\sigma=\exists x\phi$ is false in $\mathfrak{A}$ , then $\neg\sigma$ (which is logically equivalent to $\exists x\neg\phi$ or $\forall x\neg\phi$ , respectively) is true in $\mathfrak{A}$ , and, hence, $T\vDash\neg\sigma$ . Therefore, by induction, we conclude that $T\vDash\sigma$ ($\sigma\in T$ ) iff $\sigma$ is true in $\mathfrak{A}$ ($\sigma\in\mbox{Th}\mathfrak{N}$ ) (here, we use the fact the $T$ is consistent).
Note. $\mbox{Cn}A_{E}$ is not $\omega$ -complete. For example, if $\phi=(y\neq0\rightarrow\exists xy=\mathbb{S}x)$ , then $A_{E}\vdash\phi_{\mathbb{S}^{n}0}^{y}$ for every $n\in\mathbb{N}$ , however, $A_{E}\nvdash\forall y(y\neq0\rightarrow\exists xy=\mathbb{S}x)$ , which is axiom S3 of $A_{S}$ .