# Induction on Real Numbers

One of my Fellows asked me whether total induction is applicable to real numbers, too ( or at least all real numbers ≥ 0) . We only used that for natural numbers so far. Of course you have to change some things in the inductive step, when you want to use it on real numbers.

I guess that using induction on real numbers isn't really possible, since $[r,r+\epsilon]$ with $\epsilon > 0$, $r \in \mathbb R$ is never empty.

Can you either give a good reason, why it isn't possible or provide an example where it is used?

• This is an eerie coincidence: for the last hour or so this morning I have been thinking about this very question! (I was even considering posting it as a question on this site.) I have a busy day today and will probably not get back to this question for another 12 hours or so, but when I do I'll have plenty to write, including some links to papers. Sep 7, 2010 at 12:15
• @Baju: interesting question! Now that the question has been answered in the affirmative, do you have an application of induction on real numbers in mind? Jul 8, 2011 at 14:29
• Something of this sort is used for one proof that closed intervals $[a,b] \subset \mathbb{R}$ are compact. It goes something like this: Given an open cover $\mathcal{O}$ of $[a,b]$, consider the points $x \in [a,b]$ such that $[a,x]$ is covered by finitely many open sets from $\mathcal{O}$. It is proven that $A = [a,b]$ by showing that $a \in A$ (the starting point of the IE you can get a start), that $A$ is open (IE most especially that if it contains any number less than $b$ , it has a number a bit bigger Sep 25, 2011 at 4:37
• Induction can be done beyond the reals to infinitesimals and infinity. Look up transfinite induction. Jan 15, 2017 at 16:19
• There is a variant of induction called the continuity method which can be used to prove results about reals or in general about any connected space in some situations. There is a tricki post on it which I saw earlier, but can't find it now. You may like to search for "continuity method" on some search engine. Dec 16, 2020 at 11:47

Okay, I can't resist: here is a quick answer.

I am construing the question in the following way: "Is there some criterion for a subset of $$[0,\infty)$$ to be all of $$[0,\infty)$$ which is (a) analogous to the principle of mathematical induction on $$\mathbb{N}$$ and (b) useful for something?" The answer is yes, at least to (a).

Let me work a little more generally: let $$(X,\leq)$$ be a totally ordered set which has
$$\bullet$$a least element, called $$0$$, and no greatest element.
$$\bullet$$ The greatest lower bound property: any nonempty subset $$Y$$ of $$X$$ has a greatest lower bound.

Principle of Induction on $$(X,\leq)$$: Let $$S \subset X$$ satisfy the following properties:
(i) $$0 \in S$$.
(ii) For all $$x$$ such that $$x \in S$$, there exists $$y > x$$ such that $$[x,y] \subset S$$.
(iii) If for any $$y \in X$$, the interval $$[0,y) \subset S$$, then also $$y \in S$$.
Then $$S = X$$.

Indeed, if $$S \neq X$$, then the complement $$S' = X \setminus S$$ is nonempty, so has a greatest lower bound, say $$y$$. By (i), we cannot have $$y = 0$$, since $$y \in S$$. By (ii), we cannot have $$y \in S$$, and by (iii) we cannot have $$y \in S'$$. Done!

Note that in case $$(X,\leq)$$ is a well-ordered set, this is equivalent to the usual statement of transfinite induction.

It also applies to an interval in $$\mathbb{R}$$ of the form $$[a,\infty)$$. It is not hard to adapt it to versions applicable to any interval in $$\mathbb{R}$$.

Note that I believe that some sort of converse should be true: i.e., an ordered set with a principle of induction should have the GLB / LUB property. [Added: yes, this is true. A totally ordered set with minimum element $$0$$ satisfies the principle of ordered induction as stated above iff every nonempty subset has an infimum.]

Added: as for usefulness, one can use "real induction" to prove the three basic Interval Theorems of honors calculus / basic real analysis. These three theorems assert three fundamental properties of any continuous function $$f: [a,b] \rightarrow \mathbb{R}$$.

First Interval Theorem: $$f$$ is bounded.

Inductive Proof: Let $$S = \{x \in [a,b] \ | \ f|_{[a,x]} \text{ is bounded} \}$$. It suffices to show that $$S = [a,b]$$, and we prove this by induction.
(i) Of course $$f$$ is bounded on $$[a,a]$$. (ii) Suppose that $$f$$ is bounded on $$[a,x]$$. Then, since $$f$$ is continuous at $$x$$, $$f$$ is bounded near $$x$$, i.e., there exists some $$\epsilon > 0$$ such that $$f$$ is bounded on $$(x-\epsilon,x+\epsilon)$$, so overall $$f$$ is bounded on $$[0,x+\epsilon)$$.
(iii) If $$f$$ is bounded on $$[0,y)$$, of course it is bounded on $$[0,y]$$. Done!

Corollary: $$f$$ assumes its maximum and minimum values.
Proof: Let $$M$$ be the least upper bound of $$f$$ on $$[a,b]$$. If $$M$$ is not a value of $$f$$, then $$f(x)-M$$ is never zero but takes values arbitrarily close to $$0$$, so $$g(x) = \frac{1}{f(x)-M}$$ is continuous and unbounded on $$[a,b]$$, contradiction.

(Unfortunately in the proof I said "least upper bound", and I suppose the point of proofs by induction is to remove explicit appeals to LUBs. Perhaps someone can help me out here.)

Second Interval Theorem (Intemediate Value Theorem): Suppose that $$f(a) < 0$$ and $$f(b) > 0$$. Then there exists $$c \in (a,b)$$ such that $$f(c) = 0$$.

Proof: Define $$S = \{x \in [a,b] \ | \ f(x) \leq 0\}$$. In this case we are given that $$S \neq [a,b]$$, so at least one of the hypotheses of real induction must fail. But which?
(i) Certainly $$a \in S$$.
(iii) If $$f(x) \leq 0$$ on $$[a,y)$$ and $$f$$ is continuous at $$y$$, then we must have $$f(y) \leq 0$$ as well: otherwise, there is a small interval about $$y$$ on which $$f$$ is positive.
So it must be that (ii) fails: there exists some $$x \in (a,b)$$ such that $$f \leq 0$$ on $$[a,x]$$ but there is no $$y > x$$ such that $$f \leq 0$$ on $$[a,y]$$. As above, since $$f$$ is continuous at $$x$$, we must have $$f(x) = 0$$!

Third Interval Theorem: $$f$$ is uniformly continuous.

(Proof left to the interested reader.)

Moreover, one can give even easier inductive proofs of the following basic theorems of analysis: that the interval $$[a,b]$$ is connected, that the interval $$[a,b]$$ is compact (Heine-Borel), that every infinite subset of $$[a,b]$$ has an accumulation point (Bolzano-Weierstrass).

Acknowledgement: My route to thinking about real induction was the paper by I. Kalantari "Induction over the Continuum".

His setup is slightly different from mine -- instead of (ii) and (iii), he has the single axiom that $$[0,x) \subset S$$ implies there exists $$y > x$$ such that $$[0,y) \subset S$$ -- and I am sorry to say that I was initially confused by it and didn't think it was correct. But I corresponded with Prof. Kalantari this morning and he kindly set me straight on the matter.

For that matter, several other papers exist in the literature doing real induction (mostly in the same setup as Kalantari's, but also with some other variants such as assuming (ii) and that the subset $$S$$ be closed). The result goes back at least to a 1922 paper of Khinchin, who in fact later used real induction as a basis for an axiomatic treatment of real analysis. It is remarkable to me that this appealing concept is not more widely known -- there seems to be a serious PR problem here.

Added Later: I wrote an expository article on real induction soon after giving this answer: it's very similar to what I wrote above, but longer and more polished. It is available here if you want to see it.

• I'm not sure you need a total order, induction can be defined on any set-like and well-partially ordered class. Sep 7, 2010 at 12:51
• @Asaf: Don't you need a lub/glb property at least to make induction go through? Sep 7, 2010 at 13:37
• @Pete, to define a function inductively on a class you don't need a lub/glb property. Just the two properties I mentioned earlier. Sep 7, 2010 at 15:30
• It seems to me that ii) is flawed. You could have $[0, x] = [0, y)$ (think of the case of natural numbers where y = x+1). Hence in your argument you cannot deduce that $y \notin S$. Sep 7, 2010 at 16:09
• @columbus8myhw: Thanks for pointing it out. I was looking only at the transfinite induction part of it (which is of course very standard). I agree that his proof of the Extreme Value Theorem has points in common with the real inductive approach (which is not "mine"!!), and it would be interesting to think more about this. In fact, it is my understanding that Heine's original proof of Heine-Borel was by transfinite induction(!), so I think this kind of approach used to be more standard. Feb 26, 2015 at 6:33

Such results on continuous induction are folklore dating back over a century - much older than the references in the Kalantari paper referenced by Pete L. Clark. I once had a large file of papers on this topic but, alas, it's long lost. But I can still recall one old paper  because the author was the world-renowned multi-talented Chinese linguist Yuen Ren Chao. If memory serves correct he did his thesis under Sheffer at Harvard on aspects of the continuum, so his BAMS paper was probably an offshoot of his thesis. Since Project Euclid seems to be having intermittent problems I have appended the short paper below. For some biographical information on Chao see here1 and here2.

 Yuen Ren Chao. A note on “Continuous mathematical induction".
Bull. Amer. Math. Soc. Volume 26, Number 1 (1919), 17-18.  • Bill Dubuque is right: there are many precedents for real induction in the literature. I have compiled some at the end of math.uga.edu/~pete/realinduction.pdf Sep 12, 2010 at 0:34
• Thanks for the pointer. I've always been curious to see what's in Chao's Harvard thesis but have never had the chance to investigate. If memory serves correct there are other references predating Chao. Sep 12, 2010 at 0:38

There's a phenomenal paper by Don Zagier which uses a sort of induction over the real numbers to give an explicit solution to some recurrence relations (which, it just so happens, calculate the Betti numbers of the moduli space of central Yang-Mills connections on bundles over Riemann surfaces). But you don't need to understand those words to appreciate Zagier's paper. The reference is:

Zagier, Don Elementary aspects of the Verlinde formula and of the Harder-Narasimhan-Atiyah-Bott formula. (English summary) Proceedings of the Hirzebruch 65 Conference on Algebraic Geometry (Ramat Gan, 1993), 445--462, Israel Math. Conf. Proc., 9, Bar-Ilan Univ., Ramat Gan, 1996.

• Is there any chance you could provide a link to this paper? Sep 7, 2010 at 22:25
• I don't know of an on-line version. At some point I photocopied the paper from the published proceedings, and I don't seem to have an electronic copy. Sep 8, 2010 at 2:03
• @PeteL.Clark I believe this is the paper: people.mpim-bonn.mpg.de/zagier/files/mpim/94-5/fulltext.pdf Aug 13, 2012 at 1:33

You can interpret mathematical induction on the natural numbers simply as "proof according to the method using which the world in question was constructed". The construction of $\mathbb{N}$ is inductive in nature, so it makes sense that induction should work. For a similar reason, you might want to accept the following as an induction method on $\mathbb{R}$:

Suppose that there is given a set $A \subset \mathbb{R}$ with the following properties:

1. $0 \in A$.
2. If $x \in A$ then $x+1 \in A$.
3. If $x \in A$ then $-x \in A$.
4. If $x,y \in A$ and $y \ne 0$ then $\frac{x}{y} \in A$.
5. $A$ satisfies the least upper bound property (equivalently, is complete, closed,etc. in $\mathbb{R}$).

Then $A = \mathbb{R}$.

• Does this cover the irrationals? Nov 17, 2021 at 7:58
• Lovely answer! Sorry to comment on such an old post - I thought it would be worth mentioning that a concrete example of a scheme like this being used is in order to prove "if $f: \Bbb R \to \Bbb R$ is continuous, and such that $f(x + y) = f(x) + f(y)$ for all $x, y$, then $f(x) = xf(1)$ for all $x$ - so $f$ is linear." To prove this it's helpful to actually weaken 4. a bit to only consider $x, y$ being of the form $1 + \dotsb + 1$. Jul 23, 2022 at 22:58

If you assume a particular limit ordinal for the cardinality of the reals, you can prove new theorems about them using transfinite induction with a bounded limit case! But I doubt these theorems have any application.

The other answers are very interesting but it is hard for me to believe in a process truly analogous to induction on a set which cannot be well-ordered. The ability to well-order the reals depends on the Axiom of Choice, and the precise consequences of such an ordering depend on the Continuum Hypothesis.

In the case of $[0,\infty[$, perhaps this looks like induction:

Let $A\subseteq [0,\infty[$ such that

$i)$ $[0,1]\subset A$

$ii)$ if $x\in A$ then $x+1\in A$.

Let $x\in[0,\infty[$. Then $x - \lfloor x\rfloor\in A$ by $i)$, and by repeating $ii)$ some times, we get $$(x - \lfloor x\rfloor)+\underbrace{1+\cdots+1}_{\text{\lfloor x\rfloor times}}=x\in A.$$ Therefore $A=[0,\infty[$.

After reading Pete Clark's excellent answer, I realized there is an interesting way to think about this real induction principle as an adaptation of a more general (and more trivial) notion of "topological induction" on connected spaces.

Topological Induction. Let $$X$$ be a connected topological space with basis $$\mathscr B$$, and suppose $$S\subseteq X$$ satisfies the following three properties:

1. $$S\neq\varnothing$$
2. $$S$$ satisfies the basis criterion with respect to $$\mathscr B$$ (that is, for all $$s\in S$$, there exists some $$B\in\mathscr B$$ such that $$s\in B\subseteq S$$)
3. If $$U\subseteq S$$ is open, then $$\overline{U}\subseteq S$$.

Then $$S=X$$. Proof. Property (2) says $$S$$ is open (by definition). Hence $$\overline S\subseteq S$$ by (3), so $$S$$ is closed. But $$\varnothing$$ and $$X$$ are the only subsets of a connected space that are both open and closed, and $$S$$ is nonempty by (1), so $$S=X$$. $$\square$$

Real Induction. Now let $$X=[0,\infty)$$ with the standard topology, which has a basis consisting of open intervals and intervals of the form $$[0, a)$$. Let's call intervals of the form $$[0, a)$$ left neighborhoods. Then the above axioms can be tweaked as follows, reproducing (almost) exactly Pete Clark's axioms but in a more topological language.

1. $$S\neq\varnothing$$
2. $$S$$ satisfies the basis criterion with respect to the set of all left neighborhoods
3. If $$U\subseteq S$$ is a left neighborhood, then $$\overline{U}\subseteq S$$.

Then $$S=X.$$ [(1) and (2) are slightly different from Pete Clark's, but it is straightforward to check that they are equivalent.]

Analytical Proof. See Pete Clark's answer. $$\square$$

Topological Proof. Since the set of all left neighborhoods is itself a topology on $$X$$, (2) says that $$S$$ is open in this topology, hence $$S$$ is a left neighborhood (hence also open in the standard topology). Therefore, by (3) $$\overline S\subseteq S$$, so $$S$$ is closed (in the standard topology). Since $$X$$ is connected and $$S$$ is nonempty by (1), $$S=X$$. $$\square$$

• An order topology is connected if and only if it is Dedekind complete and order-dense: see Theorem 2.7 of alpha.math.uga.edu/~pete/instructors_guide_2017.pdf. So I don't think this is actually more general than the Principle of Ordered Induction, since e.g. that applies to Well-Ordered Sets, which are not connected in the order topology. Oct 3, 2022 at 19:14
• Your formulation is interesting though. It reminds me a bit of "Induction on Connectedness" in the Elementary Topology Problem Textbook of Viro et. al, but it seems not to be the same. Oct 3, 2022 at 19:16