Notion of independence of Turing degrees

Question

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?

Answer 1

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.

Answer 2

Rather belatedly, I should probably mention that Uri Andrews, Peter Gerdes, Steffen Lempp, Joe Miller, and I have written a paper on this: Computability and the symmetric difference operator (DOI); see also these slides of Peter.

In particular, we proved that there are incomparable r.e. degrees ${\bf a},{\bf b}$ with well-defined symmetric difference degree but for which there is also an r.e. ${\bf c}<_T{\bf a\oplus b}$ such that ${\bf c\oplus a}\ge_T{\bf b}$ and ${\bf c\oplus b}\ge_T{\bf a}$. The general question of which nonzero r.e. degrees are one half of a "symmetric pair" is still open; Peter(?) conjectured that the answer is the promptly simple degrees, but I dont' know enough about that topic to have an opinion.