Section 2.2: Problem 15 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 the addition relation,
, is not definable in
. Suggestion: Consider an automorphism of
that switches two primes.
Digression: Algebraically, the structure of the natural numbers with multiplication is nothing but the free Abelian semigroup with
generators (viz. the primes), together with a zero element. There is no way you could define addition here. If you could define addition, then you could define ordering (by Exercise 11 and the natural transitivity statement). But one generator looks just like another. That is, there are
automorphisms — simply permute the primes. None of them is order-preserving except the identity.
As suggested, we consider an automorphism that permutes primes. The simplest case would be to switch
and
. That is, for any
, if
then
. To see that it is indeed an automorphism, we verify that
is bijective, and for
and
,
. At the same time, while
where
is the addition relation,
. Therefore,
is not definable.