Classes of structures with no intermediate isomorphism problems

DOI10.1017/JSL.2014.55MaRDI QIDQ2805027zbMATH OpenOpenAlexFDO

Authors Antonio Montalbán

Publication date 9 May 2016

Published in The Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

Vaught's conjectureequivalence relationseffective reducibility

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Other infinitary logic (03C75)

Abstract: We say that a theory $T$ is intermediate under effective reducibility if the isomorphism problems among its computable models is neither hyperarithmetic nor on top under effective reducibility. We prove that if an infinitary sentence $T$ is uniformly effectively dense, a property we define in the paper, then no extension of it is intermediate, at least when relativized to every oracle on a cone. As an application we show that no infinitary sentence whose models are all linear orderings is intermediate under effective reducibility relative to every oracle on a cone.

Recommendations

• Isomorphism relations on computable structures
• The isomorphism problem for classes of computable fields
• Computable transformations of structures
• Isomorphism and classification for countable structures
• Categorical linearly ordered structures

Cites work

• scientific article; zbMATH DE number 3494394 (Why is no real title available?)
• scientific article; zbMATH DE number 976831 (Why is no real title available?)
• A computability theoretic equivalent to Vaught's conjecture
• Bounds on weak scattering
• Computable structures and the hyperarithmetical hierarchy
• Countable admissible ordinals and hyperdegrees
• Counting the number of equivalence classes of Borel and coanalytic equivalence relations
• Equivalence Relations on Classes of Computable Structures
• On the Equimorphism Types of Linear Orderings
• Scott sentences and admissible sets
• The isomorphism problem for torsion-free abelian groups is analytic complete
• The isomorphism relation on countable torsion free abelian groups
• Theories of linear order

Cited in

(2)

• The 𝜔-Vaught’s conjecture
• Using computability to measure complexity of algebraic structures and classes of structures

This page was built for publication: Classes of structures with no intermediate isomorphism problems

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