Cantor Flips A Coin 


This page has been Tagged As Maths 
Consider the collection of natural numbers, including 0. Call it $\mathbb{N}$. We all agree that $\mathbb{N}$, also described as the set of nonnegative integers, is infinite.
So the result is a function $f:\mathbb{N}\to\{H,T\}$ 
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. We'll write $F$ for the set of all possible results obtained from flipping the coin at each of times $t_0,$ $t_1,$ $t_2,$ and so on.
We can think of $F$ as the collection of functions from $\mathbb{N}$ to $\{H,T\}$. In symbols, $F=\left\{f:\mathbb{N}\to\{H,T\}\right\}.$ We can simplify that slightly by saying the set of possible results of a single flip is $R=\{H,T\},$ so $F=\left\{f:\mathbb{N}\to R\right\}.$
So we have two sets, $\mathbb{N}$ and $F$. Whenever we have two sets it's always interesting to compare them. In particular, it's interesting to ask whether we can have an injective function from one to the other, and whether we can have a surjective function.
An injective function from $A$ to $B$ is one where any given element of $B$ gets hit at most once. 
But what about a surjective function? Can we have a function from $\mathbb{N}$ to $F$ that hits every element of $F$ at least once?
No.
A standard technique is to assume that it is possible, and then from that, derive a contradiction.
So let's suppose we can. Let's suppose we have a function from $\mathbb{N}$ to ${F}$ that hits every element of $F$ at least once. Let's call it $m$.
So we have $m:\mathbb{N}\to{F},$ and for every $f\in{F}$, there is an $n\in\mathbb{N}$ such that $m(n)=f$. We now construct an interesting specific element of $F$, we'll call it $x.$ Remember, an element of $F$ is a function $f:\mathbb{N}\to R,$ so to define $x$ we have to say for each $n\in\mathbb{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 $\mathbb{N}\to R$. That means we can look at $m(n)(n)$. That's in $R$, so it's either $H$ or $T$.
And here's the trick: we choose $x(n)$ to be the opposite.
But $m$ hits every element of $F,$ so there is an $n$ in $\mathbb{N}$ such that $m(n)=x$.
Which one?
Pick any element $k$ in $\mathbb{N}.$ We will show that $m(k)$ is not $x.$
Well, suppose $m(k)$ is $x.$ Then $m(k)(k)= x(k).$ But we explicitly defined $x$ so that $m(k)(k)$ is not equal to $x(k).$
We have a contradiction. Our assumption that there is a function $m:\mathbb{N}\to{F}$ that hits every element of $F$ leads to a problem. So such a function cannot exist.
So given $\mathbb{N},$ which is infinite, we cannot have a function $m$ from $\mathbb{N}$ to $F$ such that every $F$ gets hit. In short, there aren't enough elements in $\mathbb{N}$ to "cover" every element in $F.$
So $F$ must be bigger.
Bigger than $\mathbb{N}.$
Which is infinite.
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 