2
Mathematical
Preliminaries
In this chapter we introduce the concepts of set theory and graph theory. Also,
we define strings and discuss the properties of stlings and operations on strings.
In the final section we deal with the principle of induction, which will be used
for proving many theorems throughout the book.
2.1 SETS, RELATIONS AND FUNCTIONS
2.1.1 SETS AND SUBSETS
A set is a well-defined collection of objects, for example, the set of all students
in a college. Similarly. the collection of all books in a college library is also a
set. The individual objects are called members or elements of the set.
We use the capital letters A, B, C, ... for denoting sets. The small letters
a, b, c, ... are used to denote the elements of any set. When a is an element
of the set A. we write a E A. "\Then a is not an element of A, we write a rl. A.
Various Ways of Describing a Set
(i) By listing its elements. We write all the elements of the set (without
repetition) and enclose them within braces. We can write the elements
in any order. For example, the set of all positive integers divisible by
15 and less than 100 can be wlitten as {IS. 30, 45. 60. 75. 90}.
(ii) By describing the properties of the elements of the set. For example. the
set {IS, 30. 45. 60. 75. 90} can be described as: {n In is a positive
integer divisible by 15 and less than 100}. (The descliption of the
property is called predicate. In this case the set is said to be implicitly
specified.)
36
http://engineeringbooks.net