Cantor Flips A Coin

Recent changes
Table of contents
Links to this page

This page has been
Tagged As Maths
An alternative to the page talking about the occasion when Cantor Visits Hilberts Hotel ...

Consider the collection of natural numbers, including 0. Call it $\mathbb{N}$. We all agree that $\mathbb{N}$, also described as the set of non-negative integers, is infinite.

So the result is a function
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 at each of ties $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\}.$

So we have two set, $\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$ where any given element of $B$ gets hit at most once.
We can have an injective function from $\mathbb{N}$ to $F$, that's easy, and we leave it as an exercise for the interested reader. Just think carefully about what we're actually asking for, and see what you can come up with.

But what about a surjective function? Can we have a function $\mathbb{N}$ to $F$ that hits every element of $F$ at least once?


How do we prove that something like that is impossible?

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 element of $F$, let's call it $x.$ Remember, an element of $F$ is a function $f:\mathbb{N}\to\{H,T\},$ 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}->\{H,T\}$. That means we can look at $m(n)(n)$. That's either $H$ or $T$.

And here's the trick: we choose $x(n)$ to be the opposite.

So now $x$ is a function from $\mathbb{N}$ to $\{H,T\}$, so it's an element of $F$ as required.

That means there is an $n$ in $\mathbb{N}$ such that $m(n)=x$.

Which one?

(still to be crafted ...)

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.

What does that mean?

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.

What now?

You might like to see the page about Stacking Blocks, or the one about Balls In Barrels.



Links on this page

Site hosted by Colin and Rachel Wright:
  • Maths, Design, Juggling, Computing,
  • Embroidery, Proof-reading,
  • and other clever stuff.

Suggest a change ( <-- What does this mean?) / Send me email
Front Page / All pages by date / Site overview / Top of page

Universally Browser Friendly     Quotation from
Tim Berners-Lee
    Valid HTML 3.2!