Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-27T18:32:13.461Z Has data issue: false hasContentIssue false
  • English
  • Français

Copyable Structures

Published online by Cambridge University Press:  12 March 2014

Antonio Montalbán
Antonio Montalbán*
Affiliation:
Department of Mathematics, 721 Evans Hall, University of California, Berkeley, Berkeley, CA 94720-3840, USA, E-mail: [email protected] URL: www.math.berkeley.edu/~antonio
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce the notions of copyable and diagonalizable classes of structures. We then show how these notions are connected to two other notions that had already been studied for some particular classes of structures, namely the listability property and the low property.

The main result of this paper is the characterizations of the classes of structures with the low property, that is, the classes whose low members all have computable copies. We characterize these classes as the ones whose structural jumps are listable.

Keywords

03D80
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 78 , Issue 4 , December 2013 , pp. 1199 - 1217
Copyright
Copyright © Association for Symbolic Logic 2009

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

[DJ94] Downey, Rod and Jockusch, Carl G., Every low Boolean algebra is isomorphic to a recursive one, Proceedings of the American Mathematical Society, vol. 122 (1994), no. 3, pp. 871–880.Google Scholar
[GN02] Goncharov, S. S. and Knight, J., Computable structure and antistructure theorems, Algebra i Logika, vol. 41 (2002), no. 6, pp. 639–681.Google Scholar
[HM12] Harris, Kenneth and Montalbán, Antonio, On the n-back-and-forth types of Boolean algebras, Transactions of the American Mathematical Society, vol. 364 (2012), no. 2, pp. 827–866.Google Scholar
[HM] Harris, Kenneth and Montalbán, Antonio, Boolean algebra approximations, Transactions of the American Mathematical Society, to appear.Google Scholar
[JS91] Jockusch, Carl G. Jr. and Soare, Robert I., Degrees of orderings not isomorphic to recursive linear orderings, Annals of Pure and Applied Logic, vol. 52 (1991),no. 1-2, pp. 39–64.Google Scholar
[KM11] Asher, M. Kach and Montalbán, Antonio, Cuts of linear orders, Order, vol. 28 (2011), no. 3, pp. 593–600.Google Scholar
[KS00] Knight, Julia F. and Stob, Michael, Computable Boolean algebras, this Journal, vol. 65 (2000), no. 4, pp. 1605–1623.Google Scholar
[Mil01] Miller, Russell, The Δ0 2-spectrum of a linear order, this Journal, vol. 66 (2001), no. 2, pp. 470–486.Google Scholar
[Mon09] Montalbán, Antonio, Notes on the jump of a structure, Mathematical theory and computational practice (Ambos-Spies, Klaus et al., editors), Lecture Notes in Computer Science, vol. 5635, Springer, 2009, pp. 372–378.Google Scholar
[Mon12a] Montalbán, Antonio, Counting the back-and-forth types, Journal of Logic and Computability, vol. 22 (2012), no. 4, pp. 857–876.CrossRefGoogle Scholar
[Mon 12b] Montalbán, Antonio, Rice sequences of relations, Philosophical Transactions of the Royal Society of London. Series A, vol. 370 (2012), no. 1971, pp. 3464–3487.Google Scholar
[Mon13] Montalbán, Antonio, A computability theoretic equivalent to Vaught's conjecture, Advances in Mathematics, vol. 235 (2013), pp. 56–73.Google Scholar
[Nur74] Nurtazin, A. T., Computable classes and algebraic criteria for autostability, Ph.D. thesis, Institute of Mathematics and Mechanics, Alma-Ata, 1974.Google Scholar