Section 3.2: Other Reducts of Number Theory
𝔑_{L}
Consider
.
Additional notation.
stands for
.
Axiomatization
Consider the following set of axioms
.
 (S3) .
 (L1) .
 (L2) .
 (L3) .
 (L4) .
 (L5) .
Clearly,
. Moreover, we will show that
is complete, therefore,
.
At the same time, we cannot proceed as with
at this point, that is by showing that
is categorical, because it is not categorical for any cardinal number. So, we will utilize the elimination of quantifiers property of
, see below. As we will see below, all axioms of
are true in
, therefore, every model
of
consists of the standard part isomorphic to
and nonstandard part consisting of
chains of the form
However, unlike
, here all
chains are ordered. Since for an infinite cardinality there are many nonisomorphic ways to order elements, for every cardinality there are nonisomorphic models of
.
Consequences of the axioms
 .
 .
 (trichotomy).
 .
 and .
 for .
Elimination of quantifiers and decidability
admits elimination of quantifiers.
 is complete. The completeness of follows from the elimination of quantifiers property. Indeed, each atomic formula of a sentence is of the form or which is either deducible or refutable from the axioms, and so is the quantifierfree sentence logically equivalent to a given sentence.
 (Exercise 2 of Section 2.6).
 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 ).
Definability of subsets and relations

Any relation definable in
is also definable by a quantifierfree formula.
 A subset of is definable in iff either it is finite or its complement is finite. So, has the same definable subsets as does.
 has more definable relations (even binary) than does. For example, is definable in .
 The relation is not definable in .
 Another example of a theory that admits elimination of quantifiers is .
𝔑_{A}
Consider
.
Axiomatization
The theory of
is axiomatizable, however, the list of the axioms is rather long.
We can again argue that every model
of
consists of the standard part isomorphic to
and nonstandard part consisting of
chains ordered by
. However, unlike
, the ordering of the
chains is not arbitrary. In particular, there is no largest or smallest
chain, and between any two
chains there is another one.
 In fact, is equal to , as in the latter we can define relations , and .
Elimination of quantifiers and decidability
, by itself, does not admit elimination of quantifiers. However, it can be amended to the expanded language including
for every
, where
iff
and
are congruent modulo
.
Let
.
 admits elimination of quantifiers.
 , and, hence, is decidable.
Definability of subsets and relations
A set
is called periodic iff for some positive
,
iff
. A set
is called eventually periodic iff for some positive
and some
, if
, then
iff
.
A subset of
is definable in
iff it is eventually periodic.
 The relation is not definable in .