1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – palmpo Feb 14 '18 at 18:09
  • $\begingroup$ 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? $\endgroup$ – palmpo Feb 14 '18 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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