§ 1. Preliminary information, notation.
Sets are denoted by: A, B, . . . (capital letters);
elements of sets are denoted by: a, b, . . . (lowercase letters);
the element a of the set A is denoted by: a ∈ A;
the subset B of the set A is denoted by: B ⊂ A;
specifying a subset B of the set A by the condition ϕ(X):
B = {x ∈ A : ϕ(X)}
(or B = {x : ϕ(X)}, if it is clear which set A is being discussed);
the empty set is denoted by: ∅ (convention: the empty set contains no elements);
sets whose elements are themselves sets are called families of sets and are denoted by: A, B, . . . (calligraphic letters).
Intersection of sets A and B: A ∩ B = {x : x ∈ A and x ∈ B};
sets A and B are disjoint if A ∩ B = ∅;
union of sets A and B: A ∪ B = {x : x ∈ A or x ∈ B};
intersection of a nonempty family of sets A:
union of a nonempty family of sets A:
Distributive laws:
Difference of sets A and B: A \ B = {x : x ∈ A and x 6∈ B}.
De Morgan's laws:
§ 2. Mappings of sets.
An ordered pair (x, y) is the set {{x}, {x, y}}, if x 6= y, and the set {x}, if
x = y. The Cartesian product of sets X and Y :
X × Y = {(x, y) : x ∈ X, y ∈ Y }.
Every subset of the product X × Y is a certain relation. A relation f ⊂ X × Y
is called a mapping of the set X into the set Y if
1) for every x ∈ X there exists (x, y) ∈ f, and
2) from (x, y) ∈ f and (x, y0
) ∈ f it follows that y = y0.
Notation f : X → Y .
For x ∈ X the unique y ∈ Y for which (x, y) ∈ f is called the value of f at the point x and
is denoted f(x). The image f(A) of a set A ⊂ X under the mapping f is the set f(A) = {y ∈ Y : y = f(x) for some x ∈ A}.
The preimage f−1(B) of a set B ⊂ Y under the mapping f is the set f−1 (B) = {x ∈ X : f(x) ∈ B}.
For a mapping f : X → Y and a subset M ⊂ X, the mapping f, considered only
on M, is called the restriction of the mapping f to M and is denoted f|M. We obtain a mapping f|M : M → Y , where (f|M)(x) = f(x).
For mappings f : X → Y and g : Y → Z the equality (g ◦ f)(x) = g(f(x)), x ∈ X defines the composition of the mappings f and g: (g ◦ f) : X → Z.
A mapping f : X → Y is called injective if for any pair of points x1, x2 ∈ X, from f(x1) = f(x2) it follows that x1 = x2.
A mapping f : X → Y is called surjective, or a mapping “onto,” if f(X) = Y .
A mapping f : X → Y that is both injective and surjective is called bijective or one-to-one.
A mapping f : X → Y is called invertible if there exists a mapping g : Y → X such that g ◦ f = idX and f ◦ g = idY , where idX (respectively idY ) is the identity mapping of the set X (respectively Y ) onto itself. The mapping g is called the inverse of f, is uniquely determined by the mapping f, and is denoted f−1
.
For a family of sets A, a surjective mapping f of the set J onto A is called an indexing mapping. A family A with an indexing mapping f : J → A is called an indexed family of sets. Notation: A = {Aα : α ∈ J}. Any family
of sets A with the identity indexing mapping id : A → A is an indexed family A = {AA : A ∈ A}. The union and intersection of indexed families are denoted:
respectively.
If J = {1, . . . , k} or J = N (N being the natural numbers), then the unions and intersections of
indexed families are denoted:
.
The family of all subsets of a set A is denoted 2
A. The justification for this notation is as follows. For any element B ∈ 2
A consider the mapping fB : A → 2 = {0, 1} (the characteristic function of the subset B),
The elements of 2A are in one-to-one correspondence with characteristic functions.
§ 3. Equivalence relation.
A relation R on a set X, i.e., a subset of the product X × X, is called an equivalence relation if R satisfies the following properties (x ∼ y denotes that
(x, y) ∈ R):
1) x ∼ x for every x ∈ X (reflexivity),
2) x ∼ y ⇒ y ∼ x (symmetry),
3) x ∼ y, y ∼ z ⇒ x ∼ z (transitivity).
Every equivalence relation R on a set X defines a partition of X into pairwise
disjoint sets (the equivalence classes of the relation R): x, y are in the same equivalence class if and only if x ∼ y. The equivalence class of an element x ∈ X
is denoted by [x]. The set of all equivalence classes of the relation R is denoted
by X/R and is called the quotient set of X with respect to R.
Conversely, every partition of a set X into disjoint sets defines on it
a unique equivalence relation whose equivalence classes coincide with the original partition.
3.1. Examples. Let f : X → Y be a surjective mapping. An equivalence relation R on X is defined: x ∼ y if and only if f(x) = f(y). The equivalence classes of the relation are the preimages of points under the mapping f. A natural bijection of X/R onto Y is defined.
Special cases of this construction are: the projection mapping of the plane
onto the Ox axis (the equivalence classes are lines parallel to the Oy axis); the mapping of the plane
onto the nonnegative real numbers
2 (a point of the plane is assigned its distance to the origin) (the equivalence classes are circles centered at the origin O, and the point O).
3.2. Proposition. Let R be an equivalence relation on X and Y ⊂ X. Then the restriction R|Y of the relation R to Y is an equivalence relation.
§ 4. Ordering, linear ordering, well-ordering.
Let ≤ be a relation on a set X. We say that ≤ orders X, or that ≤ is an ordering (order) on X, if the relation ≤ satisfies the following properties:
1) If x ≤ y and y ≤ z, then x ≤ z (transitivity),
2) x ≤ x for every x ∈ X (reflexivity),
3) If x ≤ y and y ≤ x, then x = y (antisymmetry).
A set X together with an order ≤ on it is called an ordered set. Notation (X, ≤). Two elements x and y of an ordered set X are called incomparable if neither of the inequalities x ≤ y and y ≤ x holds.
4.1. Examples. On the plane
consider the following relation ≤:
(x1, x2) ≤ (y1, y2) ⇐⇒ x1 ≤ y1 and x2 ≤ y2. (4.1)
It is easy to see that ≤ is an order on R2
. For a point (x, y) the set of points {(a, b) : x ≤ a, y ≤ b}
is a quadrant bounded by rays parallel to the coordinate axes, with vertex at (x, y) (the set of points {(a, b) : a ≤ x, b ≤ y} is a quadrant bounded by rays parallel to the coordinate axes and having the opposite direction, with vertex at (x, y)). Points lying in the
complement of these two quadrants are incomparable with (x, y). Ordering on N: a ≤ b ⇐⇒ a|b (a divides b).
A subset Y of an ordered set X is said to have an upper bound in X if there exists an element x ∈ X such that y ≤ x for all y ∈ Y .
An element x of an ordered set X is called maximal if for any other element y ∈ X either y ≤ x, or y is incomparable with x. An element x ∈ X is called the greatest if y ≤ x for all y ∈ X.
Similarly one defines: a lower bound of a subset, a minimal element, and a least element of an ordered set.
4.2. Example. Consider the set
with the order that is the restriction to X of the order on the plane (4.1). The subset Y = (x, −x) : x ∈ R
is the set of all maximal elements of the ordered set X, and none of the elements of Y is the greatest in X.
An ordered set (X, ≤) is called linearly ordered if it contains no incomparable elements, i.e., for x, y ∈ X always x ≤ y or y ≤ x. If X is linearly ordered by the relation ≤, then, setting for any x, y ∈ X
x < y if and only if x ≤ y and x 6= y
we obtain the linear order relation <. It satisfies the following properties:
1) If x < y and y < z, then x < z (transitivity),
2) If x < y, then the relation y < x does not hold (antireflexivity),
3) If x 6= y, then either y < x, or x < y (comparability).
In a linearly ordered set, the notions of maximal and greatest (minimal and least) elements coincide.
4.3. Examples. On the plane R2 the relation (x1, x2) < (y1, y2) ⇐⇒ x1 < y1, or x1 = y1 and x2 < y2 is a linear order.
Let (X, <) and (Y, <) be linearly ordered sets. The lexicographic order on the product X × Y is the linear order:
(x1, y1) < (x2, y2), if x1 < x2 or x1 = x2 and y1 < y2.
The linear order on the product of lines is a special case of the lexicographic order.
4.4. Proposition. Let (X, ≤) be an ordered set and Y ⊂ X. Then the relation ≤ |Y is an order relation on Y . If ≤ is a linear order on X, then ≤ |Y is a linear order on Y .
A linear order < on a set X is called a well-ordering, and the set X together with the order < is called well-ordered, if every nonempty subset of the set X has a least element.
4.5. Examples. Any finite linearly ordered set is well-ordered.
The set of natural numbers N (with the natural order) is a well-ordered set.
The set of natural numbers with an added element N∪{∞} (with the natural order on N, n < {∞} for every n ∈ N) is a well-ordered set.
The sets of integers Z and real numbers R (with the natural orders) are not well-ordered sets.
A subset of a well-ordered set is a well-ordered set.
The lexicographic order on the product of well-ordered sets A and B is a well-ordering. Indeed, let X ⊂ A × B, pr : A × B → A be the projection. Denote by a0 the least element of the set pr(X) ⊂ A. Then the set {b : (a0, b) ∈ X} ⊂ B has a least element b0. The element (a0, b0) will be the least element of the set X.
§ 5. Equipotence of sets. Cardinality of a set. Cardinal numbers. The Cantor–Bernstein theorem.
The cardinality of a set is, in a sense, the “number” of its elements. For a finite
set the notion of the number of its elements raises no questions. With infinite
sets the situation is more complicated.
Sets A and B are called equivalent or equipotent (notation: A ∼ B or
|A| = |B|), if there exists a bijective mapping f : A → B. Equipotence of sets is an
equivalence relation. To each set X a cardinal number (or
cardinal) |X| is assigned — the cardinality of the set X. Equipotent sets are assigned equal
cardinal numbers.
A set is called countable if it is equipotent to the set of natural numbers N. Its
cardinality is denoted ℵ0.
A set is called uncountable if it is not finite and not equipotent to N.
Order on cardinals. If there exists an injective mapping of a set A into B, then
|A| ≤ |B|. If |A| ≤ |B| and the sets A and B are not equivalent, then |A| < |B|.
5.1. Theorem (existence of non-equivalent infinite sets). For any set
Proof. The mapping g : A → 2
A, g(a) = {a}, of the set A onto the set {{a} :a ∈ A} ⊂ 2
A of all one-point subsets of A is injective. Thus
. (5.1)
To complete the proof, we show that there is no surjective mapping of A onto 2
A. Let g : A → 2
A be an arbitrary mapping. For every a ∈ A the set g(a)
is a subset of A either containing a, or not containing it. Set
B = {a ∈ A : a 6∈ g(a)} (the set of elements of A whose images do not contain themselves).
We show that B 6∈ g(A). Then g(A) 6= 2A.
Take any a ∈ A. If a ∈ g(a), then, by the definition of the set B, a 6∈ B and, hence,
g(a) 6= B. If a 6∈ g(a), then a ∈ B, and again g(a) 6= B. So, for all a ∈ A, g(a) 6= B, i.e., B 6∈ g(A).
Hence
(5.2)
From (5.1) and (5.2) we have |A| < |2A|.
5.2. Corollary. The set 2
N is uncountable.
5.3. Proposition. The set 2
N is equipotent to the set of points of the segment I = [0, 1].
Proof. The set 2
N is naturally identified with the set of sequences of 0's and 1's. The binary expansion
t = 0, i1i2 . . . ik . . .
of an arbitrary number t ∈ I = [0, 1] gives us a mapping f : 2N → I. It is surjective, but not one-to-one. Numbers of the form
(5.3)
correspond to exactly two expansions: in one, starting from some index, all digits are
0, and in the other — all are ones. Denote by D the set of binary-rational numbers on the segment I, i.e., the set of numbers of the form (5.3). On the set f
−1 (I \D) the mapping f is injective. But the sets D and f −1(D) are countable. Hence there exists a bijection g : f−1 (D) → D. Then the mapping h : 2N → I, defined as follows:
,
is a bijection.
The cardinality of the continuum is the cardinality of the segment I = [0, 1]. It is denoted c.
5.4. Theorem (Cantor–Bernstein) (antisymmetry of the order on cardinals). If
|A| ≤ |B| and |B| ≤ |A|, then |A| = |B|.
Proof. Let f : A → B0
, B0 ⊂ B, g : B → A0
, A0 ⊂ A, be bijections. Set
It is easy to see that
f(C) = D, g(D) = C \ C0.
Then the mapping
h : A → B, where h|C = f, h|A\C = g
−1
is the required bijection.
§ 6. Ordinals.
Well-ordered sets (X, <) and (Y, <0) are similar if there exists a bijection f of the set X onto Y that preserves order, i.e., for any x, y ∈ X, if x < y, then f(x) <0 f(y).
Similarity of well-ordered sets is an equivalence relation. To each well-
ordered set (X, <) an ordinal number, or ordinal — the order
type of the set X — is assigned. The order types of well-ordered sets (X, <) and (Y, <0) are the same if and only if the sets (X, <) and (Y, <0) are similar.
Order on ordinals. Let α and β be ordinals that are the order types of the sets (X, <) and (Y, <0) (with least elements x0 and y0 respectively). Set α < β, if there exists y ∈ Y such that X is similar to the initial segment [y0, y) = {t ∈ Y : t <0 y}.
6.1. Remark (properties of initial segments). A finite well-ordered set of n elements has n − 1 initial segments.
An infinite well-ordered set contains initial segments of n elements, n ∈ N.
Let X be a well-ordered set, [x0, x) an initial segment of X. Then either [x0, x) ∪ {x} = X, or [x0, x) ∪ {x} is an initial segment.
The union of initial segments of a well-ordered set X is either an initial segment, or the set X itself.
If ϕ defines a similarity of the sets X and Y , [x0, x) an initial segment of X, then ϕ|[x0,x) defines a similarity of [x0, x) and the initial segment [y0, f(x)) in Y .
6.2. Proposition. For any two distinct ordinals α and β, one of the following cases always holds:
(1) α < β,
(2) α > β.
Proof. The case when one of the ordinals α or β is finite is left as an exercise.
Let the ordinals α and β be the order types of the infinite sets (X, <) and (Y, <0)
with least elements x0 and y0 respectively.
Let Z be the set of pairs (X0, Y 0) of similar initial segments of X and Y . Z 6= ∅.
The similarity of the initial segments X0 and Y0 is uniquely determined by the set X0. Indeed,
suppose there exist two distinct embeddings: ϕ : X0 → Y and ϕ0
: X0 → Y , defining a similarity of X0 and initial segments of Y . Denote by x the least element of the set X0
such that ϕ(x) 6= ϕ0(x). Clearly x 6= x0. Then ϕ|[x0,x) = ϕ0 |[x0,x) and
It follows that ϕ(x) = ϕ0(x). Contradiction.
Set
a similarity.
The mapping ψ is well defined (by the fact from Remark 6.1 and the argument given
above in the proof). The mapping ψ realizes a similarity of the sets A and B.
By the fact from Remark 6.1, A is either the initial segment [x0, x), or A = X; B is either the initial
segment [y0, y), or B = Y .
I The case A = X, B = Y is impossible due to the assumption α 6= β.
II The case A = X, B = [y0, y) corresponds to the inequality α < β.
III The case A = [x0, x), B = Y corresponds to the inequality α > β.
IV The case A = [x0, x), B = [y0, y). Set A+ = A ∪ {x}, B+ = B ∪ {y}. A mapping is defined
ψ
+ : A+ → B+, ψ
+|A = ψ, ψ
+(x) = y, realizing a similarity of the sets A+ and B+.
If A+ 6= X and B+ 6= Y , then A+ and B+ are similar initial segments. But (A+, B+) 6∈ Z.
Contradiction.
If A+ = X and B+ 6= Y , then α < β.
If A+ 6= X and B+ = Y , then α > β.
If A+ = X and B+ = Y , then X and Y are similar sets. Contradiction with the assumption
α 6= β.
In all cases, either α < β, or α > β.
6.3. Theorem. The set of ordinals is well-ordered.
Proof. Taking into account Proposition 6.2, the set of ordinals is linearly ordered.
Let A be a subset of ordinals, α an arbitrary element of A. If α is the least
element of A, then everything is proved.
Otherwise, let Yα be a well-ordered set of order type α ∈ A (with least
element y0), A0 = {α
0 ∈ A : α
0 < α}, Yα0 a well-ordered set of order type
α
0 ∈ A0
.
For every α
0 ∈ A0
there exists an initial segment [y0, yα0 ) in Yα, similar to Yα0 . Set
yα0 = inf{yα0 : α
0 ∈ A0}. Then α0 is the least element of A.
One of the main purposes of well-ordered sets is to serve as the basis for proofs by transfinite induction. The principle of transfinite induction, generalizing the ordinary principle of mathematical induction, is as follows.
Theorem (principle of transfinite induction). Let (W, <) be a well-ordered set, and to each α ∈ W let there correspond some statement P(α), such
that the following two conditions hold:
(1) the statement P(0) is true, where 0 is the first element of the set (W, <);
(2) if β ∈ W and P(α) is true for all α < β, α ∈ W, then P(β) is also true.
Then P(α) is true for all α ∈ W.
§ 7. Axiom of choice. Kuratowski–Zorn lemma. Zermelo's theorem. Well-ordering of cardinals.
Axiom of choice. For every family {Xα : α ∈ J} of nonempty sets there exists
a mapping f : J →S
α∈J Xα, such that f(α) ∈ Xα for every α ∈ J.
Kuratowski–Zorn lemma. Let (X, ≤) be an ordered set. Suppose that every linearly ordered subset Y ⊂ X has an upper bound in X. Then X has a maximal element.
Zermelo's theorem. On every set X there exists a relation < that well-orders X.
The Kuratowski–Zorn lemma, Zermelo's theorem, and the axiom of choice are equivalent.
Well-ordering of cardinals. Let α and |X| be an ordinal and a cardinal, for the set X, β and |Y | an ordinal and a cardinal, for the set Y . The choice of ordinals is possible by Zermelo's
theorem. The choice is not unique. Arbitrarily chosen ordinals will suit us.
If α ≤ β, then |X| ≤ |Y | (if there exists a similarity of α to an initial segment of β, or α and β
are similar, then there exists an injection of X into Y ). Hence the cardinals are comparable.
If |X| < |Y |, then α < β (if there is no injection of Y into X, then α and β are not similar and there is no
similarity of β to an initial segment of α). This last condition allows us to regard the
set of cardinals as a subset of the ordinals (with consistent orders). Namely,
to each cardinal κ is assigned an arbitrary order type (ordinal) of a set of cardinality κ. Thereby the cardinals are a well-ordered set (as a subset of the ordinals).
7.1. Example. There exists a well-ordered set T with a greatest element ω1
(and least element t0) such that the initial segment [t0, ω1) = {t ∈ T : t < ω1} is uncountable,
while the initial segments [t0, y) = {t ∈ T : t < y}, y < ω1, are countable.
Take an uncountable well-ordered set A (with least element a) and consider the lexicographically ordered product {0, 1}×A (with the order 0 < 1 on the two-point set
{0, 1}). The initial segment [(0, a),(1, a)) is uncountable. Let c be the least element of {0, 1}×A, for
which the initial segment [a, c) is uncountable. It exists, since the set {0, 1} × A with the lexicographic order is well-ordered. Then the subset T = [a, c) ∪ {c} is the
required one.
The set T(ω1) = T \ {ω1} is called the set of countable transfinites. Its cardinality
is denoted ℵ1.
The equality 2
ℵ0 = ℵ1 is called the continuum hypothesis. The generalized continuum hypothesis
states that for any infinite set X, there does not exist a set Y of cardinality
less than 2
X and greater than X. They are independent of the axioms of set theory.
Problem Set No. 1
1. Verify that the following equalities hold: for A, B, C ⊂ X
(a) A ∩ (B \ C) = (A ∩ B) \ (A ∩ C);
(b) A ∪ (B \ C) = (A ∪ B) \ (A ∪ C);
for A, C ⊂ X, B, D ⊂ Y
(c) (A × B) ∩ (C × D) = (A ∩ C) × (B ∩ D);
(d) (A × B) ∪ (C × D) = (A ∪ C) × (B ∪ D);
(e) (A \ C) × (B \ D) = (A × B \ C × B) \ A × D;
(f) (A × B) \ (C × D) = (A \ C) × (B \ D).
2. Let X0 ⊂ X, Y0 ⊂ Y and f : X → Y . Prove that
10
(a) X0 ⊂ f
−1
(f(X0)) and equality holds if f is injective;
(b) f(f
−1
(Y0)) ⊂ Y0 and equality holds if f is surjective.
3. Let X0, X1 ⊂ X, Y0, Y1 ⊂ Y and f : X → Y . Prove that:
(d)
and equality holds if the mapping is injective;
(e)
(f)
and equality holds if the mapping is injective.
5. Let f : X → Y , g : Y → Z and the mapping g ◦ f is injective (surjective). Prove that f is injective (g is surjective).
6. Prove that a mapping is invertible if and only if it is bijective.
7. Let R be an equivalence relation on X and Y ⊂ X. Prove that the restriction R|Y of the relation R to Y is an equivalence relation.
8. On the plane
a subset is given
Describe the equivalence relation on the line R that is the intersection of all equivalence relations containing the set A (i.e., the smallest equivalence relation on R containing the set A).
9. Is the relation: a ≤ b if and only if a|b (a divides b), an ordering on Z (the integers)?
10. Is the relation: B ≤ C if and only if B ⊂ C, an ordering on 2A (the family of all subsets of a set A)?
11. Let (X, ≤) be an ordered set and Y ⊂ X. Prove that the relation ≤ |Y is an order relation on Y , and if ≤ is a linear order on X, then ≤ |Y is a linear order on Y .
12. Prove that the sets {0, 1} × N and N × {0, 1} with the lexicographic order are not similar.
13. (a) Prove that a finite well-ordered set of n elements has n − 1
initial segments.
(b) Prove that an infinite well-ordered set contains initial
segments of n elements, n ∈ N.
(c) Let X be a well-ordered set, [x0, x) an initial segment of X. Prove
that then either [x0, x) ∪ {x} = X, or [x0, x) ∪ {x} is an initial segment.
(d) Prove that the union of initial segments of a well-ordered set X is either an
initial segment, or the set X itself.
(e) Prove that if ϕ defines a similarity of the sets X and Y , [x0, x) an initial segment of X, then
ϕ|[x0,x) (the restriction of ϕ to [x0, x)) defines a similarity of [x0, x) and the initial segment [y0, f(x)) in Y .
14. Prove that the only self-similarity of a well-ordered set is the identity mapping.
15. Prove that for any nonempty set X there exists a bijection of XN × XN onto XN (where XN is the set of mappings from N to X).
16. Prove that the product Nn is countable for any n ∈ N. Prove that the product N N (or the set of mappings from N to N) has the cardinality of the continuum.
17. Find the cardinality of the set
(the set of mappings from
to
).
Additional Problems for Problem Set No. 1
18. Prove that on N
N the relation (a1, a2, . . .) < (b1, b2, . . .) if and only if
ai = bi for i < n and an < bn, is a linear order, but not a well-ordering.
19. (a) Prove that a linearly ordered set A is not well-ordered if and only if A contains a set similar to the sequence
{−n : n ∈ N}.
(b) Prove that a linearly ordered set A is well-ordered if and only
if every countable subset of it is well-ordered.
20. (a) Find the cardinality of all finite subsets of an infinite set X.
(b) Find the cardinality of all countable subsets of an infinite set X.
21. Let X be an infinite set. Prove that the sets X × X and X are equipotent.
22. (a) What is the cardinality of the set of all order types of a finite set?
(b) What is the cardinality of the set of all order types of a countable set?
. Prove that 
Comments