Section 2.2: Problem 11 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
For each of the following relations, give a formula which defines it in
. (The language is assumed to have equality and the parameters
,
, and
).
(a)
.
(b)
.
(c)
.
(d)
.
Digression: This is merely the tip of the iceberg. A relation on
is said to be arithmetical if it is definable in this structure. All decidable relations are arithmetical, as are many others. The arithmetical relations can be arranged in a hierarchy; see Section 3.5.
The difference between this exercise and examples on page 91 seems to be in the language used, as here we are missing two essentially used in the examples symbols
and
. That is, the purpose of the exercise seems to be to show that those two symbols do not expand the set of what can be defined in
, in particular, we show that using our restricted language we can still define both
and the successor of any natural number.
(a)
(
iff for every
,
).
(b)
(
iff for every
,
).
(c)
(
iff for some
,
and
).
(d)
(
iff for some
,
and
).