February 9
Leszek Kołodziejczyk,
University of Warsaw
An isomorphism theorem for models of Weak Kőnig's Lemma without induction
We prove that any two countable models of the theory ${\rm WKL}^*_0$ sharing the same first-order universe and containing the same counterexample to $\Sigma^0_1$ induction are isomorphic.
This theorem implies that over ${\rm WKL}^*_0 + \neg I\Sigma^0_1$, the analytic hierarchy collapses to the arithmetic hierarchy. It also implies that ${\rm WKL}^*_0$ is the strongest $\Pi^1_2$ statement that is $\Pi^1_1$-conservative over ${\rm RCA}^*_0 + \neg I\Sigma^0_1$. Together with the (slightly subtle) generalizations of the theorem to higher levels of the arithmetic hierarchy, this gives an 'almost negative' answer to a question of Towsner, who asked whether $\Pi^1_1$-conservativity of $\Pi^1_2$ sentences over collection principles is a $\Pi^0_2$-complete computational problem. Our results also have some implications for the reverse mathematics of combinatorial principles: for instance, we get a specific $\Pi^1_1$ sentence that is provable in ${\rm RCA}_0 + B\Sigma^0_2$ exactly if the $\Pi^1_1$ consequences of ${\rm RCA}_0 + {\rm RT}^2_2$ coincide with $B\Sigma^0_2$.
On the side, we also give a positive answer to Towsner's question as originally stated.
Joint work with Marta Fiori Carones, Tin Lok Wong, and Keita Yokoyama.