| Register
\(\newcommand{\Cat}{{\rm Cat}} \) \(\newcommand{\A}{\mathcal A} \) \(\newcommand{\freestar}{ \framebox[7pt]{$\star$} }\)

9. Further questions


    1. Add remark

      Problem 9.1.

      Consider the collection $C$ of countable structures. Consider two equivalence relations on $C$:
      1. Medvedev equivalence: $A\equiv_s B$ if there are two Turing functionals $\Phi$ and $\Psi$ such that for every $A'\cong A$, we have $\Phi(A') \cong B$, and for every $B'\cong B$, we have $\Psi(B') \cong A$.
      2. Muchnik equivalence: $A\equiv_w B$ if for every $A'\cong A$, there is some $B'\cong B$ such that $A' \equiv_T B'$, and vice versa.
      Are these two equivalence relations $\Pi^1_2$-complete under Borel reduction?


        • Add remark

          Problem 9.2.

          Is there a $T_2$ (or $T_1$) and second countable space such that the relation $x E y$ iff $\bigcup_n U_{X(n)} = \bigcup_n U_{Y(n)}$ has arbitrarily high Borel rank (but is Borel)? (Even for rank $\ge 2$?)


            • Add remark

              Problem 9.3.

              Which equivalence relations on c.e. sets are induced by an action of a semi-group computable on the indices?


                • Add remark

                  Problem 9.4.

                  Are there Borel (or continuous) non-reducibility result proved using the recursion theorem?

                      Cite this as: AimPL: Invariant descriptive computability theory, available at http://aimpl.org/invdesccomp.