Creating 2^ω with Sequence: Discovering Infinite Possibilities

[netzweltler]

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?

 

[jedishrfu]

do you mean like this?

00000001 = 2^0
00000010 = 2^1
00000100 = 2^3
00001000 = 2^4
...

 

[netzweltler]

I mean the infinite cartesian product {0,1} x {0,1} x {0,1} x ..., which is {0,1}^ω or 2^ω.

 

[netzweltler]

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} = ...

 

[Hurkyl]

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].

 

[netzweltler]

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?

 

[Hurkyl]

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?

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.

 

[netzweltler]

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].

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?