Double induction

Question

Hi I'm studying Introduction to Set Theory by Hrbacek and Jech and I am not sure if I am doing a certain problem correctly. Problem 2.13 in Chapter 3 is:

(Double Induction) Let $P(x,y)$ be a property. Assume that if $P(k,l)$ holds for all $k,l \in \mathbb{N}$ such that $k < m$ or ($k=m$ and $l<n$), then $P(m,n)$ holds. Conclude that $P(m,n)$ holds for all $m,n \in \mathbb{N}$.

Now, my interpretation of this is that $$ (*) \,\,\,\,\forall k,l \in \mathbb{N} [k < m \vee (k=m \wedge l<n) \to P(k,l)] \to P(m,n) $$ is true, which I'm not entirely convinced is correct. Also it seems to me that to prove something using strong induction, one must show that $$ \forall k \in \mathbb{N}[k < n \to P(k)] \to P(n) \,. $$ So my proof of the double induction problem is as follows:

Consider an arbitrary $n \in\ \mathbb{N}$. Then by (*) above $$ \forall k,l \in \mathbb{N} [k < m \to P(k,l)] \to P(m,n) \,. $$ So by strong induction $$ \forall m \in \mathbb{N}[P(m,n)] $$ and since $n$ is arbitrary $$ \forall m,n \in \mathbb{N}[P(m,n)] $$ as desired.

Is this proof valid? The fact that the problem is titled "Double Induction" leads me to believe that I have made a mistake somewhere since I only had too use induction once. Any guidance here is appreciated.

Answer 1

The formula $\forall m\in\Bbb N[P(m,n)]$ isn’t a sentence: it has a free variable $n$. In less technical language, it doesn’t actually assert anything, so you can’t prove it.

You want to split the induction into two, one ‘inside’ the other. The outer induction is on $m$:

Show that if $P(k,\ell)$ holds for all $k<m$ and all $\ell\in\Bbb N$, then $P(m,\ell)$ holds for all $\ell\in\Bbb N$.

Carrying out the induction step has two parts. First you have to justify the assertion that $P(m,0)$ holds. Then you have to do an induction on $\ell$ to show that $P(m,\ell)$ holds for each $\ell\in\Bbb N$.

There is, by the way, a rather different way to look at it that might be easier. Define a relation $\preceq$ on $\Bbb N\times\Bbb N$ by $\langle k,\ell\rangle\preceq\langle m,n\rangle$ iff either $k<m$, or $k=m$ and $\ell\le n$. Show that $\preceq$ well-orders $\Bbb N\times\Bbb N$. Suppose that $B=\{\langle m,n\rangle\in\Bbb N\times\Bbb N:\neg P(m,n)\}\ne\varnothing$; then $B$ has a $\preceq$-least element $\langle m,n\rangle$, from which you can derive a contradiction.

Answer 2

First let's rewrite the problem statement more clearly:

Let $P(x,y)$ be a property, and let $A(m,n)$ denote the following statement:

---

If $P(k,l)$ holds for all $k,l∈\mathbb N$ such that either

1. $k<m$
2. $k=m$ and $l<n$

then $P(m,n)$ holds.

---

Then the problem is to prove the following:

Proposition. Assume that $A(m,n)$ holds for all $m,n∈\mathbb N$. Then $P(m,n)$ holds for all $m,n∈\mathbb N$.

Proof. Let $Q(m,n)$ denote the property that $P(k,l)$ holds for all $k,l$ satisfying $1$ or $2$ above. We will show that $Q(m,n)$ holds for all $m,n∈\mathbb N$ by induction on $m$ (with some inductions on $n$ inside the proof).

Base case. $m=0$. We proceed by induction on $n$. The statement $Q(0,0)$ is vacuously true since there are no $k,l$ statisfying $1$ or $2$ in this case. Suppose $Q(0,n)$ holds for some $n \in \mathbb N$. Then, since $A(0,n)$ is true by assumption, $P(0,n)$ also holds. It follows that $Q(0,n+1)$ must hold. Therefore by the induction principle we conclude that $Q(0,n)$ holds for all $n \in \mathbb N$.

Inductive step. Suppose that, for some $m \in \mathbb N$, $Q(m,n)$ holds for all $n \in \mathbb N$ . We need to show that $Q(m+1,n)$ holds for all $n \in \mathbb N$. We proceed by induction on $n$ ($m$ is fixed). Since $Q(m,0)$ and $A(m,0)$ both hold by assumption, $P(m,0)$ also holds. It follows that $Q(m+1,0)$ must hold.

Now suppose $Q(m+1,n)$ holds for some $n\in\mathbb N$. There are two cases:

1. $k<m+1$ and $l\in\mathbb N$. Then either $k=m$ or $k<m$. In either case we have that $P(k,l)$ holds because $Q(m,l)$ and $A(m,l)$ both hold by assumption.

2. $k=m+1$ and $l<n+1$. Then either $l=n$ or $l<n$. In either case we have that $P(k,l)$ holds because $Q(m+1,n)$ and $A(m+1,n)$ both hold.

It follows that $Q(m+1,n+1)$ is true. Therefore by the induction principle we conclude that $Q(m+1,n)$ holds for all $n\in\mathbb N$.

We have shown by induction on $m$ that $Q(m,n)$ holds for all $m,n∈\mathbb N$. In particular this implies that $P(m,n)$ holds for all $m,n∈\mathbb N$.