Nonuniversality conjecture for recursive isomorphism on
Nonuniversality conjecture for recursive isomorphism on
Let be Cantor space. Recursive isomorphism on is the countable Borel equivalence relation identifying recursively isomorphic elements.
Nonuniversality conjecture. Recursive isomorphism on is not a universal countable Borel equivalence relation.
The conjecture is motivated by the close connection between recursive isomorphism and many-one equivalence, together with the fact that known approaches proving universality for recursive isomorphism also prove universality for many-one equivalence. The source leaves the question open.
Equivalent formulations 1
Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.
Nonuniversality conjecture for recursive isomorphism on
Let be Cantor space. Recursive isomorphism on is the countable Borel equivalence relation identifying two elements when they are recursively isomorphic.
Nonuniversality conjecture. Recursive isomorphism on is not a universal countable Borel equivalence relation.
Recursive isomorphism on is known to be measure universal, but its universality remains unresolved; the conjecture asserts that measure universality does not extend to universality.
source: Andrew S Marks, “Uniformity, Universality, and Computability Theory”, arXiv:1606.01976 (2017).
Sources & referencesView supporting material
Primary source
Andrew S Marks, “Uniformity, Universality, and Computability Theory”, arXiv:1606.01976 (2017).
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
Sign in to submit a solution.
No solutions have been posted yet.