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.