# well-foundedness and axiom of foundation

Recall that a relation $R$ on a class $C$ is well-founded if

1. 1.

For any $x\in C$, the collection $\{y\in C\mid yRx\}$ is a set, and

2. 2.

for any non-empty $B\subseteq C$, there is an element $z\in B$ such that if $yRz$, then $y\notin B$.

$z$ is called an $R$-minimal element of $B$. It is clear that the membership relation $\in$ in the class of all sets satisfies the first condition above.

###### Proof.

Suppose $\in$ is well-founded and $A$ a non-empty set. We want to find $x\in A$ such that $x\cap A=\varnothing$. Since $\in$ is well-founded, there is a $\in$-minimal set $x$ such that $x\in A$. Since no set $y$ such that $y\in x$ and $y\in A$ (otherwise $x$ would not be $\in$-minimal ), we have that $x\cap A=\varnothing$.

Conversely, suppose that AF is true. Let $A$ be any non-empty set. We want to find a $\in$-minimal element in $A$. Let $x\in A$ such that $x\cap A=\varnothing$. Then $x$ is $\in$-minimal in $A$, for otherwise there is $y\in A$ such that $y\in x$, which implies $y\in x\cap A=\varnothing$, a contradiction . ∎

Title well-foundedness and axiom of foundation WellfoundednessAndAxiomOfFoundation 2013-03-22 17:25:34 2013-03-22 17:25:34 CWoo (3771) CWoo (3771) 6 CWoo (3771) Theorem msc 03E30
{"ft_lang_label":"__label__en","ft_lang_prob":0.8884463,"math_prob":0.9999192,"size":1289,"snap":"2021-04-2021-17","text_gpt3_token_len":345,"char_repetition_ratio":0.14396887,"word_repetition_ratio":0.017857144,"special_character_ratio":0.28006205,"punctuation_ratio":0.13307984,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99997926,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18],"im_url_duplicate_count":[null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-04-17T14:23:01Z\",\"WARC-Record-ID\":\"<urn:uuid:21059677-27c7-4696-89bc-b5619a2389d4>\",\"Content-Length\":\"15753\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:d465bce2-5c01-4fa6-9391-a5583c094d73>\",\"WARC-Concurrent-To\":\"<urn:uuid:aa5a854c-e64a-4e38-bea2-9a7b95957079>\",\"WARC-IP-Address\":\"129.97.206.129\",\"WARC-Target-URI\":\"https://planetmath.org/WellfoundednessAndAxiomOfFoundation\",\"WARC-Payload-Digest\":\"sha1:FN76K5RCGO2DSTPWBR5JBRB4O3NMFYKK\",\"WARC-Block-Digest\":\"sha1:LOY7OYGZG4MZNDJCFIMLEZSPZYY4SJEK\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-17/CC-MAIN-2021-17_segments_1618038460648.48_warc_CC-MAIN-20210417132441-20210417162441-00292.warc.gz\"}"}