Lecture Notes on Discrete Mathematics

July 26, 2019

T
AF
DR
 2

DR
AF
T
Contents

1 Basic Set Theory 7

1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Operations on sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Composition of functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.6 Equivalence relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 The Natural Number System 27

2.1 Peano Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2 Other forms of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . 31
2.3 Applications of Principle of Mathematical Induction . . . . . . . . . . . . . . . . . . . 34
2.4 Well Ordering Property of Natural Numbers . . . . . . . . . . . . . . . . . . . . . . . . 38
T
AF

2.5 Recursion Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2.6 Construction of Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
DR

2.7 Construction of Rational Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3 Countable and Uncountable Sets 49

3.1 Finite and infinite sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.2 Families of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3 Constructing bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4 Cantor-Schröder-Bernstein Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.5 Countable and uncountable sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4 Elementary Number Theory 71

4.1 Division algorithm and its applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4.2 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3 Chinese Remainder Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

5 Combinatorics - I 83
5.1 Addition and multiplication rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.2 Permutations and combinations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.1 Counting words made with elements of a set S . . . . . . . . . . . . . . . . . . 85
5.2.2 Counting words with distinct letters made with elements of a set S . . . . . . . 86
5.2.3 Counting words where letters may repeat . . . . . . . . . . . . . . . . . . . . . 87
5.2.4 Counting subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.2.5 Pascal’s identity and its combinatorial proof . . . . . . . . . . . . . . . . . . . . 89

3
4 CONTENTS

5.2.6 Counting in two ways . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

5.3 Solutions in non-negative integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.4 Binomial and multinomial theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
5.5 Circular arrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.6 Set partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.7 Number partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
5.8 Lattice paths and Catalan numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6 Combinatorics - II 125
6.1 Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
6.2 Principle of Inclusion and Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.3 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
6.3.1 Generating Functions and Partitions of n . . . . . . . . . . . . . . . . . . . . . 145
6.4 Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
6.5 Generating Function from Recurrence Relation . . . . . . . . . . . . . . . . . . . . . . 155

7 Introduction to Logic 169

7.1 Logic of Statements (SL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
7.2 Formulas and truth values in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
7.3 Equivalence and Normal forms in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
7.4 Inferences in SL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
7.5 Predicate logic (PL) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
T

7.6 Equivalences and Validity in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

AF

7.7 Inferences in PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

DR

8 Partially Ordered Sets, Lattices and Boolean Algebra 201

8.1 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
8.2 Lattices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
8.3 Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
8.4 Axiom of choice and its equivalents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

9 Graphs - I 237
9.1 Basic concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
9.2 Connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
9.3 Isomorphism in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
9.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
9.5 Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257
9.6 Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
9.7 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
9.8 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
9.9 Vertex coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269

10 Graphs - II 271
10.1 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271
10.2 Matching in graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
10.3 Ramsey numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
10.4 Degree sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
CONTENTS 5

10.5 Representing graphs with matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279

11 Polya Theory∗ 283

11.1 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
11.2 Lagrange’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292
11.3 Group action . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
11.4 The Cycle index polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
11.5 Polya’s inventory polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304

Index 312

T
AF
DR
6 CONTENTS

T
AF
DR
Chapter 1

Basic Set Theory

The following notations will be followed throughout the book.

1. The empty set, denoted ∅, is the set that has no element.
2. N := {1, 2, . . .}, the set of Natural numbers;
3. W := {0, 1, 2, . . .}, the set of whole numbers
4. Z := {0, 1, −1, 2, −2, . . .}, the set of Integers;
5. Q := { pq : p, q ∈ Z, q 6= 0}, the set of Rational numbers;
6. R := the set of Real numbers; and
7. C := the set of Complex numbers.
T
AF

This chapter will be devoted to understanding set theory, relations, functions. We start with the basic
DR

set theory.

1.1 Sets
Mathematicians over the last two centuries have been used to the idea of considering a collection of
objects/numbers as a single entity. These entities are what are typically called sets. The technique of
using the concept of a set to answer questions is hardly new. It has been in use since ancient times.
However, the rigorous treatment of sets happened only in the 19-th century due to the German math-
ematician Georg Cantor. He was solely responsible in ensuring that sets had a home in mathematics.
Cantor developed the concept of the set during his study of the trigonometric series, which is now
known as the limit point or the derived set operator. He developed two types of transfinite numbers,
namely, transfinite ordinals and transfinite cardinals. His new and path-breaking ideas were not well
received by his contemporaries. Further, from his definition of a set, a number of contradictions and
paradoxes arose. One of the most famous paradoxes is the Russell’s Paradox, due to Bertrand Russell
in 1918. This paradox amongst others, opened the stage for the development of axiomatic set theory.
The interested reader may refer to Katz [8].
In this book, we will consider the intuitive or naive view point of sets. The notion of a set is taken
as a primitive and so we will not try to define it explicitly. We only give an informal description of
sets and then proceed to establish their properties.
A “well-defined collection” of distinct objects can be considered to be a set. Thus, the principal
property of a set is that of “membership” or “belonging”. Well-defined, in this context, would enable
us to determine whether a particular object is a member of a set or not.

7
8 CHAPTER 1. BASIC SET THEORY

Members of the collection comprising the set are also referred to as elements of the set. Elements
of a set can be just about anything from real physical objects to abstract mathematical objects. An
important feature of a set is that its elements are “distinct” or “uniquely identifiable.”
A set is typically expressed by curly braces, { } enclosing its elements. If A is a set and a is an
element of it, we write a ∈ A. The fact that a is not an element of A is written as a 6∈ A. For instance,
if A is the set {1, 4, 9, 2}, then 1 ∈ A, 4 ∈ A, 2 ∈ A and 9 ∈ A. But 7 6∈ A, π 6∈ A, the English word
‘four’ is not in A, etc.
Example 1.1.1. 1. Let X = {apple, tomato, orange}. Here, orange ∈ X, but potato 6∈ X.
2. X = {a1 , a2 , . . . , a10 }. Then, a100 6∈ X.
3. Observe that the sets {1, 2, 3}, {3, 1, 2} and {digits in the number 12321} are the same as the
order in which the elements appear doesn’t matter.

We now address the idea of distinctness of elements of a set, which comes with its own subtleties.
Example 1.1.2. 1. Consider the list of digits 1, 2, 1, 4, 2. Is it a set?
Ans: The set consisting of digits of the list 1, 2, 1, 4, 2 is of course {1, 2, 4}. However, the list
1, 2, 1, 4, 2 in itself is not a set.
2. Let X = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Then X is the set of first 10 natural numbers. Or equivalently,
X is the set of integers between 0 and 11.

Definition 1.1.3. The set S that contains no element is called the empty set or the null set and
is denoted by { } or ∅. A set that has only one element is called a singleton set.
T

One has three main ways for specifying a set. They are:
AF

1. Listing all its elements (list notation), e.g., X = {2, 4, 6, 8, 10}. Then X is the set of even integers
DR

between 0 and 12.

2. Stating a property with notation (predicate notation), e.g.,
(a) X = {x : x is a prime number}. This is read as “X is the set of all x such that x is a prime
number”. Here, x is a variable and stands for any object that meets the criteria after the
colon.
(b) The set X = {2, 4, 6, 8, 10} in the predicate notation can be written as
i. X = {x : 0 < x ≤ 10, x is an even integer }, or
ii. X = {x : 1 < x < 11, x is an even integer }, or
iii. x = {x : 2 ≤ x ≤ 10, x is an even integer } etc.

Note that the above expressions are certain rules that help in defining the elements of the set
X. In general, one writes X = {x : p(x)} or X = {x | p(x)} to denote the set of all elements x
(variable) such that property p(x) holds. In the above, note that “colon” is sometimes replaced
by “|”.
3. Defining a set of rules which generate its members (recursive notation), e.g., let

X = {x : x is an even integer greater than 3}.

Then, X can also be specified by

(a) 4 ∈ X,
(b) whenever x ∈ X, then x + 2 ∈ X, and
(c) every element of X satisfies the above two rules.
1.2. OPERATIONS ON SETS 9

In the recursive definition of a set, the first rule is the basis of recursion, the second rule gives
a method to generate new element(s) from the elements already determined and the third rule
binds or restricts the defined set to the elements generated by the first two rules. The third rule
should always be there. But, in practice it is left implicit. At this stage, one should make it
explicit.

Definition 1.1.4. Let X and Y be two sets.

1. Suppose X is the set such that whenever x ∈ X, then x ∈ Y as well. Here, X is said to be a
subset of the set Y , and is denoted by X ⊆ Y . When there exists x ∈ X such that x 6∈ Y , then
we say that X is not a subset of Y ; and we write X 6⊆ Y .
2. If X ⊆ Y and Y ⊆ X, then X and Y are said to be equal, and is denoted by X = Y .
3. If X ⊆ Y and X 6= Y , then X is called a proper subset of Y .
Thus, X is a proper subset of Y if and only if X ⊆ Y and X 6= Y .
Example 1.1.5. 1. For any set X, we see that X ⊆ X. Thus, ∅ ⊆ ∅. Also, ∅ ⊆ X. Hence, the
empty set is a subset of every set. It thus follows that there is only one empty set.
2. We know that N ⊆ W ⊆ Z ⊆ Q ⊆ R ⊆ C.
3. Note that ∅ 6∈ ∅.
4. Let X = {a, b, c}. Then a ∈ X but {a} ⊆ X. Also, {{a}} 6⊆ X.
5. Notice that {{a}} 6⊆ {a} and {a} 6⊆ {{a}}; though {a} ∈ {a, {a}} and also {a} ⊆ {a, {a}}.

We now mention some set operations that enable us in generating new sets from existing ones.
T
AF

1.2 Operations on sets

DR

Definition 1.2.1. Let X and Y be two sets.

1. The union of X and Y , denoted by X ∪ Y , is the set that consists of all elements of X and also
all elements of Y . More specifically, X ∪ Y = {x|x ∈ X or x ∈ Y }.
2. The intersection of X and Y , denoted by X ∩ Y , is the set of all common elements of X and
Y . More specifically, X ∩ Y = {x|x ∈ X and x ∈ Y }.
3. The sets X and Y are said to be disjoint if X ∩ Y = ∅.
Example 1.2.2. 1. Let A = {1, 2, 4, 18} and B = {x : x is an integer, 0 < x ≤ 5}. Then,

A ∪ B = {1, 2, 3, 4, 5, 18} and A ∩ B = {1, 2, 4}.

2. Let S = {x ∈ R : 0 ≤ x ≤ 1} and T = {x ∈ R : .5 ≤ x < 7}. Then,

S ∪ T = {x ∈ R : 0 ≤ x < 7} and S ∩ T = {x ∈ R : .5 ≤ x ≤ 1}.

3. Let X = {{b, c}, {{b}, {c}}, b} and Y = {a, b, c}. Then

X ∩ Y = {b} and X ∪ Y = {a, b, c, {b, c}, {{b}, {c}} }.

We now state a few properties related to the union and intersection of sets.

Lemma 1.2.3. Let R, S and T be sets. Then,

1. (a) S ∪ T = T ∪ S and S ∩ T = T ∩ S (union and intersection are commutative operations).
10 CHAPTER 1. BASIC SET THEORY

(b) R ∪ (S ∪ T ) = (R ∪ S) ∪ T and R ∩ (S ∩ T ) = (R ∩ S) ∩ T (union and intersection are

associative operations).
(c) S ⊆ S ∪ T, T ⊆ S ∪ T .
(d) S ∩ T ⊆ S, S ∩ T ⊆ T .
(e) S ∪ ∅ = S, S ∩ ∅ = ∅.
(f ) S ∪ S = S ∩ S = S.
2. Distributive laws (combines union and intersection):
(a) R ∪ (S ∩ T ) = (R ∪ S) ∩ (R ∪ T ) (union distributes over intersection).
(b) R ∩ (S ∪ T ) = (R ∩ S) ∪ (R ∪ T ) (intersection distributes over union).

Proof. 2a. Let x ∈ R ∪ (S ∩ T ). Then, x ∈ R or x ∈ S ∩ T . If x ∈ R then, x ∈ R ∪ S and x ∈ R ∪ T .

Thus, x ∈ (R ∪ S) ∩ (R ∪ T ). If x 6∈ R, then x ∈ S ∩ T . So, x ∈ S and x ∈ T . Here, x ∈ R ∪ S and
x ∈ R ∪ T . Thus, x ∈ (R ∪ S) ∩ (R ∪ T ). In other words, R ∪ (S ∩ T ) ⊆ (R ∪ S) ∩ (R ∪ T ).
Now, let y ∈ (R ∪ S) ∩ (R ∪ T ). Then, y ∈ R ∪ S and y ∈ R ∪ T . Now, if y ∈ R ∪ S then either
y ∈ R or y ∈ S or both.
If y ∈ R, then y ∈ R∪(S∩T ). If y 6∈ R then the conditions y ∈ R∪S and y ∈ R∪T imply that y ∈ S
and y ∈ T . Thus, y ∈ S ∩T and hence y ∈ R∪(S ∩T ). This shows that (R ∪S)∩(R ∪T ) ⊆ R ∪(S ∩T ),
and thereby proving the first distributive law. The remaining proofs are left as exercises.

Exercise 1.2.4. 1. Complete the proof of Lemma 1.2.3.

2. Prove the following:
T
AF

(a) S ∪ (S ∩ T ) = S ∩ (S ∪ T ) = S.
(b) S ⊆ T if and only if S ∪ T = T .
DR

(c) If R ⊆ T and S ⊆ T then R ∪ S ⊆ T .

(d) If R ⊆ S and R ⊆ T then R ⊆ S ∩ T .
(e) If S ⊆ T then R ∪ S ⊆ R ∪ T and R ∩ S ⊆ R ∩ T .
(f ) If S ∪ T 6= ∅ then either S 6= ∅ or T 6= ∅.
(g) If S ∩ T 6= ∅ then both S 6= ∅ and T 6= ∅.
(h) S = T if and only if S ∪ T = S ∩ T .

Definition 1.2.5. Let X and Y be two sets.

1. The set difference of X and Y , denoted by X \ Y , is defined by X \ Y = {x ∈ X : x 6∈ Y }.
2. The set (X \ Y ) ∪ (Y \ X), denoted by X∆Y , is called the symmetric difference of X and Y .
Example 1.2.6. 1. Let A = {1, 2, 4, 18} and B = {x ∈ Z : 0 < x ≤ 5}. Then,

A \ B = {18}, B \ A = {3, 5} and A∆B = {3, 5, 18}.

2. Let S = {x ∈ R : 0 ≤ x ≤ 1} and T = {x ∈ R : 0.5 ≤ x < 7}. Then,

S \ T = {x ∈ R : 0 ≤ x < 0.5} and T \ S = {x ∈ R : 1 < x < 7}.

3. Let X = {{b, c}, {{b}, {c}}, b} and Y = {a, b, c}. Then

X \ Y = {{b, c}, {{b}, {c}}}, Y \ X = {a, c} and X∆Y = {a, c, {b, c}, {{b}, {c}}}.
1.2. OPERATIONS ON SETS 11

In naive set theory, all sets are essentially defined to be subsets of some reference set, referred to
as the universal set, and is denoted by U . We now define the complement of a set.

Definition 1.2.7. Let U be the universal set and X ⊆ U . Then, the complement of X, denoted by
X c , is defined by X c = {x ∈ U : x 6∈ X}.

We state more properties of sets.

Lemma 1.2.8. Let U be the universal set and S, T ⊆ U . Then,

1. U c = ∅ and ∅c = U .

2. S ∪ S c = U and S ∩ S c = ∅.

3. S ∪ U = U and S ∩ U = S.

4. (S c )c = S.

5. S ⊆ S c if and only if S = ∅.

6. S ⊆ T if and only if T c ⊆ S c .

7. S = T c if and only if S ∩ T = ∅ and S ∪ T = U .

8. S \ T = S ∩ T c and T \ S = T ∩ S c .

9. S∆T = (S ∪ T ) \ (S ∩ T ).

10. De-Morgan’s Laws:

T
AF

(a) (S ∪ T )c = S c ∩ T c .
DR

(b) (S ∩ T )c = S c ∪ T c .

The De-Morgan’s laws help us to convert arbitrary set expressions into those that involve only
complements and unions or only complements and intersections.

Exercise 1.2.9. Let S and T be subsets of a universal set U .

1. Then prove Lemma 1.2.8.

2. Suppose that S∆T = T . Is S = ∅?

Ans: Yes. Otherwise, let x ∈ S. Either x ∈ T or x 6∈ T . If x ∈ T , then x ∈ S ∩ T . Hence,

using Lemma 1.2.8.9 x 6∈ S∆T = T , a contradiction. If x 6∈ T , then x ∈ S \ T ⊆ S∆T = T , a
contradiction.

Definition 1.2.10. Let X be a set. Then, the set that contains all subsets of X is called the power
set of X and is denoted by P(X) or 2X .

Example 1.2.11. 1. Let X = ∅. Then P(∅) = P(X) = {∅, X} = {∅}.

2. Let X = {∅}. Then P({∅}) = P(X) = {∅, X} = {∅, {∅}}.

3. Let X = {a, b, c}. Then P(X) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

4. Let X = {{b, c}, {{b}, {c}}}. Then P(X) = {∅, {{b, c}}, {{{b}, {c}}}, {{b, c}, {{b}, {c}}} }.
12 CHAPTER 1. BASIC SET THEORY

1.3 Relations
In this section, we introduce the set theoretic concepts of relations and functions. We will use these
concepts to relate different sets. This method also helps in constructing new sets from existing ones.

Definition 1.3.1. Let X and Y be two sets. Then their Cartesian product, denoted by X × Y , is
defined as X × Y = {(a, b) : a ∈ X, b ∈ Y }. The elements of X × Y are also called ordered pairs
with the elements of X as the first entry and elements of Y as the second entry. Thus,

(a1 , b1 ) = (a2 , b2 ) if and only if a1 = a2 and b1 = b2 .

Example 1.3.2. 1. Let X = {a, b, c} and Y = {1, 2, 3, 4}. Then

X × X = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}.
X ×Y = {(a, 1), (a, 2), (a, 3), (a, 4), (b, 1), (b, 2), (b, 3), (b, 4), (c, 1), (c, 2), (c, 3), (c, 4)}.

2. The Euclidean plane, denoted by R2 = R × R = {(x, y) : x, y ∈ R}.

3. By convention, ∅ × Y = X × ∅ = ∅. In fact, X × Y = ∅ if and only if X = ∅ or Y = ∅.

Remark 1.3.3. Let X and Y be two nonempty sets. Then, X × Y can also be defined as follows:
Let x ∈ X and y ∈ Y and think of (x, y) as the set {{x}, {x, y}}, i.e., we have a new set in which an
element (a set formed using the first element of the ordered pair) is a subset of the other element (a set
formed with both the elements of the ordered pair). Then, with the above understanding, the ordered
pair (y, x) will correspond to the set {{y}, {x, y}}. As the two sets {{x}, {x, y}} and {{y}, {x, y}} are
not the same, the ordered pair (x, y) 6= (y, x).
T
AF

Exercise 1.3.4. Let X, Y, Z and W be nonempty sets. Then, prove the following statements:
DR

1. The product construction can be used on sets several times, e.g.,

X × Y × Z = {(x, y, z) : x ∈ X, y ∈ Y, z ∈ Z} = (X × Y ) × Z = X × (Y × Z).

2. X × (Y ∪ Z) = (X × Y ) ∪ (X × Z).
3. X × (Y ∩ Z) = (X × Y ) ∩ (X × Z).
4. (X × Y ) ∩ (Z × W ) = (X ∩ Z) × (Y ∩ W ).
5. (X × Y ) ∪ (Z × W ) ⊆ (X ∪ Z) × (Y ∪ W ). Give an example to show that the converse need not
be true.
Ans: Let X = {1}, Y = {2}, Z = {3} and W = {4}. Then, X × Y = {(1, 2)} and Z ×
W = {(3, 4)}. So, (X × Y ) ∪ (Z × W ) = {(1, 2), (3, 4)}, whereas (X ∪ Z) × (Y ∪ W ) =
{(1, 2), (1, 4), (3, 2), (3, 4)}.
6. Is it possible to write the set T = {(x, x, y) : x, y ∈ N} as Cartesian product of 3 sets? What
about the the set T = {(x, x2 , y) : x, y ∈ N}?

A relation can be informally thought of as a property which either holds or does not hold between
two objects. For example, x is taller than y can be a relation. However, if x is taller than y, then y
cannot be taller than x.

Definition 1.3.5. Let X and Y be two nonempty sets. A relation R from X to Y is a subset of
X × Y , i.e., it is a collection of certain ordered pairs. We write xRy to mean (x, y) ∈ R ⊆ X × Y .
Thus, for any two sets X and Y , the sets ∅ and X × Y are always relations from X to Y . A relation
from X to X is called a relation on X.
1.3. RELATIONS 13

Example 1.3.6. 1. Let X be any nonempty set and consider the set P(X). Define a relation R
on P(X) by R = {(S, T ) ∈ P(X) × P(X) : S ⊆ T }.

2. Let A = {a, b, c, d}. Some relations R on A are:

(a) R = A × A.
(b) R = {(a, a), (b, b), (c, c), (d, d), (a, b), (a, c), (b, c)}.
(c) R = {(a, a), (b, b), (c, c)}.
(d) R = {(a, a), (a, b), (b, a), (b, b), (c, d)}.
(e) R = {(a, a), (a, b), (b, a), (a, c), (c, a), (c, c), (b, b)}.
(f) R = {(a, b), (b, c), (a, c), (d, d)}.
(g) R = {(a, a), (b, b), (c, c), (d, d), (a, b), (b, c)}.
(h) R = {(a, a), (b, b), (c, c), (d, d), (a, b), (b, a), (b, c), (c, b)}.
(i) R = {(a, a), (b, b), (c, c), (a, b), (b, c)}.

Sometimes, we draw pictures to have a better understanding of different relations. For example,
to draw pictures for relations on a set X, we first put a node for each element x ∈ X and label
it x. Then, for each (x, y) ∈ R, we draw a directed line from x to y. If (x, x) ∈ R then a loop is
drawn at x. The pictures for some of the relations is given in Figure 1.1.
T
AF

c d c d c d
DR

a b a b a b

A×A Example 2.b Example 2.c

Figure 1.1: Pictorial representation of some relations from Example 2

3. Let A = {1, 2, 3}, B = {a, b, c} and let R = {(1, a), (1, b), (2, c)}. Figure 1.2 represents the
relation R. 1

1 a

2 b

3 c

Figure 1.2: Pictorial representation of the relation in Example 3

1
We use pictures to help our understanding and they are not parts of proof.
14 CHAPTER 1. BASIC SET THEORY

4. Let R = {(x, y) : x, y ∈ Z and y = x + 5m for some m ∈ Z} is a relation on Z. If we try to draw

a picture for this relation then there is no arrow between any two elements of {1, 2, 3, 4, 5}.

5. Fix n ∈ N. Let R = {(x, y) : x, y ∈ Z and y = x + nm for some m ∈ Z}. Then, R is a relation

on Z. A picture for this relation has no arrow between any two elements of {1, 2, 3, . . . , n}.

Definition 1.3.7. Let X and Y be two nonempty sets and let R be a relation from X to Y . Then,
the inverse relation, denoted by R−1 , is a relation from Y to X, defined by R−1 = {(y, x) ∈ Y × X :
(x, y) ∈ R}. So, for all x ∈ X and y ∈ Y

(x, y) ∈ R if and only if (y, x) ∈ R−1 .

Example 1.3.8. 1. If R = {(1, a), (1, b), (2, c)} then R−1 = {(a, 1), (b, 1), (c, 2)}.
2. Let R = {(a, b), (b, c), (a, c)} be a relation on A = {a, b, c} then R−1 = {(b, a), (c, b), (c, a)} is
also a relation on A.

Let R be a relation from X to Y . Consider an element x ∈ X. It is natural to ask if there exists

y ∈ Y such that (x, y) ∈ R. This gives rise to the following three possibilities:
1. (x, y) 6∈ R for all y ∈ Y .
2. There is a unique y ∈ Y such that (x, y) ∈ R.
3. There exists at least two elements y1 , y2 ∈ Y such that (x, y1 ), (x, y2 ) ∈ R.

One can ask similar questions for an element y ∈ Y . To accommodate all these, we introduce a
notation in the following definition.
T
AF

Definition 1.3.9. Let R be a nonempty relation from X to Y . Then,

DR

1. the set dom R:= {x : (x, y) ∈ R} is called the domain of R1 , and

2. the set rng R:= {y ∈ Y : (x, y) ∈ R} is called the range of R.

Notation 1.3.10. Let R be a nonempty relation from X to Y . Then,

1. for any set Z, one writes R(Z) := {y : (z, y) ∈ R for some z ∈ Z}.
2. for any set W , one writes R−1 (W ) := {x ∈ X : (x, w) ∈ R for some w ∈ W }.

Example 1.3.11. Let a, b, c, and d be distinct symbols and let R = {1, a), (1, b), (2, c)}. Then,
1. dom R = {1, 2}, rng R = {a, b, c},
2. R({1}) = {a, b}, R({2}) = {c}, R({1, 2}) = {a, b, c}, R({1, 2, 3}) = {a, b, c}, R({4}) = ∅.
3. dom R−1 = {a, b, c}, rng R−1 = {1, 2},
4. R−1 ({a}) = {1}, R−1 ({a, b}) = {1}, R−1 ({b, c}) = {1, 2}, R−1 ({a, d}) = {1}, R−1 ({d}) = ∅.

The following is an immediate consequence of the definition, but we give the proof of a few parts
for the sake of better understanding.

Proposition 1.3.12. Let R be a nonempty relation from X to Y , and let Z be any set.
1. R(Z) = R(X ∩ Z) ⊆ Y, R−1 (Z) = R−1 (Z ∩ Y ) ⊆ X.
2. dom R = R−1 (Y ) = rng R−1 ⊆ X, rng R = R(X) = dom R−1 ⊆ Y.
3. R(Z) 6= ∅ if and only if dom R ∩ Z 6= ∅.
1
In some texts, the set X is referred to as the domain set of R and it should not be confused with dom R.
1.4. FUNCTIONS 15

4. R−1 (Z) 6= ∅ if and only if rng R ∩ Z 6= ∅.

Proof. We prove the last two parts. The proof of the first two parts is left as an exercise.
3. Let f (S) 6= ∅. There exist a ∈ S ∩ A and b ∈ B such that (a, b) ∈ f . It implies that a ∈ dom f ∩ S
(a ∈ S). Converse is proved in a similar way.
4. Let rng f ∩ S 6= ∅. There exist b ∈ rng f ∩ S and a ∈ A such that (a, b) ∈ f . Then a ∈ f −1 (b) ⊆
f −1 (S). Similarly, the converse follows.

1.4 Functions
Definition 1.4.1. Let X and Y be nonempty sets and let f be a relation from X to Y .
1. f is called a partial function from X to Y , denoted by f : X * Y , if for each x ∈ X, f ({x})
is either a singleton or ∅.
2. For an element x ∈ X, if f ({x}) = {y}, a singleton, we write f (x) = y. Hence, y is referred to
as the image of x under f ; and x is referred to as the pre-image of y under f .
f (x) is said to be undefined at x ∈ X if f ({x}) = ∅.
3. If f is a partial function from X to Y such that for each x ∈ X, f ({x}) is a singleton then f is
called a function and is denoted by f : X → Y .

Observe that for any partial function f : X * Y , the condition (a, b), (a, b0 ) ∈ f implies b = b0 .
Thus, if f : X * Y , then for each x ∈ X, either f (x) is undefined, or there exists a unique y ∈ Y
T

such that f (x) = y. Moreover, if f : X → Y is a function, then f (x) exists for each x ∈ X, i.e., there
AF

exists a unique y ∈ Y such that f (x) = y.

DR

It thus follows that a partial function f : X * Y is a function if and only if dom f = X, i.e.,
domain set of f is X.

Example 1.4.2. Let A = {a, b, c, d}, B = {1, 2, 3, 4} and X = {3, 4, b, c}.

1. Consider the relation R1 = {(a, 1), (b, 1), (c, 2)} from A to B. The following are true.
(a) R1 is a partial function.
(b) R1 (a) = 1, R1 (b) = 1, R1 (c) = 2. Also, R1 ({d}) = ∅; thus R1 (d) is undefined.
(c) R1 (X) = {1, 2}.
(d) R1−1 = {(1, a), (1, b), (2, c)}. So, R1−1 ({1}) = {a, b} and R1−1 (2) = c. For any x ∈ X,
R1−1 (x) = ∅. Therefore, R1−1 (x) is undefined.

2. R2 = {(a, 1), (b, 4), (c, 2), (d, 3)} is a relation from A to B. The following are true.
(a) R2 is a partial function.
(b) R2 (a) = 1, R2 (b) = 4, R2 (c) = 2 and R2 (d) = 3.
(c) R2 (X) = {2, 4}.
(d) R2−1 (1) = a, R2−1 (2) = c, R2−1 (3) = d and R2−1 (4) = b. Also, R2−1 (X) = {b, d}.

Convention:
Let p(x) be a polynomial in the variable x with integer coefficients. Then, by writing ‘f : Z → Z
is a function defined by f (x) = p(x)’, we mean the function f = {(a, p(a)) : a ∈ Z}. For example,
the function f : Z → Z given by f (x) = x2 corresponds to the set {(a, a2 ) : a ∈ Z}.
16 CHAPTER 1. BASIC SET THEORY

Example 1.4.3. 1. For A = {a, b, c, d} and B = {1, 3, 5}, let f = {(a, 5), (b, 1), (d, 5)} be a relation
in A × B. Then, f is a partial function with dom f = {a, b, d} and rng f = {1, 5}. Further, we
can define a function g : {a, b, d} → {1, 5} by g(a) = 5, g(b) = 1 and g(d) = 5. Also, using g, one
obtains the relation g −1 = {(1, b), (5, a), (5, d)}.
2. The following relations f : Z → Z are indeed functions.
(a) f = {(x, 1) : x is even} ∪ {(x, 5) : x is odd}.
(b) f = {(x, −1) : x ∈ Z}.
(c) f = {(x, 1) : x < 0} ∪ {(0, 0)} ∪ {(x, −1) : x > 0}.

3. Define f : Q+ → N by f = {( pq , 2p 3q ) : p, q ∈ N, q 6= 0, p and q are coprime}. Then, f is a

function.
Remark 1.4.4. 1. If X = ∅, then by convention, one assumes that there is a function, called the
empty function, from X to Y .
2. If Y = ∅ and X 6= ∅, then by convention, we say that there is no function from X to Y .
3. Individual relations and functions are also sets. Therefore, one can have equality between rela-
tions and functions, i.e., they are equal if and only if they contain the same set of pairs. For exam-
ple, let X = {−1, 0, 1}. Then, the functions f, g, h : X → X defined by f (x) = x, g(x) = x|x| and
h(x) = x3 are equal as the three functions correspond to the relation R = {(−1, −1), (0, 0), (1, 1)}
on X.
4. A function is also called a map.
5. Throughout the book, whenever the phrase ‘let f : X → Y be a function’ is used, it will be
T
AF

assumed that both X and Y are nonempty sets.

DR

Some important functions are now defined.

Definition 1.4.5. Let X be a nonempty set.

1. The relation Id := {(x, x) : x ∈ X} is called the identity relation on X.
2. The function f : X → X defined by f (x) = x, for all x ∈ X, is called the identity function and
is denoted by Id.
3. The function f : X → R with f (x) = 0, for all x ∈ X, is called the zero function and is denoted
by 0.
Exercise 1.4.6. 1. Do the following relations represent functions? Why?
(a) f : Z → Z defined by
i. f = {(x, 1) : 2 divides x} ∪ {(x, 5) : 3 divides x}.
Ans: No. (6, 1) ∈ f and also (6, 5) ∈ f .
ii. f = {(x, 1) : x ∈ S} ∪ {(x, −1) : x ∈ S c }, where S = {n2 : n ∈ Z} and S c = Z \ S.
Ans: Yes. Each integer is either a square or not.
iii. f = {(x, x3 ) : x ∈ Z}.
Ans: Yes. Cube of a number is unique.
√
(b) f : R+ → R defined by f = {(x, ± x) : x ∈ R+ }, where R+ is the set of all positive real
numbers.
Ans: No. (1, −1) ∈ f and also (1, 1) ∈ f .
√
(c) f : R → R defined by f = {(x, x) : x ∈ R}.
Ans: No. −1 6∈ dom f .
1.4. FUNCTIONS 17

√
(d) f : R → C defined by f = {(x, x) : x ∈ R}.
Ans: Yes.
(e) f : R− → R defined by f = {(x, loge |x|) : x ∈ R− }, where R− is the set of all negative real
numbers.
Ans: Yes. loge is defined uniquely for each positive real number.
(f ) f : R → R defined by f = {(x, tan x) : x ∈ R}.
π
Ans: No. f is not-defined for odd multiples of .
2
2. Let f : X → Y be a function. Then f −1 is a relation from Y to X. Show that the following
results hold for f −1 :
(a) f −1 (A ∪ B) = f −1 (A) ∪ f −1 (B) for all A, B ⊆ Y .
(b) f −1 (A ∩ B) = f −1 (A) ∩ f −1 (B) for all A, B ⊆ Y .
(c) f −1 (∅) = ∅.
(d) f −1 (Y ) = X.
(e) f −1 (Y \ B) = X \ f −1 (B) for each B ⊆ Y .

Ans: x ∈ f −1 (Y \ B) ⇔ f (x) ∈ Y \ B ⇔ f (x) ∈ Y and f (x) 6∈ B ⇔ x ∈ X and

x 6∈ f −1 (B) ⇔ x ∈ X \ f −1 (B).

3. Let S = {(x, y) ∈ R2 : x2 + y 2 = 1, x ≥ 0}. It is a relation from R to R. Draw a picture of the

inverse of this relation.
√ √
Ans: S contains points like ( 12 , ± 23 ) and (0, ±1). So, the inverse contains points like