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

About 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. The source says that it was made by Ted Slaman and Hugh Woodin in 1989, but supplies no resolution.

References

Primary source

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

Additional 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.

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.