Skip to main content
deleted 9 characters in body
Source Link

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)$$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 basically fixfixes $y=2$ and takes an input $(x,y)\in\mathbb{N}^2$$x\in\mathbb{N}$ and runs $f$ on it$(x,2)$.

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

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 basically fix $y=2$ and takes an input $(x,y)\in\mathbb{N}^2$ and runs $f$ on it.

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

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

Source Link

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 basically fix $y=2$ and takes an input $(x,y)\in\mathbb{N}^2$ and runs $f$ on it.

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