I'm studying Real Analysis using Robert Bartle's text Elements of Real Analysis.

Wonder if I could get some help on understanding the proof of the following theorem:

The following statements are equivalent: (a) S is a countable set. (b) There exists a surjection of $\Bbb{N}$ onto S. (c) There exists an injection of S into $\Bbb{N}$

Proof. (a) $\Rightarrow$ (b) If $S$ is finite, there exists a bijection $h$ of some set $\Bbb{N}_n$ on $S$ and we define H on $\Bbb{N}$ by

$$ H(k) = \left\{ \begin{array}{ll} h(k) & \quad k = 1,...,n, \\ h(k) & \quad k > n \end{array} \right. $$

Then $H$ is a surjection of $\Bbb{N}$ onto $S$.

If $S$ is a denumerable, there exists a bijection $H$ of $\Bbb{N}$ onto $S$, which is also a surjection of $\Bbb{N}$ onto $S$.


The part of the proof that I do not understand is: $h(k)$ for $k>n$. Why is there a need for this piecewise of the function? How is it defined? In the sense that, if set $S = \text{{A,B,C,D}}$, then there exists a bijection $h$ of set $\Bbb{N}_4$ on $S$ (which is then, $H$ is a surjection of $\Bbb{N}$ onto $S$). Why then $h(k)$ for $k>n$? How to map a surjection of $\Bbb{N}$ onto $S$ for $k>4$ when $S$ only have 4 elements?

I feel like I'm missing a point here but couldn't quite point out what it is?


As you correctly observe, it does not make sense to define $H(k)=h(k)$ for $k>n$ since $h(k)$ is not defined in that case. I'm guessing this is just a typo, and it means to say $h(1)$ instead of $h(k)$ in that case. That is, you pick some particular element of $S$ (say the first one according to $h$, namely $h(1)$) and define $H(k)$ to be that particular element for all $k>n$.

(Incidentally, there is still an error here: $h(1)$ is only defined if $n>0$. Indeed, the statement being proved is not quite true: you need to assume $S$ is nonempty. If $S$ is empty, then $S$ is countable, but there is no surjection $\mathbb{N}\to S$, since there is no function $\mathbb{N}\to S$ at all.)


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.