SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

Course
UNIT II SET Material
THEORY
SMT5201 - Foundation of mathematics
Unit
Basic concepts of Set theory - Laws of Set theory -I
- Partition of set, Relations - Types of Relations:
Set -Theory
Equivalence relation, Partial ordering relation Graphs of relation - Hasse diagram, Functions:
Injective, Surjective, Bijective functions, Compositions of functions, Identity and Inverse
functions.

Introduction to Set theory, Laws of set theory, Venn diagram, Partition of Sets,
Cartesian of Sets, basic theorems in set.

The concept of a set is used in various disciplines and particularly in computers.

Basic Definition:

1. “A collection of well defined objects is called a set”.

The capitals letters are used to denote sets and small letters are used for denote
objects of the set. Any object in the set is called element or member of the set. If x
is an element of the set X, then we write to be read as ‘x belongs to X’ , and
if x is not an element of X, the we write to be read as ‘ x does not belongs to
X’.

2. The number of elements in the set A is called cardinality of the set A,

denoted by |A| or n(A) . We note that in any set the elements are distinct.
The collection of sets is also a set.

Here itself one set and it is one element of S and |S|=4.

3. Let A and B be any two sets. If every element of A is an element of B, then

A is called a subset of B is denote by .

We can say that A contained (included) in B, (or) B contains (includes) A.

Symbolically, (or)

Logically,

1
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

Let

Then

, since and

Some of the important properties of set inclusion.

For any sets A, B and C

(Reflexive)

(Transitive)

Note that does not imply except for the following case.

4. Two sets A and B are said to be equal if and only if and ,

Example and then

Since and eventhough

The equality of sets is reflexive, symmetric, and transitive.

5. A set A is said to be a proper subset of a set B if and .

Symbolically it is written as

is also called a proper inclusion.

6. A set is said to be universal set if it includes every set under our discussion. A
universal set is denoted by or E.

In other words, if p(x) is a predicate.

One can observe that universal set contains all the sets.

7. A set is said to be empty set or null set if it does not contain any element, which
id denoted by .

2
SATHYABAMA UNIVERSITY,DISCRETE MATHEMATICS & NUMERICAL METHODS, SMT1203, UNIT 2
SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

In other words, if p(x) is a predicate.

One can observe that null set is a subset for all sets.

8. For a set A, the set of all subsets of A is called the power set of A. The power set
of A is denoted by or

Example, Let

Then

Then set and A are called improper subsets of A and the remaining sets are
called proper subsets of A.

One can easily note that the number of elements of is

.

SOME OPERATIONS ON SETS

1. Intersection of sets

Definition:

Let A and B be any two sets, the intersection of A and B is written as is the
set of all elements which belong to both A and B.

Symbolically

Example then . From the

definition of intersection it follows that for any sets A,B,C and universal set E.

2. Disjoint sets

3
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

Definition:

Two set A and B are called disjoint if and only if , that is, A and B have
no element in common.

Example

A and B are disjoint and B and C also, but A and C are not disjoint.

3. Mutually disjoint sets

Definition:

A collection of sets is called a disjoint collection, if for every pair of sets in the
collection, are disjoint. The elements of a disjoint collection are said to be mutually
disjoint.

Let be an indexed set, A is mutually disjoint if and only if

for all

Example

Then is a disjoint collection of sets.

and

4. Unions of sets

Definition:

The union of two sets A and B, written as , is the set of all elements which
are elements of A or the elements of B or both.

Symbolically

Example Let then

From the union, it is clear that, for any sets A, B,C, and universal set E.

4
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

5. Relative complement of a set

Definition:

Let A and B are any two sets. The relative complement of B in A, written is
the set of elements of A which are not elements of B.

Symbolically

Note that .

Example Let

then

It is clear from the definition that, for any set A and B.

6. Complement of a set

Definition:

Let A be any set, and E be universal. The relative complement of A in E is called

absolute complement or complement of A. The complement of A is denoted by
(or )

Symbolically

5
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

Example Let be universal set and

be any set in E.

Then

From the definition, for any sets A

7. Boolean sum of sets

Definition:

Let A and B are any two sets. The symmetric difference or Boolean sum of A and
B is the set A+B defined by

(or)

Example Let

then

From the definition, for any sets A and B.

and

6
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

8. The principle of duality

If we interchange the symbols , , E and and and in a set equation

or expression. We obtain a new equation or expression is said to be dual of the
original on (primal).

“ If T is any theorem expressed in terms of and deducible from the given

basic laws, then the dual of T is also a theorem”.

Note that, the theorem T is proved in m steps, then dual of T also proved in m step.

Example The dual of is given by .

Remark: Dual (Dual T) =T.

Identities on sets

Idempotent laws

Commutative laws

Associative laws

Distributive laws

Absorption laws

De Morgan’s laws

7
SATHYABAMA UNIVERSITY,DISCRETE MATHEMATICS & NUMERICAL METHODS, SMT1203, UNIT 2
SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

PROBLEMS

1. , Find and

Solution:

2. If . Find

Solution:

and

3. Write all proper subsets of .

Solution:

The proper subsets are

8
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

4. Show that

Solution:

If , then

Now , let

and

If then

Let

Therefore

5. If Find and

Solution:

6. If Find
and

Solution:

9
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

Note that

7. Show that and

Solution:

Let

Now let

Hence and

Remark: and

8. Show that for any two sets A and B,

Solution:

10
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

and

Therefore

9. Show that

Solution:

Therefore

10. Show that

Solution:

Let

Therefore

11. Show that

11
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

Solution:

( )

(Associative)

(De Morgan’s law)

12. Show that

Solution:

Let

ASSIGNMENT PROBLEMS

Part –A

1. Define a set
2. Define subset of a set. What is mean by proper subset?

12
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

(i) Find all subset of

(ii) Find all proper subsets of A.
3. Define power set.
4. Define disjoint sets with example?
5. If and . Find

and

6. Which of the following sets are empty?

7.
8.
9.
10.State duality principle in set theory.
11.Define cardinality of a set.
12.If a set A has n elements, then the number of elements of power set of A
is……..
13.Find the intersection of the following sets
(i)
14.Write the dual of
15.Let A, B and C sets, such that and , can we
conclude that B=C.
16.State De Morgan’s Laws.
17.Whether the union of sets is commutative or not?

PART –B

13
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

1. Show that
2. Verify the De Morgan’s laws
(i) , (ii)
3. Show that the intersection of sets is associative.
4. Show that .
5. Show that
6. Let for find (a) (b)
7. Prove that
8. Show that for any two sets A and B,
9. Prove that and .
10. If and , prove that B=C.(cancelation law)
11. Show that .
12. Show that where + is the symmetric difference of sets.
13. Show that and imply .
14. Given that and . Show that .

CARTESIAN PRODUCT OF SETS

The Cartesian product of the sets A and B, is written an is the set of all
ordered pairs in which the first elements are in A and the second elements are in
B.

For example

Let

Now

14
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

It is clear from the definition

and is an ordered triple then

and .

Now ,

Note that is not an ordered triple.

This fact show that

i.e. Cartesian product is not associative.

Now

and

Note that if A has n elements and B has m elements has nm elements.

PROBLEMS

1.If . Find and and

Solution :

15
 SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

2.Show that .

Solution: For any ,

3.Show that .

Solution: For any ,

ASSIGNMENT PROBLEMS

16
SATHYABAMA INSTITUTE OF SCIENCE AND TECHNOLOGY, DISCRETE MATHEMATICS-SMTA1302, UNIT II

Part A

1. Define Cartesian product of sets? Given an example?

2. If find .
3. If and , find , .
4. True or False
I. If , the
II. If , the
5. If

Part B

6. If A,B and C are sets, prove that .

7. Prove that .
8. If and ,and , find
I.
II.
III.
IV.
9. Show that the Cartesian product is not commutative? It is commutative
only for equality of sets?

RELATIONS

Binary relation

Any set of ordered pairs defines a binary relation.

17