Computable structures in generic extensions

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

15 pages; submitted