The theorem says: If $R(x,y)$ is a recursive relation, then there exists $y\leq2$ such that $R(x,y)$ is recursive.

Here is my attempt of proof:

Since $R(x,y)$ is recursive, we can construct a partial recursive function $f:\mathbb{N}^2\rightarrow\mathbb{N}$ be such that $f(x,y)=1$ if $(x,y)\in R$ and $f(x,y)=0$ if $(x,y)\notin R$.

Let $y=2$. Then either $(x,y)\in R$ or $(x,y)\notin R$. So we can just construct a partial recursive function $f'$ that fixes $y=2$ and takes an input $x\in\mathbb{N}$ and runs $f$ on $(x,2)$.

Is this enough? Can I generalize this for any values of $y$ or does this only apply for when $y\leq 2$?

  • $\begingroup$ Do you mean that if $R(x,y)$ is a recursive relation then there is some fixed $y_0 \leq 2$ such that $R(x, y_0)$ is also a recursive relation? $\endgroup$ – fade2black Oct 13 '17 at 8:05
  • $\begingroup$ I think the latter "$R(x,y)$ is recursive" statement actually means "the set $\{x | R(x,y)\}$ is recursive", since $y$ was fixed. Right? The notation can be a bit confusing here: indeed, strictly speaking $R(x,y)$ is not a relation -- $R$ is the (binary) relation, and $R(-,y)$ is the new (unary) relation after $y$ is fixed (i.e. it is now a set). $\endgroup$ – chi Oct 13 '17 at 14:08

Fixing $y$ in $R(x,y)$ results in a special case of the problem "whether $\langle x,y \rangle \in R$", and hence the latter should be no more harder than the general problem of deciding if $\langle x,y \rangle \in R$. So, intuitively if $R(x,y)$ is a recursive relation then $R(x,y_0)$ should also be recursive for some fixed $y_0$.

Formally, recall that a relation $R(x,y)$ is recursive if its characteristic function

$$ c_R(x,y) = \begin{cases} 1 & \text{ if } \langle x,y \rangle \in R \\ 0 & \text{ if } \langle x,y \rangle \notin R \end{cases} $$ is recursive.

Now assume that $R(x,y)$ is recursive. Then $c_R(x,y)$ is also recursive. Let $M(x,y)$ be a TM computing $c_R(x,y)$. For a fixed $y_0$ our new TM $M'(x)$ will take $x$, call $M(x, y_0)$ and return its value. Since $M(x,y)$ computes a recursive function (always returns $0$ or $1$), $M'(x)$ also computes a recursive function, namely $c_R(x,y_0)$. Thus $R(x,y_0)$ is recursive.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.