# Section 3.1: Problem 6 Solution

Working problems is a crucial part of learning mathematics. No one can learn... merely by poring over the definitions, theorems, and examples that are worked out in the text. One must work part of it out for oneself. To provide that opportunity is the purpose of the exercises.

James R. Munkres

Show that
is not finitely axiomatizable.

*Suggestion*: Show that no finite subset of suffices, and then apply Section 2.6.
According to Theorem 26H, if
were finitely axiomatizable, there would be a finite subset
of
such that
. We show that this is not the case.

If a finite
, then
, and we need to show that
. That is, there is a sentence
true in
that is not true in
. At the same time, every model of
is a model of
, and every sentence true in
will be true in such a model. Therefore, we need to find a model of
that is not a model of
, and a sentence
true in
that is not true in this particular model of
.

Let us call each axioms S1-S4 as
,
,
and
for
. Let
,
. Then, for a finite
, there is some
such that
, and
. If we show that for every
,
, then we will show the strict inclusion for every finite
.

For
, as the sentence that is true in
but not in
, consider
. Then, obviously,
is true in
. We need to provide a model of
such that
is not true in the model. The axioms of group 4 ensure that there is no loop of any finite length. In
we excluded all such axioms for the lengths of the loop greater than
. In particular,
says that there is no loop of length
. So, our model of
may have loops of any length greater than
, and to ensure that
is false, it has to have a loop of length
. At the same time, we still need to satisfy all axioms S1-S3:
has no predecessor,
is one-to-one, and every element except
has a predecessor. So, consider the set
, and let
be
for
, and
for
. Then, let
. We check that all axioms S1-S4n hold for
.

- S1: . Indeed, , and for every , , while for every , .
- S2: . Indeed, if for , , then either , and implies , or , and implies and (all numbers in have different residuals).
- S3: . Indeed, if , , then , and , and if , then if , , otherwise .
- S41-S4n: for every , , . Indeed, there are no loops in , and , where each element except is mapped by to the next one, while is mapped to (since is finite, one can even check the finite number of axioms S41-S4n for each element in ).

Therefore,
is indeed a model of
. At the same time,
is not true in
, as there is a loop of length
in
(actually, for every
,
, i.e.
).