5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ You cannot let $P(n)$ be a statement that quantifies $n$. $P(n)$ is a statement about $n$, not about all natural numbers. $\endgroup$ Dec 21, 2013 at 20:16
  • $\begingroup$ 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. $\endgroup$
    – Gawin
    Dec 21, 2013 at 20:27
  • $\begingroup$ Please give a more formal presentation of the "proof". Besides helping answerers, this may help you see the problem yourself. $\endgroup$ Dec 21, 2013 at 20:47

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Gawin
    Dec 21, 2013 at 20:31
  • $\begingroup$ @Gawin Yes, something like that. Also, usually you have to treat limit ordinals separately. $\endgroup$ Dec 22, 2013 at 1:10
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .