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

(Monotone recursion) Assume that
is a representable binary relation on
. Let
be the smallest subset of
(i.e., the intersection of all subsets) such that for all
,
,
,
Further assume that (1) for all
,
,
,
and (2) there is a representable function
such that for all
,
,
,
Show that
is representable. (
is, in a sense, generated by
.
in general because if
, then
.)

The conditions (1) and (2) given in the problem essentially restrict the set of tuples that can generate a given number
. Therefore, we can at least argue that
is decidable. Indeed, given
, we can run a procedure that will first check all the numbers
whether they belong to
(so, basically, we apply the same procedure inductively), and then for all
and
check whether
and whether
. If these conditions hold for some tuple, then
, otherwise it is not.

In other words, we start with
. Given (1), the only possibility for
to be in
is if
, hence, we can decide whether this holds or not. Next, we take
. According to (1) and (2), the only possibility for
to be in
is if
or
and
for some
, so, again, we can effectively decide whether
is in
. And so on, until we reach a given
.

This procedure shows that
is decidable, which, according to Church’s Thesis, implies
is representable in a consistent finitely axiomatizable theory in a language with
and
(and, as was promised to be shown later in the text, this implies
is representable in
). But the problem is that we want to explicitly show that
is representable. We have a theorem saying that a representable set is decidable, and a conjecture saying that a decidable set is representable, and the fact, that so far all sets considered decidable were found to be representable. So, let us further confirm this latter finding, and proof explicitly that this decidable set
is also representable and supports Church’s Thesis.

iff for some
and
,
,
. In terms of characteristic functions, this can be expressed as
iff there is
(we could have make this boundary more precise, but we want to avoid cases: as stated,
is always a possibility) such that
is a sequence number,
and for
,
, otherwise
. This definition of
refers to itself using the value of
at
(Exercise 7(b)). Hence, we may apply primitive recursion. Let
iff there is
such that
is a sequence number,
and for
,
, otherwise
. In other words,
keeps the values of
for
, and based on this we see if
can be generated from some
where
,
, and
(
). Now, by catalog items 1 and 13,
and
are representable if
is, and, since
and
are representable,
is representable due to catalog items 0, 2, 3, 7, 9, 10, 11.