# Difference between revisions of "Complexity and classification of countable models"

(→Borel classification questions) |
(→Finitely generated models) |
||

Line 7: | Line 7: | ||

The complexity of $\cong^{fg}_T$ can be analyzed more closely using the concept of Borel reducibility. Here, if $E,F$ are equivalence relations on standard Borel spaces $X,Y$, then $E$ is said to be Borel reducible to $F$ iff there is a Borel function $f\colon X\to Y$ such that | The complexity of $\cong^{fg}_T$ can be analyzed more closely using the concept of Borel reducibility. Here, if $E,F$ are equivalence relations on standard Borel spaces $X,Y$, then $E$ is said to be Borel reducible to $F$ iff there is a Borel function $f\colon X\to Y$ such that | ||

\[x\mathrel{E}x'\iff f(x)\mathrel{F}f(x')\] | \[x\mathrel{E}x'\iff f(x)\mathrel{F}f(x')\] | ||

+ | See <cite> gao2009:invariant </cite> for an introduction and survey of this subject of study. | ||

It was shown in <cite> coskeykossak2010:thecomplexity </cite> that $\cong^{fg}_T$ is Borel reducible to $E_\infty$, the universal countable equivalence relation. It was furthermore shown that $E_0$, the almost equality relation on the set of infinite binary sequences, is Borel reducible to $\cong^{fg}_T$. | It was shown in <cite> coskeykossak2010:thecomplexity </cite> that $\cong^{fg}_T$ is Borel reducible to $E_\infty$, the universal countable equivalence relation. It was furthermore shown that $E_0$, the almost equality relation on the set of infinite binary sequences, is Borel reducible to $\cong^{fg}_T$. | ||

Line 12: | Line 13: | ||

'''Problem''': What is the precise complexity of $\cong^{fg}_T$? There is a wide gap between $E_0$ and $E_\infty$. Is $\cong^{fg}_T$ bireducible with $E_\infty$? Is $\cong^{fg}_T$ bireducible with $E_0$? | '''Problem''': What is the precise complexity of $\cong^{fg}_T$? There is a wide gap between $E_0$ and $E_\infty$. Is $\cong^{fg}_T$ bireducible with $E_\infty$? Is $\cong^{fg}_T$ bireducible with $E_0$? | ||

− | It should be remarked that the classification of many other sorts of finitely generated structures lies at the level of $E_\infty$. For instance, the classification of locally finite graphs, finitely branching trees, and fields of finite transcendence degree all have been shown to be bireducible with $E_\infty$. | + | It should be remarked that the classification of many other sorts of finitely generated structures lies at the level of $E_\infty$. For instance, the classification of locally finite graphs, finitely branching trees, finitely generated groups, and fields of finite transcendence degree all have been shown to be bireducible with $E_\infty$. Some of these arguments are worked out in Chapter 13 of <cite> gao2009:invariant </cite>. |

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

## Latest revision as of 10:36, 4 February 2013

## Finitely generated models

This question is about the complexity of the classification problem for finitely generated models of a given completion $T$ of $PA$.

Let us denote the space of finitely generated models of $T$ by $X^{fg}_T$. (More precisely: if $A$ is a fixed countable set, then we can identify the set of models of $T$ whose underlying set is $A$ with a subset of $A^{A^6}$, where each model is represented by its addition and multiplication functions.) Letting $\cong^{fg}_T$ denote the isomorphism relation on $X^{fg}_T$, it is not hard to see that $\cong^{fg}_T$ is Borel, considered as a subset of $X^{fg}_T\times X^{fg}_T$.

The complexity of $\cong^{fg}_T$ can be analyzed more closely using the concept of Borel reducibility. Here, if $E,F$ are equivalence relations on standard Borel spaces $X,Y$, then $E$ is said to be Borel reducible to $F$ iff there is a Borel function $f\colon X\to Y$ such that \[x\mathrel{E}x'\iff f(x)\mathrel{F}f(x')\] See [1] for an introduction and survey of this subject of study.

It was shown in [2] that $\cong^{fg}_T$ is Borel reducible to $E_\infty$, the universal countable equivalence relation. It was furthermore shown that $E_0$, the almost equality relation on the set of infinite binary sequences, is Borel reducible to $\cong^{fg}_T$.

**Problem**: What is the precise complexity of $\cong^{fg}_T$? There is a wide gap between $E_0$ and $E_\infty$. Is $\cong^{fg}_T$ bireducible with $E_\infty$? Is $\cong^{fg}_T$ bireducible with $E_0$?

It should be remarked that the classification of many other sorts of finitely generated structures lies at the level of $E_\infty$. For instance, the classification of locally finite graphs, finitely branching trees, finitely generated groups, and fields of finite transcendence degree all have been shown to be bireducible with $E_\infty$. Some of these arguments are worked out in Chapter 13 of [1].

## References

- Su Gao.
*Invariant descriptive set theory.*Vol. 293, CRC Press, Boca Raton, FL, 2009. MR bibtex - 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