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

**of $A$ if there does not exist $b\in A$ such that $a\longrightarrow b.$**

*minimal element*2) If each nonempty subset of $X$ has a $\longrightarrow$-minimal element, then $\longrightarrow$ is called a

**on $X.$**

*well-founded relation*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**. (

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

*Well-Founded Induction*** 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$-

**if \begin{equation} f(x)=h(x,f(\overrightarrow{x\,})) \end{equation} for all $x\in X.$**

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

** Proposition**. (

**) Let $\longrightarrow$ be a relation on $X.$ Then the following are equivalent.**

*Well-Founded Recursion*$\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

**if it satisfies the property $$ \forall a\in X, (a,a)\notin R. $$**

*irreflexive*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

**if it satisfies the property $$ \forall a,b\in X, (a,b)\in R \land (b,a)\in R\implies a=b. $$**

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