Double induction 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.
 A: 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.
A: 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

*

*$k<m$

*$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:

*

*$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.


*$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$.
