This interesting question resulted from a query of Mushfeq: In ZFC, can we find a non null set of pairwise Turing incomparable reals?

  • 2
    $\begingroup$ Hmm... I remember I gave a talk about these facts in Madison. Maybe you were not there. But I am sure that Mushfeq was there. $\endgroup$
    – 喻 良
    Sep 22 '15 at 5:42
  • $\begingroup$ I do remember seeing your talk. As soon as I posted this, Mushfeq sent me a link to your paper. His original question was about the existence of a non measurable upward closed (under Turing reduction) set of reals which follows from your result on antichain. I don't know if this is any easier than finding non measurable antichains. $\endgroup$
    – Ashutosh
    Sep 22 '15 at 19:58

This is a $ZFC$-theorem. Actually for any $\Sigma^1_1$-locally countable partial ordering, there is a non-null antichain.

The proof is not quite simple. See my paper


I feel that it might be helpful to give more details.

The idea is as following:

By Harrison's theorem, the question concerning $\Sigma^1_1$-locally countable partial ordering can be reduced to the question about the measure of antichains of hyperarithmetic degrees. So it is sufficient to construct a non-null antichain of hyperarithmetic degree. By an application of some algorithmic randomness results due to Kucera, Miller and me, any such antichain must be nonmeasurable.

So we just need to construct a nonmeasureable antichain of hyperdegrees. By a generlaization of the results due to Miller and me, it can be proved that sufficient randomness (in the paper "sufficient randomness" means $\Delta^1_2$-randomness. Now we know that $\Pi^1_1$-randomness is sufficient after the development of higher randomness theory) is $\leq_h$-downward closed.

Now take a maximal set $X$ of reals so that any two different reals in $X$ bounds disjoint "sufficiently random" reals. If $X$ is not null, then we are done. Otherwise, by the randomness result above, the $\leq_h$-upward closure of $X$ must be null. For each $e$, let $X_e$ be the collection of the $e$-th "sufficiently random" real hyperarithmetically below some $x\in X$ (such an $\omega$-type well ordering is "natural" for each $x$, i.e. the $e$-th hyperarithmetic reduction.) It cannot be true that for every $e$, $X_e$ is null (Otherwise, by the randomness result and maximality of $X$, the set of "sufficiently random" reals would be null). By the property of $X$, $X_e$ is an antichain for every $e$. So there must be some $e_0$ so that $X_{e_0}$ is an antichain and non-null.

Note that even the hyperarithmetic closure of $X_{e_0}$ does not have a positive measure.

Under $MA+\neg CH$, any locally countable partial ordering has a non-null antichain. However, under $V=L$, it fails for the $\Delta^1_2$ well-ordering $\leq_L$. I am not sure about $\Pi^1_1$-locally countable partial orderings.

  • $\begingroup$ Can you give the argument? $\endgroup$ Sep 22 '15 at 1:44
  • $\begingroup$ @Joel. I added more details. $\endgroup$
    – 喻 良
    Sep 22 '15 at 1:47
  • $\begingroup$ Thanks for your paper and sketch. Your last paragraph is a little cryptic, under CH, any well ordering of all reals of order type $\omega_1$ is locally countable but has no antichains. Did you perhaps mean to also require than for each member of the partial order, the set of comparable elements is null? $\endgroup$
    – Ashutosh
    Sep 22 '15 at 20:01
  • $\begingroup$ You are right. It fails under $CH$. Actually we need $MA_{\aleph_1}$ to prove it. $\endgroup$
    – 喻 良
    Sep 22 '15 at 21:51
  • $\begingroup$ Thanks for adding a proof for this. I noticed you mentioned a question (5.3) of Jockusch in your paper about the existence of a null maximal quasi-antichain. Is that still open? $\endgroup$
    – Ashutosh
    Sep 23 '15 at 1:42

This is a great question.

Let me get things started by showing that the answer is yes under the continuum hypothesis. Assume CH. Let $\langle U_\alpha\mid\alpha<\omega_1\rangle$ enumerate all the open sets with less than full measure. I shall build an antichain $\langle a_\alpha\mid\alpha<\omega_1\rangle$ of Turing incomparable reals, which are not contained entirely in any $U_\alpha$. Thus, the set $\{a_\alpha\mid\alpha<\omega_1\}$ will have full outer measure. At any stage of the construction, we will have already specified $a_\beta$ for $\beta<\alpha$, which is countably many reals. Since $U_\alpha$ is an open set with less than full measure, I claim that we may find a real $a_\alpha$ that is not in $U_\alpha$ and which is Turing incomparable with all $a_\beta$ for $\beta<\alpha$. To see this, observe first that if we force to add a random real $r$ not in $U_\alpha$, then $r$ will fit the bill in the forcing extension $V[r]$, since clearly $r$ is not computable from any ground model real, and conversely I believe that no non-computable ground model real is computable from a random real. But next, observe that the existence of such a real is a $\Sigma^1_1$ assertion, and hence it was already true in $V$ by Shoenfield absoluteness. So we may find $a_\alpha\notin U_\alpha$ that is incomparable with all earlier $a_\beta$. Thus, we have built the antichain of Turing incomparable reals, which is not contained in any open set of less than full measure. And so it is not measure zero. QED

  • $\begingroup$ Perhaps we can weaken the CH assumption to a suitable cardinal characteristic assumption. $\endgroup$ Sep 22 '15 at 1:40

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.