Computable structures in generic extensions

Original · EN

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 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 ω₂ 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 ω₂ countable has a copy in the ground model. We also show that any countable structure A that is generically presentable by a forcing notion not collapsing ω₁ has a countable copy in V, as does any structure B generically Muchnik reducible to a structure A of cardinality ₁. The former positive result yields a new proof of Harrington's result that counterexamples to Vaught's conjecture have models of power ₁ with Scott rank arbitrarily high below ω₂. 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.