[proofplan]
We first identify the computable [Turing degree](/page/Turing%20Degree) as the least degree, since a computable set can be decided without using any oracle. We then define the [Turing reducibility](/page/Turing%20Reducibility) notation used in the proof and prove that the expression $\deg_T(A \oplus B)$, where $A \oplus B$ is the [Turing join](/page/Turing%20Join), depends only on the degrees of $A$ and $B$, not on the representatives chosen. Finally, we show that $A \oplus B$ computes both components and that any oracle computing both components also computes their join, which proves the least-upper-bound property.
[/proofplan]
[step:Identify the computable degree as the least element]
Let $\mathcal{D}_T$ denote the partially ordered set of [Turing degrees](/page/Turing%20Degree), ordered by [Turing reducibility](/page/Turing%20Reducibility) of representatives. For subsets $X,Y \subset \mathbb{N}$, write $X \leq_T Y$ to mean that an oracle Turing machine with oracle $Y$ decides membership in $X$. Write $X \equiv_T Y$ to mean that both $X \leq_T Y$ and $Y \leq_T X$ hold. For degrees $d = \deg_T(X)$ and $e = \deg_T(Y)$, write $d \leq e$ when $X \leq_T Y$; this is the order relation on $\mathcal{D}_T$. Define $\mathbf{0} := \deg_T(\varnothing)$, the Turing degree of the empty subset $\varnothing \subset \mathbb{N}$. If $C \subset \mathbb{N}$ is computable, then $C \equiv_T \varnothing$, because a Turing machine can decide membership in $C$ without making any oracle queries, and $\varnothing \leq_T C$ by the same oracle-ignoring computation.
Now let $A \subset \mathbb{N}$ be arbitrary. Since $\varnothing$ is computable, $\varnothing \leq_T A$: the deciding machine for $\varnothing$ ignores its oracle and rejects every input. Hence
\begin{align*}
\mathbf{0} = \deg_T(\varnothing) \leq \deg_T(A).
\end{align*}
Thus $\mathbf{0}$ is the least element of $\mathcal{D}_T$.
[/step]
[step:Show that the join operation is independent of representatives]
Let $A,A',B,B' \subset \mathbb{N}$ satisfy $A \equiv_T A'$ and $B \equiv_T B'$. For any subsets $X,Y \subset \mathbb{N}$, define their [Turing join](/page/Turing%20Join) $X \oplus Y \subset \mathbb{N}$ by
\begin{align*}
X \oplus Y := \{2n : n \in X\} \cup \{2n+1 : n \in Y\}.
\end{align*}
With this definition, we prove
\begin{align*}
A \oplus B \equiv_T A' \oplus B'.
\end{align*}
Because $A \leq_T A'$, there is an oracle Turing machine $M_A$ which decides membership in $A$ using oracle $A'$. Because $B \leq_T B'$, there is an oracle Turing machine $M_B$ which decides membership in $B$ using oracle $B'$.
Construct an oracle Turing machine $M$ with oracle $A' \oplus B'$ as follows. On input $m \in \mathbb{N}$, first decide whether $m$ is even or odd. If $m = 2n$, simulate $M_A$ on input $n$. Whenever $M_A$ asks whether $k \in A'$, the machine $M$ asks its oracle whether $2k \in A' \oplus B'$. If $m = 2n+1$, simulate $M_B$ on input $n$. Whenever $M_B$ asks whether $k \in B'$, the machine $M$ asks its oracle whether $2k+1 \in A' \oplus B'$.
This computes $A \oplus B$ from $A' \oplus B'$, so
\begin{align*}
A \oplus B \leq_T A' \oplus B'.
\end{align*}
Applying the same construction with the reductions $A' \leq_T A$ and $B' \leq_T B$ gives
\begin{align*}
A' \oplus B' \leq_T A \oplus B.
\end{align*}
Therefore $A \oplus B \equiv_T A' \oplus B'$.
[guided]
The issue in this step is that $a \vee b$ is supposed to be a degree, not a construction depending on particular sets. Thus, if we replace $A$ by a Turing-equivalent set $A'$ and $B$ by a Turing-equivalent set $B'$, we must prove that the resulting joins have the same degree.
Assume $A \equiv_T A'$ and $B \equiv_T B'$. Recall that $A \equiv_T A'$ means $A \leq_T A'$ and $A' \leq_T A$, and that $A \leq_T A'$ means there is an oracle Turing machine with oracle $A'$ deciding membership in $A$. Similarly, $B \equiv_T B'$ means $B \leq_T B'$ and $B' \leq_T B$. From $A \leq_T A'$, choose an oracle Turing machine $M_A$ deciding $A$ with oracle $A'$. From $B \leq_T B'$, choose an oracle Turing machine $M_B$ deciding $B$ with oracle $B'$.
We now build a single reduction from $A \oplus B$ to $A' \oplus B'$. The join separates the two components by parity:
\begin{align*}
2n \in A \oplus B &\iff n \in A, \\
2n+1 \in A \oplus B &\iff n \in B.
\end{align*}
Likewise,
\begin{align*}
2k \in A' \oplus B' &\iff k \in A', \\
2k+1 \in A' \oplus B' &\iff k \in B'.
\end{align*}
On input $m \in \mathbb{N}$, if $m = 2n$, we need to decide whether $n \in A$. We simulate $M_A$ on input $n$. When $M_A$ asks its oracle whether $k \in A'$, we answer that question by asking the oracle $A' \oplus B'$ whether $2k \in A' \oplus B'$. This gives exactly the same answer because the even positions of $A' \oplus B'$ encode $A'$.
If $m = 2n+1$, we need to decide whether $n \in B$. We simulate $M_B$ on input $n$. When $M_B$ asks whether $k \in B'$, we ask the oracle $A' \oplus B'$ whether $2k+1 \in A' \oplus B'$. This gives exactly the same answer because the odd positions of $A' \oplus B'$ encode $B'$.
Therefore the constructed oracle machine decides $A \oplus B$ using oracle $A' \oplus B'$, and hence
\begin{align*}
A \oplus B \leq_T A' \oplus B'.
\end{align*}
Repeating the identical construction with the reductions $A' \leq_T A$ and $B' \leq_T B$ gives
\begin{align*}
A' \oplus B' \leq_T A \oplus B.
\end{align*}
Thus
\begin{align*}
A \oplus B \equiv_T A' \oplus B',
\end{align*}
so $\deg_T(A \oplus B)$ depends only on $\deg_T(A)$ and $\deg_T(B)$.
[/guided]
[/step]
[step:Show that the join computes both components]
Let $A,B \subset \mathbb{N}$. Define $J := A \oplus B$. We show
\begin{align*}
A \leq_T J
\quad \text{and} \quad
B \leq_T J.
\end{align*}
To decide whether $n \in A$ using oracle $J$, query whether $2n \in J$. By the definition of $J$,
\begin{align*}
2n \in J \iff n \in A.
\end{align*}
Hence $A \leq_T J$.
Similarly, to decide whether $n \in B$ using oracle $J$, query whether $2n+1 \in J$. By the definition of $J$,
\begin{align*}
2n+1 \in J \iff n \in B.
\end{align*}
Hence $B \leq_T J$.
Therefore
\begin{align*}
\deg_T(A) \leq \deg_T(A \oplus B)
\quad \text{and} \quad
\deg_T(B) \leq \deg_T(A \oplus B),
\end{align*}
so $\deg_T(A \oplus B)$ is an upper bound for $\deg_T(A)$ and $\deg_T(B)$.
[/step]
[step:Show that every common upper bound computes the join]
Let $c \in \mathcal{D}_T$ be a common upper bound of $\deg_T(A)$ and $\deg_T(B)$. Choose a representative $C \subset \mathbb{N}$ with $c = \deg_T(C)$. Since $c$ is a common upper bound, we have
\begin{align*}
A \leq_T C
\quad \text{and} \quad
B \leq_T C.
\end{align*}
Choose oracle Turing machines $N_A$ and $N_B$ such that $N_A$ decides $A$ using oracle $C$, and $N_B$ decides $B$ using oracle $C$.
Construct an oracle Turing machine $N$ with oracle $C$ deciding $A \oplus B$. On input $m \in \mathbb{N}$, if $m = 2n$, run $N_A$ on input $n$ with oracle $C$. If $m = 2n+1$, run $N_B$ on input $n$ with oracle $C$. This decides membership in $A \oplus B$, because
\begin{align*}
m \in A \oplus B
\iff
\begin{cases}
n \in A, & \text{if } m = 2n, \\
n \in B, & \text{if } m = 2n+1.
\end{cases}
\end{align*}
Hence
\begin{align*}
A \oplus B \leq_T C.
\end{align*}
Therefore
\begin{align*}
\deg_T(A \oplus B) \leq c.
\end{align*}
[/step]
[step:Conclude that the Turing degrees form an upper semilattice]
By the representative-independence step, the assignment
\begin{align*}
(a,b) \mapsto \deg_T(A \oplus B),
\end{align*}
where $A \in a$ and $B \in b$, is well-defined on Turing degrees. By the upper-bound step, this degree is an upper bound for $a$ and $b$. By the leastness step, it is below every common upper bound of $a$ and $b$.
Thus every pair $a,b \in \mathcal{D}_T$ has a least upper bound, namely
\begin{align*}
a \vee b = \deg_T(A \oplus B).
\end{align*}
Together with the least element $\mathbf{0}$ established above, this proves that the partially ordered set of Turing degrees is an upper semilattice with least element.
[/step]
