Skip to main content
1 of 2
James E Hanson
  • 13.2k
  • 3
  • 37
  • 72

Can a path in Kleene's $\mathcal{O}$ enumerate all of the computable reals via uniform diagonalization?

It's a well-known fact that there are computable diagonalization functions on $\mathbb{R}$ (i.e., functions which take a name for a sequence $(r_i)_{i\in \mathbb{N}}$ and produces a name of a real $s$ 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 real numbers relative to a path in Kleene's $\mathcal{O}$.

I'm going to write $\mathbb{B}$ for Baire space (i.e., $\mathbb{N}^\mathbb{N}$). For concreteness, let's fix some standard computable representation $f : \mathbb{B} \to \mathbb{R}$, and 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}$, $f(h((r_i))) \neq f(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 $0 \in \mathbb{R}$ 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 f(h^\ast(e))$ defines an injection from $P$ into the computable real numbers.

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 non-zero computable real numbers?

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)?

James E Hanson
  • 13.2k
  • 3
  • 37
  • 72