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

  • 1
    $\begingroup$ Could it be that $\dfrac12n$ was intended where $\dfrac12$ appears in the piecewise definition of $g$? $\endgroup$ Jan 13 '13 at 1:44
  • 1
    $\begingroup$ Note that $g$ is not the same function as $f$: $g(3)=1$, but $f(3)=10$. $\endgroup$ Jan 13 '13 at 1:46
  • $\begingroup$ 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(!) $\endgroup$
    – Seraphina
    Jan 13 '13 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?

  • $\begingroup$ 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'? $\endgroup$
    – Seraphina
    Jan 13 '13 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.