Why is the sequence of infinitely many coin tosses uncountable?

1. Sep 8, 2014

rayven1lk

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: May 6, 2017
2. Sep 8, 2014

gopher_p

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

WWGD

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

HallsofIvy

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

gopher_p

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

FactChecker

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

jbriggs444

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

rayven1lk

Now I get it!

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

9. Sep 11, 2014

phinds

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

WWGD

Good, now think about what happens if you include that new sequence of the previous list... ;).

11. Sep 12, 2014

caveman1917

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

caveman1917

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
13. Sep 12, 2014

gopher_p

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

caveman1917

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.