Sets

A set is an unordered collection of distinct objects, called elements or members of the

We write a ∈ A to denote that a is an element of the set A.

set.

The notation a ∉ A denotes that a is not an element of the set A.

There are two ways to describe a set.

1. One way is to list all the members of a set, when this is possible. We use a
notation where all members of the set are listed between braces. For example,
the notation {a, b, c, d} represents the set with the four elements a, b, c, and d.
This way of describing a set is known as the roster method.

2. Another way to describe a set is to use set builder notation. We characterize all

be members. The general form of this notation is {x ∣ x has property P} and is

those elements in the set by stating the property or properties they must have to

read “the set of all x such that x has property P.” For instance, the set O of all odd

 = {x ∣ x is an odd positive integer less than 10}

positive integers less than 10 can be written as

Write the following sets using the roster method and set builder method:

(a) The set of natural numbers less than 50

Sol: Roster method A={1,2,3,…,49} This is still the roster method, but in a concise

Set builder method A= {x ∈N ∣x<50}

form that shows the pattern clearly without listing all 49 numbers.

(b) The set of even numbers between 1 and 15

A={x ∈N ∣x is even and x ≤ 14}

Sol. A= {2,4,6,8,10,12,14}

(c) The set of letters in the word “BANANA”

X= {x ∣x is a letter in the word “BANANA”}

Sol. X = {B,A,N}

(d) The set of square numbers less than 50

X= {x ∈ n2 |n ∈N, and n<=7}

Sol: X={1,4,9,16,25,36,49}

Some important Set

These sets, each denoted using a boldface letter, play an important role in discrete
mathematics:
N = {1, 2, 3,…}, the set of all natural numbers
Z = {…,−2,−1, 0, 1, 2,…}, the set of all integers

Q = {p∕q ∣ p ∈ Z, q ∈ Z, and q ≠ 0}, the set of all rational numbers

Z+ = {1, 2, 3,…}, the set of all positive integers

set,or null set, and is denoted by ∅. The empty set can also be denoted by{ }
EMPTY SET There is a special set that has no elements. This set is called the empty

confuse the empty set ∅ with the set {∅}, which is a singleton set.
Singleton set A set with one element is called a singleton set. A common error is to

element of A is also an element of B. We use the notation A ⊆ B to indicate that A is a

Subsets : The set A is a subset of B, and B is a superset of A, if and only if every

subset of the set B.

Note: For every set S, (i ) ∅ ⊆ S and (ii ) S ⊆ S.

⊂ B and say that A is a proper subset of B.

When we wish to emphasize that a set A is a subset of a set B but that A ≠ B, we write A

Q. Find all subset and proper subset of set {a,b}

1.∅ (the empty set)

Sol. The set { a, b} has the following subsets:
2.{a} 3.{b} 4.{a, b}

1.∅ (the empty set)

Q. The set { a, b} has the following proper subsets:
2.{a} 3.{b}

Cardinality: Let S be a set. If there are exactly n distinct elements in S where n is a

nonnegative integer, we say that S is a finite set and that n is the cardinality of S. The
cardinality of S is denoted by |S|.
Example : Let A be the set of odd positive integers less than 10. Then |A| = 5.

Q. Find Cardinality of S={∅,{∅}}

1. The empty set ∅

Sol. So, the set S has two distinct elements:

2. A set containing the empty set {∅}

Cardinality of {∅,{∅}}= 2

Q. Find Cardinality of S={a,a,b}

Sol. So, the set S has two distinct elements: a and b
So Cardinality of S= 2

Power Sets Given a set S, the power set of S is the set of all subsets of the set S. The
power set of S is denoted by P(S).

Question: What is the power set of the set {0, 1, 2}?

Solution: The power set P({0, 1, 2}) is the set of all subsets of {0, 1, 2}. Hence, P({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.

Q. Find power Set of S={∅,{∅}}

Sol. P(S)={∅, {∅}, {{∅}}, {∅,{∅}}}

Cartesian Products

ordered pairs (a, b), where a ∈ A and b ∈ B. Hence,

Let A and B be sets. The Cartesian product of A and B, denoted by A × B, is the set of all

A × B = {(a, b) ∣ a ∈ A ∧ b ∈ B}.

Question: What is the 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)}.

Question: What is the Cartesian product A × B × C, where A = {0, 1}, B = {1, 2},
and C = {0, 1, 2}?

∈ A,
Solution: The Cartesian product A × B × C consists of all ordered triples (a, b, c), where a

b ∈ B, and c ∈ C. Hence,
A × B × C = {(0, 1, 0), (0, 1, 1), (0, 1, 2), (0, 2, 0), (0, 2, 1), (0, 2, 2),
(1, 1, 0), (1, 1, 1), (1, 1, 2), (1, 2, 0), (1, 2, 1), (1, 2, 2)}. ◂

Set Operations
Set operations can be defined as the operations that are performed on two or more sets
to obtain a single set containing a combination of elements from both the sets being
operated upon.

Union Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is the set
that contains those elements that are either in A or in B, or in both.
An element x belongs to the union of the sets A and B if and only if x belongs to A or x
belongs

A ∪ B = {x ∣ x ∈ A ∨ x ∈ B}.
to B. This tells us that

{1, 3, 5} ∪ {1, 2, 3} = {1, 2, 3, 5}.

The union of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 2, 3, 5}; that is,

Intersection Let A and B be sets. The intersection of the sets A and B, denoted by A ∩

A ∩ B = {x ∣ x ∈ A ∧ x ∈ B}.
B, is the set containing those elements in both A and B.

The intersection of the sets {1, 3, 5} and {1, 2, 3} is the set {1, 3}; that is,
{1, 3, 5} ∩ {1, 2, 3} = {1, 3}.

Let A = {1, 3, 5, 7, 9} and B = {2, 4, 6, 8, 10}. Because A ∩ B = ∅, A and B are disjoint.

Two sets are called disjoint if their intersection is the empty set.

Difference Let A and B be sets. The difference of A and B, denoted by A − B, is the set
containing those elements that are in A but not in B. The difference of A and B is also

An element x belongs to the difference of A and B if and only if x ∈ A and x ∉ B. This tells
called the complement of B with respect to A.

A − B = {x ∣ x ∈ A ∧ x ∉ B}.
us that

A - B = {0,1}
Example: A={0,1,2} and B={2,3,4} set are given. Find A-B and B-A

B – A = {3,4}

Complement Let U be the universal set. The complement of the set A, denoted by Ac, is
the complement of A with respect to U. Therefore, the complement of the set A is U − A.
Remark: The definition of the complement of A depends on a particular universal set U.
This definition makes sense for any superset U of A. If we want to identify the universal

An element belongs to Ac if and only if x ∉ A. This tells us that

set U, we would write “the complement of A with respect to the set U.”

Ac = {x ∈ U ∣ x ∉ A}.
Example :Let A = {a, e, i, o, u} (where the universal set is the set of letters of the English
alphabet). Then Ac = {b, c, d, f, g, h, j, k, l, m, n, p, q, r, s, t, v, w, x, y, z}.

The symmetric difference between two sets A and B, which is denoted by A ⊕ B, is the
symmetric difference

A ⊕ B = (A ∪ B) - (A ∩ B)
set of elements that are in either of the sets but not in their intersection.

A ⊕ B = (A - B) ∪ (B - A)

A ⊕ B = {0,1,3,4}
Example: The symmetric difference of A={0,1,2} and B={2,3,4} is

Set Identies
Let U be the universal set, A,B and C are subsets of the universal set U.

A∩B=B∩A ; A∪B=B∪A
1. Commutative Laws.
 (A ∪ B) ∪ C = A ∪ (B ∪ C) ; (A ∩ B) ∩ C = A ∩ (B ∩ C)
2. Associative Laws.

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
3. Distributive Laws

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

A ∪ ∅ = A; A ∩ U = A
4. Identity Laws

A ∪ A' = U ; A ∩ A' = ∅
5. Complement Laws

6. Double Complement Laws

(A')' = A

A∪A=A; A∩A=A
7. idempotent laws

A ∪ U = U; A ∩ ∅ = ∅
8. Universal Bound Law

(A ∪ B)' = A' ∩ B' ; (A ∩ B)' = A' ∪ B'

9. De-Morgan’s Laws

A ∪ (A ∩ B) = A ; A ∩ (A ∪ B) = A
10. Absorption Laws.

∅’ = U And U’ = ∅
11. complement law

12. Set Difference Laws

A – B = A ∩ B'

How to prove: A = B

1. Prove A ⊆ B: Assume an arbitrary element 'x' is in set A (x ∈ A). Then, using logical
reasoning and set theory definitions and laws, show that 'x' must also be in set B (x ∈ B).

2. Prove B ⊆ A: Assume an arbitrary element 'y' is in set B (y ∈ B). Then, using logical
reasoning and set theory definitions and laws, show that 'y' must also be in set A (y ∈ A).

3. Conclusion: If both subset relationships are proven, then you can conclude that A = B.
Example:
Q. prove that if A and B are sets, and A ⊆ B, then A ∪ (B - A) = B.

Part a. Prove A ∪ (B - A) ⊆ B:
Sol.

Assume x ∈ A ∪ (B - A).
This means x ∈ A or x ∈ (B - A).
If x ∈ A, since A ⊆ B, then x ∈ B.
If x ∈ (B - A), then x ∈ B and x ∉ A.
In either case, x ∈ B.
Therefore, A ∪ (B - A) ⊆ B.
Part b. Prove B ⊆ A ∪ (B - A):
Assume x ∈ B.
If x ∈ A, then x ∈ A ∪ (B - A).
If x ∉ A, then x ∈ (B - A), which means x ∈ A ∪ (B - A).
Therefore, B ⊆ A ∪ (B - A).
Conclusion: Since A ∪ (B - A) ⊆ B and B ⊆ A ∪ (B - A), then A ∪ (B - A) = B

Q. Prove that A×(𝐵∩𝐶)=(𝐴×𝐵)∩(𝐴×𝐶)

Sol.
Part a. Prove A×(𝐵∩𝐶) ⊆ (𝐴×𝐵)∩(𝐴×𝐶)

This means x ∈ A and y ∈ (B ∩ C).

Let (x,y)∈A×(B∩C)

⇒x ∈ A and (y ∈ B and y ∈ C).

⇒( x ∈ A and y ∈ B) and (x ∈ A and y ∈ C) (Distributive Law)
⇒ (x,y)∈A×B and (x,y)∈A×C
⇒(x,y)∈ (𝐴×𝐵)∩(𝐴×𝐶)
Part b. Prove (𝐴×𝐵)∩(𝐴×𝐶) ⊆ A×(𝐵∩𝐶)

⇒(x,y)∈ ∈ 𝐴×𝐵 and (x,y)∈ ∈ 𝐴×𝐶)

Let (x,y)∈ (𝐴×𝐵)∩(𝐴×𝐶)

⇒(x ∈ A and y ∈ B )and (x ∈ A and y ∈ C)

⇒x ∈ A and and (y ∈ B and y ∈ C)
⇒x ∈ A and and (y ∈ B ∩ C) (Distributive Law)
⇒ (x,y)∈A× (B ∩ C)
Conclusion: Since ⇒(x,y)∈ (𝐴×𝐵)∩(𝐴×𝐶)
and (x,y)∈A× (B ∩ C), then A×(𝐵∩𝐶)=(𝐴×𝐵)∩(𝐴×𝐶)

Principle of Inclusion and Exclusion - is a combinatorial method used to calculate

the cardinality (size) of the union of multiple sets.
Formula for Two Sets

|AUB∣ = ∣A∣+∣B∣-∣A∩B∣
For two sets A and B

 ∣A∣ is the number of elements in set 𝐴.

Where,

 ∣B∣ is the number of element sin set B.

 ∣A∩B∣ is the number of elements in both set A and B.

Q. In a room of 50 people whose dresses have either red or white color, 30 are wearing
red dress, 16 are wearing a combination of red and white. How many are wearing
dresses that have only white color?
Sol: Total people: |RUW∣ = 50
Red dresses: |R∣ =30

| RUW ∣ = ∣R∣+∣W∣-∣R∩W∣
Red and white dresses: |R∩W∣ = 16

50=30 + |W| -16

white dresses =|W| = 50-30+16 = 36
Only red dresses: =|R∣ -|R∩W∣ =30 - 16 = 14
Only white dresses: =|W∣ -|R∩W∣ = 36-16 =20

Q. In a survey of 60 people, it was found that 25 eat Apple, 26 eat Orange | 10 and 26 eat Banana
fruit. Also 9 eat both Apple and Banana, 11 eat both Orange and Apple, and 8 eat both Orange and
Banana. 8 eat no fruit at all. Then determine
1. the number of people who eat all three fruit.
2. the number of people who eat exactly two fruit.
3. the number of people who eat exactly one fruit
Sol.

We are given:

 Total people surveyed: 60

 Eat Apple (A): 25
 Eat Orange (O): 26
 Eat Banana (B): 26
 Eat both Apple and Banana: A ∩ B = 9
 Eat both Orange and Apple: O ∩ A = 11
 Eat both Orange and Banana: O ∩ B = 8
 Eat no fruit at all: 8
 Let the number of people who eat all three fruits be x.

Part 1: People who eat at least one fruit=60−8=52

Number of people who eat at least one fruit=A+O+B−(A∩O+A∩B+O∩B)+(A∩O∩B)

52 = 49 + x ⇒x=3 ,Number of people who eat all three fruits = 3

52 = 25+26+26−(11+9+8)+x

Part 2:
 Exactly Apple and Banana = A∩B−x=9−3=6
 Exactly Apple and Orange = A∩O−x=11−3=8
 Exactly Orange and Banana = O∩B−x=8−3=5
number of people who eat exactly two fruits = 6 + 8 +5 =19

Part 3:
Exactly One=Total eating at least one−(Exactly Two+All Three)=52−(19+3)=30

Formula for three sets:

For three sets A,B,C the Principle of Inclusion and Exclusion formula to find the size of

∣AUBUC∣ = ∣A∣+∣B∣+∣C∣-∣A∩B∣-∣A∩C∣-∣B∩C∣+∣A∩B∩C∣
the union is:

Q. In a class of 100 students: 70 students play football. 60 students play basketball. 50

students play cricket. 30 students play both football and basketball. 25 students play
both basketball and cricket. 20 students play both football and cricket. 15 students play
all three sports. How many students play at least one of these three sports?
Sol.
Sol.

We are given:

 Total students: 100

 F=70: students who play football
 B=60: students who play basketball
 C=50: students who play cricket
 F∩B= 30: students who play both football and basketball
 B∩C=25: students who play both basketball and cricket
 F∩C=20: students who play both football and cricket
 F∩B∩C=15: students who play all three sports

which is: =∣F∪B∪C∣

 We have to find the number of students who play at least one of the three sports,

Using the inclusion-exclusion principle:

∣F∪B∪C∣=∣F∣+∣B∣+∣C∣−∣F∩B∣−∣B∩C∣−∣F∩C∣+∣F∩B∩C∣

Substitute the given values:

 ∣F∪B∪C∣=70+60+50−30−25−20+15
=180−75+15=120

Answer: 120 students play at least one of the three sports.

Relations
Let A and B be sets. A binary relation from A to B is a subset of A × B.
In other words, a binary relation from A to B is a set R of ordered pairs, where the first

use the notation aRb to denote that (a, b) ∈ R and a R b to denote that (a, b) ∉ R.
element of each ordered pair comes from A and the second element comes from B. We

Moreover, when (a, b) belongs to R, a is said to be related to b by R.

Relations on a Set -A relation on a set A is a relation from A to A. In other words, a

relation on a set A is a subset of A × A.
Let A be the set {1, 2, 3, 4}. Which ordered pairs are in the relation R = {(a, b) ∣ a
divides b}?
Solution: Because (a, b) is in R if and only if a and b are positive integers not exceeding 4
such that a divides b, we see that
R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

 A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A.

Properties of Relations

 A relation R on a set A is called symmetric if (b, a) ∈ R whenever (a, b) ∈ R, for all

a, b ∈ A.
 A relation R on a set A such is called anti-symmetric that for all a, b ∈ A,
If a = b and (a, b) ∈ R then (b, a) ∈ R
If a ≠ b and (a, b) ∈ R then (b, a) ∉ R
(i)

 A relation R on a set A is called transitive if whenever (a, b) ∈ R and (b, c) ∈ R,

(ii)

then (a, c) ∈ R, for all a, b, c ∈ A.

Q- Each of these relations on the set {1, 2, 3, 4}, decide whether it is reflexive, whether
it is symmetric, whether it is antisymmetric, and whether it is transitive.
a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)}
b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)}
c) {(2, 4), (4, 2)}
d) {(1, 2), (2, 3), (3, 4)}
e) {(1, 1), (2, 2), (3, 3), (4, 4)}
f ) {(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)}
Solution:
a) Transitive
b) Reflexive, symmetric, transitive
c) Symmetric
d) Antisymmetric
e) Reflexive, symmetric, antisymmetric, transitive
f) None of these properties

Combining Relations
Q-Let A = {1, 2, 3} and B = {1, 2, 3, 4}. The relations R1 = {(1, 1), (2, 2), (3, 3)} and
R2 = {(1, 1), (1, 2), (1, 3), (1, 4)} can be combined to obtain.

R1 ∪ R2 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (3, 3)},
Solution:

R1 ∩ R2 = {(1, 1)},
R1 − R2 = {(2, 2), (3, 3)},
R2 − R1 = {(1, 2), (1, 3), (1, 4)}.

Composition of Relations

composite of R and S is the relation consisting of ordered pairs (a, c), where a ∈ A, c ∈ C,
Let R be a relation from a set A to a set B and S a relation from B to a set C. The

and for which there exists an element b ∈ B such that (a, b) ∈ R and (b, c) ∈ S. We
denote the composite of R and S by S ◦R.

Question: What is the composite of the relations R and S, where R is the relation from
{1, 2, 3} to {1, 2, 3, 4} with R = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)} and S is the relation
from {1, 2, 3, 4} to {0, 1, 2} with S = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}?
Solution: S ◦R is constructed using all ordered pairs in R and ordered pairs in S, where
the second element of the ordered pair in R agrees with the first element of the ordered
pair in S. For example, the ordered pairs (2, 3) in R and (3, 1) in S produce the ordered
pair (2, 1) in S ◦R. Computing all the ordered pairs in the composite, we find
S ◦ R = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)}.

Composing the Parent Relation with Itself

Let R be a relation on the set A. The Powers Rn, n=1,2,3,…,are defined recursively by R1
=R and Rn+1 = Rn ◦R. (for example R3 = R2 ◦ R)

Question: Let R={(1,1),(2,1),(3,2),(4,3)}.Find the powers Rn, n=2,3,4,….

Solution:
Because R2 =R◦R, we find that R2={(1,1),(2,1),(3,1),(4,2)}
R3= R2◦R, R3={(1,1),(2,1),(3,1),(4,1)}.
R4= R3◦R, R4={(1,1),(2,1),(3,1),(4,1)}.
It also follows that Rn = R3 for n = 5, 6, 7,….

Inverse Relation

, is the set of ordered pairs {(b, a) ∣ (a,b) ∈ R}.

Let R be a relation from a set A to a set B. The inverse relation from B to A, denoted by R-
1

Example: Let A = {1, 2, 3} and B = {a, b}.

Let R be a relation from A to B defined as R = {(1, a), (2, b)}.
The inverse relation, R⁻¹, would be {(a, 1), (b, 2)}.

Complementary Relation
The complement of a relation R (often denoted as R' or R ) includes all the pairs from the
universal set (A x B, where the relation is from A to B) that are not present in R.

Example: Let A = {1, 2} and B = {x, y}.

Let R be a relation from A to B defined as R = {(1, x)}.
The universal set A x B would be {(1, x), (1, y), (2, x), (2, y)}.
The complement of R, R', would be {(1, y), (2, x), (2, y)}.

Question: Let R be the relation R ={(a,b) ∣ a divides b} on the set of positive integers.
Find a) R-1 b) Rc

a) {(a,b) ∣ b divides a} .
Solution:

b) {(a,b) ∣ a does not divide b}

Representing Relations Using Matrices

Let A={a1,a2,a3} and B={b1,b2,b3,b4,b5}.Which ordered pairs are in the relation R represented by
the matrix

0 1 00 0
MR = 1 0 1 1 0
1 0 10 1
Solution : R={(a1,b2),(a2,b1),(a2,b3),(a2,b4),(a3,b1),(a3,b3),(a3,b5)}.

Question: Let R be the relation represented by the matrix

0 1 1
MR = 1 1 0
1 0 1
Find the matrix representing a) R−1. b) Rc. c) R2.
Solution:
0 1 1 1 0 0 1 1 1
−1 c 2
MR = 1 1 0 MR = 0 0 1 MR = 1 1 1
1 0 1 0 1 0 1 1 1

Question: Let R1 and R2 be the relation represented by the matrix

 0 1 1 0 1 0
MR1 = 1 1 0 MR2 = 0 1 1

Find the matrix representing a) R1∪ R2. b) R1∩ R2. c) R2◦ R1. d) R1◦ R1 e) R1⊕ R2
1 0 1 1 1 1

Solution:
0 1 0 1 1 1
MR1∪ R2 =1 1 1 MR1◦ R1 = 11 1
1 1 1 0 1 0

0 1 0 0 0 0
MR1∩ R2=0 1 1 MR1⊕ R2 = 10 0
1 0 0 0 1 1

0 1 1
M R2◦ R1 = 1 1 0
1 0 1

Question: Let R be the relation represented by the matrix

0 1 0
MR= 0 0 1
1 1 0
2 3 4
Find the matrices that represent a) R . b) R . c) R .
Solution:
0 0 1 1 1 0 0 1 1
M 1 1 0
2
R = M 3
R = 0 1 1 M 4
R = 1 1 1
0 1 1 1 1 1 1 1 1

Closure of Relations

for each a ∈ A.
1. Reflexive Closure The reflexive closure of a relation R on A is obtained by adding (a, a) to R

b) ∈ R.
2. Symmetric Closure The symmetric closure of R is obtained by adding (b, a) to R for each (a,

each (a, b) ∈ R and (b, c) ∈ R.

3. Transitive Closure The transitive closure of R is obtained by repeatedly adding (a, c) to R for

Q-Let R be the relation on the set {0, 1, 2, 3} containing the ordered pairs(0, 1),(1, 1),(1, 2),(2, 0),
(2, 2),(3, 0). Find the reflexive symmetric closure
Solution:
a) reflexive closure of R We need to add (a, a) in R to make a reflexive closure.
{(0, 0),(0, 1),(1, 1),(1, 2),(2, 0),(2, 2),(3, 0),(3, 3)}
b) symmetric closure of R We need to add (b, a) for each (a, b) in R to make a symmetric
closure.
{(0, 1),(0, 2),(0, 3),(1, 0),(1, 1),(1, 2),(2, 0),(2, 1),(2, 2),(3, 0)}

Q- Find the transitive closures of these relations on {1, 2, 3, 4}.

a) {(1, 2), (2, 1), (2, 3), (3, 4), (4, 1)}
b) {(2, 1), (2, 3), (3, 1), (3, 4), (4, 1), (4, 3)}
Solution:
 Another method to find transitive closure
(Warshall’s Algorithm)

Equivalence Relations - A relation on a set A is called an equivalence relation if it is

reflexive, symmetric, and transitive.
Which of these relations on {0, 1, 2, 3} are equivalence relations? Determine the properties of an
equivalence relation that the others lack.
a) {(0, 0),(1, 1),(2, 2),(3, 3)}
Sol:This is an equivalence relation because it is reflexive, symmetric, and transitive.
b) {(0, 0),(0, 2),(2, 0),(2, 2),(2, 3),(3, 2)(3, 3)}
Sol:This is not an equivalence relation because it is neither reflexive nor transitive. Missing
(1, 1) for reflexive and missing (0, 3) for the path (0, 2),(2, 3) for transitive.
c) {(0, 0),(1, 1),(1, 2),(2, 1),(2, 2),(3, 3)}
Sol. This is an equivalence relation because it is reflexive, symmetric, and transitive.
d) {(0, 0),(1, 1),(1, 3),(2, 2),(2, 3),(3, 1),(3, 2),(3, 3)}
Sol. This is not an equivalence relation because it is not transitive. Missing (1, 2) for the path
(1, 3),(3, 2).

Functions
Let A and B be nonempty sets. A function f from A to B is an assignment of exactly one
element of B to each element of A. We write f (a) = b if b is the unique element of B
assigned by the function f to the element a of A. If f is a function from A to B, we write f :
A → B.
Remark: Functions are sometimes also called mappings or transformations.
If f is a function from A to B, we say that A is the domain of f and B is the codomain of f.
If f (a) = b, we say that b is the image of a and a is a pre-image of b. The range, or
image, of f is the set of all images of elements of A. Also, if f is a function from A to B, we
say that f maps A to B.

Injective (one to one) function: A function f is said to be one-to-one, or an injection, 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 injective if it is one-to-one.
Note that a function f is one-to-one if and only if f (a) ≠ f (b) whenever a ≠ b. This way of
expressing that f is one-to-one is obtained by taking the contrapositive of the implication
in the definition.

Question -Determine whether the function f (x) = x2 from the set of integers to the
set of integers is one to-one.
Solution: The function f (x) = x2 is not one-to-one because, for instance, f (1) = f (−1)
= 1, but 1 ≠ −1.

Question -Determine whether the function f (x) = x + 1 from the set of real
numbers to itself is one-to-one.
Solution: Suppose that x and y are real numbers with f (x) = f (y), so that x + 1 = y
+ 1. This means that x = y. Hence, f (x) = x + 1 is a one-to-one function from R to R.
Surjective (Onto) Function

b ∈ B there is an element a ∈ A with f (a) = b. A function f is called surjective if it is onto.

A function f from A to B is called onto, or a surjection, if and only if for every element

Question -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.

Question -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. (Note that y − 1 is also an integer, and so, is in the domain of f .)

Bijective (one-to-one correspondence )Function

The function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and
onto. We also say that such a function is bijective.

Question: Determine whether each of these functions is a bijection

from R to R.
a) f (x) = −3x + 4 f (x) = −3x2 + 7
b) f (x) = (x + 1)/(x + 2) f (x) = x5 + 1

Solution:
a) For function f(x) = -3x + 4, we check if it is one-to-one. Assume f(a) = f(b): -3a + 4 = -3b +
4. Simplifying gives -3a = -3b, which implies a = b. Thus, f is one-to-one .
Next, we check if f(x) = -3x + 4 is onto. For any y in R, we can solve -3x + 4 = y.
Rearranging gives x = (4 - y)/3, which is in R. Thus, f is onto. Therefore, f is a
bijection.
b) For function f(x) = -3x^2 + 7, we check if it is one-to-one. Assume f(a) = f(b): -
3a^2 + 7 = -3b^2 + 7. Simplifying gives -3a^2 = -3b^2, or a^2 = b^2. This
implies a = b or a = -b, so f is not one-to-one. Since f(x) = -3x^2 + 7 is not one-
to-one, it cannot be onto either. Therefore, f is not a bijection.
c) For function f(x) = (x + 1)/(x + 2), we check if it is one-to-one. Assume f(x₁) = f(x₂)
(x₁ + 1)/( x₁ + 2)= (x₂ + 1)/( x₂ + 2), Simplifying gives x₁x₂ + 2x₁ + x₂ + 2 = x₁x₂ +
x₁ + 2x₂ + 2 indicates x₁ = x₂ Thus, f is one-to-one.
Next, we check if f(x) = (x + 1)/(x + 2), is onto. For any y in R, we can solve (x
+ 1)/(x + 2) = y
Solving for x: x+1 = y(x+2) => x+1 = y.x + 2y => x – y.x = 2y - 1 =>
x(1-y) = 2y-1 => x = (2y-1)/(1-y) . Since y can be any real number
except 1, the value of x is well-defined and real. Thus, for every y in the
codomain, there exists an x in the domain such that f(x) = y, proving the function
is onto. Therefore, f is a bijection.
d) For function f(x) = x5+1, we check if it is one-to-one. Assume f(x₁) = f(x₂):
x15+1= x25+1. Simplifying gives x₁ = x₂. Thus, f is one-to-one.
The function f(x) = x5+1 is an onto function because for every y∈R. Therefore, f is
a bijection.

Quest: Determine whether each of these functions is a bijection from R to R.

a) f (x) = x3
b) f (x) = (x2 + 1) ∕ ( x2 + 2)
Solution:
For function f(x) = x3, we check if it is one-to-one. Assume f(x₁) = f(x₂): x 13=
x23. Taking the cube root of both sides x₁ = x₂. Thus, f is one-to-one.
Next, we check if f(x) = x3, is onto. For any y in R, we can solve x3=
y => x =∛ y Since ∛ y is always a real number for any real y. Thus, for every y in
 the codomain, there exists an x in the domain such that f(x) = y, proving the
function is onto. Therefore, f is a bijection.

For function f(x) = (x2 + 1) ∕ ( x2 + 2).we check if it is one-to-one. Assume f(x₁) = f(x₂)
(x₁2 + 1)/( x₁2 + 2)= (x₂2 + 1)/( x₂2 + 2), Simplifying gives x₁2 x22 + x₂2+ 2x₁2+ 2= x₁2
x22 + x12+ 2x22+ 2 => -x₂2 + x12 = 0 => x12 = x22 => x1=x2 & x1=-x2
Hence f(x) is not one to one function
Note that x2>=0 so x2 +1 >=1 & x2 +2 >=2 Also x2 +1 < x2 +2 so (x2
1
+ 1) ∕ ( x2 + 2)<1. As x → ∞,f(x) → 1 The range of f(x) is [ ,1] Since the range is not
2
all of R ,f(x) is not surjective

Inverse Function :
Let f be a one-to-one correspondence from the set A to the set B. The inverse function of
f is the function that assigns to an element b belonging to B the unique element a in A
such that f (a) = b. The inverse function of f is denoted by f −1. Hence, f −1(b) = a when f
(a) = b. A one-to-one correspondence is called invertible because we can define an
inverse of this function. A function is not invertible if it is not a one-to-one
correspondence, because the inverse of such a function does not exist.

Q1-Let f : Z → Z be such that f (x) = x + 1. Is f invertible, and if it is, what is its inverse?
Solution: The function f has an inverse because it is a one-to-one correspondence
. To reverse the correspondence, suppose that y is the image of x, so
that y = x + 1. Then x = y − 1. This means that y − 1 is the unique element of Z that is
sent to y by f . Consequently, f −1 (y) = y − 1.

Q2-Let f be the function from R to R with f (x) = x2. Is f invertible?

Solution: Because f (−2) = f (2) = 4, f is not one-to-one. Hence, f is not invertible.

Composition of functions

to the set C. The composition of the functions f and g, denoted for all a ∈ A by f
Let g be a function from the set A to the set B and let f be a function from the set B

◦g, is the function from A to C defined by

( f ◦g)(a) = f (g (a)).

Question: Let f and g be the functions from the set of integers to the set of integers
defined by f (x) = 2x + 3 and g(x) = 3x + 2. What is the composition of f and g?
What is the composition of g and f ?
Solution: Both the compositions f ◦g and g◦f are defined. Moreover,
( f ◦g)(x) = f (g(x)) = f (3x + 2) = 2(3x + 2) + 3 = 6x + 7 and
(g◦f )(x) = g( f (x)) = g(2x + 3) = 3(2x + 3) + 2 = 6x + 11.

2
Question: Functions f , g : R → R are defined, respectively, by f (x) = x + 3x + 1,
g (x) = 2x – 3, find (i) f ◦ g (ii) g ◦ f (iii) f ◦ f (iv) g ◦ g
2 2
Solution: f ◦ g = f(g(x)) = f(2x – 3) = (2x – 3) + 3. (2x – 3) + 1 = 4 x - 6 x +1
2
g ◦ f = g(f(x)) = g(x + 3x + 1) = 2 x2 + 6 x -1
2 2 2
f ◦ f = f(f(x)) = f(x + 3x + 1) = (x + 3x + 1)2 + 3 (x + 3x + 1) +1
4 3 2
= x +6x + 14. x + 15x + 5
g ◦ g= g(g(x)) =g(2x – 3) = 2(2x – 3)-3= 4x - 9

2
Question: Functions f , g ,h: R → R are defined, respectively, by f (x) = 3x + 2,
g (x) = 7x – 5 and h (x) = 1/x
 find (i) f ◦ g ◦ h(x) (ii) g ◦ g (x) (iii) g ◦ h (x)
Solution: (f∘g∘h)(x)=f(g(h(x)))
Step 1: h(x)=1/x
Step 2: g(h(x))=g(1/x)=7⋅1/x−5 =7/x-5
147 210
Step 3: f(g(h(x)))=f(7/x−5) =3(7/x−5)2 +2 = 2 − + 77
x x
g ◦ g (x) =g(g(x)) =
Step 1: g(x)=7x−5
Step 2: g(g(x))=g(7x−5)=7(7x−5)−5=49x−35−5=49x−40
g ◦ h (x) = g(h(x))
1
Step 1: h(x)=
x
1 1 7
Step 2: g(h(x))=g( )=7⋅ −5=⋅ −5
x x x

Mathematical Induction

In general, mathematical induction∗ can be used to prove statements that assert that
P(n) is true for all positive integers n, where P(n) is a propositional function. A proof by
mathematical induction has two parts, a basis step, where we show that P(1) is true,
and an inductive step, where we show that for all positive integers k, if P(k) is true,
then P(k + 1) is true.
To complete the inductive step of a proof using the principle of mathematical induction,
we assume that P(k) is true for an arbitrary positive integer k and show that under this
assumption, P(k + 1) must also be true. The assumption that P(k) is true is called the
inductive hypothesis.

P(n) is true for all positive integers n, that is, we have shown that ∀nP(n) is true where
Once we complete both steps in a proof by mathematical induction, we have shown that

∀k(P(k) → P(k + 1)) is true, where again, the domain is the set of positive integers.
the quantification is over the set of positive integers. In the inductive step, we show that
1 ⋅ 2⋅3+2⋅3⋅4+⋯+n(n+1)(n+2) = n(n+1)(n+2)(n+3)∕4.
Question: Prove that for every positive integer n,

Solution:
Step 1: Base Case (n = 1)
LHS:1.2.3=6
RHS: 1(1+1)(1+2)(1+3)∕4 = [Link]/4 = 6

Step 2: Inductive Hypothesis

We first assume the inductive hypothesis that P(k) is true for an arbitrary
positive integer k. That is, the inductive hypothesis P(k) is the statement that
1.2⋅3+2⋅3⋅4+⋯+k(k+1)(k+2) = k(k+1)(k+2)(k+3)∕4. ------- eq (1)
To complete the inductive step, we need to show that if P(k) is true, then P(k + 1), which
is the statement that
1.2⋅3+2⋅3⋅4+⋯+ k(k+1)(k+2)+(k+1)(k+2)(k+3) = (k+1)(k+2)(k+3)(k+4)∕4.
is also true.
LHS = 1.2⋅3+2⋅3⋅4+⋯+ k(k+1)(k+2)+(k+1)(k+2)(k+3)
= k(k+1)(k+2)(k+3)∕4 +(k+1)(k+2)(k+3) (using eq (1))
=(k+1)(k+2)(k+3) [ k/4 +1]
=(k+1)(k+2)(k+3))(k+4)/4
=R.H.S
We have completed the basis step and the inductive step, so by mathematical induction
P(n) is true for every positive integer n.
Q- Use mathematical induction to prove the inequality n < 2n for all positive integers n.

Solution: Let P(n) be the proposition that n < 2n

BASIS STEP: P(1) is true, because 1 < 21 = 2. This completes the basis step.
INDUCTIVE STEP: We first assume the inductive hypothesis that P(k) is true for an
arbitrary
positive integer k. That is, the inductive hypothesis P(k) is the statement that k < 2k. To
complete the inductive step, we need to show that if P(k) is true, then P(k + 1), which is
the statement that k + 1 < 2k+1 is true. That is, we need to show that if k < 2k, then k + 1
< 2k+1. To show that this conditional statement is true for the positive integer k, we first

k + 1< 2k +1 ≤ 2k + 2k = 2 ⋅ 2k = 2k+1
add 1 to both sides of k < 2k, and then note that 1 ≤ 2k. This tells us that

This shows that P(k + 1) is true, namely, that k + 1 < 2k+1, based on the assumption that
P(k)
is true. The induction step is complete.
Therefore, because we have completed both the basis step and the inductive step, by
the principle of mathematical induction we have shown that n < 2n is true for all positive
integers n.

Q- Use mathematical induction to prove that n3 − n is divisible by 3 whenever n is a

positive
integer.
Solution: To construct the proof, let P(n) denote the proposition: “n3 − n is divisible by 3.”

BASIS STEP: The statement P(1) is true because 13 − 1 = 0 is divisible by 3. This

completes
the basis step.
INDUCTIVE STEP: For the inductive hypothesis we assume that P(k) is true; that is, we
assume
that k3 − k is divisible by 3 for an arbitrary positive integer k. To complete the inductive
step, we must show that when we assume the inductive hypothesis, it follows that P(k +
1), the statement that
(k + 1)3 − (k + 1) is divisible by 3, is also true. That is, we must show that (k + 1)3 − (k
+ 1)
is divisible by 3. Note that
(k + 1)3 − (k + 1) = (k3 + 3k2 + 3k + 1) − (k + 1)
= (k3 − k) + 3(k2 + k).
Using the inductive hypothesis, we conclude that the first term k3 − k is divisible by 3.
The
second term is divisible by 3 because it is 3 times an integer. (k + 1)3 − (k + 1) is also
divisible by 3. This completes the inductive step.
Because we have completed both the basis step and the inductive step, by the principle
of mathematical induction we know that n3 − n is divisible by 3 whenever n is a
positive integer.

Proof Methods

Proof by Contraposition
Proofs by contraposition make use of the fact that the conditional statement p → q is
equivalent to its contrapositive, ~q → ~p. This means that the conditional statement p
→ q can be proved by showing that its contrapositive, ~q → ~p, is true.

Q- Prove that if n is an integer and 3n + 2 is odd, then n is odd.

Solution:
The first step in a proof by contraposition is to assume that the conclusion of the
conditional statement “If 3n + 2 is odd, then n is odd” is false; namely, assume that n is
even. Then, by the definition of an even integer, n = 2k for some integer k. Substituting
2k for n, we find that 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1). This tells us that 3n + 2 is
even (because it is a multiple of 2), and therefore not odd. This is the negation of the
premise of the theorem. Because the negation of the conclusion of the conditional
statement implies that the hypothesis is false, the original conditional statement is true.
Our proof by contraposition succeeded; we have proved the theorem “If 3n + 2 is odd,
then n is odd.”

Proofs by Contradiction

Proof by contradiction can be used to prove conditional statements. In such proofs, we

first assume the negation of the conclusion. We then use the premises of the theorem
and the negation of the conclusion to arrive at a contradiction.

Proofs by Counter-examples
A proof by counterexample is not technically a proof. It is merely a way of showing that a
given statement cannot possibly be correct by showing an instance that contradicts a
universal statement.

Q-Show that the statement “Every positive integer is the sum of the squares of two
integers” is false.
Solution: To show that this statement is false, we look for a counterexample, which is a
particular integer that is not the sum of the squares of two integers. It does not take long
to find a counterexample, because 3 cannot be written as the sum of the squares of two
integers.
To show this is the case, note that the only perfect squares not exceeding 3 are 0 2 = 0
and 12 = 1. Furthermore, there is no way to get 3 as the sum of two terms each of which
is 0 or 1. Consequently, we have shown that “Every positive integer is the sum of the
squares of two integers” is false.