Discrete Mathematics - Set Theory, Relations, Functions, and Logic

SCHOOL OF SCIENCE, COMPUTER SCIENCE,
INFORMATION TECHNOLOGY AND HUMANITIES
DEPARTMENT OF MATHEMATICS
SMT5201 – DISCRETE MATHEMATICS




UNIT – I – Set Theory – SMT5201

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




UNITCourse Material
II SET THEORY

SMT5201 - Discrete of mathematics Unit - I
Set Theory
Basic concepts of Set theory - Laws of Set theory - Partition of set, Relations - Types of Relations:
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