7
$\begingroup$

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!

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ 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. $\endgroup$
    – Noah Schweber
    Jan 21, 2013 at 17:40
  • 2
    $\begingroup$ 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!). $\endgroup$
    – user28172
    Jan 21, 2013 at 17:43
  • 8
    $\begingroup$ "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 $\endgroup$
    – Feldmann Denis
    Jan 21, 2013 at 18:11
  • 1
    $\begingroup$ How about the lack of need for parentheses in the presence of associativity a(b((cd)e)) $\endgroup$
    – Anthony Quas
    Jan 21, 2013 at 18:13
  • 2
    $\begingroup$ Incidentally, if you're doing induction on a well-ordered set, you don't need to check the first condition (that $P(0)$ holds) if the second condition holds. $\endgroup$
    – S. Carnahan ♦
    Jan 22, 2013 at 14:00

4 Answers 4

Reset to default
8
$\begingroup$

Goodstein's Theorem

http://en.wikipedia.org/wiki/Goodstein%27s_theorem

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

Improve this answer
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ This is a very nice example. $\endgroup$
    – Emil Jeřábek
    Sep 5, 2013 at 12:59
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ For every $(x,y)$, by symbolically applying the recursive definition of the Ackermann function enough times, one eventually reaches an integer. $\endgroup$
    – Will Sawin
    Jan 21, 2013 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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