Real Induction

Did you know you can do mathematical induction over the reals? Don't listen to the naysayers. Follow along!

Theorem: Real Induction
Consider a predicate $P$ and a closed real interval $[a,b]$ where $a$ < $b$, if the following hold:

• base assumption: $P([a,a])$
• hypothesis one: $P([a,x])$ implies $P([a,y])$ for some real numbers $x < y$
• hypothesis two: $P([a,z))$ implies $P([a,z])$ for some real number $z$

Then $P([a,b])$.

---

Proof:

First of all, shout out to Peter Clarke for his paper on real induction. Our assumptions are slightly different, but he inspired this proof by contradiction.

For a given predicate $P$ and some real numbers $a < b, x < y, z$, let's assume that we have our base assumption, hypothesis one, and hypothesis two all hold, but a contrarian claims $P([a,b])$ does not hold!

This means there is some non-empty subset, $F$ of $[a,b]$ such that $\neg P(F)$. Since every bounded real set has a greatest lower bound, and $a$ is a lower bound of $F$, let $c$ be the infimum of $F$. Then we have three possible cases:

• $c = a$.
• $c > a$ and $c \not \in F$
• $c > a$ and $c \in F$

Let's investigate each case:

• In the case where, $c = a$ By the base assumption we have $P([c,c])$ and by hypothesis one, $P([c, c + \varepsilon])$ (where, doing its usual thing $\varepsilon > 0$). But this means $[c, c + \varepsilon] \not \in F$, contradicting our statement that $c$ is the infimum of $F$.

• When $c > a$ and $c \not \in F$, we have $P([a, c])$, from which hypothesis one gives us $P([a, c + \varepsilon])$. Again, contradicting the claim that $c$ is the infimum of $F$.

• Lastly, in the case that $c > a$ and $c \in F$, we'd have $P([a,c))$. However, hypothesis two tells us that $P([a,c])$ holds. So, we have both $c \not \in F$ and $c \in F$. Once again we've contradicted ourselves.

Thus our contrarian's claim is refuted. Under our three assumptions, $P([a,b])$ holds. $\blacksquare$

Also, Joel David Hamkins has a nice proof in his book, Proof and the Art of Mathematics.