2012 seminar talk: The complexity of isomorphism

Talk held by Sy-David Friedman (KGRC) at the KGRC seminar on 2012-03-29.

Abstract

If $X$ is a set of reals then $Iso(X)$ denotes the set of pairs $(x,y)$ from $X$ such that $x,y$ code isomorphic structures on $\omega$. This is the restriction to $X$ of a $\Sigma_1^1$ equivalence relation. We say that $Iso(X)$ is weakly complete if whenever $E$ is a $\Sigma_1^1$ equivalence relation there are functions $f,g$ which are $\Delta_1^1$ with parameters from $X$ such that for $x,y$ in $X, E(x,y)$ iff $Iso(f(x,y),g(x,y))$, and is complete if there is a function $f$ which is $\Delta_1^1$ with parameters from $X$ such that for $x,y$ in $X, E(x,y)$ iff $Iso(f(x),f(y))$. Let $R$ denote the set of all reals and $Comp$ the set of all computable reals. Then $Iso(R)$ is weakly complete but not complete and $Iso(Comp)$ is complete (the latter due to Fokina-F-Harizanov-Knight-McCoy-Montalban). I don't know if $Iso(Hyp)$ is complete, where $Hyp$ denotes the set of hyperarithmetic reals. One can also consider $Iso$ on structures with universe $\omega_1$, assuming $V = L$. Then $Iso(\omega_1\text{-}Comp)$ is again complete, but it is not known if $Iso$ for arbitrary $\omega_1$ structures is complete (it is weakly complete).