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
    Commented Oct 13, 2017 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
    Commented Oct 13, 2017 at 14:08

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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