\(\epsilon\) Induction

Induction over natural numbers is a standard tool in Mathematics. But what about doing induction over real numbers (non-negative real numbers)? The structure is different and it’s not immediately clear what is meant, so let me clarify it.

Let \(P(v)\) be a proposition that we want to show for all \(v \in \mathbb{R}^+_0\).

Then we can use the following “induction principle” to prove it:

\[ \exists \epsilon \in \mathbb{R}^+ \] \[ \text{a)} \forall u \in \left [0,\epsilon \right ]: P(u) \] \[ \text{b)} \forall v \ge \epsilon: \left( \forall u \in \left [0, v - \epsilon \right ]: P(u) \right ) \Rightarrow P(v) \]

It’s easy to show that this is a correct way to prove it. I’ll use induction over natural numbers to prove it :-)

Let \(I_k := \left [k \cdot \frac \epsilon 2, (k+1) \cdot \frac \epsilon 2 \right ]\). Then let’s show by induction over \(k\) that \(\text{(*)} \forall u \in I_k: P(u)\):

Base:

From a) it follows that (*) already holds for \(I_0\) and \(I_1\).

Induction Step (\(k \ge 2\)):

If (*) holds for \(I_0, ..., I_{k-1}\), then it obviously holds for all \(u \in \left [ 0, k \cdot \frac \epsilon 2 \right ]\).

Fix \(v \in I_k\), then \(v \le (k+1) \cdot \frac \epsilon 2 \Leftrightarrow v - \epsilon \le (k-2) \cdot \frac \epsilon 2 < k \cdot \frac \epsilon 2\). With b) it follows that \(P(v)\) holds.

That is, \(P(v)\) \(\forall v \in I_k\).

It should be possible to show that you can generalize this to: \[ \exists \epsilon \in \mathbb{R}^+ \] \[ \text{a)} \forall u \in \left [0,\epsilon \right ]: P(u) \] \[ \text{b)} \left( \forall u \in \left [\psi(v), \phi( v ) \right ]: P(u) \right ) \Rightarrow P(v) \] with \(\phi( v ): \mathbb{R}^+ \to \mathbb{R}^+_0\), \(\psi( v ): \mathbb{R}^+ \to \mathbb{R}^+_0\) and \(\psi(v) \le \phi(v) < v\).