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 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 $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 There's obviously something wrong with the "proof". I suppose it's because "$P(m)$ holds whenever $m 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
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
No comments:
Post a Comment