Hostname: page-component-6bf8c574d5-mggfc Total loading time: 0 Render date: 2025-02-19T20:01:06.488Z Has data issue: false hasContentIssue false
  • English
  • Français

CLASSES OF STRUCTURES WITH NO INTERMEDIATE ISOMORPHISM PROBLEMS

Published online by Cambridge University Press:  22 January 2016

ANTONIO MONTALBÁN
ANTONIO MONTALBÁN*
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CALIFORNIA BERKELEY, USAE-mail: [email protected]: www.math.berkeley.edu/∼antonio
Get access Rights & Permissions [Opens in a new window]

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 in 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 in a cone.

Keywords

Vaught’s conjectureeffective reducibilityequivalence relations
Type
Articles
Information
The Journal of Symbolic Logic , Volume 81 , Issue 1 , March 2016 , pp. 127 - 150
Copyright
Copyright © The Association for Symbolic Logic 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Ash, C. J. and Knight, J., Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, Elsevier, Amsterdam, 2000.Google Scholar
Barwise, Jon, Admissible Sets and Structures: An Approach to Definability Theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1975.Google Scholar
Becker, Howard, Isomorphism of computable structures and Vaught’s conjecture, this Journal, vol. 78 (2013), no. 4, pp. 1328–1344.Google Scholar
Becker, Howard and Kechris, Alexander S., The Descriptive Set Theory of Polish Group Actions, London Mathematical Society Lecture Note Series, vol. 232, Cambridge University Press, Cambridge, 1996.Google Scholar
Burgess, John P., A reflection phenomenon in descriptive set theory. Fundamenta Mathematicae, vol. 104 (1979), no. 2, pp. 127–139.Google Scholar
Downey, Rod and Montalbán, Antonio, The isomorphism problem for torsion-free abelian groups is analytic complete. Journal of Algebra, vol. 320 (2008), pp. 2291–2300.Google Scholar
Fokina, Ekaterina B. and Friedman, Sy-David, Equivalence relations on classes of computable structures, Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, vol. 5635, Springer, Berlin, 2009, pp. 198–207.Google Scholar
Fokina, E. B., Friedman, S., Harizanov, V., Knight, J. F., McCoy, C., and Montalbán, A., Isomorphism and bi-embeddability relations on computable structures, this Journal, vol. 77 (2012), no. 1, pp. 122–132.Google Scholar
Friedman, Harvey and Stanley, Lee, A Borel reducibility theory for classes of countable structures, this Journal, vol. 54 (1989), no. 3, pp. 894–914.Google Scholar
Gao, Su, Some dichotomy theorems for isomorphism relations of countable models, this Journal, vol. 66 (2001), no. 2, pp. 902–922.Google Scholar
Gao, Su, Invariant descriptive set theory, Pure and Applied Mathematics, vol. 293, CRC Press, Boca Raton, FL, 2009.Google Scholar
Harrison, J., Recursive pseudo-well-orderings. Transactions of the American Mathematical Society, vol. 131 (1968), pp. 526–543.Google Scholar
Hjorth, Greg, The isomorphism relation on countable torsion free abelian groups. Fundamenta Mathematicae, vol. 175 (2002), no. 3, pp. 241–257.Google Scholar
Harnik, V. and Makkai, M., A tree argument in infinitary model theory. Proceedings of the American Mathematical Society, vol. 67 (1977), no. 2, pp. 309–314.Google Scholar
Kanamori, Akihiro, The Higher Infinite, second ed., Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003.Google Scholar
Knight, Julia and Montalbán, Antonio, $\sum _1^1 $-equivalence relations which are on top, unpublished notes, September 2010.Google Scholar
Montalbán, Antonio, On the equimorphism types of linear orderings. Bulletin of Symbolic Logic, vol. 13 (2007), no. 1, pp. 71–99.CrossRefGoogle Scholar
Montalbán, Antonio, A computability theoretic equivalent to Vaught’s conjecture. Advances in Mathematics, vol. 235 (2013), pp. 56–73.Google Scholar
Montalbán, Antonio, Priority arguments via true stages, this Journal, accepted.Google Scholar
Montalbán, Antonio, Analytic equivalence relations satisfying hyperarithmetic-is-recursive, submitted.Google Scholar
Nadel, Mark, Scott sentences and admissible sets. Annals of Mathematical Logic, vol. 7 (1974), pp. 267–294.Google Scholar
Rosenstein, Joseph G., Linear orderings, Pure and Applied Mathematics, vol. 98, Academic Press [Harcourt Brace Jovanovich Publishers], New York, 1982.Google Scholar
Rubin, Matatyahu, Theories of linear order. Israel Journal of Mathematics, vol. 17 (1974), pp. 392–443.Google Scholar
Sacks, Gerald E., Countable admissible ordinals and hyperdegrees. Advances in Mathematics, vol. 20 (1976), no. 2, pp. 213–262.Google Scholar
Sacks, Gerald E., Bounds on weak scattering. Notre Dame Journal of Formal Logic, vol. 48 (2007), no. 1, pp. 5–31.Google Scholar
Silver, Jack H., Counting the number of equivalence classes of Borel and coanalytic equivalence relations. Annals of Mathematical Logic, vol. 18 (1980), no. 1, pp. 1–28.CrossRefGoogle Scholar
Slaman, Theodore A. and Steel, John R., Definable functions on degrees, Cabal Seminar 81–85, Lecture Notes in Mathematics, vol. 1333, Springer, Berlin, 1988, pp. 37–55.Google Scholar
Steel, John R., On Vaught’s conjecture, Cabal Seminar 76–77 (Proc. Caltech-UCLA Logic Sem., 1976–77), Lecture Notes in Mathematics, vol. 689, Springer, Berlin, 1978, pp. 193–208.Google Scholar