The complexity of isomorphism

29.03.2012 15:00 - 16:30

S. D. Friedman (U Wien)

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).

Organiser:

KGRC

Location:
SR 101, 2. St., Währinger Str. 25