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.

I'm doing a bit of research on set theory. So far it's quite interesting. Right now I'm reading about transfinite induction. The book states the following theorem about induction in a well-ordered set:

Let $(X,<)$ be a well-ordered set. Let $P$ be a property which may hold for elements of $X$. Suppose that, for all $x \in X$, if every element $y<x$ has property $P$, then $x$ has property $P$. Then we conclude that every element of $X$ has property $P$.

The theorem doesn't require a base case to hold. The book mentions that a base case is not needed here because if $x$ is the smallest element of $X$, then there are no elements $y<x$ so vacuously all such elements have property $P$. In a way, I understand what the author is saying. But I appeared to have found a trivial counterexample. If we consider $X=\mathbb{N}$ with the normal ordering, the statement is the same as "strong induction". If we try to "prove" the following statement is true $ \forall n\in \mathbb{N}$:

$P(n)$ is the statement "$n>1000$" ,

(which is obviously false for $n=1$, say)

Then we get something like: Suppose that $n$ is such that $P(m)$ holds whenever $m<n$, then $n>1000$. Thus $P(n)$ holds $\forall n \in \mathbb{N}$.

There's obviously something wrong with the "proof". I suppose it's because "$P(m)$ holds whenever $m<n$" does not imply "$n>1000$"? But I'm not too sure...

Later on, the book states the version of induction for ordinals:

Let $P$ be a property of ordinals, assume that

  • $P(0)$ is true,

  • $P(\alpha)$ implies $P(s(\alpha))$ for any ordinal $\alpha$ ($s(\alpha)$ is the successor ordinal of $\alpha$)

  • If $\lambda$ is a limit ordinal and $P(\beta)$ holds for all $\beta < \lambda$, then $P(\lambda)$ holds.

Then $P(\alpha)$ is true for all ordinals $\alpha$.

This time a base case is required. But I read Wikipedia (http://en.wikipedia.org/wiki/Mathematical_induction) near the bottom under Transfinite Induction and it says "strictly speaking, it doesn't..." so I'm pretty confused.

share|improve this question
    
You cannot let $P(n)$ be a statement that quantifies $n$. $P(n)$ is a statement about $n$, not about all natural numbers. –  Tobias Kildetoft Dec 21 '13 at 20:16
    
Just changed my wording on $P$ concerning on what Tobias said. The book is "Sets, Logic and Categories" by Peter J. Cameron. It's theorem 2.2 and 2.9 in the book. –  Gawin Dec 21 '13 at 20:27
    
Please give a more formal presentation of the "proof". Besides helping answerers, this may help you see the problem yourself. –  Bill Dubuque Dec 21 '13 at 20:47

2 Answers 2

up vote 2 down vote accepted

Strictly speaking, it is true that you don't need to assume the base case because of the following: suppose you have a well-ordered set $X$ with minimal element $x_0$. Then to prove that the property $P(x)$ holds for every element of $X$ you must prove, as you said, that if you assume the property to hold for all elements $y<x$, then it holds for $x$. Notice that this includes proving that if $P$ holds for every element $y<x_0$, then it holds for $x_0$. But as there is no element satisfying $y<x_0$, this amounts exactly to proving that $P(x_0)$ holds, i.e. you have to prove the base case.

share|improve this answer
    
I see. So you still need to prove the base case since the fact that $P$ holds for any $y<x_0$ is somewhat meaningless as no such $y$ exists? –  Gawin Dec 21 '13 at 20:31
    
@Gawin Yes, something like that. Also, usually you have to treat limit ordinals separately. –  Daniel Robert-Nicoud Dec 22 '13 at 1:10

let $A$,$B$ and $C$ be the assertions (quantifiers over the ordinals, restricted to whatever universe may be required)

(A) $\forall m(\;\forall n(n \lt m \rightarrow P(n)) \rightarrow P(m)\;)$

(B) $\forall m P(m)$

(C) $A \land (A \rightarrow B)$

here $(A \rightarrow B)$ is just the law of induction in the formulation you present. but you must still demonstrate the truth of $A$. in particular, $P(0)$ is a consequence of $A$, so if $\lnot P(0)$, $A$ cannot be true.

share|improve this answer

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.