Is this proof of the First Transfinite Induction Principle incomplete or incorrect?

Question

Context: Cheating on my homework.

I am studying Smullyan and Fitting's Set Theory and the Continuum Hypothesis (2010: rev.ed.) and I have reached Chapter 4: Superinduction, Well-Ordering and Choice: $\S 1$ Introduction to Well-Ordering, Theorem $1.8$ (Transfinite Induction Principle $1$).

Let $A$ be a well-ordered class under $\le$. Let $P$ be a property satisfying the following condition: For every $x \in A$, if $P$ holds for every $y < x$, $P$ holds for $x$. Then $P$ holds for every element of $A$.

The proof of this theorem is offered up as follows:

If $P$ failed to hold for some element of $A$, then there must be a least element $x$ of $A$ for which $P$ fails to hold. Then for every $y < x$, $P$ holds for $y$. This violates the hypothesis. $\blacksquare$

And yet, suppose the "some element" that $P$ fails to hold for is the smallest element of $A$.

Then the set of elements that $P$ fails to hold for, of which $x$ is the smallest, has no $y$ for which $y < x$.

Hence $P$ holds for no elements of $A$.

While this does not appear to invalidate the statement of the theorem, it does appear to invalidate the proof.

Is the proof as given above in S&F actually incorrect and/or incomplete, or am I failing once more to misunderstand the concept of vacuous truth?

• If the former, what would need to be done to salvage the proof?
• If the latter, where is my thinking incorrect?

Answer 1

I believe the misunderstanding is precisely related to "vacuous truths", as you said.

When you state your hypothesis:

For every $x \in A$, if $P$ holds for every $y < x$, then $P$ holds for $x$.

and you plug in the smallest element of $A$ for $x$, the hypothesis reads:

if $P$ holds for every $y $ in the empty set, then $P$ holds for $x$.

Notice that any property, whatsoever, holds for every $y $ in the empty set!

Moreover, when an implication has a manifestly true antecedent, like the one above, the truth value of the whole thing is the truth value of the consequent.

In other words, the above instance of the hypothesis simply says that $P$ holds for $x$, period. Hence it is already a contradiction to assume that $P$ fails for the smallest element.

PS: In the usual induction process, as taught at more elementary levels, it is usually explicitly assumed that the given property holds for the smallest element, namely the natural number zero. We could therefore include a similar hypothesis that $P$ holds for the least element, but this is actually superfluous by the reasoning above.