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

Cardinality of Cross Products

  1. Mar 4, 2009 #1
    Since Tex is giving me a hard time this question is going to be a lot more undeveloped than it was going to be. We were discussing in class the cardinality of the Natural numbers being aleph null and that the cross product was also of cardinality aleph null. Is it true then that:

    [tex]|\textbf{N} \times \textbf{N} \times \ldots \times \textbf{N}| = \aleph_0[/tex]

    For any finite number of cross products?

    Is it true for a countably infinite number of times? If not, why not?
     
  2. jcsd
  3. Mar 4, 2009 #2
    Do you mean direct product? If so, then the answer is yes.

    We can do this by induction and by using the definition of [tex]\mathbb{N} \times \cdots \times \mathbb{N}[/tex].

    (N x ... x N) is a product of k sets with cardinality aleph-null.

    This is equal to (N x N) x ... x N, which, given the fact that the product of 2 sets with cardinality aleph-null has cardinality aleph-null, means that N x ... x N is a product of k-1 sets with cardinality aleph-null. Keep going. You'll eventually reach the case where we can conclude that N x ... x N is a product of 2 sets with cardinality aleph-null and therefore must have cardinality aleph-null by induction assumption.
     
    Last edited: Mar 4, 2009
  4. Mar 5, 2009 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    As for a countable number of times, there is an obvious one-to-one correspondence between {XN}countable times} and the real numbers between 0 and 1: the countable ordered list (a1, a2, a3, ...) is mapped to the decimal number 0.a1a2a3...

    (a1, a2, etc. are, of course, not single digits but they are finite "lists" of decimals. Just append them: (1233, 2343, 0, 232,... ) is mapped to 0.123323430232...)
     
  5. Mar 5, 2009 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    How about this continued fraction (x_1 + 2, x_2 + 2, x_3 + 2, ...)?
     
  6. Mar 5, 2009 #5
    Yes, I did, my apologies on my wording.

    Isn't (N x N) x N = {((n_1,n_2),n_3 | n_i in N} different from {(n_1, n_2, n_3) | n_i is in N}?
     
  7. Mar 5, 2009 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Yes, but there is an obvious isomorphism.
     
  8. Mar 5, 2009 #7
    What does one do then with (1, 2, 3, 4, 5, 6, ...) and (123, 456, 789, ...) where the successive terms are the exact same. The decimals would be the same, the method you referred to. Does one need to put a labeling of some sort before each ai, say ci delineating how many digits are between each comma?

    And thank you for your point out the isomorphism--it was not obvious to me at first.
     
  9. Mar 5, 2009 #8
    Also (0, 9, 9, 9, ...) and (1, 0, 0, 0, ...) map to the same number 0.1.

    However Ivy's argument still shows that the set is at least as big as the reals, since the mapping is onto.

    Is the set bigger than the reals?
     
  10. Mar 5, 2009 #9

    I would actually disagree--the mapping would then not be a function, which is the whole goal.


    But either way, I realized my mistake. The proof then comes from selecting ai from the matrix..etc. I forgot and didn't realize how it would be different. I can see now. Thank you HallsofIvy for getting me straightened out. (I know that I'm a little slow/tedious sometimes).

    And as for your question, they would be of the same size. The mapping would be 1-1 and onto and would have equal number of elements.
     
  11. Mar 6, 2009 #10

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Step outside of set theory for a minute and remember that there are functions besides injections :p
     
  12. Mar 6, 2009 #11

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    It is a function. It is not a "one-to-one" function.
     
  13. Mar 6, 2009 #12
    Sorry. Somehow got it into my mind that it was going backwards. I apologize. I'm sorry I get turned around so easily.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Cardinality of Cross Products
  1. Cardinality Question (Replies: 1)

Loading...