Conjecture on the complexity of definable orbits of c.e. sets

About 13 years old · traced to

Let AA be a c.e. set whose orbit is properly Δα0\Delta^0_{\alpha} for a finite α>8\alpha>8, as in Theorem 3.2, and let Lω1,ω\mathcal{L}_{\omega_1,\omega} denote the infinitary logic used to describe orbits in the lattice E\mathcal{E} of computably enumerable sets. Orbit-complexity conjecture. The above orbits can be built so that the complexity of the Lω1,ω\mathcal{L}_{\omega_1,\omega} formula describing the orbit is close to α\alpha. This would refine the known existence of properly Δα0\Delta^0_{\alpha} 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

Never refreshed

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.