# Mod 2 is primitive recursive

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.

• 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. – Andrej Bauer Mar 5 '20 at 7:22
• (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. – Keane Moraes Mar 5 '20 at 7:28
• 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. – Andrej Bauer Mar 5 '20 at 7:54
• 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. – Andrej Bauer Mar 5 '20 at 7:57

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