Cantor Flips A Coin 


This page has been Tagged As Maths 
Consider the collection of natural numbers, including 0. Call it N. We all agree that N, also described as the set of nonnegative integers, is infinite.
Now imagine flipping a coin at times t_0, t_1, t_2, etc. If you're worried that this will take infinite amounts of time, we can suppose that each flip  because we are practised  takes half the time of the previous flip, so all the flips can be done in finite time. However, we're in the realm of Pure Mathematics now, chasing the puzzle for its own sake, and not worrying about practicalities.
So what might the result be?
Well, you might get all heads, you might get all tails, you might get alternating heads and tail, in practice, of course, you'll get something that looks random.
Let's think about all the possible results of flipping the coin. All possible results. Let's let F be the set of all possible results obtained from flipping the coin are each of t_0, t_1, t_2, and so on.
We can think of F as the collection of functions from N to {H,T}.
So we have N and we have F. We can now wonder if it's possible to have a function from N to F that hits every element of F.
Suppose we can. We'll show that things go horribly wrong.
So we have m:N>F, and for every f in F, there is an n in N such that m(n)=f. We now construct an interesting element of F, let's call it x. Remember, an element of F is a function N>{H,T}, so to define x we have to say for each n in N whether x(n) is H or T.
Choose an n, how will we decide what x(n) should be?
Well, n has an associated element of F, namely m(n). This is an element of F, so it's a function N>{H,T}. That means we can look at m(n)(n). That's either H or T, and we choose x(n) to be the opposite.
Choose n in N, and suppose m(n) = x. Then m(n)(n) = x(n). but we explicitly chose x so that m(n)(n) is not equal to x(n).
We have a contradiction. Our assumption that there is a function m:N>F that hits every element of F leads to a problem. So such a function cannot exist.
So given N, which is infinite, we cannot have a function m from N to F such that every F gets hit. In short, there aren't enough elements in N to "cover" every element in F. So F must be bigger.
You might like to see the page about Stacking Blocks, or the one about Balls In Barrels.
Contents 
Links on this page 

Quotation from Tim BernersLee 