Suppose $\kappa< 2^{\aleph_0}$ and $\langle P_i : i < \kappa\rangle$ is a sequence of perfect subsets of $2^{\omega}$. Can we find $Q_i \subseteq P_i$ for $i < \kappa$ such that each $Q_i$ is perfect and for every $x_i \in Q_i$ (for $i < \kappa$), the set $\{x_i: i < \kappa\}$ is Turing independent?

  • 1
    $\begingroup$ Can you clarify exactly what sense of Turing independence you mean? Do you mean just that they are pairwise non-computable from each other, or do you mean something more? $\endgroup$ – Joel David Hamkins May 22 at 13:57
  • 1
    $\begingroup$ Hi @dan, welcome to mathoverflow, and thanks for your interesting question! $\endgroup$ – Dominic van der Zypen May 22 at 17:49
  • $\begingroup$ @喻良 That is fascinating! Can you link to a reference? I suggest you post an answer. $\endgroup$ – Joel David Hamkins May 27 at 10:14
  • $\begingroup$ @Joel, sorry, I misunderstood Dan's question. Groszek and Slaman's result can be found here: (ams.org/tran/1983-277-02/S0002-9947-1983-0694377-4/…) $\endgroup$ – 喻 良 May 27 at 11:19

If Martin's axiom holds, then the answer is yes. In particular, under the continuum hypothesis, the answer is yes. In any case, the answer is yes when $\kappa$ is countable. More generally, the answer is yes if $\text{MA}_\kappa$ holds. (See update below for improvements.)

Let's consider the case first that $\kappa$ is countable. Suppose that we have countably many perfect sets $\langle P_n\mid n\in\omega\rangle$, each of which is the set of branches through a perfect tree $T_n$, so that $P_n$ consists of the branches through $T_n$.

I propose to refine these trees using the construction method of this answer, in order to construct perfect subtrees $S_n\subseteq T_n$ whose sets of branches $Q_n$ will be the desired perfect refinements with pairwise Turing incompatible branches.

Specifically, we build the subtrees $S_n$ in a sequence of stages. At each stage, we are committed to only finitely much information altogether about which nods are in $S_n$, and at each stage, we end-extend the current approximation to $S_n$. At a given stage, we consider whether a given program $e$ might compute a branch through $S_m$ using an oracle that is a branch through $S_n$. Call this requirement $R_{e,n,m}$.

We can meet this requirement by extending the branches of $S_n$ sufficiently so that program $e$ determines a branch higher than the current branches we have promised about $S_m$, in such a way that we can extend our promise of $S_m$ to the next stage so as to avoid it. In this way, we are fulfilling requirement $R_{e,n,m}$.

I am not saying that this process is computable, since perhaps no extension of the current promise to $S_n$ will enable $e$ to halt sufficiently; but the point is that in this case, we needn't worry about this program, since it will not be giving us a branch through $S_m$. So I am computing the subtrees using the jumps of the oracles.

We can also fold in stages of the construction to ensure that the trees $S_n$ are all branching, so that each $Q_n$ will be a perfect set.

In this way, in $\omega$ many stages, we construct the perfect refinements $Q_n\subseteq P_n$ so that no real in $Q_n$ computes any real in $Q_m$ for $n\neq m$, as desired. We can even arrange the construction so that no branch through any $S_n$ computes any other distinct branch through any $S_m$, including $n=m$.

Now, consider the case of general $\kappa$, under the assumption that $\text{MA}_\kappa$ holds. In this case, we can consider the forcing to add the subtrees $S_n$ with finite conditions, each specifying a finite piece of $S_n$ inside $T_n$, with finite support, ordered by end-extension. This forcing is isomorphic to adding $\kappa$ many Cohen reals, and is therefore c.c.c. Thus, by Martin's axiom, there is a way of choosing the subtrees so as to meet all the requirements $R_{e,\alpha,\beta}$, for Turing programs $e$ and distinct $\alpha,\beta<\kappa$. Each requirement corresponds to a dense set in the forcing, and there are only $\kappa$ many requirements.

Update. I've now realized several improvements.

Let us call your principle the perfect set refinement property ($\text{PSR}_\kappa$).

Theorem. The perfect set refinement property $\text{PSR}_\kappa$ follows from $\text{MA}_\kappa(\text{Cohen})$.

Proof. The principle $\text{MA}_\kappa(\text{Cohen})$ is the very weak version of Martin's axiom, which applies only to the forcing $\text{Add}(\omega,1)$ that adds a single Cohen real. Fix any family of perfect sets $P_\alpha$ for $\alpha<\kappa$. Consider the forcing to add a single Cohen real. Such forcing adds a size-continuum family of pairwise mutually generic Cohen reals $c_\alpha$ for $\alpha<\mathfrak{c}$. Use these reals to pick out perfect subtrees $S_\alpha\subset T_\alpha$. By the argument above, paths through these trees will be Turing incomparable. And so we will have realized our desired family in the extension by adding a Cohen real. The actual properties needed in this argument are only the $\kappa$ many dense sets corresponding to the pairwise independence. So we don't need an actual Cohen real, but only $\text{MA}_\kappa(\text{Cohen})$. $\Box$

Theorem. $\text{PSR}_\kappa$ holds after forcing to add $\theta$ many Cohen reals, for any $\theta\geq\kappa^+$.

Proof. Suppose $G$ is $V$-generic for the forcing to add $\theta$ many Cohen reals, where $\theta\geq\kappa^+$. If $\langle P_\alpha\mid\alpha<\kappa\rangle$ is a family of perfect sets, then this sequence is added by the restriction of $G$ to a set of size $\kappa$. On one of the remaining coordinates, we have added a Cohen real generically over that part of $G$, and so we have created the desired perfect refinement already in $V[G]$. $\Box$

Corollary. One can force the full perfect set refinement property, $\text{PSR}_\kappa$ for all $\kappa<\mathfrak{c}$, simply by adding sufficiently many Cohen reals.

Meanwhile, one might ask why the OP has insisted that $\kappa<\mathfrak{c}$. The reason is that allowing $\kappa$ to be the continuum itself (or larger) makes the principle false.

Theorem. $\text{PSR}_\kappa$ is false for $\kappa\geq\mathfrak{c}$.

Proof. For each real $x$, there is a perfect set $P_x$ of reals $y$ such that $x\leq_T y$. Consider any perfect refinement $Q_x\subseteq P_x$. Let $y\in Q_x$ and consider any $z\in Q_y$. It follows that $y\leq_T z$, and so these are not Turing independent. So there is no independent perfect refinement of this continuum-sized family. $\Box$

  • $\begingroup$ The argument shows how to force instances of the perfect refinement with c.c.c. forcing. Indeed, the forcing argument works even when you have continuum many perfect sets; you can refine them to perfect subsets in a forcing extension, where any choice of paths are pairwise Turing incomparable. $\endgroup$ – Joel David Hamkins May 22 at 17:37
  • $\begingroup$ If you add mutually generic perfect subtrees $S_\alpha$ to $T_\alpha$, then you will achieve the pairwise independence property by genericity. So any given sequence of perfect sets can be refined as desired in a c.c.c. forcing extension. I would like to combine that observation with some kind of absoluteness result to conclude that we already had such a refinement without forcing; but I'm not sure how to make such an argument work. $\endgroup$ – Joel David Hamkins May 23 at 10:01
  • $\begingroup$ In light of the results at the end, if you want to force the PSR property to fail, you have to pump up the continuum, but not by having added Cohen reals, since that will force it to hold. This could either be taken as a direction to seek out another kind of forcing, or as evidence that the principle is outright provable. I'm not sure which way it will go. $\endgroup$ – Joel David Hamkins May 23 at 13:53

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.