Creating 2^ω with Sequence: Discovering Infinite Possibilities

  • Context: Graduate 
  • Thread starter Thread starter netzweltler
  • Start date Start date
  • Tags Tags
    Infinite Product
Click For Summary

Discussion Overview

The discussion revolves around the construction of the set of all infinite binary sequences, denoted as 2^ω, using sequences and Cartesian products. Participants explore the implications of these constructions in relation to countably infinite steps and the nature of set exponentiation.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant describes a method to create lists of natural numbers and their binary complements through a sequence of steps.
  • Another participant suggests a representation of binary numbers as powers of 2, questioning the relationship to infinite sequences.
  • A participant introduces the concept of the infinite Cartesian product {0,1} x {0,1} x {0,1} x ... as equivalent to {0,1}^ω, aiming to establish a connection to all infinite binary sequences.
  • There is a discussion about whether the infinite Cartesian product can generate all infinite binary sequences in countably many steps, with examples provided to illustrate the process.
  • One participant asserts that {0,1}^ω is equivalent to the set of all infinite binary sequences, while also noting that it represents the union of finite binary sequences created at each step, leading to a cardinality of aleph_0.
  • Another participant questions the validity of the equivalence between {0,1} x {0,1} x {0,1} x ... and {0,1}^ω, suggesting that the interpretation of exponentiation affects the outcome.
  • Further clarification is sought on the definitions and implications of the notation used, particularly regarding the nature of set exponentiation and its application to infinite sequences.
  • One participant emphasizes that their method describes a single infinite list rather than multiple finite lists, proposing a bijection between intermediate lists and the results of the Cartesian product.

Areas of Agreement / Disagreement

Participants express differing views on the relationship between the infinite Cartesian product and the set of infinite binary sequences. There is no consensus on the definitions and implications of the notation used, leading to ongoing debate.

Contextual Notes

Participants highlight the importance of definitions in set exponentiation and the implications of constructing sequences through countably infinite steps. The discussion remains nuanced with various interpretations of the concepts involved.

netzweltler
Messages
26
Reaction score
0
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?
 
Physics news on Phys.org
do you mean like this?

00000001 = 2^0
00000010 = 2^1
00000100 = 2^3
00001000 = 2^4
...
 
I mean the infinite cartesian product {0,1} x {0,1} x {0,1} x ..., which is {0,1}^ω or 2^ω.
 
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} = ...
 
The set \{0, 1\}^{\mathbb{N}} 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 2^{\aleph_0}.


However, the set \{0, 1\}^{\omega} 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 \omega, and cardinality \aleph_0.


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 \{0, 1\}^\omega.
 
What is true then:

{0,1} x {0,1} x {0,1} x ... = \{0, 1\}^{\mathbb{N}}
or
{0,1} x {0,1} x {0,1} x ... = \{0, 1\}^{\omega}

or both - in some sense?
 
netzweltler said:
What is true then:

{0,1} x {0,1} x {0,1} x ... = \{0, 1\}^{\mathbb{N}}
or
{0,1} x {0,1} x {0,1} x ... = \{0, 1\}^{\omega}

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 \{0,1\}^\omega (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 \{0,1\}, 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 \omega as the exponent", then the second equation would be true.
 
Last edited:
Hurkyl said:
However, the set \{0, 1\}^{\omega} 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 \omega, and cardinality \aleph_0.

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: