Baby Rudin's Proof in Theorem 2.8

Question

2.8 Theorem Every infinite subset of a countable set $A$ is countable

Proof Suppose $E \subset A$, and $E$ is infinite. Arrange the elements $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_{n1} \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 1-1 correspondence between $E$ and $J$.

---

I am confused why $x$ should be distinct in paragraph 1 and does my understanding right?

Rudin first let $A = ${$x_{1}, x_{2}, ...$} for convenient. Then chooses some elements randomly in $A$, for example, $x_{2}, x_{5}, x_{6}, ...$ which constrct $E$. Then $n_{1} = 2, n_{2}=5, n_{3} = 6, ...$. Therefore $E = $ {$x_{n_{k}}:x_{n_{k}}=f(k), k = 1, 2, 3, ...$} ~ $\mathbb{N}$.

Answer 1

A sequence of elements from $A$ could, in principle, have repetition. For example, $\{1,2,1,3,1,4,1,\ldots\}$ is a sequence of integers, but not a sequence of distinct integers.

If the element $1$ were in $E$, the above sequence would mess up the second part of the proof, because we would choose it over and over again from our sequence, unless we put in more language about letting $n_k$ be the smallest integer greater than $n_{k-1}$ such that $x_{n_k}\in E$ and $x_{n_k}\ne x_{n_j}$ for all $j<k$. If we make $A$ a non-repeating sequence, then we don't have to worry about such things.

Your understanding of the proof seems right, modulo that one point, which is hopefully clarified now. :)

Answer 2

First maybe you already know, the set $A$ contains distinct elements. This is a standard notion, for example $\{1,1,2\}$ and $\{1,2\}$ are the same set, so we may assume that $A$ has distinct elements.

Next the important part, a sequence is not just a set. To construct a sequence from a set $A$, it is essentially defining a map $$f: \mathbb{N} \rightarrow A.$$ For an easy example, if $A=\{a,b\}$, we would like to construct a sequence, we might define $$x_1 = a, x_2 = b, x_3 = a, x_4 = a \cdots$$ but this is the same thing as defining a map $f:\mathbb{N} \rightarrow A$ $$f(1) = a, f(2) = b, f(3) = a, f(4) = a, \cdots.$$

Here we want this map to be injective, so $f$ can not map two different integers to the same element of $A$, thus "each element in the sequence is distinct".