Real Induction

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

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

• assumption one: $P([a,a])$
• assumption two: $P([a,x])$ implies $P([a,y])$ for some real numbers $x < y$
• hypotheses two: $P([a,z))$ implies $P([a,z])$ for some real numbers $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.

Assume as a contrarian might, that we have the necessary predicate, real numbers, and conditions above, but there's a catch $P([a,b])$ does not hold!

This means there is some non-empty subset of $[a,b]$ such that for every of its points $r$, $\neg P(\{r\})$. Since every bounded real set has a greatest lower bound, let $c$ be the greatest lower bound of our the set on which $P$ does not hold. Then we have three possible cases:

• $c = a$. Consider then our first two conditions. By assumption one we have $P([c,c])$ and by the second assumption, $P([c, c + \varepsilon])$ (where, doing its usual thing $\varepsilon > 0$). But contradicts our statement that $c$ is the infimum of the $\neg P$ set.

• Of course, it could be the case that $c > a$ and $P(\{c\})$. Then, we'd have one of $P((c, c + \varepsilon))$, $P((c, c + \varepsilon])$, or $P(\{c + \varepsilon,c\}) \subset Q$.*

  Morever, we'd also have $P([a,c])$. Then if we let $x = c$ and $y = c + \varepsilon$, our second assumption would allow $P([a,c + \varepsilon])$ at the same time as $\neg P([c + \varepsilon,c + \varepsilon])$. Again a contradiction.

• Lastly, it could be the case that $c > a$ and $\neg P(\{c\})$. Then we'd have $P([a,c))$. And letting $z = c$, our third assumption would tell us $P([a,c])$. We'd have both $P(\{c\})$ and $\neg P(\{c\})$. Again a contradiction.

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

*Technically these cases can be reduced to the open interval $P((c, c + \varepsilon))$, but that might require some other theorems.