Computable shuffle sums of ordinals

Abstract

The main result is that for sets ${S \subseteq \omega + 1}$, the following are equivalent:

• (1) The shuffle sum σ(S) is computable.

• (2) The set S is a limit infimum set, i.e., there is a total computable function g(x, t) such that ${f(x) = \lim inf_t g(x, t)}$ enumerates S.

• (3) The set S is a limitwise monotonic set relative to 0′, i.e., there is a total 0′-computable function ${\tilde{g}(x, t)}$ satisfying ${\tilde{g}(x, t) \leq \tilde{g}(x, t+1)}$ such that ${{\tilde{f}(x) = \lim_t \tilde{g}(x, t)}}$ enumerates S.

Other results discuss the relationship between these sets and the ${\Sigma^0_3}$ sets.