Real Induction Over Multiple Variables?

Question

I've seen in several different places* that one can use normal mathematical induction to prove the truth of a statement that relies not on just one variable (say, $x$,) but multiple variables (for example, $a$, $b$, and $c$.) Can one use real induction (described in this paper) in a similar manner?

---

*Some Examples:

• Mathematics Stack Exchange — i. e.: here on this site:
  • How does one determine which variables to do induction on?
  • Induction for statements with more than one variable.
• Other Site:
  • Proof method: Multidimensional induction (from MathBlog)

Answer 1

$\newcommand{\R}{\mathbb{R}}$ This is an excellent question. In fact I do not know of a multivariable version of real induction which is truly satisfactory, by which I mean that it gives a proof technique which is not obviously inferior to the standard ones.

Let's concentrate on $[0,1]^n$ to fix ideas. A useful version of real induction should allow us to prove that $[0,1]^n$ is compact and/or that it is connected. Note that already there is a bit of a limitation here, which is that if we know enough basic topology we don't need any new proof technique: we can show that (finite is easier, and is enough) products of quasi-compact (resp. connected) spaces are quasi-compact (resp. connected). Whatever we come up with has to be measured against that.

About a year ago I wrote a little note giving "an inductive proof" of the full Heine-Borel Theorem: compactness of $[0,1]^n$. (You could state it in other ways, but this carries the full content.) Here is an excerpt from the introduction to the note (which is not available anywhere; you'll see why shortly):

It is the purpose of this note to give an "inductive proof" of the Heine-Borel Theorem. When $n =1$ we did so earlier by a method we called real induction: we repeat that argument here in self-contained terms. In brief this method takes advantage of the order-completeness of $[a,b]$ by pushing the truth of a proposition from left to right. (Many earlier authors have introduced similar methods.) A limitation of real induction is that it does not apply directly in $\R^n$ for $n > 1$, in which the order structure is absent. In this case, if one wants to carry over the "expanding example" style of proof from $\R$ to $\R^n$ one needs to establish an auxiliary fact, the Ring Lemma. To establish the Ring Lemma in $\R^n$ for $n \geq 2$ we need to use the compactness of the boundary of an $n$-cube. Thus we finish the proof by using "discrete" mathematical induction!

I suppose it will also help to see:

Ring Lemma Let $n \geq 2$. Suppose that Heine-Borel holds in $\R^{n-1}$, let $[a,b]^n \subset \R^n$ be a cube, and let $U$ be a bounded open neighborhood of $\partial [a,b]^n$ in $\R^n$. Then there is $\epsilon > 0$ such that $[a,b+\epsilon]^n \setminus [a,b-\epsilon]^n \subset U$.

What's going on here? The most evident idea here is to do a "real induction on the length of a subcube". In other words, we start with the compactness of a subcube $[0,x]^n$ and try to establish the compactness of a slightly larger subcube $[0,x+\delta]^n$. This works like a dream when $n = 1$, but when $n \geq 2$ we run into the problem that one cube minus an even slightly smaller one does not have diameter approaching zero, so you can't just take one more element of the covering. You really have to do something, which is what the "Ring Lemma" is there for.

I was happy with this for a day or two. I especially liked the fact that it mixed "discrete mathematical induction" with "continuous mathematical induction", and I was even thinking of writing it up for publication. Then I showed it to a colleague of mine, who is a topologist. He immediately said, "Sure, you're proving the Tube Lemma." And I said "No, it's different because blah blah blah," at which point he very generously gave me some weird statement about foliations to think about, and I walked out of his office thinking momentarily about that. A few hours later I realized he was right: I had spent a full page writing out an argument which amounts to proving a very special case of the Tube Lemma in a way which is distinctly more complicated than the (really very simple) proof of the general case. So this is not a good way to prove the Heine-Borel Theorem.

If one is willing to drop the emphasis on the order structure -- which, since it seems not to be absolutely clear, let me make sure to say is what I consider to be the characteristic feature of real induction -- then there are other things to do. Oleg Viro has recently published a very attractive student problem book in (basic, undergraduate level) general topology, and he has two exercises in there called induction on compactness and induction on connectedness. If you do not mind the fact that these have nothing to do with order structures, definitely check these out as a plausible answer to your question.

Answer 2

The simplest to state and prove version of "real induction" on $\mathbb{R}^n$ is the following: suppose $A\subseteq\mathbb{R}^n$ is a nonempty closed subset such that if $p\in A$, then some ball around $p$ is contained in $A$. Then $A$ is all of $\mathbb{R}^n$. (Proof: The hypotheses just say $A$ is a nonempty clopen subset of $\mathbb{R}^n$, and $\mathbb{R}^n$ is connected).

The version of "real induction" in Pete Clark's paper is slightly different from this because it uses weaker versions of the "open" and "closed" hypotheses and it only ends up asserting that if $0\in A$ then $[0,\infty)\subseteq A$. This version also generalizes to $\mathbb{R}^n$, as follows. Suppose $A\subseteq [0,\infty)^n$ contains the origin and satisfies:

1. If $x=(x_1,\dots,x_n)\in A$, there is an $\epsilon>0$ such that $[x_1,x_1+\epsilon)\times\dots\times[x_n,x_n+\epsilon)\subseteq A$
2. If $x=(x_1,\dots,x_n)\in [0,\infty)^n$ and for some $i$, $\{x_1\}\times\dots\times\{x_{i-1}\}\times[0,x_i)\times\{x_{i+1}\}\times\dots\times\{x_n\}\subseteq A$, then $x\in A$.

Then $A$ is all of $[0,\infty)^n$. (Proof: By induction on $n$, $A$ must contain all of $\{0\}\times[0,\infty)^{n-1}$. For any $y\in [0,\infty)^{n-1}$, the $n=1$ case now implies $A$ contains all of $[0,\infty)\times\{y\}$.)