# If $R(x,y)$ is a recursive relation, then $\exists y\leq 2$ such that $R(x,y)$ is recursive

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$?

• 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? Commented Oct 13, 2017 at 8:05
• 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).
– chi
Commented Oct 13, 2017 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.