Mathematical Proof and the Principles of Mathematics/Sets/Classes and foundation

Foundation edit

Much of mathematics can be accomplished without the Axiom of Foundation, but it eliminates numerous pathological cases that would otherwise complicate set theory.

For example, the Axiom of Foundation excludes sets of the form   where  ,  , etc. It also excludes sets that contain themselves.

Later we'll also see that the Axiom of Foundation can be used along with the Axiom Schema of Replacement, which we have not defined yet, to show that sets cannot be nested infinitely deep. All sets can be built up from the bottom.

Axiom (Foundation)

Every non-empty set   contains an element that is disjoint from  .

The Axiom of Foundation is sometimes called the Axiom of Regularity.

One of the immediate consequences of the Axiom of Foundation is the following.

Theorem If   is a set then  .

Proof Consider the set   which is a set by the Axiom of Pair. Now the Axiom of Foundation says that this set must have an element that is disjoint from  . However the only element is   and thus   must be disjoint from  . Since   contains  , this means that   may not contain  .  

Another way to show this result is to prove the following more general result and specialise it for  .

Theorem If   and   are sets then we do not have both   and  .

Proof Consider the set   which is a set by the Axiom of Pair. By the Axiom of Foundation it must contain an element which is disjoint from it. Thus either   or   is disjoint from  .

As   contains both   and  , either   or  .  

Now we will show that there are no sets of the form   with   for all  .

Theorem There does not exist a set   with the property that for all   there exists   such that  .

Proof This follows directly from the Axiom of Foundation, since every element   has an element in common with  , namely the element   that is assumed to exist.  

Exercises edit

  • Let  . Use the Axiom of Foundation to show that  .

Union and intersection · Power sets