Discrete Mathematics/Zermelo-Frankel Axioms

Introduction

Zermelo–Fraenkel set theory, with the axiom of choice, commonly abbreviated ZFC, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics.

ZFC consists of a single primitive notion, that of set, and a single assumption, namely that all mathematical objects are sets. There is a single primitive binary relation, set membership; that set a is a member of set b is written $a\in b$ (usually read "a is an element of b" or "a is in b"). The axioms of ZFC govern how sets behave and interact.

The axioms

1. Axiom of extensionality: Two sets are equal (are the same set) if they have the same elements.

$\forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow x=y].$

The converse of this axiom follows from the substitution property of equality. If the background logic does not include equality "=", x=y may be defined as abbreviating ∀z[z∈x↔z∈y] ∧ ∀z[x∈z↔y∈z], in which case this axiom can be reformulated as $\forall x\forall y[\forall z(z\in x\Leftrightarrow z\in y)\Rightarrow \forall z(x\in z\Leftrightarrow y\in z)]$ — if x and y have the same elements, then they belong to the same sets.

2. Axiom of regularity (also called the Axiom of foundation): Every non-empty set x contains a member y such that x and y are disjoint sets.

$\forall x[\exists y(y\in x)\Rightarrow \exists y(y\in x\land \lnot \exists z(z\in y\land z\in x))].$

3. Axiom schema of specification (also called the axiom schema of separation or of restricted comprehension): If z is a set, and $\phi \!$ is any property which may characterize the elements x of z, then there is a subset y of z containing those x in z which satisfy the property. More formally:

$\forall z\forall w_{1}\ldots w_{n}\exists y\forall x[x\in y\Leftrightarrow (x\in z\land \phi )].$

The axiom of specification can be used to prove the existence of the empty set, denoted $\varnothing$, once the existence of at least one set is established (see above). A common way to do this is to use an instance of specification for a property which all sets do not have. For example, if w is a set which already exists, the empty set can be constructed as

$\varnothing =\{u\in w\mid (u\in u)\land \lnot (u\in u)\}$.

If the background logic includes equality, it is also possible to define the empty set as

$\varnothing =\{u\in w\mid \lnot (u=u)\}$.

Thus the axiom of the empty set is implied by the nine axioms presented here. The axiom of extensionality implies the empty set is unique, if it exists. It is common to make a definitional extension that adds the symbol $\varnothing$ to the language of ZFC.

4. Axiom of pairing: If x and y are sets, then there exists a set which contains x and y as elements.

$\forall x\forall y\exists z(x\in z\land y\in z).$

5. Axiom of union: For any set ${\mathcal {F}}$ there is a set A containing every set that is a member of some member of ${\mathcal {F}}.$

$\forall {\mathcal {F}}\,\exists A\,\forall Y\,\forall x(x\in Y\land Y\in {\mathcal {F}}\Rightarrow x\in A).$

6. Axiom schema of collection: This axiom states that if the domain of a function f is a set, and f(x) is a set for any x in that domain, then the range of f is a subclass of a set, subject to a restriction needed to avoid paradoxes.

7. Axiom of infinity: Let $S(x)\!$ abbreviate $x\cup \{x\}\!$, where $x\!$ is some set. Then there exists a set X such that the empty set $\varnothing$ is a member of X and, whenever a set y is a member of X, then $S(y)\!$ is also a member of X.

$\exists X\left[\varnothing \in X\land \forall y(y\in X\Rightarrow S(y)\in X)\right].$

More colloquially, there exists a set X having infinitely many members.

8. Axiom of power set: Let $z\subseteq x$ abbreviate $\forall q(q\in z\Rightarrow q\in x).$ For any set x, there is a set y which is a superset of the power set of x. The power set of x is the class whose members are every possible subset of x.

$\forall x\exists y\forall z[z\subseteq x\Rightarrow z\in y].$

Alternative forms of axioms 1–8 are often encountered. Some ZF axiomatizations include an axiom asserting that the empty set exists. The axioms of pairing, union, replacement, and power set are often stated so that the members of the set x whose existence is being asserted, are just those sets which the axiom asserts x must contain.

9. Well-ordering theorem: For any set X, there is a binary relation R which well-orders X. This means R is a linear order on X such that every nonempty subset of X has a member which is minimal under R.

$\forall X\exists R(R\;{\mbox{well-orders}}\;X).$

Given axioms 1-8, there are many statements provably equivalent to axiom 9, the best known of which is the axiom of choice (AC), which goes as follows. Let X be a set whose members are all non-empty. Then there exists a function f, called a "choice function," whose domain is X, and whose range is a set, called the "choice set," each member of which is a single member of each member of X. Since the existence of a choice function when X is a finite set is easily proved from axioms 1-8, AC only matters for certain infinite sets. AC is characterized as nonconstructive because it asserts the existence of a choice set but says nothing about how the choice set is to be "constructed." Much research has sought to characterize the definability (or lack thereof) of certain sets whose existence AC asserts.