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.

  • $\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$ 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$ 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$ 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$ Mar 5, 2020 at 7:57

1 Answer 1


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).


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.