# 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$. Commented Oct 25, 2019 at 16:19
• The proof is on the right track, I just think it's a bit too handwavy at points. Commented Oct 25, 2019 at 16:21
• @DonThousand may you please elaborate?
– user643073
Commented Oct 25, 2019 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 Commented Oct 25, 2019 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?
– user643073
Commented Oct 25, 2019 at 16:23

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.

Edit. Just trying to comment on your question as to how to enumerate the union, starting with your suggestion that $$A_j=(a_{1j},a_{2j}…,a_{m_j j})$$. You could make the additional assumption that for each $$j$$ there is $$k_j$$ with $$0\le k_j\le m_j$$ such that if $$n\le k_j$$ then $$a_{n,j}$$ does not belong to any $$A_i$$ with $$i, and on the other hand if $$k_j then $$a_{n,j}$$ belongs to at least one $$A_i$$ with $$i.

Just to clarify this notation, if $$k_j=m_j$$ then all elements of $$A_j$$ are "new", i.e they do not appear in any "earlier" $$A_i$$'s (with $$i). On the other hand, if $$k_j=0$$ then none of the elements of $$A_j$$ is "new", i.e each element of $$A_j$$ is already an element of $$A_i$$'s for some $$i (where $$i$$ need not be unique and may depend on the particular element of $$A_j$$).

Since the family $$(A_i)_i$$ is countably infinite, there are infinitely many $$j$$ with $$k_j\ge1$$. (Hint for this part. If there were a largest $$j$$ with $$k_j\ge1$$ then let $$B=\bigcup_{i\le j}A_i$$. Then $$B$$ is finite and hence has only finitely many subsets, but on the other hand every $$A_i$$ with $$i>j$$ is one of these finitely many sets, a contradiction.)

Let $$J=\{j:k_j\ge1\}=\{j_1,j_2,j_3,...\}$$ where $$j_1
Then $$\bigcup_{n \in \mathbb{N}}A_n$$ can be listed as
$$(a_{1j_1},…,a_{k_{j_1} j_1},a_{1j_2},…,a_{k_{j_2} j_2},a_{1j_3},…,a_{k_{j_3} j_3},…)$$

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.
– user643073
Commented Oct 25, 2019 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! Commented Oct 25, 2019 at 16:34
• i'm really not sure what to do next.
– user643073
Commented Oct 25, 2019 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. Commented Oct 26, 2019 at 1:43