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.