MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I've been thinking for a while about different ways two Turing degrees might be "independent" of each other (from the point of view of computability theory). The simplest such notion would be to say that they have no information in common: $ d_0\wedge d_1= $ 0. This is a very natural notion.

A different notion of independence that I've been playing around with, is the following: say that degrees $d_0$, $d_1$ are independent if $$ \forall A\in d_0,\forall B\in d_1, A\Delta B\equiv_T A\oplus B$$ (where "$\Delta$" denotes symmetric difference). The intuition behind this definition is that two sets are independent if there is no way to lay sets equivalent to them over each other and "cancel out" any of the information contained in them. Note that this is equivalent to asking that $\forall A, C\in d_0, \forall B, D\in d_1, A\Delta B\equiv_T C\Delta D$.

This is a somewhat odd notion of independence. For instance, a strong minimal cover of a degree $d$ is a degree $e>_T d$ such that for all $a<_T e$, $a\le_T d$. Under this definition, if $e$ is a strong minimal cover of $d$ then $e$ and $d$ are independent: since for $A\in e, B\in d$, we have $(A\Delta B)\oplus B\equiv_T A\oplus B\equiv_T A>_T B$, so $A\Delta B\not \le_T B$, but since $A>_T B$ we have $A\ge_T A\Delta B$, so $A\Delta B\equiv_T A\equiv_T A\oplus B$ since $e$ is a strong minimal cover of $d$. Also, this version of independence is not obviously definable in the u.s.l. of Turing degrees. Still, I've found it interesting to play with, but I haven't made much progress towards understanding it, so my question is: has this (or anything like this) been looked at, and more generally, what are some sources on the possible degrees of the symmetric differences of sets from prescribed degrees?

share|cite|improve this question
I don't see how you got from $(A\Delta B)\oplus B>_TB$ to $A\Delta B>_TB$. Fortunately, it's clear how to get to $A\Delta B\not\leq_TB$, and that suffices for your argument. – Andreas Blass Jan 2 '13 at 15:08
Argh, quite right, fixed. – Noah Schweber Jan 2 '13 at 17:42

I think we can work out the basic properties of this notion right here. Let $\mathbf{d_0}$ and $\mathbf{d_1}$ be our degrees.

  1. In the following situation $\mathbf{d_0}$ and $\mathbf{d_1}$ are not independent:

    $$(\exists \mathbf{r}, \mathbf{a}, \mathbf{b})(\mathbf{r} \in \mathbf{d_0} \land_T \mathbf{d_1} \;\&\; \mathbf{r} \oplus \mathbf{a} \equiv_{T} \mathbf{d_0} \;\&\; \mathbf{a} \oplus \mathbf{d_1} \ngeq_{T} \mathbf{d_0}$$

    Proof: Consider $D_0=R\oplus A$ and $D_1=R \oplus D_1$. $D_0\Delta D_1 = A \oplus D_1 \ngeq_T D_0 \leq_T D_0 \oplus D_1$

  2. If $(\exists \mathbf{r})(\mathbf{r} \in \mathbf{d_0} \land_T \mathbf{d_1})$ with $\mathbf{r}$ of hyperimmune degree then $\mathbf{d_0}$ and $\mathbf{d_1}$ are not independent. If $\mathbf{r}$ is of hyperimmune degree then it computes a weakly 1-generic. Divide this weakly 1-generic into 5 mutually weakly 1-generic components and call this set $G=g_0\oplus g_1 \oplus g_2 \oplus g_3 \oplus g_4$. Now we build $D'_0$ as follows. If $g_1(n)=1$ then set $D'_0(n)=g_0(n)$. If $g_1(n)=0$ and this is the $k$-th $0$ encountered let $D'_0(n)=D_0(n)$. Define $D'_1$ similarly with $g_3,g_4$. Now we claim that $D'_0, g_2,D'_1$ are mutually weakly generic. To see this observe that if it is possible to extend an initial segment of length $l$ of these reals to meet a $\Sigma^0_1$ dense set then it is possible to extend a length $l$ segment of the reals $g_0\oplus g_1 \oplus g_2 \oplus g_3 \oplus g_4$ so that $g_0,g_2,g_4$ are extended by whatever sequence would extend $D'_0, g_2,D'_1$ to meet the dense set and $g_1,g_3$ are extended by all 1's so that $D'_0, D'_1$ copies these extensions. But now consider the sets $D'_0 \oplus \emptyset \oplus G$ and $\emptyset \oplus D'_1 \oplus G$. These sets below to $\mathbf{d_0}$ and $\mathbf{d_1}$ but have symetric difference equivalent to $D'_0 \oplus D'_1$. If this could compute $D_0 \oplus D_1$ then $D'_0 \oplus D'_1$ would be able to compute $g_2$. Yet, densely often $g_2$ has the chance to disagree with such a computation so by mutual weak 1-genericity this is a contradiction.

I bet this generalizes out to showing that if the degrees are incomparable and both compute some non-computable set they turn out not to be independent on this notion. However, this might be totally wrong.

share|cite|improve this answer
I don't know, it seems like bounding a sufficiently generic set is crucial to your argument. For instance, what if we take a set $A$ of minimal (noncomputable) degree, and consider sets $X, Y$ of incomparable degrees $d_0, d_1$ which are both strong minimal covers of $deg(A)$ (I'm not certain this can happen, but it seems plausible)? I don't see any room to make an argument like yours, in this setting. (Also, would you object if I changed your "$D_1'$"s, etc. to "$\hat{D_1}$s"? I keep thinking of jumps.) – Noah Schweber Jan 12 '13 at 17:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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