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}, 2n \mapsto n \text{ from the second copy of } \textbf{N}.$$.

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}, 2n \mapsto n \text{ from the second copy of } \textbf{N}.$$.

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.