Last modified on 21 September 2009, at 20:28

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

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

A\subseteq R[A]\Rightarrow A=\emptyset


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

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

S\circ R\subseteq R\circ S

Let

X=field(R)

and let

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

Then

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 R\cap S^{-1}=\emptyset

Conversely, suppose that for every relation S we have

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


Let A be a set such that

A\subseteq R[A]


Let B=field(R) and let S=BxA. Then

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

It follows that

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


and so

R[A]=\emptyset

and consequently A=\emptyset