# Does $WKL_0$ provide more comprehension than $RCA_0$?

$WKL_0$ extends $RCA_0$ with the statement that any infinite subset of the infinite binary tree has an infinite branch. Does $WKL_0$ Prove that there are sets which are not proven to exist by the $\Delta_0$-comprehension schema of $RCA_0$? If so, to what level of comprehension do such sets belong?

If I understand your question correctly, the answer is "no" in the following sense:

Fix a model $M=(\omega_M, \mathbb{R}_M)$ of $RCA_0$, and let $\mathcal{C}_M$ be the set of structures $N=(\omega_N, \mathbb{R}_N)$ such that

• $N\models WKL_0$,

• $\omega_N=\omega_M$ (same first-order parts), and

• $\mathbb{R}_N\supseteq\mathbb{R}_M$ ($N$ is gotten by adding sets to $M$).

Then we have:

• $\mathcal{C}_M$ is nonempty. (This is due to Harrington, and is how he shows that $WKL_0$ is $\Pi^1_1$-conservative over $RCA_0$.)

• $\bigcap_{N\in\mathcal{C}_M} \mathbb{R}_N=\mathbb{R}_M$. That is, there is no specific set which must be added when we expand $M$ to a model of $WKL_0$. (This is a direct consequence of the proof of Jockusch and Soare's Low Basis Theorem, but I don't know who first explicitly observed this.)

In particular, the intersection of all the Scott sets is precisely $REC$, the set of recursive sets.

• Is it true also for $WKL$ that adding induction does not add sets? – Frode Alfson Bjørdal Oct 5 '15 at 22:16
• Well, it depends what you mean by "does not add sets," but the argument at the end of my answer to your other question will still work with $WKL_0$ in place of $RCA_0$ - so I think the answer is "yes." In fact, I can't off the top of my head think of a reasonable theory over which that argument won't work, but I could be wrong. – Noah Schweber Oct 5 '15 at 22:18
• @FrodeBjørdal Yes, that is true. (Although in that specific case the argument is easier - all you need is that there is a Scott set not containing $0'$.) – Noah Schweber Oct 5 '15 at 22:42