How is induction related to a well founded set?

Question

I read a proof that went along these lines:

"Let $(X, \le)$ be a woset. Let $E$ be a subset of $X$ such that:

1. the minimal element of $X$ is a member of $E$
2. for any $x \in X$, if $\forall_y[y \lt x \rightarrow y \in E]$, then $x \in E$

Then, $E = X.$ Proof:

Suppose that $E \ne X$. Then, let $x$ be the minimal element of $X - E$. Since, it is an element of $X - E$, it can not be an element of $E$. But, any $y \lt x$ would imply $y \in E$, because $x$ is the minimal element of $X - E$, so any element $y$ such that, $y \lt x$ would have to be in $E$. If it wasn't, $x$ wouldn't be the minimal element of $X -E$. Since $y \lt x$ implies $y \in E$, then by the second condition, $x \in E$ and a contradiction arises, so $X = E$."

But, then the claim was made that this being true allows proof by induction on any well founded set. I understand the proof, but I don't see how this theorem and induction are related. Could someone explain?

Answer 1

Notice that a well-ordered set is precisely a well-founded total ordering, but the proof you quoted makes no use of the total property, so it is valid whenever $X$ is well-founded.

Next, notice that condition 1 is redundant, because it is simply the special case of condition 2 where $x$ is the minimal element of $X$.

(In that case, there simply is no $y \in X$ such that $y < x$, so the antecedent proposition that $y \in E$ for all $y < x$ is vacuously true, therefore the consequence that $x \in E$ is also true.)

Finally, notice that the proof actually works in both directions. Condition 2 can be rewritten:

2' If $x \in X \setminus E$ then there exists $y < x$ such that $y \in X \setminus E$.

Equivalently:

2'' $X \setminus E$ has no minimal element.

So what was proved was the implication:

"If $E$ is any subset of $X$ such that $X \setminus E$ has no minimal element, then $X \setminus E$ is empty."

Since $E$ is an arbitrary subset of $X$, this is equivalent to the implication:

"If $F$ is any subset of $X$ with no minimal element, then $F$ is empty."

Or to put it another way:

"If $F$ is any non-empty subset of $X$, then $F$ has a minimal element."

Of course this is true, by definition, if and only if $X$ is well-founded.

In other words, the proposition that induction on $X$ is a valid method of proof can actually be used as an alternative definition of what it means for the poset $X$ to be well-founded.