I am puzzling over a sentence in an example in a textbook, showing that a function $f$, defined by cases, is primitive recursive.
Let $E$ be the set of even natural numbers. The function $f$ defined by
$$ f(n) = \begin{cases} \frac12n,&\text{if }n\in E\\\\ 3n + 1,& \text{if }n \notin E \end{cases}$$
is primitive recursive.
Now let $g: \mathbb{N} \longrightarrow \mathbb{N}$ be the function defined by
$$g(n)=\begin{cases} \frac12n,&\text{if }n\in E\\\\ \frac12(n-1),&\text{if }n\notin E\;. \end{cases}$$
My understanding is that the function $g$ has been picked, because it does the same thing as $f$, and also because it is easier to convert into primitive recursive form. Am I right?
This is the sentence that is puzzling me:
'We observe that $g(n+1) = g(n)$ if $n+1$ is odd and $g(n+1)=g(n)+1$ if $n+1$ is even'
I'm sure the thinking behind this is incredibly simple, and I've just experienced a moment of blindness. For example, has this observation come about through substitution, or am I looking at it the wrong way? Some illumination would be fantastic- and any alternative proofs. Just one final note- would I be right in understanding that there are lots of different ways of writing a function $f$ which determines whether $n$ is odd or even (defined by two cases)?
The proof concludes: we have $n+1 = \operatorname{succ}(n)$, so $g$ can be defined by the equations
$$\begin{align*} &g(0)=0\\ &g(n+1) = g(n) + \chi_E(\operatorname{succ}(n))\;. \end{align*}$$
If $n+1$ is odd, then $g(n+1)=\frac12\big((n+1)-1\big)=\frac12n=g(n)$, while if $n+1$ is even, then $g(n+1)=\frac12(n+1)=\frac12\big((n-1)+2\big)=\frac12(n-1)+1=g(n)+1$, since $n$ is odd.
However, $g$ and $f$ are clearly not the same function, as can be seen by evaluating them at any odd natural number. I’m not sure exactly what you mean by ‘a function $f$ which determines whether $n$ is odd or even (defined by two cases)’. Do you mean a function $f$ such that by looking at $f(n)$ (perhaps in conjunction with $n$) one can infer the parity of $n$, like $\chi_E$? Or do you simply mean one whose definition requires two cases, one to cover odd arguments and the other to cover even arguments?