# Simplification in Proof of Countable Union of Countable Sets is Countable

In the book Analysis I by Amann and Escher, Chapter 1, Proposition 6.8 the following statement is given:

6.8 Proposition A countable union of countable sets is countable

Proof For each $$n\in\mathbb{N}$$, let $$X_{n}$$ be a countable set. By Proposition 6.7, we can assume that the $$X_{n}$$ are countably infinite and pairwise disjoint. Thus we have $$X_{n}=\{x_{n,k}:k\in\mathbb{N}\}$$ with $$x_{n,k}\neq x_{n,j}$$ for $$k\neq j$$, that is $$x_{n,k}$$ is the image of $$k\in\mathbb{N}$$ under a bijection from $$\mathbb{N}$$ to $$X_{n}$$. Now we order the elements of $$X=\bigcup_{n=0}^{\infty}X_{n}$$ as indicated by the arrows in the 'infinite matrix' below. This induces a bijection from $$X$$ to $$\mathbb{N}$$.

We leave to the reader the task of defining this bijection explicitly. $$\blacksquare$$

Here is Proposition 6.7:

6.7 Proposition Any subset of a countable set is countable.

The part of Proposition 6.8 that I am unsure about is that it can be assumed that the $$X_{n}$$ are countably infinite and pairwise disjoint.

Suppose you have the sets $$X_{n}$$. Then you can recursively define $$Y_{0}=X_{0}$$ and $$Y_{n+1}=X_{n+1}\setminus\left(\bigcup_{k=0}^{n}X_{k}\right)$$. Then $$\bigcup_{n=0}^{\infty}X_{n}=\bigcup_{n=0}^{\infty}Y_{n}$$ and the collection of $$Y_{n}$$ is pairwise disjoint. In particular, each $$Y_{n}$$ is countable from Proposition 6.7 as it is a subset of a countable set.

However, I cannot see why each $$X_{n}$$ can also be assumed to be countably infinite. This is also stopping me from understanding why there must also be a countably infinite number of sets which restricts the case where there are a finite number. Is there supposed to be a simple way to either rule out these cases or to transform them into the above form?

The proposition states that the countable union of countable sets is countable. So, the $$X_n$$ are chosen to be countable. You would not choose any $$X_n$$ uncountable to try to prove that the countable union of countable sets is countable.

Now, to add that they are pairwise disjoint, you can use the your construction for the $$Y_n$$'s along with proposition 6.7. But, you are not trying to prove that the starting $$X_n$$'s were countable. That is a given by their definition.

From the comments, it is clear the question is not what if some of the sets are uncountable. The question is, what if some of them are finite.

From the definition of each $$X_n$$ with elements $$x_{n,k}$$, you have a natural injection $$f:\bigcup X_n \to \mathbb{N}\times \mathbb{N}$$ given by $$f(x_{n,k})=(n,k)$$.

Let $$N=\{f(x_{n,k})\in \mathbb{N}\times\mathbb{N}\mid x_{n,k}\in \bigcup X_n\}$$

Obviously $$N\subset \mathbb{N}\times\mathbb{N}$$. And there exists a bijection between $$\bigcup X_n$$ and $$N$$.

So, use the proof given to show that $$\mathbb{N}\times\mathbb{N}$$ is countable by splitting $$\mathbb{N}\times\mathbb{N}$$ into $$\mathbb{N}\times \{n\}$$ for each $$n\in \mathbb{N}$$.

Now, by Proposition 6.7, $$N$$ is countable because it is a subset of $$\mathbb{N}\times\mathbb{N}$$. Then since $$\bigcup X_n$$ is in bijection with a countable set, it too is countable.

• Thanks for this explanation. I meant to ask about proving Proposition 6.8 using Proposition 6.7 and how those restrictions can be assumed from the start. I will improve the explanation of my question in the main post. Mar 14, 2022 at 12:37
• Ok, I updated my answer Mar 14, 2022 at 12:44
• I still don't understand the statement in the proof "By Proposition 6.7, we can assume that the $X_{n}$ are countably infinite and pairwise disjoint." Because Proposition 6.8 is a statement for countable sets, but in the proof only the case where the $X_{n}$ are countably infinite and pairwise disjoint is addressed. Mar 14, 2022 at 12:54
• If any of the sets are finite, then you have a subset of a countably infinite set. Extend any sets that are finite to infinite sets by adding elements. Once all pairwise disjoint sets are countable infinite, the proof follows. Now, apply Proposition 6.7. Your finite sets are subsets of the countable infinite sets. So, their union will yield a subset. And a subset of a countable set is countable. Mar 14, 2022 at 23:09
• Now I understand everything. Thank you very much for taking the time to help me with this. Mar 14, 2022 at 23:55