Section 3.2: Problem 1 Solution »

# 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 .

### Axiomatization

Consider the following set of axioms $A_{L}$ .
1. (S3) $\forall y(y\neq0\rightarrow\exists xy=\mathbb{S}x)$ .
2. (L1) $\forall x\forall y(x<\mathbb{S}y\leftrightarrow x\le y)$ .
3. (L2) $\forall xx\nless0$ .
4. (L3) $\forall x\forall y(x .
5. (L4) $\forall x\forall y(x .
6. (L5) $\forall x\forall y\forall z(x .
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 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

1. $A_{L}\vdash\forall xx<\mathbb{S}x$ .
2. $A_{L}\vdash\forall xx\nless x$ .
3. $A_{L}\vdash\forall x\forall y(x\nless y\leftrightarrow y\le x)$ (trichotomy).
4. $A_{L}\vdash\forall x\forall y(x .
5. $A_{L}\vdash S1$ and $A_{L}\vdash S2$ .
6. $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 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}$ .