What is the fixed-point theorem proof that the reals are uncountable?

198 Views Asked by At

I know the diagonal argument that the reals are uncountable, but I've heard it said that there is a so-called "fixed point theorem" version of the proof. However, in all my looking up of fixed point theorems, I don't see how such a theorem could demonstrate that the reals are uncountable. They usually demonstrate that for some $x$ we have $x=f(x)$, but if we are showing that $f$ is not a bijection $f:\mathbb{N}\rightarrow \mathbb{R}$ then this wouldn't seem to help.

Can anyone explain what the fixed point theorem proof is and why it counts as a "fixed point theorem"?

1

There are 1 best solutions below

2
On BEST ANSWER

In category theory there is Lawvere's fixed point theorem. Which essentially means—when applied to sets—the following:

Suppose that there is a surjection from $f\colon A\to B^A$, then every function $h\colon B\to B$ has a fixed point.

Of course, there is a function $h\colon\{0,1\}\to\{0,1\}$ without a fixed point, therefore there is no surjection from $A$ onto $\{0,1\}^A$, or its power set.

About $\Bbb R$, this can be slightly tricky to obtain as a direct corollary, but it is enough to notice that there is an injection from $\Bbb R$ to $\Bbb{N^N}$, by mapping $\Bbb R$ to $(0,1)$ and then mapping each number to its unique non-terminating binary expansion. Now by Lawvere there is no surjection from $\Bbb N$ onto $\Bbb{N^N}$, and thus no surjection onto $\Bbb R$ either.