Understanding the Definition of Well-Founded Induction

Question

I would like to understand how to apply well-founded induction. I have found two definitions which I list now, followed by the question.

(1) A binary relation $\prec$ is well-founded if there are no infinite descending chains. An infinite descending chain is an infinite sequence $a_0, a_1, \dotsc$ such that $a_{i + 1} \prec a_i$ (it goes in reverse order) for all $i \geq 0$.

(2) Well-founded induction says that, in order to prove a property $P$ holds on a set $A$ which has a well-founded binary relation $\prec$, it's enough to prove that $P$ holds for any $a \in A$ whenever $P$ holds for $b \prec a$.

That last paragraph I don't quite understand. And I am having trouble parsing the multiple-nested $\Rightarrow$ blocks in the formal definition:

$$\forall a \in A.(\forall b \in A.b \prec a \Rightarrow P(b)) \Rightarrow P(a) \Rightarrow \forall a \in A.P(a)$$

An alternative from Wikipedia is just as difficult to parse:

(3) If $x$ is an element of $X$ and $P(y)$ is true for all $y$ such that $y R x$, then $P(x)$ must also be true.

$$\forall x\in X\,[(\forall y\in X\,(y\,R\,x\to P(y)))\to P(x)]\to \forall x\in X\,P(x)$$

The questions are:

1. If one could break down / parse that formal equation to explain its meaning.
2. And likewise for that paragraph (2), what it means that "it's enough to prove that $P$ holds for any $a \in A$ whenever $P$ holds for $b \prec a$"

My attempt at understanding the wiki version is, for all $x \in X$, then if [the first big block] is true, then we can say for all $x \in X$, $P(x)$ is true. So that is essentially saying if that big chunk is true, then we have proven our property $P(x)$ is true for all x. Not sure how that is the case, but continuing...

Then the "first big block" is saying, if for all $y \in X$ [the second big block] is true, then $P(x)$ is true, for the specific $x$ we are focused on atm. So for all $y \in X$, $P(x)$ is going to be true if that "second big block" is true.

Finally, the "second big block" is saying if $y$ precedes $x$, then $P(y)$ is true. So if $y$ comes before $x$, then we at least know $P(y)$ is true. Not really sure what this means (how we know $P(y)$ is true).

So to summarize, if for all $x$, that for all $y$, if $y$ precedes $x$ then $P(y)$ is true, that if that is true, then $P(x)$ is true, and if that's true, then $P(x)$ is true for all $x$.

I have no idea what I am saying right now lol, I am having a tough time understanding this and looking for some guidance. Thank you so much.

Answer 1

I think the key to resolving your confusion lies in this paragraph:

Finally, the "second big block" is saying if $y$ precedes $x$, then $P(y)$ is true. So if $y$ comes before $x$, then we at least know $P(y)$ is true. Not really sure what this means (how we know $P(y)$ is true).

Note that we don't have to know how $P(y)$ is true ... we just have to show that if $P(y)$ is true for all $y$ that are 'smaller' than $x$, then $P(x)$ will hold as well. For if we can show that, then indeed all objects will have property $P$.

And why is that?

Well, take any arbitrary object of the set. Given that there is no infinitely descending chain, there are only two possibilities:

A. The object has no 'smaller' element. We call such an element a 'minimal' element. There may be any number of 'minimal elements, but every minimal element $x$ will have to have the property $P$ once we were able to show that if $P(y)$ is true for all $y$ that are 'smaller' than $x$, then $P(x)$ will hold as well. And that is because with no smaller elements, it is vacuously true that $P(y)$ is true for all $y$ that are 'smaller' than such a minmal element, and hence the minimal element will have to have the property $P$. As such, these 'minimal elements' are of course the base cases of the induction.

B. The object is some finite number of steps 'up' from the base cases. Well, given that those base cases all have the property, then their successors all have the property as well, etc. ... and given that any object is only some finite number of steps up from the base cases, eventually this step-by-step 'propagation' of objects having the property $P$ will reach the object under consideration as well.

In the end, the logic here is really very similar to the logic behind strong induction for the natural numbers. It's just generalized to point out that it will work for any well-founded set.

Answer 2

Let $A$ have a well-founded order $\prec$. A proof by well-founded induction would look like this:

Theorem. For all $x\in A$ we have $P(x)$.

Proof. Let $a\in A$ be arbitrary. Assume that $P(b)$ holds for all $b$ with $b\prec a$. Then (bla bla bla ... some argument ... bla bla). Therefore, also $P(a)$. Thus the claim of the theorem follows by well-founded induction. $\square$

You may note that this proof skeleton is very similar to what is called "strong induction" for the natural numbers. And as to why well-founded induction works is indeed very similar to why (strong) induction works on the natural: The central point of the proof shows

If $P(b)$ holds true for all $b\prec a$, then $P(a)$

which is the same as saying

If $\neg P(a)$, then there exists $b\prec a$ with $\neg P(b)$

or succinctly

There is no smallest counterexample

And this the shows that there is no counterexample at all because for any counterexample $a_0$, the continued picking of smaller counterexamples $a_1\prec a_0$, $a_2\prec a_1$, etc. would give us an infinite descending chain.