Section 3.1: Problem 1 Solution »

# Section 3.1: Natural Numbers with Successor

Consider $\mathfrak{N}_{S}=(\mathbb{N};0,S)$ .

## Axiomatization

Let $A_{S}$ be the set of the following axioms S1-S4.
1. $\forall x\mathbb{S}x\neq0$ .
2. $\forall x\forall y(\mathbb{S}x=\mathbb{S}y\rightarrow x=y)$ .
3. $\forall y(y\neq0\rightarrow\exists xy=\mathbb{S}x)$ .
4. For every $n\in\mathbb{N}$ , $n\ge1$ , $\forall x\mathbb{S}^{n}x\neq x$ .
• Alternatively, instead of S3 and S4, we could use the induction axiom $\phi(0)\rightarrow\forall v_{1}(\phi(v_{1})\rightarrow\phi(\mathbb{S}v_{1}))\rightarrow\forall v_{1}\phi(v_{1})$ for every $\phi$ , a wff (in the language of $\mathfrak{N}_{S}$ ) in which no variable except $v_{1}$ occurs free.
• $\mbox{Th}\mathfrak{N}_{S}$ is not finitely axiomatizable.
Clearly, $\mbox{Cn}A_{S}\subseteq\mbox{Th}\mathfrak{N}_{S}$ . Moreover, every model $\mathfrak{A}$ of $A_{S}$ consists of the standard part isomorphic to $\mathfrak{N}_{S}$ and non-standard part consisting of $Z$ -chains of the form
If models $\mathfrak{A}$ and $\mathfrak{B}$ of $A_{S}$ have the same number of $Z$ -chains, then they are isomorphic.
• Uncountable models $\mathfrak{A}$ and $\mathfrak{B}$ of $A_{S}$ are isomorphic iff they are of the same cardinality.
• Therefore, $\mbox{Th}\mathfrak{N}_{S}$ is categorical in every uncountable cardinality.
• $\mbox{Cn}A_{S}$ is complete (Łoś–Vaught test).
• $\mbox{Cn}A_{S}=\mbox{Th}\mathfrak{N}_{S}$ (Exercise 2 of Section 2.6).
• $\mbox{Th}\mathfrak{N}_{S}$ is decidable (axiomatizable and complete).

## Elimination of Quantifiers

A theory $T$ admits elimination of quantifiers iff for every wff $\phi$ there is a quantifier-free wff $\psi$ such that $T\vDash\phi\leftrightarrow\psi$ .
• In fact, to show that $T$ admits elimination of quantifiers, it is enough to show that $T$ admits elimination of quantifiers for every wff $\phi$ of the form $\exists x(\alpha_{0}\wedge\ldots\wedge\alpha_{n})$ where $\alpha_{i}$ is atomic or the negation of an atomic formula.
$\mbox{Th}\mathfrak{N}_{S}$ admits elimination of quantifiers.
• The completeness of $\mbox{Cn}A_{S}$ follows from the elimination of quantifiers property as well. Indeed, each atomic formula of a sentence is of the form $\mathbb{S}^{k}0=\mathbb{S}^{l}0$ which is either deducible or refutable from the axioms, and so is the quantifier-free sentence logically equivalent to a given sentence.
• Any relation definable in $\mathfrak{N}_{S}$ is also definable by a quantifier-free formula.
• A subset of $\mathbb{N}$ is definable in $\mathfrak{N}_{S}$ iff either it is finite or its complement is finite.
• The relation $m is not definable in $\mathfrak{N}_{S}$ .
• Another example of a theory that admits elimination of quantifiers is $\mbox{Th}(\mathbb{Q};<)$ .