7
$\begingroup$

     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:

Question-Derived Reference Material:


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

$\endgroup$
  • $\begingroup$ Hmm…seems the tags I entered for the question were scrambled. I tried to fix it, but alas, it didn't work! Oh, well; guess it's OK as long as all of the tags are still there, I suppose, right? $\endgroup$ – RandomDSdevel May 28 '15 at 20:09
  • $\begingroup$ Um…don't leave me hanging? I need an answer relatively quickly here since I only have a limited amount of time (it started out as about one year in the early middle of May) to finish my independent-study calculus course. $\endgroup$ – RandomDSdevel May 29 '15 at 22:43
  • 3
    $\begingroup$ There is something called transfinite induction, I am writing something about it right now. $\endgroup$ – user223391 Jun 5 '15 at 0:03
  • 2
    $\begingroup$ Also, there's a nice connection between the Real Induction presented there and transfinite induction — a connection that I don't think has been mentioned so far. I'd put it as my own answer but it's getting late where I am. $\endgroup$ – Akiva Weinberger Jun 5 '15 at 2:35
  • 2
    $\begingroup$ Most of the paper deals with analysis, a sort of generalization of calculus… If you haven't learned about that yet, that would explain why you're having trouble. As for the intro, maybe the notation is tripping you up? (And as for the discussion about Dedekind complete ordered sets after the intro — it won't make sense unless you already know about Dedekind complete ordered sets, but it can be skipped.) $\endgroup$ – Akiva Weinberger Jun 5 '15 at 20:32
9
$\begingroup$

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]$.

$\endgroup$
  • $\begingroup$ Thank you, thank you, thank you! This is exactly what I was looking for! $\endgroup$ – RandomDSdevel Jun 5 '15 at 19:54
  • $\begingroup$ Or was it? Your answer doesn't mention how to prove that a statement is true for all real numbers, but instead only seems to show me how to prove that a statement is true for any closed interval in $\mathbb{R}$. Can you update your post with a little something on that? I'd also like to know how to write down a summary of the methods behind real induction in some form of mathematical logic (like the axiom of mathematical induction does for that method.) Then again, maybe I should ask these questions separately as follow-up inquiries? $\endgroup$ – RandomDSdevel Jun 9 '15 at 18:58
  • 1
    $\begingroup$ @RandomDSdevel In some sense, induction on closed intervals is the "hard part" of induction on $\mathbb{R}$. The main result of the more general section of Clark's paper, which might be difficult to parse unless you've seen some analysis and/or topology, implies that there is an analogous principle for all of $\mathbb{R}$. However, it's likely not as useful in practice (consider why ordinary induction is done over $\mathbb{N}$ rather than $\mathbb{Z}$). A somewhat more useful version would involve the half-line $[0,\infty)$, and can probably be proven fairly easily from this one. $\endgroup$ – Ross Jennings Jun 9 '15 at 23:49
  • 2
    $\begingroup$ Something is wrong with your second condition. It should say "Given any $x \in S$, there is some $y \in (x,b]$ such that $[x,y] \subseteq S$. Also, this "induction" principle is cute but in my opinion unnecessary since the more fundamental is simply the existence of supremum of a bounded set of reals, which can be used to directly find the desired points. For example to prove the extreme value theorem directly you take $c = \sup\{ x : x \in [a,b] \land \forall y \in [a,x]\ ( f(x) \ge f(y) ) \}$. If $f(c) < f(y)$ for some $y \in (c,b]$, take $\inf\{ x : x \in (c,b] \land f(x) \le f(y) \}$. $\endgroup$ – user21820 Jul 25 '15 at 15:04
  • 1
    $\begingroup$ @RandomDSdevel: To make it clear, this "induction" principle is simply one consequence of the existence of supremum of a bounded set of reals, and has nothing to do with the axiom of choice or well-orderings. It is provable over any base system that proves the existence of the standard reals. $\endgroup$ – user21820 Jul 26 '15 at 11:10
4
$\begingroup$

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)$.

$\endgroup$
  • 2
    $\begingroup$ Contrast real induction with nonstandard analysis — in nonstandard analysis (specifically, IST) you can create a finite set containing all standard reals and induct over that. (IST is weird.) $\endgroup$ – Akiva Weinberger Jul 23 '15 at 19:43
2
$\begingroup$

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)$.

$\endgroup$
  • 2
    $\begingroup$ "Why can't a well ordering be explicitly given for $\mathbb{R}$?" is a very deep and important question. :) I don't know if there is a way of proving it or explaining it too much. Here is a relevant post: math.stackexchange.com/questions/150992/… $\endgroup$ – user223391 Jun 5 '15 at 0:44
  • 3
    $\begingroup$ I take it you haven't looked at Clark's sources, given by the OP? (He claims "The Instructor's Guide" is more polished, if I recall correctly.) $\endgroup$ – Akiva Weinberger Jun 5 '15 at 2:31
  • 1
    $\begingroup$ @RandomDSdevel: Note that this thing called well-ordering of a set (using the axiom of choice) has nothing to do with the other thing that Pete calls real induction (which does not use the axiom of choice). $\endgroup$ – user21820 Jul 25 '15 at 14:52
  • 1
    $\begingroup$ @RandomDSdevel: No it has nothing to do with total ordering. See my comment on the other answer; basically it's simply the existence of the supremum of an upper bounded set. Also, it is meaningless to say well ordered or not well ordered without specifying an ordering. $\endgroup$ – user21820 Jul 26 '15 at 10:56
  • 1
    $\begingroup$ @RandomDSdevel: By the way, MathWorld articles are simply terrible teachers. Any finite total order (a set together with an ordering) is also a well-order because its ordering is a well-ordering on its set. If you just have a set, it has no order whatsoever. Also, there are in general many possible orderings that you can find on the same set (especially using the axiom of choice). $\endgroup$ – user21820 Jul 26 '15 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.