# Section 3.1: Problem 4 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
Show that a subset of $\mathbb{N}$ is definable in $\mathfrak{N}_{S}$ iff either it is finite or its complement (in $\mathbb{N}$ ) is finite.
As suggested on page 192, we use the fact that a subset $A$ is definable in $\mathfrak{N}_{S}$ iff there is a quantifier-free formula $\phi$ that defines it. In fact, $\phi$ can be further assumed to be in its disjunctive normal form. Each atomic formula is of the form $\mathbb{S}^{m}t=\mathbb{S}^{n}u$ , where $t$ and $u$ are either $v_{1}$ or $0$ . If $t=u$ , then, if $m=n$ , the atomic formula is always satisfied, otherwise, using axioms S2 and S4, the atomic formula is never satisfied. Thus, if $t=u$ , the atomic formula defines either $\emptyset$ or $\mathbb{N}$ . If $t\neq u$ , then, without loss of generality, it is $\mathbb{S}^{m}v_{1}=\mathbb{S}^{n}0$ . If $m>n$ , then, using axioms S2 and S1, we conclude that the atomic formula is never satisfied. If $m\le n$ , then, using axiom S2, $A_{S}\vDash\mathbb{S}^{m}v_{1}=\mathbb{S}^{n}0\leftrightarrow v_{1}=\mathbb{S}^{n-m}0$ . In the first case, the atomic formula defines the empty set, and in the second case, the atomic formula defines a singleton. Overall, an atomic formula can define a subset containing 0, 1 or all points only (and every such subset can be defined in the standard model of $\mathfrak{N}_{S}$ , using the fact that for every $n\in\mathbb{N}$ , $\{n\}$ is defined by $v_{1}=\mathbb{S}^{n}0$ ). Therefore, the negation of an atomic formula can define any subset containing 0, all or all but one points and only such subsets of . Each component of $\phi$ (the conjunction of atomic formulas or their negations) defines the intersection of the subsets defined by the atomic formulas or their negations, i.e. a subset containing 0, 1, all or all but a finite number of points (and any such subset can be defined). Now, $\phi$ , as the disjunction of its components, defines a subset that is the union of the subsets defined by the components, i.e. a subset containing a finite number of points or all points but a finite number of them, and any such subset can be defined by a formula.