Why is the sequence of infinitely many coin tosses uncountable?

  • Thread starter rayven1lk
  • Start date
  • Tags
    Sequence
In summary, the conversation discusses Cantor's diagonal argument for proving that the set of sequences of coin tosses is uncountable. The argument involves mapping the set of sequences to real numbers in the interval [0,1] and showing that the resulting set is uncountable. The use of binary expansions and the concept of doubling binary sequences is also discussed.
  • #1
rayven1lk
3
0
Hi everyone,

I recently began a grad program and we have started taking a course in stochastic methods. However I can't figure out the answer to a question posed by the professor which is:

http://i.imgur.com/dkdEDMo.jpg

http://imgur.com/dkdEDMo [Broken]

He proved this by contradiction. It started off by illustrating some type of a matrix that "exhausted" all possibilities of the sequences, then taking a diagonal line through the matrix and inverting each entry. So for example, each H (head) would becomes a T (tail) and vice versa. So this creates a new sequence which does not belong in the list and therefore makes it uncountable.

My problem is not being able to see how inverting the entries in the diagonal creates a sequence which is not in the list of sequences. I would really appreciate someone's help in this matter.

Thanks
 
Last edited by a moderator:
Mathematics news on Phys.org
  • #2
The the ##n##th entry of created sequence differs from the ##n##th entry of the ##n##th sequence on the given list of sequences. Since the created sequence differs from every sequence on the list, it can't be on the list itself.
 
  • #3
This sounds /reads like Cantor's diagonal argument. Like using binary to show the Reals are uncountable , using their binary decimal expansions; send every sequence of 0's and 1's to the Real number with that expansion.
 
  • #4
Think of each head as a "1" and each tail as a "0". A "sequence of infinitely many coin tosses" can be thought of as a infinite sequence of "1"s and "0"s and, putting a decimal point in front of it, as a real number, between 0 and 1, expressed in binary. That is, there exist a one-to-one and onto function from the set of such sequences to the real numbers between 0 and 1. The set of all such sequences is uncountable because the set of real numbers, between 0 and 1, is uncountable.

(By the way, your initial reference to "the sequence of infinitely many coin tosses" confused me for a moment. Such a sequence is NOT "uncountable" (a "sequence", pretty much by definition, is countable). You meant "the set of all sequences of infinitely many coin tosses".)
 
  • #5
If you map this set of sequences of coin flips to the real numbers in ##[0,1]## via the "just change all of the ##h##s to ##0##s and ##t##s to ##1##s and interpret the output as a binary expansion" function, you will not get something 1-1 due to the problem of multiple binary representatives; e.g. ##0.\overline{1}=1##.
 
  • #6
rayven1lk said:
My problem is not being able to see how inverting the entries in the diagonal creates a sequence which is not in the list of sequences. I would really appreciate someone's help in this matter.
Because you forced it to be different at that position from every single number on the list. So it can not be any number on that list.
 
  • #7
FactChecker said:
Because you forced it to be different at that position from every single number on the list. So it can not be any number on that list.

Careful with the wording. Flipping the first position made it different from the first sequence. Flipping it at the second position made it different from the second sequence...

For every sequence that was already on the list you have forced it to be different from that sequence, hence the "anti-diagonal" sequence cannot have been on the list.
 
  • #8
jbriggs444 said:
Careful with the wording. Flipping the first position made it different from the first sequence. Flipping it at the second position made it different from the second sequence...

For every sequence that was already on the list you have forced it to be different from that sequence, hence the "anti-diagonal" sequence cannot have been on the list.

Now I get it!

Thanks for putting it that way. Makes a lotta sense.
 
  • #9
HallsofIvy said:
(By the way, your initial reference to "the sequence of infinitely many coin tosses" confused me for a moment. Such a sequence is NOT "uncountable" (a "sequence", pretty much by definition, is countable). You meant "the set of all sequences of infinitely many coin tosses".)

That puzzled me too and I don't know math the way you do so thanks for that clarification. I REALLY couldn't figure out how the subject line made sense
 
  • #10
rayven1lk said:
Now I get it!

Thanks for putting it that way. Makes a lotta sense.

Good, now think about what happens if you include that new sequence of the previous list... ;).
 
  • #11
gopher_p said:
If you map this set of sequences of coin flips to the real numbers in ##[0,1]## via the "just change all of the ##h##s to ##0##s and ##t##s to ##1##s and interpret the output as a binary expansion" function, you will not get something 1-1 due to the problem of multiple binary representatives; e.g. ##0.\overline{1}=1##.

The set of "doubled" binary sequences is countable though (it is the set of binary sequences that are eventually constant), so you can just remove those (and the real numbers they map to).
 
Last edited:
  • #12
Actually you don't have to remove them, the set of doubled binary sequences is 2-to-1 to its image in ##[0,1]##, both infinite, hence a bijection exists.
 
Last edited:
  • #13
caveman1917 said:
The set of "doubled" binary sequences is countable though (it is the set of binary sequences that are eventually constant), so you can just remove those (and the real numbers they map to).

caveman1917 said:
Actually you don't have to remove them, the set of doubled binary sequences is 2-to-1 to its image in ##[0,1]##, both infinite, hence a bijection exists.

Of course. The point was that, although there is a bijection - the sets have the same cardinality - the "naive" function suggested, while surjective, is not injective.
 
  • #14
gopher_p said:
Of course. The point was that, although there is a bijection - the sets have the same cardinality - the "naive" function suggested, while surjective, is not injective.

Certainly. It only had to be surjective for the question asked though, not injective. The unnecessarily strong, and incorrect, statement on bijectivity just seemed easily fixed - at least relative to a related proof of a bijection between the unit square and the unit interval by interleaving binary sequences.
 

1. What is the meaning of an uncountable sequence of coin tosses?

An uncountable sequence of coin tosses refers to a sequence of events where the number of outcomes is infinite and cannot be counted or listed. In other words, it is a never-ending sequence of coin tosses that cannot be assigned a specific number.

2. How is an uncountable sequence of coin tosses different from a countable sequence?

A countable sequence is a sequence of events where the number of outcomes is finite and can be counted or listed. This means that each outcome in a countable sequence can be assigned a specific number. On the other hand, an uncountable sequence has an infinite number of outcomes and cannot be assigned a specific number to each outcome.

3. Why is the sequence of infinitely many coin tosses considered uncountable?

The sequence of infinitely many coin tosses is considered uncountable because it has an infinite number of possible outcomes. Even if we were to list all the possible outcomes, we would never reach an end, making it impossible to assign a specific number to each outcome.

4. Can the sequence of infinitely many coin tosses ever be counted?

No, the sequence of infinitely many coin tosses cannot be counted. Since it has an infinite number of outcomes, there is no way to assign a specific number to each outcome, making it impossible to count or list all the outcomes.

5. How is the uncountable sequence of coin tosses related to the concept of infinity?

The uncountable sequence of coin tosses is related to the concept of infinity because it represents a never-ending sequence of events. Just like infinity, the sequence of coin tosses has no beginning or end, and it cannot be fully comprehended or counted.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
14
Views
1K
Replies
4
Views
2K
  • Calculus
Replies
3
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
  • Linear and Abstract Algebra
2
Replies
43
Views
5K
Replies
255
Views
25K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
10K
  • Set Theory, Logic, Probability, Statistics
3
Replies
93
Views
16K
  • Math Proof Training and Practice
4
Replies
116
Views
14K
  • Programming and Computer Science
Replies
12
Views
3K
Back
Top