Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Statement Proof.

  1. Jul 11, 2007 #1
    My question is this:

    Theorem 1.4.13 part (ii) says: 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 can't use induction to prove the validity of the theorem, but the question does say how does arranging [tex]\mathbf{N}[/tex] 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.
     
    Last edited: Jul 11, 2007
  2. jcsd
  3. Jul 11, 2007 #2

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

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

    [tex]f(0)=A_1(0)[/tex]
    [tex]f(1)=A_1(1)[/tex]
    [tex]f(2)=A_2(0)[/tex]
    [tex]f(3)=A_1(2)[/tex]
    [tex]f(4)=A_2(1)[/tex]
    [tex]f(5)=A_3(0)[/tex]
    [tex]f(6)=A_1(3)[/tex]
    . . .
     
  4. Jul 11, 2007 #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.
     
  5. Jul 11, 2007 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    $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)$&...
    ... ... ... ...
     
  6. Jul 11, 2007 #5

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

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

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  8. Jul 14, 2007 #7
    but how is this a 1-1 and onto function? how is it that [tex]A_n[/tex] 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 [tex]A_n[/tex]?
     
    Last edited: Jul 14, 2007
  9. Jul 14, 2007 #8

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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 :smile:)
    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
    [tex]2n - 1 \mapsto n \text{ from the first copy of } \textbf{N},
    2n \mapsto n \text{ from the second copy of } \textbf{N}.
    [/tex].

    Now consider the Cartesian product [tex]\textbf N \times \textbf N[/tex], 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 [itex]\textbf{N}^k[/itex] is countable for any natural number k, as well as [itex]\frac{1}{2} \textbf{N}[/itex] (all halfintegers 0, 1/2, 1, 3/2, ...) and the integers [itex]\textbf{Z}[/itex] (it's basically two copies of the naturals, like in my first example, with a zero added) and even that the rationals [itex]\textbf{Q}[/itex] are countable. And, also the question from your initial post can be solved like this.
     
  10. Jul 14, 2007 #9
    thanks, i understand the example you showed. and to think, this is just an introductory text and i'm self-studying!...
     
    Last edited: Jul 14, 2007
  11. Jul 14, 2007 #10
    (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 [tex]A_n[/tex] 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 [tex]A_1[/tex] and [tex]A_2[/tex] was countable, i did this by defining a function that chose the minimum element first in [tex]A_1[/tex] and then in [tex]A_2[/tex], then choosing the next smallest element in both, and so on, thus i was able to show [tex]A_1\cup{}A_2[/tex]~[tex]\mathbb{N}[/tex]. 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 [tex]A_n[/tex] is countable, so each [tex]A_n(a\in\mathbb{N})[/tex] addresses the elements in [tex]A_n[/tex]. now i see.
     
    Last edited: Jul 14, 2007
  12. Jul 15, 2007 #11

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

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


    It isn't a function.
     
  13. Jul 15, 2007 #12
    wouldn't it qualify as a function since [tex]A_n[/tex] is countable thus [tex]A_n \mapsto \mathbb{N} [/tex]?
    i thought [tex]\mapsto[/tex] represents some type of function. does it not?

    i also have another question, what happens if a particular [tex]A_n[/tex] is finite?
     
    Last edited: Jul 15, 2007
  14. Jul 15, 2007 #13

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Yeah, so for each n we can assign a natural number to each element from [tex]A_n[/tex], and in the end, have neither elements of [tex]A_n[/tex] 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 [tex]A_n[/tex] is countable, we can denote the elements by [tex]A_n(k)[/tex] (with k = 1, 2, 3, ...). Now you can order the elements in the union like this:
    [tex]A_1(1) \, A_2(1) \, A_3(1) \, \cdots[/tex]
    [tex]A_1(2) \, A_2(2) \, A_3(2) \, \cdots[/tex]
    [tex]A_1(3) \, A_2(3) \, A_3(3) \, \cdots[/tex]
    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 [tex]\textbf{N} \times \textbf{N}[/tex]. As shown in my earlier post, the latter is countable (there is a bijection to [tex]\textbf{N}[/tex], so by composing the bijections you get one from the union to [tex]\textbf{N}[/tex]. Actually, it also uses the diagonal counting argument (to show that [tex]\textbf{N} \times \textbf{N}[/tex] is countable) but perhaps this approach is more intuitive (and once you've proven this result about [tex]\textbf{N} \times \textbf{N} \times \cdots \times \textbf{N}[/tex] you can use it and prove countability of other things, like this union of [tex]A_n[/tex], without explicitly invoking a diagonal counting argument).
     
    Last edited: Jul 15, 2007
  15. Jul 15, 2007 #14

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  16. Jul 15, 2007 #15
    thanks a million man!
     
  17. Jul 15, 2007 #16

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  18. Jul 16, 2007 #17

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    You said A_n was a function, not that |-> was a function. Don't be sloppy.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?