Induction Limitations in Proving Countable Sets: Understanding Analysis

[linuxux]

Hello, I'm working from a book called 'Understanding Analysis' by Stephen Abbott and there is a question I'm not sure about:

Explain why induction cannot be used to prove part (ii) of Theorem 1.4.13 from part (i).

Theorem 1.4.13 says:
(i) If [tex]A_1 , A_2 , \ldots A_m[/tex] are each countable sets, then the union [tex] A_1 \cup A_2 \cup \ldots \cup A_m [/tex] is countable.
(ii) If [tex]A_n[/tex] is a countable set for each [tex]n \in \mathbf{N}[/tex], then [tex]\cup^{\infty}_{n=1} A_n[/tex] is countable.

I thought it would be helpful to note that in the previous problem, I had two sets [tex]A_1[/tex] and [tex]A_2[/tex], both of which are countable, and had to prove that their union was also countable. in that instance, a set [tex]B_1[/tex] was made by [tex]A_1 / A_2 [/tex] which made [tex]A_1 \cup B_1[/tex] equal to [tex]A_1 \cup A_2[/tex] but [tex]A_1[/tex] and [tex]B_1[/tex] were disjoint, which was required in order to have a 1-1 function.

-im not sure if i could prove it by contradiction like this: i can assume there is a single list of all the combined elements in the sets. in this list there are nested intervals, and because the list will be mapped to a function, we assume there are no repeated elements in the list. so i define the list so element [tex]x_k[/tex] does not belong to interval [tex]I_{k+1}[/tex] (i'm not sure if this qualifies as an induction). thus the intersection of intervals is an empty set, as it should be. but the nested interval property says that the intersection is non-empty, so we know the list is missing at least on element, so we can't use the inductive method to prove part (ii) of Theorem 1.4.13 from part (i).

 

[matt grime]

You haven't actually said what your problem is i.e. what you're not sure about. Your statement after the question doesn't really shed any light on what's bothering you.

If I assume you don't see why induction won't work, let me put it this way:

What does induction say? SUppose we have a set of statements indexed by the integers:

P(1), P(2),...

and if P(1) is true, and P(m) implies P(m+1), then all statements are true.

The statement P(m) here is that the union of m countable sets is countable. So (ii) induction doesn't even apply to (ii), since it isn't any of the statements P(m) for any integer m. We could label it the statement P(infinity), I suppose, but then induction has nothing to say about P(infinity) given P(m) for any m less than infinity.

 

[linuxux]

if its any help, the next question is how does arranging [tex]\mathbf{N}[/tex] into a two-dimensional array like:

1 3 6 10 15 ...
2 5 9 14 ...
4 8 13 ...
7 12 ...
11 ...

lead to the proof of part (ii) of Theorem 1.4.13?

- for this question, i can see right off the bat that if we create a function which maps [tex]\mathbf{N}[/tex] to the index's of the array then we'll get a function which is onto.

 

[matt grime]

What do you mean 'if it's any help'? You're the person asking for help, but so far you haven't said what the problem* is.

So, do you understand why induction doesn't work? Do you understand why this other idea does work? (Hint: each natural number n occurs precisely once in the array.)

* in the sense of what you do not understand.

 

[linuxux]

thanks, that was my original idea, there is no infinity+1, i didn't know how to phrase it though.