The conditions (1) and (2) given in the problem essentially restrict the set of tuples that can generate a given number $b$ . Therefore, we can at least argue that $C$ is decidable. Indeed, given $b$ , we can run a procedure that will first check all the numbers $c<b$ whether they belong to $C$ (so, basically, we apply the same procedure inductively), and then for all $n<f(b)$ and $a_{0},\ldots,a_{n-1}<b$ check whether $a_{0},\ldots,a_{n-1}\in C$ and whether $<\langle a_{0},\ldots,a_{n-1}\rangle,b>\in R$ . If these conditions hold for some tuple, then $b\in C$ , otherwise it is not.

In other words, we start with $b=0$ . Given (1), the only possibility for $0$ to be in $C$ is if $<\langle\rangle,0>\in R$ , hence, we can decide whether this holds or not. Next, we take $b=1$ . According to (1) and (2), the only possibility for $1$ to be in $C$ is if $<\langle\rangle,1>\in R$ or $0\in C$ and $<\langle\underbrace{0,\ldots,0}_{n}\rangle,1>\in R$ for some $n<f(1)$ , so, again, we can effectively decide whether $b=1$ is in $C$ . And so on, until we reach a given $b$ .

This procedure shows that $C$ is decidable, which, according to Church’s Thesis, implies $C$ is representable in a consistent finitely axiomatizable theory in a language with $0$ and $\mathbb{S}$ (and, as was promised to be shown later in the text, this implies $C$ is representable in $\mbox{Cn}A_{E}$ ). But the problem is that we want to explicitly show that $C$ 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 $C$ is also representable and supports Church’s Thesis.

$b\in C$ iff for some $n<f(b)$ and $a_{0},\ldots,a_{n-1}<b$ , $a_{0},\ldots,a_{n-1}\in C$ , $<\langle a_{0},\ldots,a_{n-1}\rangle,b>\in R$ . In terms of characteristic functions, this can be expressed as $g(b)=K_{C}(b)=1$ iff there is $a\le p_{f(b)}^{b\cdot f(b)}$ (we could have make this boundary more precise, but we want to avoid cases: as stated, $a=1$ is always a possibility) such that $a$ is a sequence number, $<a,b>\in R$ and for $i<\mbox{lh}a$ , $g((a)_{i})=1$ , otherwise $g(b)=0$ . This definition of $g(b)$ refers to itself using the value of $g$ at $(a)_{i}<a$ (Exercise 7(b)). Hence, we may apply primitive recursion. Let $d(x,b)=1$ iff there is $a\le p_{f(b)}^{b\cdot f(b)}$ such that $a$ is a sequence number, $<a,b>\in R$ and for $i<\mbox{lh}a$ , $(x)_{(a)_{i}}=1$ , otherwise $d(x,b)=0$ . In other words, $x$ keeps the values of $g(k)$ for $k<b$ , and based on this we see if $b$ can be generated from some $\langle a_{0},\ldots,a_{n\text{−}1}\rangle$ where $n<f(b)$ , $a_{i}<b$ , and $(x)_{a_{i}}=1$ ($a_{i}\in C$ ). Now, by catalog items 1 and 13, $C$ and $K_{C}(b)=g(b)=d(\overline{g}(b),b)$ are representable if $d(x,b)$ is, and, since $f$ and $R$ are representable, $d(x,b)$ is representable due to catalog items 0, 2, 3, 7, 9, 10, 11.