Difference between revisions of "Complexity and classification of countable models"
From Peano's Parlour
| Line 3: | Line 3: | ||
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. | 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 proved 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$? | + | Coskey and Kossak <cite> coskeykossak2010:thecomplexity </cite> proved 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$? |
| − | + | {{References}} | |
| − | + | ||
Revision as of 08:48, 21 January 2013
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 [1] proved 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$?
References
- Samuel Coskey and Roman Kossak. The complexity of classification problems for models of arithmetic. Bull. Symbolic Logic 16(3):345--358, 2010. www MR bibtex
