Université McMaster, 5 - 8 décembre 2014
In recent work, Diamondstone, Downey, Greenberg and Turetsky prove that a degree is FIP if it computes a Cohen 1-generic, and that the converse holds in the $\Delta^0_2$ case. We present a priority-free construction that directly ties 1-genericity to FIP, and that shows that the converse holds in general. This provides what might be the first instance of a classical theorem of mathematics whose computability theoretic strength aligns exactly with the ability to compute a 1-generic.
A more subtle priority argument also shows that the a priori weaker 2IP property is also equivalent to being able to compute a 1-generic, and hence to FIP.
In this talk, we will introduce generic Muchnik reducibility, and examine the question mentioned above. We show that the answer to this question (when made precise) is in general "no," although the answer is "yes" if we assume that $B$ has cardinality at most $\aleph_1$. We will also show how these ideas lead to a new proof of a theorem of Harrington, that a counterexample to Vaught's conjecture must have models of cardinality $\aleph_1$ with Scott rank arbitrarily high below $\omega_2$.
This is joint work with Julia Knight and Antonio Montalban.