# Section 3.3: Problem 7 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

Establish the following facts:

(a)
.

(b)
; equality holds iff
.

(c)
; equality holds iff
.

(d)
.

(e)
is the smaller of
and
.

Regardless, of whether we are supposed to show all these facts as consequences of
or not, my solution of Exercise 2 shows that there is one-to-one correspondence between “finite” numbers in
and natural numbers
, in the sense that
iff
(
proves the negation otherwise), and
iff
(
proves the negation otherwise). Therefore, we will proceed informally, as is done for the most part of the section in the text, keeping in mind that the solution can be translated into the formal language to be proved from
.

(a)
. By induction,
implies
.

(b) Note, that, formally,
is defined for

*all*natural numbers as the least such that either or where is the divisibility relation. By definition, for all . For , either , or , and divides , i.e. . We just need to argue that for and , . In fact, we will show . For , we have , and, by induction, if , then .
(c) Again, formally,
is defined for

*all*natural numbers as the least such that either or . By definition, . For , either , or , and divides . By (a), .
(d) Again, formally,
is defined for

*all*natural numbers as the least such that either or both and for every , , implies . Suppose, . Then, , implying , implying , implying for every , there are and such that but , in particular, for , there are and such that but , contradiction. Hence, , and .
(e)
is the least
such that either
or
, where
is the least
such that either
or both
and for every
,
,
implies
. Further,
the least
such that either
or
. If
, then
,
, and
. If
and
, then
and
. Now, suppose
and
. Then,
. If
, then, by definition of
, for all
,
, and, by definition of
,
, but for
,
(otherwise, we can divide
by
to obtain a smaller
satisfying the definition). Then, by definition of
,
. Finally, if
, then, by definition of
, for all
,
, but
. Then, by definition of
, for all
,
, but
(otherwise, we can divide
by
to obtain a smaller
satisfying the definition). Hence, by definition of
,
.

Note. This last point holds for every number
, even if it is not a sequence number, and even if it is odd (
).