1
$\begingroup$

How do I prove this function is injective and surjective:

$$h(n)=\begin{cases}f((n+1)/2),&\text{ if }n\text{ is odd}\\ g(n/2),&\text{ if }n\text{ is even}\end{cases}$$

  • 2
    what are $f$ and $g$?2012-09-17
  • 1
    You can't prove that this function is injective or surjective, without knowing some details about $f$ and $g$. Can you please post the whole question?2012-09-17

1 Answers 1

3

The details will depend on $f$ and $g$, but the general procedure is no different from the one that you’d use if the function were not defined by cases.

To show that $h$ is injective, show that if $h(m)=h(n)$, then $m=n$. This potentially involves considering three cases: $m$ and $n$ both odd, $m$ and $n$ both even, and one of $m$ and $n$ odd and the other even.

To show that $h$ is surjective (onto what set?), you have to show that for each $x$ in the codomain of $h$ there is an integer $n$ such that $h(n)=x$. Typically this will be done by working out what things are in the ranges of $f$ and $g$ and showing that each $x$ in the codomain of $h$ really can be ‘hit’ by one of the cases.

  • 0
    @Ben: Sorry; I was writing another answer and didn’t think before I wrote my last (now deleted) comment. Of course there’s no problem here, for the reason that you mentioned in parentheses, and I took that to be obvious.2012-09-17
  • 0
    @Ben: But I’ve revised the wording slightly to avoid the problem without getting excessively detailed or formal.2012-09-17
  • 0
    Okay, I went ahead and deleted my comments (they didn't make sense anymore in any case)2012-09-17