Need explanation about the proof of theorem 2.12 in baby Rudin: the union of a sequence of infinite, countable sets is countable.

Question

While reading Walter Rudin's Principles of Mathematical Analysis, I ran into the following theorem and proof:

Theorem 2.12. Let $\left\{E_n\right\}$, $n=1,2,\dots$, be a sequence of countable sets, and put

$$ S=\bigcup_{n=1}^\infty E_n. $$

Then $S$ is countable.

Proof. Let every set $E_n$ be arranged in a sequence $\left\{X_{nk}\right\}$, $k=1,2,3,\dots$, and consider the infinite array

                                                            

in which the elements of $E_n$ form the $n$th row. The array contains all elements of $S$. As indicated by the arrows, these elements can be arranged in a sequence

$$ x_{11};x_{21},x_{12};x_{31},x_{22},x_{13};x_{41},x_{32},x_{23},x_{14};\dots\tag{*} $$

If any two of the sets $E_n$ have elements in common, these will appear more than once in $(*)$. Hence there is a subset $T$ of the set of all positive integers such that $S\sim T$, which shows that $S$ is at most countable. Since $E_1\subset S$, and $E_1$ is infinite, $S$ is infinite, and thus countable. $\blacksquare$

One accepted answer has been provided in the link, The union of a sequence of infinite, countable sets is countable., which is,

Look at the sequence *

$x_{11};x_{21},x_{12};x_{31},x_{22},x_{13};x_{41},x_{32},x_{23},x_{14};…$

Within each ;; add the suffixes.

1+1 =2

2+1 = 1+2 = 3

1+3 = 2+2 = 3+1 = 4

and so on.

So for any positive integer you shall get a countable (finite) number of such combination and in each case you shall get elements of $S$. If you remove duplicate items then you shall get a set $S$. This set will be bijective with the set of natural numbers as for each natural number you shall get only a finite number of elements.

I hope it is clear now. The bold sequence is constructed by taking arrows in the matrix. In the matrix the elements of the set $E_i$ are written in arrow.

I understand there is a bijective mapping from N to the collection of subsets of S, each of which is formed by taking points between two consecutive ;; in (*). Because the set of En is countable, the collection of such subsets is countable, by the construction of the subsets. The part I don't understand in the answer is that,

This set will be bijective with the set of natural numbers as for each natural number you shall get only a finite number of elements.

Even after removing duplicates, what we have still a bijective, mapping from N to a collection of subsets of S, whose union is equal to S. What is theorem or definition in baby Rudin that implies the existence of such bijective mentioned in the answer?

Thanks,

Answer 1

This traditional picture of the ''countably infinite rectangular array'' might serve to give a certain description of what is going on, but it certainly doesn't make for a very clean and elegant proof. Let us then try to indicate a more succinct argumentation for

Theorem. Let $A$ be a sequence (indexed by $\mathbb{N}$) of countably infinite sets. Then $$\bigcup_{n \in \mathbb{N}} A_n$$ is also countably infinite.

Proof: Let us employ the following lemmas:

Lemma 1. Any infinite subset of $\mathbb{N}$ is equipotent to (i.e. of the same cardinality as) $\mathbb{N}$.

It is not difficult to supply a proof for this, let me know if you were interested in seeing one.

Lemma 2. $\mathbb{N} \times \mathbb{N}$ and $\mathbb{N}$ are equipotent.

proof of lemma: on the one hand, $\mathbb{N} \times \mathbb{N}$ clearly embeds $\mathbb{N}$ (set $A$ is said to embed set $B$ if there exists an injection from $B$ to $A$) so the cartesian product is infinite; on the other hand, the map: $$\mathbb{N} \times \mathbb{N} \to \mathbb{N} \\ (m,n) \mapsto 2^m3^n$$ is seen to be an injection esentially thanks to the fundamental theorem of arithmetic (the uniqueness of prime factor decompositions); therefore, $\mathbb{N} \times \mathbb{N}$ will have the same cardinality as an infinite subset of $\mathbb{N}$ hence as that of $\mathbb{N}$, by virtue of lemma 1.

Coming back to the context of the theorem, set $$\bigcup_{n \in \mathbb{N}}A_n=B$$ Since $B$ includes the infinite set $A_0$ it itself is infinite; on the other hand we have the relation: $$|B| \leqslant \left|\bigsqcup_{n \in \mathbb{N}} A_n\right|=\sum_{n \in \mathbb{N}}|A_n|=\sum_{n \in \mathbb{N}}|\mathbb{N}|=|\mathbb{N}|^2=|\mathbb{N}^2|=|\mathbb{N}|$$ by virtue of lemma 2, so $B$ is seen to be equipotent to an infinite subset of $\mathbb{N}$, therefore itself equipotent to $\mathbb{N}$ by another application of lemma 1.

The inequality in the relation above is a particular case of the general statement that $$\left|\bigcup_{i \in I} A_i\right| \leqslant \left|\bigsqcup_{i \in I} A_i\right|$$ in other words the cardinal of a union of a family of sets is always at most equal to the cardinal of the disjoint union of the respective family of sets. $\Box$

Answer 2

Suppose $\phi:\Bbb N\to T$ is surjective, where $T$ is a family of finite subsets of $S$ and $\cup T=S.$ For each $n\in \Bbb N$ the set $B_n$ of bijections from $\phi(n)$ into $\Bbb N$ is non-empty. By the Axiom of Choice there exists $\{b_n:n\in \Bbb N\}$ where $b_n\in B_n$ for each $n\in \Bbb N.$

Now for $s\in S,$ let $H(s)$ be the least $n\in \Bbb N$ such that $s\in \phi(n),$

and let $P(s)=(\cup_{(j<H(s))}\phi(j))\;\cup \;\{t:H(t)=H(s)\land b_{H(s)}(t)\le b_{H(s)}(s)\},$

and let $f(s)$ be the number of members of $P(s).$

Then $f$ is a bijection from $S$ to $\Bbb N$ or a bijection from $S$ to an initial segment $\{j\in \Bbb N:j<m\}$ of $\Bbb N$ for some $m\in \Bbb N.$

The idea is to impose a linear order $<^*$ on $S$ where $s'<^*s$ if

(i). $H(s')<H(s),$ or

(ii). $H(s)=H(s')=n$ and $b_n(s')<b_n(s).$

Then $<^*$ is actually a well-order, and for each $s,$ the set $\{s':s'<^*s\}$ is finite, so $(S,<^*)$ must be order-isomorphic to $\Bbb N$ or to an initial segment of $\Bbb N...$ And $f(s)$ is the number of members of $\{s':s'<^*s \lor s'=s\}.$

Answer 3

As mentioned in my comment above, may I suggest a version of the argument produced by Daniel Wainfleet (I dare say a more concise one).

We want to prove the following specific result

Proposition: the union of a sequence of finite sets is countable.

Proof: By countable set I mean one that is embeddable in $\mathbb{N}$ (this includes the case of the empty set, which is vacuously countable by there being nothing to count in it).

It will suffice to show that the disjoint union of a sequence $A$ of finite sets is countable. In the same vein of the idea above consider the cartesian product $$\prod_{n \in \mathbb{N}} \mathscr{Tot}(A_n)$$ where by $\mathscr{Tot}(M)$ we mean the set of all total orders on given set $M$; such a set is never empty, hence our cartesian product will contain an element say $T$; in other words, for each $n \in \mathbb{N}$ we have that $T_n$ is a total order on $A_n$.

Consider now the ordinal sum of the sequence of ordered sets $((A_n, T_n))_{n \in \mathbb{N}}$ taken with respect to the standard order on the index set $\mathbb{N}$; as the ordinal sum of a family of well-ordered sets indexed by well-ordered index set, this ordinal sum itself will be a well-ordered set; furthermore, since all the terms $A_n$ in the sequence are finite, any proper initial segment of this well-ordered ordinal sum is clearly finite. Hence, by virtue of the fundamental theorem of well-ordered sets (that given two such objects one of them is necessarily isomorphic to an initial segment of the other), as $\mathbb{N}$ cannot be isomorphic to any proper initial segment of the ordinal sum, it follows that it is the ordinal sum that must be isomorphic to an initial segment of $\mathbb{N}$, in other words that the disjoint union $$\bigsqcup_{n \in \mathbb{N}} A_n$$ which is the support-set of the ordinal sum is embeddable in $\mathbb{N}$. $\Box$

Answer 4

Rudin uses $J$ for the positive integers and defines 'set size stuff' in Definition 2.4, so that $J$ is countable and countable means infinite.

---

Rudin proves

2.8 $\;$ Theorem $\;$ Every infinite subset of a countable set is countable.

A subset of $J$ is either finite or infinite. If it is infinite then by the above theorem it is countable. So any subset of $J$ is at most countable.

This allows Rudin to argue what the OP put in bold typeset.

---

The OP should also give some thought to Rudin's statement

The book is on real analysis and not concerned with a rigorous presentation of set theory; see Dedekind infinite set.