Daily Archives: May 26, 2009

\epsilon Induction

Induction over natural numbers is a standard tool in Mathematics. But what about doing induction over 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)} \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 \right . 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 .