The complexity of isomorphism for complete theories of linear orders with unary predicates

DOI10.1007/S00153-017-0525-ZMaRDI QIDQ527333zbMATH OpenOpenAlexFDO

Authors Richard Rast

Publication date 11 May 2017

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.03037

zbMATH Keywords

back-and-forth equivalenceBorel completenessBorel complexitylinear orders

Mathematics Subject Classification ID

Model theory of denumerable and separable structures (03C15) Model theory of ordered structures; o-minimality (03C64) Descriptive set theory (03E15)

Abstract: We show that if A is a linear order then Th(A) is either $alep{h}_0$-categorical or Borel complete (in the sense of Friedman and Stanley). We generalize this; if A has countably many unary predicates attached, then Th(A) is $alep{h}_0$-categorical, has finitely many countable models (at least three), is Borel equivalent to equality on the reals, is Borel equivalent to "countable sets of reals," or is Borel complete. Furthermore, each of these cases corresponds in a natural way to a count of models of all sizes, up to back-and-forth equivalence. All these cases are possible and we compute precise model-theoretic conditions indicated which case occurs. This complements work on o-minimal theories where analogous results were shown. A large portion of the machinery under the proof is based on work by Matatyahu Rubin in "Theories of Linear Order," where it was shown that such a theory satisfies Vaught's Conjecture and cannot have precisely $alep{h}_0$ countable models.

Recommendations

• On ‐complete equivalence relations on the generalized Baire space
• The classification of the countable models of complete theories of unary predicates with a substitution of a bounded order
• The Borel complexity of isomorphism for theories with many types
• The Borel complexity of isomorphism for o-minimal theories
• Categorical linearly ordered structures

Cites work

• ℵ_0-categoricity of linear orderings
• A Borel reductibility theory for classes of countable structures
• Borel completeness of some \(\aleph_{0}\)-stable theories
• Borel equivalence relations induced by actions of the symmetric group
• Countably categorical coloured linear orders
• scientific article; zbMATH DE number 5853298 (Why is no real title available?)
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• Invariant descriptive set theory
• Model Theory
• Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers
• The Borel complexity of isomorphism for o-minimal theories
• The Borel complexity of isomorphism for theories with many types
• Theories of linear order

Cited in

(8)

• Countably categorical theories
• Stationarily ordered types and the number of countable models
• scientific article; zbMATH DE number 3557788 (Why is no real title available?)
• The Complexity of Order Type Isomorphism
• The classification of the countable models of complete theories of unary predicates with a substitution of a bounded order
• HOMOGENEITY AND FIX-POINTS: GOING FORTH!
• Around Rubin's ``Theories of linear order
• Characterizing the existence of a Borel complete expansion

This page was built for publication: The complexity of isomorphism for complete theories of linear orders with unary predicates

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q527333)