Can you expand induction proofs to the real numbers?

180 Views Asked by At

Everyone knows the principle of induction, where you first prove a base case for some $n_0\in \mathbb{N}$, and than show that by assuming the case for an $n \in \mathbb{N}$ the $n+1$ case follows. This is true because of the application of some sort of domino principle. However, you could also try to combine this principle with an epsilon proof. For any statement $S_x$, show that $S_{x_{0}}$ holds and than show that from $S_x$, $S_{x+\epsilon}$ follows, for $|\epsilon |>0$, where $\epsilon,x_0,x \in \mathbb{R}$. If I am not mistaken this should at least work for proving statements for all rational numbers, please correct me if I am wrong(I am still new to this). But does this also work for proofs of real numbers and if not, is there some sort of "induction for the reals"?

I hope that I could make my question clear enough. I am quite sorry for any sort of mistakes and hope nonetheless, that you could help/correct me.

2

There are 2 best solutions below

2
On BEST ANSWER

You have to be quite careful where you put the quantifiers in your principle, to make it valid. If you have $S_{x_0}$ and, for some $\varepsilon > 0$, you have that for all $x, y \in \Bbb{Q}$ (or $\Bbb{R}$) $S_x$ implies $S_y$ whenever $|x - y| < \varepsilon$, then you have that $S_x$ for all $x \in \Bbb{Q}$ (or $\Bbb{R}$). This is really just induction over the natural numbers for the proposition for $n \in \Bbb{N}$ that $S_x$ holds for all $x$ with $|x - x_0| < n\epsilon$.

The general replacement for induction in $\Bbb{R}$ is the principal of completeness: every non-empty set that is bounded above has a least upper bound. One application of completeness is to prove the Archimedean property: if $\epsilon > 0$, then for any $x$ there is $n \in \Bbb{N}$ such that $x < n\epsilon$ (the proof begins by assuming that $x$ is an upper bound for $\{n\epsilon \mid n \in \Bbb{N}\}$ and then derives a contradiction using completeness). The Archimedean property justifies the line of argument in the previous paragraph.

1
On

To add on to Rob Arthan's answer: the induction principle does not work if you put the quantifiers differently, that is: for all $x$ there is some $\epsilon > 0$ such that if $S_x$ holds, then also $S_y$ for all $y\in \mathbb{R}$ with $\lvert x-y\rvert < \epsilon$. The problem is that now the $\epsilon$ you get might get smaller and smaller when you try to go away from $x_0$ and you don't get very far. A counterexample could be the statement $$S_x = x \in (-1,1),$$ which is certainly true for $x = 0$ and around each $x\in (-1,1)$ you can find a small interval that is still completely contained in $(-1,1)$.