(a) Define the halting set $\mathbb{K}$. Prove that $\mathbb{K}$ is recursively enumerable, but not recursive.

(b) Given $A, B \subseteq \mathbb{N}$, define a many-one reduction of $A$ to $B$. Show that if $B$ is recursively enumerable and $A \leqslant_{m} B$, then $A$ is also recursively enumerable.

(c) Show that each of the functions $f(n)=2 n$ and $g(n)=2 n+1$ are both partial recursive and total, by building them up as partial recursive functions.

(d) Let $X, Y \subseteq \mathbb{N}$. We define the set $X \oplus Y$ via

$$X \oplus Y:=\{2 x \mid x \in X\} \cup\{2 y+1 \mid y \in Y\}$$

(i) Show that both $X \leqslant_{m} X \oplus Y$ and $Y \leqslant_{m} X \oplus Y$.

(ii) Using the above, or otherwise, give an explicit example of a subset $C$ of $\mathbb{N}$ for which neither $C$ nor $\mathbb{N} \backslash C$ are recursively enumerable.

(iii) For every $Z \subseteq \mathbb{N}$, show that if $X \leqslant_{m} Z$ and $Y \leqslant_{m} Z$ then $X \oplus Y \leqslant_{m} Z$.

[Note that we define $\mathbb{N}=\{0,1, \ldots\}$. Any use of Church's thesis in your answers should be explicitly stated.]