Summary Discrete mathematics (210241)

󾠮
Set Theory and Logic
Chapter 1:

Set:-
A set is a collection of well defined objects

Subsets
A set A is said to be a subset of set B if every element of A is also an element of B
If A is a subset of B i.e
B is called the superset of A

Proper Subset
A proper subset of a set A is a subset of A that is not equal to A
In other words, if B is a proper subset of A, then all elements of B are in A but A contains at
least one element that is not in B. For example, if A={1,3,5} then B={1,5} is a proper subset
of A.

Improper Subset
An improper subset is a subset containing every element of the original set
. A proper subset contains some but not all of the elements of the original set. For example,
consider a set {1,2,3,4,5,6}. Then {1,2,4} and {1} are the proper subset while {1,2,3,4,5} is
an improper subset.

Equal Sets
Two sets A and B can be equal only if each element of set A is also the element of the
set B

Types of sets

Universal Set

It is a collection of all elements in a particular context or application. All the sets in that
context or application are essentially subsets of this universal set. Universal sets are


Set Theory and Logic 1

, represented as U.

Singleton Set or Unit Set

Singleton set or unit set contains only one element. A singleton set is denoted by { s }.

Finite Set

A set which contains a definite number of elements is called a finite set.

Infinite Set

A set which contains infinite number of elements is called an infinite set.

Power Set

In set theory, the power set (or power set) of a Set A is defined as the set of all subsets of the
Set A including the Set itself and the null or empty set. It is denoted by P(A). Basically, this
set is the combination of all subsets including null set, of a given set.

Power set of power set of A

In set theory, the power set (or power set) of a Set A is defined as the set of all subsets of the
Set A including the Set itself and the null or empty set. It is denoted by P(A). Basically, this
set is the combination of all subsets including null set, of a given set.

Element and Subset difference

The difference between element and Subset are very evident

eg.
A = {a, b, c}

Here a is not a subset of the set but {a} is a subset, in the same manner {a} is not an element
of the set but only a subset.

Venn Diagram

1. Universal Set is represented using U and by a large rectangle

2. Subsets of U are represented by circles or some closed curve

3. If A and B are disjoint sets then the circles do not have common area and vice versa

Operations on Sets

Union of two sets:-



Set Theory and Logic 2

, The union of two sets X and Y is equal to the set of elements that are present in set X, in set
Y, or in both the sets X and Y. This operation can be represented as;
X ∪ Y = {a: a ∈ X or a ∈
Y}

Intersection of sets:-

The intersection of sets A and B is the set of all elements which are common to both A and
B.

A ∩ B = {x : x ∈ A and x ∈ B}
Disjoint sets:-

Two sets are said to be disjoint if A ∩ B = ϕ

Complement of a Set

In set theory, the complement of a set A, often denoted by Ac (or A′), are the elements not in
A.

A’ = {x : x ∈ U and x ∉ A}
Properties of Complement of Sets:-

1. A ∪ A’ = U ( Complement Laws)
2. A ∩ A’ = ∅ ( Complement Laws)

3. (A’)’ = A ( Law of Double Complementation)

4. ∅’ = U And U’ = ∅ (Law of empty set and universal set)

5. A ∪ U = U

6. A ∩ U = A

Difference of Sets:-

Difference of two sets A and B is the set of elements which are present in A but not in B. It
is denoted as A-B. In the following diagram, the region shaded in orange represents the
difference of sets A and B. And the region shaded in violet represents the difference of B
and A.

Let A = {3 , 4 , 8 , 9 , 11 , 12 } and B = {1 , 2 , 3 , 4 , 5 }. Find A – B and B – A.
Solution: We can say that A – B = { 8, 9, 11, 12} as these elements belong to A but not to B
B – A ={1,2,5} as these elements belong to B but not to A.




Set Theory and Logic 3