2
$\begingroup$

It's a well-known fact that there are computable diagonalization functions on Baire space $\mathbb{B} = \mathbb{N}^\mathbb{N}$ (i.e., functions which take a sequence $(r_i)_{i\in \mathbb{N}}$ of elements of $\mathbb{B}$ and produces an element $\mathbb{B}$ not equal to any of the $r_i$'s). I'm curious about whether one such function can generate an 'almost computable enumeration' of the computable elements of $\mathbb{B}$ relative to a path in Kleene's $\mathcal{O}$.

Let's say that a computable diagonalization function is a function $h : \mathbb{B}^{\mathbb{N}} \to\mathbb{B}$ with the property that for any sequence $(r_i)_{i \in \mathbb{N}}$ of elements of $\mathbb{B}$, $h((r_i)) \neq r_i$ for every $i \in \mathbb{N}$.

Given any non-zero $e$ in Kleene's $\mathcal{O}$, let $g_e : \mathbb{N} \to \mathcal{O}$ be some enumeration of the set of $<_{\mathcal{O}}$-predecessors of $e$ (possibly with repetitions) chosen so that $g_e(n)$ is uniformly computable in $n$ and $e$.

Given any computable diagonalizing function $h$, by effective transfinite recursion we get a computable function $h^\ast : \mathcal{O} \to \mathbb{B}$ satisfying that $h^\ast(0)$ is some fixed computable name of $(i \mapsto 0) \in \mathbb{B}$ and for any non-zero $e \in \mathcal{O}$, $h^\ast(e) = h(n \mapsto h^\ast(g_e(n)))$.

We then have that for any path $P$ in $\mathcal{O}$ with $c \in P$, $e \mapsto h^\ast(e)$ defines an injection from $P$ into the computable elements of $\mathbb{B}.

Given how flexible paths through $\mathcal{O}$ are, it seems likely to me that with a careful choice of $h$ we can actually get a bijection, but I am unable to come up with an argument.

Question. Does there exist a computable diagonalization function $h$ and a path $P$ in $\mathcal{O}$ such that $h^\ast$ is a bijection between $P$ and the computable elements of $\mathbb{B}?

If no such $h$ and $P$ exist, is it possible if we only require that $h$ be defined on the computable elements of $\mathbb{B}^\mathbb{N}$ (which is all we need for effective transfinite recursion)?

$\endgroup$
8
  • $\begingroup$ Isn't it more natural to forget about $f$ and just think about diagonalizing directly in Baire space? It would simplify the question, but keep the essence, no? Or is there something important in that for your question? That is, you want a path through $\mathcal{O}$ such that iteratively applying the diagonalization to sequences over $\mathbb{N}$ you will get all the computable elements of Baire space. Is this right? $\endgroup$ Commented Aug 8 at 21:36
  • $\begingroup$ @JoelDavidHamkins Well the ultimate application I have in mind involves $\mathbb{R}$ specifically, but it seems rather likely that a construction for the Baire space version won't be too hard to adapt to an $\mathbb{R}$ version, so I'll edit the question. $\endgroup$ Commented Aug 8 at 21:38
  • $\begingroup$ Very nice revision. I think it is much cleaner now. $\endgroup$ Commented Aug 8 at 21:54
  • $\begingroup$ Can't we arrange a path through $\mathcal{O}$ by specifying a cofinal $\omega$-sequence, such that the $n$th element of it is a simple limit in $\mathcal{O}$ that will ensure that a particular computable sequence is hit? That is, I want to reduce from the question of a path to the question of showing that a particular sequence arises at a given trivial kind of limit. Then, we can put them together to make a path on which every computable sequence will arise. $\endgroup$ Commented Aug 9 at 1:19
  • $\begingroup$ My proposal amounts to: given a list of sequences $a_0,a_1,\ldots$ and a given computable sequence $b$, can we enumerate a sequence that is $b$, if $b$ does not occur amongst the $a_n$, but otherwise is some new sequence $b'$, if it does? If so, we could answer your question affirmatively. But unfortunately, I now think that this proposal isn't possible, since we can make a bad $a_n$ sequence by the Kleene recursion theorem that pretends to put $b$ as $a_0$ and waits until a non-$b$ bit appears in the answer, but then prevents $b$ from appearing. So my idea is not helpful. $\endgroup$ Commented Aug 9 at 12:33

0

You must log in to answer this question.

Browse other questions tagged .