Here is Theorem 1.5.8 in "Understanding Analysis" by S. Abbott, 2nd edition.
Theorem 1.5.8
(i) If $A_1, A_2, ..., A_n$ are each countable sets, then the union $A_1\cup A_2 \cup ... \cup A_n$ is countable.
(ii) If $A_n$ is a countable set for each $n \in \mathbb{N}$, then $\bigcup^\infty_{n=1}A_n$ is countable.
Exercise 1.5.3 (b) asks:
b) Explain why induction cannot be used to prove part (ii) of Theorem 1.5.8 from part (i).
On Slader I find this solution. I have pasted it below:
I don't quiet understand the reasoning above and why should it imply (does it?) that the infinite union would not be countable.
Suppose I split $\mathbb{N}$ into an infinite number of sets corresponding to the rows below:
$1 \;\;\;3 \;\;\;6 \;\;\;10\;\;...$
$2 \;\;\;5\;\;\; 9\;\;...$
$4\;\;\; 8\;\;...$
$7\;\;...$
The infinite union is clearly countable.
However, if I am to replicate the argument given in the solution, given $N\in \mathbb{N}$, we can always find infinitely many $x \in \bigcup_{n=1}^\infty A_n$ such that $x \not\in \bigcup_{n=1}^N A_n$.
What am I missing?
$\endgroup$ 143 Answers
$\begingroup$Ignore what you found on slader -- that just doesn't make sense.
However, it is not straightforward at all to prove that you cannot use induction to prove part (ii) from part (i). Luckily, you aren't asked to provide such a proof. All you are asked to do is to give an explanation (which is much more of a pedagogical technique than it has to do with mathematics).
So, why can't you use induction here? Induction says: Suppose you have a property $P$ such that $P(0)$ holds true and $P(n) \implies P(n+1)$ for all $n \in \mathbb N$. Then $P(n)$ holds for all $n \in \mathbb N$.
In our case the property $P(n)$ is "the union of $n$ countable sets is countable". By induction we get that $P(n)$ holds true for all $n \in \mathbb N$.
The statement "the union of countable many countable sets is countable" is not among those statements $P(n)$ (there is no $n \in \mathbb N$ such that "the union of countable many countable sets is countable" is equivalent to $P(n)$). Hence induction doesn't provide us with any information about this statement.
$\endgroup$ $\begingroup$First of all the statement " infinite" union of countable sets is countable is not true unless the infinite is replaced by countably infinite.
Otherwise the set of real numbers would be countable because it is an infinite union of singletons.
For your question about the induction, you can prove using induction that for every positive integer $n$ the union of $n$ countable set is countable but that is not the same thing as the union of countably infinite countable sets is countable.
$\endgroup$ 2 $\begingroup$The situation you are in is pretty much similar to the following:
We know that, for any $n \in \mathbb{N}$, if $r_1, \ldots, r_n$ are some real numbers, then the set $$ \left\{ r_1, \ldots, r_n \right\} = \left\{ r_1 \right\} \cup \cdots \cup \left\{ r_n \right\} $$is a finite set.
However, if $r_1, r_2, r_3, \ldots$ are distinct real numbers, then the set $$ \bigcup_{i=1}^\infty \left\{ r_i \right\} = \left\{ r_1, r_2, r_3, \ldots \right\} $$is NOT a finite set.
Similarly, for each $n \in \mathbb{N}$, although the set $$ \prod_{i=1}^n \{ 0, 1 \} = \underbrace{ \{0, 1 \} \times \cdots \times \{ 0, 1 \} }_{n \mbox{ times} } $$is a countable (in fact finite) set. However, the infinite product $$ \prod_{i=1}^\infty \{ 0, 1\} = \{ 0, 1 \} \times \{ 0, 1 \} \times \{ 0, 1 \} \times \cdots $$is not a finite (or even countable) set.
Hope you can now appreciate what is involved.
$\endgroup$
