# Set Theory/Zorn's Lemma and the Axiom of Choice/Well-founded

A binary relation R is well-founded iff for every set A

${\displaystyle A\subseteq R[A]\Rightarrow A=\emptyset }$

Theorem: A binary relation R is well-founded iff for every binary relation S

${\displaystyle S\circ R\subseteq R\circ S\Rightarrow R\cap S^{-1}=\emptyset }$

Proof: Let R be a well founded relation and let S be a relation such that

${\displaystyle S\circ R\subseteq R\circ S}$

Let

${\displaystyle X=field(R)}$

and let

${\displaystyle A=dom(R\cap S^{-1})}$

Then

${\displaystyle A=dom(R\cap S^{-1})=dom((S\circ R)\cap I_{X})\subseteq dom((R\circ S)\cap I_{X})=dom(S\cap R^{-1})=ran(R\cap S^{-1})\subseteq R[A]}$

It follows that A is empty, and therefore ${\displaystyle R\cap S^{-1}=\emptyset }$

Conversely, suppose that for every relation S we have

${\displaystyle S\circ R\subseteq R\circ S\Rightarrow R\cap S^{-1}=\emptyset }$

Let A be a set such that

${\displaystyle A\subseteq R[A]}$

Let ${\displaystyle B=field(R)}$ and let ${\displaystyle S=BxA}$. Then

${\displaystyle S\circ R=R^{-1}[B]\times A\subseteq B\times R[A]=R\circ S}$

It follows that

${\displaystyle R\circ I_{A}=R\cap (A\times B)=R\cap S^{-1}=\emptyset }$

and so

${\displaystyle R[A]=\emptyset }$

and consequently ${\displaystyle A=\emptyset }$