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

Infinite Product

  1. Feb 7, 2012 #1
    In infinitely many steps I am using the sequence (displayed in bold) to create the list of natural numbers (001 = 01 = 1):
    1.
    ...000000
    ...000001
    ...000010
    ...000011
    ...000100
    ...000101
    ...000110
    ...000111
    ...001000
    ...

    2.
    ...000000
    ...000001
    ...000010
    ...000011
    ...000100
    ...000101
    ...000110
    ...000111
    ...001000
    ...

    3.
    ...000000
    ...000001
    ...000010
    ...000011
    ...000100
    ...000101
    ...000110
    ...000111
    ...001000
    ...

    In infinitely many steps I am using the same sequence to create a list of what I would call the binary complement of the natural numbers:
    1.
    ...
    ...110111
    ...111000
    ...111001
    ...111010
    ...111011
    ...111100
    ...111101
    ...111110
    ...111111

    2.
    ...
    ...110111
    ...111000
    ...111001
    ...111010
    ...111011
    ...111100
    ...111101
    ...111110
    ...111111

    3.
    ...
    ...110111
    ...111000
    ...111001
    ...111010
    ...111011
    ...111100
    ...111101
    ...111110
    ...111111

    I have displayed how to create two different lists of countably infinitely many lines. Is there a similar way to display how the same sequence can be used to create 2^ω which includes all infinite binary sequences?
     
  2. jcsd
  3. Feb 7, 2012 #2

    jedishrfu

    Staff: Mentor

    do you mean like this?

    00000001 = 2^0
    00000010 = 2^1
    00000100 = 2^3
    00001000 = 2^4
    ...
     
  4. Feb 7, 2012 #3
    I mean the infinite cartesian product {0,1} x {0,1} x {0,1} x ..., which is {0,1}^ω or 2^ω.
     
  5. Feb 10, 2012 #4
    Is it true that {0,1} x {0,1} x {0,1} x ... = {0,1}^ω means that we can create the set of all infinite binary sequences (including ...000000 as well as ...111111) in countably many steps? Like

    1. {0,1} x {0,1} = {(0,0),(0,1),(1,0),(1,1)}

    2. {(0,0),(0,1),(1,0),(1,1)} x {0,1} = {(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}

    3. {(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)} x {0,1} = ...
     
  6. Feb 10, 2012 #5

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The set [itex]\{0, 1\}^{\mathbb{N}}[/itex] is (equivalent to) indeed the set of all infinite binary sequences; this is true by directly comparing the definition of set exponentiation and the definition of sequence. or less by definition. This set has cardinality [itex]2^{\aleph_0}[/itex].


    However, the set [itex]\{0, 1\}^{\omega}[/itex] is something different. It is the (disjoint) union of all of the lists you created at each finite step -- in particular, it is the set of finite binary sequences. This set has order type [itex]\omega[/itex], and cardinality [itex]\aleph_0[/itex].


    What you get out of countably many steps depends on what precisely you mean. In the usual way to give meaning to transfinite algorithms, the algorithm suggested by what you write merely results in [itex]\{0, 1\}^\omega[/itex].
     
  7. Feb 10, 2012 #6
    What is true then:

    {0,1} x {0,1} x {0,1} x ... = [itex]\{0, 1\}^{\mathbb{N}}[/itex]
    or
    {0,1} x {0,1} x {0,1} x ... = [itex]\{0, 1\}^{\omega}[/itex]

    or both - in some sense?
     
  8. Feb 10, 2012 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member


    1+1=3 if, by +, I mean "add the two numbers then add 1".

    The answer to your question depends on what you mean by exponentiation. The way the notation is usually used, the first equation is true and it doesn't make sense to ask the question of the second one since it's grammatically incorrect.


    The "method" you described in your opening post is the missing ingredient to make sense out of [itex]\{0,1\}^\omega[/itex] (as the notation is usually used), and in that context the second equation is now well-defined, but false.

    (another way with identical results is if by [itex]\{0,1\}[/itex], you don't mean the set, but instead the ordered set specified by the ordering 0 < 1, in which case you have ordinal^ordinal which also makes sense how the operation is usually used)


    However, if for the second one you really mean "I want ordinary set exponentiation with a set representing [itex]\omega[/itex] as the exponent", then the second equation would be true.
     
    Last edited: Feb 10, 2012
  9. Feb 11, 2012 #8
    Take into account that the method in my opening post describes how I am writing a single infinite list, not infinitely many finite lists! It is like filling an infinite grid. What has been written up to each step (in bold) will not be rewritten at the following step. Taking this into account, can we biject the intermediate lists of each step to the intermediate results of the product {0,1} x {0,1} x {0,1} x ... and shouldn't we get the same set of binary sequences after infinitely many steps?
     
    Last edited: Feb 11, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook