2

Suppose I am proving the statement $P(m,n)$ in natural numbers.

Steps:

1) Proving $P(1,1)$ true

2) $P(m,n) \implies P(m+1,n)$

My doubt while proving second step is that, can I assume $P(m,1), P(m,2),\cdots P(m,n)$ are true or I have to prove by taking $n$ as constant (using $P(m,n)$ only)?

Suppose I prove step 2, then

3) $P(m,n) \implies P(m,n+1)$

Here can I assume $P(m-1,n+1)$ as true?

md2perpe
  • 26,770
hanugm
  • 2,353
  • 1
  • 13
  • 34
  • 1
    $n$ must remain constant. Once you have proved $P(m,n)$ for a fixed $n$ then you can apply induction in the second argument. – Dog_69 Aug 04 '18 at 21:20
  • In you prove $\forall{n}P(1,n)$ and you prove $\forall{n}P(m,n)\implies\forall{n}P(m+1,n)$ you will have proved the theorem. – saulspatz Aug 04 '18 at 21:24
  • Exactly. The validity of your reasoning depends on this : can you prove 1) $P(1,n)$ true for all $n$, 2) $P(m,n)\Longrightarrow P(m+1,n)$ for all $n$ ? If this is the case, then $n$ is merely a parameter in your induction. If not, then you have to build some sort of induction on $\mathbb N\times \mathbb N$, which can be quite tricky. – Nicolas FRANCOIS Aug 04 '18 at 21:25
  • @NicolasFRANCOIS Can I prove $P(m,n) \implies P(m+1,n+1)$ without step 2 and 3? – hanugm Aug 04 '18 at 21:28
  • To be more precise on the "quite tricky" part : it is not that you can't build good orders on $\mathbb N\times \mathbb N$, but the double induction part can be not so easy to find. Maybe $P(m,n)\Longrightarrow P(m,n+1)$ is not that hard to prove... – Nicolas FRANCOIS Aug 04 '18 at 21:28
  • @Nicole It's not that tricky! It's just the lexicographic ordering. See my answer. – Rob Arthan Aug 04 '18 at 21:37
  • I didn't say it's difficult to fine good orders on $\mathbb N\times \mathbb N$, I said it's not always easy to find the induction step on such a good order. Sometimes, you have to be creative in your good orders. It depends on the property $P(m,n)$. – Nicolas FRANCOIS Aug 04 '18 at 21:40
  • 1
    @hanugm : no, it's not enough. You lose $P(m,n+1)$ and $P(m+1,n)$. – Nicolas FRANCOIS Aug 04 '18 at 21:41

2 Answers2

1

If $X$ is a set that is well-ordered by some ordering relation $<$, then you can prove a property $Q(x)$ by induction on $x$, by showing that for any $x \in X$, if $Q(y)$ holds for every $y < x$, then $Q(x)$ holds.

This is called complete or course-of-values induction when $X$ is the natural numbers with the usual ordering. Peano's principle of induction for the natural numbers asking you to prove that $Q(0)$ holds and that for every $x \in \Bbb{N}$, $Q(x + 1)$ holds if $Q(x)$ holds is a special case.

In your case, $X$ is $\Bbb{N}\times\Bbb{N}$ (the set of pairs of natural numbers $(m, n)$). The induction principle you want to use is justified by considering the lexicographic ordering on $X$: $(m, n) < (m', n')$ iff $m < m'$ or $m = m'$ and $n < n'$.

Rob Arthan
  • 48,577
1

It is easier to figure out the answer by drawing a grid with the first few elements of $\Bbb N\times \Bbb N$.

Given the question you're asking, what you really want to do is proceed by squares: let $T(n)$ denote the proposition

$P(p,q)$ is true for all $p,q$ such that $p\leq n$ and $q\leq n$.

I claim that if you prove what you said, then you can prove that $T(n)\implies T(n+1)$ for all $n$.

What you said you can prove is

$$[P(p,1), P(p,2),\cdots P(p,q)]\implies P(p+1,q)\tag{1}$$ $$[P(p-1,q+1), P(p,q)] \implies P(p,q+1)\tag{2}$$

I'm assuming here that cases where $p\leq 0$ or $q\leq 0$ are considered vacuously true.

Now assume $T(n)$.

  • By $(2)$, you can prove that $P(1,n+1)$ and then $P(p,n+1)$ for all $p\leq n$.
  • By applying $(1)$ to every $q$ between $1$ and $n+1$, you get $P(n+1,q)$ for all $q\leq n+1$.

Hence $T(n+1)$ as claimed.

Arnaud Mortier
  • 27,276