1. Effective Jumps
-
Problem 1.1.
For which equivalence relation $E$ is $E < E^+$? (In both the computable and Borel context.)- For which orbit equivalence relation?
- For which $\Sigma^1_1$ equivalence relation?
- Is there an $E$ for which we do not know if $E < E^+$?
-
Problem 1.2.
Given an equivalence relation $E$ on $X$ and a countable group $G$, define an equivalence relation on $X^G$ by $\alpha E^{[G]} \beta$ iff there is some $g\in G$ such that for every $h\in G$, we have $\alpha(g^{-1} h) E \beta(h)$. For which $E$ and $G$ is $E < E^{[G]}$? What about the effective versions of this problem? -
Problem 1.3.
For countable groups $G$, $H$, and an equivalence relation $E$, is there a countable group $K$ such that $(E^{[G]})^{[H]}$ is bi-reducible with $E^{[K]}$ -
Problem 1.4.
For a “reasonable" computable group $G$ and some arithmetical $E$ is $E^{[G]}$ always universal at some $\Sigma^0_n$ level? -
Problem 1.5.
Modify the Friedman–Stanley jump by using a fixed subgroup $G \le S_\infty$. Ask the above questions. -
Problem 1.6.
Consider the Louveau jump: let $F$ be a filter on $\omega$ and $E$ an equivalence relation, define $E^F$ to be the equivalence relation on $X^\omega$ by $\alpha E^F \beta$ iff $\{n:\alpha(n) E \beta(n)\}\in F$.
On $X = \omega$, define $i E^F j$ iff $\{n \mid \varphi_i(n) E \varphi_j(n)\}\in F$. Ask the above questions.
Cite this as: AimPL: Invariant descriptive computability theory, available at http://aimpl.org/invdesccomp.