Chapter # 02, Basic Structures:

Sets, Functions, Sequences, Sums, and Matrices

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}

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Chapter # 02, Basic Structures:
Sets, Functions, Sequences, Sums, and Matrices

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
How to describe a set by saying what properties its
members have.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Intervals Notation
 Types of Set
Finite Set
A set which contains a definite number of elements is called a finite set.

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

Infinite Set
A set which contains 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 is 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.
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
Proper Subset
Types of Set
The term “proper subset” can be defined as “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 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, set of all
mammals is a subset of U, set of all fishes is a subset of U, 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, empty set is a finite set. The cardinality of empty set or null set is zero.
Example − S={x|x∈N and 7<x<8}=∅
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Types of Set
Singleton Set or Unit Set
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 of two sets are same, they are called equivalent sets.
Example − If A={1,2,6} and B={16,17,22},
they are equivalent as 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.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Another look at Equality of Sets

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 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.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
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)}.

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.
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Using Set Notation with Quantifiers

Truth Sets
and
Quantifiers
Set Operation Venn Diagrams
If sets A and B are represented as regions in the plane, relationships
between A and B can be represented by pictures, called Venn
diagrams, that were introduced by the British mathematician John
Venn in 1881.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Set Operation
Union of Sets: Union of Sets A and B is defined to be the set of all those elements which belong to A or B or
both and is denoted by A∪B.
A∪B = {x: x ∈ A or x ∈ B}
Example: Let A = {1, 2, 3}, B= {3, 4, 5, 6}
A∪B = {1, 2, 3, 4, 5, 6}.

|A ∪ B|=|A|+|B|−|A ∩ B|
Principle of inclusion–exclusion.

Intersection of Sets: Intersection of two sets A and B is the set of all those elements which belong to both A
and B and is denoted by A ∩ B.
A ∩ B = {x: x ∈ A and x ∈ B}
Example: Let A = {11, 12, 13}, B = {13, 14, 15}
A ∩ B = {13}.

Difference of Sets: The difference of two sets A and B is a set of all those elements which belongs to A but do
not belong to B and is denoted by A - B.
A - B = {x: x ∈ A and x ∉ B}
Example: Let A = {1, 2, 3, 4} and B = {3, 4, 5, 6}
then A - B = {3, 4} and B - A = {5, 6}
 Set Operation
Complement of a Set: The Complement of a Set A is a set of all those elements of the
universal set which do not belong to A and is denoted by Ac.

Ac = U - A = {x: x ∈ U and x ∉ A} = {x: x ∉ A}

Example: Let U is the set of all natural numbers.
A = {1, 2, 3}
Ac = {all natural numbers except 1, 2, and 3}.

Symmetric Difference of Sets: The symmetric difference of two sets A and B is the
set containing all the elements that are in A or B but not in both and is denoted by A ⨁ B
i.e.

A ⨁ B = (A ∪ B) - (A ∩ B)
Example: Let A = {a, b, c, d}
B = {a, b, l, m}
A ⨁ B = {c, d, l, m}

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Set Identities Generalized Unions and Intersections

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Methods of identity Proof
1. Prove that each set (side of the identity) is a subset of the other.
2. Use set builder notation and propositional logic.
3. Membership Tables: Verify that elements in the same combination of sets
always either belong or do not belong to the same side of the identity. Use 1 to
indicate it is in the set and a 0 to indicate that it is not.

Proving Set Identities

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Proof of Second De Morgan Law

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Set-Builder Notation: Second De Morgan Law

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Use a membership table to show that A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Generalized Unions and Intersections

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Computer Representation of Sets
There are various ways to represent sets using a computer. One method is to
store the elements of the set in an unordered fashion. However, if this is done,
the operations of computing the union, intersection, or difference of two sets
would be time-consuming, because each of these operations would require a
large amount of searching for elements. We will present a method for storing
elements using an arbitrary ordering of the elements of the universal set. This
method of representing sets makes computing combinations of sets easy.
Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in increasing order; that is,
ai = i. What bit strings represent the subset of all odd integers in U, the subset of all even integers in U, and the
subset of integers not exceeding 5 in U?

The bit string that represents the set of odd integers in U, namely, {1, 3, 5, 7, 9}, has a one bit
in the first, third, fifth, seventh, and ninth positions, and a zero elsewhere.
It is 10 1010 1010.

(We have split this bit string of length ten into blocks of length four for easy reading.)
Similarly, we represent the subset of all even integers in U, namely, {2, 4, 6, 8, 10},
by the string 01 0101 0101.

The set of all integers in U that do not exceed 5, namely, {1, 2, 3, 4, 5}, is represented
by the string 11 1110 0000.
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Functions

Definition: Let A and B be nonempty sets. A function f from A

to B, denoted f: A → B is an assignment of each element of A
to exactly one element of B. We write f(a) = b if b is the unique
element of B assigned by the function f to the element a of A.
Functions are sometimes called mappings or
transformations.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Functions

Relation VS Function
A = {1, 2} and B = {a, b, c}?
The Cartesian product A × B is;
A × B = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}.
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Types of Functions
Injections
Definition: A function f is said to be one-to-one , or
injective, if and only if f(a) = f(b) implies that a = b for
all a and b in the domain of f. A function is said to be
an injection if it is one-to-one.

Surjections
Definition: A function f from A to B is called onto or
surjective, if and only if for every element there is an
element with. A function f is called a surjection if it is onto.

Bijections
Definition: A function f is a one-to-one correspondence, or
a bijection, if it is both one-to-one and onto (surjective
and injective).

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Is the function f (x) = x2 from the set of integers to the set of integers onto?

Solution: The function f is not onto because there is no integer x with x2 = −1, for instance

Is the function f (x) = x + 1 from the set of integers to the set of integers onto?

Solution: This function is onto, because for every integer y there is an integer x such that f (x) = y. To see this,
note that f (x) = y if and only if x + 1 = y, which holds if and only if x = y − 1

Let f be the function from {a, b, c, d} to {1, 2, 3, 4} with f (a) = 4, f (b) = 2, f (c) = 1, and f (d) = 3. Is f a bijection?

Solution: The function f is one-to-one and onto. It is one-to-one because no two values in the domain are
assigned the same function value. It is onto because all four elements of the codomain are images of elements in
the domain. Hence, f is a bijection.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Showing that f is one-to-one or onto

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Showing that f is one-to-one or onto

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
A function is called Real-Valued if its codomain is the set of real numbers, and it is called
integer-valued if its codomain is the set of integers. Two real-valued functions or two integer
valued functions with the same domain can be added, as well as multiplied.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Increasing/ decreasing functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Increasing/ decreasing functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Increasing/ decreasing functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
Inverse Functions and Compositions of Functions
 Inverse Functions and Compositions of Functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Inverse Functions and Compositions of Functions
 Inverse Functions and Compositions of Functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Inverse Functions and Compositions of Functions
Example 0:

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Inverse Functions and Compositions of Functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Inverse Functions and Compositions of Functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 The Graphs of Functions
We can associate a set of pairs in A × B to each function from A to B. This set of pairs is called
the graph of the function and is often displayed pictorially to aid in understanding the
behavior of the function.

Let f be a function from the set A to the set B. The graph of the function f is the set of
ordered pairs {(a, b) | a ∈ A and f (a) = b}.
 The Graphs of Functions
Some Important Functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 The Graphs of Functions
Some Important Functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 The Graphs of Functions
Some Important Functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 The Graphs of Functions
Some Important Functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 More Functions

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Partial Functions

A partial function f from a set A to a set B is an assignment to each

element a in a subset of A, called the domain of definition of f , of a
unique element b in B. The sets A and B are called the domain and
codomain of f , respectively. We say that f is undefined for elements in
A that are not in the domain of definition of f . When the domain of
definition of f equals A, we say that f is a total function.

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 2.4 Sequences and Summations
A sequence is a discrete structure used to represent an ordered list.
For example, 1, 2, 3, 5, 8 is a sequence with five terms and 1, 3, 9, 27,
81 , … , 3n, … is an infinite sequence.

A sequence is a function from a subset of the set of integers (usually

either the set {0, 1, 2, …} or the set {1, 2, 3, …}) to a set S. We use the
notation a to denote the image of the integer n.
We call a a term of the sequence.
A sequence is just a list of elements usually written in a row.
Sequence VS Series

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Arithmetic Progression OR Sequences

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Arithmetic Progression

EXAMPLE 4 The string abcd is a string of length four

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Arithmetic Progression
 Arithmetic Progression

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Geometric Progression

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Geometric Progression GENERAL TERM OF A GEOMETRIC SEQUENCE:
 Geometric Progression

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Geometric Progression

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Geometric Progression

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Useful Sequences

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Series

SUMMATIONS
 ARITHMETIC SERIES:

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
ARITHMETIC SERIES:
 ARITHMETIC SERIES:

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 GEOMETRIC SERIES:

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Recurrence Relations
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 Fibonacci Sequence

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Iterative Solution Example

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 Iterative Solution Example

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
Some Useful Summation Formulae

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 2.5 Cardinality of Sets
The sets A and B have the same cardinality if and only if there is a
one-to-one correspondence from A to B. When A and B have the
same cardinality, we write |A| = |B|. For infinite sets the definition of
cardinality provides a relative measure of the sizes of two sets, rather
than a measure of the size of one particular set. We can also define
what it means for one set to have a smaller cardinality than another
set.
OR
If there is a one-to-one function from A to B, the cardinality of A is
less than or the same as the cardinality of B and we write |A| ≤ |B|.
Moreover, when |A| ≤ |B| and A and B have different cardinality

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 2.5.2 Countable Sets

A One-to-One Correspondence Between

Z+ and the Set of Odd Positive Integers.
FREE: For Complete Playlist: [Link]
For Code, Slide and Books: [Link]
 HILBERT’S GRAND HOTEL
We now describe a paradox that shows that something impossible with
finite sets may be possible with infinite sets. The famous mathematician
David Hilbert invented the notion of the Grand Hotel, which has a
countably infinite number of rooms, each Links occupied by a guest.
When a new guest arrives at a hotel with a finite number of rooms, and
all rooms are occupied, this guest cannot be accommodated without
evicting a current guest. However, we can always accommodate a new
guest at the Grand Hotel, even when all rooms are already occupied, we
can accommodate a finite number of new guests and a countable
number of new guests, respectively, at the fully occupied Grand Hotel.
EXAMPLES OF COUNTABLE AND UNCOUNTABLE SETS

FREE: For Complete Playlist: [Link]

For Code, Slide and Books: [Link]
 EXAMPLES OF COUNTABLE AND UNCOUNTABLE SETS
Show that the set of positive rational numbers is countable.

It may seem surprising that the set of positive rational numbers is countable, but
we will show how we can list the positive rational numbers as a sequence r1, r2,
… , rn, … . First, note that every positive rational number is the quotient p∕q of
two positive integers. We can arrange the positive rational numbers by listing
those with denominator q = 1 in the first row, those with denominator q = 2 in
the second row, and so on, as displayed
 2.5.3 An Uncountable Set
We have seen that the set of positive rational numbers is a countable set. Do we
have a promising candidate for an uncountable set? The first place we might look is
the set of real numbers. In Example 5 we use an important proof method,
introduced in 1879 by Georg Cantor and known Links as the Cantor diagonalization
argument, to prove that the set of real numbers is not countable. This proof method
is used extensively in mathematical logic and in the theory of computation.
2.5.3 An Uncountable Set
 UNCOMPUTABLE FUNCTIONS
UNCOMPUTABLE FUNCTIONS We will now describe an important
application of the concepts of this section to computer science. In
particular, we will show that there are functions whose values
cannot be computed by any computer program. We say that a
function is computable if there is a computer program in some
programming language that finds the values of this function. If a
function is not computable we say it is uncomputable.
 Matrices
A matrix is a rectangular array of numbers. A matrix with m rows and n
columns is called an m × n matrix. The plural of matrix is matrices. A matrix
with the same number of rows as columns is called square. Two matrices
are equal if they have the same number of rows and the same number of
columns and the corresponding entries in every position are equal.

Rest of all lecture taken from direct BOOK.