Maths - Sets - ZF / ZFC

ZF is a rigorous axomatic foundation for set theory based on work by Ernst Zermelo and extended by Abraham Fraenkel. Like NBG it is intended to eliminate potential paradoxes, in set theory, pointed out by Bertrand Russel.

In this theory all sets are built up from certain simple ones by operations like:

These operations can only be applied to sets that have already been constructed and the result is always a set.

The Comprehension Principle can now only be used for an already defined set. (see separation principle).

ZF can be considered as a subsystem of NBG.

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 an abbreviation for the following formula (Hatcher 1982, p. 138, def. 1):

\forall z [ z \in x \Leftrightarrow z \in y] \land \forall z [x \in z \Leftrightarrow y \in z].

In this case, the axiom of extensionality 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) ],

which says that if x and y have the same elements, then they belong to the same sets (Fraenkel et al. 1973).

2. Axiom of regularity (also called the Axiom of foundation) Main article: Axiom of regularity

Every non-empty set x contains a member y such that x and y are disjoint sets.

\forall x [ \exists a ( a \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) Main article: Axiom schema of specification

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. The "restriction" to z is necessary to avoid Russell's paradox and its variants. More formally, let \phi\! be any formula in the language of ZFC with free variables among x,z,w_1,\ldots,w_n\!. So y is not free in \phi\!. Then:

\forall z \forall w_1 \forall w_2\ldots \forall w_n \exists y \forall x [x \in y \Leftrightarrow ( x \in z \land \phi )].

In some other axiomatizations of ZF, this axiom is redundant in that it follows from the axiom schema of replacement.

The set constructed by the axiom of specification is often denoted using set builder notation. Given a set z and a formula \phi(x) with one free variable x, the set of all x in z that satisfy \phi is denoted

\{x \in z : \phi(x)\}.

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 (does not depend on w). 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 \exist z (x \in z \land y \in z).

The axiom schema of specification must be used to reduce this to a set with exactly these two elements. This axiom is part of Z, but is redundant in ZF because it follows from the axiom schema of replacement, if we are given a set with at least two elements. The existence of a set with at least two elements is assured by either the axiom of infinity, or by the axiom schema of specification and the axiom of the power set applied twice to any set.

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 replacement

Let \phi \! be any formula in the language of ZFC whose free variables are among x,y,A,w_1,\ldots,w_n \!, so that in particular B is not free in \phi \!. Then:

\forall A\forall w_1 \forall w_2\ldots \forall w_n \bigl[ \forall x ( x\in A \Rightarrow \exists!y\,\phi ) \Rightarrow \exists B \ \forall x \bigl(x\in A \Rightarrow \exists y (y\in B \land \phi)\bigr)\bigr].

Less formally, this axiom states that if the domain of a definable function f (represented here by the relation \phi \!) is a set (denoted here by A), and f(x) is a set for any x in that domain, then the range of f is a subclass of a set (where the set is denoted here by B). The form stated here, in which B may be larger than strictly necessary, is sometimes called the axiom schema of collection.

7. Axiom of infinity

Let S(w)\! abbreviate w \cup \{w\} \!, where w \! is some set (We can see that \{w\} is a valid set by applying the Axiom of Pairing with x=y=w \! so that the set z\! is \{w\} \!). 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.

\exist X \left [\varnothing \in X \and \forall y (y \in X \Rightarrow S(y) \in X)\right ].

More colloquially, there exists a set X having infinitely many members. The minimal set X satisfying the axiom of infinity is the von Neumann ordinal ω, which can also be thought of as the set of natural numbers \mathbb{N}.

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 all of the subsets of x.

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

Axioms 1–8 define ZF. Alternative forms of these axioms are often encountered, some of which are listed in Jech (2003). 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.

The following axiom is added to turn ZF into ZFC:

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 from X to the union of the members of X, called a "choice function", such that for all Y ∈ X one has f(Y) ∈ Y. 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.


metadata block
see also:

http://www.mathreference.com/

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Modern Graph Theory (Graduate Texts in Mathematics, 184)

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2023 Martin John Baker - All rights reserved - privacy policy.