Non null Turing antichain

Question

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

Answer 1

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

http://ims.nju.edu.cn/~yuliang/lcpfinal

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.

Answer 2

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