Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In most books,the principle of strong induction is stated as follows:

Let $X$ be a well ordered set with an ordering relation $\leq$,and let $P(n)$ be a property pertaining to an element $n\in X$.Let $x_0$ be the smallest element in $X$.$p(x_0)$ is true,and

$$\forall m<n,P(m) \text{ is true}\Rightarrow P(n)\text{ is true}$$ Then we can say that $\forall x\in X$,$P(x)$ is true.


I wonder whether the principle of strong induction can be stated as such:

Let $X$ be a well ordered set with an ordering relation $\leq$,and let $P(n)$ be a property pertaining to an element $n\in X$.Let $x_0$ be the smallest element in $X$.$p(x_0)$ is true,and

$$P(y)\text{ is true} \Rightarrow P(\min (X\backslash\{x\in X:x\leq y \}))\text{ is true}$$Then we can say that $\forall x\in X$,$P(x)$ is true.

share|improve this question
1  
Note that in the first version there is no need to show $p(x_0)$ separately as "$\forall m<x_0$" is a void condition. –  Hagen von Eitzen Jan 26 '13 at 13:00
    
@HagenvonEitzen Thanks. –  Luqing Ye Jan 26 '13 at 15:39
add comment

4 Answers

up vote 2 down vote accepted

For general well-ordered sets your statement of well-ordered (strong) induction does not work for two reasons:

  1. A well-ordered set can have elements without an immediate predecessor. An example of this is the ordinal $\omega + 1 = \{ 0 , 1, \ldots \} \cup \{ \omega \}$, ordered by extending the usual ordering on the natural numbers by declaring $x \leq \omega$ for all $x \in \omega+1$.

    Given such an element $z$ in a well-ordered set $X$ there would be no $y \in X$ such that $z = \min ( X \setminus \{ x \in X : x \leq y \} )$, and so the induction step would never concern itself with $z$. Or, to be a bit more precise, if this $z$ happened to be the least element of $X$ for which $P(x)$ fails, then you could not derive a contradiction by using your inductive implication to discover a yet smaller element for which $P(x)$ fails.

  2. A well-ordered set can have maximum elements, for example $X = \{ 0 , 1 , 2 , \ldots , 424 \}$ has $424$ as its maximum. Note that if $y$ is the maximum element of $X$ then $$X \setminus \{ x \in X : x \leq y \} = X \setminus X = \emptyset$$ which has no elements, let alone a minimum element. Therefore the implication $$P(y) \rightarrow P (\min (X \setminus \{x\in X:x\leq y \}))$$ would either be meaningless or false.

share|improve this answer
add comment

For a well ordered set, your definition is the same as normal mathematical induction, because $$\min(X \setminus \{x \leq y \}) = \text{succ}(y)$$ where succ() is the successor operator induced by the well ordering (e.g. $\text{succ}(y) = y+1$ for the naturals). So your assumption then becomes $$P(y) \Rightarrow P(\text{succ}(y))$$ as in normal induction.

Note that strong induction is equivalent to mathematical induction in that both can prove the same things, so while it is technically valid to use your definition, it's not really the strong induction principle.

share|improve this answer
1  
When $n$ is uncountable,do you think the second statement can "enumerate" all the elements of $X$? –  Luqing Ye Jan 26 '13 at 12:49
add comment

Your definition doesn't work at limit stages. As a basic example where it fails you could show that every element of $\omega + 1$ is also an element of $\omega$. There is an equivalent definition of induction where you assume the conditions that you stated and also that whenever $X' \subseteq X$ and $(\forall n \in X')P(n)$ then $P(\sup{X'})$, then $(\forall n)P(n)$.

By the way, in the first definition that you gave (the usual one) you don't need to prove $P(x_0)$; it follows from the other condition because $\{ x | x < x_0 \}$ is empty.

share|improve this answer
    
I don't think that "every element of ω+1 is also an element of ω"... –  Luqing Ye Jan 26 '13 at 15:31
    
@Luqing It isn't, so by contradiction OP's definition of induction fails for $\omega + 1$. Sorry if this wasn't clear. –  aws Jan 27 '13 at 14:44
    
Sorry I misunderstood you ,maybe it is because of my lack of English.@aws –  Luqing Ye Jan 28 '13 at 7:38
add comment

Your phrasing is incorrect; really, you have done nothing more than restate ordinary induction, since $\min (X\backslash\{x\in X:x\leq y \})$ is simply the successor of $y$.

Consider an inductive proof of the statement that every integer greater than 1 has a prime factorization, if we already know that every number has a prime factor:

Let $P(x)$ = "x has a prime factorization".

Now, suppose $P(x)$ is true for all $x < m$. Then to show $P(m)$ is true, we consider two cases:

  • If $m$ is prime, then the prime factorization of $m$ is just $m$.
  • Otherwise, $m$ has a prime factor $p$. $m/p < m$ and so by the inductive hypothesis $P(m/p)$ is true., Let $F$ be a prime factorization of $m/p$. Then $m$ has a prime factorization $p \cdot F$.

Note that the necessary implication here was $P(m/p) \implies P(m)$, where $m$ is very much not the smallest natural number that is not less than or equal to $m/p$.

In other examples of strong induction, not just a single prior statement is used. Sometimes to prove $P(m)$ the argument uses several statements $P(x)$ with $x < m$; occasionally, the argument even needs to invoke the truth of all $P(x)$ with $x < m$.

share|improve this answer
1  
On $\Bbb N$, all 3 induction schema are equivalent: OP = ordinary = strong induction. So what do you mean when you say that the OP's inductive schema does not work when the index set is $\Bbb N?\ \ $ –  Math Gems Jan 26 '13 at 15:09
    
@MathGems: As I pointed out in the aside: to use ordinary induction to prove $P(x)$ for all $x \in \mathbb{N}$, you have to apply it to $Q$. Applying ordinary induction to $P$ doesn't work. –  Hurkyl Jan 26 '13 at 15:42
1  
But the OP's schema works with Q. The problem occurs with limit ordinals, not in $\Bbb N$. –  Math Gems Jan 26 '13 at 15:51
    
@MathGems: The problem also occurs if you want to prove P by applying induction to P. –  Hurkyl Jan 26 '13 at 16:34
1  
But one is free to choose P in the OP's schema, using P' = Q if need be. Is your point that, on $\Bbb N,$ strong induction schema may be more convenient, since one doesn't need to massage strong inductions into ordinary form? If so, then it would help greatly to clarify the intent of your second sentence, e.g. replacing "doesn't work" by "less convenient". –  Math Gems Jan 26 '13 at 16:55
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.