Axiom:Zermelo-Fraenkel Axioms

From ProofWiki
Jump to: navigation, search


The Zermelo-Fraenkel axioms are the most well-known basis for axiomatic set theory.

There is no standard numbering for them, and their exact formulation varies. Certain axioms can in fact be derived from other axioms, so their status as "axioms" can be questioned.

The axioms are as follows:

The Axiom of Extension

Two sets are equal if and only if they contain the same elements:

$\forall x: \left({x \in A \iff x \in B}\right) \iff A = B$

The order of the elements in the sets is immaterial.

The Axiom of the Empty Set

There exists a set that has no elements:

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

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: \left({y \in x \iff y = A \lor y = B}\right)$

Thus it is possible to create a set containing any two sets that you have already created.

Otherwise known as the Axiom of the Unordered Pair.

The Axiom of Subsets

For every set and every condition, there corresponds a set whose elements are exactly the same as those elements of the original set for which the condition is true.

Because we cannot quantify over functions, we need an axiom for every condition we can express. Therefore, this axiom is sometimes called an axiom scheme, as we introduce a lot of similar axioms.

This axiom scheme is formally stated as follows:

For any function of propositional logic $P \left({y}\right)$, we introduce the axiom:

$\forall z: \exists x: \forall y: \left({y \in x \iff \left({y \in z \land P \left({y}\right)}\right)}\right)$

This means that if you have a set, you can create a set that contains some of the elements of that set, where those elements are specified by stipulating that they satisfy some (arbitrary) condition.

The Axiom of Unions

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

$\forall A: \exists x: \forall y: \left({y \in x \iff \exists z: \left({z \in A \land y \in z}\right)}\right)$

The Axiom of Powers

For every set, there exists a set of sets that contains amongst its elements all the subsets of the given set.

$\forall x: \exists y: \left({\forall z: \left({z \in y \iff \left({w \in z \implies w \in x}\right)}\right)}\right)$

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: \left({\left({\exists y: y \in x \land \forall z: \neg \left({z \in y}\right)}\right) \land \forall u: u \in x \implies u^+ \in x}\right)$

The Axiom of Replacement

For any function $f$ and subset $S$ of the domain of $f$, there is a set containing the image $f \left({S}\right)$.

More formally, let us express this as follows:

Let $P \left({y, z}\right)$ be a propositional function, which determines a function.

That is, we have $\forall y: \exists x: \forall z: \left({ P \left({y, z}\right) \iff x = z }\right)$.

Then we state as an axiom:

$\forall w: \exists x: \forall y: \left({y \in w \implies \left({ \forall z: \left({ P \left({y, z}\right) \implies z \in x }\right) }\right) }\right)$

Alternatively, the two above statements may be combined into a single (somewhat unwieldy) expression:

$\left({ \forall y: \exists x: \forall z: \left({ P \left({y, z}\right) \implies x = z }\right) }\right) \implies \forall w: \exists x: \forall y: \left({y \in w \implies \forall z: \left({ P \left({y, z}\right) \implies z \in x }\right) }\right)$

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: \left({ \left({\exists x: x \in S}\right) \implies \exists y \in S: \forall z \in S: \neg \left({z \in y}\right) }\right)$

The antecedent states that $S$ is not empty.

The above axioms taken together as a system, but without the Axiom of Choice below, is called ZF set theory. The validity of the AC is still debated.

The Axiom of Choice

For every set of non-empty sets, we can provide a mechanism for choosing one element of each element of the set.

$\displaystyle \forall s: \left({\varnothing \notin s \implies \exists \left({f: s \to \bigcup s}\right): \forall t \in s: f \left({t}\right) \in t}\right)$

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

The system of the axioms of ZF set theory in combination with the Axiom of Choice is known as ZFC set theory; ZF plus Choice.

Source of Name

This entry was named for Ernst Zermelo and Abraham Fraenkel.