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.