$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?

up vote 6 down vote accepted

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.

Does this answer your question?

  • 2
    Note that my interpretation of your question here is not the same as my interpretation of your similar question mathoverflow.net/questions/220101/… - I'm pretty sure this is what you mean in this question, but I don't know how to interpret your other question. – Noah Schweber Oct 5 '15 at 21:22
  • Is it true also for $WKL$ that adding induction does not add sets? – Frode Bjørdal Oct 5 '15 at 22:16
  • 2
    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
  • In particular, may we assume that WKL with full induction does not prove the existence of the set of the Gödel numbers of formulas that it proves? – Frode Bjørdal Oct 5 '15 at 22:40
  • 2
    @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

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.