Section 3.2: Other Reducts of Number Theory

𝔑_L

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

Additional notation. $x\le y$ stands for $(x<y\vee x=y)$ .

Axiomatization

Consider the following set of axioms $A_{L}$ .

(S3) $\forall y(y\neq0\rightarrow\exists xy=\mathbb{S}x)$ .
(L1) $\forall x\forall y(x<\mathbb{S}y\leftrightarrow x\le y)$ .
(L2) $\forall xx\nless0$ .
(L3) $\forall x\forall y(x<y\vee x=y\vee y<x)$ .
(L4) $\forall x\forall y(x<y\rightarrow y\nless x)$ .
(L5) $\forall x\forall y\forall z(x<y\rightarrow y<z\rightarrow x<z)$ .

Clearly, $\mbox{Cn}A_{L}\subseteq\mbox{Th}\mathfrak{N}_{L}$ . Moreover, we will show that $\mbox{Cn}A_{L}$ is complete, therefore, $\mbox{Cn}A_{L}=\mbox{Th}\mathfrak{N}_{L}$ .

At the same time, we cannot proceed as with $A_{S}$ at this point, that is by showing that $\mbox{Th}\mathfrak{N}$ is categorical, because it is not categorical for any cardinal number. So, we will utilize the elimination of quantifiers property of $\mbox{Cn}A_{L}$ , see below. As we will see below, all axioms of $\mathfrak{N}_{S}$ are true in $\mbox{Cn}A_{L}$ , therefore, every model $\mathfrak{A}$ of $A_{L}$ consists of the standard part isomorphic to $\mathfrak{N}_{L}$ 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.$ However, unlike

, here all $Z$ -chains are ordered. Since for an infinite cardinality there are many non-isomorphic ways to order elements, for every cardinality there are non-isomorphic models of $\mathfrak{N}_{L}$ .

Consequences of the axioms

$A_{L}\vdash\forall xx<\mathbb{S}x$ .
$A_{L}\vdash\forall xx\nless x$ .
$A_{L}\vdash\forall x\forall y(x\nless y\leftrightarrow y\le x)$ (trichotomy).
$A_{L}\vdash\forall x\forall y(x<y\leftrightarrow\mathbb{S}x<\mathbb{S}y)$ .
$A_{L}\vdash S1$ and $A_{L}\vdash S2$ .
$A_{L}\vdash S4.n$ for $n=1,2,\ldots$ .

Elimination of quantifiers and decidability

$\mbox{Cn}A_{L}$ admits elimination of quantifiers.

$\mbox{Cn}A_{L}$ is complete. The completeness of $\mbox{Cn}A_{L}$ follows from the elimination of quantifiers property. Indeed, each atomic formula of a sentence is of the form $\mathbb{S}^{k}0=\mathbb{S}^{l}0$ or $\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.
$\mbox{Cn}A_{L}=\mbox{Th}\mathfrak{N}_{L}$ (Exercise 2 of Section 2.6).
$\mbox{Th}\mathfrak{N}_{L}$ is decidable (on the one hand, it is axiomatizable and complete, on the other hand, for each sentence, the quantifier elimination property yields a more direct procedure to check whether it is true in $\mbox{Th}\mathfrak{N}_{L}$ ).

Definability of subsets and relations

Any relation definable in $\mathfrak{N}_{L}$ is also definable by a quantifier-free formula.
- A subset of $\mathbb{N}$ is definable in $\mathfrak{N}_{L}$ iff either it is finite or its complement is finite. So, $\mathfrak{N}_{L}$ has the same definable subsets as $\mathfrak{N}_{S}$ does.
- $\mathfrak{N}_{L}$ has more definable relations (even binary) than $\mathfrak{N}_{S}$ does. For example, $m<n$ is definable in $\mathfrak{N}_{L}$ .
- The relation $m+n=p$ is not definable in $\mathfrak{N}_{L}$ .
Another example of a theory that admits elimination of quantifiers is $\mbox{Th}(\mathbb{R};<)$ .

𝔑_A

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

Axiomatization

The theory of $\mathfrak{N}_{A}$ is axiomatizable, however, the list of the axioms is rather long.

We can again argue that every model $\mathfrak{A}$ of $\mbox{Th}\mathfrak{N}_{A}$ consists of the standard part isomorphic to $\mathfrak{N}_{A}$ and non-standard part consisting of $Z$ -chains ordered by $<^{\mathfrak{A}}$ . However, unlike $\mathfrak{N}_{L}$ , the ordering of the $Z$ -chains is not arbitrary. In particular, there is no largest or smallest $Z$ -chain, and between any two $Z$ -chains there is another one.

In fact, $\mbox{Th}\mathfrak{N}_{A}$ is equal to $\mbox{Th}(\mathbb{N};+)$ , as in the latter we can define relations $\{0\}$ , $S$ and $<$ .

Elimination of quantifiers and decidability

$\mbox{Th}\mathfrak{N}_{A}$ , by itself, does not admit elimination of quantifiers. However, it can be amended to the expanded language including $\equiv_{n}$ for every $n\ge2$ , where $a\equiv_{n}b$ iff $a$ and $b$ are congruent modulo $n$ .

Let $\mathfrak{N}^{\equiv}=(\mathbb{N};0,S,<,+,\equiv_{2},\equiv_{3},\ldots)$ .

$\mbox{Th}\mathfrak{N}^{\equiv}$ admits elimination of quantifiers.
$\mbox{Th}\mathfrak{N}^{\equiv}$ , and, hence, $\mbox{Th}\mathfrak{N}_{A}$ is decidable.

Definability of subsets and relations

A set $D\subseteq\mathbb{N}$ is called periodic iff for some positive $p$ , $n\in D$ iff $n+p\in D$ . A set $D\subseteq\mathbb{N}$ is called eventually periodic iff for some positive $p$ and some $N\in\mathbb{N}$ , if $n\ge N$ , then $n\in D$ iff $n+p\in D$ .

A subset of $\mathbb{N}$ is definable in $\mathfrak{N}_{A}$ iff it is eventually periodic.

The relation $m\cdot n=p$ is not definable in $\mathfrak{N}_{A}$ .

Subpages

Section 3.2: Other Reducts of Number Theory

Section 3.2: Other Reducts of Number Theory

𝔑L

Axiomatization

Consequences of the axioms

Elimination of quantifiers and decidability

Definability of subsets and relations

𝔑A

Axiomatization

Elimination of quantifiers and decidability

Definability of subsets and relations

𝔑_L

𝔑_A