Computably Enumerable Reals and Uniformly Presentable Ideals
Rodney G. Downey, Sebastiaan A. Terwijn · Mathematical logic quarterly · 2002
We study the relationship between a computably enumerable real and its presentations. A set A presents a computably enumerable real α if A is a computably enumerable prefix-free set of strings such that . Note that is precisely the measure of the set of reals that have a string in A as an initial segment. So we will simply abbreviate by μ(A). It is known that whenever A so presents α then A ≤wtt α, where ≤wtt denotes weak truth table reducibility, and that the wtt-degrees of presentations form an ideal ℐ(α) in the computably enumerable wtt-degrees. We prove that any such ideal is , and conversely that if ℐ is any nonempty ideal in the computably enumerable wtt-degrees then there is a computable enumerable real α such that ℐ = ℐ(α). We also prove a kind of Rice Theorem for these ideals, namely that if the index set of such a ideal is not empty or equal to ω then it is -complete.