Set Theory for Computer Science

Sandjai Bhulai
Sandjai Bhulai
VU University Amsterdam
Department of Mathematics
De Boelelaan 1111
1081 HV Amsterdam
The Netherlands
[Link]@[Link]

Copyright © 2024 Sandjai Bhulai

Apart from any fair dealing for the purposes of research or private study, or
criticism or review, as permitted under the Copyright, Designs and Patents
Act 1988, this publication may only be reproduced, stored or transmitted,
in any form or by any means, with the prior permission in writing of the
publishers, or in the case of reprographic reproduction in accordance with
the terms of licenses issued by the Copyright Licensing Agency. Inquiries
concerning reproduction outside those terms should be sent to the author.
Set Theory for Computer Science

Sandjai Bhulai
Preface

You have finished secondary school and are about to begin at a university of
technical college. You want to study computing. The course includes some
mathematics – and that was not necessarily your favorite subject. But there
is no escape: a certain amount of finite mathematics is a required part of the
first-year curriculum, because it is a necessary toolkit for the subject itself.
That is where this book comes in. Its purpose is to provide the basic
mathematical language that you need to enter the world of the information
and computer sciences. You can learn the essentials here and perhaps have
even fun doing so. The book contains certain tools that we need to apply
over and over again when thinking about computations. They include:

1. Collecting things together (set theory).

2. Comparing things (relations).

3. Associating one item with another (functions).

4. Recycling outputs as inputs (recursion and induction).

Without an understanding of these basic concepts, large portions of computer

science remain behind closed door. As you begin to grasp the ideas and
integrate them into your thought, you will also find that their application
extends far beyond computing into many other areas.

Sandjai Bhulai
Amsterdam, 2014

i
ii Bhulai — Set Theory for Computer Science

Minor modifications have been made by Sander Dahmen in 2024.

Contents

Preface i

1 Sets 1
1.1 What is a set? . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Elements and subsets . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Operations: union and intersection . . . . . . . . . . . . . . . 4
1.4 The universe and the complement . . . . . . . . . . . . . . . . 6
1.5 Venn diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.6 The algebra of sets . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.9 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Relations 19
2.1 Lists, position, and length . . . . . . . . . . . . . . . . . . . . 19
2.2 Cartesian product . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Relations with n positions . . . . . . . . . . . . . . . . . . . . 23
2.4 Binary relations . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5 Different representations of binary relations . . . . . . . . . . 26
2.6 Some constructions with binary relations . . . . . . . . . . . . 28
2.7 Relations in a set . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.9 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3 Relations: Partial Order 39

3.1 Refresher: binary relations . . . . . . . . . . . . . . . . . . . . 39
3.2 Relations for orderings . . . . . . . . . . . . . . . . . . . . . . 41
3.3 Two constructions of relations for orderings . . . . . . . . . . 45

iii
iv Bhulai — Set Theory for Computer Science

3.4 Maxima and minima . . . . . . . . . . . . . . . . . . . . . . . 48

3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.6 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4 Relations: Equivalence 53
4.1 Refresher: binary relations . . . . . . . . . . . . . . . . . . . . 53
4.2 Equivalence relations . . . . . . . . . . . . . . . . . . . . . . . 54
4.3 Two constructions of equivalence relations . . . . . . . . . . . 55
4.4 Equivalence classes and partitions . . . . . . . . . . . . . . . 59
4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.6 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5 Functions 67
5.1 Processes and functions . . . . . . . . . . . . . . . . . . . . . 68
5.2 Mathematical description . . . . . . . . . . . . . . . . . . . . 69
5.3 Functions and equivalence relations . . . . . . . . . . . . . . . 73
5.4 Composition and inverse . . . . . . . . . . . . . . . . . . . . . 75
5.5 Counting and cardinality . . . . . . . . . . . . . . . . . . . . . 79
5.6 Some results on cardinality . . . . . . . . . . . . . . . . . . . 84
5.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.8 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

6 Induction and Recursion 95

6.1 The integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.2 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3 The well-ordering principle in Z . . . . . . . . . . . . . . . . . 102
6.4 Sequences and recursion . . . . . . . . . . . . . . . . . . . . . 104
6.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.6 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

Bibliography 110
Chapter 1

Sets

Goals of this chapter:

• Build up sets through enumeration, description, union, intersection, and

complements.
• Use Venn diagrams to depict formulas with sets or to determine the num-
ber of elements.
• Apply fundamental rules of computation for sets.
• Recognize and create a partition of a set.

1.1 What is a set?

Basic concepts, notation
People collect many things: stamps, baseball cards, pictures of mills, etc.
The notion of a set is thus a daily concept, however, at the same time it is an
essential part of the mathematical language. In this book we see a set as an
imaginary collection of objects. These objects are called elements (members)
of the set. Synonyms for the notion of a set are collection, family, or class.
A set can be represented by summing up the elements between curly
brackets { …}:
Planets := { Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune }
DaysOfWeek := {Monday, Tuesday, Wednesday, Thursday, Friday, Saturday,
Sunday}

1
2 Bhulai — Set Theory for Computer Science

MainColours := { Red, Green, Blue }

Digits := { 0, 1, 2, 3, …, 9 }
PrimeNumbers := { 2, 3, 5, 7, 11, 13, …}
The last two examples are more suggestive in summing up the elements.
More often it is easier to describe the elements of a set: the planets of a solar
system, the days of the week, the main colours, etc. The notation is then as
follows:
Months := { x : x is a month }
MultiplesOfTwo := { x : x is an even natural number }

The general form is

{ x : description of x }, or { x | description of x },
which is to be read as: the sets of all elements x that satisfy the descrip-
tion. The symbol x can be interpreted as the name of a generic element
(“prototype”).

Naming of sets
Sets usually get a name, such that one can point easily at the collection. In
each of the examples, one can find the name on the left. The symbol ‘:=’ is
the assignment or definition operator. For instance, the description
DivisorsOf10 := { x : x is a divisor of 10 }
assigns the name ‘DivisorsOf10’ to the set followed after the symbol ‘:=’. The
formula
MonthsOf30:= { April, June, September, November }
assigns the rather natural name to the set of months with 30 days.
The names can be chosen in any way, however, it is preferable to choose
them suggestively. Sometimes, neutral symbols such as A, B, C, …are used
for general sets. Some mathematical sets have a standard symbol:
N := { 0, 1, 2, 3, 4, …} (the set of all natural numbers)
Z := { …, -3, -2, -1, 0, 1, 2, 3, …} (the set of all integer numbers)
Q := { x : x is a rational number } (the set of all rational numbers)
R := { x : x is a real number } (the set of all real numbers)
Rational numbers are also called fractions.

1.2 Elements and subsets

Elements of a set
We have introduced the set Planets in the previous section. One of these
Chapter 1 — Sets 3

elements is Mars. We can write this as follows:

Mars ∈ Planets.
The symbol ‘∈’ can be read as “is element of”, or “is member of”. For
instance, “Mars ∈ Planets” can be read as
Mars is an element of the set Planets,
Mars is a member of the set Planets, or
Mars belongs to the set Planets.
The symbol ‘∈’ is called the element-of symbol. If the element x belongs to
the set A, we write that as x ∈ A. When x does NOT belong to A, we write
that as x ∈
/ A (a crossed-out ‘∈’-symbol).
Ganymedes 6∈ Planets.

Subsets of a set
The set { Mercury, Venus, Earth } consists of element belonging to the set
Planets. We say that { Mercury, Venus, Earth } is a subset of the set Planets
and write this as
{ Mercury, Venus, Earth } ⊆ Planets.
Here are some other examples. Every digit 0, 1, …, 9 is a natural number.
Hence
Digits ⊆ N.
A month has 28 to 31 days. As a consequence
{ x : x is a month with 30 days } ⊆ Months.
The symbol ‘⊆’ is the inclusion symbol. It can be read as “is a subset of”
or “is contained in”. A set A is a subset of set B when every element of A is
also an element of B. We write A ⊆ B when A is a subset of B. Note that
A ⊆ A is always true. When A is NOT a subset of B, we write A 6⊆ B (a
crossed-out ‘⊆0 symbol). For instance,
{ Sun, Moon, Earth } 6⊆ Planets.

Equality of sets
Two sets are equal if they have exactly the same elements. For example, the
set {1, 2, 3, 4, 5} and {5, 2, 4, 1, 3, 2, 3} are equal. We write this as
{1, 2, 3, 4, 5} = {5, 2, 4, 1, 3, 2, 3}.
Note that repetitions and the order in summing up the elements are irrele-
vant; they do not contribute to the information of the set, and they sometimes
can make the notation difficult to read. The symbol ‘=’ is called the equality
symbol. Note that the equality symbol is different from the definition symbol
4 Bhulai — Set Theory for Computer Science

‘:=’. When two sets A and B are equal, we write A = B. If two sets are NOT
equal, we write A 6= B (a crossed-out ‘=’ symbol). For instance,
MainColours 6= {Red, Yellow, Blue}.

An empty set does not have any element. For example { } and { x : x is a
prime number and 24 ≤ x ≤ 28 } are empty sets. Since empty sets contain
exactly the same elements (namely, none), they are the same. Hence, there
is only one empty set en we write that as ∅. As a side remark: A ⊆ B and
B ⊆ A can be true simultaneously; this exactly means that A = B.

Number of elements
When a set is given, relevant information is provided by the number of ele-
ments belonging to the set. The number of elements of a set A is given by
#A (in some books one uses | A| or A). For instance,
#Planets = 8,
#DaysOfWeek = 7,
#{ 0, 1, 0, 1, 0, 1 } = 2,
#∅ = 0.
NZQ
Equal sets have an equal number of elements. Sets as , , , and areR
infinitely large. Their “number” of elements cannot be represented with a
natural number.

1.3 Operations: union and intersection

Union of two sets
Take the following two sets of planets:
InnerPlanets := { Mercury, Venus, Earth, Mars }
PlanetsWithMoon := { Earth, Mars, Jupiter, Saturn, Uranus, Neptune }.
We can unite these two sets into one big set of all planets that are an inner
planet or are a planet having a moon:
{ Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune }.
The result of the union is denoted by InnerPlanets ∪ PlanetsWithMoon and
is exactly equal to the set Planets. Note that the planet Earth belongs to
both the set InnerPlanets as the set PlanetsWithMoon. Even though, this
element is mentioned only once in the union.
The union of two sets A and B contains elements that belong to set A or
set B. The result of the operation “union” is a set that we write as A ∪ B.
The symbol ‘∪’ is the union symbol. The definition of the union is
Chapter 1 — Sets 5

A ∪ B := { x : x ∈ A or x ∈ B }.
We earlier saw that an element of A ∪ B may well belong to both sets A and
B. In this context, one also speaks of non-exclusive or inclusive membership.
We will return to this in Section 1.4.

Intersection of two sets

Take the following sets EUmemberstates, consisting of all member state of
the European Union, and the set of NATOmemberstates, consisting of all
NATO member states. Every country is abbreviated by three letters of its
name; this is the configuration of February 2014:
EUmemberstates := { AUS, BEL, BUL, CRO, CYP, CZE, DEN, EST, FIN,
FRA,
GER, GRE, HUN, IRE, ITA, LAT, LIT, LUX, MAL, NET, POL, POR, ROM,
SLW, SLV, SPA, SWE, UK }
NATOmemberstates := { ALB, BEL, BUL, CAN, CRO, CZE, DEN, EST, FRA,
GER, GRE, HUN, ICE, ITA, LAT, LIT, LUX, NET, NOR, POL, POR,
ROM, SLW, SLV, SPA, TUR, UK, USA }.
We can now take the intersection of these two sets, which results in the set
of all countries that are a member of the European Union and NATO:
{ BEL, BUL, CRO, CZE, DEN, EST, FRA, GER, GRE, HUN, ITA, LAT, LIT,
LUX, NET, POL, POR, ROM, SLW, SLV, SPA, UK }
The result of the intersection is written as EUmemberstates ∩ NATOmem-
berstates en consists exactly of 22 elements. The intersection of set A and
set B consists of all elements that are member of both set A and B. The
result of the operation “intersection” is a set that is written as A ∩ B. The
symbol ‘∩’ is the intersection symbol. The definition of the intersection is
given by:
A ∩ B := { x : x ∈ A and x ∈ B }.

More than two sets

We have three sets 1CS, 1LI, and 1IMM consisting of all first-year students
of the three programmes CS, LI, and IMM, respectively. The union of these
three sets consists of all students that belong to at least one of the three sets.
The union of three sets A, B, and C is the set of exactly those elements that
belong to at least A, B, or C:
A ∪ B ∪ C := { x : x ∈ A or x ∈ B or x ∈ C }.
Something similar can done with the intersection. Take the following three
sets: HighlyIntelligent consisting of people with an IQ ≥ 140, Woman con-
6 Bhulai — Set Theory for Computer Science

sisting of all female persons, and Physics consisting of all students physics.
The intersection of these three sets is a set of people that belong to all three
sets simultaneously. Hence, the intersection is thus exactly the set of highly
intelligent female persons that study physics. The intersection A ∩ B ∩ C of
three sets A, B, and C is the set having elements that belong to each set A,
B, and C:
A ∩ B ∩ C := { x : x ∈ A and x ∈ B and x ∈ C }.
All these definitions can be easily extended to four or more sets.

1.4 The universe and the complement

Universal set
For any given problem, there is a specific type (a set) of objects of interest.
The set of stellar objects is contextually relevant when talking about stars,
planets, moons, and comets. The set of all books is relevant when studying
genres such as biographies, fiction, poetry, science, lexicons, etc. A universal
set of universe is a prescribed set of elements that is relevant for a specific
problem under study.

Complement
Besides the union and intersection operations, we now introduce a third oper-
ation. Given a universal set U and a subset A of U, we define the complement
of a set A as the set of all elements (of the universe!) that are not member of
A. We denote this set as A0 (sometimes one sees Ac ). For instance: let the
universe U consist of all four-letter words and let A be the set of all words
(in U!) with at least two vowels. Then, A0 is the set of all words (in U!)
with at most one vowel.

Difference of two sets

When the complement operation has been defined, one can also define the
difference or relative complement A \ B of two sets A and B as follows:
A \ B := A ∩ B0 .
We can also describe this difference directly as the set of elements that are
element of A but not of B. This description is also meaningful when no
universe is given. Occasionally, one encounters the operation symmetric dif-
ference A ∆ B of two sets A and B, defined by
A ∆ B := ( A ∪ B) ∩ ( A ∩ B)0 .
Elements of A ∆ B are exactly those objects belong to A or B, but not to
Chapter 1 — Sets 7

Figure 1.1: Venn diagram with 2 and 3 sets, respectively.

both (exclusive membership). Do not confuse this with the union of two sets.
The symmetric difference can also be expressed with the following formula:
A ∆ B := ( A \ B) ∪ ( B \ A).
Example: let the universe be given by the set of persons. We have two subsets
FEW (containing all students at the Faculty of Sciences) and CS (containing
all students computer science all over the world). Then the set FEW \ CS is
the set of all students at the Faculty of Sciences that do not study computer
science. Compare it with CS’ containing all students (wherever) who do not
study computer science.

1.5 Venn diagrams

There is a convenient method to visualize information on different sets si-
multaneously in a so-called Venn diagram. Such a diagram usually consists
of a rectangular areas with several ellipses inside. The different parts in the
rectangle represent with different sets.
In the left graph of Figure 1.1 one can see two sets A and B. The left
ellipse depicts set A, whereas the right ellipse depicts set B. The total area
within the ellipses is A ∪ B. The common area between the two ellipses is
A ∩ B. The outer area is ( A ∪ B)0 . The whole area within the rectangle is
the universe U.
Venn diagrams with three or more sets are possible as well (see the right
graph in Figure 1.1). The area that corresponds with a formula can be filled
8 Bhulai — Set Theory for Computer Science

Figure 1.2: Area corresponding to formula A ∪ ( B ∩ C ).

in grey. In Figure 1.1 several “atomic” areas have a formula added to them.
We additionally give an example with a formula with three sets in a more
complicated setting.
Example: The area that corresponds to the formula A ∪ ( B ∩ C ) consists
of five parts:
A \ ( B ∪ C ), ( A ∩ B) \ C, ( A ∩ C ) \ B, A ∩ B ∩ C, (B ∩ C) \ A
The first four parts are areas of A, and the fifth part is the area B ∩ C without
A. These parts are marked with a ‘+’ symbol in the next Venn diagram (see
Figure 1.2).

Application: equalities
A first application of Venn diagrams is to check if two sets described by
formulas are equal. Every formula can be represented in a Venn diagram and
consequently the areas described can be visually compared. For instance, we
have already depicted the set A ∪ ( B ∩ C ) in Figure 1.2. Let us now represent
the set ( A ∪ B) ∩ ( A ∪ C ), see Figure 1.3. The areas marked with an ‘x’ depict
A ∪ B, and those with ‘y’ depict A ∪ C. Hence, the areas marked with ‘x’
and ‘y’ depict ( A ∪ B) ∩ ( A ∪ C ). We can now see that this yields the same
area as in the previous figure. Hence, we can conclude that
A ∪ ( B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C ).

Application: Counting of elements A second application of the Venn diagram

is related to counting the number of elements. Every part of a Venn diagram
corresponds to a formula (e.g., A0 , A ∩ B, …). In this part one can also fill
in the number of corresponding elements in order to calculate the number of
Chapter 1 — Sets 9

Figure 1.3: Area corresponding to formula ( A ∪ B) ∩ ( A ∪ C ).

Figure 1.4: Counting the number of elements with a Venn diagram.

elements in the other parts. For instance, take a universe U with 15 elements.
There are two subsets A and B, of which A ∩ B has 3 elements, A has 10
elements, and B has 6 elements. How many elements does U have outside of
A ∪ B. In Figure 1.4 we have placed the sets as in left graph of Figure 1.1.
The number of elements in each part is written in the part itself.

We have first filled in the number of elements in A ∩ B, which equals 3.

Then, we can determine the number of elements in A ∩ B0 , which is 7, and
in B ∩ A0 , which is 3. Now, we can see that A ∪ B has exactly 13 elements,
and that the outer area ( A ∪ B)0 contains 2 additional elements.
10 Bhulai — Set Theory for Computer Science

1.6 The algebra of sets

In the previous section we demonstrated how Venn diagrams can be used to
check the equality of sets described by formulas. In practice this method is
only efficient for relatively easy formulas with at most three to four sets. For
more complex formulas one can take refuge to algebra of sets.

Algebra
The word “algebra” hints at the presence of operations that satisfy some
general principles. We have thus far seen three (main) operations with sets,
namely
union ∪ A ∪ B (union of A with B)
intersection ∩ A ∩ B (intersection of A with B)
complement 0 A0 (complement of A)
The operations “difference” and “symmetric difference” are considered sec-
ondary operations, since they can be expressed in the operations above. In
order to apply the operation complement, a universe U has been fixed. Sev-
eral rules for calculation are valid for these operations, such that one can
speak of an algebra of sets.
One may compare the situation at hand with a familiar one. Consider
the operations a + b, a · b, and − a with numbers. Arithmetic formulas can
often be expressed in more simple formulas using several basic principles and
rules, such as −( a + b) = (− a) + (−b) and ( a + b) · c = a · c + b · c.

Parentheses and priority

The three operations ∪ (union), ∩ (intersection), and 0 (complement) can
be used to build up more complex formulas in the algebra of sets. In many
formulas one needs parentheses ‘(’ and ‘)’ to avoid ambiguity, e.g., when one
needs to negate the sum of a and b, one has to write −( a + b) instead of
− a + b. Too many parentheses in a formula makes it more complex how-
ever. Therefore, one agrees on some priority rules to avoid a multitude of
parentheses:
• The operation “complement” always has highest priority;

• The operation “union” and “intersection” have equal second priority.

For instance, A ∪ B0 means A ∪ ( B0 ), because the complement has priority
over union. If one needs the complement of A ∪ B, one needs to write ( A ∪ B)0 .

Laws, the substitution rule

Chapter 1 — Sets 11

Commutativity: Idempotence:
A∪B = B∪A A∪A = A
A∩B = B∩A A∩A = A
Associativity: Complement:
A ∪ ( B ∪ C ) = ( A ∪ B) ∪ C A ∪ A0 = U
A ∩ ( B ∩ C ) = ( A ∩ B) ∩ C A ∩ A0 = ∅
Distributivity: De Morgan’s laws:
A ∪ ( B ∩ C ) = ( A ∪ B) ∩ ( A ∪ C ) ( A ∪ B)0 = A0 ∩ B0
A ∩ ( B ∪ C ) = ( A ∩ B) ∪ ( A ∩ C ) ( A ∩ B)0 = A0 ∪ B0
Identity: Domination:
A∪∅ = A A∪U = U
A∩U = A A∩∅ = ∅
Involution:
( A0 )0 = A
Substitution rule: to replace some part of a formula with an equal formula.
Table 1.1: Laws of the algebra of sets.

Just as in the algebra of numbers, a small number of principles are needed to

calculate set theoretic formulas. The laws are summed up in Table 1.1 and
are fundamental to the algebra of sets. They can be easily established with
the use of Venn diagrams. Remember, U is the universe and ∅ is the empty
set.

It is important to recognize a law when it occurs in a formula. One often

sees a formula with different notation. For example:
C ∩ ( D ∪ A) = (C ∩ D ) ∪ (C ∩ A)
is the second distributive law, in which A, B, and C are replaced with C,
D, and A, respectively. It is also possible that at the place of a symbol a
complete formula appears. For instance:
A0 ∪ ( B ∩ C ) = ( A0 ∪ B) ∩ ( A0 ∪ C )
is the distributive law in which the symbol A has been replaced with the
formula A0 .

The substitution rule

We have added, for sake of completeness, a fairly evident principle to the
list of laws: the substitution rule. This rule allows one the replace part of
12 Bhulai — Set Theory for Computer Science

formulas with equal formulas. An example of this is given by the equality

( A ∪ B) ∩ C = ( B ∪ A) ∩ C
which is valid because the right part of the formula can be obtained by
replacing A ∪ B with the equal formula B ∪ A (commutative law).

Arithmetic with sets

The laws of Table 1.1, together with the substitution rule, describe the
so-called algebra of sets. With the data in the table it is, in principle,
possible to do any calculation with sets. The following example resem-
bles the rule for arithmetic on the product ( a + b) · (c + d) for sets instead
of numbers in which the operations add/multiply has been replaced with
union/intersection. ( A ∪ B) ∩ (C ∪ D ) = (( A ∪ B) ∩ C ) ∪ (( A ∪ B) ∩ D )
= (( A ∩ C ) ∪ ( B ∩ C )) ∪ (( A ∩ D ) ∪ ( B ∩ D )).
In the second line, the parts ( A ∪ B) ∩ C and ( A ∪ B) ∩ D were replaced with
equal expressions according to the distributive laws.

1.7 Partitions
Families of sets
Remember that a set is a collection of imaginary objects. These objects can
be anything; we have seen a lot of examples already. We have not seen one
particular possibility, however: sets are themselves legitimate objects too,
and can consequently be collected as well. Because a “set of sets” does not
sound too well, we may alternatively use expressions like

• A collection of sets

• A family of sets

• A class of sets

We can collect all sets that we have introduced in the beginning of this
chapter:
{ Planets, DaysOfWeek, MainColours, Digits, PrimeNumbers, Months }.
This is a collection of 6 sets.

Splitting (partitioning) a set

Sets are often being split into smaller subsets. For instance, the set DaysOfWeek
can be split in a rather natural manner into the following two subsets.
Chapter 1 — Sets 13

Weekdays := { Monday, Tuesday, Wednesday, Thursday, Friday }

WeekendDays := { Saturday, Sunday }
First, we may observe that these subsets are disjoint, that is: they do not
have any element in common:
Weekdays ∩ WeekendDays = ∅.
More generally formulated: two sets A and B are disjoint when A ∩ B = ∅,
i.e., they do not have any elements in common. Second, we also observe that
the sets Weekdays and WeekendDays unite to the original set DaysOfWeek:
Weekdays ∪ WeekendDays = DaysOfWeek,
Each day of the week belongs to exactly one of the two subsets.
In a more complex situation, we may have several subsets P1 , P2 , P3 , . . .
which can be pairwise disjoint:
P1 ∩ P2 = ∅, P1 ∩ P3 = ∅, P2 ∩ P3 = ∅, etc.
For instance, the subsets
P1 := {2, 4, 6, 8}, P2 := {0, 1, 9}, P3 := {3, 5, 7}
are pairwise disjoint. We can also conclude that their union is the set Digits:
P1 ∪ P2 ∪ P3 = Digits.
Each digit belongs to exactly one of the sets P1 , P2 , and P3 .

Partition of a set
The previous observations form the essence of the notion of a “partition”. A
partition of a set V is a collection of non-empty subsets of V (the “parts”
of the partition) such that each element of V belongs to exactly one of the
parts. To put it differently, a partition of a set V is a family of non-empty,
pairwise disjoint subsets of V, such that the union is equal to V.
Examples: We have a partition
{ Weekdays, WeekendDays }
of the set DaysOfWeek into two parts Weekdays and WeekendDays. Every
day belongs to exactly one of these two parts. There is a partition
{{2, 4, 6, 8}, {0, 1, 9}, {3, 5, 7}}
of the set Digits into three parts. Every digit belongs to exactly one of these
three parts.

The summation formula

We take a closer look at the above mentioned partition of Digits. We know
that #Digits = 10. This number is now divided over the different parts of
the partition:
14 Bhulai — Set Theory for Computer Science

#{2, 4, 6, 8} = 4, #{0, 1, 9} = 3, #{3, 5, 7} = 3.

With respect to the given partition, we indeed find that 10 = 4 + 3 + 3. In
general, we can say that if the sets { P1 , P2 , . . . , Pn } form a partition of V,
then
#V = #P1 + #P2 + · · · + #Pn .
This is the summation formula for partitions.
Example: We have a partition of the set Alphabet into two subsets:
Vowels := { ‘a’, ‘e’, ‘i’, ‘o’, ‘u’ }
Consonants := { ‘b’, ‘c’, ‘d’, ‘f’, ‘g’, ‘h’, ‘j’, ‘k’, ‘l’, ‘m’, ‘n’, ‘p’, ‘q’, ‘r’, ‘s’, ‘t’, ‘v’,
‘w’, ‘x’, ‘y’, ‘z’ }
Now, we have #Alphabet = 26, and this is exactly the sum of the parts:
#Vowels + #Consonants = 5 + 21.

1.8 Exercises
1. Write the following sets in the curly-bracket notation by means of sum-
ming up the elements or by description. Choose the most convenient
of the two.
(a) The set of all integers that are divisible by 7 or 11.
(b) The set of all roots of the polynomial x3 − 6x2 + 11x − 6.
(c) The set of all solutions < x, y > of the set of equations
{
3x − y = 0,
(1.1)
x + 2y = 7.

2. In this exercise we work with the universe U := {1, 2, . . . , 30} with

three subsets named MultiplesOf2, MultiplesOf3, and MultiplesOf5
(described suggestively by the names). Give the formula for each of
the following sets using the union, intersection, and/or complement us-
ing the defined sets.
(a) Multiples of 2 that are not a multiple of 5.
(b) Multiples of 6.
(c) Multiples Odd numbers that are divisible by 3.
(d) { 30 }.

R
3. Take the set of real numbers as universe and study the following sets
A : = { x : 0 < x ≤ 2},
B : = { x : 1 ≤ x < 3}.
Chapter 1 — Sets 15

Describe the sets A ∪ B, A ∩ B, ( A ∪ B)0 , and ( A ∩ B)0 .

4. Make a Venn diagram for each of the two given formulas. Clearly
indicate which area is described by the formulas. Are the two sets
equal?
(a) ( A ∪ B) \ C, ( A \ C ) ∪ ( B \ C ).
(b) ( A ∆ B) ∩ C, ( A ∩ C ) ∆ ( B ∩ C ).
(c) A ∪ ( B ∆ C, ( A ∪ B) ∆ ( A ∪ C ).
(d) A0 ∆ B0 , ( A ∆ B)0 .
5. Show using Venn diagrams that
(a) ( A ∆ B) ∆ C = A ∆ ( B ∆ C ).
(b) ( A ∆ B) ∪ ( A ∆ B0 ) = U.
6. From an infinite number of nickels n (5 cents), dimes d (10 cents), and
quarters q (25 cents) three coins are sampled in sequence. A sample
such as “nickel, dime, nickel” is represented symbolically as “ndn”.
(a) Describe the universe U of all results and determine #U.
(b) Describe the subset V of all elements of U that together form a
sum of at least 50 cents and determine #V.
(c) Describe the complement V 0 of V and determine #V 0 .
7. A disease Z occurs in 5% of the population, and two symptoms A
and B appear to be related to the disease. In a study the following
conclusions are drawn. With people that are ill, 45% have symptom
A, 70% have symptom B, and 15% has neither of them. With healthy
people symptom A appears 10% of the time, symptom B appears 30%
of the time, whereas 65% none of the symptoms appear.
We apply the above information on an arbitrary population of 10.000
people. Depict the information for this group in one Venn diagram, and
use this to determine which diagnosis is the best predictor for disease
Z: symptom A, symptom B, of the two together.
Hint: for a given combination (0, 1, or 2) of symptoms, the ratio of
#(ill) / #(sample) is meaningful.
8. The law of absorption says
A ∩ ( A ∪ B) = A (with intersection),
A ∪ ( A ∩ B) = A (with union).
These equalities can be checked by using the algebra of sets on the left
part of the equality reducing it to the right part.
16 Bhulai — Set Theory for Computer Science

(a) Check the law of absorption for intersection.

(b) Check the law of absorption for union.

9. Check the following formulas using the algebra of sets. Formulas that
contain the symmetric difference ‘∆’ need to be converted into union
‘∪’, intersection ‘∩’, and complement first.
(a) ( A ∪ B) ∩ (C ∪ D ) = ( A ∩ C ) ∪ ( A ∩ D ) ∪ ( B ∩ C ) ∪ ( B ∩ D ).
(b) ( A ∩ B) ∪ (C ∩ D ) = ( A ∪ C ) ∩ ( A ∪ D ) ∩ ( B ∪ C ) ∩ ( B ∪ D ).
(c) A ∆ A = ∅ and A ∆ A0 = U.
(d) ( A ∆ B)0 = ( A ∩ B) ∪ ( A0 ∩ B0 ).
(e) A0 ∆ B0 = A ∆ B.

10. The set NLnumberplates contains all series of symbols in one of the
forms.
CC LL LL LL CC LL LL LL CC,

where an L is an arbitrary capital letter (more specific, a consonant)

and a C is an arbitrary digit.
(a) Let P1 be the subset of NLnumberplates consisting of all digits up
front. Define in analogy P2 (digits in the middle), and P3 (digits at the
end). Check that this is a partition of NLnumberplates.
(b) Use part (a) to calculate #NLnumberplates, a formula suffices.

11. Let W be the set of all three-letter words with at least one vowel. Take
for P1 the subset of all words with a vowel as first letter. Define P2 in
analogy (a vowel a ssecond letter) en P3 (a vowel as third letter).
(a) Determine #W, #P1 , #P2 , and #P3 .
(b) Is { P1 , P2 , P3 } a partition of W?

12. Given are the following sets (note that 0 ∈ N by definition).

N
P0 := {3n | n ∈ };
N
P1 := {3n + 1 | n ∈ };
N
P2 := {3n + 2 | n ∈ }.

Check that { P0 , P1 , P2 } is a partition of the set N of natural numbers.

1.9 Background

The founder of set theory is Georg Cantor (1845–1918). He developed

his ideas concerning sets around 1880. The symbols ‘∈’, ‘∪’, ‘∩’ were
Chapter 1 — Sets 17

introduced by the Italian mathematician Giuseppe Peano (1858–1932).

Venn diagrams are named after the British person John Venn (1834–
1923), who introduced the method in 1894. The laws on complement of
the union and the intersection are named of the British mathematician
Augustus DeMorgan (1806–1871).
Cantor’s set theory is also termed the naive set theory (zie [3] and
[6]). It is indeed a little ‘naive’: the extensive use of the possibilities to
construct sets has led to the paradox of Bertrand Russell (1872–1970)
from 1902. In this paradox the fact that sets are objects that can be
used as elements in new sets is used in a smart way. By doing so,
Russell defines a set R of all objects x for which it holds that x ∈ / x.
The answer to the question if R ∈ R is neither yes nor no.
The contemporary set theory is build up through axioms and avoids
all known paradoxes. Most of the axioms are related to the laws in the
algebra of sets in Table 1.1. For the purposes of this course, the naive
set theory suffices. Reference [9] is explicitly mentioned for computer
science students.
18 Bhulai — Set Theory for Computer Science
Chapter 2

Relations

Goals of this chapter:

• Correctly use finite lists of data, length of lists, and position of elements.
• Construct and use the Cartesian product of two or more sets.
• Construct and use binary or multi-set relations (data banks).
• Perform arithmetic with binary relations: compositions and inverses.
• Recognize important properties of binary relations (reflexivity, symmetry,
anti-symmetry, transitivity).

2.1 Lists, position, and length

Basic concepts, notation
A list is an enumeration of objects in a certain sequence. These objects are
the elements (members) of the list. Repetitions in lists are allowed. Lists are
denoted by enumerating the elements between angle brackets < . . . > in the
correct sequence:
PlanetList := <Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune>
DaysOfWeekList := <Monday, Tuesday, Wednesday, Thursday, Friday, Satur-
day, Sunday>
JustAList := <‘l’, ‘e’, ‘t’, ‘t’, ‘e’, ‘r’, ‘w’, ‘o’, ‘o’, ‘r’, ‘d’>
DigitList := <0, 1, 2, 3, …, 9>
NumberList := <0, 1, 2, …>

19
20 Bhulai — Set Theory for Computer Science

Note that the quotes around the letters (such as in ‘a’, ‘b’, …) are commonly
used (also in programming languages) in order not to confuse with one-letter
variables. Every thinkable object can be member of a list. A list of lists is
also a valid construction. For instance, a word is (essentially) a list of letters,
and one can construct a list of words. Also the empty list <> is allowed.
The lists in the above mentioned examples have been assigned to a name
(just as with sets) using the definition symbol ‘:=’.

Position and length

Every listed object has a position in the list, denoted by the sequence num-
ber of the element in the enumeration. For example, in the list of planets,
the planet Earth has the third position and Uranus the seventh. The total
number of positions is called the length of the list. The list with the days of
the week has length 7, en the empty list has length 0. Lists that are infinite
in length are also possible, e.g., the list NumberList of all natural numbers
in sequence of increasing numbers.
A list of length two is called a pair or a tuple, a list of length three is
called a triple. In general: a list of length n is called an n-pair. When the
lists is not too length, the elements are called the coordinates of the list.
The n-th coordinate is the element at position n. For example, in the pair
< a, b > the element a is the first coordinate, and b the second coordinate.
Example: a date consists of at least a number for the day and one for the
month, usually mentioned in this order. Think of, e.g., “2 October’ denoted
as 02-10. Mathematically seen, this is a pair < 02, 10 >. Hence, ‘10 October’
is represented as < 10, 10 > (remember that repetition is allowed in lists!).
One can also have an extensive date, such as ‘Thursday 2 October’. This is
a triple < Thu, 02, 10 >. Even more specific is ‘Thursday 2 October 2004’.
This is a 4-pair < Thu, 02, 10, 2004 >. In the same manner: time is usually
denoted by a list with hours and minutes. Often one also mentions the day,
week, etc. The 5-pair < Mon, 09, 45, 11, 30 > is a representation of the time
‘Monday between 9:45am and 11:30am’.

Equality of lists
Two lists L1 and L2 are equal, symbolically L1 = L2 , if they have the same
objects at the same position. Hence, the same number of objects are enumer-
ated in the same sequence. Consequently, equal lists have the same length.
Thus, we can see that
< 1, 1 >6=< 1 > < 02, 10 >6=< 10, 02 >.
In the first case the length of the two lists are different, in the second list the
Chapter 2 — Relations 21

order in which the elements are mentioned is different (‘2 October’ is not the
same as ‘10 February’).

2.2 Cartesian product

Recall that a set is a collection of objects. Lists are legitimate objects to be
“collected”. Think of the set of all lists of digits, or the set of all words, i.e.,
non-empty, finite lists of letters. We want to collect lists in a more structured
manner.
Example: a date such as “27 January” (or “27-01”) can be seen a pair (a
list of length two) < 27, 01 > with its first coordinate the number of the day,
and as second coordinate the number of the month. Hence, let us define two
sets:
DayNumbers := { 01, 02, 03, …, 31 },
MonthNumbers := { 01, 02, 03, …, 12 }.
We can create the set Data as the set of all pairs (lists of length two) with
its first coordinate an element of DayNumbers and its second coordinate an
element of MonthNumbers. A suggestive notation for this set of dates is:
DayNumbers × MonthNumbers.

Product of two sets

The set Data is an example of a Cartesian product of two sets, DayNumbers
and MonthNumbers. In general: a Cartesian product of two sets A and B is
defined as the set of alle pairs < a, b > with a ∈ A and b ∈ B, and is denoted
by A × B. Hence:
A × B := {< a, b > : a ∈ A and b ∈ B}.
The set A is the first factor and the set B is the second factor.
In Figure 2.1 the Cartesian product of {0, 12} and { a, b, c} is depicted.
The pairs are shown at the right location in the graph. The first coordinate
can be read from the horizontal axis, and the second coordinate from the
vertical axis.

Product of more than two sets

The date can be extended with a third number, the year. For this purpose,
introduce the set YearNumbers, and consider a date to be a triple with first
and second position as defined as before, and the third position an element
of the set YearNumbers. The set of all data that is established in this way,
is the Cartesian product of three sets:
22 Bhulai — Set Theory for Computer Science

Figure 2.1: Cartesian product {0, 1, 2} × { a, b, c}.

DayNumbers × MonthNumbers × YearNumbers.

A typical element of this set is the triple < 16, 07, 2004 >.
In general, one has n sets A1 , A2 , . . . , An , and one constructs the set of all
lists < a1 , a2 , . . . , an > of length n with element a1 from the set A1 , element
a2 from the set A2 , etc. The resulting Cartesian product is denoted by
A1 × · · · × An . This gives:
A1 × A2 × · · · × An := {< a1 , a2 , . . . , an > : a1 ∈ A1 , a2 ∈ A2 , . . . , an ∈ An }.
In this product Ai is the i-factor (i = 1, . . . , n). When one takes n times the
Cartesian product of the same set A, then one writes the Cartesian product
as An (A to the power n). This is the exponential notation.
Example: we have the sets DaysOfWeek, Hours, and Quarters := { 00,
15, 30, 45 }. An interval in a schedule can be seen as a 5-pair of the form
<day, start_hour, start_quarter, end_hour, end_quarter>.
Hence, one could have a lecture in the schedule as < Tue, 9, 00, 10, 45 >. The
set of such 5-pairs is the Cartesian product
DaysOfWeek × Hours × Quarters × Hours × Quarters.
The exponential notation can be found in the following examples:
R23 := R × R (the plane); a typical element is < 3, −2 >,
R := R ×4 R × R (the space); a typical element is < 3, −2, 5 >.
Alphabet (all 4-letter words); a typical element is <‘w’, ‘o’, ‘r’, ‘d’>.

The product formula

Suppose that two finite sets A and B are given. It is easily seen that there
are (#A) · (#B) ways to construct a pair < a, b > with a ∈ A and b ∈ B. As
Chapter 2 — Relations 23

a consequence:
#( A × B) = #A · #B.
This product formula also is valid for a Cartesian product with more than
two factors:
#( A1 × A2 × · · · × An ) = #A1 · #A2 · · · · · #An .
In case all sets A1 , A2 , . . . , An are equal to the same set A, the product for-
mula yields #( An ) = (#A)n . Hence, one can see that the exponential notation
for sets (An ) corresponds to the classical powers for numbers ((#A)n ).
Examples: There are 31 numbers for the days, and there are 12 numbers
for the month. How many pairs of the type
<daynumber, monthnumber>
can one construct? According to the product formula, the answer is 31 · 12 =
372. Depending on whether we have a leap year or not, we have six or seven
dates that do not make sense in the Cartesian product
Data := DayNumbers × MonthNumbers.
The set Alphabet of all small letters a to z has 26 elements. The set of all
four-letter words is Alphabet4 , and has according to the product formula
264 = 456, 976 elements.

2.3 Relations with n positions

Relations as sets
In practice, one almost daily encounters relations between a variety of sub-
jects: people, objects, time, places, …. For example, personal results of exams
relate certain subjects and certain grades, and can be represented as pairs of
the form
<subject, grade>.
A schedule for college consists of courses with corresponding teachers, time
schedules, number of lecture halls, en weeknumbers; more precisily, it consists
of 5-pairs of the form:
<week, time, teacher, course, room>,
and thus relates five objects of different types.
A relation sometimes is decribed in words (e.g., relations in family be-
tween brothers, aunts, …) or with formulas (e.g., relations between numbers
such as x2 + y2 + z2 = 1). Sometimes a relation is described by enumeration
of the elements. This is the case with the results of exams and with the
24 Bhulai — Set Theory for Computer Science

schedule of colleges.
Relations can thus be seen as sets. In the following definition n ≥ 2
represents a natural number. A relation with n factors is a set with n-pairs
(recall that these are lists of length n). The number n is also called the arity
of the relation R. if R is a subset of an n-ary Cartesian product A1 × · · · × An
of sets A1 , . . . , An , then R is a relation with n factors and the product set
A1 × · · · × An is called the type of the relation. In this case, we speak of a
typed relation.
For an n-ary relation R, the formula < a1 , . . . , an >∈ R is also read as
the n-pair < a1 , . . . , an > that is in relation R.

Examples: The personal results of the exam form a 2-ary (binary) relation
of type
Courses × Grades,
and the schedule of lectures is a 5-ary relation of type
Weeks × Times × Teachers × Courses × Rooms.
The relation between numbers given by x2 + y2 + z2 = 1 is a 3-ary relation
R
of type 3 .

Description of a relation
When seen as a set, a relation can also be defined by a description. This is
the case, e.g., for the relation
{< x, y, z > : x2 + y2 + z2 = 1}.
The description “x2 + y2 + z2 = 1” is also called the description of the rela-
tion. A relation R with n factors can therefore be represented as:
{< x1 , . . . , xm > : description of the relation for x1 , . . . , xn }.

Example: a date is a triple with as first coordinate an element from DayNum-

bers, second coordinate an element from MonthNumbers, and the third co-
ordinate an element from YearNumbers. There is a relation RealData con-
sisting of all triples that are legitimate dates according to the calendar. The
description of the relation is rather complicated with a lot of restrictions on
the number of the days in each month also depending on the leap year.

Databases
Relations of a given type also appear as “relational databases”. In their
simplest form, these are tables with several columns, one for each factor that
appears in the relation type. The schedule of the lectures are an example of
Chapter 2 — Relations 25

a database with five columns (a 5-ary relation). In column 1 we have the list
of weeks, in column 2 a time (day, start, and end). In column 3 the teacher
is listed, in column 4 the course, and in column 5 the room.

2.4 Binary relations

In this section we focus our attention to simple relations that are used a
lot in practice, namely, relations with arity 2. Such relations are also called
binary relations. When a binary relation R is assigned to a type, then this
is necessarily of the form A × B, where A and B are sets. In this situation,
we have R ⊆ A × B, and we can say that R is a relation between elements of
A en of B (in this order).
Example: the next relation describes which muses correspond to which
domains of art according to the old-Greek mythology.
{<Clio, History>, <Euterpe, Song>, <Euterpe, Elegiac poetry>,
<Thalia, Comedy>, <Melpomene, Tragedy>, <Terpsichore, Dance>,
<Erato, Lyric Poetry>, <Polyhymnia, Hymns>, <Urania, Astronomy>,
<Calliope, Epic poetry> }
This relation consists integrally of pairs and is therefore binary. This lengthy
enumeration can be better represented in a table.

Muse Domain
Clio History
Euterpe Song, Elegiac poetry
Thalia Comedy
Melpomene Tragedy
Terpsichore Dance
Erato Lyric Poetry
Polyhymnia Hymns
Urania Astronomy
Calliope Epic poetry

Different pairs can sometimes be joined on one line (see, e.g., the two domains
of Euterpe). Relations within a family are often binary relations:
IsBrotherOf := { < x, y > : x is a brother of y }.
After the introduction of the set People, one can define the relation IsBroth-
erOf to be of type People × People. Another example is
FollowsCourse := { < x, y > : x ∈ Students and y ∈ Courses and x follows y }.
26 Bhulai — Set Theory for Computer Science

The relation FollowsCourse is of type Students × Courses.

Infix notation
With binary relations we use the so-called infix notation:
x R y instead of < x, y >∈ R.
In combination with a good choice for the name, the notation for the relation
is suggestive:
x IsBrotherOf y instead of < x, y >∈ IsBrotherOf
x FollowsCourse y instead of < x, y >∈ FollowsCourse
The infix notation is very common in mathematical relations such as IsE-
qualTo (symbol =) and IsSmallerThanOrEqualTo (symbol ≤). An addi-
tional advantage is that the information on series of pairs can be represented
more efficiently: compare the following:
52 ≤ 3 · 9 ≤ 85/3 ≤ 30,
with the more tedious
< 52 , 3 · 9 >∈ IsSmallerThanOrEqualTo,
< 3 · 9, 85/3 >∈ IsSmallerThanOrEqualTo,
< 85/3, 30 >∈ IsSmallerThanOrEqualTo.

2.5 Different representations of binary relations

In order to work effectively with relations, a good representation is important.
For instance, in Calculus one has been taught to depict real-valued functions
with graphs. Mathematical concepts such as maximum, minimum, zero,
extreme points get a more visual and geometric meaning. In this section we
discuss three representations that are useful for finite binary relations.

First representation: Venn diagrams

Suppose that a binary relation R ⊆ A × B is given for finite sets A and B.
Thus: R is of type A × B. The sets A and B can be represented by the usual
ellipse, but apart from each other. Elements of A and B are depicted by a
dot in the corresponding ellipse. Now, an arrow is drawn from dot a ∈ A to
a dot b ∈ B when a and b are related in R, i.e., < a, b >∈ R.
The relation, depicted in Figure 2.2, can be summarized through enumer-
ation by
{< p1 , q1 >, < p1 , q5 >, < p3 , q1 >, < p3 , q3 >, < p4 , q4 >, < p5 , q6 >,
< p6 , q5 >}.
and it is one of type A × B with A := { p1 , p2 , . . . , p6 } and B := {q1 , q2 , . . . , q6 }.
Chapter 2 — Relations 27

Figure 2.2: Representation with a Venn diagram.

Figure 2.3: A directed graph with four vertices.

Second representation: directed graphs

A directed graph (or a digraph) is a set of vertices connected with edges. The
vertices are usually represented by circles. A relation of type A × B with A
and B finite can be represented by a directed graph by drawing a vertex for
every element of A ∪ B. An edge from vertex a ∈ A to vertex b ∈ B denotes
that < a, b > are in relation. This representation is used a lot when the
types A and B are not explicitly given, or when A = B.
The relation represented in Figure 2.3 is
{< a, a >, < b, b >, < c, c >, < d, d >, < a, b >, < b, d >, < d, a >}
and is a relation of type { a, b, c, d}2 .

Third representation: 0/1 matrices and relation tables

Suppose that a relation R of type A × B is given with A and B finite sets,
28 Bhulai — Set Theory for Computer Science

i.e., R ⊆ A × B. We provide an order to the elements of A and B (remember

that a set does not have an order for enumeration). Now, we can create a
relation table, of which the rows are tied to the elements of A in the specified
order, and of which the column are tied to the elements of B in the specified
order. We place a ‘1’ at the entry for row a ∈ A and column b ∈ B when
a R b and a ‘0’ otherwise. Alternatives are to put ‘T’ (of ‘true’) instead of ‘1’,
and ‘F’ (of ‘false’) instead of ‘0’. Another alternative is to place ‘+’ instead
of ‘1’, and to place ‘-’ instead of ‘0’. The matrix representation of R follows
from deletion of the names for the rows and the columns. This matrix is also
called the relation matrix of R.
Example: Take the following two sets:
A := { a, b, c, d} B := {1, 2, 3, 4},
with the provided order of enumeration. In the schemes that follow, we first
give the relation table of the binary relation R of type A × B en next we
provide the matrix representation (the relation matrix). of R by deletion of
the names for the rows and columns. By a 0/1 matrix one understands a
rectangular scheme of zeros and ones.
 
R 1 2 3 4 1 2 3 4
a 0 1 0 1  0 1 0 1 
 
Relation table: b 0 0 0 0 Matrix representation: 
 0 0 0 0 

c 1 1 1 1  1 1 1 1 
d 0 0 1 1 0 0 1 1
In this example one can see that a R 2 is valid, but not a R 1.

2.6 Some constructions with binary relations

Inverse relation
Consider the relation R := IsParentOf between people. With the infix no-
tation x R y we denote that x is parent (father or mother) of y, in correct
notation < x, y >∈ IsParentOf. Now, a pair is a list, and thus sensitive for
order: x first, and then y. It is thus a different relation than S which relates
y to x. This relation has as description:
yRx holds exactly when x IsParentOf y.
Which relation S is this? Common sense gives the answer:
y IsChildOf x holds exactly when x IsParentOf y.
We call the relation IsChildOf the inverse of the relation IsParentOf.
In general, the inverse relation S of a relation R is constructed by reversing
all pairs in relation R: x R y gives y R x, and vice verse. The ‘neutral’ notation
Chapter 2 — Relations 29

Figure 2.4: Inverse relation R−1 of R.

R−1 (read: the inverse of R) is common for the inverse relation of R. Hence:
R−1 := {< x, y > :< y, x >∈ R}.
For instance, the inverse relation of IsParentOf is the relation IsChildOf:
(IsParentOf)−1 = IsChildOf.

Example: Consider the relation LivesIn of type Persons times Places. When
Jan lives in Amsterdam, this can be represented in the following two ways.
Jan LivesIn Amsterdam <Jan, Amsterdam>∈ LivesIn.
Reversely, one could say that Amsterdam is the residence place of Jan. The
relation that appears can be called IsResidenceOf:
Amsterdam IsResidenceOf Jan <Amsterdam, Jan>∈ ResidenceOf.
Conclusion: the inverse relation of LivesIn is the relation IsResidenceOf, en
we can represent this by
(LivesIn)−1 = IsResidenceOf.
The type of the inverse relation IsResidenceOf is Places × Persons. Recall
that, in comparison with the type of the relation LivesIn, the factors are in
reversed order. This is a general phenomenon: if R is of type A × B, then
R−1 is of type B × A. As a side note: it is a fairly easy observation that the
inverse of the inverse yields the original relation. Thus: ( R−1 )−1 = R.

Representation with Venn diagrams

If the relation R is given by means of a directed graph or by means of a Venn
diagram, then the inverse relation R−1 is given by reversing the arrows in the
graph (see Figure 2.4).
30 Bhulai — Set Theory for Computer Science

Representation with matrices

If the relation R is given in matrix form, then the inverse relation R−1 is
given by transposing the matrix, i.e., change the rows into columns and vice
verse, with the same order. For example: take the two sets
A := { a, b, c, d}, B := {1, 2, 3, 4},
with the given order of enumeration. Furthermore, we define the relation R
by
{< a, 2 >, < a, 4 >, < c, 1 >, < c, 2 >, < c, 3 >, < c, 4 >, < d, 3 >, < d, 4 >}
of type A × B from the example of the third representation. The matrices of
R and R−1 are given by
   
0 1 0 1 0 0 1 0
 0 0 0 0   1 0 1 0 
R:
 1
, R −1 : .
1 1 1   0 0 1 1 
0 0 1 1 1 0 1 1
In the left matrix, the rows correspond to a, b, c, d (in this order). In the right
matrix, the rows corresponds to 1, 2, 3, 4 (in this order). The rows of the left
matrix have become the columns of the right matrix and vice verse.

Composite relation
Expressions such as “the uncle of a friend” and “the grandson of a neighbour
of an aunt” are not unusual in conversation. These are, in fact, a series of
relation or composite relations. Let us study this in more detail.
Example: Focus on the relation of all pairs < x, y > with description “x
is an uncle of a friend of y”. Assume that Aad is uncle uncle of Bea, and that
Bea is a friend of Cor. We can represent that in two ways:
Aad IsUncleOf Bea <Aad, Bea>∈ IsUncleOf,
Bea IsFriendOf Cor <Bea, Cor>∈ IsFriendOf.
We now make a composition. Aad is an uncle of a friend of Cor.
the pairs <Aad, Bea> and <Bea, Cor> are chained to <Aad, Cor>.
A general description of this phenomenon is as follows. Let R and S be
given relations. The composition of R after S exists exactly of those pairs
< x, z > that result when there is an ‘intermediate’ element y such that the
pair < x, y > in S can be ‘chained’ to the pair < y, z > in R:
the pairs < x, y > and < y, z > are chained to < x, z >.
The notation for this composite relation is R ◦ S, to be read as R after S.
The operator used for this has the symbol ‘◦’, and the operator is called the
composition operator. The definition for the composite relation is
Chapter 2 — Relations 31

R ◦ S := {< x, z > : there is a y with x S y and y R z}.

First an S-pair, then an R-pair chained to each other. Hence, the reason to
read R after S.
The example of IsFriendOf as R and IsUncleOf as S yields
IsFriendOf ◦ IsUncleOf :=
{< x, z > : there is a y with x IsUncleOf y and y IsFriendOf z }.
Hence, we find that <Aad, Cor>∈ IsFriendOf ◦ IsUncleOf. The intermediate
element is Bea. There could be more than one intermediate elements: maybe
Cor has two friends that are nieces of each other, with Aad as common uncle.
Please do note that difference in description and notation:
• An uncle of a friend
• IsFriendOf after IsUncleOf
• IsFriendOf ◦ IsUncleOf
The order of the components when using ◦ is quite essential.

Here are some other examples:

IsMarriedTo ◦ IsParentOf = IsParentInLawOf
IsParentOf ◦ IsMarriedTo = IsParentOf.
Note that the incorrect use of the composition can lead to absurd relations.
For instance, the composition of ‘the residence of a teacher’ is meaningful,
but the composition ‘the teacher of a residence’ is the empty relation.

Representation with Venn diagrams

If R is a relation of type B × C, and S is a relation of type A × B, then
the situation for a composite relation R ◦ S can be depicted well with Venn
diagrams. A pair < a, c > with a ∈ A and c ∈ C are in relation R ◦ S exactly
then if there is a path of arrows starting in a leading to c via an element of
b ∈ B. In Figure 2.5 there are exactly 8 pairs in the composite relation.
As a side note. When the relations R and S are given by matrices, then
the composite relation R ◦ S is in essence given by the matrix product S with
R (denoted by S · R). This is not exactly a relation matrix, since there could
be entries that are greater than 1. These entries need to be replaced by a 1.

Multi-composite relations
The result of a composition is a new binary relation, and therefore the process
of composition can be repeated. A composition turns out to be associative:
for the composition of three relation R, S, and T
( R ◦ S ) ◦ T = R ◦ ( S ◦ T ).
32 Bhulai — Set Theory for Computer Science

Figure 2.5: Composite relation R ◦ S with a S b R c.

Take as example the description “the grandson of a neighbour of an aunt”.

It is given that
Aart IsGrandsonOf Betty <Aart, Betty>∈ IsGrandsonOf
Betty IsNeighbourOf Carla <Betty, Carla>∈ IsNeighbourOf
Carla IsAuntOf David <Carla, David>∈ IsAuntOf
When chained together, we get: Aart is grandson of a neighbour of an aunt of
David. Hence, <Aart, David>∈ IsAuntOf ◦ IsNeighbourOf ◦ IsGrandsonOf.
The intermediate elements are Betty and Carla. This multi-composite rela-
tion can be build up in two steps, and in two manners. First, Betty is a
neighbour of an aunt of David (the intermediate element is Carla):
<Aart, David>∈ (IsAuntOf ◦ IsNeighbourOf) ◦ IsGrandsonOf
with intermediate element Betty. Second, Aart is grandson of an aunt of
Carla (the intermediate element is Betty):
<Aart, David>∈ IsAuntOf ◦ (IsNeighbourOf ◦ IsGrandsonOf)
with intermediate element Carla. We can see that the composition is asso-
Chapter 2 — Relations 33

ciative:
(IsAuntOf ◦ IsNeighbourOf) ◦ IsGrandsonOf =
IsAuntOf ◦ (IsNeighbourOf ◦ IsGrandsonOf).

Inverse of composite relations

The composition of two binary relations is a binary relation. One can there-
fore study the inverse of this relation. There is a simple rule: the inverse
of the composite relation is the composite in reverse order of the inverse
relations:
( R ◦ S ) −1 = S −1 ◦ R −1 .
Example: Take the relation with the description “a residence of the teacher
of”. Given is that < a, b >∈ IsResidenceOf and < b, c >∈ IsTeacherOf. This
means that a is a residence of b, who is teacher of c, and consequently, a is a
residence of a teacher of c; in formal notation
< a, c >∈ IsTeacherOf ◦ IsResidenceOf.
The inverse relations can be named as follows:
LivesIn = (IsResidenceOf)−1
IsStudentOf = (IsTeacherOf)−1
The inverse of the composite relation now expresses that c is a student of
someone that lives in a:
< c, a >∈ LivesIn ◦ IsStudentOf = (IsResidenceOf)−1 ◦ (IsTeacherOf)−1
= (IsTeacherOf ◦ IsResidenceOf)−1 .
Indeed: c is a student of b, and b lives in a.

2.7 Relations in a set

Relations in a family, such as ‘brother’ and ‘uncle’ are binary relations of the
type People × People and the relation IsSmallerThan is of the type × . R R
In all these cases the type of the relation is the square of the set. There is a
special name for this phenomenon. If V is a set, then a relation of the type
V × V is called a relation in V.
Examples: The relation IsBrotherOf is a relation in the set of People.
R
The relation IsSmallerThan is a relation in the set . The relation LivesIn
is of type People × Places, and can therefore not be seen as a relation in a
set.
In this section, we are interested in the following properties of a relation
R in a set V.
34 Bhulai — Set Theory for Computer Science

Reflexivity: every element of V is with itself in relation R.

Symmetry: if an element of V is in relation R with a second element of V,

then the second element is in relation R with the first element.

Anti-symmetry: if an element of V is in relation R with a second element of

V, and the second element is in relation R with the first element, then the
two elements are the same.

Transitivity: if an element of V is in relation R with a second element of V,

and the second element is in relation R with a third element of V, then the
first element is in relation R with the third element.

A convenient reformulation of these descriptions is given in the language of

logic. Note that it can happen that one element of V is in relation R with
itself, but a different element of V is not. The relation R is then not reflexive.
Similar statements can be made for the other three properties as well.
The table hereafter summarizes the properties together with an intuitive
example of a relation that satisfies the property. In every example, we con-
sider a relation in a set of all people.

Property Example
Reflexivity Knows
Symmetry IsFriendOf
Anti-symmetry IsParentOf
Transitivity IsDecendentOf

• The relation Knows is reflexive, since for every person x it holds that
x Knows x.

• The relation IsFriendOf is symmetric: if x IsFriendOf y, then also y

IsFriendOf x.

• The relation IsParentOf is anti-symmetric: the case where x IsParentOf

y and y IsParentOf x as well does not occur.

• The relation IsDecendentOf is transitive: if x IsDecendentOf y and y

IsDecendentOf z, then also x IsDecendentOf z.
Chapter 2 — Relations 35

2.8 Exercises
1. Product of sets.

(a) For a specific game one has to throw three dice. The first one has
the usual number on each face, the second has a different colour
on each face (say, black, wit, red, yellow, green, and blue), and
the third has a sign ‘♥’ on three faces and a ‘♣’ on the others.
Describe the set of possible throws in this game as a Cartesian
product. How many different outcomes are there?
(b) Given are the sets
A := {b, c, f }; B = { a, b, c, e, f }; C = { a, c, d}; D = { a, c, e}.
How many elements are there in the set ( B × C ) ∩ ( A × D ), and
how many elements are there in the set ( B × C ) ∩ ( A × D )0 ?
(c) Check with the outcomes of part (b) that
#(( B × C ) ∩ ( A × D )) + #(( B × C ) ∩ ( A × D )0 ) = #( B × C ).

2. Given is a set Throws := Number × Number, with Number := {1, 2,

…, 6}, together with a collection of eleven subsets P2 , . . . , P12 . The set
with number k (for k = 2, . . . , 12) is defined as
Pk := {< o1 , o2 > : o1 , o2 ∈ Number, o1 + o2 = k }.

For example, P3 is the set with all throws having a sum of 3. Do

the subsets for a partition of the set V? Respond with ‘yes’ or ‘no’;
however, please explain when the answer is ‘no’.

3. Given are two relations R and S in the set { a, b, c, d} depicted by the

following graphs.

Figure 2.6: Relation R (left) and relation S (right).

36 Bhulai — Set Theory for Computer Science

(a) Give a description by enumeration of the relations R and S. Also

give a representation by 0/1 matrices of both relations.
(b) Draw the directed graphs corresponding to R ◦ S and S ◦ R. Sys-
tematically determine if the relations are reflexive, symmetric,
anti-symmetric, en/or transitive.
(c) Is R ◦ S = S ◦ R?

4. R and S are two relations in a set with 4 elements in enumerated order.

Determine the matrix of R ◦ S when R and S are described as follows
in matrix form:
   
0 1 0 0 0 0 0 1
 0 1 0 0   1 1 0 1 
R:
 0
 S: 
0 0 1   0 0 0 1 
1 0 0 0 0 0 1 1
Hint: Number the elements in the give order from 1 to 4. Take two
numbers i, j ∈ {1, 2, 3, 4} and investigate if i ( R ◦ S) j as follows. Fix
row number i of S and column number j of R, and check if in one of
more positions there is a common ‘1’.

5. In a set of people are given the relations IsParentOf and IsIdenticalWith

(the relation with exclusively pairs < x, x > with x a person). In the
following parts one is asked to construct new relations, based on the two
relations and the operations composition, inverse, union, intersection,
complement of relations.

(a) The relation IsGreatGrandChildOf

(b) The relation IsSiblingOf
(c) The relation IsCousinOf

6. In this exercise we consider a date as an element of the Cartesian prod-

uct
DayNumbers × MonthNumbers × YearNumbers,

of which the factors are defined as follows.

DayNumbers := {01, 02, …, 31},
MonthNumbers := {01, 02, …, 12},
YearNumbers := {x : 1990 ≤ x }.
Chapter 2 — Relations 37

The set Data consists of all real data according to the calendar. Con-
sider a binary relation Period that consists of all pairs of dates <
d1 , d2 > from Data with d1 ≤ d2 (i.e., date d1 appears before date
d2 or is equal to it) and the difference d2 − d1 is at most 21 days.

(a) Which data pairs < x, y > satisfy < x, y >∈ Period?
<< 08, 10, 1998 >, < 20, 09, 1998 >>;
<< 10, 10, 1998 >, < 01, 11, 1998 >>;
<< 10, 11, 1998 >, < 01, 12, 1998 >>.
(b) Is the relation Period reflexive? Symmetric? Anti-symmetric?
Transitive?
(c) What does the relation Period ◦ Period mean?

7. A library registers every loan and the period for the loan. This admin-
istration is seen as a 5-ary relation Administration of type
Members × Books × Out × Back × Data,

of which Members is the set of all library members, Books is the col-
lection of all books in the library, Out := Data, and Back := Data (see
previous exercise for a definition of Data). It is the intention that a
5-pair such as
<Jan, NiceBook, < 15, 09, 1998 >, < 04, 10, 1998 >, < 24, 09, 1998 > >
represents a certain case, namely, that Jan borrowed the book NiceBook
on 15-09-98, and has not delivered it yet on 24-09-98, and that Jan is
allowed to keep the book until 04-10-98. One can imagine that every
day the administration is processed with the mutations of the previous
day and that old files are never thrown away.

(a) Suppose that < x1 , x2 , x3 , x4 , x5 >∈ Administration. What can

one say about x3 , x4 , x5 ?
(b) Give a precise description, with the use of the relation Adminis-
tration, of the following (intuitive) relations.
i. The relation Borrowed of type Books × Data.
ii. The relation Available of type Books × Data.
iii. The relation InViolation of typeMembers × Books × Data.
(c) Discuss the possibility of two 5-pairs that are element of Admin-
istration but only differ in one position.
38 Bhulai — Set Theory for Computer Science

2.9 Background

The name ‘Cartesian’ refers to the French philosopher and mathemati-

cian René Descartes (1596–1650), who introduced the coordinate sys-
tem that allowed to compare points in the plane to two real numbers
< x, y >. This reduced the ‘difficult’ geometry of the plane to the ‘easy
calculus of real numbers.
The rather sober definition of a binary relation as a set of pairs is
due to the logician A. DeMorgan (British, 1806–1871) and C.S. Peirce
(American, 1839–1914). In 1864 the operations for the inverse and the
composition of two binary relations were described by DeMorgan. And
in 1870 the logic of binary relations was sketched by Peirce. Around
1940, the famous Polish logician Alfred Tarski (1902–1983) developed
the general relation algebra that could describe, apart from the oper-
ations union, intersection, and complement, also the composition and
inverse of binary relations.
Relation algebra is commonly used in semantics of (imperative) pro-
gramming languages. The idea behind this is that a computer instruc-
tion in a given state (memory value) is transformed into a new state (a
different value in memory), and thus creates a binary relation. Consec-
utive instructions lead to composite relations. The first three chapters
from [11] are a representation of the contents of this chapter in the
language of relation algebra. Reference [9] is more at the level of this
book.
Relations of higher arity are rare in mathematics, but are relevant for
the study of relational databases (E.F. Codd, 1970). The columns
in the relation table are called attributes in this context. There are
special languages to perform operations on relations of high arity. A
well-known language is SQL (Structured Query Language), developed
in the seventies (see [5], [7]). This language is used in modern database
programs.
Chapter 3

Relations: Partial Order

Goals of this chapter:

• Recognize a partial order or a total ordering and their properties.

• Display relations for orderings by Hasse diagram, and vice verse, read
information on relation for orderings from a Hasse diagram.
• Reproduce the most frequently used examples for relations for orderings
(ordering for numbers, inclusion of sets, Cartesian and lexicographic prod-
ucts).
• Create simple proofs on partial orders by a strategy and a chain of valid
arguments.
• Find maxima and minima in subsets of a partially ordered set.

3.1 Refresher: binary relations

Basic concepts
In Chapter 2 we introduced the concept of a relation as a set of n-pairs for
a specific integer n ≥ 1. The number n is called the arity of the relation.
Relations are often a subset of a Cartesian product of the form
V1 × V2 × · · · × Vn .
This product set is called the type of the relation. An element of a relation
of the type V1 × V2 × · · · × Vn is thus an n-pair (list of length n, n-pair)
< a1 , a2 , . . . , a n >,

39
40 Bhulai — Set Theory for Computer Science

with a1 ∈ V1 , a2 ∈ V2 , . . . , an ∈ Vn .
We then restricted ourselves to binary (2-pairs) relations. Such relations
consist of pairs and are of type V1 × V2 . Binary relations can be represented
by means of directed graphs or by means of matrices. Next, we further
restricted ourselves to relations in a set V, i.e., relations of the type R ⊆
V × V.
Relations are sets. The notation < x, y >∈ R for a binary relation R is
thus meaningful and expresses that x and y are in relation R. We denote
this as x R y (infix notation). Relations can (as with sets) be described by
enumeration or by description. For instance, the so-called circle relation is
the relation in the set R of real numbers, and is given by
R := {< x, y > : x2 + y2 = 1}.
(This relation is called circle relation because it exactly consists of points
R
< x, y > on the unit circle in the plane 2 . The phrase x2 + y2 = 1 is the
description of the relation R. It is common to write the relation as
xRy :↔ x2 + y2 = 1.
The symbol ‘:↔’ (colon, double implications) refers to an equivalence re-
lation. There is some analogy with the symbol for assignment ‘:=’, which
refers to a defined equality.

Possible properties of a relation in a set

For relations in a set we have introduced four concepts in Chapter 2
Reflexivity, Symmetry, Anti-symmetry, Transitivity. We formulate the prop-
erties here once again, only this time in logic form. We start from a relation
R of type V × V.

Property Formal definition Example

Reflexivity ∀ x ∈ V, x R x IsEquallyOldAs
Symmetry ∀ x, y ∈ V, ( x R y → y R x ) IsFriendOf
Anti-symmetry ∀ x, y ∈ V, ( x R y ∧ y R x → x = y) IsParentOf
Transitivity ∀ x, y, z ∈ V, ( x R y ∧ y R z → x R z) IsDecendentOf

In this and the next chapter we shall focus on a particular set of three of the
four properties.
reflexivity + anti-symmetry + transitivity (this chapter)
reflexivity + symmetry + transitivity (next chapter)
Chapter 3 — Relations: Partial Order 41

3.2 Relations for orderings

Definition
A relation R in a set V is called a partial order when R satisfies the following three
properties:
reflexivity, anti-symmetry, and transitivity.
The collection of the set V together with the partial order R is called a
partially ordered set. The specification “partial” is often omitted.

Example: Consider the natural ordering in the alphabet. We previously

defined the 26 letters of the alphabet as the following list:
<a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z>.
One can see this as a description for a partial order between the 26 elements:
x ≤ y ↔ x is before y in the enumeration or x is equal to y.

N
Example: Consider the natural ordering of numbers. In the set of natural
numbers the natural ordering ≤ is a partial order. We list the three properties
that are required for this relation.
(i) (reflexivity) ∀ x ∈ N, x ≤ x.
(ii) (anti-symmetry) ∀ x, y ∈ N, ( x ≤ y ∧ y ≤ x → x = y).
(iii) (transitivity) ∀ x, y, z ∈ N, ( x ≤ y ∧ y ≤ z → z ≤ z).
N Z
Instead of the set , one can also focus on the set of integers and on ≤ for
the natural ordering for integers. This is also a partial order. The natural
Q
ordering in the set of rational numbers and the natural ordering in the set
R of real numbers are partial orders as well.

Example: Consider the relation IsDivisorOf between positive numbers

Let P be the set of all integers > 0:
P := {z : z ∈ Z and z > 0} = N \ {0}.
The relation IsDivisorOf (with symbol ‘|’) in P is described as follows:
x |y :↔ ∃z ∈ P, x · z = y.
The relation ‘|’ is a partial order in P.

Example: Consider the power set and the ordering through inclusions. Re-
member (see Chapter 1) that a set is a collection of arbitrary objects. There-
fore, a set itself is a legitimate object and can be collected in a ‘larger’ collec-
tion. For instance, a partition of a set V is a set of subsets of V (with some
additional properties). When V is a set, then there exists a set of all subsets
of V:
42 Bhulai — Set Theory for Computer Science

P (V ) : = { X : X ⊂ V }.
This set is called the power set of V. When X and Y are subsets of V (i.e.,
when X, Y ∈ P (V )), then X ⊆ Y means that X is a subset of Y. Then, it is
not difficult to recognize the infix notation in this for a binary relation with
the symbol ⊆. This leads us to this example: inclusion is a relation in P (V ),
and, more specifically, it is a partial order. We list the three properties for
this relation:
(i) (reflexivity) ∀ X ∈ P (V ), X ⊆ X.
(ii) (anti-symmetry) ∀ X, Y ∈ P (V ), ( X ⊆ Y ∧ Y ⊆ X → X = Y ).
(iii) (transitivity) ∀ X, Y, Z ∈ P (V ), ( X ⊆ Y ∧ Y ⊆ Z → X ⊆ Z ).

Notation and terminology

Relations for orderings are a common phenomenon in daily life: alphabetic
orders, small and large numbers, etc. Relations for orderings are used quite
frequently in mathematics and in theoretical computer science. Traditionally,
the smaller than/equal to symbol ‘≤’ or the symbol ‘⊆’ is used to describe
a partial order. The sentence ‘x ≤ y’ can be phrased in different ways. We
list some common expressions:
‘x is smaller than or equal to y’ ‘y is greater than or equal to x’
‘x comes before y’ ‘y comes after x’

Graphical representation with Hasse diagrams

A partial order defined on a finite set can, as with any binary relation, be
depicted by a directed graph. In case of a partial order is it possible to draw
the graph such that the order can be read ‘from below to top’. For example,
in Figure 3.1 we see that
a ≤ d, b ≤ d, d ≤ f.
In order to depict the information as clearly as possible, the reflexive part of
the relation is not drawn, and one includes sufficient arrows for the relations
to reconstruct the transitive relations. For example, through the arrows
a→d→ f
we can reconstruct the (omitted) arrow a → f . This ‘thinned’ representation
is called the Hasse diagram of a partial order. The Hasse diagram thus has
the minimum information to completely reconstruct the partial order.
In order to construct this diagram, one needs to ‘thin’ the information to
the strict minimum. Here is a precise recipe:
For every point x:
1. Let Gx := {y : x < y}.
Chapter 3 — Relations: Partial Order 43

Figure 3.1: A Hasse diagram.

2. For every y ∈ Gx: let Gy := {z : y < z} and Gx := Gx \ Gy.

3. For every y ∈ Gx: draw an arrow between x → y in the Hasse diagram.
Additional info: for a given y ∈ Gx and z ∈ Gy, we have x < y < z. The
arrow x → z can be omitted, because the information can be recovered from
x → y → z.

Comparability and total ordering

When a and b are two elements in a partially ordered set for which a ≤
b ∨ b ≤ a, then the two elements a and b are comparable in the given order.
We already saw that in the natural ordering in each of the systems of numbers
NZQ
, , , and R is a partial order. In fact, every system of numbers has the
property that two numbers are comparable. In the following definition we
give this property a name.
A partial order in a set V is called a total ordering (or a linear ordering)
on V when
∀ x ∈ V, ∀y ∈ V, ( x ≤ y ∨ y ≤ x ).
A partial order is thus total when all elements are comparable to each other.
The natural ordering in a standard system of numbers is a total ordering.
The Hasse diagram of a total ordering is a sequence of arrows. Hence, the
name ‘linear ordering’ that is used as well.
The order, drawn in the Hasse diagram in Figure 3.1 is not total, because
the elements a and b are not comparable. For a different example, consider
the power set of V := {0, 1}. This set consists of four elements
∅, {0}, {1}, {0, 1}.
44 Bhulai — Set Theory for Computer Science

Figure 3.2: Hasse diagram of N with the natural ordering.

The following holds: {0} 6⊆ {1} and {1} 6⊆ {0}, i.e., the elements {0} and
{1} are not comparable for inclusion. More generally, one can conclude that
the ordering by inclusion of P (V ) is not a total ordering as soon as V has
two or more elements.

Strict ordering
A partial order is reflexive: equality is included. With every partial order ≤
comes a strict partial order <, defined by
x < y :↔ x ≤ y ∧ x 6= y.
The relation < that one gets is also called the small-than relation. A strict
ordering comes forth out of a partial order by omitting the reflexive part.
When reversed, a partial order can be constructed by adding the reflexive
part to a strict ordering:
x ≤ y ↔ x < y ∨ x = y.
The most frequent ways in which the sentence x < y are phrased are:

‘x is (strictly) smaller than y’ ‘y is (strictly) greater than x’

‘x comes strictly before y’ ‘y comes strictly after x’

A relation R in a set V is called anti-reflexive if no element of V is in relation

with itself. Formally: ∀ x, ¬ x R x. We prove the following:

Theorem 3.1. Given is a partial order ≤ in a set V and the corresponding

strict ordering <. Then, the relation < is anti-reflexive, anti-symmetric, and
transitive.

Proof. Checking the anti-reflexivity is left as an exercise for the reader.

We prove that the relation < is anti-symmetric. The goal is to show that
for all x, y in V we have: x < y ∧ y < x → x = y. Let x, y ∈ V arbitrary,
and assume that x < y and y < x. Then, we have that x ≤ y and y ≤ x.
Hence, x = y based on anti-symmetry of ≤.
We now show that the relation < is transitive. Take x, y, z ∈ V arbitrary,
and assume that x < y and y < z. We first check that x ≤ z. From x < y
we have that x ≤ y. From y < z we have that y ≤ z. Now, from x ≤ y
Chapter 3 — Relations: Partial Order 45

Figure 3.3: Hasse diagram of {0, 1, 2}2 with Cartesian ordering.

and y ≤ z we have that x ≤ z by transitivity of ≤. Next, we check that

x 6= z. This is done by a proof by contradiction. For this purpose, assume
the contrary x = z. It then follows that x < y and y < x (since, y < z = x.
However, from the anti-symmetry of < (see first part of the proof) it follows
that x = y. However, at the same time it follows from x < y that x 6= y.
Hence, we have a contradiction.

3.3 Two constructions of relations for orderings

First construction: Cartesian product
Given are two sets V1 and V2 , each with their own partial order ≤1 and ≤2 ,
respectively. The Cartesian ordering in the product set V1 × V2 is defined by
(CART): < x1 , x2 >≤< y1 , y2 > :↔ x1 ≤1 y1 ∧ x2 ≤2 y2 .
Loosely spoken: in the Cartesian ordering a pair is smaller than or equal
to a second pair when the inequalities corresponding to both first and both
second coordinates hold.

Example: Let V1 := V2 := {0, 1, 2} with the natural (total) ordering where

0 < 1 < 2. In the Cartesian ordering on {0, 1, 2}2 we have
< 0, 0 >≤< 0, 1 >, < 0, 0 >≤< 1, 0 >, < 1, 0 >≤< 1, 1 >, < 0, 1 >≤< 1, 1 >,
but not < 0, 1 >≤< 1, 0 > and not < 1, 0 >≤< 0, 1 >. The constructed
Cartesian order is not total. In Figure 3.3 the pairs are depicted in short by
omitted the angle brackets and commas. For instance, ‘01’ corresponds to
the pair < 0, 1 >.
46 Bhulai — Set Theory for Computer Science

Figure 3.4: Hasse diagram of { a, b, c}2 with lexicographic ordering.

Theorem 3.2. Given are two sets V1 and V2 , each with their partial order ≤1
and ≤2 , respectively. The relation (CART) yields a partial order on V1 × V2 .

Proof. Let ≤ be the relation in V := V1 × V2 described by (CART). One

needs to show that ≤ is reflexive, anti-symmetric, and transitive. We only
show transitivity of ≤.
Let x, y, z, ∈ V be arbitrary and assume that x ≤ y and y ≤ z. Then,
there exists x1 , y1 , z1 ∈ V1 and x2 , y2 , z2 ∈ V2 such that
x =< x1 , x2 >, y =< y1 , y2 >, z =< z1 , z2 >.
From x ≤ y it follows from the definition of (CART) that (1) x1 ≤1 y1 and
(2) x2 ≤2 y2 . From y ≤ z it follows from the definition of (CART) that (3)
y1 ≤2 z1 and (4) y2 ≤2 z2 . From (1) and (3) it follows (by transitivity of ≤1 )
that x1 ≤1 z1 . Similarly, from (2) and (4) it follows (from transitivity of ≤2 )
that x2 ≤2 z2 . These conclusions together with the description of (CART)
result in x =< x1 , y1 >≤ z =< z1 , z2 >.

The construction of the Cartesian ordering can be extended relatively

easy to products with more than two ordered sets. With three factors the
relation is defined as:
(CART3): < x1 , x2 , x3 >≤< y1 , y2 , y3 > :↔ x1 ≤1 y1 ∧ x2 ≤2 y2 ∧ x3 ≤3 y3 .
Note that Theorem 3.2 remains unchanged.

Second construction: Lexicographic ordering Given are two sets V1 and V2 ,

each with their own partial order ≤1 and ≤2 , respectively. The lexicographic
ordering in the product set V1 × V2 is defined by
(LEX): < x1 , x2 >≤< y1 , y2 > :↔ x1 <1 y1 ∨ ( x1 = y1 ∧ x2 ≤2 y2 ).
Loosely spoken: in the lexicographic ordering a pair is smaller than or equal
to a second pair when the inequality holds for the first coordinate, and the
second coordinate otherwise. Summarized: the first coordinate decides.
Chapter 3 — Relations: Partial Order 47

Let V1 := V2 := {‘a0 , ‘b0 , ‘c0 } with the usual (total) ordering. Then,
V1 × V2 is the set of all two-letter words with the letters ‘a0 , ‘b0 , ‘c0 . In the
lexicographic ordering on these words, we find that
‘aa0 ≤ ‘ab0 ≤ ‘ba0 ≤ ‘bb0 .
The constructed lexicographic ordering is clearly total. In Figure 3.4 all pairs
are displayed in a shortened manner without the parentheses and commas.
For instance, ‘ab’ represents < a, b >.

Theorem 3.3. Given are two sets V1 and V2 , each with their partial order ≤1
and ≤2 , respectively. The relation (LEX) yields a partial order on V1 × V2 .
This ordering is total if both the orderings ≤1 and ≤2 are total.

Proof. Let ≤ be the relation in V := V1 × V2 described by (LEX). The strict

orderings corresponding with ≤1 and ≤2 are <1 and <2 , respectively. One
needs to show that ≤ is reflexive, anti-symmetric, transitive, and total. We
only show transitivity of ≤.
Let x, y, z ∈ V be arbitrary and assume that x ≤ y and y ≤ z. Then,
there exists x1 , y1 , z1 ∈ V1 and x2 , y2 , z2 ∈ V2 such that
x =< x1 , y1 >, y =< y1 , y2 >, z =< z1 , z2 >.
It follows from x ≤ y and the definition (LEX) that x1 <1 y1 , or x1 = y1
and x2 ≤2 y2 . From y ≤ z it follows using (LEX) that y1 <1 z1 or y1 = z1
and y2 ≤2 z2 . The combination of these two facts leads to four alternatives,
which we will check:

(i) x1 <1 y1 and y1 ≤1 z1 : transitivity of ≤1 yields x1 ≤1 z1 , and thus

< x1 , x2 >≤< z1 , z2 > according to (LEX).

(ii) x1 <1 y1 and y1 = z1 and x2 ≤2 y2 . The strict inequality and equality

yield x1 <1 z1 and thus < x1 , x2 >≤< z1 , z2 > according to (LEX).

(iii) x1 = y1 and x2 ≤2 y2 and y1 <1 z1 : The strict inequality and equality

yield x1 ≤1 z1 and thus < x1 , x2 >≤< z1 , z2 > according to (LEX).

(iv) x1 = y1 and x2 ≤2 y2 and y1 = z1 and y2 ≤2 z2 : The equalities yield

x1 = z1 . The inequalities and transitivity of ≤2 yield x2 ≤ z2 . Hence,
< x1 , x2 >≤< z1 , z2 > according to (LEX).

In all cases we find x =< x1 , x2 >≤ z =< z1 , z2 >.

48 Bhulai — Set Theory for Computer Science

The construction of the lexicographic ordering can also be extended to

products of two or more sets. The description of this relation is rather cum-
bersome, but the principle is clear: the symbol at the left decides, in case of
equality the next symbol decides, etc. Theorem 3.3 remains unchanged.
In case of a product with n factors, that are all equal to the standard set
Alphabet with the usual ordering, one gets the (total) dictionary-ordering for
words of length n. The name ‘lexicographic ordering’ actually refers to this
example. Time stamps and dates can also be described through a product
set of two or more factor and a lexicographic ordering.

3.4 Maxima and minima

Definitions
Let (V, ≤) be a partially ordered set with a subset A ⊆ V and an element
p ∈ V. We define the following four concepts:
(1) p is a largest element (maximum) of A if p ∈ A and each element of A
is smaller than or equal to p.
(2) p is a smallest element (minimum) of A if p ∈ A and p is smaller than
or equal to any other element of A.
(3) p is a maximal element of A if p ∈ A and each element of A is not
strictly larger than p.
(4) p is a minimal element of A if p ∈ A and each element of A is not
strictly smaller than p.
The expressions (1) and (2) correspond well to our intuitive concept of
‘largest’ and ‘smallest’ element. The sentence of these properties are denoted
in a more compact form in the following table.

# Property Definition
(1) p is a largest element of A p ∈ A ∧ ∀ a ∈ A, a ≤ p
(2) p is a smallest element of A p ∈ A ∧ ∀ a ∈ A, p ≤ a
(3) p is a maximal element of A p ∈ A ∧ ∀ a ∈ A, ( p ≤ a → p = a)
(4) p is a minimal element of A p ∈ A ∧ ∀ a ∈ A, ( a ≤ p → a = p)
The properties (3) and (4) may be a surprise in comparisons in verbal form.
Theorem 3.4. Given is a partially ordered set V with ordering ≤, and a subset
A. The following holds: A cannot have two different largest elements and A
cannot have two different smallest elements.
Chapter 3 — Relations: Partial Order 49

Proof. The arguments are the same for both statements; we, therefore, only
prove the first statement. We formulate the goal as follows: if p and q are
both largest elements of A, then p = q.
First, assume that p and q are both largest elements of A. The fact that
p is a largest element, means that p ∈ A and ∀ a ∈ A, a ≤ p. The fact that
q is largest element, means that q ∈ A and ∀ a ∈ A, a ≤ q. From q ∈ A and
∀ a ∈ A, a ≤ p it follows that q ≤ p. From p ∈ A and ∀ a ∈ A, a ≤ q it follows
that p ≤ q. Now, from p ≤ q and q ≤ p, we have p = q (anti-symmetry).

Theorem 3.5. Given is a partially ordered set V with ordering ≤, and a subset
A. The following holds: a largest element of A is a maximal element of A,
and a smallest element of A is a minimal element of A.

Proof. We only prove the first statement (the proof of the second statement
is completely analogous). The goal is to show that: if p is the largest element
of A, then p is a maximal element of A.
Assume that p ∈ V and that p is a largest element of A. We will show
that p is a maximal element of A. First, p ∈ A, since p is the largest element
of A. Now, let a ∈ A arbitrary and assume that p ≤ a. Since p is the largest
element of A, we have a ≤ p. From p ≤ a and anti-symmetry of ≤, we
conclude that a = p, as required for a maximal element.

In case of a total ordering, the reverse implications also hold.

3.5 Exercises
1. In the zoo, the animals are fed according to a fixed schedule:

(a) The giraffes are fed before the zebras, but after the apes.
(b) The bears are fed immediately after the apes.
(c) The lions are fed after the zebras.

Can you recover the full schedule? Do you need additional ‘common-
sense’ premises?

N
2. Let P be the set of all integers > 0; in the notation of sets: P := \ {0}.
The relation IsDivisorOf (with symbol ‘|’) in P is described as follows:
x | y :↔ ∃z ∈ P, x · z = y.
50 Bhulai — Set Theory for Computer Science

(a) Show that ‘|’ is a partial order on P.

(b) Show that the ordering is not total.
(c) Let a = 12 and b = 30. Show that the set
{ x : x | a ∧ x | b}
of all common divisors x of a, b has a largest element in this or-
dering. Does this result also hold for arbitrary a, b ∈ P?
(d) Let a = 12 and b = 30 as in part (c). Show that the set
{x : a |x ∧ b | x}
of all common multiples x of a, b has a smallest element in this
ordering. Does this result also hold for arbitrary a, b ∈ P?

3. Given is a set V with a total ordering ≤. Furthermore, it is given that

p ∈ V is a maximal element.

(a) Argue that p is a largest element of V.

(b) Give (for example through a Hasse diagram) an example of a par-
tial (not total) ordering and an element that is maximal, but not
the largest.

4. Let Alphabet be the set of alphabetic symbols ‘a‘ …‘z’ with the usual
alphabetic ordering.

(a) Give (in words or with formulas) a description of the lexicographic

ordering for the set Alphabet4 of all four-letter words.
(b) Answer (a) for the Cartesian ordering for Alphabet4 .
(c) In this part Alphabet4 has the lexicographic ordering. Let V be
the set of all four-letter words with both at the second and third
position one of the letters ‘b’ or ‘c’. Give a largest and a smallest
element of V or explain why such an element does not exist.
(d) In this part Alphabet4 has the Cartesian ordering. Let W be the
set of all four-letter words with at the second position a ‘b’ or at
the third position a ‘c’ (or both). Give a largest and a smallest
element of W or explain why such an element does not exist.

Z Z
5. Take for V the set × with the Cartesian ordering (using the natural
Z
ordering on ), and for A the subset
{< x, y > : 1 ≤ x, 1 ≤ y, x + y ≤ 5}.
Chapter 3 — Relations: Partial Order 51

(a) Give a full enumeration of all elements of A and draw the Hasse
diagram.
(b) Does A have a largest element? If so, please give this element; if
not, give all maximal elements of A.
(c) Does A have a smallest element? If so, please give this element; if
not, give all minimal elements of A.

6. Given are two sets A := { a1 , a2 , a3 } and B := {b1 , b2 , b3 }, each with the

partial order ‘≤’ described by the following Hasse diagrams.

In this exercise we study the Cartesian ordering of A × B (parts (a)

and (b)) and the lexicographic ordering of A × B (part (c)).

(a) Develop a Hasse diagram for A × B with the Cartesian ordering.

In the included figure all points are position such that the end
result will be transparent.

(b) Give all maximal and minimal elements of A × B in the Cartesian

ordering.
(c) The lexicographic ordering of A × B is not total. Give an example
of two non-comparable elements in A × B.
52 Bhulai — Set Theory for Computer Science

3.6 Background
The notion of a partially ordered set in its current form was formulated by
Felix Hausdorff (1868–1942) in 1914. The three axioms (reflexivity, anti-
symmetry, and transitivity) were used earlier by Gottfried Wilhelm Leibniz
(1646–1716) around 1690 and total orderings were used before by Georg Can-
tor in 1895. Hasse diagrams are named after the German number theoretician
Helmut Hasse (1898–1979). For partial orderings that are not too large, this
is a convenient representation.
Partial orderings are used in the study of correctness of computer pro-
grams (see [5]). But they also appear in problems such as topological sorting
and job scheduling. For this last example, one needs a set of jobs that need to
be processed to complete a project. The jobs can be ordered strict partially:
job1 < job2 means that job1 must be processed before job2 can be started. In
topological sorting, one needs to extend a partial order to a total ordering.
For example, in job scheduling one has a partial order of jobs, that one tries
to extend to a total ordering (the sequence of processing, see [4]).
Finally, boolean algebras can be seen as partially ordered sets with a
largest element (usually named 1) and a smallest element (usually named 0).
Additionally, there are two special properties. Among the common smaller
elements of two given elements a, b, there is a largest (usually denoted by
a ∧ b), and among the common larger elements of two given elements a, b,
there is a smallest (usually denoted by a ∨ b). Furthermore, for each element
a there is an element a0 for which a ∧ a0 = 0 and a ∨ a0 = 1. This algebra
operates in a similar way as the set-algebra and proposition-algebra. It is a
generalization of both algebras.
Chapter 4

Relations: Equivalence

Goals of this chapter:

• Recognize an equivalence relation through its properties.

• Reproduce some relevant examples of equivalence relations (logic equiva-
lence, congruence modulo m.
• Understand the connection between equivalence relations and a partition
in equivalence classes.
• Recognize and design a complete system of representatives of an equiva-
lence relation.

4.1 Refresher: binary relations

Basic concepts
In the previous chapter, we have again studied (binary) relations in a set V,
i.e., relations of type V × V. For binary relations, we use the infix notation
x R y to express that < x, y >∈ R (“x is in relation R with y”).
Remember the definition of the following four properties that a relation
R in a set V can have

53
54 Bhulai — Set Theory for Computer Science

Property Formal definition

Reflexivity ∀ x ∈ V, x R x
Symmetry ∀ x, y ∈ V, ( x R y → y R x )
Anti-symmetry ∀ x, y ∈ V, ( x R y ∧ y R x → x = y)
Transitivity ∀ x, y, z ∈ V, ( x R y ∧ y R z → x R z)

In Chapter 3 we studied relations that satisfied a combination of three prop-

erties:
reflexivity + anti-symmetry + transitivity.
We called such a relation a partial order. In this chapter, we study a different
combination of three properties:
reflexivity + symmetry + transitivity.
We change from anti-symmetry to symmetry. As will follow from the contents
of this chapter, this change brings forth completely different behaviour of
relations.

4.2 Equivalence relations

A relation R in a set V is called an equivalence relation when R satisfies the
following three properties:
reflexivity + symmetry + transitivity.
The symbol ‘≡’ is often used to denote an equivalence relation. Compare
this with the use of ‘≤’ for orderings.
As we will show in this and next chapter, equivalence relations come
from expressions of certain similarity of elements. Please pay attention to
this phenomenon in the examples that we will discuss.

Example: Let Date10 be the set of all pairs < x, y > of which x is an element
of the set
DayNumbers := {01, 02, …, 31},
and of which y is an element of the set
MonthNumbers := {01, 02, …, 12},
such that the pair < x, y > is a real date that occurs in 2010. As illustration:
< 31, 03 >∈ Date10 , but < 31, 04 >6∈ Date10 . A date such as < 31, 01 > is
usually represented as 31-01. The relation R10 now exists of all pairs of dates
that (in 2010) fall on the same day. For example, < 31, 01 > R10 < 07, 11 >,
because both dates fall on a Sunday in 2010. One can easily check that the
Chapter 4 — Relations: Equivalence Relations 55

defined relation R10 is an equivalence relation in the set Date10 . As a remark,

note that this relation slightly depends on the chosen year, 2010. Can you
describe the difference for this relation in the year 2008?

Let V be the Cartesian product V1 × V1 . For two arbitrary pairs < x1 , x2 >
and < y1 , y2 > we describe the following relation:
< x1 , x2 > R < y1 , y2 > : ↔ x1 = y1 .
Then R is an equivalence relation in V. In words: two pairs are equivalent if
they have the same first coordinate. One can easily check that the described
relation is an equivalence relation in V1 × V2 . An alternative equivalence
relation is defined when we change the requirement to having the same second
coordinate.

4.3 Two constructions of equivalence relations

First construction: logic equivalence of propositions
Logic equivalence in proposition logic is an important subject. Remember:
two formulas (logic forms) F1 and F2 are called logically equivalent, symbol-
ically: F1 ≡ F2 , if they have the same truth tables. The use of the term
‘equivalence’ poses the question if equivalence relations have something to
do with logic equivalence. This is indeed the case.

Examples:

(i) ¬( p ∨ q) ≡ ¬ p ∧ ¬q (DeMorgan’s Law)

(ii) p ∨ (q ∧ r ) ≡ ( p ∨ q) ∧ ( p ∨ r ) (Distributive Law)

(iii) ( p ∧ ¬ p) ∨ q ≡ q

In general, the formulas F1 and F2 contain several proposition symbols p1 ,

p2 , etc. Every row in the truth table of a formula has a certain value of
truth (0 or 1) depending on the proposition, and give a truth value of the
total formula. If F1 ≡ F2 , then the outcomes on each row are the same. The
computation of the truth value can be different; it is even possible that the
formulas do not have exactly the same proposition symbols! One can see
that in the example (iii) above.
56 Bhulai — Set Theory for Computer Science

p q ( p ∧ ¬ p) ∨q q
0 0 0 0 0
0 1 0 1 1
1 0 0 0 0
1 1 0 1 1

The column of q is (superfluously) repeated as outcome of the second formula.

The outcomes in this column are 0 − 1 − 0 − 1, of which the first two belong
to the value 0 of p, and the next two are a repetition of the previous outcomes
for the value 1 of p: this value does not matter since p does not appear in
the formula q. The final values of both formulas ( p ∧ ¬ p) ∨ q and q (denoted
in bold) are the same for every line.
Back to the general case. We list the relevant properties of logic equiva-
lence:

Reflexivity: A formula has the same truth table as itself.

Symmetry: If F1 has the same truth table as F2 , then clearly, F2 has the same
truth table as F1 .

Transitivity: First collect all proposition symbols that appear in F1 , F2 , and

F3 . Next, create a joint truth table for the three formulas. If F1 has the same
truth value as F2 on each line, and if F2 has the same truth value as F3 on
each line, then F1 has the same truth value as F3 on each line.

Logic equivalence also appears in sentences (predicate logic). One can easily
check that also here an equivalence relation appears.

Second construction: congruence modulo an integer

The second construction pertains arithmetic modulo an integer. Such sys-
tems of arithmetic appear surprisingly often in daily life. In all of the follow-
ing examples, a special number m, the modulus, is present.

• Read a clock: the hours on a clock run constantly in a cycle of 12 or

24. If we have a 12-hour clock, then we do not say that ‘it is 15 ’o
clock’, but we say ‘it is 3 ’o clock’. The number 3 is the reduction of
15 modulo 12 (m = 12). If we have a 24-hour clock, then we do not
say ‘it is 29 ’o clock’, but we say ‘it is 5 ’o clock’. The number 5 is the
reduction of 29 modulo 24 (m = 24).
Chapter 4 — Relations: Equivalence Relations 57

• Arithmetic with minutes and seconds: minutes and seconds constantly

run in cycles of 60. We do not say that “this movie lasts 2h77min’,
but ‘this movie lasts 3h17min’. The number 17 is the reduction of 77
modulo 60 (m = 60). Something similar can be said of seconds.

• Arithmetic with weekdays: weekdays constantly run in a cycle of 7. If

it is Tuesday today, than 8 days later it is Wednesday, this is one day
further in the cycle (m = 7).

• Shifts in the alphabet: simple cryptographic systems render a text

unreadable by shifting the letter in the alphabet by a fixed number
(the so-called Caesar code). The letters at the end that tend to be
discarded, are put at the beginning of the alphabet. This corresponds
to arithmetic modulo m = 26.
More precisely, we represent 0 for ‘a’, 1 for ‘b’, 2 for ‘c’, etc. until 25
for ‘z’. Assume that we want to shift three letters. The letter ‘y’ is
represented by the number 24. If the shift is applied, then we get 27.
This contains a full cycle of 26 plus 1. This is the code for the letter
‘b’.

• Number representation in a computer: (m = 232 ). Most modern com-

puters work with units of memory of 32 bits (or 4 bytes). One can
quickly see that every number from 0 to 232 − 1 = 4, 294, 967, 295 can
be represented. In order to add to number, the binary representation
with bitsum and carry are used:

27 → 00000000000000000000000000011011
55 → 00000000000000000000000000110111
+ +
82 → 00000000000000000000000001010010

1 294 967 296 → 01001101001011111010001000000000

3 000 000 001 → 10110010110100000101111000000001
+ +
4 294 967 297 → 00000000000000000000000000000001

The binary scheme is an obvious adjustment to the decimal method.

The number 2 plays the role of a ten-fold. When the outcome of an
addition is greater than m − 1 = 4294967295, then the first bits appear
58 Bhulai — Set Theory for Computer Science

to be discarded. In more imaginary terms: the bit-reservoir has an

overflow on the left side. Instead of a really large number, we only end
up with the overflow, the part that was greater than m.

Arithmetic modulo m
What does one exactly mean when one does arithmetic modulo a number m.
For a given integer m ≥ 2, we focus on the relation R with description
x R y :↔ y − x is divisible by m.
Z
We shall verify that this relation in an equivalence relation in . It is also
called the congruence modulo m and the number m is called to modulus
(moduli in plural). Instead of x R y one writes
x ≡ y (mod m).
The addition of “mod m” to the equivalence symbol ‘≡’ reminds us to the
used modulus m.

Examples:
17 ≡ 5 (mod 12), because 5 − 17 = −12, which is divisible by 12.
11 ≡ 25 (mod 7), because 25 − 11 = 14, which is divisible by 7.
−3 ≡ 181 (mod 2), because 181 − (−3) = 184), which is divisible by 2.
For each integer x, one can find a remainder r after integer division of x by
m. If q is the quotient, then x = mq + r and 0 ≤ r < m. Since, x − r = mq
if follows that r is congruence modulo m with x. One also called r the
reduction of x modulo m. A number is, thus, always congruent modulo m
with his reduction modulo m.

Example: the reduction modulo 24 of the number 51 is 3. The reduction

modulo 10 of a natural number is the last digit of that number.

We list the relevant properties of ‘congruence modulo m’ for a given modulus

m ≥ 2:

Reflexivity: x ≡ x (mod m) because x − x = 0 is divisble by m.

Symmetry: Assume that x ≡ y (mod m). Then, x − y is divisible by m. But

then also reversely, y − x is divisible by m. Hence, y ≡ x (mod m).

Transivity: Assume x ≡ y (mod m) and y ≡ z (mod m). Then x − y is

divisible by m, and y − z is divisible by m. But then the sum of these
numbers is divisible by m. This sum is:
Chapter 4 — Relations: Equivalence Relations 59

( x − y) + (y − z) = x − z.
Consequently, x ≡ z (mod m). We conclude that the relation ‘congruence
modulo m’ is an equivalence relation in . Z
As a side remark: why do we restrict ourselves to moduli m with m ≥ 2?
It is clear that m = 0 is not valid, due to division by zero. If one tries m = 1,
Z Z
then it is not a useful relation: the trivial relation × . For positive m one
automatically gets m ≥ 2. And how about a negative value for m? Simply
put: divisibility by m is the same as divisibility by −m. Hence, we can use
the positive modulus in future.

4.4 Equivalence classes and partitions

Equivalence classes
Let R be an equivalence relation in a set V and let p ∈ V. We define the
equivalence class of p with respect to R (or shorter: the R-equivalence class
of p, or even shorter, the class of p) as the set
[ p] := [ p] R := { x : x ∈ V, p R x }.
Hence, the equivalence class of p exists exactly of the elements of V which
p is related to in R. The reference to the equivalence relation R is usually
omitted.

Example: Consider the equivalence relation “congruence modulo 2” in Z.

Z
The class of 0 ∈ is according to the definition
[0] = { x : 0 ≡ x (mod 2)} = { x : 2|0 − x },
en thus [0] is the set of all even numbers. Similarly,
[1] = { x : 1 ≡ x (mod 2)} = { x : 2|1 − x },
and thus [1] is the set of all odd numbers.

Example: The cube {0, 1}3 exists of all triples of bits (0/1). An equivalence
relation R in the cube can be defined by the following description:
w1 R w2 exactly then if w1 and w2 have an equal number of zeros (and thus an
equal number of ones as well).
The equivalence classes of R are:
[000] = {000} [111] = {111}
[001] = {001, 010, 100} [110] = {110, 101, 011}
[010] = the same as [001] [101] = the same as [110]
[100] = the same as [001] [011] = the same as [110].
Note that there are exactly four different classes.
60 Bhulai — Set Theory for Computer Science

Theorem 4.1. Let R be an equivalence relation in a set V, and let p and q be

two elements of V. The following statements are true:

(i) p ∈ [ p].

(ii) [ p] ∩ [q] 6= ∅ → [ p] = [q].

Proof. The statement that p ∈ [ p] follows directly from reflexivity of R:

p R p. We therefore focus on the second part.
Assume that [ p] ∩ [q] 6= ∅. Then, there is an element v ∈ [ p] ∩ [q]. From
v ∈ [ p] it follows that p R v. From v ∈ [q] it follows that q R v, and thus
v R q (by symmetry of R). From p R v and v R q it follows that p R q (by
transitivity of R). We can show that [q] ⊆ [ p]. Take x ∈ [q] arbitrary. Then
(by definition) q R x, while we know that p R q. Thus (by transitivity) p R x,
i.e., x ∈ [ p]. In a completely analogous manner, one can show that [ p] ⊆ [q].
With both inclusions, we have that [ p] = [q].

Remember that a partition P of a set V is a collection of non-empty

subsets of V, such that each element of V is member of exactly of subset.
We can express this in the language of predicate logic as follows:
(i) ∀ P ∈ P , ( P ⊆ V ∧ P 6= ∅).
(ii) ∀ x ∈ V, ∃!P ∈ P , x ∈ P.
An alternative formulation is the following: a partition of a set V is a collec-
tion of non-empty, pairwise disjoint subsets of V, of which the union is equal
to V. We can express this in the language of predicate logic as follows:
(i) ∀ P ∈ P , ( P ⊆ V ∧ P 6= ∅).
(ii) ∀ P1 , P2 ∈ P , ( P1 6= P2 → P1 ∩ P2 = ∅).
(iii) ∀ x ∈ V, ∃ P ∈ P , x ∈ P.
Both definitions say the same thing (this is left as an exercise to the reader
to check this).

Theorem 4.2. Let R be an equivalence relation in a set V. Then, the equiv-

alence classes of R form a partition of V.

Proof. The equivalence classes of R are non-empty subsets (the class of an

element p contains at least p). Let x be an arbitrary element of V. There
is at least one equivalence class that contains x, namely [ x ]. There is also
at most one equivalence class that contains x, because if [ p] and [q] both
contain the element x, then [ p] = [q] according to Theorem 4.1.
Chapter 4 — Relations: Equivalence Relations 61

Example: The different equivalence classes of the equivalence relation “con-

gruence modulo 2” are: [0] and [1]. These sets form the partition “even
Z
versus odd” numbers in . More generally, if m ≥ 2, then [0], [1], . . . , [m − 1]
are the different equivalence classes for congruence modulo m. The fact that
classes [ p] and [q] (0 ≤ p 6= q ≤ m − 1) are different, follows simply from the
fact that p − q cannot be divisible by m, because −(m − 1) ≤ p − q ≤ m − 1
and p − q 6= 0. Also, this set represents all classes and this follows from
Z
the possibility of reduction modulo m: for given a ∈ , the remainder of a
divided by m is a number r congruent to a modulo m, where 0 ≤ r ≤ m − 1.
As a consequence, [ a] = [r ] is one of the mentioned classes. The resulting
partition P consists of the set of multiples of m, the set of multiples of m
plus one, etc., and the set of all multiples of m plus m − 1.:
P := {[0], [1], . . . , [m − 1]}.

Example: Remember the equivalence relation R in the cube with the de-
scription
w1 R w2 exactly then if w1 and w2 have an equal number of zeros (and thus an
equal number of ones as well).
There are exactly four different equivalence classes in R:
{000}, {111}, {001, 010, 100}, {110, 101, 011}.
These sets clearly form a partition of the elements of the cube.

Equivalence relations from partitions

In Theorem 4.2, it was shown that an equivalence relation gives rise to a
partition of equivalence classes. We now show that the reverse also holds.

Theorem 4.3. Let P be a partition of the set V. The description

x R y : ↔ ∃ P ∈ P , ( x ∈ P ∧ y ∈ P ),
is an equivalence relation in V. The equivalence classes of this relation are
exactly the members of the partition.

Proof. We first check that the relation is an equivalence relation.

• The relation is reflexive: Let x ∈ V be arbitrary. Then there exists a

set P ∈ P with x ∈ P. We find x R x according to the description.

• The relation is symmetric: this is a direct consequence of commutativity

of ‘∧’.
62 Bhulai — Set Theory for Computer Science

• The relation is transitive: Let x, y, z ∈ V arbitrary and assume that

x R y and y R z. Because of x R y, there exists a set P1 ∈ P with
x, y ∈ P1 . Because of y R z, there exists a set P2 ∈ P with y, z ∈ P2 .
Apparently, y belongs to two sets P1 and P2 of a partition. According
to the definition these sets are the same: P1 = P2 . Hence, there is a set
that simultaneously contains x and z. Therefore, x R z.

We finally show that the equivalence classes of R are exactly the partitions
of P .
For a given equivalence class [v] with v ∈ V, there exists a P ∈ P with
v ∈ P. We check that P = [v]. Every element of P satisfies per definition
of R the condition v R x. This shows that P ⊆ [v]. Reversily, every x ∈ [v]
satisfies per definition of an equivalence class the condition v R x. According
to the definition of R, there is a P0 ∈ P with x ∈ P0 and v ∈ P0 . Since P is
unique with v ∈ P, we have P0 = P and consequently x ∈ P. Hence, we have
shown that [v] ⊆ P.
For a given partition P ∈ P , there exists an element v ∈ P; we need to
check that [v] = P. This can be done similar to the proof above.

Example: The set {0, 1}3 of all lists of bit of length three can be split into
four sets: the list without zeros, the list with one zero, the list with two zeros,
and the list with three zeros. This leads to the equivalence relation “have an
equal number of zeros” in the set of lists of bits of length three.

Example: Consider the set Date10 of all real dates in 2010. We can divide
this set of 365 elements into seven parts, of which each part consists of all
dates that fall on a particular day (Sunday, Monday, etc.). This partition
leads to the equivalence relation “falls on the same day”.

Complete system of representatives

Let V be a set and R an equivalence relation in V. A set S ⊆ V is called a
complete system of representatives of R if S contains on element from each
R-equivalence class. Note that a complete system of representatives contains
as many elements as there are equivalence classes.

Example: Consider the equivalence relation in Date10 , in which two dates

are in relation when the fall on the same day (Sunday, Monday, …) in 2010.
We conclude that 1 January 2010 is a Friday, 2 January 2010 a Saturday, 3
January a Sunday, 4 January a Monday, 5 January a Tuesday, 6 January a
Chapter 4 — Relations: Equivalence Relations 63

Wednesday, and 7 January a Thursday. A complete system of representatives

is there, e.g.,
{< 01, 01 >, < 02, 01 >, < 03, 01 >, < 04, 01 >, < 05, 01 >, < 06, 01 >, <
07, 01 >}.
However, one can take any other seven consecutive dates in 2010: these will
also form a complete system of representatives.

Example: If m ≥ 2, then the complete system of representatives of congru-

ence modulo m is given by 0, 1, . . . , m − 1. This is a consequence of the the-
orem that [0], [1], . . . , [m − 1] is the collection of all equivalence classes. The
set {0, 1, . . . , m − 1} has one representative out of these equivalence classes.

Theorem 4.4. Let V be a set and R an equivalence relation in V. A set A ⊆ V

is a complete system of representatives of R if and only if the following two
conditions hold.

(i) Each element of V is equivalent to an element of A, in logical form

∀v ∈ V, ∃ a ∈ A, v R a.
(ii) Two different elements of A are not equivalent with respect to R, in
logical form: ∀ a1 , a2 ∈ A, ( a1 6= a2 → ¬ a1 R a2 ).

Proof. First assume that A is a complete system of representatives. of R,

and take an arbitrary element of v ∈ V. Then, [v] is an equivalence class, and
by assumption, it contains a element a ∈ A. For this a we find v R a which
shows (i). Now assume that a1 6= a2 in A and assume that a1 R a2 . Then, a1
and a2 are two different representatives of the same equivalence class; this is
in contradiction with the assumption on A. Hence, this proves (ii).
Reversely, let A satisfy the conditions (i) and (ii). We show that A
is a complete system of representatives of R as follows. Take an arbitrary
equivalence class of R. This is of the form [v] for certain v ∈ V. This class has
a representative in A because of (i), and it cannot have two representatives
in A because of (ii).

4.5 Exercises
1. Let E be the set of all non-empty (letter)words of length smaller than
or equal to 6. Two words w1 and w2 in E are in relation R if they have
the same length and if they both begin with a vowel or they both begin
with a consonant.
64 Bhulai — Set Theory for Computer Science

(a) Show that R is an equivalence relation in E.

(b) How many different equivalent classes are represented by the fol-
lowing words:
“yes”, “no”, “indeed”, “not”, “some”, “none”, “chem”, “ai”, “inf”, “imm”.
(c) Give a complete system of representatives for the relation R in E.
2. Given is a set Throws := Number × Number, in which Number :=
{1, 2, …, 6}, together with a collection of 11 subsets P2 , . . . , P12 . Set
number k (with 2 ≤ k ≤ 12) is defined as:
Pk := {< o1 , o2 > : o1 , o2 ∈ Number, o1 + o2 = k}.
Note that this collection of 11 subsets is a partition of the set Throws.
(a) Give a convenient description of the corresponding equivalence
relation in Throws.
(b) Design a complete system of representatives for the equivalence
relation of part (a).
3. Check for each of the following relation if they are an equivalence re-
lation in the specificied set. Please give a complete and convenient
system of representatives.
(a) The relation x = y in the set . N
(b) < a, b >≡< c, d >:↔ a + d = b + c in the set × . N N
Z Z
(c) < a, b >≡< c, d >:↔ a · d = b · c in the set × ( \ {0}) (pairs
of integers with the second coordinate different from zero).
(d) Let P be the set of all functioning programmes that each accept
as input a word of 32 bits and return a word of 32 bits as output.
Define the relation R in P with the following description:
x R y means that for every acceptable input both programmes x and
y deliver the same output.

4. In R2 we have a partition by sets of the form

Cr := {< x, y > : x2 + y2 = r2 },
with r ≥ 0 is a real number. Note that Cr can be represented by a circle
around the origin with radius r. For r = 0 the circle is “degenerate”
and yields a single point. Provide a convenient description for the
corresponding equivalence relation in formulas. Is there a complete
and convenient system of representatives?
Chapter 4 — Relations: Equivalence Relations 65

5. Given is a set V and a partition P of V. Provide a convenient descrip-

tion for the equivalence relation in V that comes forth from P in the
following cases.

(a) V is the set of (alphabetic) words and P consists of sets Pn :=

{ x : x has length n} for n = 0, 1, . . ..
(b) V := R and P consists of sets Pz := { x : b x c = z} for z ∈ . Z
R
Note that b x c is the entier of x ∈ , i.e., it is a largest integer z
for which z ≤ x (“rounding down”).

4.6 Background
Equivalance relations are, next to order relations, the most frequently used
class of binary relations. The view on logic equivalence via truth tables
with the same values has a parallel in the important concept of equivalence
in automata. These abstract machines can indeed be seen as a “behaviour
table” with an output for a given input and a state.
The relation “congruence modulo m” was already studied by one of the
most prominent mathematicians of all times: Carl Friedrich Gauss (1777-
1855). Modulo arithmetic is the basis of modern number theory and her many
applications in (among others) cryptography and coding. See references [1]
and [12] for an elementary introduction to this subject.
Equivalence classes are used as a tool for certain techniques to test soft-
ware. The underlying concept is to classify potential input data into specific
data classes, in which elements of the same class are treated in similar way
by the program [8].
66 Bhulai — Set Theory for Computer Science
Chapter 5

Functions

Goals of this chapter:

• Recognize functions in binary relations.

• Has knowledge of special properties of functions: partial versus total,
surjective, injective (one-one), and bijective.
• Can determine the domain and the codomain of a function.
• Can connect the concepts between partitions in equivalence classes in
equivalence relations (quotient set) and similarity in elements under a
surjective function.
• Determine the composition of two functions, and check if the inverse func-
tion is a function as well.
• See the relation between counting processes and bijections of finite sets,
and the extension to infinite sets.
• Knows the cardinality of infinite sets and the gradations of infinity, among
which the concept of countability.

Remark on terminology. What we call total functions in these notes, are sim-
ply called functions in many other texts; consequently, what we call functions
in these notes, are then called partial functions in those texts.

67
68 Bhulai — Set Theory for Computer Science

5.1 Processes and functions

Computer produce output for a given input. Between the input and the
output, there is a process that translates the first into the latter. This process
has some special properties: it is steered by precise instructions and rules (the
process is algorithmic and it produces unambiguous results (the process is
deterministic. These two properties usually go hand in hand.

Example: Consider the process in which a text in Dutch is check for spelling
errors. The input is: a Dutch text. The output is: a list of incorrectly spelled
words in the text. The process description: A list is created of all consecutive
words in the text. Each word that is read and that is already in the list is
ignored. The resulting list is compared word for word with a standard list
(a dictionary) taking into account different forms of the words (singular or
plural forms, etc). Remove the word from the list if it is recognized in the
list. The list of words that remain is the output.
We have left out most technical details of this usual procedure. The
mentioned characterics (precision, unambiguity) are visible even without the
details.

Example: Instructions such as “divide the number by two or multiply the

number with three”, or “double the number several times” are not precisely
formulated (for a given input) and therefore the output is undetermined.

Example: A cooking book typically contains examples of processes that are

not (or partly) algorithmic / deterministic in nature. Think of instructions
as
“Leave the dish cooking for several minutes on the stove”,
“Add some spices according to your taste”.
Give the input (the ingredients of the recipe), the output (the final dish) can
strongly vary based on the person that has prepared it.

Functions: informal
Some buttons of your calculator (such that the button for the square root,
sine, cosine, etc.) are also called function buttons. After input of a specific
number and pressing of the button, an unambiguous answer appears on screen
after running a process, of which one does not need to know the details (and
usually does not know it either).
The central concept in this chapter is based on this phenomenon. A
Chapter 5 — Functions 69

function is the relation between input and output of a deterministic process.

The process can be seen as a black box. With the concept of a function, we
do not focus on the details of the implementation or formula, but we focus
on the outcome of it.

Example: square root

Input: a √
positive real number x.
Output: x.
Process: a technical procedure to√calculate the square root.
The corresponding function ties x to x.

Example: reverse a sequence

Input: a word (list of letters) w.
Output: the reverse of the word w.
Process: a technical procedure to reverse the letters in a word.
The corresponding function ties the reverse of a word to itself.

Example: read a table

The process behind a function usually consists of reading a table with two
rows. The first row consists of all acceptable input values, the second row
is the corresponding output value for the input value. Here is an example.
In the jargon of mountain climbers, one speaks of a ‘summit’ when someone
reaches the top. The following table lists a few summits for the Mount
Everest from 1985 to 1997. The input is the year, and the output is the
number below in the table. For example: in 1986 there were 4 people that
reached the top of the Everest.
Year: 85 86 87 88 89 90 91 92 93 94 95 96 97
Summits: 30 4 2 50 24 72 38 90 129 51 83 98 85

5.2 Mathematical description

Functions: formal
In order to describe functions informally, we did not bother with the details
of the process that leads from input to output. What remains is: a binary
relation between possible input and output, where an unambiguous output
value is coupled to an acceptable input. Now that we have all key ingredients
for a function, we can give a formal mathematical definition.
A function is a binary relation of which each element is in relation with
at most one element. Formally expressed: a function is a binary relation f
70 Bhulai — Set Theory for Computer Science

such that
∀ x ∀ y1 ∀ y2 , ( x f y1 ∧ x f y2 → y1 = y2 ).
This expresses quite nicely the concept of determinism.
Such as with sets and relations, a function can be given a name. The
name can be chosen suggestively (e.g., square-root, summits). In a general
context, we usually use the neutral names such as f , g, ….

Typing
For a binary relation R one usually gives the type A × B. We say that R is
of type A × B. This expresses that R ⊆ A × B. Explicitly: if x R y, then
x ∈ A and y ∈ B. Since functions are binary relations, we can also provide
a type for functions. We can then speak of typed functions. A function of
type A × B is also described as a function from A to B. We denote this in
the following way:
f
f : A → B, A → B.
The set A is called the domain and B the codomain of the function f .

Domain of definition and image

Every function has a domain of definition: this is the set of all acceptable
inputs of the function. The domain of definition of a function f is denoted
by D f . Note the difference: 0 is a possible input of the real-valued function
1/x of type R R
→ , but it is not an acceptable input and does not belong
to the domain of definition of this function.
As a side remark: It may be strange on first sight that next to the domain
of definition D f we also have the domain A. The distinction is convenient, for
example, with programming. When defining a procedure, one can use A for
the type of the input variable (assume, e.g., integer) and D f can be the set of
integers that are really accepted by the procedure. In case of programming
the square root procedure, the set A consists of integers, and D f consists
of the set of non-negative integers. When choosing a data-type for A, one
chooses for D f the set of “real” input. The benefit is that A can in principle
be checked at compile time, and D f can sometimes only be checked at run
time.
A function also has an image: this is the set of all producible outputs. In
general, we rather speak of values than the output of a function. The image
of f is denoted by W f . Note the difference: −1 is element of the codomain
R R
of the real-valued function x2 of type → , but is not effectively assumed
as value.
Chapter 5 — Functions 71

Examples: Remember the functions square root and summits.

R
Dsquare root = { x : x ∈ , x ≥ 0},
R
Wsquare root = { x : x ∈ , x ≥ 0},
Dsummits = {85, 86, . . . , 97},
Wsummits = {2, 4, 24, 30, 38, 50, 51, 72, 83, 85, 90, 98, 129}.

Value and argument

The value of a function f for acceptable input x is usually denoted as f ( x )
or f x. When the input x is transformed into a value y by a function f , we
can denote this in the following ways.
f
f : x 7→ y, x 7→ y, f ( x ) = y.
In the expression f ( x ) we call x the argument of the function f . We will
preferably use the term argument instead of input in the sequel. Similarly,
we will use value instead of output.

Examples:
square root
square root(100) = 10; 100 7→ 10,
summits
summits(97) = 85, 97 7→ 85.

Relations are often defined by a description. This can also be done for defin-
ing functions by so-called function descriptions.

N N
The function add2 of type → has description x 7→ x + 2. We can rewrite
the descriptions also as add2( x ) := x + 2. The function NextLetter of type
Alphabet → Alphabet has as description: NextLetter(x) is the letter of the
alphabet that immediately follows x.

Partial function versus total function; surjective function

For a typed function f : A → B each acceptable input comes from the domain
A and each producible output comes from the codomain B. In set-theoretic
language, this is represented as
D f ⊆ A, W f ⊆ B.
We speak of a total function f : A → B when the domain and the domain
of definition of f coincide: D f = A. Explicitly: a (typed) function is total
if every element of the domain is also effectively accepted as input of the
function. To stress the contrast, we shall speak of a partial function in the
general case. Compare the language with the partial orderings.
There is also a specific term for a typed function f : A → B for which
72 Bhulai — Set Theory for Computer Science

the codomain is equal to the image: W f = B. Such functions are called

surjective. In words: a (typed) function is surjective if every element of the
codomain is effectively produced as a value of the function.

Example: Consider the function square root with domain of definition the
√ numbers x ≥ 0. Indeed, only such numbers have a (real) root. The value
real
x is a number ≥ 0. However, the result of the square root is also a number
≥ 0. Hence, the image is also equal to { x : x ∈ R, x ≥ 0}.
The function square root can also be typed as R R
→ . When typed
in this way, the function is not total since only non-negative numbers are
accepted as input, and not surjective since only non-negative numbers are
the result of the square root.

Example: Take the function f that produces 1/x2 for every number x. A
fitting type is R R
→ . The domain of definition of f consists of all real
numbers different from 0, thus f is not total. The image of f consists of
all real numbers greater than 0. The function f is therefore not surjective
either.

Let V1 and V2 be non-empty sets and let V be the Cartesian product V :=

V1 × V2 . We can now construct a function f that for a given pair from V
returns the first coordinate: thus, the input < v1 , v2 > yields as output v1
where v1 ∈ V1 and v2 ∈ V2 . The domain of definition of f is the whole
Cartesian product V1 × V2 . The image of f is the first factor V1 of the
product. This function f is also called the projection on the first coordinate.
The type is V1 × V2 → V1 . Instead of the first coordinate, one can also take
the second coordinate. In this way, one creates a projection on the second
coordinate with type V1 × V2 → V2 .
The previous construction can be generalized to a Cartesian product of
n non-empty sets (n ≥ 2):
V := V1 × V2 × · · · × Vn .
One obtain for each i = 1, 2, . . . , n the i-th projection of the product V on the
i-coordinate Vi . The i-th projection is of type V → Vi . The domain is the
Cartesian product V and the codomain is the i-th coordinate Vi . The i-th
projection is a function with domain of definition V and image Vi . Hence,
this function is both total and surjective. (Check yourself what goes wrong
when one of the set V1 , . . . , Vn is empty).

Projections of a product set V1 × V2 × · · · × Vn on the factors V1 , V2 , . . . , Vn

Chapter 5 — Functions 73

are examples of what is called: a function with n arguments. In general,

there are also function of type
V1 × V2 × · · · × Vn → W.
The input is an n-pair < x1 , x2 , . . . , xn > with xi ∈ Vi for i ∈ {1, 2, . . . , n}.
For such an input, xi is called the i-th argument of the function. When f is
the name of the function, one rewrites the correct f (< x1 , . . . , xn >) as the
short convenient f ( x1 , . . . , xn ).

Remark: terms in the predicate logic. In predicate logic, one sometimes use
terms such as “father of …” en “the double of …”. In the formal language,
these were represented in this style: t( x ). The suggestion that this is a
function is correct. More precisely: the interpretation of a term (with one
argument) in a universe U is a function in that universe. It is also a total
function U → U, because a term t( x ) should have a subject for each value
of x. A term with n arguments corresponds to a total function U n → U.

5.3 Functions and equivalence relations

Refresher
An equivalence relation R in a set V is reflexive, symmetric, and transitive.
For a given relation R in V, we can determine the equivalence class [v] of an
element v ∈ V as the set
[ v ] : = { x : v R x }.
These classes together form a partition {[v] : x ∈ V } of V. This means that
the classes are non-empty, pairwise disjoint, and together they contain all
elements of V.

Quotient set and the quotient function

The partition that belongs to an equivalence relation R in a set V is sometimes
denoted by V/R, read: V modulo R. Hence, the quotient set V/R is the set
of all R-equivalence classes:
V/R := {[ x ] : x ∈ V }.
We now can introduce a function V to V/R by defining
q : V → V/R, q( x ) := [ x ].
The process that belong to q is thus the construction of the equivalence
class of x. This function is called to quotient function corresponding to the
equivalent relation R.
74 Bhulai — Set Theory for Computer Science

Example: Take the equivalence relation “congruence modulo m”. This rela-
tion is denoted symbolically (m). The corresponding partition is then /(m). Z
Z
One simply reads this as “ modulo m”. We have already shown that
Z/(m) = {[0], [1], . . . , [m − 1]}.
Arithmetic modulo m actually takes place in this set, the number system
modulo m. We also have a quotient function q of type Z Z
→ /(m) that
converts integers into “numbers modulo m”. For example:
q(0) = {0, m, −m, 2m, −2m, . . .} =: mZ,
q(1) = {1, m + 1, −m + 1, 2m + 1, −2m + 1, . . .} =: mZ + 1.

Theorem 5.1. Let R be an equivalence relation in V, and q the quotient

function corresponding to R. Then, q is a total function:
∀ x ∈ V, ∀y ∈ V, ( x R y ↔ q( x ) = q(y)).

Proof. The fact that q is a total function is given by the fact that each
element x of V has an R-equivalence class [ x ]. We concentrate our attention
to the formula.
Take x, y ∈ V arbitrary, and assume that x R y. We want to show that
q x = q y. Because x R y, we have y ∈ [ x ] and x ∈ [y] (by definition of
equivalence class). Hence, (consequence of Theorem 4.1 of Chapter 4) we
have [ x ] = [y]. Thus, q x = q y.
Now assume that q x = q y. We want to show that x R y. From q x = q y
we have [ x ] = [y]. Since y ∈ [y], it follows that y ∈ [ x ] and thus (by definition
of equivalence class) x R y.

Theorem 5.2. Let f : V → W be a total function. The relation R with

description
x R y :↔ f ( x ) = f (y)
is an equivalence relation in V.

Proof. Checking reflexivity and symmetry is left as an exercise to the reader.

We prove the transitivity of R.
Let x, y, z in V be arbitrary elements and assume that x R y and y R z.
According to the definition, we have f x = f y and f y = f z and therefore
f x = f z. Again, by using the definition, we have x R z.

Theorem 5.2 says that a description f ( x ) = f (y) of similarity leads to an

equivalence relation. Theorem 5.1 says the reverse: an equivalence relation
leads to a description of similarity through a specific function. In both the-
orems, the function are total.
Chapter 5 — Functions 75

Z N
Example: We consider the set of integers and a number m ∈ with m ≥ 2.
Z
Then, for every x, y ∈ we have x ≡ y (mod m) if and only if the remainder
of x after division by m is the same as the remainder of y after division by
m. In this example the description of similarity is given by a function f of
Z N
type to with
f ( x ) := remainder of x after division by m.

5.4 Composition and inverse

Composition of functions
Functions are special relations and can thus be composed just like relations.
The result is similar to the result of running two processes after each other.
Each of the processes give an output for a given (acceptable) input. We
called this ‘determinism’ before. It is not difficult to see that the composite
process is also deterministic. The figure that belong to the composition f ◦ g
( f after g) is as follows.

The description corresponding to the composition f ◦ g of two function f

and g can also depicted by
g f g f
x 7→ y 7→ z, x 7→ g( x ) 7→ f ( g( x )).
As a side note: the “◦” symbol was originally developed to depicted compo-
sitions of functions. The notation was later generalized for compositions of
two relations.
In the composition of f ◦ g is can happen that a certain output of g is not
acceptable as input for f . In many textbooks two functions f and g can also
be composed when the condition Wg ⊆ D f is met. In words: each output of
g is an acceptable input of f . This relates to the usual condition that the
domain and the domain of definition of a typed function should be the same.
This restriction is not necessary, but is a tradition that is of no use in this
course.

Example: Take two real-valued function f and g with description

g f √
x 7→ 1 − x2 , x 7→ x,
76 Bhulai — Set Theory for Computer Science

respectively. The image of g and the domain of definition of f are as follows:

Wg = { x : x ≤ 1}, D f : = { x : 0 ≤ x }.
√
Note that Wg 6⊆ D f . Furthermore, f ◦ g( x ) is given by 1 − x2 . The domain
of definition of this composition is given by
D f ◦ g = { x : 0 ≤ 1 − x 2 } = { x : −1 ≤ x ≤ 1}.

One-to-one and many-to-one functions

For the definition of the second concept from the section title, the inverse
function, we need to think about the following question: given the output of
an unknown input, is it possible to recover the input anyways? Sometimes
this can be done, but often it cannot.

Example: Suppose that we have a function planet, that for a given moon of
the solar system returns the corresponding [Link] the value of the function
is pluto, then we know for sure that the input was charon. If the value was
jupiter, then one cannot recover which moon was the input, as jupiter has
more than one moon.

A function f is called one-one (one-to-one, 1-1, injective) if for each produced

output of f , there is only one corresponding input of f . Formally expressed,
∀ x1 , x2 , ( f ( x1 ) = f ( x2 ) → x1 = x2 ).
A different expression is
∀y, ∀ x1 , x2 , ( f ( x1 ) = y ∧ f ( x2 ) = y → x1 = x2 ).
Note the similarity with the formal definition of determinism of functions.
The definition is basically a form of determinism “in the other direction”,
namely from output to input. A function is called many-one (many-to-one)
if it is not one-one.
As a side note: The notions of domain of definition and the image of a
function f leads to the following true statements.
∀y ∈ W f , ∃ x ∈ D f , f ( x ) = y.
In combination with the property that f is 1-1 we now find that
∀y ∈ W f , ∃!x ∈ D f , f ( x ) = y.

Examples: The function planet from the previous example is many-one, be-
cause in some cases multiple moons belong to the same planet. The function
square root, on the contrary, is 1-1: for a given value y, we know that y ≥ 0.
This number is the (positive) square root of x := y2 .
Chapter 5 — Functions 77

Inverse of 1-1 functions

Since functions are special relations, we can also take the inverse of a function.
The inverse of a relation R was denoted by R−1 . Remember
x R y ↔ y R−1 x.
When a relation is a function f , the underlying thought is to reverse the
process belonging to f . Unfortunately, this is not always possible without
loss of determinism, and in general, the inverse of a function is not a function
anymore.
We shall denote the inverse of a function f by f −1 . In general, f −1 is thus
a relation. In case it is a function, then the input of f becomes the output
of f −1 and vice verse. In the usual notation:
D f −1 = W f , W f −1 = D f .

Example: The function planet returns the planets of a given moon. The
process cannot be reserved without losing determinism. For a given planet
it is not always known which moon is considered.

The process for the real-valued function square root can be reversed by the
process of squaring: square root−1 = square. In this example, we find:
Dsquare = Wsquare root = { x : x ≥ 0},
Wsquare = Dsquare root = { x : x ≥ 0}.

Example: The function add2 of type N→ N has description add2( x ) :=

N
x + 2. The domain of definition is , and the image is {y : y ≥ 2}. The
process is simple to reverse: given a producible output y of f (i.e., y ≥ 2), the
original input can be obtained by x := y − 2. Thus, (add2)−1 is the function
sub2 : N → N, y 7→ y − 1,
with domain of definition {y : y ≥ 2} and image . N
Theorem 5.3. Let f be a function. The inverse of a function f is a function
if and only if f is an 1-1 function.

Proof. First assume that f is 1-1. We show that f −1 is a function, i.e.,

∀ y ∀ x1 ∀ x2 , ( y f −1 x1 ∧ y f −1 x2 → x1 = x2 ).
Take y, x1 , x2 arbitrary and assume that y f −1 x1 and y f −1 x2 . Then (by
definition of the inverse relation) x1 f y and x2 f y. Since f is 1-1, it follows
that x1 = x2 .
Next, assume dat f −1 is a function. We show that f is 1-1, i.e.,
∀ y ∀ x1 ∀ x2 , ( y = f ( x1 ) ∧ y = f ( x2 ) → x1 = x2 ).
78 Bhulai — Set Theory for Computer Science

Take y, x1 , x2 in V arbitrary and assume that y = f ( x1 ) and y = f ( x2 ). Then

(definition of inverse) y f −1 x1 and y f −1 x2 . Since f −1 is a function, we have
x1 = x2 .

In order to find the inverse of a composition, one take the inverse of each
of the components and takes the composition of these in the reverse order.
This is illustrated in the following scheme.

Both compositions can be represented as follows:

f g
x 7→ y 7→ z, g ◦ f ( x ) = z.
f −1 g −1
x →7 y →7 z, f −1 ◦ g−1 (z) = x.
This rule allows one to easily compute the inverse of complex function.

Bijective functies
We saw earlier that the inverse of a function f is a function again precisely
if f is injective: different input yields different output. Let f be typed as
f : A → B. Remember that f is total if the domain of definition is exactly
A. The inverse of a total function is (when it is already a function) not
automatically a total function of type B → A. Remember that a typed
function f : A → B is surjective is the image is exactly B. One can now
prove the following: Let f be a typed function. The inverse of f is a total
function if and only if f is injective and surjective. A total function with
a total inverse is also called a bijection or a bijective function. A bijection,
differently said, is a typed total function that is both injective and surjective.

Take A := Alphabet := {‘a‘, ‘b‘, . . . , ‘z0 } and B := {1, 2, . . . , 26}. The typed
function A → B that assign a number to a letter from the alphabet is a
bijection. Indeed, different letters have a different number in the alphabet
(the function is injective), and each number in B effectively corresponds to a
Chapter 5 — Functions 79

letter in the alphabet (the function is surjective).

5.5 Counting and cardinality

Counting processes
In Chapter 1 we have studied the number of elements #A of a set A. This
number can be obtained by (often a tedious) direct count of the complete set,
or by building up the from easily countable subsets and derive a final answer
by a formula, think of the summation formula and the product formula. In
this section, we focus ourselves on counting.
Nothing seems to be so easy as counting, but what exactly happens when
you count? In classical counting, one calls consecutive numbers: one, two,
three, etc., and points to an element of a set with each number. In principle,
one creates a function with as input the number and as output the element
of the set corresponding to that number. But not every function of that type
is a counting function (counting process). There can be three ways in which
errors can occur:

• Elements can be counted at least twice.

• Elements are skipped during the counting process.

• In the sequence “one, two, …” at least one number has been skipped.

This corresponds to some nice concepts on functions (injective, surjective,

and total) from the previous paragraph.
Remember that a typed function f : V → W is a bijection if it satisfies
the following three conditions:

(i) f is injective, i.e., different elements of V have different f -values in W.

(ii) f is surjective, i.e., each element of W is an f -value of an element of V.

(iii) f is total, i.e., each element of V yields a function value.

Now, one can clearly see the relation between non-injective and counting
elements twice. And there is also a relation between non-surjective and skip-
ping an element. And finally the relation between non-total and skipping a
number also exists.
A counting process is thus a total bijection between a standard set of
numbers and a set that one wants to count. If n is a natural number and
80 Bhulai — Set Theory for Computer Science

A a set, then the definition of “#A = n” (A has n elements) can now be

translated nicely into a concrete statement: there is a total bijection
{1, 2, . . . , n} → A.
The elements of the left set are the used numbers for counting. Note that for
n = 0 the left set is empty!. In that case, the function is also empty (there
is no pair with first coordinate in ∅), and an empty function produces an
empty image. Therefore, A is also empty, because otherwise the function is
not surjective. And this coincides with #A = 0 having meaning that A = ∅.

Figure 5.1: Counting a set with eight elements { a, b, . . . , h}.

Figure 5.1 illustrates a count #A = 8 via a bijective function {1, 2, . . . , 8} →

A. The depicted function is bijective. In the first place, it is a total function
(all number 1, . . . , 8 are used). Furthermore, we can see that each element of
A is counted ( f is surjective) and only once ( f is injective).
For a simple count, one chooses a number for each element to be counted.
For larger examples, one needs to construct a counting function more care-
fully.

N
For a given number n ∈ , we want to count the corners of the n-cube.
Hence, we are dealing with the set {0, 1}n . A corner is a sequence of n bits (0
or 1). Such sequences appear, for instance, through the binary representation
of numbers, such as it is used internally in computers. The following table
represents 0, . . . , 7 with three bits. The figure is also a usual representation
of a 3-cube.
Chapter 5 — Functions 81

Number Binary Number Binary

0 000 4 100
1 001 5 101
2 010 6 110
3 011 7 111

This observation allows us to construct a counting function for the corners

of the n-cube:
f : {0, 1, . . . , 2n − 1} → {0, 1}n ,
with f (k ) := the binary representation of the number k with n bits. The table
above is exactly the function table for n = 3. The function is total (each
number between 0 (included) and 2n (not included) has a representation
with n bits. The function is injective (different numbers have a different
binary representation). And the function is surjective (every row of n bits
corresponds to a number between 0 and 2n − 1). We conclude that #{0, 1}n =
2n .

Sets with the same cardinality

We have seen that counting is nothing else than creating a bijection between
elements of the set A to be counted and the standard set of number {1, . . . , n}
or {0, . . . , n − 1}. Such a bijection is called a counting function for A. A
counting function yields, apart from a great deal of details, also the conclusion
that the two sets are equally large. This observation needs a generalization.
Two sets A and B have the same cardinality if there exists a total bijection
A → B. When two sets A and B have the same cardinality, we shall denote
that with A ≈ B. In general (with possibly infinite sets) the expression
82 Bhulai — Set Theory for Computer Science

“having the same cardinality” is preferable above the expression “are equally
large”, which might be confusing at some times.
Note that a set has exactly n elements when it has the same cardinality
as {1, . . . , n}. Hence, it is also clear that two sets with the same number of
elements have the same cardinality.

Example: Let V be a set with n points. We show that the power set P (V )
has the same cardinality as the n-cube {0, 1}n . Remember that a point of
the n-cube is an n-pair of bits. In order to construct a bijection of the n-cube
with P (V ), we first endow V with an order: a bijection f : {1, . . . , n} → V.
Now, each element of V corresponds to one number from 1, 2, . . . , n. A subset
A of V can be unambiguously described by saying which elements of V belong
to A. Even better: of each number 1, . . . , n one can tell if the corresponding
element in V is an element of A. If a ‘yes’ is denoted by a ‘1’, and a ‘no’ by
a ‘0’, then we have a bijection
g : {0, 1}n → P (V ).
The input is a sequence of bits b :=< b1 , . . . , bn >. The output is a set
A := { f (i ) : bi = 1} ⊆ V. Simply put, the sequence of bits is a sequence of
answers to the question “does element f (i ) belong to A?” (i = 1, 2, . . . , n).

We have studied the set V := {‘a0 , ‘b0 , . . . , ‘g0 } earlier, and counted 8 elements
(0 7→ ‘a0 , 1 7→ ‘b0 , etc.). Let A be a subset of V, say {‘b0 , ‘d0 , ‘ f 0 }. Then, we
can determine an 8-bit word that represents A by 01010100. In this way, we
can easily see that the number of subsets of V is exactly 28 = 256. In general,
a set with n elements has exactly 2n subsets. The exponential function for
#P (V ) explains partly the name power set for P (V ).

Example: For finite sets we say that “having the same cardinality” has the
same meaning as “has the same number of elements”. For infinite sets, the
notion of “number of elements” does not have a simple meaning anymore.
This gives some counter-intuitive results, which were considered as paradoxes
in the past. Here is an illustration.
The sets N N
(natural numbers) and 2 (even natural numbers) have the
same cardinality. Here is a bijection:
f : N → 2N, f (n) := 2n.
Please check this! A real subset can have the same cardinality with the
complete set. This is why the statements “equally big” and “has the same
number of elements” are naive and need to be avoided. The use of this
Chapter 5 — Functions 83

terminology has led to considering the infinite as a paradox in the past.

When one carefully observes the pattern, one sees already the structure.

• A student that loses half of its student allowance, has acute financial
problems.

• A top manager that sees his salary being reduced to half will have to
change his lifestyle to accommodate to his new salary.

• An oil multi-millionaire who loses half of his fortune will be disgruntled

at most.

• Someone with a fortune having the same cardinality as N will not

experience any difference when we loses half of his fortune.

One observes that how bigger the numbers get, the less is the effect noticeable
of loosing half of it. In the infinite the effect is completely gone.

Theorem 5.4. Having the same cardinality is an equivalence relation between

sets.

Proof. We need to check three conditions.

• Reflexivity: a set has the same cardinality as itself through the identity
function.

• Symmetry: When A has the same cardinality as B, then there exists

(according to definition) a bijection f : A → B. The inverser function
(!) f −1 : B → A is also a bijection, and this directly shows that B has
the same cardinality as A.

• Transitivity: Let A have the same cardinality as B, and let B have

the same cardinality as C. Hence, there are bijection f : A → B and
g : B → C. The composite function g ◦ f : A → C is a bijection, and
A has the same cardinality as C.

The symbol ‘≈’ that we introduced earlier is common for equivalence re-
lations. We finally end with a surprising example of sets having the same
cardinality.

Let N0 be the set of all natural numbers without 0. We construct a bijection

84 Bhulai — Set Theory for Computer Science

f : N0 → N × N, f ( x ) :=< m, n > with x = 2m (2n + 1).

The function process can be described as follows: First find all factors 2 of
x, note this number m, and divide these factors out of x. The quotient is an
odd number of the form 2n + 1. Note this number n.
For instance, 28 is twice divisble by 2, thus m = 2. Now, dividing by 22
yields 7 = 2 · 3 + 1, hence n = 3. Therefore, f (28) =< 2, 3 >. Here is a
table of function values f ( x ) for 1 ≤ x ≤ 9.
x 1 2 3 4 5
< m, n > < 0, 0 > < 1, 0 > < 0, 1 > < 2, 0 > < 0, 2 >
x 6 7 8 9
< m, n > < 1, 1 > < 0, 3 > < 3, 0 > < 0, 4 >
One can clearly see that

(i) The procedure works for any positive x, i.e., the function f is total.

(ii) Different input numbers x give different pairs, i.e., the function f is
injective.

(iii) For each pair < m, n > one can find a suitable number x, i.e., the
function is surjective.

N N N N N
Hence, we find that 0 ≈ × . Since, ≈ 0 , we find that ≈ × . N N N
We saw that halving/doubling in the infinite does not have an effect.
This last example shows that also squaring in the infinite does not have
an effect either. In the next paragraph we will see that this has important
consequences for classical number systems.

5.6 Some results on cardinality

Finite and countable
In the previous section we have used bijective functions to check for infinite
sets if they had “the same number” of elements. In the positive case, we
say that A and B have the same cardinality, and we write this statement as
A ≈ B.
We can give a precise meaning to the intuitive concept of (in)finite sets.
A set V is called finite if there exists a number n ∈ N
with V ≈ {1, . . . , n}.
If such a number does not exist, then the set is called infinite. To a finite set
V we can thus associate a quantity n, which is tradionally denoted by #V.
Chapter 5 — Functions 85

N
A set V is called countable if it has the same cardinality as , the set of
N
natural numbers. In the previous section we have seen that 2 and × N N
are countable.

Comparison of size
In Theorem 5.4 we have seen that cardinality creates an equivalence relation
between sets. The equivalence symbol ‘≈’ suggests something like: equal in
size, and it suggests also formulas like #A = #B. The symbool #A would
then refer to the ‘size’ of A. One can expect statements that allow one to
say that A is bigger or smaller than B, in the style of #A ≤ #B. Here is a
proposal:
#A ≤ #B :↔ there is a total injection f : A → B.

It is clear that

(i) (Reflexivity) #A ≤ #A.

(ii) (Transitivity) #A ≤ #B ∧ #B ≤ #C → #A ≤ #C.

One recognizes two properties of partial orders in here. One only misses one
property: anti-symmetry. The usefulness of the definition is partly covered
in the following result, that shows anti-symmetry.

Theorem 5.5 (Cantor en Bernstein). Let A and B be two sets. If there are
total injective functions A → B and B → A, then there also exists a total
bijection A → B.

In formulas, the theorem says: #A ≤ #B ∧ #B ≤ #A → #A = #B. This is

indeed the anti-symmetry property. The size of sets is (partially) ordered in
86 Bhulai — Set Theory for Computer Science

this manner. The ordering is even total, but a proof of this result is beyond
the scope of this course.

Proof. Let f : A → B and g : B → A be total injective functions. Starting

with a point a ∈ A, one can create a sequence of points, that lie alternatingly
in the sets A and B. If one has point x ∈ A, then the next point is f ( x ) ∈ B.
If one has point x ∈ B, the next point is g( x ) ∈ A. The process stops when
one encounters a point for the second time (that point has to be point a!).

In the left picture, the starting point is a = a1 . Starting from this point,
we can traverse the process backwards: is there a x ∈ B with g( x ) = a? If so,
then there is a unique b for the unknown x, and one can ask if there a x ∈ A
with f ( x ) = b, etc. This process only stops when the question is answered
with ‘no’.
The right graph is a simplification of the sawtooth, produced by a forward
and backward process. But it does not reveal how the process ends in both
directions. In principle, there are four options (types of sawtooth graphs),
and they are depicted below.
Type 1 is created when after some time an earlier used point appears.
Type 2 is a sawtooth with a starting point in B and for which the process
does not stop. Type 3 is a sawtooth with a starting point in A and for
which the process does not stop. Type 4 is the result of a process that never
goes back to a point that has been used and never stops either, both for the
forward and backward process.
The proof of the theorem now builds upon the following observation:
Each point of A ∪ B belongs to exactly one sawtooth. Hence, in other words,
one has an equivalence relation in A ∪ B with the complete sawtooth graphs
are equivalence classes.
Chapter 5 — Functions 87

The bijection A → B that we seek, can now be constructed per equiva-

lence class and the description for points of A in the sawtooth.

Type 1: Use the description x 7→ f ( x ).

Type 2: Use the description x 7→ g−1 ( x ).

Type 3: Use the description x 7→ f ( x ).

Type 4: Use the description x 7→ f ( x ).

Note that the description yields a point from the B-part of the corresponding
sawtooth. The four parts of the description together yields the desired result.

Application
N
One can see that for every infinite set V, there is an injection → V. Thus,
N
# ≤ #V. Indeed, V is not empty (because ∅ is finite), thus there is an
element v0 . But, a one-point set is finite, thus V has another point v1 . A
two-point set is finite, thus there is another element v2 , etc. This process
yields a list of different points v0 , v1 , v2 , . . . and with that a total injection
N → V, with n 7→ vn (n ∈ ). N
We can conclude that: #N is the smallest possible ‘infinite’ quantity.

Application
There is an injection f : Q N N
→ × , where a fraction x := a/b ( a, b ∈
Z, b 6= 0) first is simplified to an equal fraction c/d with d > 0 and numbers
88 Bhulai — Set Theory for Computer Science

c, d that are not divisible by each other. We take f ( x ) :=< c, d >. One the
other hand, there is an evident injection N
→ Q with f ( x ) := x for each
natural number x. Since the set Nis insensitive to squaring, we find that
#(N × N) = #N ≤ #Q ≤ #(N × N).
From the theorem of Cantor and Bernstein, it now follows that # N = #Q.
Hence,
#N = #Z = #Q.
The three classic number systems: natural numbers, integers, and fractions
all have the same cardinality. Even more precise, they are all countable. The
question now remains: how does this relate to the set of real numbers ? R
For an answer, the following concept is useful.

Sequence in a set
We define a sequence in a set V a total function f : N→ V. The element
f (n) is called the n-th element or the n-th term in the sequence. One denotes
the sequence f also as ( f (n))∞
n=0 (this suggests a function table). The index
notation is often used as well: f (n) = an . In fact, a sequence is nothing else
than an infinite list.

Example: Sequences of real numbers are perhaps known from calculus. An

obvious example can be found in the decimal representation of real numbers:
the numbers after the decimal form a sequence in {0, 1, . . . , 9}. In this section,
we shall mainly use sequences of bits: these are sequences in {0, 1}. Such a
sequence typically has the form:
001010100011110100110010010001010000111011110010100101 . . .
This represents a function f : N → {0, 1} with f (0) = 0, f (1) = 0, f (2) =
1, f (3) = 0, etc.

Function sets
Remember that {0, 1}n (the n-cube) consists of all n-pairs of bits. The set
of all (infinite) sequences of bits can (to analogy) be denoted as {0, 1}N , or
(somewhat more sloppy) as 2N . In general, it is customary, for two given sets
A and B, to denote the set of all total functions A → B as B A .

N
Example: We have shown that for (n ∈ ) the n-cube {0, 1}n has the same
cardinality as the power set of an n-point set. Something similar appears to
hold for infinite-dimensional cubes {0, 1}V :
#{0, 1}V = #P (V ).
Chapter 5 — Functions 89

The proof is almost identical to that of the n-cube: a subset A of V can be

coded by a total function f A : V → {0, 1}, where f A ( x ) = 1 if x ∈ A and
f A ( x ) = 0 otherwise. The function f A is called the characteristic function of
A in V. Reversely, one can construct a subset A of V, for a given function
f : V → {0, 1}, that consists of all x ∈ V with f ( x ) = 1. In this way, we get
a bijection {0, 1}V → P (V ) that ties functions V → {0, 1} to subsets of V.

After this intermezzo on function sets we return to the sequences.

The sequence set {0, 1}N

We compare the size of Nand the one from the interval [0, 1) with the size
N
of {0, 1} . There is a simple bijection
N → {0, 1}N,
that assigns to a number n ∈ N
a sequence of bits that starts with n ones,
and has only zeros thereafter. This shows that
#N ≤ #{0, 1}N .
On the other hand, every real number can be written in a binary repre-
sentation instead of a decimal representation. For the numbers between 0
(included) and 1 (not included) this results in a sequence of bits for the num-
bers after the decimal point. Note that just as 0.4999 . . . = 0.5000 . . ., we
also have in the binary system that (for instance) 0.00111 . . . = 0.0100 . . .. If
we agree on the convention that in case of ambiguity, we choose for the right
representation, then we have an injective function [0, 1) → {0, 1}N .
Reversely, there is an injective function {0, 1}N → [0, 1), in which a
sequence of bits first is converted to a sequence with a zero added to the
every two positions. The longer sequence unambiguously represents a real
number in [0, 1). This leads to
#R = #[0, 1) = #{0, 1}N .
We now have shown that:

Theorem 5.6. The system of real numbers has the same cardinality as the
N-cube.
It seems that in the infinite all ‘quantities’ are the same. However, the
following theorem states that there are indeed more degrees of infinity.

Theorem 5.7 (Cantor). The set {0, 1}N does not have the same cardinality
N
of .
90 Bhulai — Set Theory for Computer Science

N
In combination with the earlier observation, we can say that # < {0, 1}N .
N
We have found a system that is ‘even more infinite’ than ! More correctly:
apparently there are several gradations of infinity.

Proof. The proof of Cantor’s Theorem is through the diagonal method. It is

N
a proof by contradiction. Suppose that there is a total bijection → {0, 1}N .
This bijection can be explicitly depicted by the list of bits
row 0: 0 1 0 0 1 …
row 1: 0 1 1 1 0 …
row 2: 1 0 0 1 0 …
row 3: 1 1 1 0 0 …
row 4: 0 0 1 1 1 …
…
Now create a new sequence with the ‘complements’ of the diagonal:
At position 0 of row 0 there is a ‘0’: note ‘1’.
At position 1 of row 1 there is a ‘1’: note ‘0’.
At position 2 of row 2 there is a ‘0’: note ‘1’.
At position 3 of row 3 there is a ‘0’: note ‘1’.
etc.

This procedure create a sequence 10110…that cannot be in the list: it differs

at position 0 in row 0, at position 1 in row 1, etc. Hence, the counting
function is not surjective leading to a contradiction.

Cantor’s Theorem essentially says that the N-cube (and hence the set of
real numbers) is not countable.

5.7 Exercises
1. Is the function one-one or many-one? Please provide arguments

N N
(a) f : V → , with V the set { x : x ∈ , 10 ≤ x < 100} and
f (n) the sum of the digits of n (in decimal representation). For
example: f (29) = 2 + 9 = 11.
(b) f : W → W, with W the set of all non-empty (alphabet) words,
and f a function that converts a word into the word that one gets
by shifting each letter one in the alphabet (‘z’ becomes ‘a’). For
example, f (‘this’) = ‘uijt’.
Chapter 5 — Functions 91

(c) The function f given by the following table.

x 0 1 2 3 4 5 6 7 8 9 10
f ( x ) 0 1 3 5 9 11 18 17 14 5 2

2. In this exercise, we use the set A := {‘a0 , ‘b0 , . . . , ‘z0 } of all small un-
capitalized letters. Let W2+ be the set of all words with at least two
letters from A, and let W2 be the set of all words with exactly two
letters from A. We have the function cap : W2+ → W2 that provides a
cap of length 2 on each word, so
cap(‘tree’) = ‘tr’.

We also have the function seqnr : W2 → {1, 2, . . . , 1000}, where se-

qnr(x) is the sequence number of x in the lexicographical sorted list of
elements of W2 up to a maximum of 1000.
seqnr(‘af’) = 6, seqnr(‘ba’) = 27.

(a) Give a brief description of the process of the function seqnr ◦ cap.
(b) Show that the composition seqnr ◦ cap is total.
(c) Is the function seq ◦ cap surjective? Please explain.

3. In this exercise we have for each a ∈ R four functions

adda , suba , mula , diva (a 6= 0)

of type R → R. The description is as follows.

adda ( x ) := x + a;
suba ( x ) := x − a;
mula ( x ) := x · a;
diva ( x ) := x/a (a 6= 0).

Furthermore, we have disposal of the functions exp2 , root : R → R,

with descriptions
√
exp2 ( x ) := x2 , root( x ) := x.

(a) Give a description of the function and the domain of definition for
the following functions:
f := root ◦ add1 ◦ mul2 .
f := sub3 ◦ exp2 ◦mul5 .
92 Bhulai — Set Theory for Computer Science

(b) Give the description for the inverse function (assume that we have
a function) of the following compositions:
f := div5 ◦ add2 ◦ mul3 .
f := exp2 ◦add1 .
√
R R
(c) Rewrite the function f : → with f ( x ) := (3 x + 1)2 in parts
of the above defined functions.

4. Consider the function

√
f : R2 → R, f < x1 , x2 > : = x12 + x22 .
Note that based on the classical Pythagorean theorem on rectangular
triangles, this is the distance between a point < x1 , x2 > to the origin
< 0, 0 >.
(a) Describe the corresponding equivalence relation and its equiva-
lence classes.
(b) Describe (as simple as possible) the complete system of represen-
tatives.

5. Equivalence relations from functions.

(a) Let the function f : 2 → N Z

be given by the description f <
a, b >:= a − b. Show that the corresponding equivalence relation
N N
in × is exactly the relation in Exercise 3(b) from Chapter 4.
Z Z Q
(b) Let the function g : × ( \ {0}) → be defined by the descrip-
tion g < a, b >:= a/b (remember that Q
is the set of fractions).
Z Z
Show that the corresponding equivalence relation in × ( \ {0})
is exactly the relation of exercise 3(c) in Chapter 4.
Z N
(c) Let m ≥ 2 be an integer and let h : to be the function that
assigns to a number z its remainder when z is divided by m. For
example, for m = 4, we have f (17) = 1, since 17 = 4 · 4 + 1, and
h(−17) = 3, since −17 = −5 · 4 + 3. Show that the corresponding
equivalence relation is exactly the relation “congruence modulo
m”.

6. Equivalence relations and functions. Of a set Students, all the members

are checked for their capacities. The test results can be represented as
a total function
capacity : Students → Scores,
Chapter 5 — Functions 93

where Scores := {0, 1, 2, 3, 4, 5} has the natural ordering 0 < 1 <

· · · < 5. The function capacity yields a number (score) for any student
as input. The higher the score, the more capable the person is. Let R
be the binary relation in Students with description
x R y :↔ capacity( x ) ≤ capacity(y).

(a) Show that the relation R is reflexive and transitive.

(b) Suppose that Students := {p1 , . . . , p9 }, and let the function ca-
pacity be given by the following table.
person: p1 p2 p3 p4 p5 p6 p7 p8 p9
capacity: 3 0 5 4 2 5 3 4 1
Explain why the relation R is not an order relation in Students.
(c) (Assuming the general case again). Let S be the inverse relation
of R. Give a description of S using the function capacity, and
show that the relation R ∩ S is an equivalence relation in the set
Students.
(d) Give in the concrete situation of (b) the equivalence class of person
p4 with the equivalence relation of (c).

5.8 Background
The notion of a function is, next to the notion of a set, the most fundamen-
tal in mathematics. The word “function” was first used in contemporary
mathematics by Gottfried Wilhelm von Leibniz (1646–1716) in 1692. The
f ( x )-notation comes from Alexis Clairaut (1719–1765). The concept of func-
tions was formulated in 1837 by Peter Gustav Lejeune-Dirichlet (1805–1859),
and has slowly developed from calculus-like formulas with the usual opera-
tions addition, subtraction, multiplication, division, powers, and roots. The
informal description of functions as a relation between inputs and outputs
with omitting the process details can also be found in reference [2].
There are various programming languages based on the idea of functions.
This style of programming is better known as functional programming. The
oldest and most well-known language of this type is LISP (John, McCarty,
1960). For an introduction into the modern functional language Miranda,
see [4].
Cardinality of sets dates back to the end of the nineteenth century based
on ideas of Georg Cantor. Some results and methods of proofs in this the-
94 Bhulai — Set Theory for Computer Science

ory have been of influence on later subjects such as Turing machines and
completeness.
Chapter 6

Induction and Recursion

Goals of this chapter:

• Knowledge of arithmetic rules in Z with respect to addition, multiplica-

tion, and the natural ordering.
• Give and understand a proof by induction.
• Knows the difference between normal and strong induction.
• Knows the relation between induction and the well-ordering principle in
Z
.
• Calculate terms in a recursively defined sequence.
• Check a given formula for a recursively defined sequence by proof of in-
duction.
• Describe the transitive closure of a relation.

6.1 The integers

Z
In this course, we have referred quite often to the set of integers, and the
usual operations addition ‘+’ and multiplication ‘·’. This chapter is about
methods of proof that a specific for integers. This paragraph provides an
overview of the fundamental rules for arithmetic in . Z
When carrying out arithmetic operations, the following priority rule is
in force: multiplication has higher priority over addition. For instance, the
expression x · y + z with parentheses has the meaning ( x · y) + z. If this is

95
96 Bhulai — Set Theory for Computer Science

not the preferred order, then parentheses are used: x · (y + z). Expressions
with operators, such as ( a + x ) · (b + y) are called terms.
Z
Equality in is a reflexive relation: x = x for all x. Furthermore, there
is a general principle from logic: in a formula one can replace equal parts by
other equal parts (the substitution rule). More precisely, when t1 = t2 (for
two given terms t1 and t2 ), then a formula is equivalent with a formula in
which t1 is replaced by t2 .

Addition
The set Z
is equipped with a binary operation ‘+’, called addition (sum),
and for which the following rules hold:

Rules for addition

(S1) Addition is associative: ∀ x ∀y∀z, ( x + y) + z = x + (y + z).

(S2) Addition is commutative: ∀ x ∀y, x + y = y + x.
(S3) Neutral element for addition 0: ∀ x, x + 0 = 0 + x = x.
(S4) Inverse: for every x there is in inverse element − x such that ∀ x, x +
(− x ) = (− x ) + x = 0.

The notation x − y is an abbreviation for x + (−y). Instead of a ‘neutral

element for addition’ one also speaks of a zero element.

Multiplication
Z
The set is also equipped with the binary operation ‘·’, called multiplication
(product), for which the following rules hold.

Rules for multiplication

(V1) Multiplication is associative: ∀ x ∀y∀z, ( x · y) · z = x · (y · z).

(V2) Multiplication is commutative: ∀ x ∀y, x · y = y · x.
(V3) Neutral element for multiplication 1: ∀ x, x · 1 = 1 · x = x.

Instead of a ‘neutral element for multiplication’ one also speaks of a unit

element.

Distributive law and zero-divisors

Chapter 6 — Induction and Recursion 97

The combination of addition and multiplication and the corresponding neu-

tral elements have to further satisfy the following rules.

1. (N) Law of zero-divisors: ∀ x ∀y, ( x · y = 0 → x = 0 ∨ y = 0).

2. (D) Distributive laws: ∀ x ∀y∀z, x · (y + z) = ( x · y) + ( x · z)
∀ x ∀y∀z, ( x + y) · z = ( x · z) + (y · z).

Ordering
In the set Z there is a total ordering ≤ available. This assumes the following
laws.

Total ordering

(O1) Reflexive: ∀ x, x ≤ x.
(O2) Anti-symmetry: ∀ x ∀y, ( x ≤ y ∧ y ≤ x → x = y).
(O3) Transitive: ∀ x ∀y∀z, ( x ≤ y ∧ y ≤ z → x ≤ z).
(O4) Total: ∀ x ∀y, ( x ≤ y ∨ y ≤ x ).

The definition of natural numbers can be given as:

N := {x : x ∈ Z, 0 ≤ x}.
For the notion of (total) ordering in general sets, one can read Chapter 3. In
this chapter one can also find information on the strict ordering ‘<’ that can
be obtained as:
x<y : x ≤ y ∧ x 6= y.
Finally, the following laws with respect to the ordering and the operations
addition and multiplication.
The laws, that we have mentioned so far, are not characteristic for in-
tegers. The fractions and the real numbers satisfy all the above mentioned
laws as well. Arithmetic with a modulus satisfy all laws that are not related
to orderings, with a possible exception of (N). With these laws, one can show
all laws that are needed for arithmetic with the usual operations and the
natural orderings.
98 Bhulai — Set Theory for Computer Science

(0&1) Inequality of 0 and 1: 0 < 1.

(O+) Stability for addition: ∀ x ∀y∀z, ( x ≤ y → x + z ≤ y + z).
(O·) Stability for multiplication (positive numbers): ∀ x ∀y∀z, ( x ≤ y ∧ 0 ≤
z → x · z ≤ y · z ).

6.2 Induction
N
The set := {0, 1, 2, 3, . . .} of all natural numbers is of fundamental impor-
tance for both mathematics and for applications outside mathematics. It is
therefore not surprising that for statement about natural numbers (and with
extension: the integers), special techniques of proof have been developed.
In this section, we will focus on a method of proof that is quite specific
for a universe such as N Z
or , namely, the principle of induction. We will
also discuss a method of construction for sequences (recursion) that is very
convenient for proving by induction.
We first start with some examples on natural numbers.

Example 1
For every natural number n, the sum of the first n number is equal to 12 n(n +
1). Thus, 0 + 1 + 2 + · · · + n = 12 n(n + 1). This is the so-called summation
formula of Gauss. The summation in the left part can be represented by the
∑-sign.
n n
∑ k, or, without the zero , ∑ k.
k =0 k =1

Example 2
For every natural number n ≥ 1, the sum of the first n odd numbers is equal
to n2 . Thus, 1 + 3 + · · · + 2n − 1 = n2 . The summation in the left part can
be represented as
n
∑ (2k − 1).
k =1

The geometric intuition behind the equality is depicted in the following figure.
Chapter 6 — Induction and Recursion 99

Example 3
A diagonal in a polygon is a line between two not-consecutive corners. The
line passes through the figure internally, so to speak. Let n ≥ 3 a natural
number. Then, the number of diagonals in a n-polygon is exactly 12 n(n − 3).

Example 4
Given is a natural number d > 0. Every natural number n has a quotient q
and a remainder r after division by d:
∃ q ∈ N, ∃ r ∈ N, ( 0 ≤ q ∧ 0 ≤ r < d ∧ n = d · q + r ) .
This is (apart from some details) the so-called Euclid’s algorithm for division,
which says that when a number n is divided by d, there is a unique pair of
number q (= quotient) and r (= remainder) such as given in the formula.

The principle of full induction

In each of the example lists before, one has to deal with statements of the
N
form ∀n ∈ , Pn. It is known that each statement is true, but we cannot use
the methods of proof of the previous chapters. With a “for all” statement in
the set of natural numbers, there is an elegant alternative, which is known
as the principle of full induction. The strategy to follow is the following.

Premisses Target:
Starting argument [arithmetic rules] N
∀n ∈ , P(n)
Working argument 1 [arithmetic rules] P (0)
Working argument 2 [arithmetic rules] N
∀n ∈ , ( P(n) → P(n + 1))

The rules of arithmetic refer to the laws for integers, described in the previous
section. The goal in the second working argument is a “for-all implication”.
Such an argument can be further simplified with the usual combination strat-
egy. This leads to the following strategy.
100 Bhulai — Set Theory for Computer Science

Full induction Premisses Target:

Starting argument [arithmetic rules] N
∀n ∈ , P(n)
Working argument 1 [arithmetic rules] P (0)
Working argument 2 [arithmetic rules], n ∈ N, P ( n ) P(n + 1))

The proof is thus split into two parts:

(i) Proof P(0). This argument is called the basis of induction.

N
(ii) Show that P(n + 1) follows from P(n) for arbitrary n ∈ . This fase
is called the induction step of n to n + 1, and P(n) is the induction
hypothesis.

The conclusion is that P(n) is true for all n ∈ N. With this strategy, one can
also see the validity of the following form of argumentation: (universe ) N


arithmetic rules, P(0)

N
∀n ∈ , ( P(n) → P(n + 1))

N
∴ ∀ n ∈ , P ( n ).

Example 1: the summation formula of Gauss

Theorem: For all n ≥ 0 we have 0 + 1 + 2 + · · · + n = 12 n(n + 1).

The formula 0 + 1 + 2 + · · · + n = 12 n(n + 1) is the sentence P(n) with subject

n. This sentence is shown to be true with induction on n ≥ 0.

Proof:
Basis: n = 0. The left and the right part of the formula are both equal to 0.
Step n 7→ n + 1: Let n ≥ 0 arbitrary and assume that the formula is valid
for n (induction hypothesis). We show that the formula for n + 1 holds.

0 + 1 + 2 + · · · + n + ( n + 1) = (0 + 1 + 2 + · · · + n ) + ( n + 1)
! 1
= n(n + 1) + (n + 1) (induction hypothesis)
2
1
= (n + 2)(n + 1),
2
from which P(n + 1) follows. Note that we place an exclamation mark above
the equal sign where the induction hypothesis is used.
Chapter 6 — Induction and Recursion 101

Induction from a starting number

In some cases , the basis of induction is not 0, but some integer b and the
Z
variable n assumes values in { x : x ∈ , x ≥ b. In Example 2 we discussed a
summation formula that is valid for all number n ≥ 1. In this case, we have
a starting number b = 1. In Example 3 (on diagonals in a polygon) we have
a formula valid for all n ≥ 3. In this case, we have a starting number b = 3.
In such situation, we speak of induction on n ≥ b or of induction on n
with basis b. The adjustment to the strategy for this more general case is
obvious:

Premisses Target:
Starting argument [arithmetic rules] ∀n ≥ b, P(n)
Working argument 1 [arithmetic rules] P(b)
Working argument 2 [arithmetic rules], n ≥ b, P(n) P(n + 1))

Strong induction
There is an induction strategy with a more extensive induction-hypothesis
and (in theory) without basis:

(i) Take n ≥ b completely arbitrary.

(ii) Assume that P(k ) is valid for all integers k with b ≤ k < n and prove
that P(n) holds.

The conclusion is that P(n) is valid for all n ≥ b. At first, the strategy has
the following form:

Premisses Target:
Starting argument [arithmetic rules] ∀n ≥ b, P(n)
Working argument [arithmetic rules] ∀n ≥ b, (∀k, (b ≤ k < n → P(k)) → P(n))

The working argument has a “for-all implication” again as target. The usual
combination strategy leads to the following result.

Strong induction Premisses Target:

Starting argument [arithmetic rules] ∀n ≥ b, P(n)
Working argument [arithmetic rules], n ≥ b
∀k, (b ≤ k < n → P(k)) P(n)
102 Bhulai — Set Theory for Computer Science

This variant of the induction principle is also called the strong induction
principle. With the strong principle of induction, one can directly see that
Z
the following line of argumentation is valid (universe ):


arithmetic rules,
∀n ≥ b, ((∀k, (b ≤ k < n → P(k))) → P(n)),


∴ ∀n ≥ b, P(n).
Please note the induction hypothesis in case n = b: since there is no k for
which b ≤ k < b(= n), one needs to show P(b) without any hypotheses. As
illustration of strong induction we discuss Example 4 more extensively.

Example
Theorem: Let d ∈ N
with d > 0. There exist for every n ≥ 0 two numbers
N
q ∈ and r ∈ N, such that n = d · q + r and r < d.

N N
The formula ∃q ∈ ∃r ∈ , (n = d · q + r ∧ r < d) (with free variable n) is
taken as sentence P(n) with subject n. We show that validity of this sentence
with strong induction on n ≥ 0.

Proof: Let n ≥ 0 be arbitrary and assume (induction hypothesis) that for all
k with 0 ≤ k < n the quotient and the remainder exist when dividing k by
d. There are two cases: n < d and n ≥ d.
In the first case n < d, we have a quotient q = 0 and a remainder r = n.
In the second case n ≥ d, take n0 = n − d. Then, 0 ≤ n0 < n and by
induction-hypothesis there exists a quotient q0 and remainder r 0 after dividing
n0 by d:
n0 = d · q0 + r 0 , r 0 < d.
With q := q0 + 1 and r 0 = r, we find that
n = n0 + d = (d · q0 + r 0 ) + d = d · (q0 + 1) + r 0 = d · q + r.
Although the principle of strong induction has no explicit provision for a
‘basis’, in practice, one sees one or more basis situations that are proven
separately from the real proof. In the previous example, we have studied the
case n < d separately.

6.3 The well-ordering principle in Z

The natural ordering in Z
Remember the natural ordering ≤ in the set Z of all integers. One of the
Chapter 6 — Induction and Recursion 103

properties is that it is a total ordering: each two elements x and y are compa-
rable in the sense that x ≤ y or y ≤ x. This ordering has another property,
related to the principle of induction. We first formulate some concepts that
will help us.

Bounded sets
Let V be a set, ≤ a partial order in V, A ⊆ V, and b ∈ V. Then, b is called
a lower bound for A when ∀ a ∈ A, b ≤ a. We called b an upper bound for A
when ∀ a ∈ A, a ≤ b. The set A is called bounded from below when A has a
lower bound. The set A is called bounded from above, when A has an upper
bound.

Z
Example: In with the natural ordering, the set { x : x > 0} has a lower
bound but not an upper bound. The set of all even numbers in Z
has no
lower nor an upper bound.

The well-ordering principle

The envision property of the natural ordering in Z can now be formulated as
follows.

“every non-empty set bounded from below in Z has a smallest element”.

This is called the well-ordering principle. Naturally, the analogous properties
that a non-empty set bounded from above in Z has a largest element. In
fact, the first principle implies the other. We will not use this version of the
principle in the sequel.

Z
Example: The cited property is specific to and does not hold in most other
orderings. The set { x : x > 0} in R is not empty and bounded from below
(by 0, for instance). However, it does not have a smallest element.

Theorem 6.1. Given the well-ordering principle, the principle of induction

holds.

N
Proof. Let P be a predicate, b ∈ , and assume that
(i) P(b)
(ii) ∀n ≥ b, ( P(n) → P(n + 1)).
Assume that the well-ordering principle holds, then we shall show that ∀n ≥
b, P(n) using proof by contradiction. Assume that P(n) does not hold for all
n ≥ b. Then the set
V := { x : x ∈ Z, x ≥ b, ¬ P( x )}
104 Bhulai — Set Theory for Computer Science

is not empty. Moreover, the set V is bounded from below (by b for example).
According to the well-ordering principle, V has a smallest element. Let n
be this element. Then, n ≥ b and ¬ P(n). Because, P(b) is true according
to (i), we have n 6= b. Thus, n > b and n − 1 ≥ b. Moreover, n − 1 ∈ / V,
since n is the smallest element of V. Therefore, P(n − 1) and ¬ P(n) are in
contradiction with (ii).

Theorem 6.2. If the principle of induction holds, then the well-ordering prin-
ciple holds.

Z
Proof. Let V ⊆ a set bounded from below and non-empty. Suppose that
the principle of induction holds, then we will show by contradiction that V
has a smallest element. Assume that V does not have a smallest element.
Let b be a lower bound for V and use the following sentence:
P(n) := b ≤ n ∧ ∀k ∈ Z, (k < n → k ∈
/ V ).
We apply the principle of induction to show that ∀n ≥ b, P(n).

Basis n = b: Since b is a lower bound of V, we have: if k ∈ V dan b ≤ k, or

put differently, if k < b then k ∈
/ V. Consequently, P(b) is valid.

Step n 7→ n + 1. Take an arbitrary n ≥ b and assume that P(n) does not

hold, i.e., b ≤ n and k < n → k ∈ Z
/ V for each k ∈ . Notice that n ∈ / V, if
not, n should have been the smallest element of V. Then, b ≤ n + 1 and if
k < n + 1 then either k < n and thus k ∈/ V (hypothesis), or k = n and thus
also k ∈
/ V. This shows that P(n + 1) holds.
Due to the principle of induction, we can now conclude ∀n ≥ b, P(n).
Verbally, for each n ≥ b and each k < n we have k ∈
/ V. But this means that
V is empty!

6.4 Sequences and recursion

A sequence in a set
Remember that a sequence in a set V is a total function f : N → V. The
element f (n) is called the n-th element or the n-th term of the sequence.
One usually denotes the sequence f also as ( f (n))∞
n=0 (this suggest a function
table). Often the index notation is used as in f (n) = an .
The domain of definition of a sequence does not need to be N at all
Z
times, but can be more general of the form { x : x ∈ , x ≥ b}, where b is
the starting index (usually 0 or 1).
Chapter 6 — Induction and Recursion 105

Example: an example of a sequence in N

is: 2, 4, 6, 8, …. This suggests a
formal definition of a sequence with the use of a function f : {1, 2, 3, . . .} →
N , where the n-th term is given by f (n) := 2n.

Example: an example of a sequence in R

is: 1, 1/2, 1/3, 1/4, 1/5, . . .. This
suggest a formal definition of a sequence with the use of a function f :
R
{1, 2, 3, . . .} → , where the n-th term is given by f (n) := 1/n.

Recursively defined sequences

Suppose that we want to have a description for a sequence f in a set V. This
can be done in a direct manner as in the previous examples. However, often
times sequences are defined recursively. One needs to envision that the n-th
term is described by the terms before the n-th. This is called a resursive
definition. Here are some examples.

Example 1: Arithmetic sequence

An arithmetic sequence can be described by a starting term c and a difference
d with the following recursive definition:
f : N → R, f (0) := c, f (n + 1) := f (n) + d.
The sequence thus starts as c, c + d, c + 2 · d, . . .. It is clearly to see with
induction that the n-th term of this sequence can be described directly by
the function f (n) = c + n · d.

Example 2: Geometric sequence

A geometric sequence can be described by a starting term c and a ratio r
with the following recursive definition:
f : N → R, f (0) := c, f (n + 1) := f (n) · r.
The sequence thus starts as c, c · r, c · r2 , . . .. It is clearly to see with induction
that the n-th term of this sequence can be described directly by the function
f (n) = c · rn .

Example 3: Factorial
The factorial f (n) is a number n that is defined as follows
f : { x : x ≥ 1} → N, f (1) := 1, f ( n + 1) : = ( n + 1) · f ( n ).
The usual notation is n! (read as n factorial). A direct description is hard
to give and usually is given in a suggestive way 1 · 2 · · · · · n, which is not
convenient in proofs. The recursive definition, on the contrary, works much
better.
106 Bhulai — Set Theory for Computer Science

Example 4: The Towers of Hanoi

There are n ≥ 1 perforated coins of different diameter, that are attached to
a stick, the largest below. There are two other sticks. The aim is to transfer
the pile of coins from one stick to the other, with the third stick for help.
There are only two rules that need to be satisfied at all times.
• Only one coin can be transferred at a time.

• A largest coin cannot be on top of a smaller one.

Define the sequence f by the following description
f (n) is the number of transfers that one needs at minimum to reach
the end goal with n coins (n ≥ 1).

A simple argument shows that

f (1) := 1, f (n + 1) := 2 · f (n) + 1.
This defines a sequence recursively. A direct description for the n-th term of
the sequence can be given, but requires some proof.

Example 5: Exponents of a relation

Let R be a binary relation in a given set V. Remember that such relations
are a subset of V × V, and that the collection of all such subsets are denoted
by P (V × V ). We now give a recursive description for the n-fold composition
of R as follows (for n ≥ 1)
f : N0 → P (V × V ), f (1) = R, f (n + 1) = f (n) ◦ R.
We calculate a few terms
f (2) = R ◦ R,
f (3) = f (2) ◦ R = R ◦ R ◦ R,
f (4) = f (3) ◦ R = R ◦ R ◦ R ◦ R,
etc.
This suggests a better notation: instead of f (n) we write Rn (the n-th power
of R). The definition can be represented more conveniently by
Chapter 6 — Induction and Recursion 107

R1 := R, Rn+1 := Rn ◦ R.
This construction yields a sequence in P (V × V ) (!) that consists of all ‘re-
peated’ compositions of R with itself. One could also have used the recursive
definition Rn+1 := R ◦ Rn . This gives the same result as the first definition.

Proofs by induction are frequently used in sequences that are recursively

defined. As application we discuss how the value of a numeric function,
described recursively, can be determined more directly. In general, this is a
difficult problem for which special techniques exist. When a ‘direct’ formula
is proposed, however, then a proof by induction can be used to prove the
correctness of the formula.

Example: the Towers of Hanoi

Statement: f (n) = 2n − 1.
Proof: with induction on n ≥ 1.
Basis n = 1: f (1) = 1 and 21 − 1 = 1.
Step n 7→ n + 1: Assume that f (n) = 2n − 1 (induction hypothesis). Then
!
f (n + 1) = 2 f (n) + 1 = 2(2n − 1) + 1 = 2n+1 − 1,
where the second equality uses the induction hypothesis.

Transitive closure
Let R be a relation in a set V. The transitive closure is the union of all
relation Rn for n ≥ 1. The explicit definition for the transitive closure of R
is:
∃n ≥ 1, < x, y >∈ Rn .
An alternative description is as follows. An R-path in the set V is a finite
list of points
< x0 , x1 , . . . , x n >
where consecutive point are in relation
x0 R x1 , x1 R x2 , ... , x n −1 R x n .
The transitive closure of R consists of exactly those pairs < x, y > for which
an R-path in V exists that starts with x and ends with y (an R-path from x
to y).
A Hasse diagram is a graphical representation of a relation, taken from
a partial order. One condition is that each pair of the order relation must
be from a ‘path of arrows’ in the Hasse diagram. From this view, the partial
order relation is the transitive closure of the Hasse diagram.
108 Bhulai — Set Theory for Computer Science

Theorem 6.3. Let R be a relation in a set. The transitive closure of R is the

smallest transitive relation that contains R.

This theorem is quite compact in its formulation, but it contains multiple

statements.

(i) The transitive closure Rtrans of R is indeed a transitive relation.

(ii) Rtrans contains R, i.e., R ⊆ Rtrans .

(iii) If R ⊆ S, where S is a transitive relation, then Rtrans ⊆ S.

6.5 Exercises
1. Prove the following statement with induction on n.

(a) n2 ≤ 2n , (n ≥ 4).
(b) 7 is a divisor of 32n+1 + 2n−1 , (n ≥ 1).
(c) 1
1·2 + 1
2·3 +···+ 1
n·(n+1)
= n+n
1, (n ≥ 1). Note that the left part
n 1
can be written as ∑k=1 k·(k+1) .
(d) 1
1·3 + 31·5 + 51·7 + · · · + (2n−1)·(
1
2n+1)
n
2n+1 , (n
= ≥ 1). Note that the
left part can be written as ∑nk=1 (2k−1)·(
1
2k +1)
.

2. (a) A sequence of real numbers (tn )∞

n=1 is defined recursively as follows
t1 := 2, tn+1 = 2tn − 2n + 3, ( n ≥ 1).
Write down the first five terms of the sequence (tn )∞
n =1 .
(b) Prove by induction that tn = 2n−1 + 2n − 1 for all n ≥ 1.

3. A set with n elements has exactly 2n subsets. Prove this with induction
on n ≥ 0.

4. When V is a set with n elements, there are exactly n! total bijections

{1, . . . , n} → V. Prove this with induction on n ≥ 1.

5. Determine the transitive closure of the following relation.

(a) The relation R in N

with description “is a direct predecessor of”.
Explicitly: x R y :↔ x + 1 = y.
Chapter 6 — Induction and Recursion 109

(b) The relation R in the set of all not-empty words with ‘0’ and ‘1’,
for which the following description holds. A word w followed by
‘0’ is related to a word w followed by ‘10’ and to a word w followed
by ‘1’. Informally, if a sequence of bits ends with a ‘0’, then the
last bit can be replaced by a ‘10’ or a ‘1’. For example
0 R 10, 1110 R 1111.

6.6 Background
Proofs by inductions belong to the mathematical arsenal for more than 400
years. The usual name “Mathematical Induction” for the principle of induc-
tion was coined by Augustus DeMorgan (1806–1871) in 1838. An important
modern application of induction related to checking the correctness of ‘while-
loops’ in computer programs. A while-loop is an instruction that is repeated
until a certain condition is or is not satisfied. To be sure that the loop ends
with a specific end result, one usually applied proofs by induction.
An early example of a recursively defined sequence comes from Leonardo
of Pisa (1175–1250), better known as Fibonacci (= son of Bonaccio). This
mathematician described a sequence of numbers, with which he could model
the growth of a population of rabbits under ideal circumstances.
Recursive definitions are usually used to construct special sets (such as
the transitive closure of a set). For example, one can see an artificial language
as a collection of statements. This set is usually recursively defined through
grammatical ‘production rules’, see [5].
The process of the transitive closure is in a certain way the opposite of
the process that corresponds to the design of the Hasse diagram for partial
orders. The ‘thinned’ information in a Hasse diagram needs to be extended
with information on the ordering. For calculating the transitive closure, the
efficient Warshall algorithm exists [10].
110 Bhulai — Set Theory for Computer Science
Bibliography

[1] K.P. Bogart. Discrete Mathematics. Health & Co., 1988.

[2] D.J. Booth. Foundations of Discrete Mathematics for Computing. In-

ternational Thomson Computer Press, London, 1995.

[3] D. van Dalen, K. Doets, and H.C.M. de Swart. Verzamelingen, naïef,

axiomatisch, en toegepast. Oosterhoek, Scheltema & Holkema, 1995.

[4] S. Epp. Discrete Mathematics with Applications. Thomson Brooks/Cole

Publ. Co., Belmont USA, 3d edition edition, 2004.

[5] W.K. Grassmann and J.-P. Tremblay. Logic and Discrete Mathematics.
Prentice Hall, New Jersey, 1996.

[6] P.R. Halmos. Naïeve verzamelingenleer. Aula pockets #372, Het spec-
trum, 1968.

[7] R. Johnsonbaugh. Discrete Mathematics. Prentice Hall, Upper Saddle

River, New Jersey, 2001.

[8] P.C. Jorgensen. Software Testing: a craftsman’s approach. CRC Press,

2002.

[9] N. Nissanke. Introductory logic and sets for computer scientists. Addison
Wesley Longman, 1999.

[10] K.H. Rosen. Discrete Mathematics and Its Applications. McGraw Hill
International Editions, Singapore, 1999.

[11] G. Schmidt and Th. Ströhlein. Relations and Graphs. EATCS mono-
graphs on Theoretical Computer Science. Springer Verlag, Berlin, 1993.

111
112 Bhulai — Set Theory for Computer Science

[12] J.K. Truss. Discrete Mathematics for Computer Science. Addison-

Wesley, 1999.