2

The principle of infinite descent states that if the truth of $P(n)$ for some natural number $n$ implies the truth of $P(m)$ for some natural number $m<n$, then $P(k)$ is false for all natural numbers $k$.

However, there's a variant of mathematical induction for finite sets, which I'll called "downward induction":

Suppose $P(k+1) \implies P(k)$ for some natural number $k$, and suppose also that $P(n_{0})$ holds for some natural number $n_{0}$. Then $P(k)$ holds for every $k \leq n_{0}$.

Am I wrong in thinking that the step $P(k+1) \implies P(k)$ in downward induction is a special case of the step in infinite descent? Assuming that $P(k+1)$ is true, and showing that it implies $P(k)$ amounts to to the same thing as the step in infinite descent if we let $n=k+1$, and $k$ is definitely less than $n$. The only difference is that we need to check $P(n_{0})$.

So it seems that in a hypothetical infinite descent proof where the smaller number that we construct immediately precedes the number $n$ that we assume to satisfy $P$, we need to ensure that no natural number $n_{0}$ satifies the property, or else we won't be showing that no natural number satisfies the property, but all natural numbers up to $n_{0}$ satisfies the property! But clearly this is false, because we'll end up at where we started. Where did I go wrong?

Maxis Jaisi
  • 1,553
  • 1
    The principle of infinite descent works because a natural number only has finite descents. By repeating you will arrive at some $n$ such that no natural $m$ exists with $m<n$. That gives the contradiction. By what you call "downward induction" we are dealing with a natural number of the form $k+1$ which has a decent in $k$. By repeating after finite number of steps you will arrive at a natural number hat has no descent and there the process stops. – drhab Mar 03 '17 at 14:54

2 Answers2

3

The difference between the two principles is that the chain of implications terminates in downward induction, whereas in infinite descent it does not terminate.

Examine the two following statements carefully to see how they are different:

A) From $k\in \mathbb N$ and $P(k+1)$ you can conclude $P(k).$

B) From $m\in \mathbb N$ and $P(m)$ you can conclude $m - 1\in \mathbb N$ and $P(m-1).$

The difference is that statement A applies only when we know that there actually exists an natural number $k$ at which the conclusion $P(k)$ can be evaluated. Statement B has no such safeguard with respect to $P(m-1).$

In particular, let $n_0$ be the least natural number ($n_0 = 1$ or $n_0 = 0,$ depending on your definition of "natural number"). Then from the assumptions that statement B is true and that $P(n_0)$ is true, it follows that $n_0 - 1$ is a natural number. This is a false conclusion, of course. But if instead we have that statement A is true and that $P(n_0)$ is true, we are not led to any such false conclusions; there is no $k\in\mathbb N$ such that $k + 1 = n_0,$ so the antecedent of A is false, so we do not conclude the consequence.

Statement B is just a special case of infinite descent in which the "next" natural number in the chain is always one less than the number "before" it.

In summary, downward induction starts at some natural number and proceeds downward through every consecutive natural number until it reaches the smallest one, and then it stops. Infinite descent starts at some natural number and proceeds downward, not necessarily visiting every lesser natural number, but never stopping.

Community
  • 1
David K
  • 98,388
1

I think the problem is that in writing $P(k+1) \rightarrow P(k)$ you are implicitly assuming that $k+1 > 0$. That is, a full statement could be written as

$$ \forall k \in \mathbb{N} \,.\, k > 0 \rightarrow (P(k) \rightarrow P(k-1)) \enspace. $$

Once you get to $0$, you are "off the hook." For infinite descent, however, this is not the case. If $P(n)$ is true, there's got to be $m < n$ such that $P(n)$ is true. Once you get to $0$, you run out of $m$'s. You cannot satisfy the existential requirement, which forces you to conclude that $P(n)$ must be false for all $n$.

Fabio Somenzi
  • 7,676