1.

Axioms of Set Theory

Axioms of Zermelo-Fraenkel

1.1. Axiom of Extensionality. If X and Y have the same elements, then

X =Y.

1.2. Axiom of Pairing. For any a and b there exists a set {a, b} that
contains exactly a and b.

1.3. Axiom Schema of Separation. If P is a property (with parameter p),

then for any X and p there exists a set Y = {u ∈ X : P (u, p)} that contains
all those u ∈ X that have property P .


1.4. Axiom of Union. For any X there exists a set Y = X, the union
of all elements of X.

1.5. Axiom of Power Set. For any X there exists a set Y = P (X), the
set of all subsets of X.

1.6. Axiom of Infinity. There exists an infinite set.

1.7. Axiom Schema of Replacement. If a class F is a function, then for

any X there exists a set Y = F (X) = {F (x) : x ∈ X}.

1.8. Axiom of Regularity. Every nonempty set has an ∈-minimal element.

1.9. Axiom of Choice. Every family of nonempty sets has a choice func-
tion.

The theory with axioms 1.1–1.8 is the Zermelo-Fraenkel axiomatic set

theory ZF; ZFC denotes the theory ZF with the Axiom of Choice.

Why Axiomatic Set Theory?

Intuitively, a set is a collection of all elements that satisfy a certain given

property. In other words, we might be tempted to postulate the following
rule of formation for sets.
4 Part I. Basic Set Theory

1.10. Axiom Schema of Comprehension (false). If P is a property,

then there exists a set Y = {x : P (x)}.

This principle, however, is false:

1.11. Russell’s Paradox. Consider the set S whose elements are all those
(and only those) sets that are not members of themselves: S = {X : X ∈
/ X}.
Question: Does S belong to S? If S belongs to S, then S is not a member of
itself, and so S ∈
/ S. On the other hand, if S ∈/ S, then S belongs to S. In
either case, we have a contradiction.

Thus we must conclude that

{X : X ∈
/ X}

is not a set, and we must revise the intuitive notion of a set.

The safe way to eliminate paradoxes of this type is to abandon the Schema
of Comprehension and keep its weak version, the Schema of Separation:

If P is a property, then for any X there exists a set Y = {x ∈ X : P (x)}.

Once we give up the full Comprehension Schema, Russell’s Paradox is no

longer a threat; moreover, it provides this useful information: The set of all
sets does not exist. (Otherwise, apply the Separation Schema to the property
x∈/ x.)
In other words, it is the concept of the set of all sets that is paradoxical,
not the idea of comprehension itself.
Replacing full Comprehension by Separation presents us with a new prob-
lem. The Separation Axioms are too weak to develop set theory with its
usual operations and constructions. Notably, these axioms are not sufficient
to prove that, e.g., the union X ∪ Y of two sets exists, or to define the notion
of a real number.
Thus we have to add further construction principles that postulate the
existence of sets obtained from other sets by means of certain operations.
The axioms of ZFC are generally accepted as a correct formalization of
those principles that mathematicians apply when dealing with sets.

Language of Set Theory, Formulas

The Axiom Schema of Separation as formulated above uses the vague notion
of a property. To give the axioms a precise form, we develop axiomatic set
theory in the framework of the first order predicate calculus. Apart from
the equality predicate =, the language of set theory consists of the binary
predicate ∈, the membership relation.
 1. Axioms of Set Theory 5

The formulas of set theory are built up from the atomic formulas

x ∈ y, x=y

by means of connectives

ϕ ∧ ψ, ϕ ∨ ψ, ¬ϕ, ϕ → ψ, ϕ↔ψ

(conjunction, disjunction, negation, implication, equivalence), and quantifiers

∀x ϕ, ∃x ϕ.

In practice, we shall use in formulas other symbols, namely defined pred-

icates, operations, and constants, and even use formulas informally; but it
will be tacitly understood that each such formula can be written in a form
that only involves ∈ and = as nonlogical symbols.
Concerning formulas with free variables, we adopt the notational conven-
tion that all free variables of a formula

ϕ(u1 , . . . , un )

are among u1 , . . . , un (possibly some ui are not free, or even do not occur,
in ϕ). A formula without free variables is called a sentence.

Classes
Although we work in ZFC which, unlike alternative axiomatic set theories,
has only one type of object, namely sets, we introduce the informal notion
of a class. We do this for practical reasons: It is easier to manipulate classes
than formulas.
If ϕ(x, p1 , . . . , pn ) is a formula, we call

C = {x : ϕ(x, p1 , . . . , pn )}

a class. Members of the class C are all those sets x that satisfy ϕ(x, p1 , . . . , pn ):

x∈C if and only if ϕ(x, p1 , . . . , pn ).

We say that C is definable from p1 , . . . , pn ; if ϕ(x) has no parameters pi

then the class C is definable.
Two classes are considered equal if they have the same elements: If

C = {x : ϕ(x, p1 , . . . , pn )}, D = {x : ψ(x, q1 , . . . , qm )},

then C = D if and only if for all x

ϕ(x, p1 , . . . , pn ) ↔ ψ(x, q1 , . . . , qm ).
6 Part I. Basic Set Theory

The universal class, or universe, is the class of all sets:

V = {x : x = x}.

We define inclusion of classes (C is a subclass of D)

C ⊂ D if and only if for all x, x ∈ C implies x ∈ D,

and the following operations on classes:

C ∩ D = {x : x ∈ C and x ∈ D},
C ∪ D = {x : x ∈ C or x ∈ D},
C − D = {x : x ∈ C and x ∈/ D},



C = {x : x ∈ S for some S ∈ C} = {S : S ∈ C}.

Every set can be considered a class. If S is a set, consider the formula x ∈ S

and the class
{x : x ∈ S}.
That the set S is uniquely determined by its elements follows from the Axiom
of Extensionality.
A class that is not a set is a proper class.

Extensionality

If X and Y have the same elements, then X = Y :

∀u (u ∈ X ↔ u ∈ Y ) → X = Y.

The converse, namely, if X = Y then u ∈ X ↔ u ∈ Y , is an axiom of

predicate calculus. Thus we have

X=Y if and only if ∀u (u ∈ X ↔ u ∈ Y ).

The axiom expresses the basic idea of a set: A set is determined by its ele-
ments.

Pairing

For any a and b there exists a set {a, b} that contains exactly a and b:

∀a ∀b ∃c ∀x (x ∈ c ↔ x = a ∨ x = b).
 1. Axioms of Set Theory 7

By Extensionality, the set c is unique, and we can define the pair

{a, b} = the unique c such that ∀x (x ∈ c ↔ x = a ∨ x = b).

The singleton {a} is the set

{a} = {a, a}.

Since {a, b} = {b, a}, we further define an ordered pair

(a, b)

so as to satisfy the following condition:

(1.1) (a, b) = (c, d) if and only if a = c and b = d.

For the formal definition of an ordered pair, we take

(a, b) = {{a}, {a, b}}.

We leave the verification of (1.1) to the reader (Exercise 1.1).

We further define ordered triples, quadruples, etc., as follows:

(a, b, c) = ((a, b), c),

(a, b, c, d) = ((a, b, c), d),
..
.
(a1 , . . . , an+1 ) = ((a1 , . . . , an ), an+1 ).

It follows that two ordered n-tuples (a1 , . . . , an ) and (b1 , . . . , bn ) are equal if
and only if a1 = b1 , . . . , an = bn .

Separation Schema

Let ϕ(u, p) be a formula. For any X and p, there exists a set Y = {u ∈ X :

ϕ(u, p)}:

(1.2) ∀X ∀p ∃Y ∀u (u ∈ Y ↔ u ∈ X ∧ ϕ(u, p)).

For each formula ϕ(u, p), the formula (1.2) is an Axiom (of Separation).
The set Y in (1.2) is unique by Extensionality.
Note that a more general version of Separation Axioms can be proved
using ordered n-tuples: Let ψ(u, p1 , . . . , pn ) be a formula. Then

(1.3) ∀X ∀p1 . . . ∀pn ∃Y ∀u (u ∈ Y ↔ u ∈ X ∧ ψ(u, p1 , . . . , pn )).

8 Part I. Basic Set Theory

Simply let ϕ(u, p) be the formula

∃p1 , . . . ∃pn (p = (p1 , . . . , pn ) and ψ(u, p1 , . . . , pn ))

and then, given X and p1 , . . . , pn , let

Y = {u ∈ X : ϕ(u, (p1 , . . . , pn ))}.

We can give the Separation Axioms the following form: Consider the class
C = {u : ϕ(u, p1 , . . . , pn )}; then by (1.3)

∀X ∃Y (C ∩ X = Y ).

Thus the intersection of a class C with any set is a set; or, we can say even
more informally
a subclass of a set is a set.

One consequence of the Separation Axioms is that the intersection and the
difference of two sets is a set, and so we can define the operations

X ∩ Y = {u ∈ X : u ∈ Y } and X − Y = {u ∈ X : u ∈
/ Y }.

Similarly, it follows that the empty class

∅ = {u : u = u}

is a set—the empty set ; this, of course, only under the assumption that at
least one set X exists (because ∅ ⊂ X):

(1.4) ∃X (X = X).

We have not included (1.4) among the axioms, because it follows from the
Axiom of Infinity.
Two sets X, Y are called disjoint if X ∩ Y = ∅.
If C is a nonempty class of sets, we let
 
C= {X : X ∈ C} = {u : u ∈ X for every X ∈ C}.
 
Note that C is a set (it is a subset of any X ∈ C). Also, X ∩ Y = {X, Y }.
Another consequence of the Separation Axioms is that the universal
class V is a proper class; otherwise,

S = {x ∈ V : x ∈
/ x}

would be a set.
 1. Axioms of Set Theory 9

Union


For any X there exists a set Y = X:

(1.5) ∀X ∃Y ∀u (u ∈ Y ↔ ∃z (z ∈ X ∧ u ∈ z)).

Let us introduce the abbreviations

(∃z ∈ X) ϕ for ∃z (z ∈ X ∧ ϕ),

and
(∀z ∈ X) ϕ for ∀z (z ∈ X → ϕ).

By (1.5), for every X there is a unique set

Y = {u : (∃z ∈ X) u ∈ z} = {z : z ∈ X} = X,

the union of X.
Now we can define


X ∪ Y = {X, Y }, X ∪ Y ∪ Z = (X ∪ Y ) ∪ Z, etc.,

and also
{a, b, c} = {a, b} ∪ {c},
and in general
{a1 , . . . , an } = {a1 } ∪ . . . ∪ {an }.
We also let
X Y = (X − Y ) ∪ (Y − X),
the symmetric difference of X and Y .

Power Set
For any X there exists a set Y = P (X):

∀X ∃Y ∀u (u ∈ Y ↔ u ⊂ X).

A set U is a subset of X, U ⊂ X, if

∀z (z ∈ U → z ∈ X).

If U ⊂ X and U = X, then U is a proper subset of X.

The set of all subsets of X,

P (X) = {u : u ⊂ X},

is called the power set of X.

10 Part I. Basic Set Theory

Using the Power Set Axiom we can define other basic notions of set theory.
The product of X and Y is the set of all pairs (x, y) such that x ∈ X and
y ∈ Y:

(1.6) X × Y = {(x, y) : x ∈ X and y ∈ Y }.

The notation {(x, y) : . . . } in (1.6) is justified because

{(x, y) : ϕ(x, y)} = {u : ∃x ∃y (u = (x, y) and ϕ(x, y))}.

The product X × Y is a set because

X × Y ⊂ P P (X ∪ Y ).

Further, we define
X × Y × Z = (X × Y ) × Z,
and in general

X1 × . . . × Xn+1 = (X1 × . . . × Xn ) × Xn+1 .

Thus

X1 × . . . × Xn = {(x1 , . . . , xn ) : x1 ∈ X1 ∧ . . . ∧ xn ∈ Xn }.

We also let
Xn = X × . . . × X .
  
n times
An n-ary relation R is a set of n-tuples. R is a relation on X if R ⊂ X n .
It is customary to write R(x1 , . . . , xn ) instead of

(x1 , . . . , xn ) ∈ R,

and in case that R is binary, then we also use

xRy

for (x, y) ∈ R.
If R is a binary relation, then the domain of R is the set

dom(R) = {u : ∃v (u, v) ∈ R},

and the range of R is the set

ran(R) = {v : ∃u (u, v) ∈ R}.

Note that dom(R) and ran(R) are sets because

dom(R) ⊂ R, ran(R) ⊂ R.

The field of a relation R is the set field(R) = dom(R) ∪ ran(R).

 1. Axioms of Set Theory 11

In general, we call a class R an n-ary relation if all its elements are n-

tuples; in other words, if
R ⊂ V n = the class of all n-tuples,
where C n (and C × D) is defined in the obvious way.
A binary relation f is a function if (x, y) ∈ f and (x, z) ∈ f implies y = z.
The unique y such that (x, y) ∈ f is the value of f at x; we use the standard
notation
y = f (x)
or its variations f : x → y, y = fx , etc. for (x, y) ∈ f .
f is a function on X if X = dom(f ). If dom(f ) = X n , then f is an n-ary
function on X.
f is a function from X to Y ,
f : X → Y,
if dom(f ) = X and ran(f ) ⊂ Y . The set of all functions from X to Y is
denoted by Y X . Note that Y X is a set:
Y X ⊂ P (X × Y ).
If Y = ran(f ), then f is a function onto Y . A function f is one-to-one if
f (x) = f (y) implies x = y.
An n-ary operation on X is a function f : X n → X.
The restriction of a function f to a set X (usually a subset of dom(f )) is
the function
f X = {(x, y) ∈ f : x ∈ X}.
A function g is an extension of a function f if g ⊃ f , i.e., dom(f ) ⊂ dom(g)
and g(x) = f (x) for all x ∈ dom(f ).
If f and g are functions such that ran(g) ⊂ dom(f ), then the composition
of f and g is the function f ◦ g with domain dom(f ◦ g) = dom(g) such that
(f ◦ g)(x) = f (g(x)) for all x ∈ dom(g).
We denote the image of X by f either f “X or f (X):
f “X = f (X) = {y : (∃x ∈ X) y = f (x)},
and the inverse image by
f−1 (X) = {x : f (x) ∈ X}.
If f is one-to-one, then f −1 denotes the inverse of f :
f −1 (x) = y if and only if x = f (y).
The previous definitions can also be applied to classes instead of sets.
A class F is a function if it is a relation such that (x, y) ∈ F and (x, z) ∈ F
12 Part I. Basic Set Theory

implies y = z. For example, F “C or F (C) denotes the image of the class C

by the function F .
It should be noted that a function is often called a mapping or a corre-
spondence (and similarly, a set is called a family or a collection).
An equivalence relation on a set X is a binary relation ≡ which is reflexive,
symmetric, and transitive: For all x, y, z ∈ X,

x ≡ x,
x ≡ y implies y ≡ x,
if x ≡ y and y ≡ z then x ≡ z.
A family of sets is disjoint if any two of its members are disjoint. A par-
tition of a set X is a disjoint family P of nonempty sets such that


X = {Y : Y ∈ P }.
Let ≡ be an equivalence relation on X. For every x ∈ X, let
[x] = {y ∈ X : y ≡ x}
(the equivalence class of x). The set
X/≡ = {[x] : x ∈ X}
is a partition of X (the quotient of X by ≡). Conversely, each partition P
of X defines an equivalence relation on X:
x≡y if and only if (∃Y ∈ P )(x ∈ Y and y ∈ Y ).
If an equivalence relation is a class, then its equivalence classes may be
proper classes. In Chapter 6 we shall introduce a trick that enables us to
handle equivalence classes as if they were sets.

Infinity
There exists an infinite set.
To give a precise formulation of the Axiom of Infinity, we have to define
first the notion of finiteness. The most obvious definition of finiteness uses the
notion of a natural number, which is as yet undefined. We shall define natural
numbers (as finite ordinals) in Chapter 2 and give only a quick treatment of
natural numbers and finiteness in the exercises below.
In principle, it is possible to give a definition of finiteness that does not
mention numbers, but such definitions necessarily look artificial.
We therefore formulate the Axiom of Infinity differently:
∃S (∅ ∈ S ∧ (∀x ∈ S)x ∪ {x} ∈ S).
We call a set S with the above property inductive. Thus we have:
 1. Axioms of Set Theory 13

Axiom of Infinity. There exists an inductive set.

The axiom provides for the existence of infinite sets. In Chapter 2 we

show that an inductive set is infinite (and that an inductive set exists if there
exists an infinite set).
We shall introduce natural numbers and finite sets in Chapter 2, as a part
of the introduction of ordinal numbers. In Exercises 1.3–1.9 we show an al-
ternative approach.

Replacement Schema

If a class F is a function, then for every set X, F (X) is a set.

For each formula ϕ(x, y, p), the formula (1.7) is an Axiom (of Replace-
ment):

(1.7) ∀x ∀y ∀z (ϕ(x, y, p) ∧ ϕ(x, z, p) → y = z)

→ ∀X ∃Y ∀y (y ∈ Y ↔ (∃x ∈ X) ϕ(x, y, p)).

As in the case of Separation Axioms, we can prove the version of Replace-

ment Axioms with several parameters: Replace p by p1 , . . . , pn .
If F = {(x, y) : ϕ(x, y, p)}, then the premise of (1.7) says that F is
a function, and we get the formulation above. We can also formulate the
axioms in the following ways:
If a class F is a function and dom(F ) is a set, then ran(F ) is a set.
If a class F is a function, then ∀X ∃f (F X = f ).
The remaining two axioms, Choice and Regularity, will by introduced in
Chapters 5 and 6.

Exercises
1.1. Verify (1.1).

1.2. There is no set X such that P (X) ⊂ X.

Let T
N = {X : X is inductive}.
N is the smallest inductive set. Let us use the following notation:

0 = ∅, 1 = {0}, 2 = {0, 1}, 3 = {0, 1, 2}, ....

If n ∈ N , let n + 1 = n ∪ {n}. Let us define < (on N ) by n < m if and only if

n ∈ m.
A set T is transitive if x ∈ T implies x ⊂ T .
14 Part I. Basic Set Theory

1.3. If X is inductive, then the set {x ∈ X : x ⊂ X} is inductive. Hence N is

transitive, and for each n, n = {m ∈ N : m < n}.

1.4. If X is inductive, then the set {x ∈ X : x is transitive} is inductive. Hence

every n ∈ N is transitive.

1.5. If X is inductive, then the set {x ∈ X : x is transitive and x ∈

/ x} is inductive.
Hence n ∈/ n and n = n + 1 for each n ∈ N .

1.6. If X is inductive, then {x ∈ X : x is transitive and every nonempty z ⊂ x has

an ∈-minimal element} is inductive (t is ∈-minimal in z if there is no s ∈ z such
that s ∈ t).

1.7. Every nonempty X ⊂ N has an ∈-minimal element.

[Pick n ∈ X and look at X ∩ n.]

1.8. If X is inductive then so is {x ∈ X : x = ∅ or x = y ∪ {y} for some y}. Hence

 0 is m + 1 for some m.
each n =

1.9 (Induction). Let A be a subset of N such that 0 ∈ A, and if n ∈ A then

n + 1 ∈ A. Then A = N .

A set X has n elements (where n ∈ N ) if there is a one-to-one mapping of n

onto X. A set is finite if it has n elements for some n ∈ N , and infinite if it is not
finite.
A set S is T-finite if every nonempty X ⊂ P (S) has a ⊂-maximal element, i.e.,
u ∈ X such that there is no v ∈ X with u ⊂ v and u = v. S is T-infinite if it is not
T-finite. (T is for Tarski.)

1.10. Each n ∈ N is T-finite.

1.11. N is T-infinite; the set N ⊂ P (N ) has no ⊂-maximal element.

1.12. Every finite set is T-finite.

1.13. Every infinite set is T-infinite.

[If S is infinite, consider X = {u ⊂ S : u is finite}.]

1.14. The Separation Axioms follow from the Replacement Schema.

[Given ϕ, let F = {(x, x) : ϕ(x)}. Then {x ∈ X : ϕ(x)} = F (X), for every X.]

1.15. Instead of Union, Power Set, and Replacement Axioms consider the following
weaker versions:
S
(1.8) ∀X ∃Y X ⊂Y, i.e., ∀X ∃Y (∀x ∈ X)(∀u ∈ x) u ∈ Y ,
(1.9) ∀X ∃Y P (X) ⊂ Y , i.e., ∀X ∃Y ∀u (u ⊂ X → u ∈ Y ),
(1.10) If a class F is a function, then ∀X ∃Y F (X) ⊂ Y .

Then axioms 1.4, 1.5, and 1.7 can be proved from (1.8), (1.9), and (1.10), using the
Separation Schema (1.3).
 1. Axioms of Set Theory 15

Historical Notes
Set theory was invented by Georg Cantor. The first attempt to consider infinite sets
is attributed to Bolzano (who introduced the term Menge). It was however Cantor
who realized the significance of one-to-one functions between sets and introduced
the notion of cardinality of a set. Cantor originated the theory of cardinal and
ordinal numbers as well as the investigations of the topology of the real line. Much of
the development in the first four chapters follows Cantor’s work. The main reference
to Cantor’s work is his collected works, Cantor [1932]. Another source of references
to the early research in set theory is Hausdorff’s book [1914].
Cantor started his investigations in [1874], where he proved that the set of
all real numbers is uncountable, while the set of all algebraic reals is countable.
In [1878] he gave the first formulation of the celebrated Continuum Hypothesis.
The axioms for set theory (except Replacement and Regularity) are due to
Zermelo [1908]. The Replacement Schema is due to Fraenkel [1922a] and Skolem
(see [1970], pp. 137–152).
Exercises 1.12 and 1.13: Tarski [1925a].