Vacuously True Starting Point in Transfinite Induction

[BDV]

I have a hard time understanding/justifying the proper usage of "vacuously true" starting points in set theory reasoning.

E.g.,

For transfinite induction, one does not have the requirement of a starting point.
If p(a) true for all a<b implies P(b), then P(x) true for all ordinals.

In regular induction, one has both P(0) and P(n)=>P(n+1).

In transfinite induction the starting point P(0) is handwaved as being vacuously true. But then, it is vacuously false, too.

The condition for transfinite induction is obviously much stronger than that for regular induction, and possibly no P can be such that (P(0) - false) and (induction condition -true). That, I would understand. But how can a vacuously true statement - which is equally a vacuously false statement be the starting point for any true/correct judgement?

Can anyone shed some light on this issue?

 

[Stephen Tashi]

Are asking this because of the wording of the Wikipedia article on Transfinite Induction? Use Wolfram instead: http://mathworld.wolfram.com/TransfiniteInduction.html

 

[BDV]

Many authors, in online notes and in published books (e.g. Suppes in his Axiomatic Set Theory - 2nd ed. page 195-196, don't bother with P(0).

So is P(0) - true needed as a precondition (my reading of wolfram link) or not?

The only way out of this confusion (for me) is iff the inductive hypothesis implies that P(0) -true .

 

[yossell]

I'm not sure what you mean when you say P(0) is handwaved as being vacuously true. It isn't. For instance, if P is the property of having a member, then, under the usual set theoretic identification of 0 with the empty set, it is false.

Of course, it immediately follows that the inductive hypothesis fails at 0 - for what is vacuously true is that every predecessor of 0 has a member. This is vacuously true because we have a universal statement with no instances.

And in general, for any P, if P(0) is false, then the inductive hypothesis fails - for, vacuously, every predecessor of 0 has P, but P(0) is false. In this sense, for the inductive hypothesis to hold, P(0) must be true.

 

[Stephen Tashi]

for the inductive hypothesis to hold, P(0) must be true.

It would help to have a precise statement of the inductive hypothesis. There is a discussion on the "talk" page for the Wikipedia article on Transfinite Induction about whether P(0) must be treated as special case and it discusses other technical points.

The way I would interpret the "no P(0)" version of transfinite induction (slightly modifying the sybolism of one author on the talk page) is:

$( \forall \alpha ( \forall \beta ( \beta \lt \alpha \wedge P(\beta) \implies P(\alpha)) \implies (\forall \alpha P(\alpha))$

This implication could only be false in a case where the hypothesis $( \forall \alpha ( \forall \beta ( \beta \lt \alpha \wedge P(\beta) \implies P(\alpha))$ is true and the conclusion $\forall \alpha P(\alpha)$ is false.

Suppose $P(\beta)$ is false for all $\beta$. Then $\beta \lt \alpha \wedge P(\beta)$ is false for all $\beta$. Hence the implication $\beta \lt \alpha \wedge P(\beta) \implies P(\alpha)$ is (vacuuously) true for all $\beta$. I think this is the problem BDV sees.

Consider the case $\alpha = 0$. Then $\beta < \alpha$ is false for each $\beta$ Hence $\beta \lt \alpha \wedge P(\beta)$ is false. So the implication $\beta \lt \alpha \wedge P(\beta) \implies P(\alpha)$ is vacuuously true.

Apparently I have not formulated "the inductive hypothesis" correctly. What is the precise formulation?

 

[yossell]

Stephen,
I believe the bracketing is incorrect in your formulation. The left and right brackets don't match up.

The relevant conditional of the induction step is: if every b smaller than a has property P, then a has property P

When a is zero, the universal generalisation is trivially true. Thus, the conditional has a true antecedent and is not trivial. For a conditional with a true antecedent to be true, the consequent must also be true. Hence P(0)

 

[BDV]

Sorry to be a thick skull on this topic but :

P(a) for a<0

is also trivially (vacuously) false.

It would make sense to me that by the formalism/formulation of the inductive hypothesis, proving the inductive hypothesis includes having to prove P(0).

I am talking about a specific P.

 

[yossell]

Sorry BDV -- perhaps I'm not getting your worry.

The induction principle holds for any P, but I don't think my reply loses anything if you focus on a specific P.

The statement 'for all a < 0, P(a) is false' is indeed vacuously true. But I don't see why this worries you. In the course of using the inductive principle, you have to show that, for ANY a, if b < a -> Pb, then Pa. For this to hold, it had better be true that P(0) - for any b, if b < 0 -> P(b) is vacuously true; so if P(0) is false, the principle fails.

I would have thought this should allay your worries. Suppes' version of the principle is not as vacuous as it seems, after all. But, given the principle, there's no need to add the further condition that P(0)

Just for clarity's sake, here's what I take to be the formal statement of transfinite induction: As Stephen says, there may be confusion if we're not completely clear where the brackets are (at least, I hope this helps -- my texing skills are awful, and I pray this doesn't just muddy the waters further)

$$( \forall \alpha (\forall \beta ( \beta \lt \alpha \implies P(\beta))) \implies P(\alpha)) \implies (\forall \alpha P(\alpha))$$

 

[Stephen Tashi]

Stephen,
I believe the bracketing is incorrect in your formulation. The left and right brackets don't match up.

I'll try this correction:
$\{ \forall \alpha \ ( \forall \beta \ (\ ( \beta \lt \alpha \wedge P(\beta) ) \implies P(\alpha)\ )\ \ )\} \implies \{\forall x P(x) \}$

The relevant conditional of the induction step is: if every b smaller than a has property P, then a has property P

When a is zero, the universal generalisation is trivially true. Thus, the conditional has a true antecedent and is not trivial. For a conditional with a true antecedent to be true, the consequent must also be true. Hence P(0)

What is meant by "the universal generalisation"? In my version, we can consider the statement:
$\forall \beta( \ (\beta \lt \alpha \wedge P(\beta)) \implies P(\alpha) \ )$ In the particlar case that $\alpha = 0$, the antecedant is false.

P(a) for a<0

is also trivially (vacuously) false.

I don't see that. Of course, we haven't formally placed any restrictions on what the variables in our symbolic logic represent. If we assume all variables must be ordinals then $P(x)$ is always indicates evaluating $P(x)$ at an ordinal. There is no "default" value of $P$ when the argument is not an ordinal. So "P(a) evaluated at the ordinal with the property that a < 0" is not defined and you can't actually express that idea in a system where all variables must be ordinals. You can express things like $\beta \lt 0 \wedge P(\beta)$ since this expression makes sense when $\beta = 2$, for example.

 

[Stephen Tashi]

Just for clarity's sake, here's what I take to be the formal statement of transfinite induction: As Stephen says, there may be confusion if we're not completely clear where the brackets are (at least, I hope this helps -- my texing skills are awful, and I pray this doesn't just muddy the waters further)

$$( \forall \alpha (\forall \beta ( \beta \lt \alpha \implies P(\beta))) \implies P(\alpha)) \implies (\forall \alpha P(\alpha))$$

My eyes glaze over when there are lots of parentheses, but I thiink your interpretation is what most of the Wikipedia contributors have in mind. The distinction is your compound implication $(\beta \lt \alpha \implies P(\beta)) \implies P(\alpha)$ vs my formulation $\beta \lt \alpha \wedge P(\beta) \implies P(\alpha)$. Your formulation does allow one to conclude that $P(0)$ is true when the statement as a whole is true.

 

[yossell]

The distinction is your compound implication $(\beta \lt \alpha \implies P(\beta)) \implies P(\alpha)$ vs my formulation $\beta \lt \alpha \wedge P(\beta) \implies P(\alpha)$.

We surely need to be explicit about the scope of the quantifiers - in particular, the omitted universal quantifier over \beta, to assess whether what you intend to write is equivalent to the formulation I have written. Now, in the version you've given, you have P(a) falling in the scope of the 'for all \beta'.
Now, '(for all y)(P(y) -> D)' is equivalent to '(there is a y)(Py) -> D'. This may mean that your version of the principle isn't saying what you think it's saying.

 

[Stephen Tashi]

We surely need to be explicit about the scope of the quantifiers - in particular, the omitted universal quantifier over \beta, to assess whether what you intend to write is equivalent to the formulation I have written.

Taking $\alpha$ as a constant for the time being, what I mean to express is $\forall \beta(\ (\beta < \alpha \wedge P(\beta)) \implies P(\alpha) )$

With that formulation and when $\alpha = 0$ we have (for any $\beta$ ) that $\beta < \alpha$ is false. Hence the compound statement $\beta < \alpha \wedge P(\beta)$ is false. Hence the implication as a whole is true regardless of the truth or falsity of $P(\alpha)$.

I agree that your formulation is what the people who use the "no P(0)" version of Transfinite Induction must have in mind. The technical problem is seeing how the language they use to express this version translates to your interpretation and not mine. It seems to boil down to the distinction in propositonal logic between $(P \wedge Q) \implies R$ versus $(P \implies Q) \implies R$.

 

[yossell]

Taking $\alpha$ as a constant for the time being, what I mean to express is $\forall \beta(\ (\beta < \alpha \wedge P(\beta)) \implies P(\alpha) )$

Ok - so the last P(a) falls within the scope of the opening quantifier, even though it doesn't contain the variable b. I think that's the problem - I don't think that this statement is the correct way to phrase induction.

Let a = 2, and suppose that P(0) and ¬P(1). A correct statement of the principle of induction should not allow us to infer from this that P(2). But the version you've written does. Since, by your principle with a = 2, for every b, ((b < 2 & P(b)) -> P(2)), it follows that in particular, (0 < 2 & P(0)) -> P(2)). Since the two conjuncts in the antecedent are true, the consequent must be true. So the mere fact that 2 had a single predecessor which was P gives us that 2 itself has P.


It *is* surprising that the scope of quantifiers makes such a difference -- to this day, it's always a surprise to see that (Ax)( Fx -> G) is equivalent to (Ex)(Fx) -> G, and (Ex)(Fx -> D) is equivalent to (Ax)(Fx) -> D.

 

[BDV]

Thank you for the replies and the links.

Yossell, I had thought that your statement:

"And in general, for any P, if P(0) is false, then the inductive hypothesis fails - for, vacuously, every predecessor of 0 has P, but P(0) is false. In this sense, for the inductive hypothesis to hold, P(0) must be true." - clarified it for me.

Except that I realized it didn't. My snag is getting something (P(0)-true) from nothing (as there is no b<0).

Now, I realize that the argument is that one gets (P(0) - true) not from "nothing" but from (inductive hypothesis - true). But I still fail to understand the "how". Sorry for being such a blockhead, when I don't get it, I really don't get it...

Guys, I will parse over your kind explanations and the links info, and hopefully I'll get to the "A-HA!" moment.

 

[Stephen Tashi]

Ok - so the last P(a) falls within the scope of the opening quantifier, even though it doesn't contain the variable b. I think that's the problem - I don't think that this statement is the correct way to phrase induction.

I agree that my way is incorrect. In English, my way says something like "If anyone of the ordinals less than alpha makes P true then alpha makes P true". The desired hypothesis is "if all of the ordinals less than alpha make P true then alpha makes P true".

 

[BDV]

So I read, maybe there I chanced on a glimmer of understanding.

P(0) is semantically included in the inductive hypothesis. In practice, though, one would have to prove P(0) separately.

Now, if that is not correct, my problem continues to be computing properties of existing objects based on properties of inexistent objects.

...

!

However if the inductive hypothesis is stated as:


$\neg(\exists\beta|\beta<\alpha\wedge(P(\beta)-false))$

Then, all of the sudden it makes sense to me, because it's about the nonexistence of a a thing with certain property (namely beta<alpha, and P(beta) - false).

I had a similar snag with the unicity of the empty set, and I finally saw it by negating the both parts in that equivalence (x $\notin$ Empty1 $\Leftrightarrow$ x $\notin$ Empty2)

 

[Stephen Tashi]

P(0) is semantically included in the inductive hypothesis. In practice, though, one would have to prove P(0) separately.

I agree with that.

However if the inductive hypothesis is stated as:

$\neg(\exists\beta|\beta<\alpha\wedge(P(\beta)-false))$

I don't understand that notation, but I agree it should be possible to state the inductive hypothessis in a "negative" form. Taking the inductive hypothesis as being of the form $S \implies T$, one can state it as the equivalent $\neg T \cup S$. Then you can double negate that form.

 

[BDV]

To review an old topic. Still cannot wrap my head around the induction hypothesis making P(0) true from vacuously true vacuous predecessors.

OTOH, once I use the negative of the induction hypothesis things become crystal clear (to me). That is, when the induction hypothesis is TRUE, for P(α) to be false there should be a β<α such that P(β) is false. Patently, if α=0, the existence of such β is impossible, so P(0) better be true, lest the induction hypothesis itself is exposed as incorrect.