First get a feel for the rule by tabulating a few values. Non-negative integers go to even labels and negative integers go to odd labels:
| n | −3 | −2 | −1 | 0 | 1 | 2 | 3 |
|---|
| h(n) | 5 | 3 | 1 | 0 | 2 | 4 | 6 |
That observation — the two branches never produce the same kind of number — is what makes the whole proof work.
(i) h is one-one.
Suppose h(n1)=h(n2). There are three cases.
Case 1: both n1,n2≥0. Then 2n1=2n2, so n1=n2.
Case 2: both n1,n2<0. Then −2n1−1=−2n2−1, so −2n1=−2n2 and again n1=n2.
Case 3: one of each. Say n1≥0 and n2<0. Then h(n1)=2n1 is even, while h(n2)=−2n2−1 is an even number minus 1, hence odd. An even number is never equal to an odd number, so h(n1)=h(n2) is impossible in this case — it simply cannot arise.
In every case that can occur we reached n1=n2, so h is one-one.
(ii) h is onto.
Take any m∈W. Since m is a whole number it is either even or odd, and each case names its own preimage.
Case m even. Write m=2k with k=2m. Since m≥0 we have k≥0, so k satisfies the condition of the first branch, and
h(k)=2k=m
Case m odd. Write m=2k+1 with k≥0, and take
n=−(k+1)
Since k≥0 we have k+1≥1, so n≤−1 and n really is negative — the condition of the second branch. Therefore
h(n)=−2n−1=−2(−(k+1))−1=2(k+1)−1=2k+1=m
Every m∈W has a preimage in Z, so h is onto. Together with (i), h is a bijection.
(iii) Restricting to n≥0.
The restricted function is h0:W→W with h0(n)=2n, since only the first branch survives.
Still one-one. The argument of Case 1 above is untouched: 2n1=2n2 gives n1=n2.
No longer onto. Every output 2n is even, so no odd label is ever produced. For instance 1∈W would need 2n=1, that is n=21, which is not a whole number. So 1 has no preimage.
Throwing away the negative integers has cost exactly the odd labels — which is precisely what the second branch was producing.
