3
$\begingroup$

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"?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Interesting. I haven't heard about that one before. $\endgroup$ – Stefan Mesken Sep 22 '17 at 9:17
  • 1
    $\begingroup$ You learn something new every day that you learn something new. $\endgroup$ – Asaf Karagila Sep 22 '17 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.