Complexity and classification of countable models

From Peano's Parlour
Jump to: navigation, search

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


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