Jump to content

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

From Wikibooks, open books for an open world

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


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


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

Let

and let

Then

It follows that A is empty, and therefore

Conversely, suppose that for every relation S we have


Let A be a set such that


Let and let . Then

It follows that


and so

and consequently