MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Next week I am going to teach two lessons on induction to very motivated students from high schools. At some point I would like to talk about ordered sets, well-ordered sets, and mention the fact that induction works on well-ordered sets. More precisely, I will prove the following formulation of induction: let $S$ be a well-ordered set with minimal element $0$, and let $P$ be a property such that $P(0)$ is true and if $P(x)$ is true for every $x < y$, then $P(y)$ is true. Then $P(x)$ is true for every $x\in S$.

I would like to provide a (sufficiently elementary) application of this principle in a case when $S$ is not (isomorphic to) the set of natural numbers. For example, one could try to find an example for $S=\mathbb{N}\times \mathbb{N}$, endowed with the lexicographical order. I am looking for examples such that:

  • the problem is sufficiently "natural" and elementary (the audience is from high school!)

  • possibly, it should not reduce to an induction "in one variable" (for example, the induction on $(m,n)\in\mathbb{N} \times\mathbb{N}$ should not reduce to an induction on $n+m\in\mathbb{N}$)

Of course any induction on $\mathbb{N}\times\mathbb{N}$ may be reduced to a double induction on $\mathbb{N}$, but in order to avoid this I should look for too complicated well-ordered sets, so this does not bother me too much... Anyway, if anyone knows some reasonably simple examples with more complicated well-ordered sets, then this would be very good for me!

share|cite|improve this question
A comment, since I don't think this is a good answer: if you had more time available, I think a proof of clopen determinacy by induction would be a great example. The poset being used is the set of all well-founded trees (on some base set, probably $\mathbb{N}$), ordered by "is the tree below some vertex of" (so stronger than "is a subtree of"; in particular, this is a wellfounded poset, and proving that is straightforward: a descending sequence yields a path through a "well-founded" tree). This is a very large poset, and I think the result is really interesting, after some explanation. – Noah Schweber Jan 21 '13 at 17:40
Perhaps a more interesting "exotic" phenomenon is proving a result by induction with a stronger inductive hypothesis to make the induction go through (despite a weaker result being what one wants to prove). Saying enough about well-ordered sets to make the notion seem natural and useful could take away a lot of time from talking about the diverse ways in which induction arguments are actually carried out in practice (beyond the mechanical examples done in high schools). For example, the symmetric function theorem can be proved by a nice "double induction" (goes beyond # of variables!). – user28172 Jan 21 '13 at 17:43
"Proofs from the Book" gives the nice ($P(1)$ and ($P(n)$ implies $P(2n)$) and ($P(n)$ implies $P(n−1)$)) implies $\forall n, P(n)$ as a way to prove the general inequality between geometric and arithmetic mean (due to Artin, or perhaps Cauchy) – Feldmann Denis 0 secs ago – Feldmann Denis Jan 21 '13 at 18:11
How about the lack of need for parentheses in the presence of associativity a(b((cd)e)) – Anthony Quas Jan 21 '13 at 18:13
This may not be good for high school students, but their is real induction. – Lunasaurus Rex Jan 22 '13 at 0:52
up vote 7 down vote accepted

Goodstein's Theorem

is proved using an induction of length $\epsilon_0$.

share|cite|improve this answer

The Ackermann function is well-defined.

This is easily proved by lexicographic induction on $\mathbb N\times \mathbb N$. But perhaps not easily formulated -- I can only think of this awkward formulation: For every $x,y$ there is a unique function on the initial segment determined by $(x,y)$ satisfying the Ackermann recursion.

share|cite|improve this answer
For every $(x,y)$, by symbolically applying the recursive definition of the Ackermann function enough times, one eventually reaches an integer. – Will Sawin Jan 21 '13 at 21:19

The following example is not completely elementary, in that it requires the notion of sum of a family of non-negative real numbers (defined as supremum of the finite sub-sums), and some topology of the real line. But it allows a nice picture, and leads to a visualization of ordinal numbers as subsets of $\mathbb{R}$, so that it could be understood and appreciated by well-motivated high-school students, if you take the time to explain the problem, possibly skipping the technicality, and solving particular cases first. Moreover, it is close to the birth-place of the ordinal numbers.

The additivity of the length on the family of all left-closed, right-open intervals of the real line.

Let $P$ be the family of all left-closed, right-open intervals of the real line. Suppose $I=:[a,b)\in P$ is partitioned into a family elements $J_x:=[x,x')$ of $P$, that we may indicize by the left end-point $x\in S$, that is, $I=\cup_{x\in S} J_x $. Then,
$$|I|=\sum_{x\in S} |J_x|\, .$$

Proof: You may first consider and solve the case of finitely many intervals, and the case of a sequence of intervals accumulating at $b$, that gives rise to a telescopic sum. For the general case, the key point is that $S$ is well-ordered by the natural order of $\mathbb{R}$. This allows to prove
$$\Big|\bigcup_{x\in S\atop x \le u} J_x \Big|= \sum_{x\in S\atop x \le u} |J_x| \, .$$ by transfinite induction on $u\in S$.

share|cite|improve this answer
This is a very nice example. – Emil Jeřábek Sep 5 '13 at 12:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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