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

− | + | $\cong^{fg}_T$, is essentially countable and $E_0\leq_B \cong^{fg}_T$ i.e. $\cong^{fg}_T$ is not smooth <cite> coskeykossak2010:thecomplexity </cite>. | |

+ | |||

+ | Problem: Is $\cong^{fg}_T$ hyperfinite? In other words, is $\cong^{fg}_T$ Borel reducible to $E_0$? | ||

{{References}} | {{References}} |

## Revision as of 04:44, 22 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.

$\cong^{fg}_T$, is essentially countable and $E_0\leq_B \cong^{fg}_T$ i.e. $\cong^{fg}_T$ is not smooth [1].

Problem: 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