Problem #20

Essentially countable isomorphism relations of first order theories

Open!Ordinary impact — every problem listed here is a genuine, worthwhile open problem

Suppose that TT is a first order theory in a countable language and let T\cong_T be the associated isomorphism relation. If T\cong_T is essentially countable must it be smooth?

Definitions

Given a theory TT, Mod(T)\operatorname{Mod}(T) denotes the Polish space of models of TT with domain N\mathbb{N} and T\cong_T denotes the isomorphism relation on Mod(T)\operatorname{Mod}(T).

A Borel equivalence relation EE is essentially countable if it is Borel reducible to a countable Borel equivalence relation and smooth if it is Borel reducible to the equality relation on 2N2^\mathbb{N}.

Known Partial Results

  • It is well known that the question has a negative answer if countable Lω1,ω\mathcal{L}_{\omega_1, \omega}-theories are allowed.
  • Marker [Mar07] showed that if TT has uncountably many types then T\cong_T is not essentially countable and hence the question has a positive answer for such theories.
  • Rast [Ras17] showed the question has a positive answer when TT is a colored linear order (i.e. a linear order with some unary predicates).
  • Rast and Sahota [RS17] showed that the question has a positive answer for o-minimal theories.

Notes

The question was originally asked by Hjorth and Kechris in 2005 at the Notre Dame workshop on Vaught's Conjecture.

Reference for the problem statement

[Mar07]David Marker, The Borel complexity of isomorphism for theories with many types, Notre Dame Journal of Formal Logic, 2007 [doi]

Additional References

[RS17]Richard Rast and Davender Singh Sahota, The Borel complexity of isomorphism for o-minimal theories, Journal of Symbolic Logic, 2017 [doi]

[Ras17]Richard Rast, The complexity of isomorphism for complete theories of linear orders with unary predicates, Archive for Mathematical Logic, 2017 [doi]

Comments

Loading comments…