2014/05/29 by Julia F. Knight, Julia Knight, Antonio Montalbán +5
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computability, Logic, AI Algorithms #FOS: Mathematics #Logic (math.LO) #Mathematical and Theoretical Analysis #math.LO
paper · pdf · doi:10.48550/arxiv.1405.7456
15 pages; submitted
openalex publication_date 2014/05/29 · arxiv created 2014/12/10 · arxiv updated 2014/12/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ω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 ω2 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 ω1 has a countable copy in V, as does any structure B generically Muchnik reducible to a structure 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.