Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm looking for good examples where double induction is necessary. What I mean by double induction is induction on $\omega^2$. These are intended as examples in an "Automatas and Formal Languages" course.

One standard example is the following: in order to cut an $n\times m$ chocolate bar into its constituents, we need $nm-1$ cuts. However, there is a much better proof without using induction.

Another example: the upper bound $\binom{a+b}{a}$ on Ramsey numbers. The problem with this example is that it can be recast as induction on $a+b$, while I want something which is inherently inducting on $\omega^2$.

Lukewarm example: Ackermann's function, which seems to be pulled out of the hat (unless we know about the primitive recursive hierarchy).

Better examples: the proof of other theorems in Ramsey theory (e.g. Van der Waerden or Hales-Jewett). While these can possibly be recast as induction on $\omega$, it's less obvious, and so intuitively we really think of these proofs as double induction.

Another example: cut elimination in the sequent calculus. In this case induction on $\omega^2$ might actually be necessary (although I'm not sure about that).

The problem with my positive examples is that they are all quite technical and complicated. So I'm looking for a simple, non-contrived example where induction on $\omega^2$ cannot be easily replaced with regular induction (or with an altogether simpler argument). Any suggestions?

share|improve this question
4  
Maybe I am misunderstanding you, but can't every proof of a statement by induction on two natural number parameters a, b be recast as a proof by induction on a+b? –  Qiaochu Yuan Jan 21 '11 at 19:05
2  
It can be that $a$ decreases but $b$ increases, for example. –  Yuval Filmus Jan 21 '11 at 19:13
1  
I'm not sure I understand what you mean by that. How would that affect a proof by strong induction on a+b? –  Qiaochu Yuan Jan 21 '11 at 19:32
2  
It could happen that $a$ decreases by 1 and $b$ increases by 2, so that in total $a+b$ increases. You can fix that whenever you have an upper bound on the increase of $b$ which depends only on $a$. –  Yuval Filmus Jan 21 '11 at 19:44
2  
Qiaochu, the Ackerman function provably cannot be organized as a recursion on $a+b$, since this would place the function within the class of primitive recursive functions (which are closed under that kind of recursion), but it is known not to be primitive recursive. –  JDH Jan 22 '11 at 1:00
show 3 more comments

10 Answers

up vote 10 down vote accepted

A nice example arises by relativizing Goodstein's Theorem from $\rm\ \epsilon_0 = \omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ down to $\rm\ \omega^2\:.\ $

$\rm\ \omega^2\ $ Goodstein's Theorem $\ $ Given naturals $\rm\ a,\:b,\:c\ $ and an arbitrary increasing "base-bumping" function $\rm\ g(n)\ $ on $\:\mathbb N\:$ the following iteration eventually reaches $0\ $ (i.e. $\rm\ a = c = 0\:$).

$\rm\quad\quad\quad\quad\ \ a\ b + c \ \ \to\quad\quad\ \ a\ \ \ \ \ g(b)\ +\ \ \ c\ \ -\ 1\quad if\quad\ c > 0 $

$\rm\quad\quad\quad\quad\ \ \phantom{a\ b + c}\ \ \to\ \ (a-1)\ g(b)\ +\ g(b)-1\quad if\quad \ c = 0 $

Note: $\ $ The above iteration is really on triples $\rm\ (a,b,c)\ $ but I chose the above notation in order to emphasize the relationship with radix notation and with Cantor Normal form for ordinals < $\epsilon_0$. $\ \ $ For more on Goodstein's Theorem see the link in Andres's post or see my 1995\12\11 sci.math post.

share|improve this answer
add comment

Let me begin with an example of an induction of length $\epsilon_0$: The proof that Goodstein sequences terminate. I mention this because when I decided to understand this result, I began to compute the length of these sequences and eventually came to a conjecture for a general formula (!) for the length of the sequence. It turned out that proving the conjecture was easy, because the proof organized itself as an induction of length $\epsilon_0$. I was both very amused and very intrigued by this. The little paper that came out of this adventure is here.

Now, I also found once a natural example of an induction of length $\omega^2$ when studying a "Ramsey type" problem: the size of min-homogeneous sets for regressive functions on pairs. What I liked about this example is that Ackermann's function injected itself into the picture and ended up providing me with the right rates of growth. The details are in a paper here.

share|improve this answer
    
Sigh, I didn't notice your similar answer get posted while I was composing mine since I compose my answers on Mathoverflow (to get the instant MathJaxification), so I don't see new post notifications while I'm editing. But it's quite refreshing to find here someone who thinks so similarly. Never did that occur in many years on sci.math! –  Bill Dubuque Jan 22 '11 at 0:49
    
@Bill: "it's quite refreshing to find here someone who thinks so similarly." Yes indeed. :-) –  Andres Caicedo Jan 22 '11 at 3:49
    
@Andres: That's actually a really nice "little paper"! –  Desiato Mar 22 '12 at 21:25
    
@Desiato: Thanks! –  Andres Caicedo Mar 22 '12 at 22:43
add comment

Though you've already dismissed it as 'lukewarm', Ackermann's function (proving totality I think is what is wanted) is your most accessible option (I think it is a great option).

It's not contrived/unnatural because it is motivated by very different concepts. If you want to construct another example (prove $f(x,y) = g(x,y)$), you'd probably want to have x and y very much asymmetric (in the sense that they should be used in syntactically very different ways in the computations). And Ackermann's function does just that.

share|improve this answer
add comment

One could concoct a simple example, like proving that every sequence of the following moves on pairs of natural numbers eventually terminates:

$(i,j)\mapsto (i-1,N)$ for any natural number $N$.

$(i,j)\mapsto (i,j-1)$

(Edited to make it an inherently $\omega^2$ problem.)

share|improve this answer
    
This is both artificial and provable by induction on $3i+j$. The same line of thought leads to Paris-Harrington, but I'm not sure we can really go that far... –  Yuval Filmus Jan 21 '11 at 20:11
    
How about (i,j) maps to (i-1,N) for any N. I realize it's artificial. –  Grumpy Parsnip Jan 21 '11 at 20:19
1  
There must be some combinatorial game theory example along these lines. Anyone? –  Yuval Filmus Jan 21 '11 at 22:35
    
Unfortunately, all the CGT examples I know for this sort of thing really just amount (as this example does) to the definition of $\omega^2$ in disguise... –  Steven Stadnicki May 18 '11 at 23:44
add comment

What about prove $m+n = n+m$ for $m,n \in \mathbb{N}$? In particular, see this (site talking about double induction).

share|improve this answer
3  
I find such proofs artificial - we all know that $m+n=n+m$. It's not a course on the axiomatic method, so restricting yourself to use only the Peano axioms doesn't seem justified. –  Yuval Filmus Jan 21 '11 at 19:47
add comment

Let [n] denote the ordered set (0, ..., n). Show that there are precisely $\binom{n+m+1}{n+1}$ order-preserving maps $[n] \rightarrow [m]$. Also note that the collection of objects [n], together with order-preserving functions, forms a category... one can show by double induction that every map has an epi-monic factorization. I haven't actually tried doing these without double induction... it just seemed more natural that way, so I don't really know whether this is a good example, or I was just being silly.

share|improve this answer
    
This is a pretty well-known combinatorial problem, with a neat combinatorial solution. Also, the double induction proof can probably be rephrased in terms of induction on $n+m$. –  Yuval Filmus Jan 22 '11 at 7:53
add comment

I suggest the following proof for Bezout's identity. It is a double induction, in a sense, since it proves a proposition for all pairs $a,b$ of natural numbers, by using "regular" induction on $\min(a,b)$. (I propose this as a general way to prove a statement on multiple natural variables: choose a function $f(n_1,\ldots,n_k)\mapsto N$ and then show that for all $n$, if $f(n_1,\ldots,n_k)= n$ then $n_1,\ldots,n_k$ satisfy the statement. This is then proved by induction on $n$).

Theorem: Let $a$ and $b$ be natural numbers and let $d = GCD(a,b)$ be their greatest common divisor. Then there exist integer $x$ and $y$ such that $d = ax +by$.

Proof: We use induction on $b=\min\{a, b\}$. Base case: If $b=1$ then $d=1$, and, for $x=0$, $y=1$ it is $1= ax + by$. Inductive step: Assume that for each pair $a,b$, with $a\ge b$ and $b\in \{1, 2,\ldots, n-1\}$ there are integers $x,y$ such that $GCD(a,b) = ax + by$. Consider a pair $a,b$ with $a\ge b$ and $b=n$, and let $q$ and $r$ be the quotient and remainder in the division of $a$ by $b$. If $r=0$ then $GCD(a,b)=b = ax +by$ for $x=0$ and $y=1$. Otherwise, being $d= GCD(a,b) = GCD(b,r)$, from the inductive hypothesis there are integers $x'$, $y'$ such that $d=bx' + ry'$. By replacing $r=a-qb$ we get $d=bx' +(a-qb)y' = ay' +b(x'-qy') = ax + by$ for $x=y'$ e $y=x'-qy'$. \QED

Giuseppe Lancia (giulan@gmail.com)

share|improve this answer
    
Induction on $\min(a,b)$ is the same as induction on $a+b$, it is just induction on $\omega$. Besides, your proof is really an analysis of the extended Euclidean algorithm, and is perhaps better presented as such. –  Yuval Filmus Nov 17 '12 at 22:26
add comment

For equations of parabolic or hyperbolic type in two independent variables the integration process is essentially a double induction. To find the values of the dependent variables at time t + Δt one integrates with respect to x from one boundary to the other by utilizing the data at time t as if they were coefficients which contribute to defining the problem of this integration.

share|improve this answer
add comment

This has some information

share|improve this answer
1  
It only gives the infamous "chocolate bar" example. Another such guide had a proof that went like that: "prove A by induction; prove B by induction, using A"; that was used as an example for double induction! –  Yuval Filmus Jan 21 '11 at 19:15
add comment

There is a double induction in the recent paper David G Glynn, "A condition for arcs and MDS codes", Des. Codes Cryptogr. (2011) 58:215-218. See Lemma 2.4. It is about an identity involving subdeterminants of a general matrix and appears to need a double induction.

share|improve this answer
    
I was looking for something elementary - these students probably don't know what a subdeterminant is. –  Yuval Filmus Apr 3 '11 at 3:03
add comment

Your Answer

 
discard

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.