Computable structures in generic extensions

DOI10.1017/JSL.2015.30MaRDI QIDQ2976365zbMATH OpenOpenAlexFDO

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

Publication date 28 April 2017

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

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)

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.

Recommendations

• Generic Muchnik reducibility and presentations of fields
• Computing strength of structures related to the field of real numbers
• Computability in structures representing a Scott set
• Generic copies of countable structures
• An introduction to the Scott complexity of countable structures and a survey of recent results

Cites work

• scientific article; zbMATH DE number 3467077 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• A model of set-theory in which every set of reals is Lebesgue measurable
• Atomic models higher up
• Bounds on weak scattering
• Computable structures and the hyperarithmetical hierarchy
• Effective Mathematics of the Uncountable
• Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers
• Representation of ideals of relational structures

Cited in

(15)

• Characterizations of cancellable groups
• Computing strength of structures related to the field of real numbers
• Feedback computability on Cantor space
• EXPANDING THE REALS BY CONTINUOUS FUNCTIONS ADDS NO COMPUTATIONAL POWER
• Generic copies of countable structures
• Computability in structures representing a Scott set
• Complexity profiles and generic Muchnik reducibility
• Forcing a countable structure to belong to the ground model
• scientific article; zbMATH DE number 4154430 (Why is no real title available?)
• 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
• An introduction to the Scott complexity of countable structures and a survey of recent results

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)