Publication:2976365

DOI10.1017/JSL.2015.30zbMATH Open1388.03042arXiv1405.7456OpenAlexW2342149294MaRDI QIDQ2976365FDOQ2976365

Noah Schweber, J. F. Knight, Antonio Montalbán

Publication date: 28 April 2017

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

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 {em generic Muchnik reducibility} that can be used to to compare the complexity of uncountable structures; we establish basic properties of this reducibility, and study it in the context of {em generic presentability}, the existence of a copy of the structure in every extension by a given forcing. We show that every forcing notion making $omeg{a}_2$ countable generically presents some countable structure with no copy in the ground model; and that every structure generically presentble by a forcing notion that does not make $omeg{a}_2$ countable has a copy in the ground model. We also show that any countable structure $mathcalA$ that is generically presentable by a forcing notion not collapsing $omeg{a}_1$ has a countable copy in $V$, as does any structure $mathcalB$ generically Muchnik reducible to a structure $mathcalA$ of cardinality $alep{h}_1$. The former positive result yields a new proof of Harrington's result that counterexamples to Vaught's conjecture have models of power $alep{h}_1$ with Scott rank arbitrarily high below $omeg{a}_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.

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

zbMATH Keywords

generic Muchnik reducibilitygeneric presentabilityHarrington's theorem

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Other aspects of forcing and Boolean-valued models (03E40) Other degrees and reducibilities in computability and recursion theory (03D30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A model of set-theory in which every set of reals is Lebesgue measurable
• Computable structures and the hyperarithmetical hierarchy
• Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers
• Effective Mathematics of the Uncountable
• Representation of ideals of relational structures
• Atomic models higher up
• Bounds on weak scattering

Cited In (13)

• Characterizations of cancellable groups
• EXPANDING THE REALS BY CONTINUOUS FUNCTIONS ADDS NO COMPUTATIONAL POWER
• Complexity profiles and generic Muchnik reducibility
• AN INTRODUCTION TO THE SCOTT COMPLEXITY OF COUNTABLE STRUCTURES AND A SURVEY OF RECENT RESULTS
• Forcing a countable structure to belong to the ground model
• Title not available (Why is that?)
• Model Complete Generic Structures
• Structural properties for feasibly computable classes of type two
• Strong reducibilities and set theory
• Three red herrings around Vaught's conjecture
• Generic Muchnik reducibility and presentations of fields
• COMPUTING STRENGTH OF STRUCTURES RELATED TO THE FIELD OF REAL NUMBERS
• Title not available (Why is that?)

This page was built for publication: COMPUTABLE STRUCTURES IN GENERIC EXTENSIONS

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