[Math] Proof by induction: $\cup_{n=1}^\infty A_n$ is countable, for countable $A_n$

elementary-set-theory

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:

enter image description here

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?

Best Answer

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.

Related Question