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

Foundation

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 $S=\{a_{1},a_{2},a_{3},\ldots \}$ where $a_{2}\in a_{1}$, $a_{3}\in a_{2}$, 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 $S$ contains an element that is disjoint from $S$.

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 $S$ is a set then $S\notin S$.

Proof Consider the set $\{S\}$ 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 $\{S\}$. However the only element is $S$ and thus $S$ must be disjoint from $\{S\}$. Since $\{S\}$ contains $S$, this means that $S$ may not contain $S$. $\square$

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

Theorem If $X$ and $Y$ are sets then we do not have both $X\in Y$ and $Y\in X$.

Proof Consider the set $\{X,Y\}$ 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 $X$ or $Y$ is disjoint from $\{X,Y\}$.

As $\{X,Y\}$ contains both $X$ and $Y$, either $Y\notin X$ or $X\notin Y$. $\square$

Now we will show that there are no sets of the form $S=\{a_{1},a_{2},\ldots \}$ with $a_{i+1}\in a_{i}$ for all $i$.

Theorem There does not exist a set $S$ with the property that for all $x\in S$ there exists $y\in S$ such that $y\in x$.

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

Exercises

• Let $T=\{S,\{S\}\}$. Use the Axiom of Foundation to show that $S\neq T$.