# Walter Rudin's proof: countable union of countable sets is countable

The capture is from Rudin's Principles of Mathematical Analysis, and I've seen similar proof for this theorem but with a different technique. It uses a single arrow to throw all the elements, the arrow can wiggle and turn around, this kind of proof I could understand.

Q1: When I see Rudin's proof, I was confused about how those arrows have bijections with $$\mathbb{N}$$. It said arrange in sequence, it seems that the sequence's terms are increasing(e.g $$2$$nd term is a two-element tuple, $$3$$rd term is a three-element tuple, etc.) can a sequence have terms for different types?

• Think of ordering the arrows (and the elements $x_{i,j}$ that the arrows intersect) in order of increasing arrow length. Sep 10, 2022 at 15:10
• You could also suppose that at the head of each arrow you add a line joining the head of the arrow to the tail of the arrow below it. Now you have one zig-zag path starting at the upper left. Follow that path, collecting all the terms you pass over while moving upward to the right and not collecting terms while moving downward to the left. Sep 10, 2022 at 16:31

## 3 Answers

A sequence can be whatever you want - but in this case, that's making things unnecessarily complicated. Just flatten the sequence-of-sequences down into a single sequence by following the arrows and concatenating the elements you pass by together in order. That is, trade the semicolons in (17) for commas, and discard the repeated entries.

• Following this diagram proof, how should I convince myself that each arrow only covers countable elements? Also, is a diagram proof really admissible in analysis? Or this is just a sketch of the proof
– LJNG
Sep 10, 2022 at 15:27
• "Countable elements" seems to be the wrong framing. Think about the entire set; your job is to place the set in a bijection with the natural numbers (or a surjection from them). As for whether this is admissible as a proof, this depends entirely on context. (Is it for a journal article? For a teacher? Which teacher, since they don't all agree? Etc.) Sep 10, 2022 at 15:57
• @LJNG "how should I convince myself that each arrow only covers countable elements?" – Consider any arrow. That arrow covers at least one element, $x_{ab}$. Notice that all of the elements that an arrow covers have the same sum of indices. (For example, there is an arrow that covers $x_41$, $x_32$, $x_23$, and $x_14$. The sums of indices here are $4 + 1$, $3 + 2$, $2 + 3$, and $1 + 4$, all of which equal $5$.) Sep 11, 2022 at 0:22
• @LJNG So the only other elements that our arrow can cover are elements $x_cd$, where $c$ and $d$ are positive integers such that $c + d = a + b$. There are only finitely many such pairs of numbers $(c, d)$. Therefore, this arrow covers only finitely many elements. Sep 11, 2022 at 0:22
• Note that arrow number $n$ covers $n$ elements. Does that answer your question, or have I misunderstood? Sep 11, 2022 at 11:46

it seems that the sequence's terms are increasing(e.g $$2$$nd term is a two-element tuple, $$3$$rd term is a three-element tuple, etc )

This is incorrect.

Rudin is referring to the following sequence, which is a bijection of $$\mathbb{N}$$:

$$x_{1,1}$$ is the first term, $$x_{2,1}$$ is the second term, $$x_{1,2}$$ is the third term, $$x_{3,1}$$ is the forth term, $$x_{2,2}$$ is the fifth term, and so on.

A Bijection between this sequence and $$\mathbb{N}$$ can be seen because:

• For each of the elements of the union of the all the $$E_n,\$$ for example $$\ x_{3,1},\$$ the arrows do not go over this element twice and the arrows do not miss out any of these elements.
• In other words, for each element $$x_{i,j}\$$ in Rudin's "arrow sequence": $$x_{1,1},\ x_{2,1}\ x_{1,2}\ x_{3,1}\ x_{2,2}\ \ldots,\$$ there exists a unique positive integer $$n$$ such that $$x_{i,j}\$$ is the $$n$$-th element of this sequence. Furthermore, for every integer $$m,$$ there exists a unique pair $$(i,j)$$ such that $$x_{i,j}\$$ is the $$m$$-th element of the sequence. Thus the sequence is a bijection of $$\mathbb{N}$$.

The proof shows that there is a surjection from $$\mathbb{N}\times\mathbb{N}$$ to $$S$$(map each pair $$(n,k)$$ to $$x_{nk}$$), this means that there is an injection from $$S\to \mathbb{N}\times\mathbb{N}$$, since $$\mathbb{N}\times\mathbb{N}$$ is countable there is an injection $$S\to T$$ where $$T$$ is a subset of the naturals.