1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Why is the sequence of infinitely many coin tosses uncountable?

  1. Sep 8, 2014 #1
    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://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.

    Last edited by a moderator: May 6, 2017
  2. jcsd
  3. Sep 8, 2014 #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.
  4. Sep 8, 2014 #3


    User Avatar
    Science Advisor
    Gold Member

    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.
  5. Sep 9, 2014 #4


    User Avatar
    Science Advisor

    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".)
  6. Sep 9, 2014 #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##.
  7. Sep 10, 2014 #6


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    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.
  8. Sep 11, 2014 #7


    User Avatar
    Science Advisor

    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.
  9. Sep 11, 2014 #8
    Now I get it!

    Thanks for putting it that way. Makes a lotta sense.
  10. Sep 11, 2014 #9


    User Avatar
    Gold Member

    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
  11. Sep 12, 2014 #10


    User Avatar
    Science Advisor
    Gold Member

    Good, now think about what happens if you include that new sequence of the previous list... ;).
  12. Sep 12, 2014 #11
    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: Sep 12, 2014
  13. Sep 12, 2014 #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: Sep 12, 2014
  14. Sep 12, 2014 #13
    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.
  15. Sep 12, 2014 #14
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook