Proving Theorem 1.4.13 (ii): Arranging \mathbf{N} in a 2-D Array

[linuxux]

My question is this:

Theorem 1.4.13 part (ii) says: If A_n is a countable set for each n \in \mathbf{N}, then \cup^{\infty}_{n=1} A_n is countable.

I can't use induction to prove the validity of the theorem, but the question does say how does arranging \mathbf{N} into a 2-d array:

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?

so obviously it has something to do with the (x,y) co-ordinate system of the array, but I nt sure how it leads to the proof.

 

[CRGreathouse]

You can just show a function f: A\to\mathbb{N}.

f(0)=A_1(0)
f(1)=A_1(1)
f(2)=A_2(0)
f(3)=A_1(2)
f(4)=A_2(1)
f(5)=A_3(0)
f(6)=A_1(3)
. . .

 

[linuxux]

You can just show a function f: A\to\mathbb{N}.

f(0)=A_1(0)
f(1)=A_1(1)
f(2)=A_2(0)
f(3)=A_1(2)
f(4)=A_2(1)
f(5)=A_3(0)
f(6)=A_1(3)
. . .

but what is the significance of putting it into a 2-d array? i could just as easily say: 1, 2, 3, 4, ... and call it a 1-d array.

 

[CRGreathouse]

but what is the significance of putting it into a 2-d array? i could just as easily say: 1, 2, 3, 4, ... and call it a 1-d array.

$A_1(0)$ $A_1(1)$ $A_1(2)$ $A_1(3)$&...
$A_2(0)$ $A_2(1)$ $A_2(2)$ $A_2(3)$&...
$A_3(0)$ $A_3(1)$ $A_3(2)$ $A_3(3)$&...
$A_4(0)$ $A_4(1)$ $A_4(2)$ $A_4(3)$&...
$A_5(0)$ $A_5(1)$ $A_5(2)$ $A_5(3)$&...
... ... ... ...

 

[mathwonk]

this proof is due to cantor, 100 years ago. just start couting from the upper left corner, counting by sw/ne diagonals.

 

[matt grime]

but what is the significance of putting it into a 2-d array?

To demonstrate a bijection between N (the indices you're inserting) and the countable union of N (the locations in the doubly infinite array). I.E the whole point of the question.

 

[linuxux]

You can just show a function f: A\to\mathbb{N}.

f(0)=A_1(0)
f(1)=A_1(1)
f(2)=A_2(0)
f(3)=A_1(2)
f(4)=A_2(1)
f(5)=A_3(0)
f(6)=A_1(3)
. . .

but how is this a 1-1 and onto function? how is it that A_n is a function itself? the cantor theorem is the next section in my text so i can't apply that theory now. i understand that f(n) is a function, but why also A_n?

 

[CompuChip]

Here's a different explanation (sometimes I see that the understanding of the principle depends on the way it is explained, so maybe this will help you - maybe it will make it less clear to you, then please ignore this )
Suppose we put two copies of the natural numbers next to each other. We want to show that, doing this, the total number we get is still countable (that there are "as many" elements in this string of numbers as there are natural numbers, by assigning a natural number to each of the elements).
Clearly, just counting them in a line won't work. Then we assign each natural number to itself in the first copy, but when we're through with that one, we don't have any natural numbers left for the second copy. So what we do is: assign 1 to 1 from the first copy, 2 to 1 from the second copy, 3 to 2 from the first copy, 4 to 2 from the second copy, etc. - so
2n - 1 \mapsto n \text{ from the first copy of } \textbf{N}, <br /> 2n \mapsto n \text{ from the second copy of } \textbf{N}.<br />.

Now consider the Cartesian product \textbf N \times \textbf N, consisting of all pairs of natural numbers (a, b). How do you prove they are countable. One way would be to start by assigning n to (n, 1), but when we're done, we won't have any natural numbers left to assign to (n, 2) and (n, 3), etc. So here's the trick: we organize the pairs like
(1,1) (1,2) (1,3) ...
(2,1) (2,2) (2,3)
(3,1) (2,3) (3,3)
...
and now we can map them like
1 2 6 7 ...
3 5 8 ...
4 9 10
without running out of numbers too soon.

In the same way, you can prove that \textbf{N}^k is countable for any natural number k, as well as \frac{1}{2} \textbf{N} (all halfintegers 0, 1/2, 1, 3/2, ...) and the integers \textbf{Z} (it's basically two copies of the naturals, like in my first example, with a zero added) and even that the rationals \textbf{Q} are countable. And, also the question from your initial post can be solved like this.

 

[linuxux]

Here's a different explanation (sometimes I see that the understanding of the principle depends on the way it is explained, so maybe this will help you - maybe it will make it less clear to you, then please ignore this )
Suppose we put two copies of the natural numbers next to each other. We want to show that, doing this, the total number we get is still countable (that there are "as many" elements in this string of numbers as there are natural numbers, by assigning a natural number to each of the elements).
Clearly, just counting them in a line won't work. Then we assign each natural number to itself in the first copy, but when we're through with that one, we don't have any natural numbers left for the second copy. So what we do is: assign 1 to 1 from the first copy, 2 to 1 from the second copy, 3 to 2 from the first copy, 4 to 2 from the second copy, etc. - so
2n - 1 \mapsto n \text{ from the first copy of } \textbf{N}, <br /> 2n \mapsto n \text{ from the second copy of } \textbf{N}.<br />.

Now consider the Cartesian product \textbf N \times \textbf N, consisting of all pairs of natural numbers (a, b). How do you prove they are countable. One way would be to start by assigning n to (n, 1), but when we're done, we won't have any natural numbers left to assign to (n, 2) and (n, 3), etc. So here's the trick: we organize the pairs like
(1,1) (1,2) (1,3) ...
(2,1) (2,2) (2,3)
(3,1) (2,3) (3,3)
...
and now we can map them like
1 2 6 7 ...
3 5 8 ...
4 9 10
without running out of numbers too soon.

In the same way, you can prove that \textbf{N}^k is countable for any natural number k, as well as \frac{1}{2} \textbf{N} (all halfintegers 0, 1/2, 1, 3/2, ...) and the integers \textbf{Z} (it's basically two copies of the naturals, like in my first example, with a zero added) and even that the rationals \textbf{Q} are countable. And, also the question from your initial post can be solved like this.

thanks, i understand the example you showed. and to think, this is just an introductory text and I'm self-studying!...

 

[linuxux]

(1,1) (1,2) (1,3) ...
(2,1) (2,2) (2,3)
(3,1) (2,3) (3,3)

this part i understand. each (a,b) has a particular n mapped to it, thus (a,b)~N. so i got that.

but, looking at this:
$A_1(0)$ $A_1(1)$ $A_1(2)$ $A_1(3)$&...
$A_2(0)$ $A_2(1)$ $A_2(2)$ $A_2(3)$&...
$A_3(0)$ $A_3(1)$ $A_3(2)$ $A_3(3)$&...
$A_4(0)$ $A_4(1)$ $A_4(2)$ $A_4(3)$&...
$A_5(0)$ $A_5(1)$ $A_5(2)$ $A_5(3)$&...

i understand this to mean that the number of sets of A_n is countable, not that once the union is performed on the sets the elements of the union will be countable. I had a previous problem where i had to show that the union of A_1 and A_2 was countable, i did this by defining a function that chose the minimum element first in A_1 and then in A_2, then choosing the next smallest element in both, and so on, thus i was able to show A_1\cup{}A_2~\mathbb{N}. So in that exercise i addressed the elements in the sets, not the sets themselves. how does the section in red address the elements in the sets? is that even necessary?

**********

wait a minute: i know each A_n is countable, so each A_n(a\in\mathbb{N}) addresses the elements in A_n. now i see.

 

[matt grime]

but how is this a 1-1 and onto function?

By construction: do you write down the same number twice or fail to fill in a box?

how is it that A_n is a function itself?

It isn't a function.

 

[linuxux]

By construction: do you write down the same number twice or fail to fill in a box?




It isn't a function.

wouldn't it qualify as a function since A_n is countable thus A_n \mapsto \mathbb{N}?
i thought \mapsto represents some type of function. does it not?

i also have another question, what happens if a particular A_n is finite?

 

[CompuChip]

Theorem 1.4.13 part (ii) says: If A_n is a countable set for each n \in \mathbf{N}, then \cup^{\infty}_{n=1} A_n is countable.

Yeah, so for each n we can assign a natural number to each element from A_n, and in the end, have neither elements of A_n nor natural numbers "left" (that is, there is a bijection). The claim is, that the union is countable, so there is a bijection from the naturals to the union. What the 2-D array tries to visualize, is the following: since each A_n is countable, we can denote the elements by A_n(k) (with k = 1, 2, 3, ...). Now you can order the elements in the union like this:
A_1(1) \, A_2(1) \, A_3(1) \, \cdots
A_1(2) \, A_2(2) \, A_3(2) \, \cdots
A_1(3) \, A_2(3) \, A_3(3) \, \cdots
and use a diagonal counting argument, like before.

Another way is this: each element from the union is indexed by two numbers (n, k) (assuming the union is disjoint, as we implicitly did before). So it's really trivial to write down a bijection from this union to \textbf{N} \times \textbf{N}. As shown in my earlier post, the latter is countable (there is a bijection to \textbf{N}, so by composing the bijections you get one from the union to \textbf{N}. Actually, it also uses the diagonal counting argument (to show that \textbf{N} \times \textbf{N} is countable) but perhaps this approach is more intuitive (and once you've proven this result about \textbf{N} \times \textbf{N} \times \cdots \times \textbf{N} you can use it and prove countability of other things, like this union of A_n, without explicitly invoking a diagonal counting argument).

 

[CompuChip]

i also have another question, what happens if a particular A_n is finite?

Does it matter? If you have a set in the union, that is not countably infinite, but finite, will the union become bigger (so big, it will become uncountable?)

If you want to do it officially, consider this: we said a set is countable if we can assign the numbers 1, 2, 3, ... to it. But of course, we can use another offset, and assign 2, 3, 4, ... to it. Or 154842, 154843, 154844, ...
So you could of course first count off the finite sets in the union (in order, no need for diagonals here), and then the infinite ones with the diagonal argument, but using a certain offset.

 

[linuxux]

Does it matter? If you have a set in the union, that is not countably infinite, but finite, will the union become bigger (so big, it will become uncountable?)

If you want to do it officially, consider this: we said a set is countable if we can assign the numbers 1, 2, 3, ... to it. But of course, we can use another offset, and assign 2, 3, 4, ... to it. Or 154842, 154843, 154844, ...
So you could of course first count off the finite sets in the union (in order, no need for diagonals here), and then the infinite ones with the diagonal argument, but using a certain offset.

thanks a million man!

 

[CompuChip]

Most welcome, this stuff is fun and moreover, it's important basics.

Later you will encounter more diagonal arguments, for example: if you want to prove that the real numbers are uncountable, or if you get to work with converging sequences.

 

[matt grime]

wouldn't it qualify as a function since A_n is countable thus A_n \mapsto \mathbb{N}?
i thought \mapsto represents some type of function. does it not?

i also have another question, what happens if a particular A_n is finite?

You said A_n was a function, not that |-> was a function. Don't be sloppy.