An isomorphism theorem for models of Weak König's Lemma without primitive recursion

Abstract

We prove that if $(M,\mathcal{X})$ and $(M,\mathcal{Y})$ are countable models of the theory ${\mathrm{WKL}}_0^{\ast }$ such that $\mathrm{I}{\Sigma }_1(A)$ fails for some $A\in \mathcal{X}\cap \mathcal{Y}$, then $(M,\mathcal{X})$ and $(M,\mathcal{Y})$ are isomorphic. As a consequence, the analytic hierarchy collapses to ${\Delta }_1^1$ provably in ${\mathrm{WKL}}_0^{\ast }+\neg \mathrm{I}{\Sigma }_1^0$, and $\mathrm{WKL}$ is the strongest ${\Pi }_2^1$ statement that is ${\Pi }_1^1$-conservative over ${\mathrm{RCA}}_0^{\ast }+\neg \mathrm{I}{\Sigma }_1^0$. Applying our results to the ${\Delta }_n^0$-definable sets in models of ${\mathrm{RCA}}_0^{\ast }+\mathrm{B}{\Sigma }_n^0+\neg \mathrm{I}{\Sigma }_n^0$ that also satisfy an appropriate relativization of Weak König's Lemma, we prove that for each $n\ge 1$, the set of ${\Pi }_2^1$ sentences that are ${\Pi }_1^1$-conservative over ${\mathrm{RCA}}_0^{\ast }+\mathrm{B}{\Sigma }_n^0+\neg \mathrm{I}{\Sigma }_n^0$ is c.e. In contrast, we prove that the set of ${\Pi }_2^1$ sentences that are ${\Pi }_1^1$-conservative over ${\mathrm{RCA}}_0^{\ast }+\mathrm{B}{\Sigma }_n^0$ is ${\Pi }_2$-complete. This answers a question of Towsner. We also show that ${\mathrm{RCA}}_0+{\mathrm{RT}}_2^2$ is ${\Pi }_1^1$-conservative over $\mathrm{B}{\Sigma }_2^0$ if and only if it is conservative over $\mathrm{B}{\Sigma }_2^0$ with respect to $\forall {\Pi }_5^0$ sentences.

29 pages. Somewhat more polished version compared to v1, with small improvements and simplifications throughout the text but no major mathematical changes. Introduction slightly expanded to point out model-theoretic aspects of the paper