Complexity and classification of countable models
From Peano's Parlour
Revision as of 09:37, 18 January 2013 by Rkossak (Talk | contribs) (Created page with " == Borel classification questions == Let $T$ be a completion of $PA$. It is not hard to see that the isomorphism problem for finitely generated models of $T$, $\cong^{fg}_T$, i...")
Borel classification questions
Let $T$ be a completion of $PA$. It is not hard to see that the isomorphism problem for finitely generated models of $T$, $\cong^{fg}_T$, is Borel.
Coskey and Kossak prove in The complexity of classification problems for models of arithmetic, Bull. Symbolic Logic 16 (2010), no. 3, 345–358, that $\cong^{fg}_T$, is essentially countable and $E_0\leq_B \cong^{fg}_T$ i.e. $\cong^{fg}_T$ is not smooth. Is $\cong^{fg}_T$ hyperfinite? In other words, is $\cong^{fg}_T$ Borel reducible to $E_0$?
