I've been trying to show, as an exercise, that over $\mathrm{RCA_0}$ weak weak Kőnig's lemma (WWKL) does not imply weak Kőnig' lemma (WKL). I've been working on it by constructing an $\omega$-model that is the smallest Turing ideal $I$ closed under taking a relativized 1-random (i.e., Martin-Löf random) real. The idea is $I$ will not be a Scott set. (I may be wrong on this point.)

But I've been unable to show that $I$ models WWKL. I don't know how to match the computability-theoretic and measure-theoretic conditions imposed on a positive-measure $\Pi^0_1$ class and a Martin-Löf test. The first paper to show the nonimplication of WKL by WWKL, Measure theory and weak Kiinig's lemma, by Simpson and Yu, does talk about an $\omega$-model that sounds like $I$, but in their paper they consider a Turing ideal containing a real which is a member of every measure one "$\Delta^1_1$ class". I'm not sure what it means nor whether it's the same concept as the familiar 1-randomness. (Why is it $\Delta$, not $\Sigma$ or $\Pi$? Do they mean effective $F_\sigma$ or $G_\delta$ sets?)

What are $\omega$-models that model WWKL and $\neg$WKL, and why do they do so?


1 Answer 1


You want to start with the following characterizations in mind:

  • An $\omega$-model $M$ satisfies WKL if and only if for every $X$ in $M$ there is a $Y$ in $M$ that is PA over $X$ (that is, $Y$ computes a path through every infinite $\{0,1\}$ tree computable from $X$).

  • An $\omega$-model $M$ satisfies WWKL if and only if for every $X$ in $M$ there is a $Y$ in $M$ that is 1-random over $X$.

In general, if $Y$ is PA over $X$ then $Y$ computes a real that is 1-random over $X$. Hence every $\omega$-model of WKL is an $\omega$-model of WWKL.

On the other hand, although it seems counterintuitive, there are 1-random reals that compute $0'$, and thus some 1-random reals do have PA degree. Not every 1-random real has PA degree, however.

The idea of the model construction is that we form a Turing ideal generated by a sequence $(Y_n)$ of reals, each 1-random over all the sets computable from the previous ones. We need to control the sequence so that we don't accidentally make a model of WKL. Because some 1-random reals do have PA degree, if we want to make an $\omega$-model of WWKL that is not an $\omega$-model of WKL, we can't just throw arbitrary 1-random reals into the model.

The method that Simpson and Yu seem to use is to choose reals $Y_n$ that are much more random than just 1-random. I don't have a copy of their paper at hand, but I hope that this helps orient you in how to read their proof.

A class of reals is $\Delta^1_1$ if and only if it is (lightface) Borel. The lightface Borel classes include the $\Pi^0_n$ and $\Sigma^0_n$ classes for all $n \in \omega$. Simpson and Yu look at reals that are in every lightface $\Delta^1_1$ class of measure one. These reals will in particular be 1-random, because they will in particular be in every lightface $G_\delta$ class of measure 1 (these are just $\Pi^0_2$ classes). However, these super-random reals should also be random enough - and this is what Simpson and Yu must verify - that they don't have PA degree.

There is an enormous amount of background material on computability and randomness, and it takes a while to learn the technical details. The book by Downey and Hirschfeldt has summaries on page 337 of some of what I wrote here. The material on lightface Borel classes is utterly standard in computability and effective descriptive set theory, but I don't know a reference off the top of my head, unfortunately.

  • $\begingroup$ "Simpson and Yu look at reals that are in every lightface $\Delta^1_1$ class" - do you mean every lightface measure one $\Delta^1_1$ class? $\endgroup$ Mar 23, 2016 at 4:05
  • $\begingroup$ @Noah, yes, of course, thanks. $\endgroup$ Apr 3, 2016 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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