Induction without base case? 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.
 A: 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.
A: 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.
