Proof of countable family of finite sets

Definition: A set A is countable if there exists a bijection $$f:\mathbb{N}\rightarrow A$$. NOTE: According to the definition i'm using, countable = countably infinite.

Definition: A set is at most countable if it is finite or countable.

Let $$(A_i)_i$$ be a countable family of finite sets such that the family contains non-empty terms. Then $$\bigcup_{n \in \mathbb{N}}A_n$$ is countable.

My proof: As $$(A_i)_i$$ is a family of countable sets, we may enumerate the family as a sequence ($$A_1,A_2,A_3....$$) such that each term is distinct. Let $$A_1$$ $$=(a_{11},a_{21},a_{31}…,a_{n1})$$. So for an arbitrary j, we may enumerate the elements of $$A_j$$ as $$(a_{1j},a_{2j}…,a_{m_{j}j})$$. How should I enumerate the union?

• Just an FYI: The way you define countable is usually known as countably infinite. The standard definition of countable is what you call at most countable: i.e., there exists an injection from set $A\to\mathbb N$. – Don Thousand Oct 25 '19 at 16:19
• The proof is on the right track, I just think it's a bit too handwavy at points. – Don Thousand Oct 25 '19 at 16:21
• @DonThousand may you please elaborate? – orientablesurface Oct 25 '19 at 16:22
• 'As each $𝐴_i$ is distinct, we will be left with infinitely many distinct elements and therefore the union is countable." - too vague – Don Thousand Oct 25 '19 at 16:22
• @DonThousan $A_i\neq A_j$ for $i\neq j$ and we have countably infinite of them. How should I make this more clear? – orientablesurface Oct 25 '19 at 16:23

2 Answers

With these definitions, the assertion is false as stated: just let $$A_n=\emptyset$$ for all $$n$$. Or, more generally, fix a finite set $$U$$ and choose every $$A_n$$ to be a subset of $$U$$.

• Ok. Suppose $A_n$ is non-empty. If U is finite, then it has finite many subsets. I'm assuming that each subset is distinct and that I have countably infinite of them. – orientablesurface Oct 25 '19 at 16:33
• That clarification makes the assertion both true and interesting. I recommend that you edit the original post to make the statement clear. By the way, you've pretty much just outlined a proof (by contradiction) of the statement! – Greg Martin Oct 25 '19 at 16:34
• i'm really not sure what to do next. – orientablesurface Oct 25 '19 at 16:39
• @topologicalmagician Next, follow Greg Martin's advice and edit your question to make it clear that the $A_n$ are supposed to be distinct. – Mirko Oct 26 '19 at 1:43

Prove the contrapositive (or arrive at a contradiction) using the pigeon-hole principle.

It should be clear the $$U=\bigcup_{n \in \mathbb{N}}A_n$$ is "at most countable", i.e. it is either finite or countable (=countably infinite). You want to rule out the possibility that $$U$$ is finite. Clearly $$A_n\subseteq U$$ for every $$n$$. If $$U$$ were finite then its power-set $$\mathcal P(U):=\{V:V\subseteq U\}$$ would also be finite. (This just says that $$2^n$$ is a natural number whenever $$n$$ is.) But every $$A_n$$ is an element of $$\mathcal P(U)$$, and we cannot have infinitely many distinct elements in a finite set.