chapter 1

SETS AND FUNCTIONS

In this chapter we review the foundations and notations of naı̈ve set theory. We
will define sets and the notions of functions, relations and operations on sets
that are required in this text. The reader who is well acquainted with basic
mathematics can browse through the present chapter.

1.1 Sets

1.1.1 Set, element, inclusion

Let E be a set and e an element. e ∈ E means that e is a member of the set E
and is read ‘e is in E’. The negation of this relation (i.e. e is not in E) is denoted
by e ∈
/ E. The empty set is a set containing no elements; it is denoted by ∅.
Let A, B be two sets. A is said to be a subset of B, or contained in B, if and
only if any member of A is a member of B, and this is denoted by A ⊆ B. The
negation of A ⊆ B is denoted by A 6⊆ B, and this does not mean that B ⊆ A.
We notice that A = B if and only if A ⊆ B and B ⊆ A (i.e. if and only if A and
B have the same elements). If A ⊆ B, but A 6= B, we will write A ⊆ /
B. Finally,
the set of subsets of E is denoted by P(E); hence A ⊆ E if and only if A ∈ P(E).
Note that the sets ∅ and E are elements of P(E).
Example 1.1 Let E = {0, 1}. P(E) = {∅, {0}, {1}, {0, 1}}.

Remark 1.2 Some authors, mainly French, among them Bourbaki, denote in-
clusion by ⊂; so, to avoid ambiguities, strict inclusion is denoted by ⊆
/
.
The Cartesian product of two sets E and F is the set of all ordered pairs
consisting of an element of E and an element of F :

E × F = {(x, y) / x ∈ E and y ∈ F } .

1
2 1. Sets and functions

The Cartesian product can be generalized to a finite family of sets:

E1 × · · · × En = {(x1 , . . . , xn ) / x1 ∈ E1 , . . . , xn ∈ En } .

Lastly, the Cartesian product of E by itself n times, for n ≥ 1, is denoted by

E n = E × · · · × E. E n can be recursively defined by (see Chapter 3): E 1 = E
and E n = E × E n−1 .

1.1.2 Union, intersection, difference, complement, partition

Assume that a universal set E is given. Let A, B be two subsets of E. We define:

• the intersection of A and B: A ∩ B = {e ∈ E / e ∈ A and e ∈ B},

• the union of A and B: A ∪ B = {e ∈ E / e ∈ A or e ∈ B},
• the difference of A and B: A \ B = {e ∈ E / e ∈ A and e 6∈ B},
• the complement of A with respect to E, denoted by A or Ac :
A = E \ A = {e ∈ E / e ∈
/ A},
• the symmetric difference of A and B: A △ B = (A \ B) ∪ (B \ A).

Two subsets A and B of E are said to be disjoint if and only if A ∩ B = ∅.

Example 1.3
• E = ∅, and ∅ = E.
• A ∩ ∅ = ∅, A ∪ E = E, A △ E = A.
• A ∩ A = A ∪ A = A ∪ ∅ = A △ ∅ = A ∩ E = A = A.
• A \ B = A ∩ B.
• A \ A = A △ A = ∅.

De Morgan’s laws enable us to compute the complement of a union and of an

intersection: A ∪ B = A ∩ B and A ∩ B = A ∪ B.
Union and intersection are associative and commutative operations (see Section
1.4.1). Moreover, they distribute over each other (see Section 1.4.1), i.e.

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) and
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) .

These properties are to be found again in the study of lattices (see Chapter 2,
Section 2.5) and in the study of Boolean algebras (see Chapter 4).
Notations
=⇒ (resp. ⇐⇒) stands for ‘implies’ (resp. ‘if and only if’).
∃e ∈ E (resp. ∀e ∈ E) stands for ‘there exists an e in E’ (resp. ‘for any e in E’).
Sets 3

Exercise 1.1 Let A, B and C be three subsets of E. Show that

A ∩ B = A ∩ C ⇐⇒ A ∩ B = A ∩ C. ♦
Exercise 1.2 Let A, B and C be three subsets of E. Show that


A∪B ⊆A∪C and A ∩ B ⊆ A ∩ C =⇒ B ⊆ C.

When does the equality B = C hold? ♦

Exercise 1.3 Let A, B and C be three subsets of E. What is the relationship between
(i) A △ (B ∩ C) and (A △ B) ∩ (A △ C) and
(ii) A △ (B ∪ C) and (A △ B) ∪ (A △ C)?
When are they equal? ♦
Union and intersection can be generalized to any family of subsets of a set E. A
family (xi )i∈I of elements of a set X is a mapping from I to X (see Section 1.2).
I is called the set of indices, and the image by this mapping of the element i of
I is denoted by xi . When we consider a family of subsets of a set E, it means
that the elements of the family are subsets of E, i.e. X = P(E). Let (Ai )i∈I
be a family of subsets of E. Recall that ∀ (resp. ∃) means ‘for all’ (resp. ‘there
exists’). We define:
[
Ai = {e ∈ E / ∃i ∈ I, e ∈ Ai } ,
i∈I
\
Ai = {e ∈ E / ∀i ∈ I, e ∈ Ai } .
i∈I
S T
Note that i∈∅ Ai = ∅ and i∈∅ Ai = E. On the other hand, if I = {1, . . . , n},
the family (Ai )i∈I is finite, and these two operations are just the finite union
and intersection, denoted by A1 ∪ · · · ∪ An and A1 ∩ · · · ∩ An respectively. This
generalization enables us to define the notion of partition of a set E. A finite or
infinite family (Ai )i∈I of subsets of E is a partition of E if it satisfies
(i) Ai 6= ∅ for any i ∈ I,
(ii) Ai ∩ S
Aj = ∅ for all pairwise distinct i, j in I and
(iii) E = i∈I Ai .
Example 1.4 The three sets
• A0 = {n ∈ IN / n is a multiple of 3},
• A1 = {n + 1 / n ∈ A0 } = {(multiples of 3)+1} and
• A2 = {n + 2 / n ∈ A0 } = {(multiples of 3)+2}
form a partition of IN.
Exercise 1.4 Let A be a subset of E and (Bi )i∈I be a family of subsets of E. Show
that
4 1. Sets and functions
   
S T T
1. A i∈I
Bi = i∈I
A ∪ Bi ,
   
T S S
2. A i∈I
Bi = i∈I
A ∩ Bi . ♦

1.2 Functions

1.2.1 Definitions
Intuitively, a mapping f from E to F assigns to each element x of E a unique
element f (x) of F . The slightly more general notions of correspondence and
function will also be of use. Formally, the definitions are as follows.
Let E and F be two sets. A correspondence from E to F is a triple
f = (E, F, Γ), where Γ is a subset of E × F . We say that E is the pre-domain of
f , F is the co-domain of f and Γ is the graph of f . The set

Dom(f ) = {x ∈ E / ∃y ∈ F, (x, y) ∈ Γ}

is the domain of f and the set

Im(f ) = {y ∈ F / ∃x ∈ E, (x, y) ∈ Γ}

is the range of f . Let x ∈ E. Any element y of F such that (x, y) ∈ Γ is an image

of x by f . Let X ⊆ E. We denote by

f (X) = {y ∈ F / ∃x ∈ X, (x, y) ∈ Γ}

the set of images by f of the elements of X. Similarly, any element x ∈ E such

that (x, y) ∈ Γ is called a preimage by f of y ∈ F . For Y ⊆ F , we denote by

f −1 (Y ) = {x ∈ E / ∃y ∈ Y, (x, y) ∈ Γ}

the set of preimages by f of the elements of Y . We have Dom(f ) = f −1 (F ) and

Im(f ) = f (E).
A correspondence f = (E, F, Γ) is said to be a function if it assigns at most
one image to each element of E; for any element x of E this image is denoted
by f (x). The function f is denoted by f : E −→ F . A function f : E −→ F is
said to be a mapping if its domain is the whole set E: Dom(f ) = E. The set of
mappings from E to F is denoted by F E .
Functions 5

Example 1.5
• The identity mapping on E defined by f (x) = x for any x of E is denoted
by idE : E −→ E.
• The function χA : E −→ {0, 1} defined by:

1 if e ∈ A,
χA (e) =
0 if e ∈
/ A,
is called the characteristic function of the subset A of E.
A mapping f : E −→ F is said to be one-to-one or injective (resp. onto or
surjective, bijective or a one-to-one correspondence) if any element y ∈ F has at
most (resp. at least, exactly) one preimage by f . We thus have:
• f is injective if and only if ∀x, y ∈ E, f (x) = f (y) =⇒ x = y.
• f is surjective if and only if ∀y ∈ F , ∃x ∈ E, y = f (x).
• f is bijective if and only if ∀y ∈ F , ∃!x ∈ E, y = f (x), i.e. if f is both
injective and surjective. (The symbol ∃! means ‘there exists a unique’.)
Exercise 1.5 Let f : E −→ F be a mapping
and let (Ai )i∈I be a partition of F . Note:
f (E) = {f (e) / e ∈ E}. Show that f −1 (Ai ) i∈I is almost a partition of E, by which


we mean that some f −1 (Ai ) may be empty, thus preventing f −1 (Ai ) i∈I from being a
partition of E. Give a sufficient condition for all the sets f −1 (Ai ) to be non-empty. ♦
Exercise 1.6 Let f : E −→ F be a mapping. Find a necessary and sufficient condition
for ensuring that the image by f of any partition of E is a partition of F . Assume that
if f is injective, then f (A ∩ B) = f (A) ∩ f (B) (see Exercise

1.8), and

recall that the
image of a partition (Ai )i∈I of E is defined by f (Ai )i∈I = f (Ai )i∈I . ♦
Let f : E −→ F and g: F −→ G be two mappings. The composition of f and
g is the mapping g ◦ f : E −→ G defined by g ◦ f (x) = g(f (x)). For instance,
if f : E −→ F is a mapping, we have f ◦ idE = idF ◦ f = f . The composition
of mappings is associative; hence, parentheses can be omitted and we can write
h ◦ g ◦ f.
1.2.2 Properties
We present some useful properties of sets and mappings.
Let f : E −→ F be a mapping, let A and B be two subsets of E and let C and
D be two subsets of F . We have:
f (A ∪ B) = f (A) ∪ f (B) and f (A ∩ B) ⊆ f (A) ∩ f (B) ,
f −1 (C ∪ D) = f −1 (C) ∪ f −1 (D) and f −1 (C ∩ D) = f −1 (C) ∩ f −1 (D) .
If, moreover, f is injective, then f (A ∩ B) = f (A) ∩ f (B). These properties are
easily proved and can be generalized to arbitrary unions or intersections.
6 1. Sets and functions

Exercise 1.7 Let f : A −→ B be a mapping. Show that

1. f injective ⇐⇒ ∀X ⊆ A, f −1 (f (X)) = X ,
2. f surjective ⇐⇒ ∀Y ⊆ B, f (f −1 (Y )) = Y . ♦

Exercise 1.8 Let f : A −→ B be a mapping. Show that

f injective ⇐⇒ ∀X, Y ⊆ A, f (X ∩ Y ) = f (X) ∩ f (Y ). ♦

Exercise 1.9 Let E be a set and let A and B be two subsets of E. Consider the
mapping
f : P(E) −→ P(A) × P(B)
X 7−→ (X ∩ A, X ∩ B) ,

where X 7−→ (X ∩ A, X ∩ B) means that f assigns to each X in P(E) the pair (X ∩

A, X ∩B) in P(A)×P(B). Find necessary and sufficient conditions on A and B ensuring
that f will be

1. injective,
2. surjective and
3. bijective. ♦

Proposition 1.6 Let f : E −→ F and g: F −→ G be two mappings.

(i) f and g injective =⇒ g ◦ f injective.

(ii) f and g surjective =⇒ g ◦ f surjective.
(iii) f and g bijective =⇒ g ◦ f bijective.
Exercise 1.10 Prove these properties. ♦

Exercise 1.11 Consider two mappings f : A −→ B and g: B −→ C.

1. Show that
(i) g ◦ f injective =⇒ f injective,
(ii) g ◦ f surjective =⇒ g surjective.
2. Find an example for which g ◦ f is bijective, f is non-surjective and g is non-
injective.
3. Show that
(i) g ◦ f injective and f surjective =⇒ g injective,
(ii) g ◦ f surjective and g injective =⇒ f surjective. ♦

Exercise 1.12 Consider three mappings f : A −→ B, g: B −→ C and h: C −→ A.

1. Show that if h ◦ g ◦ f and g ◦ f ◦ h are injective and if f ◦ h ◦ g is surjective then

f, g and h are bijective.
2. Show that if h ◦ g ◦ f and g ◦ f ◦ h are surjective and if f ◦ h ◦ g is injective then
f, g and h are bijective. ♦
Cardinals 7

Proposition 1.7 Let f : E −→ F be a mapping.

(i) If E 6= ∅ then f is injective if and only if f has a left inverse, i.e. if there
exists a mapping r: F −→ E such that r ◦ f = idE . The mapping r is surjective
and is called a retraction of f .
(ii) f is surjective if and only if f has a right inverse, i.e. if there exists a
mapping s: F −→ E such that f ◦ s = idF . The mapping s is injective and is
called a section of f .
(iii) f is bijective if and only if f has an inverse, i.e. if there exists a mapping
f −1 : F −→ E such that f ◦ f −1 = idF and f −1 ◦ f = idE . The mapping f −1 is
a bijection and is called the inverse bijection of f .
Exercise 1.13 Prove these properties. ♦

1.3 Cardinals

1.3.1 Finite sets

For any integer n, let [n] be the set {1, . . . , n} of integers between 1 and n.
Proposition 1.8 If n < m, there is no injection from [m] to [n].
Exercise 1.14 Prove this proposition by induction (see Chapter 3). ♦

We easily deduce from this proposition that two integers n and m are equal if
and only if there exists a bijection from [n] to [m]. A set E is finite if there exists
an integer n and a bijection from E to [n]. This integer n is unique and is called
the cardinality of E; it is denoted by |E|.
Let E and F be finite sets and f : E −→ F be a mapping. With these notations,
we have

f injective ⇐⇒ ∀y ∈ F, |f −1 ({y})| ≤ 1 ,
f surjective ⇐⇒ ∀y ∈ F, |f −1 ({y})| ≥ 1 and
f bijective ⇐⇒ ∀y ∈ F, |f −1 ({y})| = 1 .

Moreover, if E is finite and |E| = |F | then,

f injective ⇐⇒ f surjective ⇐⇒ f bijective .

If E is not finite, these equivalences do not hold; for instance, f : IN =⇒ IN defined

by f (n) = 2n is injective, but not surjective.
Finally, the following properties are quite useful.
8 1. Sets and functions

Proposition 1.9 Let E and F be two finite sets.

(i) If E and F are disjoint then |E ∪ F | = |E| + |F |.
(ii) If (Ai )i∈[n] is a partition of E then |E| = |A1 | + · · · + |An |.
(iii) |E × F | = |E| × |F |.
(iv) |F E | = |F ||E| , where F E denotes the set of mappings from E to F .
(v) |P(E)| = 2|E| .
Exercise 1.15 Prove these properties. ♦

Example 1.10 Let n be the number of strings that can be coded with sixteen
bits. Each string is a sequence of 0s and 1s of length 16 and can be viewed as a
mapping from [16] to IB = {0, 1}. Hence, n = 216 = 65 536.
Exercise 1.16 A more picturesque way of stating Proposition 1.8 is the ‘pigeonhole
principle’. If n < m and a flock of m pigeons flies into n pigeonholes then there must
be at least one pigeonhole with two or more pigeons in it. More precisely, show that a
pigeonhole will contain at least p pigeons, where p is an integer p ≥ m/n. ♦

1.3.2 Countable sets

The notion of cardinality can be generalized to infinite sets in such a way that
the following properties are verified for any two sets E and F :
(i) |E| ≤ |F | ⇐⇒ there exists an injection from E to F .
(ii) |E| ≥ |F | ⇐⇒ there exists a surjection from E to F .
(iii) |E| = |F | ⇐⇒ there exists a bijection from E to F .
Exercise 1.17 From the above relations, we deduce that if there exists both an injec-
tion and a surjection from E to F then there exists a bijection from E to F . Prove this
result directly. ♦

A set E is countable if it is either finite or in a one-to-one correspondence with

the
S set IN of natural numbers. We denote by ω the cardinality of IN. A union
i∈I Ai is said to be countable if the set I of indices is countable.
The countable sets satisfy the following properties:
• Any subset of a countable set is countable.
• Any finite Cartesian product of countable sets is countable.
• Any countable union of countable sets is countable.
Exercise 1.18 Show that the set IN × IN is countable. ♦

Lastly, notice that there exist uncountable sets. This follows from the following
result.
Operations and relations 9

Proposition 1.11 Let E be a set and let P(E) be the set of subsets of E. We
have
|E| < |P(E)| .
Proof. We show by contradiction that there exists no bijection between E and
P(E). Assume that f : E −→ P(E) is a bijective mapping, and let A = {x ∈
E / x 6∈ f (x)}. Assume that there exists an a ∈ E such that A = f (a):
• If a ∈ A, we deduce from the definition of A that a 6∈ A: contradiction.
• Similarly, the hypothesis a 6∈ A leads to a contradiction.
Hence, A has no preimage by f , and this proves that f is not surjective and hence
not bijective.
Hence, there exists no bijective mapping from E to P(E), and the sets E and
P(E) thus have different cardinalities. The result is then deduced from the fact
that the mapping f : E −→ P(E) defined by f (x) = {x} is injective. ⊓
⊔
We deduce that P(IN) is uncountable.
Exercise 1.19 Consider the set U of sequences (un )n∈IN with values ranging over
{0, 1}, i.e. ∀n ∈ IN, un ∈ {0, 1}. (Sequences are studied in Chapter 7.) Show that U is
uncountable. ♦

1.4 Operations and relations

An operation Φ on a set E is a mapping Φ: E n −→ E. n is called the arity, or
the degree, of Φ. We also say that Φ is an n-ary operation, and this is denoted
by a(Φ) = n. We will mainly study operations of arity two, or binary operations.
1.4.1 Binary operations
A binary operation or binary relation ∗ on a set E is a mapping ∗: E × E −→ E.
The image of a pair (x, y) by this operation is denoted by x ∗ y (infix notation).
We define the following properties:
(i) ∗ is associative if ∀a, b, c ∈ E, a ∗ (b ∗ c) = (a ∗ b) ∗ c.
(ii) ∗ is commutative if ∀a, b ∈ E, a ∗ b = b ∗ a.
(iii) ∗ has the element 1l for unit if ∀e ∈ E, e ∗ 1l = 1l ∗ e = e.
If an operation ∗ is associative, we will denote by a ∗ b ∗ c (without parentheses)
the product of the three elements a, b and c that can be computed either as
(a ∗ b) ∗ c or as a ∗ (b ∗ c). More generally, we will denote by e1 ∗ e2 ∗ · · · ∗ en the
product of n elements.
Exercise 1.20 Show that if ∗ has a unit, this unit is unique. ♦
10 1. Sets and functions

Definition 1.12 A set E together with an associative operation ∗ is a semi-

group. If, moreover, E has a unit e for ∗, (E, ∗, e) is said to be a monoid. If
the operation ∗ is commutative, the semi-group (resp. the monoid) is said to be
commutative.

Example 1.13 The set IN together with addition + and its unit 0 is a commu-
tative monoid. The set IN together with multiplication × and its unit 1 is also a
commutative monoid.

Example 1.14 The set P(E) equipped with intersection (or union) is a commu-
tative monoid. The set of mappings from E to itself equipped with the compo-
sition of mappings is a non-commutative monoid if E has at least two elements.
The set of square n × n matrices with real-valued entries in IR is a monoid,
non-commutative if n > 1, for the operation of multiplication of matrices.
A special case of monoids, discussed in more detail in Chapter 11 because of
their importance in computer science, consists of the free monoids.
Definition 1.15 Let A be a finite set called the alphabet, whose elements are
called letters. The free monoid over A, denoted by A∗ , is the set of strings written
with letters of the alphabet A. A string u is just a finite sequence of letters.
Given a string u, the number of elements of its sequence is called the length of u
and is denoted by |u|. If the string u of length n is the sequence (u1 , u2 , . . . , un ), it
is simply denoted by u = u1 u2 · · · un . For instance, aaba, acebdacebd, a, b, aa and
aaa are strings over the alphabet A = {a, b, c, d, e}. The empty string, denoted by
ε, is a special string of A∗ containing no letters (the empty sequence). The oper-
ation of the monoid A∗ is called concatenation. The concatenation of two strings
u = u1 u2 · · · un and v = v1 v2 · · · vm is the string u · v = u1 u2 · · · un v1 v2 · · · vm .
For instance, aaba · cde = aabacde. The unit for concatenation is of course the
empty string ε.
Definition 1.16 A set E equipped with an operation ∗ is a group if it is
a monoid and every element has an inverse, i.e. ∀e ∈ E, ∃e′ ∈ E such that
e ∗e′ = e′ ∗e = 1l (where 1l denotes the unit for ∗). If, moreover, ∗ is commutative,
the group is said to be commutative.

Example 1.17 The set ZZ of integers equipped with the addition operation is a
commutative group. If E and operation ∗ form a monoid then the set of invertible
elements of E is a group. In particular, the set of invertible n × n square matrices
with real-valued entries in IR is a group, non-commutative if n > 1, for the
operation of multiplication of matrices.
Operations and relations 11

Let ⊤ and ⊥ be two operations on a set E. ⊤ is distributive over ⊥ if ∀a, b, c ∈

E,
a ⊤ (b ⊥ c) = (a ⊤ b) ⊥ (a ⊤ c)
and
(a ⊥ b) ⊤ c = (a ⊤ c) ⊥ (b ⊤ c).
If the operation ⊤ is commutative, either of the above two conditions alone is of
course enough.
Example 1.18 In IR, multiplication is distributive over addition. In P(E),
intersection and union are distributive over each other.
1.4.2 Relations

Definition 1.19 A relation on a set E is a subset R of E × E. To denote that a

pair (e, e′ ) of E × E is in this subset R, we will use one of the following notations:
(e, e′ ) ∈ R, e R e′ , R(e, e′ ).

Example 1.20
1. The following sets define relations on E = IN:
• the set {(n, m) / n ≤ m},
• the set {(n, m) / n ≤ m ≤ 2n},
• the set {(n, m) / n ≤ m and ∃k : n2 + m2 = k 2 }.
2. For any set A, inclusion is a relation on E = P(A).
1.4.3 Set-theoretic operations on relations
Because a relation is a set, we can easily define:
• the complement R of a relation R; R is the complement of R in E × E:

(e, e′ ) ∈ R ⇐⇒ (e, e′ ) 6∈ R ,

• the union R1 ∪ R2 of two relations R1 and R2 :

(e, e′ ) ∈ R1 ∪ R2 ⇐⇒ (e, e′ ) ∈ R1 or (e, e′ ) ∈ R2 ,

• the intersection R1 ∩ R2 of two relations R1 and R2 :

(e, e′ ) ∈ R1 ∩ R2 ⇐⇒ (e, e′ ) ∈ R1 and (e, e′ ) ∈ R2 .

We can also define three special relations:

• the empty relation, denoted by ∅E : ∀e, e′ ∈ E, (e, e′ ) 6∈ ∅E ,
12 1. Sets and functions

• the full relation, denoted by ΠE : ∀e, e′ ∈ E, (e, e′ ) ∈ ΠE ,

• the identity relation, denoted by IdE : ∀e, e′ ∈ E, (e, e′ ) ∈ IdE ⇐⇒ e = e′ .
Because R1 and R2 are sets, the property

∀e, e′ ∈ E, (e, e′ ) ∈ R1 =⇒ (e, e′ ) ∈ R2

can be expressed by writing R1 ⊆ R2 .

1.4.4 Other operations on relations
Let R be a binary relation on E. The inverse relation, denoted by R−1 , is defined
by
e R−1 e′ ⇐⇒ e′ R e .
Let R1 and R2 be two binary relations on E. Their product, denoted by
R1 .R2 , is the relation defined by

e R1 .R2 e′ ⇐⇒ ∃e′′ : e R1 e′′ and e′′ R2 e′ .

This product is associative; its unit is IdE .

Let R be a binary relation. The relation R∗ is equal to

IdE ∪ R ∪ (R.R) ∪ (R.R.R) ∪ · · ·

or i≥0 Ri with R0 = IdE , Ri+1 = R.Ri , for i ≥ 0. The relation R+ is defined

S

by R+ = i>0 Ri , and hence R∗ = IdE ∪ R+ .

S
We claim that ∀i, j ≤ 0, Ri+j = Ri .Rj . This result will be proved later (see
Exercise 3.5).
Exercise 1.21 Let R be a binary relation on E. Show that
1. (R1 ∪ R2 )−1 = R−1 −1
1 ∪ R2 .
2. (R1 ∩ R2 )−1 = R−1 −1
1 ∩ R2 .

−1
3. R = R−1 .
4. R1 ⊆ R2 ⇐⇒ R−1 −1
1 ⊆ R2 .
5. (R−1 )−1 = R .
6. If IdE ⊆ R then R+ = R∗ . Is the converse true? ♦
Exercise 1.22 Let R be a binary relation on E.
1. Show that
(a) (R1 .R2 )−1 = R−1 −1
2 .R1 ,
(b) (R1 ∪ R2 ).R = (R1 .R) ∪ (R2 .R) ,
(c) R.(R1 ∪ R2 ) = (R.R1 ) ∪ (R.R2 ) .
2. Show that (R1 ∩ R2 ).R = (R1 .R) ∩ (R2 .R) does not necessarily hold, but that
(R1 ∩ R2 ).R ⊆
/
(R1 .R) ∩ (R2 .R) holds. ♦
Operations and relations 13

1.4.5 Some properties of binary relations

A relation R is said to be

• left complete if ∀e ∈ E, ∃e′ ∈ E : e R e′ ,

• right complete if ∀e′ ∈ E, ∃e ∈ E : e R e′ .

The relation R is said to be

• reflexive if ∀e ∈ E, eRe,
• irreflexive if ∀e, e′ ∈ E, e R e′ =⇒ e 6= e′ ,
• symmetric if ∀e, e′ ∈ E, e R e′ =⇒ e′ R e ,
• antisymmetric if ∀e, e′ ∈ E, e R e′ and e′ R e =⇒ e = e′ ,
• transitive if ∀e, e′ , e′′ ∈ E, e R e′ and e′ R e′′ =⇒ e R e′′ .

Exercise 1.23
1. Show that if R is left (resp. right) complete then R−1 is right (resp. left) complete.
2. Show that
(i) IdE ⊆ R.R−1 if and only if R is left complete ,
(ii) IdE ⊆ R−1 .R if and only if R is right complete .
3. Show that R ∩ R−1 and R ∪ R−1 are symmetric.
4. Show that if R and R′ are transitive, then R ∩ R′ is transitive, but R ∪ R′ is not
necessarily transitive.
5. Show that R+ is transitive.
6. Show that if R is transitive then R = R+ , and that if R is reflexive and transitive
then R = R∗ . ♦

Exercise 1.24 Is the relation R defined on IN by n R m if and only if m = n + 1

symmetric? reflexive? transitive? What are the relations R+ and R∗ ? ♦

Exercise 1.25 Is the relation ‘n R m if and only if n and m have a common divisor
different from 1’ transitive? ♦

Exercise 1.26 Let E be the finite set {e1 , ..., en }, and let R be a binary relation on
E. We represent R by an n × n matrix, MR , with entries ranging over {0, 1} as follows:

1 if ei R ej ,
n
mi,j =
0 otherwise.

1. What property of MR characterizes the fact that the relation R is symmetric?

reflexive? irreflexive? antisymmetric?
2. Assuming MR and MR′ are known, how can we compute MR−1 , MR and MR.R′ ? ♦
14 1. Sets and functions

1.4.6 Equivalence relations

Definition 1.21 An equivalence relation is a reflexive, symmetric and transitive

relation.

Example 1.22
(i) The equality on a set E is an equivalence relation, denoted by both = and
IdE (see Section 1.4.3).
(ii) Let n be an integer greater than or equal to 2. The relation on ZZ: ‘x and
y have the same remainder when divided by n’ is an equivalence relation. It
is denoted by both x ≡ y[n] and x ≡ y mod n, and we say that ‘x and y are
congruent modulo n’.
The intersection R ∩ R′ of two equivalence relations is also an equivalence
relation, but the union R ∪ R′ and the product R.R′ need not be equivalence
relations.
Proposition 1.23 If R is an arbitrary relation, (R ∪ R−1 )∗ is an equivalence
relation, and it is the least equivalence relation containing R.
Proof. By definition, (R ∪ R−1 )∗ is reflexive and transitive. Since R ∪ R−1 is
symmetric, (R ∪ R−1 )∗ also is symmetric.
Clearly, (R ∪ R−1 )∗ contains R. Let R′ be an equivalence relation containing
R. Since R′ is symmetric, it also contains R ∪ R−1 , and since it is reflexive and
transitive, it contains (R ∪ R−1 )∗ . ⊓
⊔
Exercise 1.27 Show that if R and R′ are two equivalence relations, the least equiva-
lence relation containing R and R′ is (R ∪ R′ )+ . ♦

Definition 1.24 Let R be an equivalence relation on E and e be an element of

E. The set {e′ ∈ E / e R e′ }, denoted by [e]R , is called the equivalence class of e.

Proposition 1.25
1. ∀e ∈ E , e ∈ [e]R ,
2. ∀e, e′ ∈ E, e R e′ =⇒ [e]R = [e′ ]R ,
3. If [e]R ∩ [e′ ]R 6= ∅ , then [e]R = [e′ ]R .
Proof. The first point is obvious because e R e. To show the second point,
consider e′′ ∈ [e′ ]R ; then e′ R e′′ and, as e R e′ , we also have e R e′′ and
e′′ ∈ [e]R . Hence, [e′ ]R ⊆ [e]R . Conversely, [e]R ⊆ [e′ ]R for the same reasons.
Lastly, if e′′ ∈ [e]R ∩ [e′ ]R , then e R e′′ and e′′ R e′ , and hence e R e′ and
[e]R = [e′ ]R . ⊓
⊔
Operations and relations 15

The set {[e]R / e ∈ E} of subsets of E, called the factor set of E by R and

denoted by E/R, is hence a partition of E. Conversely, if A ⊆ P(E) is a partition
of E (i.e. ∀E1 , E2 ∈ A, E1 6= E2 =⇒ E1 ∩ E2 = ∅ and ∀e ∈ E, ∃Ee ∈ A : e ∈ Ee ),
we can define an equivalence relation RA by e RA e′ if and only if e and e′
are in the same subset of the partition. It is easy to see that this is indeed an
equivalence relation.
Exercise 1.28 Let P and P ′ be two partitions of a set E. P is said to be a refinement
of P ′ if ∀p ∈ P , ∃p′ ∈ P ′ : p ⊆ p′ .
Let R and R′ be two equivalence relations on E. Show that R ⊆ R′ if and only if
E/R is a refinement of E/R′ . ♦
Exercise 1.29 Let E be a set and let F be a set of subsets of E, i.e. F ⊆ P(E). For
x ∈ E, denote by Fx the set {X ∈ F / x ∈ X}. Let R be the relation defined on E by

x R y ⇐⇒ Fx ⊆ Fy .

1. Show that F is reflexive and transitive.

2. Show that R is antisymmetric if and only if: ∀x, y ∈ E, if x 6= y then there exists
X ∈ F such that |X ∩ {x, y}| = 1.
3. Show that if ∀X ∈ F, X ∈ F, then R is symmetric.
4. Assuming that the union and the intersection of any family of elements of F are
elements of F, prove the converse of 3. ♦

1.4.7 Congruences

Definition 1.26 An equivalence relation R on a set endowed with an operation

∗ is said to be a congruence if it is compatible with the operation ∗, or, in other
words if

∀e, e′ , d, d′ ∈ E, (e R e′ and d R d′ ) =⇒ (e ∗ d) R (e′ ∗ d′ ) .

Example 1.27 Let n be an integer greater than or equal to 2. The relation on

ZZ: ‘x ≡ y[n]’ is a congruence for addition and for multiplication.
If R is a congruence on the set E equipped with the operation ∗, then the
operation ∗ ‘can be factored through’ R, i.e. the factor set E/R can be endowed
with an operation [∗] defined by [e][∗][e′ ] = [e ∗ e′ ], and this operation [∗] is well
defined. (It does not depend on the chosen representatives of the equivalence
classes.) The operation [∗] will simply be denoted by ∗ .
Proposition 1.28 Let R be a congruence on a monoid (resp. group) (E, ∗).
The factor set E/R equipped with ∗ is a monoid (resp. group).
16 1. Sets and functions

Example 1.29 Let n be an integer greater than or equal to 2. The factor of ZZ

by the relation x ≡ y[n] is denoted by ZZ/nZZ. It is a group for addition and a
monoid for multiplication.
Exercise 1.30 On the set E = ZZ × (ZZ \ {0}) we define the operations + and × by

(a, b) + (c, d) = (ad + bc, bd) ,

(a, b) × (c, d) = (ac, bd) .

1. Show that (E, +) and (E, ×) are commutative monoids.

We define on E a relation ∼ by: (a, b) ∼ (c, d) ⇐⇒ ad = bc.
2. Show that ∼ is an equivalence relation on E and that it is a congruence for +
and ×.
3. Show that (E/ ∼, [+]) is a group, show that [×] is distributive over [+] and char-
acterize the elements of E/ ∼ having an inverse for [×].
Note: (E/ ∼, [+], [×]) is just the field Q of rational numbers. ♦