If $R(x,y)$ is a recursive relation, then $\exists y\leq 2$ such that $R(x,y)$ is recursive - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-22T05:55:58Z https://cs.stackexchange.com/feeds/question/82399 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/82399 1 If $R(x,y)$ is a recursive relation, then $\exists y\leq 2$ such that $R(x,y)$ is recursive Sid Caroline https://cs.stackexchange.com/users/72757 2017-10-13T01:38:38Z 2017-10-13T08:31:11Z <p>The theorem says: If $R(x,y)$ is a recursive relation, then there exists $y\leq2$ such that $R(x,y)$ is recursive.</p> <p>Here is my attempt of proof:</p> <p>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$.</p> <p>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)$.</p> <p>Is this enough? Can I generalize this for any values of $y$ or does this only apply for when $y\leq 2$?</p> https://cs.stackexchange.com/questions/82399/if-rx-y-is-a-recursive-relation-then-exists-y-leq-2-such-that-rx-y-i/82405#82405 1 Answer by fade2black for If $R(x,y)$ is a recursive relation, then $\exists y\leq 2$ such that $R(x,y)$ is recursive fade2black https://cs.stackexchange.com/users/72943 2017-10-13T08:31:11Z 2017-10-13T08:31:11Z <p>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$. </p> <p>Formally, recall that a relation $R(x,y)$ is recursive if its characteristic function </p> <p>$$c_R(x,y) = \begin{cases} 1 &amp; \text{ if } \langle x,y \rangle \in R \\ 0 &amp; \text{ if } \langle x,y \rangle \notin R \end{cases}$$ is recursive. </p> <p>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.</p>