In-Depth Explanation of How to Do Mathematical Induction Over the Set $\mathbb{R}$ of All Real Numbers?

Question

     I've seen in the answers to a few different questions here on the Mathematics Stack Exchange that one can clearly do mathematical induction over the set $\mathbb{R}$ of all real numbers. I am, however, having quite a difficult time understanding how the methods described in both those questions' answers and some reference materials to which they link. In particular, I can't seem to figure out exactly how the techniques described therein parallel the methods codified in the axiom of induction for use when doing mathematical induction over the set $\mathbb{N}$ of all natural numbers.
     If somebody would be so kind as to provide me with a more detailed explanation of how to do mathematical induction over the set $\mathbb{R}$ of all real numbers within about the next day or so, then I would be very grateful! The answer should be understandable by any beginning calculus student who also has a rudimentary understanding of set theory and mathematical logic. I've provided links to both the relevant questions and whatever reference material mentioned in them that seemed like good leads when I found them no matter how inscrutable they might have been at the time.

---

Questions About Induction Over the Real Numbers:

• Induction on Real Numbers
• Is it possible to use mathematical induction to prove a statement concerning all real numbers, not necessarily just the integers? [duplicate]
• Extending a theorem true over the integers to reals and complex numbers

Question-Derived Reference Material:

• 'The Instructor's Guide to Real Induction' by Pete L. Clark

---

P. S.: I also have the following follow-up questions:

• Version of the Axiom of Induction for Real Induction?
• Real Induction Over Multiple Variables?

Answer 1

I feel like I am jumping into this discussion rather late, but I feel that the other answers given so far have to a large extent missed the point of the question.

As a matter of fact, you CAN do induction on the real numbers under the standard order! This is called "real induction," and the main result is proven and described at length in the references given by the original poster. Explicitly, suppose $S$ is a subset of the closed interval $[a,b]$ with the following properties:

1. $a$ is in $S$.
2. For every $x$ in $[a,b)$, there is a number $y$ in $[a,b]$ such that every number $z$ in $[x,y]$ is in $S$.
3. For every $x$ in $[a,b]$, if $[a,x)$ is a subset of $S$, then $x$ is in $S$.

Then $S=[a,b]$.

Although it doesn't involve a successor function, this captures a lot of the flavor of both induction on the natural numbers and transfinite induction. Moreover, because it uses the usual order on $\mathbb{R}$, it can be used to prove interesting theorems about real numbers, including the Intermediate Value Theorem, the Extreme Value Theorem, and the Bolzano-Weierstrass Theorem.

For an example of how to use real induction in a proof, look at Theorem 5 (the Extreme Value Theorem) in the first reference. Clark proves that every continuous function on a closed interval $[a,b]$ is bounded as follows:

Let $f$ be a continuous real-valued function on the closed interval $[a,b]$. Take $S$ to be the set of numbers $x$ in $[a,b]$ for which $f$ is bounded on $[a,x]$.

1. Clearly $f$ is bounded on $[a,a]$ (any number greater than $f(a)$ is an upper bound, and any number less than $f(a)$ is a lower bound), so $a$ is in $S$.
2. Suppose $x$ is in $S$. Then $f$ is bounded on $[a,x]$. Since $f$ is continuous at $x$, there is a $\delta>0$ such that, for all $y$ in $[x-\delta,x+\delta]$,$\left|f(y)\right|<\left|f(x)\right|+1$, so $f$ is bounded on $[a,x+\delta]$.
3. Now suppose $[a,x)$ is a subset of $S$. Since $f$ is continuous at $x$, there is a positive number $\delta < x − a$ such that $f$ is bounded on $[x − \delta, x]$. But since $a < x − \delta < x$, we know also that $f$ is bounded on $[a, x − \delta]$, so $f$ is bounded on $[a, x]$.

Since $S$ satisfies the three properties given above, it follows by real induction that $S=[a,b]$, so $f$ is bounded on $[a,b]$.

Answer 2

I didn't see this question until now.

The accepted answer is indeed a good one. I have only very minor comments about it:

(i) What is described there is indeed what I call real induction. Exactly the same inductive setup was given by D. Hathaway, who called it continuity induction. These two works were completely independent of each other. (As you can see elsewhere on this site, I was thinking about this in September 2010. Hathaway's article was published in May of 2011. As the gap between submission and publication is usually at least a year, I have little doubt that he was first.) On the other hand, a lot of other mathematicians have given inductive schemes for intervals on the real line over the years. Section 1.2 of my Instructor's Guide lists 13 publications on the subject prior to Hathaway's. The last of these is a paper by I. Kalantari. My work was dependent on his: I read his paper, learned with great excitement that you can do induction on the real numbers, and expanded on that theme. I have also been told by some people working in the area of differential equations that these kind of inductive arguments are rather standard in that area. $\newcommand{\R}{\mathbb{R}}$

(ii) Yes, the formulation that I call "Real Induction" is formulated in terms of a closed bounded interval $[a,b]$ in the real line. (When you look at all the prior literature in the area, I think it becomes clear that a large contributing factor to the PR that my take on this material has gotten is the snappy name I chose, so I don't apologize for that.) In Section 2 I formulate a notion of an inductive subset of a linearly ordered set $(X,\leq)$ and show that the only inductive subset of $X$ is $X$ itself is equivalent to Dedekind completeness of $X$. I then mention that every closed interval in $\R$ is Dedekind complete. $\R$ is a closed interval in $\R$, so in that formulation real induction does apply to $\R$. In fact every interval in $\R$ is Dedekind complete: an ordered set is Dedekind complete iff the subset obtained by adjoining least and greatest elements if they are not already present is complete, and doing this to any interval in $\R$ yields something order isomorphic to a closed, bounded interval $[a,b]$.

(iii) I agree that in practice, proving something separately on $[0,\infty)$, $(-\infty,0]$ and combining is often easier than working directly with $(-\infty,\infty)$.

Answer 3

What you're talking about is transfinite induction. http://mathworld.wolfram.com/TransfiniteInduction.html

Basically induction is showing a proposition, $P$, is true on a well-ordered set, $(S,\lt)$ by the following:

1. $P(0)$ is true for the "first" element, $0\in S$
2. If $P(b)$ is true for all $b<a$ then $P(a)$ is true

Let's unpack this a little. The important part is the "well-ordered" part.

An ordered set, $(S,\lt)$ is well ordered if every subset has a minimum element.

For example, $\mathbb{N}$ is well ordered. Any subset of the natural numbers certainly has a least element.

This is NOT true of the real numbers with the (normal) ordering. For example, $(0,1)$ does NOT have a least element. So you may not induct over $\mathbb{R}$ with the NORMAL ordering.

What well ordering means (or well, implies) is that for every element in $s\in S$, there is a "next" element $t$. For example the number $3$ has the "next" number $4$. To see this consider the set $T_s\subset U$ where $T_s=\{t\in S \colon t>s\}$. There is a minimum element in this set, which is the successor of $s$. It is the next element.

This is not true with $\mathbb{R}$ with the normal ordering. For example, what real number comes after $1$? There is none, you can always find one closer.

But what if we didn't use the "normal ordering"? Well thanks to the axiom of choice, we may prove the well ordering theorem (or axiom perhaps?) https://math.berkeley.edu/~kpmann/Well-ordering.pdf

What the well ordering theorem (axiom) says is that EVERY set, even $\mathbb{R}$ can be well ordered. So there exists some ordering, $\lt_w$ on $\mathbb{R}$ such that there IS a number after $1$. Note that this ordering has absolutely nothing to do with the normal ordering on $\mathbb{R}$. For example maybe $4>_w 2323$ and $\pi<_w-4$.

Using this ordering, we MAY induct on all of $\mathbb{R}$ because $(\mathbb{R},\lt_w)$ is well ordered. However there is a problem.

By using the axiom of choice (or insisting that this is an axiom), you are guaranteeing that this well ordering will never be explicitly given. So although there IS a well ordering of $\mathbb{R}$, we don't and CAN'T know what it is. Furthermore, this well ordering might not make any sense. So practically it is very difficult to induct on $(\mathbb{R},\lt_w)$.