Intuition for Well-Founded Relations

Question

On page 11 of Holz's Introduction to Cardinal Arithmetic a well founded relation $R$ is defined as that for which

1. $\forall x\in\text{fld}(R)\exists y\left(x\in y\land R^{-1}[y]\subseteq y\right)$, and
2. $\forall x\subseteq\text{fld}\left(x\neq 0\implies \exists y\in x\forall z\in x\left(\sim z R y\right)\right).$

Is there any more intuitive way of explaining this concept and why it is introduced?

Answer 1

The user drhab has mentioned in the comments that well-foundedness is used for induction. The usual proof that induction is a sound method of mathematical reasoning goes something along these lines:

Say that you are trying to prove $\forall(x\in\mathbb N)(\phi(x))$ for some property $\phi$. Assume towards a contradiction that you have proven $\phi(0)$ and $\forall(x\in\mathbb N)(\phi(x)\implies\phi(x+1))$, but yet $\phi$ is false for some natural number. Consider the set $F$ of natural numbers for which $\phi$ fails, or $\{n\in\mathbb N\mid\lnot\phi(n)\}$. Since we assumed $\phi$ is false for some natural number, it is nonempty, so since the natural numbers are well-ordered, $F$ has a least element, call it $k$. We know $k$ can't be $0$, since you proved $\phi(0)$. So $k$ has to be some natural number greater than $0$. But since $k$ was the least element of $F$, the smaller number $k-1$ can't be in $F$, so $\phi(k-1)$ must be true. But then by the induction that you have proved, $\phi(k-1)\implies\phi(k)$, so $\phi(k)$ is true. But this contradicts that $k$ was an element of $F$.

The use of well-foundedness of $\mathbb N$ is in bold and is needed to pick the least element $k$ out of $F$ and continue the proof.

This also intuitively explains why induction does not work in some scenarios, like if one were to attempt to prove a property holds for all subsets of $\mathbb N$ by "building up the subsets". Specifically, say that someone has proven $\phi(\varnothing)$, and has shown that for $X\subseteq\mathbb N$, $y\in\mathbb N$, if you assume $\phi(X)$ is proven, then you can prove $\phi(X\cup\{y\})$, and then attempts to conclude that $\phi(X)$ holds for all $X\subseteq\mathbb N$. (For example, they show that $\phi(\{\})$ holds, then from that they conclude that $\phi(\{0\})$ holds, then that $\phi(\{0,1\})$ holds, $\phi(\{0,1,4\})$ holds, $\phi(\{0,1,4,9\})$ holds, etc., then they claim that they have just shown $\phi(\textrm{set of square numbers})$ holds by induction.)

Yet this method of induction can give false conclusions. For example, say $\phi(X)$ is "$X$ is finite". You can prove $\varnothing$ is finite, and that if $X$ is finite then $X\cup\{y\}$ has to be still finite, but clearly this attempt of induction must be doing something wrong, as not every subset of $\mathbb N$ is finite! The key thing here is that well-foundedness doesn't hold. There is an infinite decreasing sequence of counterexamples $\ldots\subset\{4,9,16,\ldots\}\subset\{1,4,9,16,\ldots\}\subset\{0,1,4,9,16,\ldots\}$, so you can't take a "smallest" counterexample and use the fact that it's the smallest to derive a contradiction, like we did in the natural number case - in the realm of subsets of $\mathbb N$, there is not always a smallest one out of any given set of them, as $\subset$ is not well-founded on $\mathcal P(\mathbb N)$. In the falling domino metaphor for induction, the problem is that the dominos for some $X$ like $\{0,1,4,9,16,\ldots\}$ are unreachable, there is an infinite backwards sequence of dominos before it that never ends up getting toppled.

---

About this formulation of well-foundedness, the first condition seems unnecessary, since if I am not mistaken you can always choose $y=\mathrm{fld}(R)$ to get $x\in y$ and $R^{-1}[y]\subseteq y$. (I am assuming $R^{-1}[y]$ is $\{z\in\mathrm{fld}(R)\mid zRy\}$.) The one I am more familiar with is as in drhab's comment, consisting just of condition 2.