Why is the sequence of infinitely many coin tosses uncountable?

[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

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

 

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

 

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

 

[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".)

 

[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$.

 

[FactChecker]

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.

 

[jbriggs444]

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.

 

[rayven1lk]

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.

 

[phinds]

(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

 

[WWGD]

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... ;).

 

[caveman1917]

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

 

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

 

[gopher_p]

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

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.

 

[caveman1917]

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.