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

6. Countable and finitary reducibility


    1. Add remark

      Problem 6.1.

      Is $E_\infty \le^{<\omega} E_0$? Is $E_{\text{set}}$ universal for $\le ^{<\omega}$ among $\Pi^0_3$ equivalence relations?


        • Add remark

          Problem 6.2.

          Consider the class $B$ defined by some $L_{\omega_1,\omega}$-sentence $\varphi$ (where the topology is generated by the fragments of the language). What are the possible complexities of the isomorphism relations on $B$ as a set? It is known that $\Sigma^0_1$ and $\Sigma^0_\alpha$ for limit $\alpha$ are not possible.


            • Add remark

              Problem 6.3.

              Consider versions of $\le^n$ or $\le^\omega$ obtained by playing a game for the reals. (I.e., you give the first input, the functional returns the first output, then you give the second input, etc.) What can be said about these reducibilities?

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