# Rudin's Proof in Theorem 2.8

In Rudin's Principle of Mathematical Analysis, in claims that in Theorem 2.8: Every infinite subset of a countable set $A$ is countable. Could someone explain why the function $f: \mathbb{N} \rightarrow E$ is surjective?

Proof Suppose $E \subset A$, and $E$ is infinite. Arrange the elements of $x$ of $A$ in a sequence $\{x_{n} \}$ of distinct elements. Construct a sequence $\{n_{k} \}$ as follows: Let $n_{1}$ be the smallest positive integer such that $x_{n_{1}} \in E$. Having chosen $n_{1}, ... n_{k-1} (k = 2, 3, 4, ...)$, let $n_{k}$ be the smallest integer greater than $n_{k-1}$ such that $x_{n_{k}} \in E$.

Putting $f(k) = x_{n_{k}} (k = 1, 2, 3, ...)$, we obtain a bijection between $\mathbb{N}$ and $E$.

-
Please insert the text in question so we can see it. –  ncmathsadist Feb 27 '12 at 2:12

If $A$ is a countable set, there is a bijective map $f:\mathbb{N}\to A$, which is the same as an order on the set: $f(1)$ is the first element, then $f(2)$, etc. If you have an infinite subset $E$ of $A$, we can order $E$ by letting $f(1)$ be the first element of $E$ (first with respect to the ordering on $A$, that is). Since every element of $E$ appears somewhere in the ordering on $A$, it will appear either in that spot or closer to the front in the ordering on $E$. (This last sentence tells you that $f:\mathbb{N}\to E$ is surjective.)