Prove that there exist two languages \(A\) and \(B\) that are Turing-incomparable- that is, where \(A \not{Z} \mathrm{~T} B\) and \(B \not \mathrm{T} A\).

Let \(R \subseteq \mathcal{N}^{k}\) be a \(k\)-ary relation. Say that \(R\) is definable in \(\mathrm{Th}(\mathcal{N},+)\) if we can give a formula \(\phi\) with \(k\) free variables \(x_{1}, \ldots, x_{k}\) such that for all $a_{1}, \ldots, a_{k} \in \mathcal{N}\(, \)\phi\left(a_{1}, \ldots, a_{k}\right)$ is true exactly when \(a_{1}, \ldots, a_{k} \in R\). Show that each of the following relations is definable in \(\operatorname{Th}(\mathcal{N},+)\). A. \(R_{0}=\\{0\\}\) b. \(R_{1}=\\{1\\}\) c. \(R_{-}=\\{(a, a) \mid a \in \mathcal{N}\\}\) d. \(R_{<}=\\{(a, b) \mid a, b \in \mathcal{N}\) and \(a

Give a model of the sentence $$ \begin{aligned} \phi_{e q}=& \forall x\left[R_{1}(x, x)\right] \\ & \wedge \forall x, y\left[R_{1}(x, y) \leftrightarrow R_{1}(y, x)\right] \\ & \wedge \forall x, y, z\left[\left(R_{1}(x, y) \wedge R_{1}(y, z)\right) \rightarrow R_{1}(x, z)\right] \end{aligned} $$

Describe two different Turing machines, \(M\) and \(N\), where \(M\) outputs \(\langle N\rangle\) and \(N\) outputs \(\langle M\rangle\), when started on any input.

In Corollary \(4.18\), we showed that the set of all languages is uncountable. Use this result to prove that languages exist that are not recognizable by an oracle Turing machine with an oracle for \(A_{\mathrm{TM}}\).

Let \(S=\\{\langle M\rangle \mid M\) is a TM and $L(M)=\\{\langle M\rangle\\}\\} .\( Show that neither \)S\( nor \)\bar{S}$ is Turing-recognizable.