Classes of structures with no intermediate isomorphism problems

DOI10.1017/JSL.2014.55zbMATH Open1436.03233arXiv1309.3815OpenAlexW2963890194MaRDI QIDQ2805027FDOQ2805027

Authors: Antonio Montalbán 

Publication date: 9 May 2016

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

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.

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

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

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)

Cites Work

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

Cited In (2)

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

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)