Well-Founded Relations (and Well-Founded Induction)

Direct Knowlege Contributor David A. Smith
  • By David A. Smith, Founder & CEO, Direct Knowledge
  • David Smith has a B.S. and M.S. in Mathematics and has enjoyed teaching calculus, linear algebra, and number theory at both Tarrant County College and the University of Texas at Arlington. David is the Founder and current CEO of Direct Knowledge.

Well-Founded induction is a generalization of mathematical induction.

Well-Founded Induction

Definition. Let $\longrightarrow$ be a relation on $X.$

1) If $A\subseteq X$ and $a\in A,$ then $a$ is called a $\longrightarrow$-minimal element of $A$ if  there does not exist $b\in A$ such that $a\longrightarrow b.$

2) If each nonempty subset of $X$ has a $\longrightarrow$-minimal element, then $\longrightarrow$ is called a well-founded relation on $X.$

3) If $x\in X,$ then the set  $$ \overrightarrow{x\,}=\{y\in X : x\longrightarrow y \land x\neq y\} $$ is called the initial segment of $x.$

Clearly, $b$ is a $\longrightarrow$-minimal element of $A$ if and only if $\overrightarrow{b\,}\cap A=\emptyset.$ 

Proposition. (Well-Founded Induction) A relation $\longrightarrow$ on $X$ is well-founded if and only if the principle of $\longrightarrow$-induction holds:  $$ \forall \, A\subseteq X,  \forall x\in X, (\overrightarrow{x\,}\subseteq A \implies x\in A) \implies  A=X. $$

Proof. Assume $\longrightarrow$ is well-founded on $X.$ Let $A\subseteq X$ and assume the following holds \begin{equation} \label{wellfind} \forall x\in X, \overrightarrow{x\,}\subseteq A \implies x\in A \end{equation} Assume for a contradiction that $X\setminus A$ is nonempty with $\longrightarrow$-minimial element $b.$ Thus $\overrightarrow{b\,}\cap X\setminus A=\emptyset$ and so it follows $\overrightarrow{b\,}\subseteq A.$  By \eqref{wellfind} we have $b\in A$ and thus $X\setminus A$ is empty. Hence $A=X.$ Conversely, assume the principle of induction holds and suppose $A$ is a nonempty subset of $X$ with no $\longrightarrow$-minimal element. We will apply the principle of $\longrightarrow$ induction to the set $X\setminus A.$ Let $x\in X$ and assume $\overrightarrow{x\,}\subseteq X\setminus A.$ Suppose $x\in A.$  Since $\overrightarrow{x\,}\cap A=\emptyset$ it follows $x$ is a $\longrightarrow$-minimal element of $A$ contrary to hypothesis. Thus, it follows $x\not\in A$ and so $x\in X\setminus A.$ We have shown $$ \forall x\in X, \overrightarrow{x\,}\subseteq X\setminus A \implies x\in X\setminus A $$ By the principle of $\longrightarrow$-induction it follows $X\setminus A=X.$ Therefore, $A$ is empty as desired.

Definition. Let $Y$ be a set and let $h:X\times P(Y)\to Y$ be a function. We call a function $f:X\to Y$ a $\longrightarrow$-recursively defined function if \begin{equation} f(x)=h(x,f(\overrightarrow{x\,})) \end{equation} for all $x\in X.$

Classic examples of recursively defined functions are the factorial function and the Fibonacci function.

Proposition. (Well-Founded Recursion) Let $\longrightarrow$ be a relation on $X.$ Then the following are equivalent. 

$\qquad (1) \longrightarrow$ is well founded on $X$

$\qquad (2) $ for every set $Y,$ there exists $\longrightarrow$-recursively defined functions from $X$ to $Y$

$\qquad (3) \longrightarrow$-recursively defined functions on $X$ are unique.

Proof. This proof is not completely rigorous and not finished.  $(1)\Leftrightarrow(2)$:  Assume $\longrightarrow$ is well-founded on $X.$ Let $Y$ be a set and let $h:X\times P(Y)\to Y.$ Consider functions $g$ defined on subsets of $X$ with values in $Y.$ We say $R(g)$ holds if both conditions are satisfied:

$\qquad (a) $ for all $x\in D(g),$ $\overrightarrow{x\,} \subseteq D(g)$

$\qquad (b) $ for all $x\in D(g),$ $g(x)=h(x,g(\overrightarrow{x\,}))$

Claim: If $R(g_1)$ and $R(g_2)$ hold, then $x\in D(g_1)\cap D(g_2)$ implies $g_1(x)=g_2(x).$  The proof of this claim follows by $\longrightarrow$-induction.  Claim: Let $f=\cup \{g : R(g) \text{ holds}\}.$  Clearly $f$ is a relation with domain included in $X.$  We claim $f$ is a function.  To prove this we have to show that if $g_1,g_2\in \{g : R(g) \text{ holds}\}$ and $x\in D(g_1)\cap D(g_2),$ then $g_1(x)=g_2(x).$  Now $Z=D(g_1)\cap D(g_2)$ is an initial segment of $\longrightarrow$ and $\longrightarrow’=\longrightarrow\cap(Z\times Z)$ is well-founded on $Z.$  It follows by induction on $\longrightarrow’$ that if $x\in Z,$ then $g_1(x)=g_2(x).$  Claim: $f$ is maximal such that $R(f)$ holds. Next we claim that  \begin{equation} \label{fmaxp} x\in D(f) \implies f(x)=g(x,f(\overrightarrow{x\,})). \end{equation} To prove \eqref{fmaxp} assume $x\in D(f).$ Then $x\in D(g)$ for some $g$ such that $R(g)$ holds.  It follows that $$ f(x)=g(x)=h(x,\{g(\overrightarrow{x\,}))=h(x,\{f(\overrightarrow{x\,})\}). $$ Claim: $D(f)=X.$ The proof of this claim follows by $\longrightarrow$-induction.  Let $x$ be such that $\overrightarrow{x\,}\subseteq D(f).$  Since $D(f)$ is an initial segment of $\longrightarrow,$ so is $D(f)\cup \{x\}.$ Let $$ f’=f\cup \{x,g(x,f(\overrightarrow{x\,}))\}. $$ Then $R(f’)$ holds and hence $x\in D(f).$  Conversely, we assume the principle of definition of recursion to hold. We define a rank function  $$ \mathop{rk}(x)=\mathop{sup}_{x\longrightarrow y} \mathop{rk}(y). $$ It then follows that $\longrightarrow$ is well-founded since  $$ x\longrightarrow y \Leftrightarrow \mathop{rk} (y)\in \mathop{rk}(x). $$ Alternatively, we can simplify the proof by assuming $\longrightarrow$ is transitive.  Suppose $A$ is a subset of $X$ that has no minimal element, and define (by recursion applied to the characteristic function of $M$): $$ \textrm{ $x$ belongs to $M$ if and only if for every $x\longrightarrow y,$ if $y$ is in $A$ then $y$ is not in $M.$ } $$ Then for $x$ in $A,$ if $x$ is in $M$ there is a $x\longrightarrow y$ in $A$ (since $A$ has no minimal element) which is not in $M.$ But then there is a $y\longrightarrow z$ in $A$ which is in $M,$ and since $x\longrightarrow z$ we have a contradiction.  So no $x$ in $A$ is in $M.$  But then every $x$ in $A$ is in $M,$ so $A$ must be empty. We thus see that given the defining property of $M,$ the assumption that $A$ has no minimal element, and the transitivity of $\longrightarrow,$ logical manipulation allows us to conclude that $A$ is empty.

$(1)\Leftrightarrow(3)$:  Assume $\longrightarrow$ is well-founded on $X.$ We say that $\phi:Z\to Y$ is an attempt if $Z$ is an initial segment of $X,$ and  $$ \phi(x)=g(x,\{\phi(z):x \longrightarrow z\}) \quad \text{for all $x\in Z.$} $$  If $\phi_1:Z_1\to Y$ and $\phi_2: Z_2\to Y$ are two attempts, they agree on $Z_1\cap Z_2$ namely $ \phi_1|_{Z_1 \cap Z_2}=\phi_2|_{Z_1 \cap Z_2}.$  Because $X_1\cap X_2$ is clearly an initial segment of $X$ and if as attempts that do not agree there is some $x_0$ which is $\longrightarrow$-minimal in $\{x\in Z_1 \cap Z_2 : \phi_1(x)\neq \phi_2(x)\}.$  But in that case we have  $$ \phi_1(x_0) =g(x_0,\{\phi_0(x) : x_0\longrightarrow x\}) =g(x_0, \{\phi_1(x) | x_0\longrightarrow x\}) $$ a contradiction. Conversely, we will show uniqueness implies well-foundedness.  Assume $X$ is nontrivial by having two elements, say $a_0$ and $a_1.$

Descending Chains

The next proposition asserts that every relation $\longrightarrow$ on $X$ is well-founded if and only if every $\longrightarrow$-chain in $X$ is finite. 

Proposition. Let $\longrightarrow$ be a relation on $X.$ Then $\longrightarrow$ is well-founded if and only there are no infinitely descending $\longrightarrow$-chains.

Proof. Assume there exists an infinite descending $\longrightarrow$-chain $B.$  Then $B\subseteq A$ has no $\longrightarrow$-minimal element and thus $\longrightarrow$ is not well-founded.  The result follows by contrapositive.  Conversely, assume for a contradiction that $B$ is a nonempty subset of $X$ with no $\longrightarrow$-minimal element. Then the set $A_a=\{b\in B : b \longrightarrow a\}$ is nonempty for each $a\in B,$ for otherwise $a$ would be an $\longrightarrow$-minimal element of $B.$ The principle of choice, applied to the family $\{A_a\}_{a\in B},$ provides a function  $$ f: B\longrightarrow \bigcup_{a\in B} A_a\subseteq B \text{ with } f(a) \longrightarrow a,  \text{ for all } a\in B. $$  Since $B$ is nonempty, fix $a_0\in B.$  Define the sequence $\{a_n\}_{n\in \mathbb{N}}$ recursively by $a_{n+1}=f(a_n)$ and notice this sequence forms a strictly descending $\longrightarrow$-chain.  This contradicts the assumption that there are no strictly descending $\longrightarrow$-chains in $X.$  Thus every nonempty subset of $B$ must have a $\longrightarrow$-minimal element.

Recursion

Proposition. Let $X$ and $Y$ be sets.  Let $\longrightarrow$ be a well-founded relation on $X,$ and let $g:X\times P(Y)\to Y$ be a function.  Then there exists a unique function $f:X\to Y$ such that $$ f(x)=g(x,\{f(z): x\longrightarrow z\}) $$ for all $x\in X.$ 

Proof. We say that $\phi:Z\to Y$ is an attempt if $Z$ is an initial segment of $X,$ and  $$ \phi(x)=g(x,\{\phi(z):x \longrightarrow z\}) \quad \text{for all $x\in Z.$} $$  If $\phi_1:Z_1\to Y$ and $\phi_2: Z_2\to Y$ are two attempts, they agree on $Z_1\cap Z_2$ namely $ \phi_1|_{Z_1 \cap Z_2}=\phi_2|_{Z_1 \cap Z_2}.$  Because $X_1\cap X_2$ is clearly an initial segment of $X$ and if as attempts that do not agree there is some $x_0$ which is $\longrightarrow$-minimal in $\{x\in Z_1 \cap Z_2 : \phi_1(x)\neq \phi_2(x)\}.$  But in that case we have  $$ \phi_1(x_0) =g(x_0,\{\phi_0(x) : x_0\longrightarrow x\}) =g(x_0, \{\phi_1(x) | x_0\longrightarrow x\}) $$ a contradiction.  Now let $f=\cup \{\phi : \phi \text{ is an attempt}\},$ so $f(x)=\phi(x)$ if there is an attempt $\phi$ with $x\in D(\phi).$ It is clear that $D(f)=\cup \{D(\phi) : \phi \text{ is an attempt} \}$ is an initial segment of $X,$ and that $f$ satisfies $f(x)=g(x,f(z)|x \longrightarrow z)\}$ for all $x\in D(f).$ So all that remains to be shown is that $D(f)=X.$ But if $D(f)\neq X$ there is some $x_0$ that is $\longrightarrow$ minimal in $\{x\in X : x\not\in D(f)\}.$ For such an $x$ define $\overline{f}:D(f)\cup \{x_0\}\to Y$ by $$\overline{f}(x)= \begin{cases} f(x) & \text{ if } x\in D(f) \\ g(x_0,\{f(x) : x_0 \longrightarrow x\}) & \text{ if } x=x_0. \end{cases} $$ Then one would clearly have that $\overline{f}$ is an attempt, but is not a subset of $f.$  Hence a contradiction and so $f:X\to Y$ as desired. 

Antisymmetric and Irreflexive

Definition. Let $X$ be a set.

A relation $R$ on $X$ is called irreflexive if it satisfies the  property $$ \forall a\in X, (a,a)\notin R. $$
A relation $R$ on $X$ is called asymmetric if it satisfies the  property $$ \forall a,b\in X, (a,b)\in R \implies (b,a)\notin R. $$
A relation $R$ on $X$ is called antisymmetric if it satisfies the  property $$ \forall a,b\in X, (a,b)\in R \land (b,a)\in R\implies a=b. $$

A $\longrightarrow$-minimal element need not be smaller than the other elements of $X.$ For example, singleton sets of $X$ all have $\longrightarrow$-minimal elements, namely $a$ is a $\longrightarrow$-minimal element of $\{a\}\subseteq X$ since there does not exist $b\in\{a\}$ such that $a\longrightarrow b$ whenever $\longrightarrow$ is irreflexive. 

Proposition. If $\longrightarrow$ is a well-founded relation on $X,$ then $\longrightarrow$ is irreflexive and antisymmetric; and hence also asymmetric.

Proof. Assume $\longrightarrow$ is a well-founded relation on $X.$ If $a\longrightarrow a,$ then $A=\{a\}\neq\emptyset$ does not have an $\longrightarrow$-minimal element, country to hypothesis.  If $a\longrightarrow b$ and $b\longrightarrow a,$ then $X=\{a,b\}\neq\emptyset$ does not have a $\longrightarrow$-minimal element, contrary to hypothesis.  Thus, if $\longrightarrow$ is well-founded and $a\longrightarrow b,$ then $b\longrightarrow a$ can not hold and so $\longrightarrow$ is asymmetric.  A relation is asymmetric if and only if it is both antisymmetric and irreflexive.

Proposition. If $\longrightarrow$ is a well-founded relation on $X$ and $\longrightarrow’$ is a subrelation of $\longrightarrow,$ then $\longrightarrow’$ is well-founded on $X.$

Proof. Assume $\longrightarrow$ is well-founded on $X$ and let $\longrightarrow’$ be a subrelation of $\longrightarrow.$  Let $A\neq\emptyset$ be a subset of $X.$  Suppose $A$ does not have a $\longrightarrow’$-minimal element.  Thus for all $a\in A$ there exists $b\in A$ that $a\longrightarrow’ b$ holds. Since $\longrightarrow’$ is a subrelation of $\longrightarrow,$ it follows that for all $a\in A$ there exists $b\in A$ such that $a\longrightarrow b.$ Thus $A$ does not have a $\longrightarrow$-minimal element, contrary to hypothesis.

Proposition. Let $f:X\to Y$ be a function. If $\longrightarrow_Y$ is a well-founded relation on $Y,$ then the relation defined on $X$ by $x \longrightarrow_X y \Leftrightarrow f(x)\longrightarrow_Y f(y)$ is well-founded.

Proof. Any infinite descending $\longrightarrow_X$-chain leads to an infinite descending $\longrightarrow_Y$-chain.

Proposition. Let $\longrightarrow$ be a relation on $X.$ Then $\longrightarrow$ is well-founded if and only if $\longrightarrow^+$ is well-founded. 

Proof. Clearly any infinite descending chain $$ x_0 \longrightarrow^+ x_1 \longrightarrow^+ x_2 \longrightarrow^+ \cdots $$ would induce an infinite descending chain with respect to $\longrightarrow.$  This follows easily since $\longrightarrow\subseteq \longrightarrow^+$ and that any subrelation of a well-founded relation is a well-founded relation.  Conversely, in order to show $\longrightarrow^+$ is well-founded, assume  $$ x_1 \longrightarrow^+ x_2 \longrightarrow^+ x_3  \longrightarrow^+\cdots  $$ is an infinite descending $\longrightarrow^+$-chain. Then there exists $i_j\geq 1$ such that $x_j\longrightarrow^{i_j} x_{j+1}$ for all $j\geq 1.$ This implies that $$ x_1 \longrightarrow^{i_1} x_2 \longrightarrow^{i_2} x_3 \longrightarrow^{i_3} \cdots $$  is an infinite $\longrightarrow$-chain. But this contradicts the well-foundedness of $\longrightarrow.$