I've been working my way through Rebecca Weber's Computability Theory for fun for a while now, but have been stuck on Exercise 3.4.4 for a few days now, and can't seem to get the proof to go all the way through. The problem states:
(i) Show that if a class $A$ of objects is constructed recursively using a finite set of basic objects and a finite collection of computable closure operators (see $\S$ 2.5), $A$ is effectively countable.
(ii) Show that even if the sets of basic objects and rules in part (i) are infinite, as long as they are effectively countable, $A$ is also effectively countable. $\S$5.1 may be helpful.
I'm working on part (i) for now. I've tried a few different approaches, but feel like I may be overthinking it. Here's my most recent approach:
Let $B$ be a finite set of objects and let $C'$ be a finite set of computable closure operators. We use these to recursively define the class $A$. Since $C'$ is finite, we can label each operator $c_i\in C'$ with $i=1,2,...,|C'|$. Each operator must only operate on a finite number of elements from $A$. Further, define $c_0(a) = a$ for $a\in A$ as the identity operator, and let $C = C'\cup\{c_0\}$.
I want to show that for any $\alpha$-length tuple of elements from $A$, we can order this recursively. If we start with some $\alpha$ elements from $B$, namely $B_\alpha=(b_{\alpha'},b_{\alpha'+1},...,b_{\alpha'+\alpha})$ (this is written like a sequence, but need not have all distinct elements), since $B$ is finite, we can come up with some ordering of all possible tuples of this form. Similarly for $C$, we can have an $\alpha$-length tuple of operators $C_\alpha = (c_{\alpha'},c_{\alpha'+1},...,c_{\alpha'+\alpha})$, where each $c_i$ here operates on a single element of $A$. (Since each $c_i$ generates a single element of $A$, if $c_i$ operated on multiple elements from $A$ then when we apply these to the tuple from $B$ it would either be undefined or would return a tuple of length less than $\alpha$. We also know that there exists at least one operator that takes a single argument: $c_0$.) Now, we can apply $C_\alpha$ to $B_\alpha$ point-wise as $C_\alpha \circ B_\alpha = (c_{\alpha'}(b_{\alpha'}),...,c_{\alpha'+\alpha}(b_{\alpha'+\alpha}))$. If we apply these $C_\alpha$'s recursively, we see that this can generate an ordering for all $\alpha$-tuples of elements from $A$.
The idea now is to try to show some bijective mapping from $A$ to $\mathbb{N}$ to show effective computability. On page 58 of Computability Theory, it shows that $\cup_{k\geq 0} \mathbb{N}^k$ is effectively countable using a function $\tau$, so I thought to try to use this by defining a map $R:\cup_{k\geq 0} A^k \to \cup_{k\geq 0} \mathbb{N}^k$ and then using this fact to show effective computability. Since we can order the $\alpha$-tuples of $A$, it seems like there should exist some bijective mapping $R$. Then, we simply define the mapping $f(a) = \tau(R(a))$ to get the bijective mapping from $A$ to $\mathbb{N}$, and we have that $A$ is effectively countable.
I'm not quite happy with this argument, but it has been the best I've been able to come up with so far. It feels lacking rigor, at the very least. Any tips on either a better approach or how to clean this up would be much appreciated. Even assuming this is correct, I'm not sure how the approach would extend to infinite sets of basic objects and operators.
Thanks!