Well-Founded Relations (and Well-Founded Induction)

Share on tumblr
Share on facebook
Share on linkedin
Share on twitter
Share on stumbleupon
Share on email
Share on pinterest

Well-Founded Relations (and Well-Founded Induction)

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.$

0/5 (0 Reviews)

Reply