Hostname: page-component-586b7cd67f-2plfb Total loading time: 0 Render date: 2024-11-22T06:45:49.087Z Has data issue: false hasContentIssue false
  • English
  • Français

COMPUTABLE STRUCTURES IN GENERIC EXTENSIONS

Published online by Cambridge University Press:  10 May 2016

JULIA KNIGHT ,
ANTONIO MONTALBÁN  and
NOAH SCHWEBER
JULIA KNIGHT
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF NOTRE DAME NOTRE DAME, IN, USAE-mail: [email protected]: http://math.nd.edu/people/faculty/julia-f-knight/
ANTONIO MONTALBÁN
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CALIFORNIA BERKELEY, CA, USAE-mail: [email protected]: www.math.berkeley.edu/∼antonio
NOAH SCHWEBER
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF CALIFORNIA BERKELEY, CA, USAE-mail: [email protected]: http://www.math.berkeley.edu/∼schweber
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we investigate connections between structures present in every generic extension of the universe V and computability theory. We introduce the notion of generic Muchnik reducibility that can be used to compare the complexity of uncountable structures; we establish basic properties of this reducibility, and study it in the context of generic presentability, the existence of a copy of the structure in every extension by a given forcing. We show that every forcing notion making ω2 countable generically presents some countable structure with no copy in the ground model; and that every structure generically presentable by a forcing notion that does not make ω2 countable has a copy in the ground model. We also show that any countable structure ${\cal A}$ that is generically presentable by a forcing notion not collapsing ω1 has a countable copy in V, as does any structure ${\cal B}$ generically Muchnik reducible to a structure ${\cal A}$ of cardinality ℵ1. The former positive result yields a new proof of Harrington’s result that counterexamples to Vaught’s conjecture have models of power ℵ1 with Scott rank arbitrarily high below ω2. Finally, we show that a rigid structure with copies in all generic extensions by a given forcing has a copy already in the ground model.

Keywords

generic presentabilitygeneric reducibilityHarrington’s Theorem
Type
Articles
Information
The Journal of Symbolic Logic , Volume 81 , Issue 3 , September 2016 , pp. 814 - 832
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. and Knight, J., Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland, Amsterdam, 2000.Google Scholar
Barwise, J., Back and forth through infinitary logic , Studies in Model Theory, Studies in Mathematics, vol. 8, Mathematical Association of America, Buffalo, 1973, pp. 5–34.Google Scholar
Barwise, J., Admissible Sets and Structures, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-New York, 1975.Google Scholar
Baldwin, J., Friedman, S.-D., Koerwien, M., and Laskowski, M. C., Three red herrings around Vaught’s conjecture, Transactions of the American Mathematical Society , to appear.Google Scholar
Calvert, W., Knight, J., and Millar, J., Computable trees of Scott rank $\omega _1^{CK}$ , and computable approximation, this Journal, vol. 71 (2006), no. 1, pp. 283–298.Google Scholar
Delhommé, C., Pouzet, M., Sági, G., and Sauer, N., Representation of ideals of relational structures . Discrete Mathematics, vol. 309 (2009), no. 6, pp. 1374–1384.CrossRefGoogle Scholar
Fraïssé, R., Theory of Relations, revised edition, Studies in Logic and the Foundations of Mathematics, vol. 145, North-Holland, Amsterdam, 2000.Google Scholar
Greenberg, N., Hamkins, J. D., Hirschfeldt, D., and Miller, R., Effective Mathematics of the Uncountable, Lecture Notes in Logic, Cambridge University Press, Cambridge, 2013.Google Scholar
Hodges, W., A Shorter Model Theory, Cambridge University Press, Cambridge, 1997.Google Scholar
Igusa, G. and Knight, J., Comparing two versions of the reals, submitted.Google Scholar
Jech, T., Set Theory, The third millennium edition, revised and expanded, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003.Google Scholar
Kaplan, I. and Shelah, S., Forcing a countable structure to belong to the ground model, on the arXiv at http://arxiv.org/abs/1410.1224.Google Scholar
Karp, C., Finite-quantifier equivalence , Theory of Models ( Proc. 1963 Internat. Sympos. Berkeley ), North-Holland, Amsterdam, 1965, pp. 407–412.Google Scholar
Keisler, H. J., Model Theory for Infinitary Logic: Logic with Countable Conjunctions and Finite Quantifiers, Studies in Logic and the Foundations of Mathematics, vol. 62, North-Holland, Amsterdam–London, 1971.Google Scholar
Larson, P., Scott processes, on the arXiv at http://arxiv.org/abs/1407.1920.Google Scholar
Laskowski, M. C. and Shelah, S., On the existence of atomic models, this Journal, vol. 58 (1993), no. 4, pp. 1189–1194.Google Scholar
Macintyre, A. and Marker, D., Degrees of recursively saturated models . Transactions of the American Mathematical Society, vol. 282 (1984), no. 2, pp. 539–554.Google Scholar
Montalbán, A., A robuster Scott rank, Proceedings of the American Mathematical Society , to appear.Google Scholar
Morley, M., The number of countable models, this Journal, vol. 35 (1970), pp. 14–18.Google Scholar
Millar, J. and Sacks, G., Atomic models higher up . Annals of Pure and Applied Logic, vol. 155 (2008), no. 3, pp. 225–241.Google Scholar
Rabin, M., Computable algebra, general theory and theory of computable fields . Transactions of the American Mathematical Society, vol. 95 (1960), pp. 341–360.Google Scholar
Richter, L., Degrees of structures, this Journal, vol. 46 (1981), no. 4, pp. 723–731.Google Scholar
Sacks, G., Bounds on weak scattering . Notre Dame Journal of Formal Logic, vol. 48 (2007), no. 1, pp. 5–31.Google Scholar
Scott, D., Logic with denumerably long formulas and finite strings of quantifiers , Theory of Models ( Proc. 1963 Internat. Sympos. Berkeley ), North-Holland, Amsterdam, 1965, pp. 329–341.Google Scholar
Solovay, R., A model of set-theory in which every set of reals is Lebesgue measurable . Annals of Mathematics ( 2 ), vol. 92 (1970), pp. 1–56.CrossRefGoogle Scholar
Zapletal, J., Reducibility invariants in higher set theory, in preparation, available on the author’s website.Google Scholar