Conjecture on the complexity of definable orbits of c.e. sets
Let be a c.e. set whose orbit is properly for a finite , as in Theorem 3.2, and let denote the infinitary logic used to describe orbits in the lattice of computably enumerable sets. Orbit-complexity conjecture. The above orbits can be built so that the complexity of the formula describing the orbit is close to . This would refine the known existence of properly orbits by relating their arithmetical complexity to the complexity of infinitary formulas defining them; the source gives no resolution of the conjecture.
References
Primary source
Peter Cholak, “Some recent research directions in the computably enumerable sets”, arXiv:1312.5979 (2013).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.