Examples of induction in sets not of order type $\omega$

Question

When introducing proof by induction there's a huge standard library of simple examples for students to practise the technique on. What are some simple but interesting beginner's examples of induction not over the natural numbers, but some other order type? I'm particularly interested in lex order on $\mathbb{N}\times\mathbb{N}$, but any order will do.

Answer 1

There’s a simple but boring example of double induction over $\Bbb Z^+\times\Bbb Z^+$ in Section $3$ of this PDF that at least serves to demonstrate the mechanics. Most of the examples that come to mind that don’t reduce easily to inductions over the order type $\omega$ are complicated or are interesting (or sometimes even comprehensible) only if one has the right background, if not both. Here’s one possible exception.

Consider the following solitaire game. You have a bag containing $r$ red and $b$ blue balls. At each turn you take out one marble. If the marble is red, you throw it away. If the marble is blue, you throw it away and add as many red marbles to the bag as you like. Show that no matter how you play, you will eventually empty the bag.

The proof is by induction on $\langle b,r\rangle$ ordered lexicographically. In terms of ordinals, the order type is $\omega^2$.

Clearly this can be extended to any finite number of colors; with $n$ colors you get an order of type $\omega^n$. You can even extend it to infinitely many colors, getting an order of type $\omega^\omega$:

You have a bag containing a finite set of numbered balls. The numbers on the balls are positive integers, and there may be any number of balls with the same number. For instance, the bag might contain three balls numbered $1$, seven numbered $3$, and a dozen numbered $11$. You play the following game. At each turn you remove one ball from the bag. If the number on the ball is $1$, you simply throw the ball away. If the number on the ball is some $n>1$, you replace the ball with as many balls numbered $n-1$ as you like. Show that no matter what balls were in the bag initially and no matter how you play, you will eventually empty the bag.

Here the possible contents of the bag can be represented by sequences $\langle n_k:k\in\Bbb Z^+\rangle$ of non-negative integers with only finitely many non-zero terms: $n_k$ is the number of balls in the bag with the number $k$. The order $\prec$ is reverse lexicographic order: if $\langle m_k:k\in\Bbb Z^+\rangle$ and $\langle n_k:k\in\Bbb Z^+\rangle$ are distinct, and $d=\max\{k\in\Bbb Z^+:m_k\ne n_k\}$, $\langle m_k:k\in\Bbb Z^+\rangle\prec\langle n_k:k\in\Bbb Z^+\rangle$ iff $m_d<n_d$.