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

From Wikibooks, open books for an open world
< Mathematical Proof and the Principles of Mathematics‎ | Sets
Jump to navigation Jump to search

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