How does it work? In the nested case.

Question

I cannot understand how double/nested induction works. I am supposed to prove that the addition operation is both commutative (x + y = y + x) and associative (x+(y+z)) = ((x+y)+z) from the following definitions of the naturals and addition (no other axiom is given).

Naturals: Base: $0 \in \mathbb{N}$ and Ind. $n \in \mathbb{N} \implies sn \in \mathbb{N}$.

Addition: Base: $0 + n = n$ and Ind. $s(m)+n = s(m+n)$.

I do understand that I am supposed to divide the proof into a base case and an inductive case, but I am very unsure about the way to proceed since there's $m$ and $n$ to care about:

Proof statement: $\forall m,n \in \mathbb{N}: n+m = m+n$.

Base case:

Assume $n=0$. This gives us $0 + m = m + 0$. By the definition of addition, this means $0 + m = m$.

But now I am stumped, obviously I should do some sort of induction on $m$, but otherwise I am stumped, since there is nothing I can say about $0 + m$ (as it is not on the definition of +. Any ideas on how to structure the proof for both the commutative and associative properties? I have seen a few explanations online, but they sometimes use other lemmas or are otherwise so quick and straightforward that I feel like I miss something. Thank you.

Answer 1

Step 1: To prove $m+0=m$ you have to start with a base case:

$$0+0=0$$

To show that $1+0=1$ you have

$$1+0=S(0)+0=S(0+0)=S(0)=1$$

Likewise, for $2$ you have

$$2+0=S(1)+0=S(1+0)=S(1)=2$$

In general, assume you have proved $k+0=k$, then you only need to show that $S(k)+0=S(k)$. But this is simple as

$$S(k)+0=S(k+0)=S(k)$$

as desired.

Step 2: Great, we've now shown that $m+0=m=0+m$ for all $m$. To show the same for $+n$ we will start with the example $n=1$.

$$1+m=S(0)+m=S(0+m)=S(m)$$

We then also need to show that $m+1=S(m)$. AGAIN this takes an induction proof! Base case

$$0+1=1=S(0)$$

Assume that $k+1=S(k)$. Then

$$S(k)+1=S(k+1)=S(S(k))$$

as desired. For general (and specific) $n$, assume that we have shown that

$$m+n=n+m$$

for all $m$. We have to show that

$$m+S(n)=S(n)+m$$

We will do this by proving the following equalities true

$$m+S(n)=S(m+n)=S(n+m)=S(n)+m$$

Some of these equal signs are easy to see

$$S(n)+m=S(n+m)\text{ by definition}$$

$$S(m+n)=S(n+m)\text{ by inductive assumption}$$

The difficult thing to prove is that $m+S(n)=S(m+n)$. AGAIN, we will use induction! Base case:

$$0+S(n)=S(n)+0=S(n+0)=S(0+n)$$

Assume $k+S(n)=S(k+n)$. Then

$$S(k)+S(n)=S(k+S(n))=S(S(k+n))$$

as desired.

Answer 2

In general, you prove things by induction on well-ordered sets. Recall that a well-ordered set is a totally ordered set $(N,\leqslant)$ such that every non-empty subset has a minimum. If $N$ is a well-ordered set and $A\subset N$ is such that $a\in A$ whenever $\{b\in A:b<a\}\subset A$, then $A=N$. If it were not so, then $N\setminus A$ would have a minimum, say $a$, but then this contradicts the hypothesis, since $\{b\in A: b<a\}\subset A$.

If $N$ is a well-ordered set and for each $a\in N$, $P(a)$ is a proposition, then you can define $A$ to be the set of $a\in N$ such that $P(a)$ is true. Proving $P$ by induction is showing that $A$, defined in this way, has the property above.

I state it in this level of generality, because one can prove things by induction on ordinals, not just $\mathbb{N}$.

Nested induction as you've described it in the problem can be proving the statement by induction on $N=\mathbb{N}\times \mathbb{N}$, which is well-ordered lexicographically. So $(m,n)\leqslant (m',n')$ iff $m<m'$ or $m=m'$ and $n<n'$. OR, of course, you could use antilexicographic ordering, which would likely make a difference, since you can't yet use the fact that addition is commutative.

As a matter of practice, not logical necessity, when you're proving that $A$ has the condition stated above, you consider the cases $a=\min N$ and $a\neq \min N$ separately. Sometimes you handle several values of $a$ as isolated cases. These are the base cases vs. inductive steps. But it may be the case that you don't really have a "base case" vs "inductive step," but rather you have some $a$ which, by the nature of $A$, have to be dealt with differently than other $a$. Quite often, when proving things on ordinals, there's a base case of $0$, a limit ordinal case, and a successor case. Since $\mathbb{N}$ does not contain any limit ordinals (in fact, it is the smallest limit ordinal), the third case doesn't come up in induction on $\mathbb{N}$.

In your case, I think pairs of the form $(m,0)$ will be dealt with separately than $(m,n+1)$. The cases $(m,0)$ can be thought of as base cases, but it might be confusing, since they're interspersed throughout, rather than all at the beginning. You can also think about this as nested induction with an outer hypothesis, and within each outer hypothesis, you have an inner hypothesis. The outer hypothesis would be something like $P(m):$ For all $n$, $s(m+n)=s(m)+n$. The inner would be different for each $m$. $P_m(n)$ would be that $s(m+n)=s(m)+n$(this is for a fixed $n$, not all $n$). Then the $(m,0)$ case is the base case of the inner induction on $P_m$. But for each $m$, you have such a base case to prove $P(m)$. So you prove the result by induction on $n$ with $m$ held fixed. Then you prove $P_{m+1}$ using that $P_k$ holds for all $k\leqslant m$, which is the outer induction. Of course, you could switch which is the outer vs. inner. Have $n$ on the outside and $m$ on the inside. Since your goal is to prove commutivity of addition, you aren't using commutivity of addition, so whether you treat $m$ or $n$ as the variable of the inner vs. outer hypothesis will likely make a difference. So it could make things hard if you pick the wrong order. As someone who frequently does double induction proofs on ordinals (where addition and multiplication are not commutative, order definitely matters).

It's worth mentioning that induction on $\mathbb{N}\times \mathbb{N}$ ordered lexicographically is essentially the same as induction on $\omega^2$. You could have the statement $P(\omega m+n):$ $s(m+n)=s(m)+n$. Prove this by induction on $\omega^2$. Then the $(m,0)$ cases are either the $0$ case if $m=0$ or the limit ordinal cases when $m>0$.

Answer 3

For the commutative property you do indeed need nested induction: see QC_QAOA’s answer how to do that.

As such, you might fear that to show the associative property that $x+(y+z) = (x +y)+z)$ you need triple-nested induction, but fortunately that is not the case. You only need to do induction once:

Simply pick $y$ and $z$ to be arbitrary, and do induction on x:

Base: Show that $0+(y+z) = (0+y) +z$

… which is trivial, since $0+(y+z) =y+z$, and $(0+y)+z =y+z$

Step: Assume (IH) that $x+(y+z)=(x+y)+z$ and show that $s(x) + (y+z) = (s(x) +y) +z$

… Which is also not hard: $s(x)+(y+z) = s(x+(y+z))= \text{(by IH)} s((x+y) +z)= s(x+y)+z = (s(x)+y)+z$