# Primitive recursive functions and characteristic functions. Methods of proof- examples. Illumination.

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*}

• Could it be that $\dfrac12n$ was intended where $\dfrac12$ appears in the piecewise definition of $g$? Commented Jan 13, 2013 at 1:44
• Note that $g$ is not the same function as $f$: $g(3)=1$, but $f(3)=10$. Commented Jan 13, 2013 at 1:46
• Ah, I did indeed miss out the 'n's! I see that f and g obviously don't do the same thing, but it is presumably no coincidence that g has been written in the way that it has. I think I'll sleep on that and take another look at it tomorrow(!) Commented Jan 13, 2013 at 2:15

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?
• Thanks so much for your answer. I think I can see the thinking behind this now- well, I get how the algebra works anyway, and mostly get the rest of it... In answer to your questions- I am referring to f in the context of inferring the parity of n, i.e. $\chi_E$ This is what I meant by f and g doing the same thing. The overall topic in the textbook that I'm reading is 'characteristic functions'. Just one more thought- presumably $\chi_E$ would only be valid for the two cases 'n even' and 'n odd'? Commented Jan 13, 2013 at 13:56