.

PREFACE
Linear Algebra plays an important role in the spheres of Mathematics, Physics, and
Engineering due to their inherent viabilities. The aim of this text book is to give rigorous
and thorough analysis and applications of various aspects of Linear algebra and analysis with
applications. Also, the present book has been designed in a lucid and coherent manner so
that the Honours and Postgraduate students of various Universities may reap considerable
benefit out of it. I have chosen the topics with great care and have tried to present them
systematically with various examples.
The author expresses his sincere gratitude to his teacher Prof. S. Das, Department
of Mathematics, R. K. Mission Residential College, Narendrapur, India, who taught him
this course at the UG level. Author is thankful to his friends and colleagues, especially,
Dr. S. Bandyopadhyay, Mr. Utpal Samanta and Mr. Arup Mukhopadhyay of Bankura
Christian College, Dr. Jayanta Majumdar, Durgapur Govt. College, Pratikhan Mandal,
Durgapur Govt. College, for their great help and valuable suggestions in the preparation
of the book. Author also extends his thanks to Prof. (Dr.) Madhumangal Pal, Dept. of
Applied Mathematics, Vidyasagar University, for his encouragement and handy suggestions.
This book could not have been completed without the loving support and encouragement
of my parents, wife (Mousumi) and son (Bubai). I extend my thanks to other well wishers
relatives and students for embalming me to sustain enthusiasm for this book. Finally, I
express my gratitude to Books and Allied (P) Ltd., specially Amit Ganguly, for bringing
out this book.
I would like to thank to Dr. Sk. Md. Abu Nayeem of Aliah University, West Bengal and
my student Mr. Buddhadeb Roy for support in writing/typing in LaTex verision.
This book could not have been completed without the loving support and encouragement
of my parents, wife (Mousumi) and son (Bubai). I extend my thanks to other well wishers
relatives and students for embalming me to sustain enthusiasm for this book. Finally, I
express my gratitude to Asian Books Private Limited, Delhi, for bringing out this book.
Critical evaluation, suggestions and comments for further improvement of the book will
be appreciated and gratefully acknowledged.
Prasun Kumar Nayak ,
(nayak [email protected])
Bankura Christian College,
Bankura, India, 722 101.

Dedicated to my parents
Sankar Nath Nayak and Mrs. Indrani Nayak
for their continuous encouragement and support..

Contents
1 Theory of Sets
1.1 Sets . . . . . . . . . . . . . . . . . . . .
1.1.1 Description of Sets . . . . . . . .
1.1.2 Types of Sets . . . . . . . . . . .
1.2 Algebraic Operation on Sets . . . . . . .
1.2.1 Union of Sets . . . . . . . . . . .
1.2.2 Intersection of Sets . . . . . . .
1.2.3 Disjoint Sets . . . . . . . . . . .
1.2.4 Complement of a Set . . . . . . .
1.2.5 Difference . . . . . . . . . . . . .
1.2.6 Symmetric Difference . . . . . .
1.3 Duality and Algebra Sets . . . . . . . .
1.4 Cartesian Product of Sets . . . . . . . .
1.5 Cardinal Numbers . . . . . . . . . . . .
1.6 Relation . . . . . . . . . . . . . . . . . .
1.6.1 Equivalence Relation . . . . . . .
1.7 Equivalence Class . . . . . . . . . . . . .
1.7.1 Partitions . . . . . . . . . . . . .
1.8 Poset . . . . . . . . . . . . . . . . . . . .
1.8.1 Dual Order . . . . . . . . . . . .
1.8.2 Chain . . . . . . . . . . . . . . .
1.8.3 Universal Bounds . . . . . . . . .
1.8.4 Covering Relation . . . . . . . .
1.8.5 Maximal and Minimal Elements
1.8.6 Supremum and Infimum . . . . .
1.9 Lattices . . . . . . . . . . . . . . . . . .
1.9.1 Lattice Algebra . . . . . . . . . .
1.9.2 Sublattices . . . . . . . . . . . .
1.9.3 Bounded Lattices . . . . . . . . .
1.9.4 Distributive Lattices . . . . . . .
1.9.5 Trivially Complement . . . . . .
1.10 Mapping . . . . . . . . . . . . . . . . . .
1.10.1 Types of Functions . . . . . . . .
1.10.2 Composite mapping . . . . . . .
1.11 Permutation . . . . . . . . . . . . . . . .
1.11.1 Equal permutations . . . . . . .
1.11.2 Identity permutation . . . . . . .
1.11.3 Product of permutations . . . . .
1.11.4 Inverse of permutations . . . . .
iii

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

1
1
2
3
6
6
7
8
9
10
11
11
15
18
20
22
30
31
34
35
36
36
37
38
40
42
44
45
45
45
46
47
48
57
63
63
63
63
64

iv

CONTENTS
1.11.5 Cyclic permutation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1.12 Enumerable Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

2 Theory of Numbers
2.1 Number System . . . . . . . . . . . . . . .
2.1.1 Non-positional Number System . . .
2.1.2 Positional Number System . . . . .
2.2 Natural Number . . . . . . . . . . . . . . .
2.2.1 Basic Properties . . . . . . . . . . .
2.2.2 Well Ordering Principle . . . . . . .
2.2.3 Mathematical Induction . . . . . . .
2.3 Integers . . . . . . . . . . . . . . . . . . . .
2.3.1 Divisibility . . . . . . . . . . . . . .
2.3.2 Division Algorithm . . . . . . . . . .
2.4 Common Divisor . . . . . . . . . . . . . . .
2.4.1 Greatest Common Divisor . . . . . .
2.5 Common Multiple . . . . . . . . . . . . . .
2.5.1 Lowest Common Multiple . . . . . .
2.6 Diophantine Equations . . . . . . . . . . . .
2.6.1 Linear Diophantine Equations . . . .
2.7 Prime Numbers . . . . . . . . . . . . . . . .
2.7.1 Relatively Prime Numbers . . . . . .
2.7.2 Fundamental Theorem of Arithmetic
2.8 Modular/Congruence System . . . . . . . .
2.8.1 Elementary Properties . . . . . . . .
2.8.2 Complete Set of Residues . . . . . .
2.8.3 Reduced Residue System . . . . . .
2.8.4 Linear Congruences . . . . . . . . .
2.8.5 Simultaneous Linear Congruences .
2.8.6 Inverse of a Modulo m . . . . . . . .
2.9 Fermats Theorem . . . . . . . . . . . . . .
2.9.1 Wilsons Theorem . . . . . . . . . .
2.10 Arithmetic Functions . . . . . . . . . . . . .
2.10.1 Eulers Phi Function . . . . . . . . .
2.10.2 The Mobius Function: . . . . . . . .
2.10.3 Divisor Function . . . . . . . . . . .
2.10.4 Floor and Ceiling Functions . . . . .
2.10.5 Mod Function . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

83
83
83
84
85
85
85
86
89
90
92
94
95
97
97
99
99
102
103
108
111
111
117
121
122
125
130
131
133
136
136
141
143
144
144

3 Theory of Matrices
3.1 Matrix . . . . . . . . . . . .
3.1.1 Special Matrices . . .
3.1.2 Square Matrix . . . .
3.2 Matrix Operations . . . . . .
3.2.1 Equality of matrices .
3.2.2 Matrix Addition . . .
3.2.3 Matrix Multiplication
3.2.4 Transpose of a Matrix
3.3 Few Matrices . . . . . . . . .
3.3.1 Nilpotent Matrix . . .
3.3.2 Idempotent Matrix . .

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

149
149
149
150
153
153
153
154
160
161
161
162

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.

CONTENTS

3.3.3 Involuntary Matrix . . . . . . . . . . . . . . . .

3.3.4 Periodic Matrix . . . . . . . . . . . . . . . . . .
3.3.5 Symmetric Matrices . . . . . . . . . . . . . . .
3.3.6 Skew-symmetric Matrices . . . . . . . . . . . .
3.3.7 Normal Matrix . . . . . . . . . . . . . . . . . .
3.4 Determinants . . . . . . . . . . . . . . . . . . . . . . .
3.4.1 Product of Determinants . . . . . . . . . . . .
3.4.2 Minors and Co-factors . . . . . . . . . . . . .
3.4.3 Adjoint and Reciprocal of Determinant . . . .
3.4.4 Symmetric and Skew-symmetric Determinants
3.4.5 Vander-Mondes Determinant . . . . . . . . . .
3.4.6 Cramers Rule . . . . . . . . . . . . . . . . . .
3.5 Complex Matrices . . . . . . . . . . . . . . . . . . . .
3.5.1 Transpose Conjugate of a Matrix . . . . . . . .
3.5.2 Harmitian Matrix . . . . . . . . . . . . . . . .
3.5.3 Skew-Harmitian Matrix . . . . . . . . . . . . .
3.5.4 Unitary Matrix . . . . . . . . . . . . . . . . . .
3.5.5 Normal Matrix . . . . . . . . . . . . . . . . . .
3.6 Adjoint of a Matrix . . . . . . . . . . . . . . . . . . . .
3.6.1 Reciprocal of a Matrix . . . . . . . . . . . . . .
3.6.2 Inverse of a Matrix . . . . . . . . . . . . . . . .
3.6.3 Singular Value Decomposition . . . . . . . . . .
3.7 Orthogonal Matrix . . . . . . . . . . . . . . . . . . . .
3.8 Submatrix . . . . . . . . . . . . . . . . . . . . . . . . .
3.9 Partitioned Matrix . . . . . . . . . . . . . . . . . . . .
3.9.1 Square Block Matrices . . . . . . . . . . . . . .
3.9.2 Block Diagonal Matrices . . . . . . . . . . . . .
3.9.3 Block Addition . . . . . . . . . . . . . . . . . .
3.9.4 Block Multiplication . . . . . . . . . . . . . . .
3.9.5 Inversion of a Matrix by Partitioning . . . . . .
3.10 Rank of a Matrix . . . . . . . . . . . . . . . . . . . . .
3.10.1 Elementary Operation . . . . . . . . . . . . . .
3.10.2 Row-reduced Echelon Matrix . . . . . . . . . .
3.11 Elementary Matrices . . . . . . . . . . . . . . . . . .
3.11.1 Equivalent Matrices . . . . . . . . . . . . . . .
3.11.2 Congruent Matrices . . . . . . . . . . . . . . .
3.11.3 Similar Matrices . . . . . . . . . . . . . . . . .
4 Vector Space
4.1 Vector Space . . . . . . . . . . . . . . . . . . .
4.1.1 Vector Subspaces . . . . . . . . . . . . .
4.2 Linear Sum . . . . . . . . . . . . . . . . . . . .
4.2.1 Smallest Subspace . . . . . . . . . . . .
4.2.2 Direct Sum . . . . . . . . . . . . . . . .
4.3 Quotient Space . . . . . . . . . . . . . . . . . .
4.4 Linear Combination of Vectors . . . . . . . . .
4.4.1 Linear Span . . . . . . . . . . . . . . . .
4.4.2 Linearly Dependence and Independence
4.5 Basis and Dimension . . . . . . . . . . . . . . .
4.6 Co-ordinatisation of Vectors . . . . . . . . . . .
4.6.1 Ordered Basis . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

163
163
163
164
165
166
171
181
183
184
186
186
189
190
190
191
192
192
192
195
195
201
202
205
206
206
207
208
208
209
211
212
213
216
218
220
220

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.

235
235
240
246
247
247
249
251
252
257
262
277
278

vi

CONTENTS
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

278
279
279
281
283

5 Linear Transformations
5.1 Linear Transformations . . . . . . . . . . . . . .
5.1.1 Kernal of Linear Mapping . . . . . . . . .
5.1.2 Image of Linear Mapping . . . . . . . . .
5.2 Isomorphism . . . . . . . . . . . . . . . . . . . .
5.3 Vector Space of Linear Transformation . . . . . .
5.3.1 Product of Linear Mappings . . . . . . . .
5.3.2 Invertible Mapping . . . . . . . . . . . . .
5.4 Singular and Non-singular Transformation . . . .
5.5 Linear Operator . . . . . . . . . . . . . . . . . .
5.6 Matrix Representation of Linear Transformation
5.7 Orthogonal Linear Transformation . . . . . . . .
5.8 Linear Functional . . . . . . . . . . . . . . . . . .
5.8.1 Dual Space . . . . . . . . . . . . . . . . .
5.8.2 Second Dual Space . . . . . . . . . . . . .
5.8.3 Annihilators . . . . . . . . . . . . . . . . .
5.9 Transpose of a Linear Mapping . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

293
293
297
300
311
316
318
321
324
326
327
341
344
345
349
350
354

6 Inner Product Space

6.1 Inner Product Space . . . . . .
6.1.1 Euclidean Spaces . . . .
6.1.2 Unitary Space . . . . .
6.2 Norm . . . . . . . . . . . . . .
6.3 Orthogonality . . . . . . . . . .
6.3.1 Orthonormal Set . . . .
6.3.2 Orthogonal Complement
6.3.3 Direct Sum . . . . . . .
6.4 Projection of a Vector . . . . .

4.7

4.8

4.6.2 Co-ordinates . . . . . . .
Rank of a Matrix . . . . . . . . .
4.7.1 Row Space of a Matrix . .
4.7.2 Column Space of a Matrix
Isomorphic . . . . . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

365
365
365
366
369
374
375
376
377
380

7 Matrix Eigenfunctions
7.1 Matrix Polynomial . . . . . . . . . .
7.1.1 Polynomials of Matrices . . .
7.1.2 Matrices and Linear Operator
7.2 Characteristic Polynomial . . . . . .
7.2.1 Eigen Value . . . . . . . . . .
7.2.2 Eigen Vector . . . . . . . . .
7.2.3 Eigen Space . . . . . . . . . .
7.3 Diagonalization . . . . . . . . . . . .
7.3.1 Orthogonal Diagonalisation .
7.4 Minimal Polynomial . . . . . . . . .
7.5 Bilinear Forms . . . . . . . . . . . .
7.5.1 Real Quadratic Forms . . . .
7.6 Canonical Form . . . . . . . . . . . .
7.6.1 Jordan Canonical Form . . .
7.7 Functions of Matrix . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

395
395
395
396
396
398
398
410
413
417
420
425
425
427
435
439

.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.

CONTENTS
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

440
441
443
443
445
446

8 Boolean Algebra
8.1 Operation . . . . . . . . . . . . . . . . . . . . .
8.1.1 Unary Operation . . . . . . . . . . . . .
8.1.2 Binary Operation . . . . . . . . . . . . .
8.2 Boolean Algebra . . . . . . . . . . . . . . . . .
8.2.1 Boolean Algebra as a Lattice . . . . . .
8.2.2 Boolean Algebra as an Algebraic System
8.2.3 Boolean Algebra Rules . . . . . . . . . .
8.2.4 Duality . . . . . . . . . . . . . . . . . .
8.2.5 Partial Order Relation . . . . . . . . . .
8.3 Boolean Function . . . . . . . . . . . . . . . . .
8.3.1 Constant . . . . . . . . . . . . . . . . .
8.3.2 Literal . . . . . . . . . . . . . . . . . . .
8.3.3 Variable . . . . . . . . . . . . . . . . . .
8.3.4 Monomial . . . . . . . . . . . . . . . . .
8.3.5 Polynomial . . . . . . . . . . . . . . . .
8.3.6 Factor . . . . . . . . . . . . . . . . . . .
8.3.7 Boolean Function . . . . . . . . . . . . .
8.4 Truth Table . . . . . . . . . . . . . . . . . . .
8.5 Disjunctive Normal Form . . . . . . . . . . . .
8.5.1 Complete DNF . . . . . . . . . . . . . .
8.6 Conjunctive Normal Form . . . . . . . . . . . .
8.6.1 Complete CNF . . . . . . . . . . . . . .
8.7 Switching Circuit . . . . . . . . . . . . . . . . .

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

455
455
455
455
455
455
456
460
461
466
467
467
467
468
468
468
468
468
469
470
470
472
472
475

7.8

7.9

7.7.1 Powers of a Matrix . . . . . . . .

7.7.2 Roots of a Matrix . . . . . . . .
Series . . . . . . . . . . . . . . . . . . .
7.8.1 Exponential of a Matrix . . . . .
7.8.2 Logarithm of a Matrix . . . . . .
Hyperbolic and Trigonometric Functions

vii
.
.
.
.
.
.

.
.
.
.
.
.

.
.
.
.
.
.

Chapter 1

Theory of Sets
George Cantor gave an intuitive definition of sets in 1895. Sets are building blocks of various
discrete structures. The theory of sets is one of the most important tools of mathematics.
The main aim of this chapter is to discuss some properties of sets.

1.1

Sets

A well defined collection of distinct object is defined as set. Each object is known as an
element or member of a set. The following are some examples of the set.
(i) All integers.
(ii) The positive rational numbers less than or equal to 5.
(iii) The planet in solar system.
(iv) Indian rivers.
(v) 4th semester B.Sc. students of Burdwan University.
(vi) The peoples in particular locality.
(vii) Cricketers in the world.
By the term well defined, we mean that we are given a collection of objects with certain
definite property or properties, given in such a way that we are clearly able to distinguish
whether a given object is our collection or not. The following collections are not examples
of set.
(i) Good students of a class, because good is not well-defined word, a student may be
good for particular people, but he/she may not be good for other people.
(ii) Tall students, tall is not well-defined measurement.
(iii) Girls and boys of a particular locality, because there is no sharp boundary of age for
which a female can surely identify.
These type of collections are designated as fuzzy sets. The elements of a set must be
distinct and distinguishable. By distinct, it means that no element is repeated, and by
distinguishable, means there is no doubt whether an element is either in the set or not in
the set.
(i) The standard mathematical symbols used to represent sets are upper-case letters like
A, B, X, etc. and the elements of the set can be written in lower-case letters like a,
b, p, q, x, y, etc.
(ii) If an element x is a member of a set A, we write x A, read as x belongs to A or
a is an element of S or a is in S. The symbol is a Greek alphabet epsilon. On
1

Theory of Sets
the other hand, if x is not the element of A, then we write x 6 A , which is read as x
does not belong to A or x is not an element of the set A.

(iii) If A is a set and a is any object, it should be easy to decide whether a A or a 6 A.

Only then is A termed well-defined.
For example, A = {1, 2, 3, 4, 5} be a set, has elements 1, 2, 3, 4, 5. Here 1 A, but 6 6 A.
Note that, S = {1, 1, 3} is not a set.

1.1.1

Description of Sets

As a set is determined by its elements, we have specify the elements of set A in order to
define A. Five common methods are used to describe the sets, they are (i) roster or list or
enumeration or tabular method, and (ii) selector or rule or set-builder property method (iii)
The characteristics method and (iv) Diagrammatic method.
(i) Roster method
In this method, all elements are listed explicitly separated by commas and are enclosed
within braces { }. Sometimes parenthesis ( ) or square [ ] may also be used.
A set is defined by naming all its members and can be used only for finite sets. Let X,
whose elements are x1 , x2 , , xn is usually written as X = {x1 , x2 , , xn }. For examples,
the set of all natural numbers less than 5 can be represented as A = {1, 2, 3, 4}.
Sometimes, it is not humanly possible to enumerate all elements, but after knowing some
initial elements one can guess the other elements. In this case dots are used at the end within
the braces. For an example, set of positive integers can be written as A = {1, 2, 3, 4, },
set of all integers B = {. . . , 2, 1, 0, 1, 2, . . .}, etc.
It may be noted that the elements of a set can be written in any order, but the name
of an element is listed only once. For example, {2,3,4}, {4,3,2}, {2,4,3} all represent the
same set. Thus, while we describe a set in this manner, the order of the elements is not
important.
(ii) Set-builder method
In this method, a set can be specified by stating one or more properties, which uniquely
satisfy by the elements. A set in this method is written as
A = {x : P1 (x) or P2 (x), etc},

(1.1)

i.e., x A if x satisfy the properties P1 (x), P2 (x), etc. The symbol : is read as such
that, it is also denoted by or /. For example,
A = {x : x is a positive even integers }
B = {x : x is a vowel in English alphabet }
C = {x : x is integer and 1 x 10} etc .
It is required that the property P be such that for any given x U , the universal set, the
proposition P (x) is either true of false.
(iii) The characteristics method
A set is defined by a function, usually called a characteristic function, that declares which
elements of U are members of the set and which are not. Let U = {u1 , u2 , . . . , un } be the
universal set and A U . Then the characteristic
function of A is defined as

1, if ui A
A (ui ) =
(1.2)
0, if ui 6 A.

Sets

i.e., the characteristic function maps elements of U to elements of the set {0, 1}, which
is formally expressed by A : U {0, 1}. For example, let U = {1, 2, 3, . . . , 10} and A =
{2, 4, 6, 8, 10}, then A (2) = 1, A (4) = 1, A (6) = 1, A (8) = 1, A (10) = 1 and A (a) = 0
for all other elements of U . It may be observed that A is onto function but not one-one.
(iv) Diagrammatic method
A set can be represented diagrammatically by closed figures like circles, triangles, rectangles,
etc. The point in the interior of the figure represents the elements of the set. Such a representation is called a Venn diagram or Venn-Euler diagram, after the British mathematician
Venn. In this diagram the universal set U is represented by the interior of a rectangle and
each subset of U is represented by the circle inside the rectangle.
If two sets are equal then they represent by same circle. If the sets A and B are disjoint
then the circles for A and B are drawn in such a way that they have no common area, If
the sets A and B have a small common area. If A B then the circle for A is drawn fully
inside the circle for B. This visual representation helps us to prove the set identities very
easily.
(v) Recursion method
A set can be described by giving one or more elements of the set and a rule for generating
the remaining elements. The underlying process is called recursion. For example, (a) the
set A = {1, 4, 7, } can be described as A = {a0 = 1, an+1 = an + 3}; (b) F = {Fn : F0 =
0, F1 = 1, Fn = Fn1 + Fn2 } is a set described by recursion. This set is called the set of
Fibonacci numbers.
Some standard sets and their notations
Some sets are frequently used in mathematical analysis or in algebraic structure, which are
stated below.
N The set of all natural numbers.
Z The set of all integers.
Z + The set of all positive integer.
Q The set of all rational numbers.
Q+ The set of all positive rational numbers.
R The set of all real numbers.
R+ The set of all positive real numbers.
C The set of all complex numbers.

1.1.2

Types of Sets

Null set
A set which contains no element is called null set or empty set or void set and is denoted by
the Greek alphabet (read as phi). In Roaster method, it is denoted by {}. For example,
A = {x : x2 + 4 = 0 and x R}
is a null set. To describe the null set, we can use any property, which is not true for any
element. It may be noted that the set {} or {0} is not a null set.
A set which is not a null set, is called non-empty set.
Singleton set
A set consisting only a single element is called a singleton or unit set. For example, A = {0},
B ={x: 1 < x < 3, x is integer}, the solution set C = {x : x 2 = 0} = {2} etc., are
examples of singleton set. Note that {0} is not a null set, since it contains 0 as its member,
it is singleton set.

Theory of Sets

Finite and infinite sets

A set containing finite elements is called finite sets, otherwise it is called infinite set, i.e., a
set does not contain a definite number of elements.
(i) A ={x: x is the consonant in English alphabet},
(ii) B ={x: 1 < x < 15, x is integer}
are examples of finite sets, whereas
(i) A ={x: x is a rational numbers},
(ii) B ={x: x is a straight line in space},
are the examples of infinite sets. Here, the process of counting the different elements comes
to one end. Here, the process of counting the different elements comes to an end. We let
|A| to denote the numbers of elements of a finite set A.
Indexed set
A set, whose elements are themselves sets is often referred to as a family of sets. Let us
consider a family of n sets A1 , A2 , . . . , An in the form F = {A | I} where A corresponds
to an element in the set I. I is said to be an indexing set and is called the set index.
In general, I be an arbitrary set then F = {A | I} is an arbitrary collection of sets A
indexed by I.
Set of sets
If the elements of a set be also the some other sets, then this set is known as a family of
sets, or a set of sets. For example, A ={{2, 3}, {5, 6, 8}, z, R+ } is a set of sets.
Subset and superset
Let A and B be two given sets. The set B is said to be a subset of A if
x B = x A,

(1.3)

i.e., every element of B is an element of A. This is very often denoted by B A (written

as B is contained or included in A). This is called set inclusion. For example,
(i) The set of all integers (Z) is the subset of all rational numbers (Q).
(ii) A ={a, b, c, d}, B ={a, b, c, d, e, f }. Here each element of A is also an element of B,
thus A B.
(iii) A ={1, 5, 7} and B ={1, 5, 7}. Here A B and B A.
(iv) is a subset of every set.
(v) The subsets of A ={2, 3, 4} are , {2}, {3}, {4}, {2, 3}, {2, 4}, {3, 4} and {2, 3, 4}.
(vi) A ={2, 3, 5}, B ={2, 3, 6}. Then A 6 B and B 6 A, because, 5 A but 5 6 B and
6 B but 6 6 B.
If B A, then A is called the super set of B, which is read as A is a super set of B.

Sets

Proper subset
The set A is called proper subset of B if every element of A is a member of B and there is
at least one element in B such that it is not in the set A. It is written as A B. Therefore,
B is the proper subset of A if
(i) x B = x A
(ii) y A such that y
/ B.
In this case, B A and A 6= B and B is said to the proper subset of A and is denoted by
B A. If B is the subset of A(i.e. B A) A is called the super set of B. For example,
(i) {1, 2} is the proper subset of {1, 2, 3, 4}.
(ii) The set of vowels is a proper subset of the set of English alphabet
(iii) N (set of natural numbers) is a proper subset of Z (set of integers).
Note the following:
(i) If even a single element in A which is not in B, then A is not a subset of B and we
write A 6 B. For example {1, 2} 6 {2, 4, 6, 8, 9}.
(ii) If A B or B A, then the sets A and B are said to be comparable. For example,
if A = {1, 2}, B = {5, 6, 7} then A 6 B and these are not comparable.
(iii) Every set is a subset of itself and every set is a subset of the universal set.
(iv) has no proper subset. Also, A A = .
(v) For any set A, A A. This is known as the reflexive law of inclusion.
(vi) If A B and B C, then A C. This is known as transitive law of inclusion.
In Venn diagram, the universal set is usually represented by a rectangular region and its
subset by closed bounded regions inside the rectangular region.
Equality of sets
If A B and B A, then A and B contain the same members. Two sets A and B are
said to be equal if every element of A is an element of B and also every element of B is an
element of A. That is, A B and B A. The equality, of two sets is denoted by A = B.
Conversely, if A = B then A B and B A must be satisfied. For example, A = {1, 4, 9}
and B = {4, 9, 1} are equal sets. To indicate that A and B are not equal, we write A 6= B.
Theorem 1.1.1 The null set is a subset of every set.
Proof: Let A be an arbitrary set. Then, in order to show that A, we must show that
there is no element of which is not contained in A. Since contains no element at all, no
such element can therefore be found. Hence, A.
Theorem 1.1.2 The number of subsets of a given set containing n elements is 2n .
Proof: Let A be an arbitrary set containing n elements. Then, one of its subsets is the
empty set. Apart from this,


(i) The number of subsets of A, each containing 1 element = n1 .


(ii) The number of subsets of A, each containing 2 elements = n2 .

Theory of Sets

(iii) The number of subsets of A, each containing 3 elements =

..
.

n
3

(iv) The number of subsets of A, each containing n elements =

n
n

Therefore, the total number of subsets of A is

   
 
n
n
n
=1+
+
+ +
= (1 + 1)n = 2n .
1
2
n
The number of proper subsets of a set with n elements is 2n 1.
Power set
A set formed by the all subsets of a given non empty set set S is called the power set of the
set S and is denoted by P (S). If S = {a, b, c} then
n
o
P (S) = , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} .
Note that P () = {}. The power set of any given set is always non-empty. The family of
all subsets of P (A) is called a second order power set of A and is denoted by P 2 (A), which
stands for P (P (A)). Similarly, higher order power sets P 3 (A), P 4 (A), . . . are defined.
Order of a set is defined by the numbers of elements of A and is denoted by O(A). From
the above property, it is observed that the number of elements of the power set P (A) is 2n
if A contains n elements. For example, if A = {1, 2, 1} then O(A) = 3 and O{P (A)} = 8.
In general, if O(A) = n then O{P (A)} = 2n and O(P 2 (A)) = 22n .
Universal sets
In the theory of set it is observed that all the sets under consideration are the subsets of
a certain set. This set is called the universal set and it is usually denoted by U or S.
Conversely, the universal set is the superset of every set. For example, The set of real
numbers < is the universal set for the set of integers Z and set of rational numbers Q.
Again, the set of integers Z is the universal set for the sets of even integers, set of positive
integers, etc.
This set is of all possible elements that are relevant and considered under particular
context or application from which sets can be formed. The set U is not unique and it is a
super set of each of the given set. In venn diagram, the universal set is usually represented
by a rectangular region.

1.2

Algebraic Operation on Sets

Like addition, multiplication and other operations on numbers in arithmetic, there are certain operations on sets, namely union, intersection, complementation, etc. In this section,
we shall discuss several ways of combining different sets and develop some properties among
them.

1.2.1

Union of Sets

Let A and B be two given subsets of an universal set U . Union (or join) of two subsets A
and B, denoted by A B, is defined by
A B = {x : x A or x B or both},

(1.4)

Algebraic Operation on Sets

here the or is means and/or, i.e. the set contains the elements which either belong to A
or B or both. The Venn diagram of Fig. 1.1 illustrate pictorially the meaning of , where
U is the rectangular area, and A and B are disks. Union is also known as join or logical sum
of A and B. Note that, the common elements are to be taken only once. For example,

Figure 1.1: Venn diagram of A B (shaded area)

(i) If A ={1, 3, 4, 5, a, b} and B ={a, b, c, 2, 3, 4, 6} then
A B ={1, 2, 3, 4, 5, 6, a, b, c}.
(ii) If A = [2, 5] and B = [1, 3], then A B = [1, 5] = {x : 1 x 5}.
From the Venn diagram we get the following properties of set union:
(i) Union s idempotent, i.e., A A = A,
(ii) Set union is associative, i.e., (A B) C = A (B C),
(iii) A U = U : Absorption by U . A = A: identity law
(iv) Set union is commutative, i.e., A B = B A,
(v) A A B and B A B for sets A and B.
(vi) If A U A U = U , U = the universal set and if A B then A B = B.
The union operation can be generalized for any number of sets. The union of the subsets
A1 , A2 , . . . , An is given by,
n
[
Ai = A1 A2 . . . An = {x : x Ai ; for some i = 1, 2, . . . , n}
i=1

and for a family of sets {Ai ; i I} is defined as

[
Ai = {x : x Ai , for some i I}.
iI

1.2.2

Intersection of Sets

Let A and B be two given subsets of an universal set U . The intersection of A and B is
denoted by A B and is defined by
A B = {x : x A and x B}.
(1.5)
The intersection of the sets A and B is the set of all elements which are in both the sets A
and B. The AB is shown in Fig. 1.2. The intersection is also known as meet. AB is read
as A intersection B or A meet B. For example, (i) let A ={2, 5, 6, 8} and B ={2, 6, 8, 9, 10}
then A B ={2, 6, 8} (ii) if A = [2, 5] and B = [1, 3], then A B = [2, 3] = {x : 2 x 3}.
From the Venn diagram we get the following properties of intersection:

Theory of Sets

Figure 1.2: Venn diagram of A B (shaded area)

(i) Intersection is idempotent, i.e., A A = A, follows from A A,
(ii) A B A ; A B B and A B then A B = A.
(iii) A = : absorption by .

A U = A: identity law.

(iv) Set intersection is commutative, i.e., A B = B A.

(v) Set intersection is associative, i.e., (A B) C = A (B C).
The intersection of the n subsets is given by
n
\
Ai = A1 A2 . . . An = {x : x Ai , i}.
i=1

Ex 1.2.1 For given two sets A = {x : 2 cos2 x + sinx 2}; B = {x : x [ 2 , 3

2 ]}, find
A B. [KH 06]
Solution: The solution of the trigonometric relation 2 cos2 x + sinx 2 is given by,
2 cos2 x + sinx 2 sin x[1 2 sin x] 0
sin x 0 and 1 2 sin x 0
or sin x 0 and 1 2 sin x 0
1
sin x 0 or sin x .
2
If x [ 2 , 3
2 ], then the solutions of sin x 0 are given by x
sin x 12 are given by 2 x 5
6 . Therefore,

 

3
5
A B = ,

,
.
2
2 6

1.2.3

3
2

and the solutions of

Disjoint Sets

It is sometimes observed that the intersection between two non-empty sets produced a null
set. In this case, no element is common in A and B and these two sets are called disjoint
or mutually exclusive sets. Thus two sets A and B are said to be disjoint if and only if
A B = , i.e. they have no element in common. Then Venn diagram of disjoint sets A and
B is shown in Fig. 1.3. For example, (i) A = {1, 2, 3} and B = {6, 7, 9} and (ii) if A ={x:
x is even integer} and B ={x: x is odd integer} then A B = , i.e., A and B are disjoint.
When A B 6= , the sets A and B are said to be intersecting.
Note 1.2.1 The three relations B A, A B = A and A B = B are mutually equivalent,
i.e., one implies the other two.

Algebraic Operation on Sets

Figure 1.3: Disjoint sets A and B

1.2.4

Complement of a Set

Let A be a subset of an universal set U . Then complement of a subset A, with respect to

U , denoted by A0 , Ac , A or A, is defined by
A0 = {x : x U but x 6 A},

(1.6)

i.e., the set contains the elements which belong to the universal set U but not elements of
A. The venn diagram of Ac is shown in Fig. 1.4. Clearly, if A0 is the complement of A, then
#

A
"!
Ac
Figure 1.4: Complement of A
A is a complement of A0 . For example, let A = {1, 3, 5, 7, 9}, if U = {1, 2, 3, 4, 5, 6, 7, 8, 9}
then A0 = {2, 4, 6, 8}. From Venn diagram we have
(i) (A0 )0 = A : involution property.
(ii) U 0 = ; 0 = U .
(iii) If A B then B c Ac and conversely, if Ac B c then B A.
(iv) A A0 = U : law of excluded middle.

A A0 = : law of contradiction.

(v) (a) (A B)c = Ac B c and (b) (A B)c = Ac B c : De Morgans laws.

In particular, for a finite family of subsets F = {A1 , A2 , . . . , An }, the De Morgans law can
be written as
!0
!0
n
n
n
n
\
\
[
[
0
Ai =
Ai and
Ai =
A0i .
i=1

i=1

i=1

i=1

Ex 1.2.2 Prove that (A C) (B C 0 ) = A B = .

Solution: The relation (A C) (B C 0 ) = gives A C = and B C 0 = . Now,
B C 0 = B C.
Therefore, A C = A B = .

10

1.2.5

Theory of Sets

Difference

Let A, B be any two subsets of an universal set U . The difference of two subsets A and B
of an universal set U is a subset of A, denoted by A B or A/B and is defined by
A B = {x : x A and x
/ B},
(1.7)
i.e., the set containing of those elements of A which are not elements of B. Also
B A = {x : x B and x 6 A}.

(1.8)

This is also called the relative component of the set B with respect to the set A. A B is
called the complement of B relative to A. The differences A B and B A are shown in
B

6
AB

6
BA

Figure 1.5: Set difference A B and B A

Fig. 1.5. A B is read as A difference B or A minus B. For example, if A ={2, 4, 5, 8}
and B ={2, 5, 7, 10} then A B ={4, 8} and B A ={7, 10}. From the Venn diagram we
have:
(i) A A = , A = A,
(ii) A B A, B A B, and A B = A if A B = .
(iii) Set difference is non-commutative, i.e., A B 6= B A,
(iv) A B = when A B.
(v) A A = then A B = A and B A = B,
(vi) A B = A B 0 .
(vii) (A B)A = A, (A B) B = A B and (A B) B = .
(viii) A B = A if and only if A B = .
(ix) A B, A B and B A are mutually exclusive.
If the set A is the universal set, the complement is absolute, known as complementation and
is usually denoted by B.
Ex 1.2.3 For two subsets A and B of an universal set U , show that
A (B C) = (A B) (A C).
Solution: Let x be any element of A (B C), then by definition,
A (B C) {x :
{x :
{x :
{x :

x A and x 6 (B C)}
x A and (x 6 B or x 6 C)}
(x A and x 6 B) or (x A and x C)}
x (A B) or x (A C)} = (A B) (A C).

Hence, A (B C) (A B) (A C) and (A B) (A C) A (B C), consequently,

A (B C) = (A B) (A C).

Duality and Algebra Sets

1.2.6

11

Symmetric Difference

If A and B be two subsets of an universal set U . The symmetric difference, denoted by

AB or A B, is defined by
AB = = {x : x A or x B but x 6 B}
= {x : (x A and x
/ B) or (x B and x
/ A)}.
The set (A B) (B A) is also called the symmetric difference of A and B. Thus,
AB = (A B) (A B) = (A B 0 ) (A0 B)
= (A B) 4 (A B).
The Venn diagram of AB is shown in Fig. 1.6. If A = {1, 2, 4, 7, 9} and B = {2, 3, 7, 8, 9}

}
A4B
Figure 1.6: Symmetric difference of A and B (shaded ares)
then, AB = {1, 3, 4, 8}. Note that,
(A B) (B A) = (A B 0 ) (B A0 )
= A (B B 0 ) A0
= (A ) A0 = A A0 = .
Therefore, A 4 B can be considered as the union of disjoint subsets A B and B A,
provided A B and B A are both non empty. From the definition, we have the following,
(i) Symmetric difference is commutative, i.e., AB = BA,
(ii) Symmetric difference is associative, i.e., (AB)C = A(BC),
(iii) A = A, for all subsets of A.
(iv) AA = , for all subsets of A.
(v) AB = iff A = B,
(vi) A (B 4 C) = (A B) 4 (A C) : Distributive property.

1.3

Duality and Algebra Sets

Principle of duality
Let E is an equation(or law) of set algebra (involving , , U , ). If we replace by ,
by , U by and by U in E then we obtain E another law, which is also a valid law.
This is known as principle of duality. For example,

12

Theory of Sets

(i) A (B C) = (A B) (A C), its dual law is A (B C) = (A B) (A C),

(ii) A A = its dual is A A = U .
It is a fact of set algebra, called the principle of duality, that, if any equation E is an identity,
then its dual E is also an identity.
Algebra of sets
Some commonly used laws of sets are stated below. Note that the law stated in (b) is the
dual law of (a) and conversely.
1. Idempotent laws
(a) A A = A
(b) A A = A.
2. Identity laws
(i)
(a) A = A
(b) A U = A.
(ii)
(a) A =
(b) A U = U.
3. Commutative laws
(a) A B = B A
(b) A B = B A.
4. Associative laws
(a) (A B) C = A (B C)
(b) (A B) C = A (B C).
5. Distributive laws
(a) A (B C) = (A B) (A C)
(b) A (B C) = (A B) (A C)
6. Inverse law
(b) A Ac =
(a) A Ac = U
7. Domination laws
(a) A U = U
(b) A =
8. Absorption laws
(a) A (A B) = A
(b) A (A B) = A
9. De Morgans laws
(a) (A B)c = Ac B c
(b) (A B)c = Ac B c .
Let S1 and S2 be two set expressions. The notation S1 S2 as well as S2 S1 . These
are the main algebraic operations on sets.
Property 1.3.1 Let A, B and C are any three finite sets, then
[WBUT 09]
(i) A (B C) = (A B) (A C); (ii) A (B C) = (A B) (A C)
Proof: (i) Let x be any element of A (B C). Then,
x A (B C) x A or x (B C).
x A or (x B and x C)
(x A or x B) and (x A or x C)
(x A B) and (x A C)
x (A B) (A C).
The symbol stands implies and is implied by. It also stands for if and only if. Hence
A (B C) (A B) (A C) and (A B) (A C) A (B C). Hence
A (B C) = (A B) (A C).
(ii) Let x be any element of A (B C). Then,
x A (B C) x A x (B C)
x A (x B x C)
(x A x B) (x A x C)
(x A B) (x A C)
x (A B) (A C)

Duality and Algebra Sets

13

Hence, A (B C) (A B) (A C) and (A B) (A C) A (B C). Hence,

A (B C) = (A B) (A C).
Property 1.3.2 Let A, B and C are any three finite sets. Then,
(i) (A B)0 = A0 B 0 .
(ii) (A B)0 = A0 B 0 .
(iii) A (B C) = (A B) (A C).
(iv) A (B C) = (A B) (A C)
Proof: (i) Let x be an arbitrary element of (A B)0 . Then,
x (A B)0 x
/ (A B)
x
/ A and x
/B
x A0 and x B 0
x (A0 B 0 )
Hence (A B)0 A0 B 0 and A0 B 0 (A B)0 . Therefore,
(A B)0 = A0 B 0 .
(ii) Similarly, (A B)0 = A0 B 0 .
(iii) Let x be an arbitrary element of A (B C). Now,
x [A (B C)] [(x A) and x
/ (B C)]
[(x A) and (x
/ B and x
/ C)]
[(x A and x
/ B) and (x A and x
/ C)]
[x (A B)] and [x (A C)]
x [(A B) (A C)]
Thus, A (B C) (A B) (A C) and (A B) (A C) A (B C) and so,
A (B C) = (A B) (A C).
(iv) Similarly, A (B C) = (A B) (A C).
Ex 1.3.1 Prove that (A C) (B C) = (A B) C.
Solution: We shall use suitable laws of algebra in sets. Using the results A C = A C 0 ;
B C = B C 0 , we get,
L.H.S = (A C) (B C) = (A C 0 ) (B C 0 )
= (A C 0 ) (C 0 B) = {(A C 0 ) C 0 } B
= (A C 0 ) B = (A B) C 0
= (A B) C = R.H.S.(proved)
Ex 1.3.2 Show (A B) (B A) = (A B) (A B), where A, B, C are three sets.
Solution: We shall use suitable laws of algebra in sets. Using the results A B = A B 0 ;
B A = B A0 , we get,
L.H.S = (A B) (B A) = (A B 0 ) (B A0 )
= {(A B 0 ) B} {(A B 0 ) A0 }
= {(A B) (B B 0 )} {(A A0 ) (B 0 A0 )}
= {(A B) S} {S (B 0 A0 )} ; S being U niversal set.
= (A B) (B 0 A0 ) = (A B) (A B)0
= (A B) (A B) = R.H.S.(proved)

14

Theory of Sets

Ex 1.3.3 Show that (A B) (A C) = (A B) C, where A, B, C are sets.

Solution: We shall use suitable laws of algebra in sets.
L.H.S = (A B) (A C) = (A B) (A C)0
= (A B) (A0 C 0 ) = {(A B) A0 } {(A B) C 0 }
= { (A B)} {(A B) C 0 }
= (A B) C 0 = (A B) C 0
= (A B) C = R.H.S.(proved)
Ex 1.3.4 Show that (A B C) (A B C 0 ) (A B 0 C) (A B 0 C 0 ) = A, where
A, B, C are sets.
[ KH 07]
Solution: We shall use suitable laws of algebra in sets.
L.H.S = (A B C) (A B C 0 ) (A B 0 C) (A B 0 C 0 )
= (X C) (X C 0 ) (Y C) (Y C 0 ) where X = A B , Y = A B 0 .
= [X (C C 0 )] [Y (C C 0 )]
= (X U ) (Y U ); where U = U niversal set.
= X Y = (A B) (A B 0 )
= A (B B 0 ) = A U = A = R.H.S.(P roved).
Ex 1.3.5 If A B = A C and A B = A C simultaneously for subsets A, B, C of a set
S, prove that B = C.
[ CH 09]
Solution: We shall use suitable laws of algebra in sets.
L.H.S = B = (A B) B = (A B) (B B)
= (A C) B [as A B = A C]
= (A B) (C B)
= (A C) (B C) [as A B = A C]
= (A C) C = C = R.H.S.(P roved).
From this, we conclude only A B = A C or only A B = A C does not necessarily
imply B = C.
Ex 1.3.6 Define complement of A by A0 such that A A0 = S, A A0 = show that
(A B)0 = A0 B 0 .
Solution: Let C = A B and D = A0 B 0 . We shall show that D = C 0 . Now,
C D = (A B) (A0 B 0 )
= (A B A0 ) (A B B 0 )
= {(A A0 ) B} {A (B B 0 )}
= {S B} {A S} = S S = S.
Also using the relations C = A B and D = A0 B 0 , we get,
C D = (A B) (A0 B 0 )
= (A A0 B 0 ) (B A0 B 0 )
= ( B 0 ) ( A0 ) = = .
Hence C 0 = D i.e. (A B)0 = A0 B 0 .

Cartesian Product of Sets

15

Ex 1.3.7 If A B and C is any set then show that A C B C.

Solution: Let x be any element of A C. Hence,
x A C x A or x C.
Again, x A x B (since A B). Therefore,
x A C x A or x C
x B or x C
x B C.
Again, x C x B C. Hence, A C B C. (Proved)
Ex 1.3.8 Prove that (A0 B 0 C) (B C) (A C) = C.
Solution: L.H.S. = (A0 B 0 C) (B C) (A C). Now consider,
(B C) (A C) = (C B) (C A)
= C (B A) = (A B) C.
Now again, A0 B 0 C = (A B)0 C. Hence,
L.H.S. = {A B)0 C} {(A B) C}
= {(A B)0 (A B)} C = S C (S = U niversal set)
= C = R.H.S. (P roved).
Ex 1.3.9 A, B, C are subsets of U , prove that [A (B C)] [A0 (B 0 C 0 )] = .
Solution: Using the properties of sets, we get,
LHS = [A (B C)] [A0 (B 0 C 0 )]
= [A (B C) A0 ] [A(B C) (B 0 C 0 )]
= [A A0 (B C)] [A (B C) (B C)0 ]
= [ (B C)] [A ] = = .

1.4

Cartesian Product of Sets

Let A and B are two nonempty sets. An order pair consists of two elements, say a A
and b B, and it is denoted by (a, b). The element a is called the first element or first
coordinate and the element b is called the second element or second coordinate. The ordered
pairs (a, b) and (b, a) are distinct unless a = b. Thus (a, a) is a well-defined ordered pair.
If a, c A and b, d B, two ordered pairs (a, b) and (c, d) are said to be equal, i.e.,
(a, b) = (c, d) if and only if a = c and b = d.
An order triple is ordered triple of objects (a, b, c) where a is first, b is second and c is
third element of triple. An order triple can also be written in terms of ordered pairs as
{(a, b), c}. Similarly, ordered quadruple is an ordered pair {((a, b), c), d} with first element
as ordered pair.
Definition 1.4.1 Let A and B be any two finite sets. The cartesian product (or cross
product or direct product) of A and B, denoted by A B, (read as A cross B), is the set
defined by,
n
o
A B = (x, y)|x A and y B

16

Theory of Sets

i.e., A B is the set of all distinct order pairs (x, y), the first element of the pair is an
element of A and the second is an element of B. For example, let A ={a, b} and B ={1, 2,
3}. Then
A B ={(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)} and
B A ={(1, a), (2, a), (3, a), (1, b), (2, b), (3, b)}.
The geometric representation of A B is depicted in the Fig. 1.7.
3 6 (a, 3)

(b, 3)

(a, 2)

(b, 2)

(a, 1)

(b, 1)

Figure 1.7: Representation of A B

From this example, it is observed that A B 6= B A, so in general, A B 6= B A.
Let A1 , A2 , , An be finite collection of non-empty sets. The cartesian product of the
collection, denoted by A1 A2 An , is the set defined by,
n
Y

Ai = A1 A2 An = {(x1 , x2 , , xn ) : xi Ai }.

i=1

In particular, if A1 = A2 = = An = A, the cartesian product of the collection of sets,

denoted by An , is the set of all ordered n tuples,
An = {(x1 , x2 , , xn ) : xi A}.
If A = B = <, the set of all real numbers, then < < (= <2 ) is a set of all points in the
plane. The ordered pair (a, b) represents a point in the plane. Similarly, < < < (= <3 )
is a set of all points in space, i.e, (a, b, c) < < < is a point in space. Below are some
important properties of cartesian product
(i) The cartesian product is non-commutative, i.e., in general A B 6= B A.
(ii) n(A) = p and n(B) = q then n(A B) = n(B A) = pq.
(iii) If A = or B = then A B = .
(iv) If either A or B is infinite and other is empty then A B = .
(v) If either A or B is infinite and other is non-empty then A B is infinite.
Following are some results on cartesian product.
(i) If A B then A C B C for any sets A, B, C.
(ii) If A B and C D then A C B D.
(iii) If A B then A A = (A B) (B A).

Cartesian Product of Sets

17

Result 1.4.1 For any non-empty sets A and B, A B = B A iff A = B.

Proof: Let A B = B A. Then let,
x A (x, y) A B, where y B
(x, y) B A, since A B = B A
x B.
Thus A B. Similarly, B A. Hence A = B. Conversely, let A = B. Then A B = A A
and B A = A A. Hence, A B = B A.
Ex 1.4.1 For three non-empty sets A, B, C, prove that
A (B C) = (A B) (A C).
Solution: This result is the direct consequence of the definition. Let (x, y) be an arbitrary
element of the set A (B C). Then,
(x, y) A (B C) x A and y (B C)
x A and [y B and y C]
[x A and y B] and [x A and y C]
[(x, y) A B] and [(x, y) A C]
(x, y) (A B) (A C).
Therefore, A (B C) (A B) (A C) and (A B) (A C) A (B C) and
consequently, A (B C) = (A B) (A C). Similarly,
A (B C) = (A B) (A C).
Ex 1.4.2 For any three sets A, B, C prove that
A (B C) = (A B) (A C).
Solution: Let (x, y) be an arbitrary element of A (B C). Then,
(x, y) A (B C) x A and y (B C)
x A and [y B and y 6 C]
[x A and y B] and [x A and y 6 C]
[(x, y) (A B)] and [(x, y) 6 (A C)]
(x, y) (A B) (A C).
Therefore, A (B C) (A B) (A C) and (A B) (A C) A (B C) and
consequently, A (B C) = (A B) (A C).
Ex 1.4.3 For any sets A, B, C and D, we have,
(A B) (C D) = (A C) (B D).

[ CH 96, 01]

Solution: Let (x, y) be an arbitrary element of (A B) (C D). Then,

(x, y) (A B) (C D) (x, y) (A B) and (x, y) (C D)
(x A and y B) and (x C and y D)
(x A and x C) and (y B and y D)
x (A B) and y (B D)
(x, y) (A C) (B D).
Thus, (A B) (C D) (A C) (B D) and (A C) (B D) (A B) (C D),
so that (A B) (C D) = (A C) (B D). Similarly, for any sets A, B, C and D, we
have A B and C D (A C) (B D).

18

1.5

Theory of Sets

Cardinal Numbers

The number of distinct elements in a set A is called the cardinal number of the set and it
is denoted by n(A) or |A| or card(A). For example, n() = 0, n({a}) = 1, n({a, b}) = 2,
n(Z) = , etc. Following are the important properties of cardinal number
(i) If A and B are disjoint, then
(a) n(A B) = n() = 0 and (b) n(A B) = n(A) + n(B),
(ii) Let A and B be two finite sets, with A B 6= , then
n(A B) = n(A) + n(B) n(A B),
(iii) If A, B, C be three arbitrary finite sets then
n(A B C) = n(A) + n(B) + n(C) n(A B)
n(B C) n(C A) + n(A B C),
(iv) Suppose we have any finite number of finite sets, say, A1 , A2 , , Am . Let sk be the
sum of the cardinalities, then
n(A1 A2 Am ) = s1 s2 + s3 + (1)m1 sm .
(v) n(A A) = n(A) and n(A A) = n(A).
The inclusion and exclusion principle
The number of elements in finite sets such as A B, A B, AB, etc. are obtained by
adding and as well as deleting certain elements. This method of finding the number of
elements in a finite set is known as inclusion and exclusion principle.
Ex 1.5.1 If n(A) and n(B) denote the number of elements in the finite sets A and B
respectively, then prove that n(A) + n(B) = n(A B) + n(A B).
Solution: If A and B are disjoint then n(A B) is equal to the sum of the elements of
A and the elements of B. That is n(A B) = n(A) + n(B). If A and B are disjoint then
A

6
K
7
B (A B) A (A B)
AB
Figure 1.8:
A B is express as union of three disjoint sets A B, A (A B) and B (A B). Let
us draw the Venn diagram showing A B 0 , A B, A0 B and A0 B 0 , where A and B are
two subsets of the universal set U . From the diagram, we have,
A = (A B 0 ) (A B) and B = (A B) (A0 B)
and the sets A B 0 , A B and A0 B are disjoint. Therefore,
n(A) = n(A B 0 ) + n(A B) and n(B) = n(A B) + n(A0 B)
n(A) + n(B) = n(A B 0 ) + 2n(A B) + n(A0 B).

Cardinal Numbers

19

Again, from the diagram, we have,

A B = (A B 0 ) (A B) (A0 B),
in which (A B 0 ), (A B) and (A0 B) are disjoint sets and so