Induction without base case?

Question

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.

Answer 1

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.

Answer 2

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.