From ProofWiki
Jump to navigation Jump to search


Zermelo-Fraenkel Set Theory with the Axiom of Choice is a system of axiomatic set theory upon which the whole of (at least conventional) mathematics can be based.

Its basis consists of a system of Aristotelian logic, appropriately axiomatised, together with the Zermelo-Fraenkel axioms of Set Theory and the (controversial) Axiom of Choice.

These are as follows:

The Axiom of Extension

Let $A$ and $B$ be sets.

The axiom of extension states that $A$ and $B$ are equal if and only if they contain the same elements.

That is, if and only if:

every element of $A$ is also an element of $B$


every element of $B$ is also an element of $A$.

This can be formulated as follows:

$\forall x: \paren {x \in A \iff x \in B} \iff A = B$

The Axiom of the Empty Set

Formulation 1

There exists a set that has no elements:

$\exists x: \forall y: \paren {\neg \paren {y \in x} }$

Formulation 2

There exists a set for which membership leads to a contradiction:

$\exists x: \forall y \in x: y \ne y$

The Axiom of Pairing

For any two sets, there exists a set to which only those two sets are elements:

$\forall A: \forall B: \exists x: \forall y: \paren {y \in x \iff y = A \lor y = B}$

Thus it is possible to create a set that contains as elements any two sets that have already been created.

The Axiom of Specification

For any function of propositional logic $\map P y$, we introduce the axiom:

$\forall z: \exists x: \forall y: \paren {y \in x \iff \paren {y \in z \land \map P y} }$

where each of $x$, $y$ and $z$ range over arbitrary sets.

The Axiom of Unions

For every set of sets $A$, there exists a set $x$ (the union set) that contains all and only those elements that belong to at least one of the sets in the $A$:

$\forall A: \exists x: \forall y: \paren {y \in x \iff \exists z: \paren {z \in A \land y \in z} }$

The Axiom of Powers

For every set, there exists a set of sets whose elements are all the subsets of the given set.

$\forall x: \exists y: \paren {\forall z: \paren {z \in y \iff \paren {w \in z \implies w \in x} } }$

The Axiom of Infinity

There exists a set containing:

$(1): \quad$ a set with no elements
$(2): \quad$ the successor of each of its elements.

That is:

$\exists x: \paren {\paren {\exists y: y \in x \land \forall z: \neg \paren {z \in y} } \land \forall u: u \in x \implies u^+ \in x}$

The Axiom of Replacement

For any function $f$ and subset $S$ of the domain of $f$, there is a set containing the image $\map f S$.

More formally, let us express this as follows:

Let $\map P {y, z}$ be a propositional function, which determines a function.

That is, we have:

$\forall y: \exists x: \forall z: \paren {\map P {y, z} \iff x = z}$.

Then we state as an axiom:

$\forall w: \exists x: \forall y: \paren {y \in w \implies \paren {\forall z: \paren {\map P {y, z} \implies z \in x} } }$

The Axiom of Foundation

For all non-empty sets, there is an element of the set that shares no element with the set.

That is:

$\forall S: \paren {\paren {\exists x: x \in S} \implies \exists y \in S: \forall z \in S: \neg \paren {z \in y} }$

The antecedent states that $S$ is not empty.

The Axiom of Choice

For every set of non-empty sets, it is possible to provide a mechanism for choosing one element of each element of the set.

$\displaystyle \forall s: \paren {\O \notin s \implies \exists \paren {f: s \to \bigcup s}: \forall t \in s: \map f t \in t}$

That is, one can always create a choice function for selecting one element from each element of the set.

Also known as

Zermelo-Fraenkel Set Theory with the Axiom of Choice is popularly seen abbreviated as ZFC.

Also see

Source of Name

This entry was named for Ernst Friedrich Ferdinand Zermelo and Abraham Halevi Fraenkel.