1
$\begingroup$

I encountered the following statement of the infinite descent principle (PID):

PID. Let $p(n)$, $n \in \mathrm{N}$, be an arbitrary property of natural number $n$. Assume that

(e) $p(1)$ is a true statement and

(f) for all $k \in \mathrm{N}$, if the statement $p(k)$ is false then there exists a natural number $m$, $m < k$, for which the statement $p(m)$ is alos false.

Then, the statement $p(n)$ is true for all natural numbers $n \in > \mathrm{N}$.

The original appears on pg. 69 of a pdf.

As I understand from a pure logic viewpoint, condition (e) an be thought of as the base case of strong induction and (f) can be thought of as stating the implication of the induction statement in strong induction in contrapositive form.

However from a pure intuitive viewpoint I don't understand the need for (e). It feels that (f) should be enough since that gives the infinite descent which contradicts that there are only a finite number that can be less than a number.

As far as a know most informal proofs using the method of infinite descent don't mention a base case like (e) in the proof. What subtlety am I missing?

I've never seen an exposition of descent that included a base case. Can someone explain why its there since as Hagen von Eitzen points out its redundant

$\endgroup$
1
  • 2
    $\begingroup$ You are right, but clarity trumps minimality. $\endgroup$ Jul 14, 2014 at 18:28

3 Answers 3

1
$\begingroup$

Note that (e) can be shown from (f): Assume $p(1)$ is false. Then by (f), there existsa natural number $m$, $m<1$ for which $p(m)$ is false. This alraeady fails because thwe cannot have $m<1$. Hence the assumptin that $p(1)$ is false must be wrong, i.e. (e) holds.

$\endgroup$
1
  • $\begingroup$ I get what you are saying. So why would the base case be mentioned? I've never seen an exposition of descent that included a base case. $\endgroup$
    – user782220
    Jul 17, 2014 at 20:36
1
$\begingroup$

Its the same idea as strong induction. Technically, you can phrase it as:

If $\forall a < b \ a \in S \implies b \in S$, then $S = \mathbb{N}$

You don't need a base case because when $b = 1$, all $a < b$ are in $S$ (vacuous truth), so this essentially requires $1 \in S$.

But this step almost always requires a different proof, so it is commonly stated as a separate condition.

$\endgroup$
0
$\begingroup$

Without the base case, (e), it seems that the statement could be false for all natural numbers. With the base case you run into $p(1)$ being both true and false, a contradiction.

$\endgroup$
1
  • $\begingroup$ No, $(f)\,\Rightarrow\,(e),\,$ see the other answers. $\endgroup$ Jul 14, 2014 at 20:30

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.