$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?
$\begingroup$
$\endgroup$
asked Oct 5, 2015 at 20:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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?
answered Oct 5, 2015 at 21:19
-
2$\begingroup$ 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. $\endgroup$ Oct 5, 2015 at 21:22
-
$\begingroup$ Is it true also for $WKL$ that adding induction does not add sets? $\endgroup$ Oct 5, 2015 at 22:16
-
2$\begingroup$ 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. $\endgroup$ Oct 5, 2015 at 22:18
-
$\begingroup$ 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? $\endgroup$ Oct 5, 2015 at 22:40
-
2$\begingroup$ @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'$.) $\endgroup$ Oct 5, 2015 at 22:42