[proofplan] We prove reflexivity by building the identity oracle procedure: to decide membership in $A$ using oracle $A$, ask the oracle the input question and return its answer. For transitivity, we compose oracle computations by simulation. A machine deciding $A$ from $B$ is simulated, and each simulated query to $B$ is answered by running a machine deciding $B$ from $C$; termination follows because the outer computation makes only finitely many oracle queries on each input, and each inner computation halts. [/proofplan] [step:Decide a set from itself by one oracle query] Let $A \subseteq \mathbb N$. Define an oracle Turing machine $R$ as follows. On input $n \in \mathbb N$ and with oracle $A$, the machine $R^A$ queries its oracle on $n$ and outputs the returned bit. Since the oracle answer is $1$ exactly when $n \in A$ and $0$ exactly when $n \notin A$, the function computed by $R^A$ is \begin{align*} \mathbb{1}_A: \mathbb N &\to \{0,1\}. \end{align*} Thus $A \le_T A$. [/step] [step:Compose two oracle reductions by nested simulation] Let $A,B,C \subseteq \mathbb N$ and assume $A \le_T B$ and $B \le_T C$. By the definition of Turing reducibility, there is an oracle Turing machine $M$ such that $M^B$ decides $\mathbb{1}_A: \mathbb N \to \{0,1\}$, and there is an oracle Turing machine $N$ such that $N^C$ decides $\mathbb{1}_B: \mathbb N \to \{0,1\}$. We construct an oracle Turing machine $P$ with oracle $C$. On input $n \in \mathbb N$, the machine $P^C$ simulates the computation of $M$ on input $n$. Whenever the simulated machine $M$ asks its oracle whether some $q \in \mathbb N$ belongs to $B$, the machine $P^C$ runs $N^C$ on input $q$. Since $N^C$ decides $B$, this inner computation halts and outputs $\mathbb{1}_B(q)$. The machine $P^C$ then supplies that bit as the answer to the simulated oracle query of $M$ and continues the simulation. For each fixed input $n$, the computation $M^B(n)$ halts because $M^B$ decides $A$. During this halting computation, only finitely many oracle queries are made; denote their queried inputs, in the order encountered along the actual computation path, by $q_1,\dots,q_k \in \mathbb N$, where $k \ge 0$. For each $i \in \{1,\dots,k\}$, the computation $N^C(q_i)$ halts and returns $\mathbb{1}_B(q_i)$, exactly the answer that oracle $B$ would give. Therefore the simulation by $P^C$ follows the same sequence of configurations as $M^B(n)$ and halts with the same output. Hence \begin{align*} P^C(n) = M^B(n) = \mathbb{1}_A(n). \end{align*} Since this holds for every $n \in \mathbb N$, $P^C$ decides $A$, so $A \le_T C$. [guided] We need to show that a computation of $A$ from $B$ and a computation of $B$ from $C$ can be combined into one computation of $A$ from $C$. The difficulty is that the first machine is allowed to ask questions about $B$, but the final machine is only allowed to ask questions about $C$. The solution is to answer each question about $B$ by running the second reduction. Formally, since $A \le_T B$, there exists an oracle Turing machine $M$ such that, with oracle $B$, the computation $M^B(n)$ halts for every $n \in \mathbb N$ and outputs $\mathbb{1}_A(n)$. Since $B \le_T C$, there exists an oracle Turing machine $N$ such that, with oracle $C$, the computation $N^C(q)$ halts for every $q \in \mathbb N$ and outputs $\mathbb{1}_B(q)$. Define a new oracle Turing machine $P$ using oracle $C$. On input $n \in \mathbb N$, the machine $P^C$ begins simulating $M$ on input $n$. If the simulated computation of $M$ performs an ordinary Turing-machine step, then $P^C$ performs the corresponding simulated step. If the simulated computation asks its oracle whether $q \in B$, then $P^C$ runs the machine $N^C$ on input $q$. This inner computation is legitimate because $P$ has access to oracle $C$, and it halts because $N^C$ decides $B$. Its output is $\mathbb{1}_B(q)$, which is exactly the bit that oracle $B$ would have returned to $M$. The machine $P^C$ supplies this bit to the simulation of $M$ and continues. It remains to justify termination. Fix $n \in \mathbb N$. Because $M^B$ decides $A$, the computation $M^B(n)$ halts after finitely many steps. In particular, along this actual computation path it makes finitely many oracle queries, say $q_1,\dots,q_k \in \mathbb N$, with $k \ge 0$. For each queried input $q_i$, the computation $N^C(q_i)$ halts and outputs $\mathbb{1}_B(q_i)$. Thus every simulated oracle query is answered after finite time, and every answer supplied by $P^C$ agrees with the answer supplied by the true oracle $B$. Consequently the simulated computation inside $P^C(n)$ follows exactly the same branch as $M^B(n)$. Since $M^B(n)$ halts and outputs $\mathbb{1}_A(n)$, the machine $P^C(n)$ also halts and outputs $\mathbb{1}_A(n)$. Therefore \begin{align*} P^C(n) = \mathbb{1}_A(n) \end{align*} for every $n \in \mathbb N$. Hence $P^C$ decides $A$, so $A \le_T C$. [/guided] [/step] [step:Conclude that Turing reducibility is a preorder] The first step proves reflexivity of $\le_T$ on $\mathcal P(\mathbb N)$, and the second step proves transitivity of $\le_T$ on $\mathcal P(\mathbb N)$. Therefore Turing reducibility is a preorder. [/step]