Discrete Structures

(CS-110)
Instructor
Engr. Iqra Jabeen
[Link]@[Link]

Cyber Security Engineering Technology

Department of Telecommunication Engineering
Introduction to Set Theory
Definition: A set is an unordered collection of distinct objects, called elements or members of the
set. A set is said to contain its elements. We write a ∈ A to denote that a is an element of the set A.
The notation a ∉ A denotes that a is not an element of the set A.
▪ The set V of all vowels in the English alphabet can be written as V = {a, e, i, o, u}
▪ The set O of odd positive integers less than 10 can be expressed by O = {1, 3, 5, 7, 9}.
▪ The set of positive integers less than 100 can be denoted by {1, 2, 3, … , 99}
Introduction to Set Theory
Why to study the sets?
▪ Data Structures should be thought of as the implementation of sets, with a particular focus on
efficient implementation of set operations.
▪ In Database theory, the notation of a relational database is that of seeing a database as a relation
over a set.
▪ In formal language theory, the language is the set of strings, and the study of operations on
languages is central.
▪ Some of these are the usual set operations of intersections, union, and complement.

▪ In programming language semantics, semantic domains are set with structures.

Set Theory

Set: A Collection of ordered and unordered objects (elements)

a∈ 𝑨 “a is an element of A”
“a is a member of A”

A={𝑎1 , 𝑎2 …….. 𝑎𝑛 } “A contains 𝑎1 , 𝑎2 …….. 𝑎𝑛 ”

▪ Order of elements is insignificant

▪ It does not matter how often the same element is listed (repetition does not count)
▪ It is common for sets to be denoted using upper-case letters.
▪ Lowercase letters are usually used to denote the elements of set.
Methods to Represent Set
There are three ways to represent a set
1. Descriptive form (English form)
2. Set builder form
3. Roster form
Roster form
▪ Use a notation where all members of the set are listed between braces.
▪ For example, a set of vowels V ={a,e,i,o,u}
▪ Although sets are usually used to group together elements with common properties, there is nothing that
prevents a set from having seemingly unrelated elements.
▪ For instance,{a,2,fred, New Jersey} is the set containing four elements.
Set Builder Notation
▪ Characterize all those elements in the set by stating the property or properties they must have to be
members.
▪ The set O of all odd positive integers less than 10 can be written as
O={x|x is an odd positive integer less than 10}
O={1,3,5,7,9}→ Roster form
Methods to Represent Set

Set of Natural Numbers N={0,1,2,3….}

Set of integers Z={…-2,-1,0,1,2,3…}
Set of positive integers Z={1,2,3,4…}
Set of Real Numbers R={47.3,-12…}
Set of Rational Numbers Q={1.5,2.6,-3.8,15…..}
Interval Notation
Types of Set
Finite Set/Countable elements
A set that contains a definite number of elements is called a finite set.

Example : S={ x | x∈N and 70>x>50}

Infinite Set/uncountable elements

A set that contains an infinite number of elements is called an infinite set.
Example : S={ x | x∈N and x>10}
Subset
A set X is a subset of set Y (Written as X⊆Y) if every element of X is an element of set Y.
Example 1 : Let X={1,2,3,4,5,6} and Y={1,2}.
Here, set Y is a subset of set X, as all the elements of set Y are in set X. Hence, we can write Y⊆X.
Example 2 : Let X={1,2,3} and Y={1,2,3}.
Here, set Y is a subset (Not a proper subset) of set X, as all the elements of set Y is in set X. Hence, we can
write Y⊆X.
Types of Set
Proper Subset
The term “proper subset” can be defined as “a subset of but not equal to”.
A Set X is a proper subset of set Y (Written as X⊂Y) if every element of X
is an element of set Y and |X|<|Y|.
Example : Let, X={1,2,3,4,5,6} and Y={1,2}. Here, set Y⊂X since all elements in Y are contained in X too,
and X has at least one element that is more than set Y.

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 represented as U.
Example: We may define U as the set of all animals on Earth. In this case, the set of all mammals is a
subset of U, the set of all fishes is a subset of U, the set of all insects is a subset of U, and so on.

Empty Set or Null Set

An empty set contains no elements. It is denoted by ∅. As the number of elements in an empty set is finite, the
empty set is a finite set. The cardinality of the empty set or null set is zero.
Example : S={x|x∈N and 7<x<8}=∅
Types of Set
Singleton Set or Unit Set
A singleton set or unit set contains only one element.
A singleton set is denoted by {S}.
Example: S={x|x∈N, 7<x<9} = {8}

Equivalent Set
If the cardinalities (object count) of two sets are the same, they are called equivalent sets.
Example: If A={1,2,6} and B={16,17,22},
they are equivalent as the cardinality of A is equal to the cardinality of B. i.e. |A|=|B|=3

Equal Set
If two sets contain the same elements, they are said to be equal.
Example : If A={1,2,6} and B={6,1,2}, they are equal as every element of set A is an element of set B
and every element of set B is an element of set A.
Types of Set
Set Equality
Set A and B are equal if and only if they contain exactly the same elements.
A ={dog, cat, horse}
B={cat, horse, rabbit, dog}
𝑨≠𝑩 Another look at Set Equality
A ={9,2,7,-3}
B={7,9,-3,2}

𝑨=𝑩
A ={dog, cat, horse}
B={cat, horse, dog, dog}
𝑨=𝑩
Types of Set
Overlapping Set
Two sets that have at least one common element are called overlapping sets.
Example: Let, A={1,2,6} and B={6,12,42}.
There is a common element ‘6’, hence these sets are overlapping sets.

Disjoint Set
Two sets A and B are called disjoint sets if they do not have even one element in common. Therefore,
disjoint sets have the following properties −
n(A∩B)=∅
n(A∪B)=n(A)+n(B)
Example :Let, A={1,2,6} and B={7,9,14}, there is not a single common element, hence these sets are
disjoint sets.
Types of Set
Power Set
What is the power set of the set {0, 1, 2}?

Solution: The power set ({0, 1, 2}) is the set of all subsets of {0, 1, 2}.
Hence, Examples ({0, 1, 2}) = {∅, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}.
Note that the empty set and the set itself are members of this set of subsets.
Cartesian product of A = {1, 2} and B = {a, b, c}?
Solution: The Cartesian product A × B is;
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.
Tuple
The cardinality of a finite set A, denoted by |A|, is the number of (distinct) elements of A.
Examples: 1. |ø| = 0
2. Let S be the letters of the English alphabet. Then |S| = 26
3. |{1,2,3}| = 3
4. |{ø}| = 1
5. The set of integers is infinite.
Examples of Set
Example#1: List the members of the following sets,
a. A={𝒙|𝒙 𝒊𝒔 𝒕𝒉𝒆 𝒓𝒆𝒂𝒍 𝒏𝒖𝒎𝒃𝒆𝒓𝒔 𝒔𝒖𝒄𝒉 𝒕𝒉𝒂𝒕 𝒙𝟐 =1}
b. B={𝒙|𝒙 𝒊𝒔 𝒂 𝒑𝒐𝒔𝒊𝒕𝒊𝒗𝒆 𝒊𝒏𝒕𝒆𝒈𝒆𝒓 𝒍𝒆𝒔𝒔 𝒕𝒉𝒂𝒏 𝟏𝟐}
c. 𝑪 = {𝒙|𝒙 𝒊𝒔 𝒕𝒉𝒆 𝒔𝒒𝒖𝒂𝒓𝒆 𝒐𝒇 𝒂𝒏 𝒊𝒏𝒕𝒆𝒈𝒆𝒓 𝒂𝒏𝒅 𝒙 < 𝟏𝟎𝟎}
d. D={𝒙|𝒙 𝒊𝒔 𝒕𝒉𝒆 𝒓𝒆𝒂𝒍 𝒏𝒖𝒎𝒃𝒆𝒓𝒔 𝒔𝒖𝒄𝒉 𝒕𝒉𝒂𝒕 𝒙𝟐 =2}
Solution
a. A={1,-1}
b. B={1,2,3,4,5,6,7,8,9,10,11}
c. C={1,4,9,16,25,36,49,64,81}
d. D=∅{ 𝟐 is not an integer}
Example#2: Use set builder notation to give description of each of these sets
a. {𝟎, 𝟑, 𝟔, 𝟗, 𝟏𝟐}
b. {-3,-2,-1,0,1,2,3}
c. {m,n,o,p}
Solution
a. {𝒙 ∈ 𝑵| 𝒙 𝒊𝒔 𝒕𝒉𝒆 𝒎𝒖𝒍𝒕𝒊𝒑𝒍𝒆 𝒐𝒇 𝟑 𝒂𝒏𝒅 𝒙 ≤ 𝟏𝟐}
b. {𝒙 ∈ 𝒁| − 𝟑 ≤ 𝒙 ≤ 3}
c. {x|x is the letter in the alphabet from m to p}
Examples of Set
Example#3: For each of these pairs of sets, determine whether the first is a subset of the second, the second is
a subset of the first, or neither is a subset of the other.
a) The set of airline flights from New York to New Delhi, the set of non-stop airline flights from New York to New
Delhi.
b) The set of people who speak English, the set of people who speak Chinese.
c) The set of flying squirrels, the set of living creatures that can fly.
Solution
a) Second is the subset of the first → A={N,city a,city b,D} B={N,D}
b) Neither is the subset of others
c) The first is the subset of others.
Example#4: Determine whether each of these pairs of sets is equal
a) {1,3,3,3,5,5,5,5,5},{5,3,1}
b) {{1}},{1,{1}}
c) ∅, {∅}
Solution
a) Yes, order and repetition do not matter.
b) No, the first set has one element, and the second set has two elements.
c) No, the first set has no elements, and second set has one element.
Examples of Set
Example#5: Suppose that A={2,4,6},B={2,6},C={4,6} and D{4,6,8}.Determine which of these sets are subsets of
which other of these sets.
Solution
a. B is a subset of A
b. C is a subset of both A and D