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.

$\forall x\mathbb{S}x\neq0$ .
$\forall x\forall y(\mathbb{S}x=\mathbb{S}y\rightarrow x=y)$ .
$\forall y(y\neq0\rightarrow\exists xy=\mathbb{S}x)$ .
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 $\cdots\overset{\mathbb{S}}{\longrightarrow}\bullet\overset{\mathbb{S}}{\longrightarrow}\bullet\overset{\mathbb{S}}{\longrightarrow}a\overset{\mathbb{S}}{\longrightarrow}\mathbb{S}^{\mathfrak{A}}(a)\overset{\mathbb{S}}{\longrightarrow}\mathbb{S}^{\mathfrak{A}}(\mathbb{S}^{\mathfrak{A}}(a))\overset{\mathbb{S}}{\longrightarrow}\cdots.$

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<n$ is not definable in $\mathfrak{N}_{S}$ .
Another example of a theory that admits elimination of quantifiers is $\mbox{Th}(\mathbb{Q};<)$ .

Subpages

Section 3.1: Natural Numbers with Successor

Section 3.1: Natural Numbers with Successor

Axiomatization

Elimination of Quantifiers