5
$\begingroup$

I have come across multiple research papers where they have mentioned that two 1-generic reals $x$ and $y$ can be constructed such that $x \oplus y \equiv_{T} \textbf{0}'$, where $\textbf{0}'$ is the degree containing the halting set. I was wondering how to prove this fact.

I know some basic computability theory and some facts about generic reals such as there exists low generic reals and that every 1-generic real $x$ can be broken down into $x = x_0 \oplus x_1$ such that $x_0$ and $x_1$ are 1-generic relative to each other. I was wondering if this was enough to prove my above question or is there some other necessary theorems to know about.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
7
$\begingroup$

Let us construct $x$ and $y$ in stages from oracle $0'$, so that they are both $1$-generic, but $x\oplus y$ will code $0'$. We specify the binary digits of $x,y$ in stages. At the first stage, we specify finitely many of $x$ so as to meet the first $\Sigma_1$ definable set, if possible, and we make $y$ all-zeros up to the same length, followed by a $1$ and then the first bit of $0'$, and then extend $y$ further so as to meet the first $\Sigma_1$ definable set, if possible. At the next stage, extend $x$ with all zeros up to the length of $y$ so far, followed by a $1$, and then get into the second $\Sigma_1$ definable set, if possible. And so forth. At each stage, we extend to get into the next dense set, but the other one has all zeros on that block, followed by a $1$, and another coded bit of $0'$.

Each of them is $1$-generic, since they met all the $\Sigma_1$-definable dense sets, but with $x,y$ together we can recognize the all-zero blocks and therefore also the coding bits, and so we can compute $0'$ from $x\oplus y$.

Here is a picture, where the generic reals being constructed are $c,d$, and together they are coding $z$. enter image description here

This argument is the same idea as used in the nonamalgamation phenomenon for forcing over countable models. See my papers Upward closure and amalgamation in the generic multiverse of a countable model of set theory, and Set-theoretic blockchains.

Improve this answer
$\endgroup$

You must log in to answer this question.