2
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ Your statement is not true assuming your definition of countability. If the sets were all identical, the infinite union would be finite. $\endgroup$
    – user694818
    Oct 2, 2019 at 18:41
  • $\begingroup$ @MatthewDaly they can't be identical. As $(A_i)$ is a countable family. $\endgroup$
    – user643073
    Oct 2, 2019 at 18:42
  • $\begingroup$ Terms of families don't need to be distinct. $\endgroup$
    – user694818
    Oct 2, 2019 at 18:43
  • $\begingroup$ @MatthewDaly So, if in addition to the hypothesis, I assume that they are distinct. Would my proof work? $\endgroup$
    – user643073
    Oct 2, 2019 at 18:46
  • $\begingroup$ 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. $\endgroup$
    – user694818
    Oct 2, 2019 at 18:53

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks for the reply. May you please add your thoughts on what has been written in the comment section, please? $\endgroup$
    – user643073
    Oct 2, 2019 at 18:48
  • $\begingroup$ If you count finite sets as countable then the concerns will go away. $\endgroup$ Oct 2, 2019 at 19:25
  • $\begingroup$ No, my class doesnt. Unfortunately. $\endgroup$
    – user643073
    Oct 2, 2019 at 19:29
  • $\begingroup$ @topologicalmagician If you have a countable family of disjoint finite sets then there would not be any problems. $\endgroup$ Oct 2, 2019 at 20:34
0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Where does it break down, if im not assuming the terms to be disjoint? $\endgroup$
    – user643073
    Oct 2, 2019 at 19:54
  • $\begingroup$ @topologicalmagician You said it was a countable family. $\endgroup$
    – user694818
    Oct 2, 2019 at 20:41
  • $\begingroup$ @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. $\endgroup$
    – user694818
    Oct 2, 2019 at 20:43

You must log in to answer this question.