← All problems

Slaman–Woodin conjecture on the complexity of the c.e. orbit relation

20 years old · traced to

Let (Wi)i∈N(W_i)_{i\in\mathbb{N}} be an effective enumeration of the computably enumerable sets, and write Wi≈WjW_i\approx W_j when the two sets lie in the same orbit under automorphisms of the lattice of computably enumerable sets modulo finite sets. Slaman–Woodin conjecture. The index relation

{⟨i,j⟩:Wi≈Wj}\{\langle i,j\rangle: W_i\approx W_j\}

is Σ11\Sigma^1_1-complete. This conjecture concerns the descriptive-set-theoretic complexity of deciding whether two computably enumerable sets are automorphic.

References

2 papers in this index state this conjecture (2006–2007). The statement above is taken from the most recent of them; the others are arXiv:math/0607264.

Status

  • Solved: Peter A. Cholak, Rod Downey, and Leo A. Harrington. The Complexity of Orbits of Computably Enumerable Sets (arXiv, 2007) https://arxiv.org/abs/0705.0125

Source: Peter A. Cholak, Rod Downey and Leo Harrington, “The Complexity of Orbits of Computably Enumerable Sets”, arXiv:0705.0125 (2007).

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.