A first-order theory with intermediate isomorphism complexity — Problem 11.1

11. Su Gao

This question is about equivalence relations given by complete first-order theories. The question has been circulating in the community since early 2000s.

Consider a complete first order theory $T$ in a countable language. Let $\mathrm{Mod}(T)$ be the Polish space of countable models of $T$ with universe $\omega$. Let $\cong\restriction_{\mathrm{Mod}(T)}$ denote the isomorphism relation on $\mathrm{Mod}(T)$. Recall two basic equivalence relations in descriptive set theory:

$=$ is the identity relation on $\mathbb{R}$;

$=^{+}$ is the equivalence relation on $\mathbb{R}^{\omega}$ that $(x_{n})_{n\in\omega}=^{+}(y_{n})_{n\in\omega}$ if they represent the same countable subset of reals, i.e., if

Also note the following fact:

Fact 11.1.

(1) There is a complete theory $T$ such that $=$ is Borel bi-reducible to $\cong\restriction_{\mathrm{Mod}(T)}$. For example, $T$ can be chosen as the theory of the equivalence relation on $\omega$ with infinitely many equivalence classes of any finite size. (2) There is a complete theory $T^{\prime}$ such that $=^{+}$ is Borel bi-reducible to $\cong\restriction_{\mathrm{Mod}(T^{\prime})}$. For example, $T^{\prime}$ can be chosen as the theory of infinitely many independent equivalence relations on $\omega$ and every equivalence relation has infinitely many equivalence classes of any finite size.

So we have the following natural question:

Remark 11.2.

Note that $=\ <_{B}\ =^{+}$, and there are equivalence relations strictly between them. For example, $E_{0},E_{\infty},E^{\omega}_{0}$. So, they are natural candidates for the complexity of $\cong\restriction_{\mathrm{Mod}(T)}$ for some $T$ if the problem has a positive answer.

There have been some research (e.g. [1, 2, 3, 4]) on this problem and more generally on the isomorphism relation $\cong\restriction_{\mathrm{Mod}(T)}$ in the Borel reducibility sense. In particular, Dave Marker showed in [1] that if $S(T)$ (the Stone space of $T$-types) is uncountable, then $T$ is not an example for Problem 11.1.

Current research status is unassessed. The dated source poses this question; inclusion does not certify that it remains open today.