1
$\begingroup$

Given a function E(x) which outputs 0 is x is even and 1 is x is odd, prove that this function is primitive recursive.

My attempt is as follows

$$ E(x) = x \mod 2$$ To show that any function is primitive recursive, it must be obtained by composition and recursion from the initial functions $s(x) = x + 1; n(x) = 0$ and $u_i^n(x_1,x_2 \ldots x_n) = x_i$
We know that $$ E(0) = 0 $$ $$ E(x+1) = (E(x) + 1) \mod 2 $$ By using induction -
$$ E(n) = n \mod 2$$ Let $n = 0$ $$ E(0) = 0$$ which is easily shown to be primitive recursive since it is an initial function of the $PRC$ class.
Assuming that this is true for $n = k$. $$E(k) = k \mod 2$$ Taking $ n = k+1 $ $$ E(k+1) = (E(k) + 1)\mod 2 $$

But at this point, I do not know how to proceed.

Improve this question
$\endgroup$
4
  • $\begingroup$ I'll give you two hints. (1) When you said "by using induction" what is the precise statement you proved by induction? It is not "$E$ is primitive recursive". (2) Why did you not simply write down the primitive recursive construction of $E$? You should make a definition of $E$ using only $s$, $n$, $u_i^n$, but in your attempt I see no such thing. It should start with "$E(x) = \cdots$" where $\cdots$ mentions only $E$, $s$, $n$, $u_i^n$ and previously defined primitive recursive functions. $\endgroup$ Commented Mar 5, 2020 at 7:22
  • $\begingroup$ (2) I don't know what the primitive construction of $ E(x) $. (1) I thought that if $E(0)$ is primitive recursive and E(k + 1) is proven to be primitive recursive then $E(x)$ will be primitive recursive by induction principle. $\endgroup$ Commented Mar 5, 2020 at 7:28
  • $\begingroup$ It is meaningless to say "$E(0)$ is primitive recursive" You can only say "$E$ is primitive recursive." Primitive recursiveness is a property of functions, and not of their values. You do not understand the definition of primitive recursive, it seems. You should first try to demonstrate that $f(x) = x + 3$ is primitive recursive, to make sure you understand the definition. $\endgroup$ Commented Mar 5, 2020 at 7:54
  • $\begingroup$ Maybe an example will help. Define $f(x,y) = x + 2$. Then we can prove that $f$ is primitve recursive as follows: $f$ is primitive recursive because $f = s \circ s \circ u_1^2$, or written a bit less mysteriously, because $f(x,y) = s(s(u_1^2(x,y)))$ for all $x, y$. This is the sort of proof you need to do. Induction might help after you have written $E$ using only the building blocks for primitive recursive functions. $\endgroup$ Commented Mar 5, 2020 at 7:57

1 Answer 1

Reset to default
0
$\begingroup$

Define a function $a(x)$ by primitive recursion as follows: $a(0) = s(0)$ and $a(x+1) = 0$. In particular, this function satisfies $a(0) = 1$ and $a(1) = 0$. Now we can define $E(x)$ by primitive recursion: $E(0) = 0$ and $E(x+1) = a(E(x))$. You can prove that $E(x)$ works by induction (left to you).

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.