Omega-model of WWKL consisting of random reals

Question

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?

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.