# Induction on cartesian products of well-ordered sets (varying cardinality)

There is a proof by contradiction of induction on $\mathbb{N}$ by the Well-Ordering Principle (WOP). It seems like we can copy the proof to show induction on $\mathbb{N}^n$ for some $n\in\mathbb{N}$:

For some $n\in\mathbb{N}$, let $\mathbb{N}^n$ be the cartesian product of $n$ sets of $\mathbb{N}$.
For every $\alpha\in\mathbb{N}^n$, let $P(\alpha)$ be a statement. If
(1) $P((1,1,\dotsc,1))$ is true and
(2) For every $k=(\dotsc,a_i,\dotsc)\in\mathbb{N}^n$, for every $1\le i\le n$, $P((\dotsc,a_i,\dotsc))\implies P((\dotsc,a_i+1,\dotsc))$ is true,
then for every $\alpha\in\mathbb{N}^n$, $P(\alpha)$ is true.

Proof: Assume, to the contrary, that (1) and (2) are true but there is some $\alpha\in\mathbb{N}^n$ such that $P(\alpha)$ is false. Let $$S=\{\alpha\in\mathbb{N}^n:P(\alpha)\ \text{is false}\}.$$ Since $S$ is a nonempty subset of $\mathbb{N}^n$, $S$ contains a least element $s$. (Define a relation $\le$ on $\mathbb{N}^n$ such that $\alpha\le\beta$ iff $a_i\le b_i$ for every $1\le i\le n$, then by the WOP, there is a least element $s_i$ for each of the $n$ coordinates). Since $P((1,1,\dotsc,1))$ is true, $(1,1,\dotsc,1)\notin S$. Thus for some index $1\le i\le n$, $s=(\dotsc,a_i,\dotsc)$ where $a_i\ge2$ and $(\dotsc,a_i-1,\dotsc)\in\mathbb{N}^n$. Therefore, $(\dotsc,a_i-1,\dotsc)\notin S$ so $P((\dotsc,a_i-1,\dotsc))$ is true. By (2), $P(s)$ is also true so $s\notin S$, contradiction.

I am wondering if this can be extended to induction on a cartesian product of a finite number of well-ordered sets (not necessarily $\mathbb{N}$, or sets like $S=\{i\in\mathbb{Z}:i\ge m\}$ for every integer $m$, that can be shown to be well-ordered by the WOP). What would the $a_i+1$ in (2) be, or $a_i-1$ in the proof be?

Furthermore, what about induction on a cartesian product of a countably infinite or uncountable number of well-ordered sets? Or even furthermore, for $\times_{\alpha\in I}A_i$ for some index set $I$, where the $A_i$'s are well-ordered sets of varying cardinality?

• $S$ need not have a least element. But fortunately all you need here is a minimal element. – Hurkyl Feb 14 '18 at 9:29

Your proof is correct except for an important detail: $\mathbb{N}^n$ with the product order is not well-ordered, so you cannot talk about the least element of $S = \{\alpha \in \mathbb{N}^n \mid P(\alpha) \text{ is false}\}$ because it might not exist. For a counterexample, consider $\mathbb{N}^2$: $(0,1)$ and $(1,0)$ are incomparable.

Luckily, you can easily circumvent the problem: take $\mathbb{N}^n$ with the lexicographical order, defined by \begin{align} (a_1, \dots, a_n) \leq (b_1, \dots, b_n) \iff \begin{cases} \exists \, 1 \leq k \leq n : a_i = b_i \ \forall \, 1 \leq i < k \text{ and } a_k < b_k, \text{ or} \\ a_i = b_i \ \forall \, 1 \leq i \leq k \end{cases} \end{align}

$\mathbb{N}^n$ with the lexicographical order is well-ordered, so you can apply your proof exactly as you wrote it even in this case.

More in general, if you have an $n$-ary relation $P$ over a well-ordered set $A$, your proof (together with my emendation) proves that the induction principle holds on $A^n$, because $A^n$ is well-ordered by the lexicographical order.

Unfortunately, well-ordering is not preserved by the lexicographical order in the (countably) infinite: the fact that $A$ is a well-ordered set does not imply that $\prod_{n\in\mathbb{N}} A = \bigcup_{n\in\mathbb{N}} A^n$ is well-ordered, so you cannot talk about the least element of $S$ because it might do not exsist. For a counterexample, consider $\prod_{n\in\mathbb{N}} \mathbb{N} = \bigcup_{n\in\mathbb{N}} \mathbb{N}^n$ and check that (you can identify a finite sequence $(a_1, \dots, a_n)$ with the infinite sequence $(a_1, \dots, a_n, 0, 0 , \dots)$ ) \begin{align} (1) > (0,1) > (0,0,1) > (0,0,0,1) > \dots \end{align}

Anyway, even in this case you can slightly modify the definition of lexicographical order and show that it is a well order on $\prod_{n\in\mathbb{N}} A$ whenever $A$ is well-ordered.

Therefore, the answer to the question in the OP (proving the induction principle for a cartesian product of well-ordered sets) is positive whenever you take countably (finite or infinite) many well-ordered sets in your cartesian product. This holds also in the case you take uncountably many well-ordered sets in your cartesian product, but you need the Axiom of Choice (a non-constructive axiom of mathematics) to prove it.

Note that the cardinality of $A$ does not play any role in the discussion above.

• Thanks for the informative response! With your emendation, what would the $a_1+1$ and $a_1-1$ be in the proof of induction on $A^n$ well-ordered? I'm not sure since I don't know anything of the elements of arbitrary $A_i$. – palmpo Feb 14 '18 at 18:09
• In addition: From what I get from your answer, it seems like lexicographical order is a sort of "standard" well-ordering on cartesian products. But there are other relations that imply well-ordering right? Also, does lexicographic ordering require choice in any form for countable sets? – palmpo Feb 14 '18 at 18:10