# Countable family of finite sets

Let $$A_1,A_2,A_3.....$$ be a countable family of finite sets. Then $$\bigcup_{i=1}^{\infty}A_i$$ is countable.

My definition of countable excluded finiteness. I.e A set is countable if it is denumerable.

My proof: As each $$A_i$$ is finite, we can write down its elements as ($$a_{i1}$$,$$a_{i2}$$$$a_{im_{i}})$$

Let $$f:\bigcup_{i=1}^{\infty}A_i \rightarrow \mathbb{N}$$ be defined as f($$a_{ij}$$) $$=$$ $$2^{i}3^{j}$$. The map is injective by the fundamental theorem of arithmetic. Furthermore, as $$\mathbb{N}$$ is countable, so is the union.

Is the proof correct?

EDIT: PLEASE PROVIDE AN ALTERNATIVE PROOF

• Your statement is not true assuming your definition of countability. If the sets were all identical, the infinite union would be finite.
– user694818
Oct 2, 2019 at 18:41
• @MatthewDaly they can't be identical. As $(A_i)$ is a countable family.
– user643073
Oct 2, 2019 at 18:42
• Terms of families don't need to be distinct.
– user694818
Oct 2, 2019 at 18:43
• @MatthewDaly So, if in addition to the hypothesis, I assume that they are distinct. Would my proof work?
– user643073
Oct 2, 2019 at 18:46
• If the sets are all disjoint, then definitely yes. If not, then you have the problem that maybe $a_{11}=a_{21}$, and you are giving those elements different indices by $f$ even though they only contribute to the union once. I'm not quite certain how to fix your proof in this case, although the conclusion is definitely true.
– user694818
Oct 2, 2019 at 18:53

Yes your proof is correct provided that we have a countable family of disjoint sets. You have defined an injective function from the union into the set of natural numbers which in turn defines a one to one correspondent between the union and a subset of natural numbers.

Thus the union is countable.

– user643073
Oct 2, 2019 at 18:48
• If you count finite sets as countable then the concerns will go away. Oct 2, 2019 at 19:25
• No, my class doesnt. Unfortunately.
– user643073
Oct 2, 2019 at 19:29
• @topologicalmagician If you have a countable family of disjoint finite sets then there would not be any problems. Oct 2, 2019 at 20:34

As per the comments, we are assuming that the sets are all distinct (but not necessarily disjoint).

We can show that the union $$U$$ is not finite by contradiction. If it were, then we could let $$n$$ be the number of elements in the union. But there are only $$2^n$$ distinct subsets that could have $$U$$ as their union. Since $$(A_i)$$ is actually infinite, we have reached a contradiction.

Your proof works if all the terms of $$(A_i)$$ are disjoint. So, in a sense, you have shown that the union cannot be uncountable even in "the worst case". Therefore, the union must be countable.

• Where does it break down, if im not assuming the terms to be disjoint?
– user643073
Oct 2, 2019 at 19:54
• @topologicalmagician You said it was a countable family.
– user694818
Oct 2, 2019 at 20:41
• @topologicalmagician The domain of your family is the union. If the sets were not disjoint, the some $x$ in the union would be in two different sets. This would make $f$ give multiple outputs for that same input.
– user694818
Oct 2, 2019 at 20:43