# Is every limit computable set in the Ershov hierarchy?

A set is limit computable, or $$\Delta^0_2$$, if its characteristic function is equal to $$\lim_{s\rightarrow\infty}g(x,s)$$ for some total computable function $$g$$. And given a computable ordinal $$\alpha$$ and a path $$P$$ through Kleene's $$O$$, a set is $$\alpha$$-c.e. if its characteristic function is equal to $$\lim_{s\rightarrow\infty}g(x,s)$$ for some total computable function $$g$$ such that there exists a total computable function $$o:\mathbb{N}^2\rightarrow P$$ such that $$o(x,0)$$ is a notation for $$\alpha$$, $$o(x,s+1)\leq_O o(x,s)$$ for all $$s$$, and $$o(x,s+1)<_Oo(s,x)$$ whenever $$g(s+1,x)\neq g(s,x)$$. The latter is known as the Ershov hierarchy.

Now I'm wondering if the Ershov hierarchy exhausts limit computable sets. In one sense the answer is a trivial yes: for every limit computable set $$X$$ there exists a path $$P$$ through Kleene's $$O$$ such that $$X$$ is $$\omega^2$$-c.e. And also there exists a path $$P$$ through Kleene’s O such that every limit computable set is $$\omega^3$$-c.e. But my question is, for any given maximal path $$P$$ through Kleene's $$O$$, is every limit computable set an $$\alpha$$-c.e. set for some computable ordinal $$\alpha$$?

No. Not only is it not the case that every maximal path in $$O$$ yields an Ershov hierarchy which exhausts the $$\Delta^0_2$$ sets, Yuri Ershov showed that there’s a great many maximal paths in $$O$$ which fail to have this property. See theorem 4.6 of this survey article.
To wit, $$P$$ be a $$\Pi^1_1$$ maximal path in $$O$$, and suppose that the Ershov hierarchy with respect to $$P$$ exhausted all $$\Delta^0_2$$ set. Fix an enumeration of $$\Delta^0_2$$ sets, and let $$h:\mathbb{N}\rightarrow P$$ be defined by, $$h(n)$$ is the $$O$$-least element $$a$$ of $$P$$ such that the $$a^{th}$$ $$\Delta^0_2$$ is $$a$$-c.e. Then $$h$$ is total and thus hyperarithmetical, which by $$\Sigma^1_1$$-boundedness implies that the range of $$h$$ is bounded, yielding a contradiction. Therefore, the Ershov hierarchy with respect to any $$\Pi^1_1$$ maximal path in $$O$$ does not exhaust the $$\Delta^0_2$$ sets.