Unit III: Relations & Functions

Questions & Step-by-Step Solutions

BCA 151 – Discrete Structure

Interactive Study Guide

BCA Programme · Second Semester

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 1 / 29
 Contents

1 Part A — Short Answer Questions (1–2 marks)

2 Part B — Medium Answer Questions (3–4 marks)

3 Part C — Long Answer Questions (5+ marks)

4 Reference — Summary Tables

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 2 / 29
 A-Q15 — Define a Relation

Question
Define a relation from A to B. Give an example. [1–2 marks]

Solution
A binary relation R from set A to set B is any subset of the Cartesian product A × B:

R ⊆ A×B

We write a R b (equivalently (a, b) ∈ R) to mean “a is related to b”.

Key Terms:
Domain of R: dom(R) = {a ∈ A | ∃ b ∈ B, (a, b) ∈ R}
Range of R: ran(R) = {b ∈ B | ∃ a ∈ A, (a, b) ∈ R}
A relation on A means R ⊆ A × A.
Example: A = {1, 2}, B = {a, b, c}, R = {(1, a), (1, b), (2, c)}.
Domain = {1, 2}, Range = {a, b, c}.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 3 / 29
 A-Q15 — Define a Relation

Question
Define a relation from A to B. Give an example. [1–2 marks]

Solution
A binary relation R from set A to set B is any subset of the Cartesian product A × B:

R ⊆ A×B

We write a R b (equivalently (a, b) ∈ R) to mean “a is related to b”.

Key Terms:
Domain of R: dom(R) = {a ∈ A | ∃ b ∈ B, (a, b) ∈ R}
Range of R: ran(R) = {b ∈ B | ∃ a ∈ A, (a, b) ∈ R}
A relation on A means R ⊆ A × A.
Example: A = {1, 2}, B = {a, b, c}, R = {(1, a), (1, b), (2, c)}.
Domain = {1, 2}, Range = {a, b, c}.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 3 / 29
 A-Q15 — Define a Relation

Question
Define a relation from A to B. Give an example. [1–2 marks]

Solution
A binary relation R from set A to set B is any subset of the Cartesian product A × B:

R ⊆ A×B

We write a R b (equivalently (a, b) ∈ R) to mean “a is related to b”.

Key Terms:
Domain of R: dom(R) = {a ∈ A | ∃ b ∈ B, (a, b) ∈ R}
Range of R: ran(R) = {b ∈ B | ∃ a ∈ A, (a, b) ∈ R}
A relation on A means R ⊆ A × A.
Example: A = {1, 2}, B = {a, b, c}, R = {(1, a), (1, b), (2, c)}.
Domain = {1, 2}, Range = {a, b, c}.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 3 / 29
 A-Q15 — Define a Relation

Question
Define a relation from A to B. Give an example. [1–2 marks]

Solution
A binary relation R from set A to set B is any subset of the Cartesian product A × B:

R ⊆ A×B

We write a R b (equivalently (a, b) ∈ R) to mean “a is related to b”.

Key Terms:
Domain of R: dom(R) = {a ∈ A | ∃ b ∈ B, (a, b) ∈ R}
Range of R: ran(R) = {b ∈ B | ∃ a ∈ A, (a, b) ∈ R}
A relation on A means R ⊆ A × A.
Example: A = {1, 2}, B = {a, b, c}, R = {(1, a), (1, b), (2, c)}.
Domain = {1, 2}, Range = {a, b, c}.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 3 / 29
 A-Q15 — Define a Relation

Question
Define a relation from A to B. Give an example. [1–2 marks]

Solution
A binary relation R from set A to set B is any subset of the Cartesian product A × B:

R ⊆ A×B

We write a R b (equivalently (a, b) ∈ R) to mean “a is related to b”.

Key Terms:
Domain of R: dom(R) = {a ∈ A | ∃ b ∈ B, (a, b) ∈ R}
Range of R: ran(R) = {b ∈ B | ∃ a ∈ A, (a, b) ∈ R}
A relation on A means R ⊆ A × A.
Example: A = {1, 2}, B = {a, b, c}, R = {(1, a), (1, b), (2, c)}.
Domain = {1, 2}, Range = {a, b, c}.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 3 / 29
 A-Q15 — Define a Relation

Question
Define a relation from A to B. Give an example. [1–2 marks]

Solution
A binary relation R from set A to set B is any subset of the Cartesian product A × B:

R ⊆ A×B

We write a R b (equivalently (a, b) ∈ R) to mean “a is related to b”.

Key Terms:
Domain of R: dom(R) = {a ∈ A | ∃ b ∈ B, (a, b) ∈ R}
Range of R: ran(R) = {b ∈ B | ∃ a ∈ A, (a, b) ∈ R}
A relation on A means R ⊆ A × A.
Example: A = {1, 2}, B = {a, b, c}, R = {(1, a), (1, b), (2, c)}.
Domain = {1, 2}, Range = {a, b, c}.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 3 / 29
 A-Q15 — Define a Relation

Question
Define a relation from A to B. Give an example. [1–2 marks]

Solution
A binary relation R from set A to set B is any subset of the Cartesian product A × B:

R ⊆ A×B

We write a R b (equivalently (a, b) ∈ R) to mean “a is related to b”.

Key Terms:
Domain of R: dom(R) = {a ∈ A | ∃ b ∈ B, (a, b) ∈ R}
Range of R: ran(R) = {b ∈ B | ∃ a ∈ A, (a, b) ∈ R}
A relation on A means R ⊆ A × A.
Example: A = {1, 2}, B = {a, b, c}, R = {(1, a), (1, b), (2, c)}.
Domain = {1, 2}, Range = {a, b, c}.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 3 / 29
 A-Q16/17/18 — Reflexive, Symmetric, Transitive
Question
Define reflexive, symmetric, and transitive relations with examples. [1–2 marks each]

Reflexive Symmetric Transitive

(a, a) ∈ R for all a ∈ A. (a, b) ∈ R ⇒ (b, a) ∈ R. (a, b), (b, c) ∈ R ⇒
Example: A = {1, 2} (a, c) ∈ R.
R = {(1, 1), (2, 2)} Example: Example:
Each element relates to it- R = {(1, 2), (2, 1)} {(1, 2), (2, 3), (1, 3)}
self. Every arrow has a reverse. 2-step ⇒ shortcut exists.

1 1
1 2

2 2 3

Key Idea
Digraph rules: Reflexive = loops at all nodes. Symmetric = all arrows bidirectional. Transitive
= 2-hop paths have a direct shortcut.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 4 / 29
 A-Q16/17/18 — Reflexive, Symmetric, Transitive
Question
Define reflexive, symmetric, and transitive relations with examples. [1–2 marks each]

Reflexive Symmetric Transitive

(a, a) ∈ R for all a ∈ A. (a, b) ∈ R ⇒ (b, a) ∈ R. (a, b), (b, c) ∈ R ⇒
Example: A = {1, 2} (a, c) ∈ R.
R = {(1, 1), (2, 2)} Example: Example:
Each element relates to it- R = {(1, 2), (2, 1)} {(1, 2), (2, 3), (1, 3)}
self. Every arrow has a reverse. 2-step ⇒ shortcut exists.

1 1
1 2

2 2 3

Key Idea
Digraph rules: Reflexive = loops at all nodes. Symmetric = all arrows bidirectional. Transitive
= 2-hop paths have a direct shortcut.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 4 / 29
 A-Q16/17/18 — Reflexive, Symmetric, Transitive
Question
Define reflexive, symmetric, and transitive relations with examples. [1–2 marks each]

Reflexive Symmetric Transitive

(a, a) ∈ R for all a ∈ A. (a, b) ∈ R ⇒ (b, a) ∈ R. (a, b), (b, c) ∈ R ⇒
Example: A = {1, 2} (a, c) ∈ R.
R = {(1, 1), (2, 2)} Example: Example:
Each element relates to it- R = {(1, 2), (2, 1)} {(1, 2), (2, 3), (1, 3)}
self. Every arrow has a reverse. 2-step ⇒ shortcut exists.

1 1
1 2

2 2 3

Key Idea
Digraph rules: Reflexive = loops at all nodes. Symmetric = all arrows bidirectional. Transitive
= 2-hop paths have a direct shortcut.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 4 / 29
 A-Q16/17/18 — Reflexive, Symmetric, Transitive
Question
Define reflexive, symmetric, and transitive relations with examples. [1–2 marks each]

Reflexive Symmetric Transitive

(a, a) ∈ R for all a ∈ A. (a, b) ∈ R ⇒ (b, a) ∈ R. (a, b), (b, c) ∈ R ⇒
Example: A = {1, 2} (a, c) ∈ R.
R = {(1, 1), (2, 2)} Example: Example:
Each element relates to it- R = {(1, 2), (2, 1)} {(1, 2), (2, 3), (1, 3)}
self. Every arrow has a reverse. 2-step ⇒ shortcut exists.

1 1
1 2

2 2 3

Key Idea
Digraph rules: Reflexive = loops at all nodes. Symmetric = all arrows bidirectional. Transitive
= 2-hop paths have a direct shortcut.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 4 / 29
 A-Q16/17/18 — Reflexive, Symmetric, Transitive
Question
Define reflexive, symmetric, and transitive relations with examples. [1–2 marks each]

Reflexive Symmetric Transitive

(a, a) ∈ R for all a ∈ A. (a, b) ∈ R ⇒ (b, a) ∈ R. (a, b), (b, c) ∈ R ⇒
Example: A = {1, 2} (a, c) ∈ R.
R = {(1, 1), (2, 2)} Example: Example:
Each element relates to it- R = {(1, 2), (2, 1)} {(1, 2), (2, 3), (1, 3)}
self. Every arrow has a reverse. 2-step ⇒ shortcut exists.

1 1
1 2

2 2 3

Key Idea
Digraph rules: Reflexive = loops at all nodes. Symmetric = all arrows bidirectional. Transitive
= 2-hop paths have a direct shortcut.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 4 / 29
 A-Q16/17/18 — Reflexive, Symmetric, Transitive
Question
Define reflexive, symmetric, and transitive relations with examples. [1–2 marks each]

Reflexive Symmetric Transitive

(a, a) ∈ R for all a ∈ A. (a, b) ∈ R ⇒ (b, a) ∈ R. (a, b), (b, c) ∈ R ⇒
Example: A = {1, 2} (a, c) ∈ R.
R = {(1, 1), (2, 2)} Example: Example:
Each element relates to it- R = {(1, 2), (2, 1)} {(1, 2), (2, 3), (1, 3)}
self. Every arrow has a reverse. 2-step ⇒ shortcut exists.

1 1
1 2

2 2 3

Key Idea
Digraph rules: Reflexive = loops at all nodes. Symmetric = all arrows bidirectional. Transitive
= 2-hop paths have a direct shortcut.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 4 / 29
 A-Q16/17/18 — Reflexive, Symmetric, Transitive
Question
Define reflexive, symmetric, and transitive relations with examples. [1–2 marks each]

Reflexive Symmetric Transitive

(a, a) ∈ R for all a ∈ A. (a, b) ∈ R ⇒ (b, a) ∈ R. (a, b), (b, c) ∈ R ⇒
Example: A = {1, 2} (a, c) ∈ R.
R = {(1, 1), (2, 2)} Example: Example:
Each element relates to it- R = {(1, 2), (2, 1)} {(1, 2), (2, 3), (1, 3)}
self. Every arrow has a reverse. 2-step ⇒ shortcut exists.

1 1
1 2

2 2 3

Key Idea
Digraph rules: Reflexive = loops at all nodes. Symmetric = all arrows bidirectional. Transitive
= 2-hop paths have a direct shortcut.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 4 / 29
 A-Q16/17/18 — Reflexive, Symmetric, Transitive
Question
Define reflexive, symmetric, and transitive relations with examples. [1–2 marks each]

Reflexive Symmetric Transitive

(a, a) ∈ R for all a ∈ A. (a, b) ∈ R ⇒ (b, a) ∈ R. (a, b), (b, c) ∈ R ⇒
Example: A = {1, 2} (a, c) ∈ R.
R = {(1, 1), (2, 2)} Example: Example:
Each element relates to it- R = {(1, 2), (2, 1)} {(1, 2), (2, 3), (1, 3)}
self. Every arrow has a reverse. 2-step ⇒ shortcut exists.

1 1
1 2

2 2 3

Key Idea
Digraph rules: Reflexive = loops at all nodes. Symmetric = all arrows bidirectional. Transitive
= 2-hop paths have a direct shortcut.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 4 / 29
 A-Q19 & A-Q20 — Equivalence vs. Partial Order

Q19: Equivalence Relation Q20: Partial Order Relation

Define equivalence relation. [1–2 marks] Define partial order relation. [1–2 marks]

Solution Solution
R is an equivalence relation if it is simulta- R is a partial order (poset) if it is:
neously: 1 Reflexive (R)
1 Reflexive (R) 2 Anti-symmetric (AS)
2 Symmetric (S) (a, b), (b, a) ∈ R ⇒ a = b
3 Transitive (T) 3 Transitive (T)
Example: “=” on Z. Example: “≤” on N.
Notation: a ∼ b (read “a equivalent to b”). (A, R) is called a poset.

Key Idea
Critical difference: Equivalence uses Symmetric (RST); Partial Order uses Anti-symmetric
(RAST).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 5 / 29
 A-Q19 & A-Q20 — Equivalence vs. Partial Order

Q19: Equivalence Relation Q20: Partial Order Relation

Define equivalence relation. [1–2 marks] Define partial order relation. [1–2 marks]

Solution Solution
R is an equivalence relation if it is simulta- R is a partial order (poset) if it is:
neously: 1 Reflexive (R)
1 Reflexive (R) 2 Anti-symmetric (AS)
2 Symmetric (S) (a, b), (b, a) ∈ R ⇒ a = b
3 Transitive (T) 3 Transitive (T)
Example: “=” on Z. Example: “≤” on N.
Notation: a ∼ b (read “a equivalent to b”). (A, R) is called a poset.

Key Idea
Critical difference: Equivalence uses Symmetric (RST); Partial Order uses Anti-symmetric
(RAST).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 5 / 29
 A-Q19 & A-Q20 — Equivalence vs. Partial Order

Q19: Equivalence Relation Q20: Partial Order Relation

Define equivalence relation. [1–2 marks] Define partial order relation. [1–2 marks]

Solution Solution
R is an equivalence relation if it is simulta- R is a partial order (poset) if it is:
neously: 1 Reflexive (R)
1 Reflexive (R) 2 Anti-symmetric (AS)
2 Symmetric (S) (a, b), (b, a) ∈ R ⇒ a = b
3 Transitive (T) 3 Transitive (T)
Example: “=” on Z. Example: “≤” on N.
Notation: a ∼ b (read “a equivalent to b”). (A, R) is called a poset.

Key Idea
Critical difference: Equivalence uses Symmetric (RST); Partial Order uses Anti-symmetric
(RAST).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 5 / 29
 A-Q19 & A-Q20 — Equivalence vs. Partial Order

Q19: Equivalence Relation Q20: Partial Order Relation

Define equivalence relation. [1–2 marks] Define partial order relation. [1–2 marks]

Solution Solution
R is an equivalence relation if it is simulta- R is a partial order (poset) if it is:
neously: 1 Reflexive (R)
1 Reflexive (R) 2 Anti-symmetric (AS)
2 Symmetric (S) (a, b), (b, a) ∈ R ⇒ a = b
3 Transitive (T) 3 Transitive (T)
Example: “=” on Z. Example: “≤” on N.
Notation: a ∼ b (read “a equivalent to b”). (A, R) is called a poset.

Key Idea
Critical difference: Equivalence uses Symmetric (RST); Partial Order uses Anti-symmetric
(RAST).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 5 / 29
 A-Q19 & A-Q20 — Equivalence vs. Partial Order

Q19: Equivalence Relation Q20: Partial Order Relation

Define equivalence relation. [1–2 marks] Define partial order relation. [1–2 marks]

Solution Solution
R is an equivalence relation if it is simulta- R is a partial order (poset) if it is:
neously: 1 Reflexive (R)
1 Reflexive (R) 2 Anti-symmetric (AS)
2 Symmetric (S) (a, b), (b, a) ∈ R ⇒ a = b
3 Transitive (T) 3 Transitive (T)
Example: “=” on Z. Example: “≤” on N.
Notation: a ∼ b (read “a equivalent to b”). (A, R) is called a poset.

Key Idea
Critical difference: Equivalence uses Symmetric (RST); Partial Order uses Anti-symmetric
(RAST).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 5 / 29
 A-Q19 & A-Q20 — Equivalence vs. Partial Order

Q19: Equivalence Relation Q20: Partial Order Relation

Define equivalence relation. [1–2 marks] Define partial order relation. [1–2 marks]

Solution Solution
R is an equivalence relation if it is simulta- R is a partial order (poset) if it is:
neously: 1 Reflexive (R)
1 Reflexive (R) 2 Anti-symmetric (AS)
2 Symmetric (S) (a, b), (b, a) ∈ R ⇒ a = b
3 Transitive (T) 3 Transitive (T)
Example: “=” on Z. Example: “≤” on N.
Notation: a ∼ b (read “a equivalent to b”). (A, R) is called a poset.

Key Idea
Critical difference: Equivalence uses Symmetric (RST); Partial Order uses Anti-symmetric
(RAST).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 5 / 29
 A-Q19 & A-Q20 — Equivalence vs. Partial Order

Q19: Equivalence Relation Q20: Partial Order Relation

Define equivalence relation. [1–2 marks] Define partial order relation. [1–2 marks]

Solution Solution
R is an equivalence relation if it is simulta- R is a partial order (poset) if it is:
neously: 1 Reflexive (R)
1 Reflexive (R) 2 Anti-symmetric (AS)
2 Symmetric (S) (a, b), (b, a) ∈ R ⇒ a = b
3 Transitive (T) 3 Transitive (T)
Example: “=” on Z. Example: “≤” on N.
Notation: a ∼ b (read “a equivalent to b”). (A, R) is called a poset.

Key Idea
Critical difference: Equivalence uses Symmetric (RST); Partial Order uses Anti-symmetric
(RAST).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 5 / 29
 A-Q19 & A-Q20 — Equivalence vs. Partial Order

Q19: Equivalence Relation Q20: Partial Order Relation

Define equivalence relation. [1–2 marks] Define partial order relation. [1–2 marks]

Solution Solution
R is an equivalence relation if it is simulta- R is a partial order (poset) if it is:
neously: 1 Reflexive (R)
1 Reflexive (R) 2 Anti-symmetric (AS)
2 Symmetric (S) (a, b), (b, a) ∈ R ⇒ a = b
3 Transitive (T) 3 Transitive (T)
Example: “=” on Z. Example: “≤” on N.
Notation: a ∼ b (read “a equivalent to b”). (A, R) is called a poset.

Key Idea
Critical difference: Equivalence uses Symmetric (RST); Partial Order uses Anti-symmetric
(RAST).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 5 / 29
 A-Q19 & A-Q20 — Equivalence vs. Partial Order

Q19: Equivalence Relation Q20: Partial Order Relation

Define equivalence relation. [1–2 marks] Define partial order relation. [1–2 marks]

Solution Solution
R is an equivalence relation if it is simulta- R is a partial order (poset) if it is:
neously: 1 Reflexive (R)
1 Reflexive (R) 2 Anti-symmetric (AS)
2 Symmetric (S) (a, b), (b, a) ∈ R ⇒ a = b
3 Transitive (T) 3 Transitive (T)
Example: “=” on Z. Example: “≤” on N.
Notation: a ∼ b (read “a equivalent to b”). (A, R) is called a poset.

Key Idea
Critical difference: Equivalence uses Symmetric (RST); Partial Order uses Anti-symmetric
(RAST).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 5 / 29
 A-Q19 & A-Q20 — Equivalence vs. Partial Order

Q19: Equivalence Relation Q20: Partial Order Relation

Define equivalence relation. [1–2 marks] Define partial order relation. [1–2 marks]

Solution Solution
R is an equivalence relation if it is simulta- R is a partial order (poset) if it is:
neously: 1 Reflexive (R)
1 Reflexive (R) 2 Anti-symmetric (AS)
2 Symmetric (S) (a, b), (b, a) ∈ R ⇒ a = b
3 Transitive (T) 3 Transitive (T)
Example: “=” on Z. Example: “≤” on N.
Notation: a ∼ b (read “a equivalent to b”). (A, R) is called a poset.

Key Idea
Critical difference: Equivalence uses Symmetric (RST); Partial Order uses Anti-symmetric
(RAST).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 5 / 29
 A-Q19 & A-Q20 — Equivalence vs. Partial Order

Q19: Equivalence Relation Q20: Partial Order Relation

Define equivalence relation. [1–2 marks] Define partial order relation. [1–2 marks]

Solution Solution
R is an equivalence relation if it is simulta- R is a partial order (poset) if it is:
neously: 1 Reflexive (R)
1 Reflexive (R) 2 Anti-symmetric (AS)
2 Symmetric (S) (a, b), (b, a) ∈ R ⇒ a = b
3 Transitive (T) 3 Transitive (T)
Example: “=” on Z. Example: “≤” on N.
Notation: a ∼ b (read “a equivalent to b”). (A, R) is called a poset.

Key Idea
Critical difference: Equivalence uses Symmetric (RST); Partial Order uses Anti-symmetric
(RAST).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 5 / 29
 A-Q21 & A-Q22 — Digraph & Matrix Representations

Question
How is a relation represented by (i) a digraph, and (ii) a matrix? [1–2 marks each]

(i) Directed Graph (Digraph) (ii) Boolean Matrix MR

Each element of A → a node Rows and columns indexed by elements of

(vertex). A: (
(a, b) ∈ R → directed edge (arrow) 1 if (i, j) ∈ R
MR [i][j] =
a → b. 0 otherwise
(a, a) ∈ R → a self-loop at node a.
Diagonal all 1 ⇔ Reflexive.
Loops at all nodes ⇔ Reflexive. MR = MR⊤ ⇔ Symmetric.
All arrows bidirectional ⇔ Symmetric.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 6 / 29
 A-Q21 & A-Q22 — Digraph & Matrix Representations

Question
How is a relation represented by (i) a digraph, and (ii) a matrix? [1–2 marks each]

(i) Directed Graph (Digraph) (ii) Boolean Matrix MR

Each element of A → a node Rows and columns indexed by elements of

(vertex). A: (
(a, b) ∈ R → directed edge (arrow) 1 if (i, j) ∈ R
MR [i][j] =
a → b. 0 otherwise
(a, a) ∈ R → a self-loop at node a.
Diagonal all 1 ⇔ Reflexive.
Loops at all nodes ⇔ Reflexive. MR = MR⊤ ⇔ Symmetric.
All arrows bidirectional ⇔ Symmetric.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 6 / 29
 A-Q21 & A-Q22 — Digraph & Matrix Representations

Question
How is a relation represented by (i) a digraph, and (ii) a matrix? [1–2 marks each]

(i) Directed Graph (Digraph) (ii) Boolean Matrix MR

Each element of A → a node Rows and columns indexed by elements of

(vertex). A: (
(a, b) ∈ R → directed edge (arrow) 1 if (i, j) ∈ R
MR [i][j] =
a → b. 0 otherwise
(a, a) ∈ R → a self-loop at node a.
Diagonal all 1 ⇔ Reflexive.
Loops at all nodes ⇔ Reflexive. MR = MR⊤ ⇔ Symmetric.
All arrows bidirectional ⇔ Symmetric.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 6 / 29
 A-Q21 & A-Q22 — Digraph & Matrix Representations

Question
How is a relation represented by (i) a digraph, and (ii) a matrix? [1–2 marks each]

(i) Directed Graph (Digraph) (ii) Boolean Matrix MR

Each element of A → a node Rows and columns indexed by elements of

(vertex). A: (
(a, b) ∈ R → directed edge (arrow) 1 if (i, j) ∈ R
MR [i][j] =
a → b. 0 otherwise
(a, a) ∈ R → a self-loop at node a.
Diagonal all 1 ⇔ Reflexive.
Loops at all nodes ⇔ Reflexive. MR = MR⊤ ⇔ Symmetric.
All arrows bidirectional ⇔ Symmetric.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 6 / 29
 A-Q21 & A-Q22 — Digraph & Matrix Representations

Question
How is a relation represented by (i) a digraph, and (ii) a matrix? [1–2 marks each]

(i) Directed Graph (Digraph) (ii) Boolean Matrix MR

Each element of A → a node Rows and columns indexed by elements of

(vertex). A: (
(a, b) ∈ R → directed edge (arrow) 1 if (i, j) ∈ R
MR [i][j] =
a → b. 0 otherwise
(a, a) ∈ R → a self-loop at node a.
Diagonal all 1 ⇔ Reflexive.
Loops at all nodes ⇔ Reflexive. MR = MR⊤ ⇔ Symmetric.
All arrows bidirectional ⇔ Symmetric.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 6 / 29
 A-Q21 & A-Q22 — Digraph & Matrix Representations

Question
How is a relation represented by (i) a digraph, and (ii) a matrix? [1–2 marks each]

(i) Directed Graph (Digraph) (ii) Boolean Matrix MR

Each element of A → a node Rows and columns indexed by elements of

(vertex). A: (
(a, b) ∈ R → directed edge (arrow) 1 if (i, j) ∈ R
MR [i][j] =
a → b. 0 otherwise
(a, a) ∈ R → a self-loop at node a.
Diagonal all 1 ⇔ Reflexive.
Loops at all nodes ⇔ Reflexive. MR = MR⊤ ⇔ Symmetric.
All arrows bidirectional ⇔ Symmetric.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 6 / 29
 A-Q21 & A-Q22 — Digraph & Matrix Representations

Question
How is a relation represented by (i) a digraph, and (ii) a matrix? [1–2 marks each]

(i) Directed Graph (Digraph) (ii) Boolean Matrix MR

Each element of A → a node Rows and columns indexed by elements of

(vertex). A: (
(a, b) ∈ R → directed edge (arrow) 1 if (i, j) ∈ R
MR [i][j] =
a → b. 0 otherwise
(a, a) ∈ R → a self-loop at node a.
Diagonal all 1 ⇔ Reflexive.
Loops at all nodes ⇔ Reflexive. MR = MR⊤ ⇔ Symmetric.
All arrows bidirectional ⇔ Symmetric.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 6 / 29
 A-Q23 & A-Q24 — Function, Domain, Range

Question
Define a function. Define domain and range of a function. [1–2 marks each]

Solution
A function f : A → B is a relation from A to B such that every element of A maps to exactly
one element of B:
∀ a ∈ A, ∃! b ∈ B s.t. f (a) = b

Domain Co-domain Range

Set A = all inputs. Set B = all possible Actual outputs used.

outputs. {f (a) | a ∈ A}
A = dom(f ) Range ⊆ Co-domain.
B = codom(f )
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 7 / 29
 A-Q23 & A-Q24 — Function, Domain, Range

Question
Define a function. Define domain and range of a function. [1–2 marks each]

Solution
A function f : A → B is a relation from A to B such that every element of A maps to exactly
one element of B:
∀ a ∈ A, ∃! b ∈ B s.t. f (a) = b

Domain Co-domain Range

Set A = all inputs. Set B = all possible Actual outputs used.

outputs. {f (a) | a ∈ A}
A = dom(f ) Range ⊆ Co-domain.
B = codom(f )
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 7 / 29
 A-Q23 & A-Q24 — Function, Domain, Range

Question
Define a function. Define domain and range of a function. [1–2 marks each]

Solution
A function f : A → B is a relation from A to B such that every element of A maps to exactly
one element of B:
∀ a ∈ A, ∃! b ∈ B s.t. f (a) = b

Domain Co-domain Range

Set A = all inputs. Set B = all possible Actual outputs used.

outputs. {f (a) | a ∈ A}
A = dom(f ) Range ⊆ Co-domain.
B = codom(f )
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 7 / 29
 A-Q23 & A-Q24 — Function, Domain, Range

Question
Define a function. Define domain and range of a function. [1–2 marks each]

Solution
A function f : A → B is a relation from A to B such that every element of A maps to exactly
one element of B:
∀ a ∈ A, ∃! b ∈ B s.t. f (a) = b

Domain Co-domain Range

Set A = all inputs. Set B = all possible Actual outputs used.

outputs. {f (a) | a ∈ A}
A = dom(f ) Range ⊆ Co-domain.
B = codom(f )
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 7 / 29
 A-Q23 & A-Q24 — Function, Domain, Range

Question
Define a function. Define domain and range of a function. [1–2 marks each]

Solution
A function f : A → B is a relation from A to B such that every element of A maps to exactly
one element of B:
∀ a ∈ A, ∃! b ∈ B s.t. f (a) = b

Domain Co-domain Range

Set A = all inputs. Set B = all possible Actual outputs used.

outputs. {f (a) | a ∈ A}
A = dom(f ) Range ⊆ Co-domain.
B = codom(f )
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 7 / 29
 A-Q25/26/27 — Types of Functions

Question
Define onto function, into function, and one-to-one function. [1–2 marks each]

One-to-One (Injective) Onto (Surjective) Into (Not Onto)

f (x1 ) = f (x2 ) ⇒ x1 = x2 Range = Co-domain. Range ⊊ Co-domain.

Different inputs ⇒ different Every b ∈ B is mapped to. Some b ∈ B not reached.
outputs. At least one arrow reaches At least one element of B
No two arrows share a tar- every element of B. has no arrow pointing to it.
get.
a x
x a
a x b y

zÖmissed
c y b
b y
c z

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 8 / 29
 A-Q25/26/27 — Types of Functions

Question
Define onto function, into function, and one-to-one function. [1–2 marks each]

One-to-One (Injective) Onto (Surjective) Into (Not Onto)

f (x1 ) = f (x2 ) ⇒ x1 = x2 Range = Co-domain. Range ⊊ Co-domain.

Different inputs ⇒ different Every b ∈ B is mapped to. Some b ∈ B not reached.
outputs. At least one arrow reaches At least one element of B
No two arrows share a tar- every element of B. has no arrow pointing to it.
get.
a x
x a
a x b y

zÖmissed
c y b
b y
c z

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 8 / 29
 A-Q25/26/27 — Types of Functions

Question
Define onto function, into function, and one-to-one function. [1–2 marks each]

One-to-One (Injective) Onto (Surjective) Into (Not Onto)

f (x1 ) = f (x2 ) ⇒ x1 = x2 Range = Co-domain. Range ⊊ Co-domain.

Different inputs ⇒ different Every b ∈ B is mapped to. Some b ∈ B not reached.
outputs. At least one arrow reaches At least one element of B
No two arrows share a tar- every element of B. has no arrow pointing to it.
get.
a x
x a
a x b y

zÖmissed
c y b
b y
c z

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 8 / 29
 A-Q25/26/27 — Types of Functions

Question
Define onto function, into function, and one-to-one function. [1–2 marks each]

One-to-One (Injective) Onto (Surjective) Into (Not Onto)

f (x1 ) = f (x2 ) ⇒ x1 = x2 Range = Co-domain. Range ⊊ Co-domain.

Different inputs ⇒ different Every b ∈ B is mapped to. Some b ∈ B not reached.
outputs. At least one arrow reaches At least one element of B
No two arrows share a tar- every element of B. has no arrow pointing to it.
get.
a x
x a
a x b y

zÖmissed
c y b
b y
c z

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 8 / 29
 A-Q25/26/27 — Types of Functions

Question
Define onto function, into function, and one-to-one function. [1–2 marks each]

One-to-One (Injective) Onto (Surjective) Into (Not Onto)

f (x1 ) = f (x2 ) ⇒ x1 = x2 Range = Co-domain. Range ⊊ Co-domain.

Different inputs ⇒ different Every b ∈ B is mapped to. Some b ∈ B not reached.
outputs. At least one arrow reaches At least one element of B
No two arrows share a tar- every element of B. has no arrow pointing to it.
get.
a x
x a
a x b y

zÖmissed
c y b
b y
c z

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 8 / 29
 A-Q25/26/27 — Types of Functions

Question
Define onto function, into function, and one-to-one function. [1–2 marks each]

One-to-One (Injective) Onto (Surjective) Into (Not Onto)

f (x1 ) = f (x2 ) ⇒ x1 = x2 Range = Co-domain. Range ⊊ Co-domain.

Different inputs ⇒ different Every b ∈ B is mapped to. Some b ∈ B not reached.
outputs. At least one arrow reaches At least one element of B
No two arrows share a tar- every element of B. has no arrow pointing to it.
get.
a x
x a
a x b y

zÖmissed
c y b
b y
c z

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 8 / 29
 A-Q25/26/27 — Types of Functions

Question
Define onto function, into function, and one-to-one function. [1–2 marks each]

One-to-One (Injective) Onto (Surjective) Into (Not Onto)

f (x1 ) = f (x2 ) ⇒ x1 = x2 Range = Co-domain. Range ⊊ Co-domain.

Different inputs ⇒ different Every b ∈ B is mapped to. Some b ∈ B not reached.
outputs. At least one arrow reaches At least one element of B
No two arrows share a tar- every element of B. has no arrow pointing to it.
get.
a x
x a
a x b y

zÖmissed
c y b
b y
c z

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 8 / 29
 A-Q28 — Hashing Function

Question
Define a hashing function. [1–2 marks]

Solution
A hashing function h : K → I maps a set of keys K to table indices I (positions in a hash
table).
The most common form uses the division method:

h(k) = k mod m

where m is the size of the hash table.

Key Idea Worked Example, m = 5

Key properties:
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 9 / 29
 A-Q28 — Hashing Function

Question
Define a hashing function. [1–2 marks]

Solution
A hashing function h : K → I maps a set of keys K to table indices I (positions in a hash
table).
The most common form uses the division method:

h(k) = k mod m

where m is the size of the hash table.

Key Idea Worked Example, m = 5

Key properties:
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 9 / 29
 A-Q28 — Hashing Function

Question
Define a hashing function. [1–2 marks]

Solution
A hashing function h : K → I maps a set of keys K to table indices I (positions in a hash
table).
The most common form uses the division method:

h(k) = k mod m

where m is the size of the hash table.

Key Idea Worked Example, m = 5

Key properties:
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 9 / 29
 A-Q28 — Hashing Function

Question
Define a hashing function. [1–2 marks]

Solution
A hashing function h : K → I maps a set of keys K to table indices I (positions in a hash
table).
The most common form uses the division method:

h(k) = k mod m

where m is the size of the hash table.

Key Idea Worked Example, m = 5

Key properties:
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 9 / 29
 A-Q28 — Hashing Function

Question
Define a hashing function. [1–2 marks]

Solution
A hashing function h : K → I maps a set of keys K to table indices I (positions in a hash
table).
The most common form uses the division method:

h(k) = k mod m

where m is the size of the hash table.

Key Idea Worked Example, m = 5

Key properties:
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 9 / 29
 B-Q15 — Check RST Properties of a Given Relation

Question
Check whether R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} on A = {1, 2, 3} is reflexive, symmetric, and
transitive. [3–4 marks]

Digraph of R:
1. Reflexive? – Check (a, a) ∈ R for all a ∈ A
(1, 1) ∈ R ✓ (2, 2) ∈ R ✓ (3, 3) ∈ R ✓ 1
⇒ YES, Reflexive.

2. Symmetric? – Check (a, b) ∈ R ⇒ (b, a) ∈ R

2 3
(1, 2) ∈ R and (2, 1) ∈ R ✓
Diagonal pairs (a, a) are trivially symmetric.
⇒ YES, Symmetric. Key Idea
R + S + T ⇒ this is an Equiva-
3. Study
Interactive Transitive? – Check
Guide (BCA Programme allSemester)
· Second 2-hop paths
Unit III – Relations & Functions lence Relation! 10 / 29
 B-Q15 — Check RST Properties of a Given Relation

Question
Check whether R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} on A = {1, 2, 3} is reflexive, symmetric, and
transitive. [3–4 marks]

Digraph of R:
1. Reflexive? – Check (a, a) ∈ R for all a ∈ A
(1, 1) ∈ R ✓ (2, 2) ∈ R ✓ (3, 3) ∈ R ✓ 1
⇒ YES, Reflexive.

2. Symmetric? – Check (a, b) ∈ R ⇒ (b, a) ∈ R

2 3
(1, 2) ∈ R and (2, 1) ∈ R ✓
Diagonal pairs (a, a) are trivially symmetric.
⇒ YES, Symmetric. Key Idea
R + S + T ⇒ this is an Equiva-
3. Study
Interactive Transitive? – Check
Guide (BCA Programme allSemester)
· Second 2-hop paths
Unit III – Relations & Functions lence Relation! 10 / 29
 B-Q15 — Check RST Properties of a Given Relation

Question
Check whether R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} on A = {1, 2, 3} is reflexive, symmetric, and
transitive. [3–4 marks]

Digraph of R:
1. Reflexive? – Check (a, a) ∈ R for all a ∈ A
(1, 1) ∈ R ✓ (2, 2) ∈ R ✓ (3, 3) ∈ R ✓ 1
⇒ YES, Reflexive.

2. Symmetric? – Check (a, b) ∈ R ⇒ (b, a) ∈ R

2 3
(1, 2) ∈ R and (2, 1) ∈ R ✓
Diagonal pairs (a, a) are trivially symmetric.
⇒ YES, Symmetric. Key Idea
R + S + T ⇒ this is an Equiva-
3. Study
Interactive Transitive? – Check
Guide (BCA Programme allSemester)
· Second 2-hop paths
Unit III – Relations & Functions lence Relation! 10 / 29
 B-Q15 — Check RST Properties of a Given Relation

Question
Check whether R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} on A = {1, 2, 3} is reflexive, symmetric, and
transitive. [3–4 marks]

Digraph of R:
1. Reflexive? – Check (a, a) ∈ R for all a ∈ A
(1, 1) ∈ R ✓ (2, 2) ∈ R ✓ (3, 3) ∈ R ✓ 1
⇒ YES, Reflexive.

2. Symmetric? – Check (a, b) ∈ R ⇒ (b, a) ∈ R

2 3
(1, 2) ∈ R and (2, 1) ∈ R ✓
Diagonal pairs (a, a) are trivially symmetric.
⇒ YES, Symmetric. Key Idea
R + S + T ⇒ this is an Equiva-
3. Study
Interactive Transitive? – Check
Guide (BCA Programme allSemester)
· Second 2-hop paths
Unit III – Relations & Functions lence Relation! 10 / 29
 B-Q15 — Check RST Properties of a Given Relation

Question
Check whether R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} on A = {1, 2, 3} is reflexive, symmetric, and
transitive. [3–4 marks]

Digraph of R:
1. Reflexive? – Check (a, a) ∈ R for all a ∈ A
(1, 1) ∈ R ✓ (2, 2) ∈ R ✓ (3, 3) ∈ R ✓ 1
⇒ YES, Reflexive.

2. Symmetric? – Check (a, b) ∈ R ⇒ (b, a) ∈ R

2 3
(1, 2) ∈ R and (2, 1) ∈ R ✓
Diagonal pairs (a, a) are trivially symmetric.
⇒ YES, Symmetric. Key Idea
R + S + T ⇒ this is an Equiva-
3. Study
Interactive Transitive? – Check
Guide (BCA Programme allSemester)
· Second 2-hop paths
Unit III – Relations & Functions lence Relation! 10 / 29
 B-Q15 — Check RST Properties of a Given Relation

Question
Check whether R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} on A = {1, 2, 3} is reflexive, symmetric, and
transitive. [3–4 marks]

Digraph of R:
1. Reflexive? – Check (a, a) ∈ R for all a ∈ A
(1, 1) ∈ R ✓ (2, 2) ∈ R ✓ (3, 3) ∈ R ✓ 1
⇒ YES, Reflexive.

2. Symmetric? – Check (a, b) ∈ R ⇒ (b, a) ∈ R

2 3
(1, 2) ∈ R and (2, 1) ∈ R ✓
Diagonal pairs (a, a) are trivially symmetric.
⇒ YES, Symmetric. Key Idea
R + S + T ⇒ this is an Equiva-
3. Study
Interactive Transitive? – Check
Guide (BCA Programme allSemester)
· Second 2-hop paths
Unit III – Relations & Functions lence Relation! 10 / 29
 B-Q15 — Check RST Properties of a Given Relation

Question
Check whether R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} on A = {1, 2, 3} is reflexive, symmetric, and
transitive. [3–4 marks]

Digraph of R:
1. Reflexive? – Check (a, a) ∈ R for all a ∈ A
(1, 1) ∈ R ✓ (2, 2) ∈ R ✓ (3, 3) ∈ R ✓ 1
⇒ YES, Reflexive.

2. Symmetric? – Check (a, b) ∈ R ⇒ (b, a) ∈ R

2 3
(1, 2) ∈ R and (2, 1) ∈ R ✓
Diagonal pairs (a, a) are trivially symmetric.
⇒ YES, Symmetric. Key Idea
R + S + T ⇒ this is an Equiva-
3. Study
Interactive Transitive? – Check
Guide (BCA Programme allSemester)
· Second 2-hop paths
Unit III – Relations & Functions lence Relation! 10 / 29
 B-Q15 — Check RST Properties of a Given Relation

Question
Check whether R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} on A = {1, 2, 3} is reflexive, symmetric, and
transitive. [3–4 marks]

Digraph of R:
1. Reflexive? – Check (a, a) ∈ R for all a ∈ A
(1, 1) ∈ R ✓ (2, 2) ∈ R ✓ (3, 3) ∈ R ✓ 1
⇒ YES, Reflexive.

2. Symmetric? – Check (a, b) ∈ R ⇒ (b, a) ∈ R

2 3
(1, 2) ∈ R and (2, 1) ∈ R ✓
Diagonal pairs (a, a) are trivially symmetric.
⇒ YES, Symmetric. Key Idea
R + S + T ⇒ this is an Equiva-
3. Study
Interactive Transitive? – Check
Guide (BCA Programme allSemester)
· Second 2-hop paths
Unit III – Relations & Functions lence Relation! 10 / 29
 B-Q15 — Check RST Properties of a Given Relation

Question
Check whether R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)} on A = {1, 2, 3} is reflexive, symmetric, and
transitive. [3–4 marks]

Digraph of R:
1. Reflexive? – Check (a, a) ∈ R for all a ∈ A
(1, 1) ∈ R ✓ (2, 2) ∈ R ✓ (3, 3) ∈ R ✓ 1
⇒ YES, Reflexive.

2. Symmetric? – Check (a, b) ∈ R ⇒ (b, a) ∈ R

2 3
(1, 2) ∈ R and (2, 1) ∈ R ✓
Diagonal pairs (a, a) are trivially symmetric.
⇒ YES, Symmetric. Key Idea
R + S + T ⇒ this is an Equiva-
3. Study
Interactive Transitive? – Check
Guide (BCA Programme allSemester)
· Second 2-hop paths
Unit III – Relations & Functions lence Relation! 10 / 29
 B-Q16 — “Is Equal To” is an Equivalence Relation
Question
Show that “is equal to” (=) is an equivalence relation on Z. [3–4 marks]

Let R = {(a, b) ∈ Z × Z | a = b}.

1. Reflexive
For any a ∈ Z: a = a is always true.
⇒ (a, a) ∈ R for all a. Reflexive!

2. Symmetric
If a = b, then b = a.
⇒ (a, b) ∈ R ⇒ (b, a) ∈ R. Symmetric!

3. Transitive
If a = b and b = c, then a = c.
⇒ (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R. Transitive!

Solution
Since “=” satisfies Reflexive + Symmetric + Transitive, it is an equivalence relation on Z. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 11 / 29
 B-Q16 — “Is Equal To” is an Equivalence Relation
Question
Show that “is equal to” (=) is an equivalence relation on Z. [3–4 marks]

Let R = {(a, b) ∈ Z × Z | a = b}.

1. Reflexive
For any a ∈ Z: a = a is always true.
⇒ (a, a) ∈ R for all a. Reflexive!

2. Symmetric
If a = b, then b = a.
⇒ (a, b) ∈ R ⇒ (b, a) ∈ R. Symmetric!

3. Transitive
If a = b and b = c, then a = c.
⇒ (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R. Transitive!

Solution
Since “=” satisfies Reflexive + Symmetric + Transitive, it is an equivalence relation on Z. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 11 / 29
 B-Q16 — “Is Equal To” is an Equivalence Relation
Question
Show that “is equal to” (=) is an equivalence relation on Z. [3–4 marks]

Let R = {(a, b) ∈ Z × Z | a = b}.

1. Reflexive
For any a ∈ Z: a = a is always true.
⇒ (a, a) ∈ R for all a. Reflexive!

2. Symmetric
If a = b, then b = a.
⇒ (a, b) ∈ R ⇒ (b, a) ∈ R. Symmetric!

3. Transitive
If a = b and b = c, then a = c.
⇒ (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R. Transitive!

Solution
Since “=” satisfies Reflexive + Symmetric + Transitive, it is an equivalence relation on Z. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 11 / 29
 B-Q16 — “Is Equal To” is an Equivalence Relation
Question
Show that “is equal to” (=) is an equivalence relation on Z. [3–4 marks]

Let R = {(a, b) ∈ Z × Z | a = b}.

1. Reflexive
For any a ∈ Z: a = a is always true.
⇒ (a, a) ∈ R for all a. Reflexive!

2. Symmetric
If a = b, then b = a.
⇒ (a, b) ∈ R ⇒ (b, a) ∈ R. Symmetric!

3. Transitive
If a = b and b = c, then a = c.
⇒ (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R. Transitive!

Solution
Since “=” satisfies Reflexive + Symmetric + Transitive, it is an equivalence relation on Z. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 11 / 29
 B-Q16 — “Is Equal To” is an Equivalence Relation
Question
Show that “is equal to” (=) is an equivalence relation on Z. [3–4 marks]

Let R = {(a, b) ∈ Z × Z | a = b}.

1. Reflexive
For any a ∈ Z: a = a is always true.
⇒ (a, a) ∈ R for all a. Reflexive!

2. Symmetric
If a = b, then b = a.
⇒ (a, b) ∈ R ⇒ (b, a) ∈ R. Symmetric!

3. Transitive
If a = b and b = c, then a = c.
⇒ (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R. Transitive!

Solution
Since “=” satisfies Reflexive + Symmetric + Transitive, it is an equivalence relation on Z. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 11 / 29
 B-Q16 — “Is Equal To” is an Equivalence Relation
Question
Show that “is equal to” (=) is an equivalence relation on Z. [3–4 marks]

Let R = {(a, b) ∈ Z × Z | a = b}.

1. Reflexive
For any a ∈ Z: a = a is always true.
⇒ (a, a) ∈ R for all a. Reflexive!

2. Symmetric
If a = b, then b = a.
⇒ (a, b) ∈ R ⇒ (b, a) ∈ R. Symmetric!

3. Transitive
If a = b and b = c, then a = c.
⇒ (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R. Transitive!

Solution
Since “=” satisfies Reflexive + Symmetric + Transitive, it is an equivalence relation on Z. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 11 / 29
 B-Q16 — “Is Equal To” is an Equivalence Relation
Question
Show that “is equal to” (=) is an equivalence relation on Z. [3–4 marks]

Let R = {(a, b) ∈ Z × Z | a = b}.

1. Reflexive
For any a ∈ Z: a = a is always true.
⇒ (a, a) ∈ R for all a. Reflexive!

2. Symmetric
If a = b, then b = a.
⇒ (a, b) ∈ R ⇒ (b, a) ∈ R. Symmetric!

3. Transitive
If a = b and b = c, then a = c.
⇒ (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R. Transitive!

Solution
Since “=” satisfies Reflexive + Symmetric + Transitive, it is an equivalence relation on Z. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 11 / 29
 B-Q16 — “Is Equal To” is an Equivalence Relation
Question
Show that “is equal to” (=) is an equivalence relation on Z. [3–4 marks]

Let R = {(a, b) ∈ Z × Z | a = b}.

1. Reflexive
For any a ∈ Z: a = a is always true.
⇒ (a, a) ∈ R for all a. Reflexive!

2. Symmetric
If a = b, then b = a.
⇒ (a, b) ∈ R ⇒ (b, a) ∈ R. Symmetric!

3. Transitive
If a = b and b = c, then a = c.
⇒ (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R. Transitive!

Solution
Since “=” satisfies Reflexive + Symmetric + Transitive, it is an equivalence relation on Z. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 11 / 29
 B-Q16 — “Is Equal To” is an Equivalence Relation
Question
Show that “is equal to” (=) is an equivalence relation on Z. [3–4 marks]

Let R = {(a, b) ∈ Z × Z | a = b}.

1. Reflexive
For any a ∈ Z: a = a is always true.
⇒ (a, a) ∈ R for all a. Reflexive!

2. Symmetric
If a = b, then b = a.
⇒ (a, b) ∈ R ⇒ (b, a) ∈ R. Symmetric!

3. Transitive
If a = b and b = c, then a = c.
⇒ (a, b), (b, c) ∈ R ⇒ (a, c) ∈ R. Transitive!

Solution
Since “=” satisfies Reflexive + Symmetric + Transitive, it is an equivalence relation on Z. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 11 / 29
 B-Q17 — “≤” is a Partial Order on N
Question
Show that “≤” on natural numbers is a partial order relation. [3–4 marks]

Let R = {(a, b) ∈ N × N | a ≤ b}.

1. Reflexive
a ≤ a for all a ∈ N. Reflexive!

2. Anti-symmetric
If a ≤ b and b ≤ a, then a = b. Anti-symmetric!
Note: This is not symmetric – 2 ≤ 3 but 3 ̸≤ 2.

3. Transitive
If a ≤ b and b ≤ c, then a ≤ c. Transitive!

Solution
Since “≤” is reflexive, anti-symmetric, and transitive, (N, ≤) is a partially ordered set (poset).
□

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 12 / 29
 B-Q17 — “≤” is a Partial Order on N
Question
Show that “≤” on natural numbers is a partial order relation. [3–4 marks]

Let R = {(a, b) ∈ N × N | a ≤ b}.

1. Reflexive
a ≤ a for all a ∈ N. Reflexive!

2. Anti-symmetric
If a ≤ b and b ≤ a, then a = b. Anti-symmetric!
Note: This is not symmetric – 2 ≤ 3 but 3 ̸≤ 2.

3. Transitive
If a ≤ b and b ≤ c, then a ≤ c. Transitive!

Solution
Since “≤” is reflexive, anti-symmetric, and transitive, (N, ≤) is a partially ordered set (poset).
□

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 12 / 29
 B-Q17 — “≤” is a Partial Order on N
Question
Show that “≤” on natural numbers is a partial order relation. [3–4 marks]

Let R = {(a, b) ∈ N × N | a ≤ b}.

1. Reflexive
a ≤ a for all a ∈ N. Reflexive!

2. Anti-symmetric
If a ≤ b and b ≤ a, then a = b. Anti-symmetric!
Note: This is not symmetric – 2 ≤ 3 but 3 ̸≤ 2.

3. Transitive
If a ≤ b and b ≤ c, then a ≤ c. Transitive!

Solution
Since “≤” is reflexive, anti-symmetric, and transitive, (N, ≤) is a partially ordered set (poset).
□

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 12 / 29
 B-Q17 — “≤” is a Partial Order on N
Question
Show that “≤” on natural numbers is a partial order relation. [3–4 marks]

Let R = {(a, b) ∈ N × N | a ≤ b}.

1. Reflexive
a ≤ a for all a ∈ N. Reflexive!

2. Anti-symmetric
If a ≤ b and b ≤ a, then a = b. Anti-symmetric!
Note: This is not symmetric – 2 ≤ 3 but 3 ̸≤ 2.

3. Transitive
If a ≤ b and b ≤ c, then a ≤ c. Transitive!

Solution
Since “≤” is reflexive, anti-symmetric, and transitive, (N, ≤) is a partially ordered set (poset).
□

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 12 / 29
 B-Q17 — “≤” is a Partial Order on N
Question
Show that “≤” on natural numbers is a partial order relation. [3–4 marks]

Let R = {(a, b) ∈ N × N | a ≤ b}.

1. Reflexive
a ≤ a for all a ∈ N. Reflexive!

2. Anti-symmetric
If a ≤ b and b ≤ a, then a = b. Anti-symmetric!
Note: This is not symmetric – 2 ≤ 3 but 3 ̸≤ 2.

3. Transitive
If a ≤ b and b ≤ c, then a ≤ c. Transitive!

Solution
Since “≤” is reflexive, anti-symmetric, and transitive, (N, ≤) is a partially ordered set (poset).
□

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 12 / 29
 B-Q17 — “≤” is a Partial Order on N
Question
Show that “≤” on natural numbers is a partial order relation. [3–4 marks]

Let R = {(a, b) ∈ N × N | a ≤ b}.

1. Reflexive
a ≤ a for all a ∈ N. Reflexive!

2. Anti-symmetric
If a ≤ b and b ≤ a, then a = b. Anti-symmetric!
Note: This is not symmetric – 2 ≤ 3 but 3 ̸≤ 2.

3. Transitive
If a ≤ b and b ≤ c, then a ≤ c. Transitive!

Solution
Since “≤” is reflexive, anti-symmetric, and transitive, (N, ≤) is a partially ordered set (poset).
□

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 12 / 29
 B-Q17 — “≤” is a Partial Order on N
Question
Show that “≤” on natural numbers is a partial order relation. [3–4 marks]

Let R = {(a, b) ∈ N × N | a ≤ b}.

1. Reflexive
a ≤ a for all a ∈ N. Reflexive!

2. Anti-symmetric
If a ≤ b and b ≤ a, then a = b. Anti-symmetric!
Note: This is not symmetric – 2 ≤ 3 but 3 ̸≤ 2.

3. Transitive
If a ≤ b and b ≤ c, then a ≤ c. Transitive!

Solution
Since “≤” is reflexive, anti-symmetric, and transitive, (N, ≤) is a partially ordered set (poset).
□

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 12 / 29
 B-Q17 — “≤” is a Partial Order on N
Question
Show that “≤” on natural numbers is a partial order relation. [3–4 marks]

Let R = {(a, b) ∈ N × N | a ≤ b}.

1. Reflexive
a ≤ a for all a ∈ N. Reflexive!

2. Anti-symmetric
If a ≤ b and b ≤ a, then a = b. Anti-symmetric!
Note: This is not symmetric – 2 ≤ 3 but 3 ̸≤ 2.

3. Transitive
If a ≤ b and b ≤ c, then a ≤ c. Transitive!

Solution
Since “≤” is reflexive, anti-symmetric, and transitive, (N, ≤) is a partially ordered set (poset).
□

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 12 / 29
 B-Q17 — “≤” is a Partial Order on N
Question
Show that “≤” on natural numbers is a partial order relation. [3–4 marks]

Let R = {(a, b) ∈ N × N | a ≤ b}.

1. Reflexive
a ≤ a for all a ∈ N. Reflexive!

2. Anti-symmetric
If a ≤ b and b ≤ a, then a = b. Anti-symmetric!
Note: This is not symmetric – 2 ≤ 3 but 3 ̸≤ 2.

3. Transitive
If a ≤ b and b ≤ c, then a ≤ c. Transitive!

Solution
Since “≤” is reflexive, anti-symmetric, and transitive, (N, ≤) is a partially ordered set (poset).
□

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 12 / 29
 B-Q18 — Digraph Representation

Question
Represent R = {(1, 2), (2, 3), (3, 1)} on A = {1, 2, 3} using a digraph. [3–4 marks]

Procedure: (i) Draw one node per element of A. (ii) Draw a directed arrow for each ordered pair
in R.

1 Reading the Digraph

3 nodes: one for each element of A.
(1, 2) ∈ R ⇒ arrow 1 → 2.
(2, 3) ∈ R ⇒ arrow 2 → 3.
(3, 1) ∈ R ⇒ arrow 3 → 1.
2 3
No loops (no reflexive pairs).

Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 13 / 29
 B-Q18 — Digraph Representation

Question
Represent R = {(1, 2), (2, 3), (3, 1)} on A = {1, 2, 3} using a digraph. [3–4 marks]

Procedure: (i) Draw one node per element of A. (ii) Draw a directed arrow for each ordered pair
in R.

1 Reading the Digraph

3 nodes: one for each element of A.
(1, 2) ∈ R ⇒ arrow 1 → 2.
(2, 3) ∈ R ⇒ arrow 2 → 3.
(3, 1) ∈ R ⇒ arrow 3 → 1.
2 3
No loops (no reflexive pairs).

Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 13 / 29
 B-Q18 — Digraph Representation

Question
Represent R = {(1, 2), (2, 3), (3, 1)} on A = {1, 2, 3} using a digraph. [3–4 marks]

Procedure: (i) Draw one node per element of A. (ii) Draw a directed arrow for each ordered pair
in R.

1 Reading the Digraph

3 nodes: one for each element of A.
(1, 2) ∈ R ⇒ arrow 1 → 2.
(2, 3) ∈ R ⇒ arrow 2 → 3.
(3, 1) ∈ R ⇒ arrow 3 → 1.
2 3
No loops (no reflexive pairs).

Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 13 / 29
 B-Q18 — Digraph Representation

Question
Represent R = {(1, 2), (2, 3), (3, 1)} on A = {1, 2, 3} using a digraph. [3–4 marks]

Procedure: (i) Draw one node per element of A. (ii) Draw a directed arrow for each ordered pair
in R.

1 Reading the Digraph

3 nodes: one for each element of A.
(1, 2) ∈ R ⇒ arrow 1 → 2.
(2, 3) ∈ R ⇒ arrow 2 → 3.
(3, 1) ∈ R ⇒ arrow 3 → 1.
2 3
No loops (no reflexive pairs).

Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 13 / 29
 B-Q18 — Digraph Representation

Question
Represent R = {(1, 2), (2, 3), (3, 1)} on A = {1, 2, 3} using a digraph. [3–4 marks]

Procedure: (i) Draw one node per element of A. (ii) Draw a directed arrow for each ordered pair
in R.

1 Reading the Digraph

3 nodes: one for each element of A.
(1, 2) ∈ R ⇒ arrow 1 → 2.
(2, 3) ∈ R ⇒ arrow 2 → 3.
(3, 1) ∈ R ⇒ arrow 3 → 1.
2 3
No loops (no reflexive pairs).

Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 13 / 29
 B-Q18 — Digraph Representation

Question
Represent R = {(1, 2), (2, 3), (3, 1)} on A = {1, 2, 3} using a digraph. [3–4 marks]

Procedure: (i) Draw one node per element of A. (ii) Draw a directed arrow for each ordered pair
in R.

1 Reading the Digraph

3 nodes: one for each element of A.
(1, 2) ∈ R ⇒ arrow 1 → 2.
(2, 3) ∈ R ⇒ arrow 2 → 3.
(3, 1) ∈ R ⇒ arrow 3 → 1.
2 3
No loops (no reflexive pairs).

Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 13 / 29
 B-Q18 — Digraph Representation

Question
Represent R = {(1, 2), (2, 3), (3, 1)} on A = {1, 2, 3} using a digraph. [3–4 marks]

Procedure: (i) Draw one node per element of A. (ii) Draw a directed arrow for each ordered pair
in R.

1 Reading the Digraph

3 nodes: one for each element of A.
(1, 2) ∈ R ⇒ arrow 1 → 2.
(2, 3) ∈ R ⇒ arrow 2 → 3.
(3, 1) ∈ R ⇒ arrow 3 → 1.
2 3
No loops (no reflexive pairs).

Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 13 / 29
 B-Q18 — Digraph Representation

Question
Represent R = {(1, 2), (2, 3), (3, 1)} on A = {1, 2, 3} using a digraph. [3–4 marks]

Procedure: (i) Draw one node per element of A. (ii) Draw a directed arrow for each ordered pair
in R.

1 Reading the Digraph

3 nodes: one for each element of A.
(1, 2) ∈ R ⇒ arrow 1 → 2.
(2, 3) ∈ R ⇒ arrow 2 → 3.
(3, 1) ∈ R ⇒ arrow 3 → 1.
2 3
No loops (no reflexive pairs).

Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 13 / 29
 B-Q18 — Digraph Representation

Question
Represent R = {(1, 2), (2, 3), (3, 1)} on A = {1, 2, 3} using a digraph. [3–4 marks]

Procedure: (i) Draw one node per element of A. (ii) Draw a directed arrow for each ordered pair
in R.

1 Reading the Digraph

3 nodes: one for each element of A.
(1, 2) ∈ R ⇒ arrow 1 → 2.
(2, 3) ∈ R ⇒ arrow 2 → 3.
(3, 1) ∈ R ⇒ arrow 3 → 1.
2 3
No loops (no reflexive pairs).

Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 13 / 29
 B-Q19 — Matrix Representation

Question
Represent R = {(1, 1), (2, 2), (1, 2)} on A = {1, 2} using a matrix. [3–4 marks]

Method: Build MR – rows and columns correspond to elements of A.

Set MR [i][j] = 1 if (i, j) ∈ R, otherwise MR [i][j] = 0.

Step 1 – Fill the Table Step 2 – Read Properties

Reflexive?
1 2
All diagonal entries = 1?
1 1 1 MR [1][1] = 1, MR [2][2] = 1. ✓
2 0 1 Symmetric?
Is MR = ⊤
   MR ?
1 1
MR =
0 1 MR⊤ =
1 0
1 1
̸= MR . Ö
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations &(1, 2) ∈
Functions R but (2, 1) ∈
/ R. 14 / 29
 B-Q19 — Matrix Representation

Question
Represent R = {(1, 1), (2, 2), (1, 2)} on A = {1, 2} using a matrix. [3–4 marks]

Method: Build MR – rows and columns correspond to elements of A.

Set MR [i][j] = 1 if (i, j) ∈ R, otherwise MR [i][j] = 0.

Step 1 – Fill the Table Step 2 – Read Properties

Reflexive?
1 2
All diagonal entries = 1?
1 1 1 MR [1][1] = 1, MR [2][2] = 1. ✓
2 0 1 Symmetric?
Is MR = ⊤
   MR ?
1 1
MR =
0 1 MR⊤ =
1 0
1 1
̸= MR . Ö
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations &(1, 2) ∈
Functions R but (2, 1) ∈
/ R. 14 / 29
 B-Q19 — Matrix Representation

Question
Represent R = {(1, 1), (2, 2), (1, 2)} on A = {1, 2} using a matrix. [3–4 marks]

Method: Build MR – rows and columns correspond to elements of A.

Set MR [i][j] = 1 if (i, j) ∈ R, otherwise MR [i][j] = 0.

Step 1 – Fill the Table Step 2 – Read Properties

Reflexive?
1 2
All diagonal entries = 1?
1 1 1 MR [1][1] = 1, MR [2][2] = 1. ✓
2 0 1 Symmetric?
Is MR = ⊤
   MR ?
1 1
MR =
0 1 MR⊤ =
1 0
1 1
̸= MR . Ö
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations &(1, 2) ∈
Functions R but (2, 1) ∈
/ R. 14 / 29
 B-Q19 — Matrix Representation

Question
Represent R = {(1, 1), (2, 2), (1, 2)} on A = {1, 2} using a matrix. [3–4 marks]

Method: Build MR – rows and columns correspond to elements of A.

Set MR [i][j] = 1 if (i, j) ∈ R, otherwise MR [i][j] = 0.

Step 1 – Fill the Table Step 2 – Read Properties

Reflexive?
1 2
All diagonal entries = 1?
1 1 1 MR [1][1] = 1, MR [2][2] = 1. ✓
2 0 1 Symmetric?
Is MR = ⊤
   MR ?
1 1
MR =
0 1 MR⊤ =
1 0
1 1
̸= MR . Ö
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations &(1, 2) ∈
Functions R but (2, 1) ∈
/ R. 14 / 29
 B-Q19 — Matrix Representation

Question
Represent R = {(1, 1), (2, 2), (1, 2)} on A = {1, 2} using a matrix. [3–4 marks]

Method: Build MR – rows and columns correspond to elements of A.

Set MR [i][j] = 1 if (i, j) ∈ R, otherwise MR [i][j] = 0.

Step 1 – Fill the Table Step 2 – Read Properties

Reflexive?
1 2
All diagonal entries = 1?
1 1 1 MR [1][1] = 1, MR [2][2] = 1. ✓
2 0 1 Symmetric?
Is MR = ⊤
   MR ?
1 1
MR =
0 1 MR⊤ =
1 0
1 1
̸= MR . Ö
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations &(1, 2) ∈
Functions R but (2, 1) ∈
/ R. 14 / 29
 B-Q19 — Matrix Representation

Question
Represent R = {(1, 1), (2, 2), (1, 2)} on A = {1, 2} using a matrix. [3–4 marks]

Method: Build MR – rows and columns correspond to elements of A.

Set MR [i][j] = 1 if (i, j) ∈ R, otherwise MR [i][j] = 0.

Step 1 – Fill the Table Step 2 – Read Properties

Reflexive?
1 2
All diagonal entries = 1?
1 1 1 MR [1][1] = 1, MR [2][2] = 1. ✓
2 0 1 Symmetric?
Is MR = ⊤
   MR ?
1 1
MR =
0 1 MR⊤ =
1 0
1 1
̸= MR . Ö
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations &(1, 2) ∈
Functions R but (2, 1) ∈
/ R. 14 / 29
 B-Q19 — Matrix Representation

Question
Represent R = {(1, 1), (2, 2), (1, 2)} on A = {1, 2} using a matrix. [3–4 marks]

Method: Build MR – rows and columns correspond to elements of A.

Set MR [i][j] = 1 if (i, j) ∈ R, otherwise MR [i][j] = 0.

Step 1 – Fill the Table Step 2 – Read Properties

Reflexive?
1 2
All diagonal entries = 1?
1 1 1 MR [1][1] = 1, MR [2][2] = 1. ✓
2 0 1 Symmetric?
Is MR = ⊤
   MR ?
1 1
MR =
0 1 MR⊤ =
1 0
1 1
̸= MR . Ö
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations &(1, 2) ∈
Functions R but (2, 1) ∈
/ R. 14 / 29
 B-Q19 — Matrix Representation

Question
Represent R = {(1, 1), (2, 2), (1, 2)} on A = {1, 2} using a matrix. [3–4 marks]

Method: Build MR – rows and columns correspond to elements of A.

Set MR [i][j] = 1 if (i, j) ∈ R, otherwise MR [i][j] = 0.

Step 1 – Fill the Table Step 2 – Read Properties

Reflexive?
1 2
All diagonal entries = 1?
1 1 1 MR [1][1] = 1, MR [2][2] = 1. ✓
2 0 1 Symmetric?
Is MR = ⊤
   MR ?
1 1
MR =
0 1 MR⊤ =
1 0
1 1
̸= MR . Ö
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations &(1, 2) ∈
Functions R but (2, 1) ∈
/ R. 14 / 29
 B-Q20 — Bijective Function

Question
Define bijective function with an example. [3–4 marks]

Solution
f : A → B is bijective (one-to-one correspondence) if it is both injective (one-to-one) and
surjective (onto).
Injective: Distinct inputs always give distinct outputs.
Surjective: Every element of B is reached by some element of A.
Consequence: |A| = |B| (sets have the same cardinality).

Example Key Idea

f : {1, 2, 3} → {a, b, c} Why bijection matters:
f (1) = a, f (2) = b, f (3) = c Only bijective f has an inverse f −1 . 15 / 29
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions
 B-Q20 — Bijective Function

Question
Define bijective function with an example. [3–4 marks]

Solution
f : A → B is bijective (one-to-one correspondence) if it is both injective (one-to-one) and
surjective (onto).
Injective: Distinct inputs always give distinct outputs.
Surjective: Every element of B is reached by some element of A.
Consequence: |A| = |B| (sets have the same cardinality).

Example Key Idea

f : {1, 2, 3} → {a, b, c} Why bijection matters:
f (1) = a, f (2) = b, f (3) = c Only bijective f has an inverse f −1 . 15 / 29
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions
 B-Q20 — Bijective Function

Question
Define bijective function with an example. [3–4 marks]

Solution
f : A → B is bijective (one-to-one correspondence) if it is both injective (one-to-one) and
surjective (onto).
Injective: Distinct inputs always give distinct outputs.
Surjective: Every element of B is reached by some element of A.
Consequence: |A| = |B| (sets have the same cardinality).

Example Key Idea

f : {1, 2, 3} → {a, b, c} Why bijection matters:
f (1) = a, f (2) = b, f (3) = c Only bijective f has an inverse f −1 . 15 / 29
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions
 B-Q20 — Bijective Function

Question
Define bijective function with an example. [3–4 marks]

Solution
f : A → B is bijective (one-to-one correspondence) if it is both injective (one-to-one) and
surjective (onto).
Injective: Distinct inputs always give distinct outputs.
Surjective: Every element of B is reached by some element of A.
Consequence: |A| = |B| (sets have the same cardinality).

Example Key Idea

f : {1, 2, 3} → {a, b, c} Why bijection matters:
f (1) = a, f (2) = b, f (3) = c Only bijective f has an inverse f −1 . 15 / 29
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions
 B-Q20 — Bijective Function

Question
Define bijective function with an example. [3–4 marks]

Solution
f : A → B is bijective (one-to-one correspondence) if it is both injective (one-to-one) and
surjective (onto).
Injective: Distinct inputs always give distinct outputs.
Surjective: Every element of B is reached by some element of A.
Consequence: |A| = |B| (sets have the same cardinality).

Example Key Idea

f : {1, 2, 3} → {a, b, c} Why bijection matters:
f (1) = a, f (2) = b, f (3) = c Only bijective f has an inverse f −1 . 15 / 29
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions
 B-Q20 — Bijective Function

Question
Define bijective function with an example. [3–4 marks]

Solution
f : A → B is bijective (one-to-one correspondence) if it is both injective (one-to-one) and
surjective (onto).
Injective: Distinct inputs always give distinct outputs.
Surjective: Every element of B is reached by some element of A.
Consequence: |A| = |B| (sets have the same cardinality).

Example Key Idea

f : {1, 2, 3} → {a, b, c} Why bijection matters:
f (1) = a, f (2) = b, f (3) = c Only bijective f has an inverse f −1 . 15 / 29
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions
 B-Q20 — Bijective Function

Question
Define bijective function with an example. [3–4 marks]

Solution
f : A → B is bijective (one-to-one correspondence) if it is both injective (one-to-one) and
surjective (onto).
Injective: Distinct inputs always give distinct outputs.
Surjective: Every element of B is reached by some element of A.
Consequence: |A| = |B| (sets have the same cardinality).

Example Key Idea

f : {1, 2, 3} → {a, b, c} Why bijection matters:
f (1) = a, f (2) = b, f (3) = c Only bijective f has an inverse f −1 . 15 / 29
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions
 B-Q20 — Bijective Function

Question
Define bijective function with an example. [3–4 marks]

Solution
f : A → B is bijective (one-to-one correspondence) if it is both injective (one-to-one) and
surjective (onto).
Injective: Distinct inputs always give distinct outputs.
Surjective: Every element of B is reached by some element of A.
Consequence: |A| = |B| (sets have the same cardinality).

Example Key Idea

f : {1, 2, 3} → {a, b, c} Why bijection matters:
f (1) = a, f (2) = b, f (3) = c Only bijective f has an inverse f −1 . 15 / 29
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions
 B-Q21 — Composite Function (g ◦ f )(x)
Question
If f (x) = 2x + 1 and g (x) = x 2 , find (g ◦ f )(x). [3–4 marks]

Solution
Definition: (g ◦ f )(x) = g (f (x)) (Apply f first, then apply g to the result.)
Step 1 – Compute f (x):
f (x) = 2x + 1
Step 2 – Apply g to f (x):

(g ◦ f )(x) = g (f (x)) = g (2x + 1) = (2x + 1)2

Step 3 – Expand:
(g ◦ f )(x) = 4x 2 + 4x + 1

Key Idea
Warning – order matters!
(f ◦ g )(x) = f (g (x)) = f (x 2 ) = 2x 2 + 1 ̸= 4x 2 + 4x + 1.
In general, g ◦ f ̸= f ◦ g .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 16 / 29
 B-Q21 — Composite Function (g ◦ f )(x)
Question
If f (x) = 2x + 1 and g (x) = x 2 , find (g ◦ f )(x). [3–4 marks]

Solution
Definition: (g ◦ f )(x) = g (f (x)) (Apply f first, then apply g to the result.)
Step 1 – Compute f (x):
f (x) = 2x + 1
Step 2 – Apply g to f (x):

(g ◦ f )(x) = g (f (x)) = g (2x + 1) = (2x + 1)2

Step 3 – Expand:
(g ◦ f )(x) = 4x 2 + 4x + 1

Key Idea
Warning – order matters!
(f ◦ g )(x) = f (g (x)) = f (x 2 ) = 2x 2 + 1 ̸= 4x 2 + 4x + 1.
In general, g ◦ f ̸= f ◦ g .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 16 / 29
 B-Q21 — Composite Function (g ◦ f )(x)
Question
If f (x) = 2x + 1 and g (x) = x 2 , find (g ◦ f )(x). [3–4 marks]

Solution
Definition: (g ◦ f )(x) = g (f (x)) (Apply f first, then apply g to the result.)
Step 1 – Compute f (x):
f (x) = 2x + 1
Step 2 – Apply g to f (x):

(g ◦ f )(x) = g (f (x)) = g (2x + 1) = (2x + 1)2

Step 3 – Expand:
(g ◦ f )(x) = 4x 2 + 4x + 1

Key Idea
Warning – order matters!
(f ◦ g )(x) = f (g (x)) = f (x 2 ) = 2x 2 + 1 ̸= 4x 2 + 4x + 1.
In general, g ◦ f ̸= f ◦ g .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 16 / 29
 B-Q21 — Composite Function (g ◦ f )(x)
Question
If f (x) = 2x + 1 and g (x) = x 2 , find (g ◦ f )(x). [3–4 marks]

Solution
Definition: (g ◦ f )(x) = g (f (x)) (Apply f first, then apply g to the result.)
Step 1 – Compute f (x):
f (x) = 2x + 1
Step 2 – Apply g to f (x):

(g ◦ f )(x) = g (f (x)) = g (2x + 1) = (2x + 1)2

Step 3 – Expand:
(g ◦ f )(x) = 4x 2 + 4x + 1

Key Idea
Warning – order matters!
(f ◦ g )(x) = f (g (x)) = f (x 2 ) = 2x 2 + 1 ̸= 4x 2 + 4x + 1.
In general, g ◦ f ̸= f ◦ g .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 16 / 29
 B-Q21 — Composite Function (g ◦ f )(x)
Question
If f (x) = 2x + 1 and g (x) = x 2 , find (g ◦ f )(x). [3–4 marks]

Solution
Definition: (g ◦ f )(x) = g (f (x)) (Apply f first, then apply g to the result.)
Step 1 – Compute f (x):
f (x) = 2x + 1
Step 2 – Apply g to f (x):

(g ◦ f )(x) = g (f (x)) = g (2x + 1) = (2x + 1)2

Step 3 – Expand:
(g ◦ f )(x) = 4x 2 + 4x + 1

Key Idea
Warning – order matters!
(f ◦ g )(x) = f (g (x)) = f (x 2 ) = 2x 2 + 1 ̸= 4x 2 + 4x + 1.
In general, g ◦ f ̸= f ◦ g .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 16 / 29
 B-Q21 — Composite Function (g ◦ f )(x)
Question
If f (x) = 2x + 1 and g (x) = x 2 , find (g ◦ f )(x). [3–4 marks]

Solution
Definition: (g ◦ f )(x) = g (f (x)) (Apply f first, then apply g to the result.)
Step 1 – Compute f (x):
f (x) = 2x + 1
Step 2 – Apply g to f (x):

(g ◦ f )(x) = g (f (x)) = g (2x + 1) = (2x + 1)2

Step 3 – Expand:
(g ◦ f )(x) = 4x 2 + 4x + 1

Key Idea
Warning – order matters!
(f ◦ g )(x) = f (g (x)) = f (x 2 ) = 2x 2 + 1 ̸= 4x 2 + 4x + 1.
In general, g ◦ f ̸= f ◦ g .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 16 / 29
 B-Q22 & B-Q23 — Composite & Inverse Functions

Q22: Composite Function Q23: Inverse Function

Define composite function with example. Define inverse function with example.

Solution Solution
If f : A → B and g : B → C , the composite If f : A → B is bijective, its inverse f −1 : B →
(g ◦ f ) : A → C is defined as: A satisfies:

(g ◦ f )(x) = g (f (x)) f −1 (f (x)) = x and f (f −1 (y )) = y

Example: Example: f (x) = 3x + 2

f (x) = x + 1, g (x) = 3x y −2
Set y = 3x + 2, solve: x =
(g ◦ f )(x) = g (x + 1) = 3(x + 1) = 3x + 3 3
y −2
f −1 (y ) =
3

Key Idea
Only bijective functions have inverses. f −1 “undoes” f : (f −1 ◦ f )(x) = x (identity function).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 17 / 29
 B-Q22 & B-Q23 — Composite & Inverse Functions

Q22: Composite Function Q23: Inverse Function

Define composite function with example. Define inverse function with example.

Solution Solution
If f : A → B and g : B → C , the composite If f : A → B is bijective, its inverse f −1 : B →
(g ◦ f ) : A → C is defined as: A satisfies:

(g ◦ f )(x) = g (f (x)) f −1 (f (x)) = x and f (f −1 (y )) = y

Example: Example: f (x) = 3x + 2

f (x) = x + 1, g (x) = 3x y −2
Set y = 3x + 2, solve: x =
(g ◦ f )(x) = g (x + 1) = 3(x + 1) = 3x + 3 3
y −2
f −1 (y ) =
3

Key Idea
Only bijective functions have inverses. f −1 “undoes” f : (f −1 ◦ f )(x) = x (identity function).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 17 / 29
 B-Q22 & B-Q23 — Composite & Inverse Functions

Q22: Composite Function Q23: Inverse Function

Define composite function with example. Define inverse function with example.

Solution Solution
If f : A → B and g : B → C , the composite If f : A → B is bijective, its inverse f −1 : B →
(g ◦ f ) : A → C is defined as: A satisfies:

(g ◦ f )(x) = g (f (x)) f −1 (f (x)) = x and f (f −1 (y )) = y

Example: Example: f (x) = 3x + 2

f (x) = x + 1, g (x) = 3x y −2
Set y = 3x + 2, solve: x =
(g ◦ f )(x) = g (x + 1) = 3(x + 1) = 3x + 3 3
y −2
f −1 (y ) =
3

Key Idea
Only bijective functions have inverses. f −1 “undoes” f : (f −1 ◦ f )(x) = x (identity function).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 17 / 29
 B-Q22 & B-Q23 — Composite & Inverse Functions

Q22: Composite Function Q23: Inverse Function

Define composite function with example. Define inverse function with example.

Solution Solution
If f : A → B and g : B → C , the composite If f : A → B is bijective, its inverse f −1 : B →
(g ◦ f ) : A → C is defined as: A satisfies:

(g ◦ f )(x) = g (f (x)) f −1 (f (x)) = x and f (f −1 (y )) = y

Example: Example: f (x) = 3x + 2

f (x) = x + 1, g (x) = 3x y −2
Set y = 3x + 2, solve: x =
(g ◦ f )(x) = g (x + 1) = 3(x + 1) = 3x + 3 3
y −2
f −1 (y ) =
3

Key Idea
Only bijective functions have inverses. f −1 “undoes” f : (f −1 ◦ f )(x) = x (identity function).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 17 / 29
 B-Q22 & B-Q23 — Composite & Inverse Functions

Q22: Composite Function Q23: Inverse Function

Define composite function with example. Define inverse function with example.

Solution Solution
If f : A → B and g : B → C , the composite If f : A → B is bijective, its inverse f −1 : B →
(g ◦ f ) : A → C is defined as: A satisfies:

(g ◦ f )(x) = g (f (x)) f −1 (f (x)) = x and f (f −1 (y )) = y

Example: Example: f (x) = 3x + 2

f (x) = x + 1, g (x) = 3x y −2
Set y = 3x + 2, solve: x =
(g ◦ f )(x) = g (x + 1) = 3(x + 1) = 3x + 3 3
y −2
f −1 (y ) =
3

Key Idea
Only bijective functions have inverses. f −1 “undoes” f : (f −1 ◦ f )(x) = x (identity function).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 17 / 29
 B-Q22 & B-Q23 — Composite & Inverse Functions

Q22: Composite Function Q23: Inverse Function

Define composite function with example. Define inverse function with example.

Solution Solution
If f : A → B and g : B → C , the composite If f : A → B is bijective, its inverse f −1 : B →
(g ◦ f ) : A → C is defined as: A satisfies:

(g ◦ f )(x) = g (f (x)) f −1 (f (x)) = x and f (f −1 (y )) = y

Example: Example: f (x) = 3x + 2

f (x) = x + 1, g (x) = 3x y −2
Set y = 3x + 2, solve: x =
(g ◦ f )(x) = g (x + 1) = 3(x + 1) = 3x + 3 3
y −2
f −1 (y ) =
3

Key Idea
Only bijective functions have inverses. f −1 “undoes” f : (f −1 ◦ f )(x) = x (identity function).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 17 / 29
 B-Q22 & B-Q23 — Composite & Inverse Functions

Q22: Composite Function Q23: Inverse Function

Define composite function with example. Define inverse function with example.

Solution Solution
If f : A → B and g : B → C , the composite If f : A → B is bijective, its inverse f −1 : B →
(g ◦ f ) : A → C is defined as: A satisfies:

(g ◦ f )(x) = g (f (x)) f −1 (f (x)) = x and f (f −1 (y )) = y

Example: Example: f (x) = 3x + 2

f (x) = x + 1, g (x) = 3x y −2
Set y = 3x + 2, solve: x =
(g ◦ f )(x) = g (x + 1) = 3(x + 1) = 3x + 3 3
y −2
f −1 (y ) =
3

Key Idea
Only bijective functions have inverses. f −1 “undoes” f : (f −1 ◦ f )(x) = x (identity function).

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 17 / 29
 C-Q15 — Congruence Modulo m is Equivalence [1/2]
Question
Prove that congruence modulo m is an equivalence relation on Z. [5–6 marks]

Definition
a ≡ b (mod m) if and only if m | (a − b),
i.e., a − b = km for some integer k.

1. Reflexive – Show a ≡ a (mod m)

a − a = 0 = 0 · m, so m | (a − a).
∴ a ≡ a (mod m) for all a ∈ Z. Reflexive!

2. Symmetric – If a ≡ b, show b ≡ a
If a ≡ b (mod m), then a − b = km for some k ∈ Z.
Then b − a = −(a − b) = (−k)m, so m | (b − a).
∴ b ≡ a (mod m). Symmetric!

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 18 / 29
 C-Q15 — Congruence Modulo m is Equivalence [1/2]
Question
Prove that congruence modulo m is an equivalence relation on Z. [5–6 marks]

Definition
a ≡ b (mod m) if and only if m | (a − b),
i.e., a − b = km for some integer k.

1. Reflexive – Show a ≡ a (mod m)

a − a = 0 = 0 · m, so m | (a − a).
∴ a ≡ a (mod m) for all a ∈ Z. Reflexive!

2. Symmetric – If a ≡ b, show b ≡ a
If a ≡ b (mod m), then a − b = km for some k ∈ Z.
Then b − a = −(a − b) = (−k)m, so m | (b − a).
∴ b ≡ a (mod m). Symmetric!

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 18 / 29
 C-Q15 — Congruence Modulo m is Equivalence [1/2]
Question
Prove that congruence modulo m is an equivalence relation on Z. [5–6 marks]

Definition
a ≡ b (mod m) if and only if m | (a − b),
i.e., a − b = km for some integer k.

1. Reflexive – Show a ≡ a (mod m)

a − a = 0 = 0 · m, so m | (a − a).
∴ a ≡ a (mod m) for all a ∈ Z. Reflexive!

2. Symmetric – If a ≡ b, show b ≡ a
If a ≡ b (mod m), then a − b = km for some k ∈ Z.
Then b − a = −(a − b) = (−k)m, so m | (b − a).
∴ b ≡ a (mod m). Symmetric!

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 18 / 29
 C-Q15 — Congruence Modulo m is Equivalence [1/2]
Question
Prove that congruence modulo m is an equivalence relation on Z. [5–6 marks]

Definition
a ≡ b (mod m) if and only if m | (a − b),
i.e., a − b = km for some integer k.

1. Reflexive – Show a ≡ a (mod m)

a − a = 0 = 0 · m, so m | (a − a).
∴ a ≡ a (mod m) for all a ∈ Z. Reflexive!

2. Symmetric – If a ≡ b, show b ≡ a
If a ≡ b (mod m), then a − b = km for some k ∈ Z.
Then b − a = −(a − b) = (−k)m, so m | (b − a).
∴ b ≡ a (mod m). Symmetric!

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 18 / 29
 C-Q15 — Congruence Modulo m is Equivalence [1/2]
Question
Prove that congruence modulo m is an equivalence relation on Z. [5–6 marks]

Definition
a ≡ b (mod m) if and only if m | (a − b),
i.e., a − b = km for some integer k.

1. Reflexive – Show a ≡ a (mod m)

a − a = 0 = 0 · m, so m | (a − a).
∴ a ≡ a (mod m) for all a ∈ Z. Reflexive!

2. Symmetric – If a ≡ b, show b ≡ a
If a ≡ b (mod m), then a − b = km for some k ∈ Z.
Then b − a = −(a − b) = (−k)m, so m | (b − a).
∴ b ≡ a (mod m). Symmetric!

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 18 / 29
 C-Q15 — Congruence Modulo m is Equivalence [1/2]
Question
Prove that congruence modulo m is an equivalence relation on Z. [5–6 marks]

Definition
a ≡ b (mod m) if and only if m | (a − b),
i.e., a − b = km for some integer k.

1. Reflexive – Show a ≡ a (mod m)

a − a = 0 = 0 · m, so m | (a − a).
∴ a ≡ a (mod m) for all a ∈ Z. Reflexive!

2. Symmetric – If a ≡ b, show b ≡ a
If a ≡ b (mod m), then a − b = km for some k ∈ Z.
Then b − a = −(a − b) = (−k)m, so m | (b − a).
∴ b ≡ a (mod m). Symmetric!

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 18 / 29
 C-Q15 — Congruence Modulo m is Equivalence [2/2]
3. Transitive – If a ≡ b and b ≡ c, show a ≡ c
Suppose a ≡ b (mod m) and b ≡ c (mod m).
Then a − b = k1 m and b − c = k2 m for integers k1 , k2 .

a − c = (a − b) + (b − c) = k1 m + k2 m = (k1 + k2 ) m

So m | (a − c), giving a ≡ c (mod m). Transitive!

Solution
Congruence modulo m is reflexive, symmetric, and transitive – therefore it is an equivalence
relation on Z. □

Key Idea
Equivalence Classes (for m = 3):
[0] = {. . . , −6, −3, 0, 3, 6, . . .}
[1] = {. . . , −5, −2, 1, 4, 7, . . .}
[2] = {. . . , −4, −1, 2, 5, 8, . . .}

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 19 / 29
 C-Q15 — Congruence Modulo m is Equivalence [2/2]
3. Transitive – If a ≡ b and b ≡ c, show a ≡ c
Suppose a ≡ b (mod m) and b ≡ c (mod m).
Then a − b = k1 m and b − c = k2 m for integers k1 , k2 .

a − c = (a − b) + (b − c) = k1 m + k2 m = (k1 + k2 ) m

So m | (a − c), giving a ≡ c (mod m). Transitive!

Solution
Congruence modulo m is reflexive, symmetric, and transitive – therefore it is an equivalence
relation on Z. □

Key Idea
Equivalence Classes (for m = 3):
[0] = {. . . , −6, −3, 0, 3, 6, . . .}
[1] = {. . . , −5, −2, 1, 4, 7, . . .}
[2] = {. . . , −4, −1, 2, 5, 8, . . .}

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 19 / 29
 C-Q15 — Congruence Modulo m is Equivalence [2/2]
3. Transitive – If a ≡ b and b ≡ c, show a ≡ c
Suppose a ≡ b (mod m) and b ≡ c (mod m).
Then a − b = k1 m and b − c = k2 m for integers k1 , k2 .

a − c = (a − b) + (b − c) = k1 m + k2 m = (k1 + k2 ) m

So m | (a − c), giving a ≡ c (mod m). Transitive!

Solution
Congruence modulo m is reflexive, symmetric, and transitive – therefore it is an equivalence
relation on Z. □

Key Idea
Equivalence Classes (for m = 3):
[0] = {. . . , −6, −3, 0, 3, 6, . . .}
[1] = {. . . , −5, −2, 1, 4, 7, . . .}
[2] = {. . . , −4, −1, 2, 5, 8, . . .}

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 19 / 29
 C-Q15 — Congruence Modulo m is Equivalence [2/2]
3. Transitive – If a ≡ b and b ≡ c, show a ≡ c
Suppose a ≡ b (mod m) and b ≡ c (mod m).
Then a − b = k1 m and b − c = k2 m for integers k1 , k2 .

a − c = (a − b) + (b − c) = k1 m + k2 m = (k1 + k2 ) m

So m | (a − c), giving a ≡ c (mod m). Transitive!

Solution
Congruence modulo m is reflexive, symmetric, and transitive – therefore it is an equivalence
relation on Z. □

Key Idea
Equivalence Classes (for m = 3):
[0] = {. . . , −6, −3, 0, 3, 6, . . .}
[1] = {. . . , −5, −2, 1, 4, 7, . . .}
[2] = {. . . , −4, −1, 2, 5, 8, . . .}

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 19 / 29
 C-Q15 — Congruence Modulo m is Equivalence [2/2]
3. Transitive – If a ≡ b and b ≡ c, show a ≡ c
Suppose a ≡ b (mod m) and b ≡ c (mod m).
Then a − b = k1 m and b − c = k2 m for integers k1 , k2 .

a − c = (a − b) + (b − c) = k1 m + k2 m = (k1 + k2 ) m

So m | (a − c), giving a ≡ c (mod m). Transitive!

Solution
Congruence modulo m is reflexive, symmetric, and transitive – therefore it is an equivalence
relation on Z. □

Key Idea
Equivalence Classes (for m = 3):
[0] = {. . . , −6, −3, 0, 3, 6, . . .}
[1] = {. . . , −5, −2, 1, 4, 7, . . .}
[2] = {. . . , −4, −1, 2, 5, 8, . . .}

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 19 / 29
 C-Q17 — Digraph and Matrix for R = {(1, 2), (2, 3), (3, 1), (1, 3)}

Question
Represent R = {(1, 2), (2, 3), (3, 1), (1, 3)} on A = {1, 2, 3} using a digraph and a matrix. [5–6
marks]

(i) Digraph: (ii) Boolean Matrix MR :

Rows = from, Columns = to; 1 if pair ∈ R, else 0.
1

1 2 3
1 0 1 1
MR =
2 3 2 0 0 1
3 1 0 0
Blue arrows: cycle 1 → 2 → 3 → 1.
Orange arrow: extra edge (1, 3). Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 20 / 29
 C-Q17 — Digraph and Matrix for R = {(1, 2), (2, 3), (3, 1), (1, 3)}

Question
Represent R = {(1, 2), (2, 3), (3, 1), (1, 3)} on A = {1, 2, 3} using a digraph and a matrix. [5–6
marks]

(i) Digraph: (ii) Boolean Matrix MR :

Rows = from, Columns = to; 1 if pair ∈ R, else 0.
1

1 2 3
1 0 1 1
MR =
2 3 2 0 0 1
3 1 0 0
Blue arrows: cycle 1 → 2 → 3 → 1.
Orange arrow: extra edge (1, 3). Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 20 / 29
 C-Q17 — Digraph and Matrix for R = {(1, 2), (2, 3), (3, 1), (1, 3)}

Question
Represent R = {(1, 2), (2, 3), (3, 1), (1, 3)} on A = {1, 2, 3} using a digraph and a matrix. [5–6
marks]

(i) Digraph: (ii) Boolean Matrix MR :

Rows = from, Columns = to; 1 if pair ∈ R, else 0.
1

1 2 3
1 0 1 1
MR =
2 3 2 0 0 1
3 1 0 0
Blue arrows: cycle 1 → 2 → 3 → 1.
Orange arrow: extra edge (1, 3). Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 20 / 29
 C-Q17 — Digraph and Matrix for R = {(1, 2), (2, 3), (3, 1), (1, 3)}

Question
Represent R = {(1, 2), (2, 3), (3, 1), (1, 3)} on A = {1, 2, 3} using a digraph and a matrix. [5–6
marks]

(i) Digraph: (ii) Boolean Matrix MR :

Rows = from, Columns = to; 1 if pair ∈ R, else 0.
1

1 2 3
1 0 1 1
MR =
2 3 2 0 0 1
3 1 0 0
Blue arrows: cycle 1 → 2 → 3 → 1.
Orange arrow: extra edge (1, 3). Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 20 / 29
 C-Q17 — Digraph and Matrix for R = {(1, 2), (2, 3), (3, 1), (1, 3)}

Question
Represent R = {(1, 2), (2, 3), (3, 1), (1, 3)} on A = {1, 2, 3} using a digraph and a matrix. [5–6
marks]

(i) Digraph: (ii) Boolean Matrix MR :

Rows = from, Columns = to; 1 if pair ∈ R, else 0.
1

1 2 3
1 0 1 1
MR =
2 3 2 0 0 1
3 1 0 0
Blue arrows: cycle 1 → 2 → 3 → 1.
Orange arrow: extra edge (1, 3). Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 20 / 29
 C-Q17 — Digraph and Matrix for R = {(1, 2), (2, 3), (3, 1), (1, 3)}

Question
Represent R = {(1, 2), (2, 3), (3, 1), (1, 3)} on A = {1, 2, 3} using a digraph and a matrix. [5–6
marks]

(i) Digraph: (ii) Boolean Matrix MR :

Rows = from, Columns = to; 1 if pair ∈ R, else 0.
1

1 2 3
1 0 1 1
MR =
2 3 2 0 0 1
3 1 0 0
Blue arrows: cycle 1 → 2 → 3 → 1.
Orange arrow: extra edge (1, 3). Key Idea
Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 20 / 29
 C-Q19 — Finding the Inverse Function
Question
If f : R → R, f (x) = 3x + 2, find f −1 (x). [5 marks]

Solution
Method: Write y = f (x), solve for x, then rename y → x for the final formula.
Step 1 – Write y = f (x):
y = 3x + 2
Step 2 – Solve for x:

y − 2 = 3x
y −2
x=
3
Step 3 – Replace y with x (standard convention):

x −2
f −1 (x) =
3

x −2
Verify: f f −1 (x) = 3 ·


+ 2 = (x − 2) + 2 = x ✓
3

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 21 / 29
 C-Q19 — Finding the Inverse Function
Question
If f : R → R, f (x) = 3x + 2, find f −1 (x). [5 marks]

Solution
Method: Write y = f (x), solve for x, then rename y → x for the final formula.
Step 1 – Write y = f (x):
y = 3x + 2
Step 2 – Solve for x:

y − 2 = 3x
y −2
x=
3
Step 3 – Replace y with x (standard convention):

x −2
f −1 (x) =
3

x −2
Verify: f f −1 (x) = 3 ·


+ 2 = (x − 2) + 2 = x ✓
3

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 21 / 29
 C-Q19 — Finding the Inverse Function
Question
If f : R → R, f (x) = 3x + 2, find f −1 (x). [5 marks]

Solution
Method: Write y = f (x), solve for x, then rename y → x for the final formula.
Step 1 – Write y = f (x):
y = 3x + 2
Step 2 – Solve for x:

y − 2 = 3x
y −2
x=
3
Step 3 – Replace y with x (standard convention):

x −2
f −1 (x) =
3

x −2
Verify: f f −1 (x) = 3 ·


+ 2 = (x − 2) + 2 = x ✓
3

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 21 / 29
 C-Q19 — Finding the Inverse Function
Question
If f : R → R, f (x) = 3x + 2, find f −1 (x). [5 marks]

Solution
Method: Write y = f (x), solve for x, then rename y → x for the final formula.
Step 1 – Write y = f (x):
y = 3x + 2
Step 2 – Solve for x:

y − 2 = 3x
y −2
x=
3
Step 3 – Replace y with x (standard convention):

x −2
f −1 (x) =
3

x −2
Verify: f f −1 (x) = 3 ·


+ 2 = (x − 2) + 2 = x ✓
3

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 21 / 29
 C-Q19 — Finding the Inverse Function
Question
If f : R → R, f (x) = 3x + 2, find f −1 (x). [5 marks]

Solution
Method: Write y = f (x), solve for x, then rename y → x for the final formula.
Step 1 – Write y = f (x):
y = 3x + 2
Step 2 – Solve for x:

y − 2 = 3x
y −2
x=
3
Step 3 – Replace y with x (standard convention):

x −2
f −1 (x) =
3

x −2
Verify: f f −1 (x) = 3 ·


+ 2 = (x − 2) + 2 = x ✓
3

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 21 / 29
 C-Q19 — Finding the Inverse Function
Question
If f : R → R, f (x) = 3x + 2, find f −1 (x). [5 marks]

Solution
Method: Write y = f (x), solve for x, then rename y → x for the final formula.
Step 1 – Write y = f (x):
y = 3x + 2
Step 2 – Solve for x:

y − 2 = 3x
y −2
x=
3
Step 3 – Replace y with x (standard convention):

x −2
f −1 (x) =
3

x −2
Verify: f f −1 (x) = 3 ·


+ 2 = (x − 2) + 2 = x ✓
3

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 21 / 29
 C-Q20 — Composition – (g ◦ f )(x) and (f ◦ g )(x)
Question
√
If f (x) = x 2 and g (x) = x, find (g ◦ f )(x) and (f ◦ g )(x). [5 marks]

(g ◦ f )(x) = g (f (x)) (f ◦ g )(x) = f (g (x))

Apply f first, then g : Apply g first, then f :
2 √
(g ◦ f )(x) = g (f (x)) = g (x ) (f ◦ g )(x) = f (g (x)) = f ( x)
√ √ 2
= x 2 = |x| = ( x) = x

(g ◦ f )(x) = |x| (f ◦ g )(x) = x

Valid for all x ∈ R. Valid for x ≥ 0 (domain of g ).
E.g. g (f (−3)) = g (9) = 3 = | − 3|. E.g. f (g (4)) = f (2) = 4.

Key Idea
(f ◦ g )(x) = x means f and g are inverse functions (on [0, ∞))!
But (g ◦ f )(x) = |x| =
̸ x, confirming g ◦ f ̸= f ◦ g in general.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 22 / 29
 C-Q20 — Composition – (g ◦ f )(x) and (f ◦ g )(x)
Question
√
If f (x) = x 2 and g (x) = x, find (g ◦ f )(x) and (f ◦ g )(x). [5 marks]

(g ◦ f )(x) = g (f (x)) (f ◦ g )(x) = f (g (x))

Apply f first, then g : Apply g first, then f :
2 √
(g ◦ f )(x) = g (f (x)) = g (x ) (f ◦ g )(x) = f (g (x)) = f ( x)
√ √ 2
= x 2 = |x| = ( x) = x

(g ◦ f )(x) = |x| (f ◦ g )(x) = x

Valid for all x ∈ R. Valid for x ≥ 0 (domain of g ).
E.g. g (f (−3)) = g (9) = 3 = | − 3|. E.g. f (g (4)) = f (2) = 4.

Key Idea
(f ◦ g )(x) = x means f and g are inverse functions (on [0, ∞))!
But (g ◦ f )(x) = |x| =
̸ x, confirming g ◦ f ̸= f ◦ g in general.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 22 / 29
 C-Q20 — Composition – (g ◦ f )(x) and (f ◦ g )(x)
Question
√
If f (x) = x 2 and g (x) = x, find (g ◦ f )(x) and (f ◦ g )(x). [5 marks]

(g ◦ f )(x) = g (f (x)) (f ◦ g )(x) = f (g (x))

Apply f first, then g : Apply g first, then f :
2 √
(g ◦ f )(x) = g (f (x)) = g (x ) (f ◦ g )(x) = f (g (x)) = f ( x)
√ √ 2
= x 2 = |x| = ( x) = x

(g ◦ f )(x) = |x| (f ◦ g )(x) = x

Valid for all x ∈ R. Valid for x ≥ 0 (domain of g ).
E.g. g (f (−3)) = g (9) = 3 = | − 3|. E.g. f (g (4)) = f (2) = 4.

Key Idea
(f ◦ g )(x) = x means f and g are inverse functions (on [0, ∞))!
But (g ◦ f )(x) = |x| =
̸ x, confirming g ◦ f ̸= f ◦ g in general.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 22 / 29
 C-Q20 — Composition – (g ◦ f )(x) and (f ◦ g )(x)
Question
√
If f (x) = x 2 and g (x) = x, find (g ◦ f )(x) and (f ◦ g )(x). [5 marks]

(g ◦ f )(x) = g (f (x)) (f ◦ g )(x) = f (g (x))

Apply f first, then g : Apply g first, then f :
2 √
(g ◦ f )(x) = g (f (x)) = g (x ) (f ◦ g )(x) = f (g (x)) = f ( x)
√ √ 2
= x 2 = |x| = ( x) = x

(g ◦ f )(x) = |x| (f ◦ g )(x) = x

Valid for all x ∈ R. Valid for x ≥ 0 (domain of g ).
E.g. g (f (−3)) = g (9) = 3 = | − 3|. E.g. f (g (4)) = f (2) = 4.

Key Idea
(f ◦ g )(x) = x means f and g are inverse functions (on [0, ∞))!
But (g ◦ f )(x) = |x| =
̸ x, confirming g ◦ f ̸= f ◦ g in general.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 22 / 29
 C-Q20 — Composition – (g ◦ f )(x) and (f ◦ g )(x)
Question
√
If f (x) = x 2 and g (x) = x, find (g ◦ f )(x) and (f ◦ g )(x). [5 marks]

(g ◦ f )(x) = g (f (x)) (f ◦ g )(x) = f (g (x))

Apply f first, then g : Apply g first, then f :
2 √
(g ◦ f )(x) = g (f (x)) = g (x ) (f ◦ g )(x) = f (g (x)) = f ( x)
√ √ 2
= x 2 = |x| = ( x) = x

(g ◦ f )(x) = |x| (f ◦ g )(x) = x

Valid for all x ∈ R. Valid for x ≥ 0 (domain of g ).
E.g. g (f (−3)) = g (9) = 3 = | − 3|. E.g. f (g (4)) = f (2) = 4.

Key Idea
(f ◦ g )(x) = x means f and g are inverse functions (on [0, ∞))!
But (g ◦ f )(x) = |x| =
̸ x, confirming g ◦ f ̸= f ◦ g in general.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 22 / 29
 C-Q20 — Composition – (g ◦ f )(x) and (f ◦ g )(x)
Question
√
If f (x) = x 2 and g (x) = x, find (g ◦ f )(x) and (f ◦ g )(x). [5 marks]

(g ◦ f )(x) = g (f (x)) (f ◦ g )(x) = f (g (x))

Apply f first, then g : Apply g first, then f :
2 √
(g ◦ f )(x) = g (f (x)) = g (x ) (f ◦ g )(x) = f (g (x)) = f ( x)
√ √ 2
= x 2 = |x| = ( x) = x

(g ◦ f )(x) = |x| (f ◦ g )(x) = x

Valid for all x ∈ R. Valid for x ≥ 0 (domain of g ).
E.g. g (f (−3)) = g (9) = 3 = | − 3|. E.g. f (g (4)) = f (2) = 4.

Key Idea
(f ◦ g )(x) = x means f and g are inverse functions (on [0, ∞))!
But (g ◦ f )(x) = |x| =
̸ x, confirming g ◦ f ̸= f ◦ g in general.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 22 / 29
 C-Q20 — Composition – (g ◦ f )(x) and (f ◦ g )(x)
Question
√
If f (x) = x 2 and g (x) = x, find (g ◦ f )(x) and (f ◦ g )(x). [5 marks]

(g ◦ f )(x) = g (f (x)) (f ◦ g )(x) = f (g (x))

Apply f first, then g : Apply g first, then f :
2 √
(g ◦ f )(x) = g (f (x)) = g (x ) (f ◦ g )(x) = f (g (x)) = f ( x)
√ √ 2
= x 2 = |x| = ( x) = x

(g ◦ f )(x) = |x| (f ◦ g )(x) = x

Valid for all x ∈ R. Valid for x ≥ 0 (domain of g ).
E.g. g (f (−3)) = g (9) = 3 = | − 3|. E.g. f (g (4)) = f (2) = 4.

Key Idea
(f ◦ g )(x) = x means f and g are inverse functions (on [0, ∞))!
But (g ◦ f )(x) = |x| =
̸ x, confirming g ◦ f ̸= f ◦ g in general.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 22 / 29
 C-Q20 — Composition – (g ◦ f )(x) and (f ◦ g )(x)
Question
√
If f (x) = x 2 and g (x) = x, find (g ◦ f )(x) and (f ◦ g )(x). [5 marks]

(g ◦ f )(x) = g (f (x)) (f ◦ g )(x) = f (g (x))

Apply f first, then g : Apply g first, then f :
2 √
(g ◦ f )(x) = g (f (x)) = g (x ) (f ◦ g )(x) = f (g (x)) = f ( x)
√ √ 2
= x 2 = |x| = ( x) = x

(g ◦ f )(x) = |x| (f ◦ g )(x) = x

Valid for all x ∈ R. Valid for x ≥ 0 (domain of g ).
E.g. g (f (−3)) = g (9) = 3 = | − 3|. E.g. f (g (4)) = f (2) = 4.

Key Idea
(f ◦ g )(x) = x means f and g are inverse functions (on [0, ∞))!
But (g ◦ f )(x) = |x| =
̸ x, confirming g ◦ f ̸= f ◦ g in general.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 22 / 29
 C-Q20 — Composition – (g ◦ f )(x) and (f ◦ g )(x)
Question
√
If f (x) = x 2 and g (x) = x, find (g ◦ f )(x) and (f ◦ g )(x). [5 marks]

(g ◦ f )(x) = g (f (x)) (f ◦ g )(x) = f (g (x))

Apply f first, then g : Apply g first, then f :
2 √
(g ◦ f )(x) = g (f (x)) = g (x ) (f ◦ g )(x) = f (g (x)) = f ( x)
√ √ 2
= x 2 = |x| = ( x) = x

(g ◦ f )(x) = |x| (f ◦ g )(x) = x

Valid for all x ∈ R. Valid for x ≥ 0 (domain of g ).
E.g. g (f (−3)) = g (9) = 3 = | − 3|. E.g. f (g (4)) = f (2) = 4.

Key Idea
(f ◦ g )(x) = x means f and g are inverse functions (on [0, ∞))!
But (g ◦ f )(x) = |x| =
̸ x, confirming g ◦ f ̸= f ◦ g in general.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 22 / 29
 C-Q20 — Composition – (g ◦ f )(x) and (f ◦ g )(x)
Question
√
If f (x) = x 2 and g (x) = x, find (g ◦ f )(x) and (f ◦ g )(x). [5 marks]

(g ◦ f )(x) = g (f (x)) (f ◦ g )(x) = f (g (x))

Apply f first, then g : Apply g first, then f :
2 √
(g ◦ f )(x) = g (f (x)) = g (x ) (f ◦ g )(x) = f (g (x)) = f ( x)
√ √ 2
= x 2 = |x| = ( x) = x

(g ◦ f )(x) = |x| (f ◦ g )(x) = x

Valid for all x ∈ R. Valid for x ≥ 0 (domain of g ).
E.g. g (f (−3)) = g (9) = 3 = | − 3|. E.g. f (g (4)) = f (2) = 4.

Key Idea
(f ◦ g )(x) = x means f and g are inverse functions (on [0, ∞))!
But (g ◦ f )(x) = |x| =
̸ x, confirming g ◦ f ̸= f ◦ g in general.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 22 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [1/2]
Question
Prove that f : R → R, f (x) = 2x + 3, is one-to-one and onto. [5–6 marks]

Part 1 – Prove Injective (One-to-One)

Strategy: Assume f (x1 ) = f (x2 ) and deduce x1 = x2 .
Suppose f (x1 ) = f (x2 ) for x1 , x2 ∈ R:

2x1 + 3 = 2x2 + 3
2x1 = 2x2
x1 = x2 ✓

∴ f is injective (one-to-one).

Key Idea
Template for injective proofs:
“Assume f (x1 ) = f (x2 )” −→ algebraic steps −→ conclude x1 = x2 .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 23 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [1/2]
Question
Prove that f : R → R, f (x) = 2x + 3, is one-to-one and onto. [5–6 marks]

Part 1 – Prove Injective (One-to-One)

Strategy: Assume f (x1 ) = f (x2 ) and deduce x1 = x2 .
Suppose f (x1 ) = f (x2 ) for x1 , x2 ∈ R:

2x1 + 3 = 2x2 + 3
2x1 = 2x2
x1 = x2 ✓

∴ f is injective (one-to-one).

Key Idea
Template for injective proofs:
“Assume f (x1 ) = f (x2 )” −→ algebraic steps −→ conclude x1 = x2 .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 23 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [1/2]
Question
Prove that f : R → R, f (x) = 2x + 3, is one-to-one and onto. [5–6 marks]

Part 1 – Prove Injective (One-to-One)

Strategy: Assume f (x1 ) = f (x2 ) and deduce x1 = x2 .
Suppose f (x1 ) = f (x2 ) for x1 , x2 ∈ R:

2x1 + 3 = 2x2 + 3
2x1 = 2x2
x1 = x2 ✓

∴ f is injective (one-to-one).

Key Idea
Template for injective proofs:
“Assume f (x1 ) = f (x2 )” −→ algebraic steps −→ conclude x1 = x2 .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 23 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [1/2]
Question
Prove that f : R → R, f (x) = 2x + 3, is one-to-one and onto. [5–6 marks]

Part 1 – Prove Injective (One-to-One)

Strategy: Assume f (x1 ) = f (x2 ) and deduce x1 = x2 .
Suppose f (x1 ) = f (x2 ) for x1 , x2 ∈ R:

2x1 + 3 = 2x2 + 3
2x1 = 2x2
x1 = x2 ✓

∴ f is injective (one-to-one).

Key Idea
Template for injective proofs:
“Assume f (x1 ) = f (x2 )” −→ algebraic steps −→ conclude x1 = x2 .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 23 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [1/2]
Question
Prove that f : R → R, f (x) = 2x + 3, is one-to-one and onto. [5–6 marks]

Part 1 – Prove Injective (One-to-One)

Strategy: Assume f (x1 ) = f (x2 ) and deduce x1 = x2 .
Suppose f (x1 ) = f (x2 ) for x1 , x2 ∈ R:

2x1 + 3 = 2x2 + 3
2x1 = 2x2
x1 = x2 ✓

∴ f is injective (one-to-one).

Key Idea
Template for injective proofs:
“Assume f (x1 ) = f (x2 )” −→ algebraic steps −→ conclude x1 = x2 .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 23 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [1/2]
Question
Prove that f : R → R, f (x) = 2x + 3, is one-to-one and onto. [5–6 marks]

Part 1 – Prove Injective (One-to-One)

Strategy: Assume f (x1 ) = f (x2 ) and deduce x1 = x2 .
Suppose f (x1 ) = f (x2 ) for x1 , x2 ∈ R:

2x1 + 3 = 2x2 + 3
2x1 = 2x2
x1 = x2 ✓

∴ f is injective (one-to-one).

Key Idea
Template for injective proofs:
“Assume f (x1 ) = f (x2 )” −→ algebraic steps −→ conclude x1 = x2 .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 23 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [1/2]
Question
Prove that f : R → R, f (x) = 2x + 3, is one-to-one and onto. [5–6 marks]

Part 1 – Prove Injective (One-to-One)

Strategy: Assume f (x1 ) = f (x2 ) and deduce x1 = x2 .
Suppose f (x1 ) = f (x2 ) for x1 , x2 ∈ R:

2x1 + 3 = 2x2 + 3
2x1 = 2x2
x1 = x2 ✓

∴ f is injective (one-to-one).

Key Idea
Template for injective proofs:
“Assume f (x1 ) = f (x2 )” −→ algebraic steps −→ conclude x1 = x2 .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 23 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [1/2]
Question
Prove that f : R → R, f (x) = 2x + 3, is one-to-one and onto. [5–6 marks]

Part 1 – Prove Injective (One-to-One)

Strategy: Assume f (x1 ) = f (x2 ) and deduce x1 = x2 .
Suppose f (x1 ) = f (x2 ) for x1 , x2 ∈ R:

2x1 + 3 = 2x2 + 3
2x1 = 2x2
x1 = x2 ✓

∴ f is injective (one-to-one).

Key Idea
Template for injective proofs:
“Assume f (x1 ) = f (x2 )” −→ algebraic steps −→ conclude x1 = x2 .

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 23 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [2/2]

Part 2 – Prove Surjective (Onto)

Strategy: Take any y in the codomain; find x in the domain with f (x) = y .
Let y ∈ R be arbitrary. Solve f (x) = y :

2x + 3 = y
y −3
x=
2
y −3
Since y ∈ R, we have x = ∈ R. ✓
  2
y −3 y −3
Verify: f =2· + 3 = (y − 3) + 3 = y ✓
2 2
∴ f is surjective (onto).

Solution
Since f (x) = 2x + 3 is both injective and surjective, it is bijective. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 24 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [2/2]

Part 2 – Prove Surjective (Onto)

Strategy: Take any y in the codomain; find x in the domain with f (x) = y .
Let y ∈ R be arbitrary. Solve f (x) = y :

2x + 3 = y
y −3
x=
2
y −3
Since y ∈ R, we have x = ∈ R. ✓
  2
y −3 y −3
Verify: f =2· + 3 = (y − 3) + 3 = y ✓
2 2
∴ f is surjective (onto).

Solution
Since f (x) = 2x + 3 is both injective and surjective, it is bijective. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 24 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [2/2]

Part 2 – Prove Surjective (Onto)

Strategy: Take any y in the codomain; find x in the domain with f (x) = y .
Let y ∈ R be arbitrary. Solve f (x) = y :

2x + 3 = y
y −3
x=
2
y −3
Since y ∈ R, we have x = ∈ R. ✓
  2
y −3 y −3
Verify: f =2· + 3 = (y − 3) + 3 = y ✓
2 2
∴ f is surjective (onto).

Solution
Since f (x) = 2x + 3 is both injective and surjective, it is bijective. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 24 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [2/2]

Part 2 – Prove Surjective (Onto)

Strategy: Take any y in the codomain; find x in the domain with f (x) = y .
Let y ∈ R be arbitrary. Solve f (x) = y :

2x + 3 = y
y −3
x=
2
y −3
Since y ∈ R, we have x = ∈ R. ✓
  2
y −3 y −3
Verify: f =2· + 3 = (y − 3) + 3 = y ✓
2 2
∴ f is surjective (onto).

Solution
Since f (x) = 2x + 3 is both injective and surjective, it is bijective. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 24 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [2/2]

Part 2 – Prove Surjective (Onto)

Strategy: Take any y in the codomain; find x in the domain with f (x) = y .
Let y ∈ R be arbitrary. Solve f (x) = y :

2x + 3 = y
y −3
x=
2
y −3
Since y ∈ R, we have x = ∈ R. ✓
  2
y −3 y −3
Verify: f =2· + 3 = (y − 3) + 3 = y ✓
2 2
∴ f is surjective (onto).

Solution
Since f (x) = 2x + 3 is both injective and surjective, it is bijective. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 24 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [2/2]

Part 2 – Prove Surjective (Onto)

Strategy: Take any y in the codomain; find x in the domain with f (x) = y .
Let y ∈ R be arbitrary. Solve f (x) = y :

2x + 3 = y
y −3
x=
2
y −3
Since y ∈ R, we have x = ∈ R. ✓
  2
y −3 y −3
Verify: f =2· + 3 = (y − 3) + 3 = y ✓
2 2
∴ f is surjective (onto).

Solution
Since f (x) = 2x + 3 is both injective and surjective, it is bijective. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 24 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [2/2]

Part 2 – Prove Surjective (Onto)

Strategy: Take any y in the codomain; find x in the domain with f (x) = y .
Let y ∈ R be arbitrary. Solve f (x) = y :

2x + 3 = y
y −3
x=
2
y −3
Since y ∈ R, we have x = ∈ R. ✓
  2
y −3 y −3
Verify: f =2· + 3 = (y − 3) + 3 = y ✓
2 2
∴ f is surjective (onto).

Solution
Since f (x) = 2x + 3 is both injective and surjective, it is bijective. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 24 / 29
 C-Q21 — Prove f (x) = 2x + 3 is Bijective [2/2]

Part 2 – Prove Surjective (Onto)

Strategy: Take any y in the codomain; find x in the domain with f (x) = y .
Let y ∈ R be arbitrary. Solve f (x) = y :

2x + 3 = y
y −3
x=
2
y −3
Since y ∈ R, we have x = ∈ R. ✓
  2
y −3 y −3
Verify: f =2· + 3 = (y − 3) + 3 = y ✓
2 2
∴ f is surjective (onto).

Solution
Since f (x) = 2x + 3 is both injective and surjective, it is bijective. □

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 24 / 29
 C-Q25 — Composition of Bijections is Bijective [1/2]

Question
Prove: if f : A → B and g : B → C are both bijective, then g ◦ f : A → C is bijective. [5–6 marks]

Proof strategy: Show g ◦ f is (i) injective and (ii) surjective.

Part 1 – g ◦ f is Injective:
Let a1 , a2 ∈ A and suppose (g ◦ f )(a1 ) = (g ◦ f )(a2 ).
⇒ g (f (a1 )) = g (f (a2 ))
⇒ f (a1 ) = f (a2 ) [g is injective]
⇒ a1 = a2 [f is injective] ✓
g ◦ f is injective.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 25 / 29
 C-Q25 — Composition of Bijections is Bijective [1/2]

Question
Prove: if f : A → B and g : B → C are both bijective, then g ◦ f : A → C is bijective. [5–6 marks]

Proof strategy: Show g ◦ f is (i) injective and (ii) surjective.

Part 1 – g ◦ f is Injective:
Let a1 , a2 ∈ A and suppose (g ◦ f )(a1 ) = (g ◦ f )(a2 ).
⇒ g (f (a1 )) = g (f (a2 ))
⇒ f (a1 ) = f (a2 ) [g is injective]
⇒ a1 = a2 [f is injective] ✓
g ◦ f is injective.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 25 / 29
 C-Q25 — Composition of Bijections is Bijective [1/2]

Question
Prove: if f : A → B and g : B → C are both bijective, then g ◦ f : A → C is bijective. [5–6 marks]

Proof strategy: Show g ◦ f is (i) injective and (ii) surjective.

Part 1 – g ◦ f is Injective:
Let a1 , a2 ∈ A and suppose (g ◦ f )(a1 ) = (g ◦ f )(a2 ).
⇒ g (f (a1 )) = g (f (a2 ))
⇒ f (a1 ) = f (a2 ) [g is injective]
⇒ a1 = a2 [f is injective] ✓
g ◦ f is injective.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 25 / 29
 C-Q25 — Composition of Bijections is Bijective [1/2]

Question
Prove: if f : A → B and g : B → C are both bijective, then g ◦ f : A → C is bijective. [5–6 marks]

Proof strategy: Show g ◦ f is (i) injective and (ii) surjective.

Part 1 – g ◦ f is Injective:
Let a1 , a2 ∈ A and suppose (g ◦ f )(a1 ) = (g ◦ f )(a2 ).
⇒ g (f (a1 )) = g (f (a2 ))
⇒ f (a1 ) = f (a2 ) [g is injective]
⇒ a1 = a2 [f is injective] ✓
g ◦ f is injective.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 25 / 29
 C-Q25 — Composition of Bijections is Bijective [1/2]

Question
Prove: if f : A → B and g : B → C are both bijective, then g ◦ f : A → C is bijective. [5–6 marks]

Proof strategy: Show g ◦ f is (i) injective and (ii) surjective.

Part 1 – g ◦ f is Injective:
Let a1 , a2 ∈ A and suppose (g ◦ f )(a1 ) = (g ◦ f )(a2 ).
⇒ g (f (a1 )) = g (f (a2 ))
⇒ f (a1 ) = f (a2 ) [g is injective]
⇒ a1 = a2 [f is injective] ✓
g ◦ f is injective.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 25 / 29
 C-Q25 — Composition of Bijections is Bijective [1/2]

Question
Prove: if f : A → B and g : B → C are both bijective, then g ◦ f : A → C is bijective. [5–6 marks]

Proof strategy: Show g ◦ f is (i) injective and (ii) surjective.

Part 1 – g ◦ f is Injective:
Let a1 , a2 ∈ A and suppose (g ◦ f )(a1 ) = (g ◦ f )(a2 ).
⇒ g (f (a1 )) = g (f (a2 ))
⇒ f (a1 ) = f (a2 ) [g is injective]
⇒ a1 = a2 [f is injective] ✓
g ◦ f is injective.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 25 / 29
 C-Q25 — Composition of Bijections is Bijective [1/2]

Question
Prove: if f : A → B and g : B → C are both bijective, then g ◦ f : A → C is bijective. [5–6 marks]

Proof strategy: Show g ◦ f is (i) injective and (ii) surjective.

Part 1 – g ◦ f is Injective:
Let a1 , a2 ∈ A and suppose (g ◦ f )(a1 ) = (g ◦ f )(a2 ).
⇒ g (f (a1 )) = g (f (a2 ))
⇒ f (a1 ) = f (a2 ) [g is injective]
⇒ a1 = a2 [f is injective] ✓
g ◦ f is injective.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 25 / 29
 C-Q25 — Composition of Bijections is Bijective [2/2]
Part 2 – g ◦ f is Surjective:
Let c ∈ C be arbitrary.
Since g is surjective: ∃ b ∈ B s.t. g (b) = c.
Since f is surjective: ∃ a ∈ A s.t. f (a) = b.
Then (g ◦ f )(a) = g (f (a)) = g (b) = c. ✓
g ◦ f is surjective.

Solution
Since g ◦ f is both injective and surjective, it is bijective. □

Key Idea
Bonus fact: (g ◦ f )−1 = f −1 ◦ g −1
(Reverse the composition order when inverting. Think: to undo “put on socks then shoes”, first
take off shoes, then socks.)

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 26 / 29
 C-Q25 — Composition of Bijections is Bijective [2/2]
Part 2 – g ◦ f is Surjective:
Let c ∈ C be arbitrary.
Since g is surjective: ∃ b ∈ B s.t. g (b) = c.
Since f is surjective: ∃ a ∈ A s.t. f (a) = b.
Then (g ◦ f )(a) = g (f (a)) = g (b) = c. ✓
g ◦ f is surjective.

Solution
Since g ◦ f is both injective and surjective, it is bijective. □

Key Idea
Bonus fact: (g ◦ f )−1 = f −1 ◦ g −1
(Reverse the composition order when inverting. Think: to undo “put on socks then shoes”, first
take off shoes, then socks.)

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 26 / 29
 C-Q25 — Composition of Bijections is Bijective [2/2]
Part 2 – g ◦ f is Surjective:
Let c ∈ C be arbitrary.
Since g is surjective: ∃ b ∈ B s.t. g (b) = c.
Since f is surjective: ∃ a ∈ A s.t. f (a) = b.
Then (g ◦ f )(a) = g (f (a)) = g (b) = c. ✓
g ◦ f is surjective.

Solution
Since g ◦ f is both injective and surjective, it is bijective. □

Key Idea
Bonus fact: (g ◦ f )−1 = f −1 ◦ g −1
(Reverse the composition order when inverting. Think: to undo “put on socks then shoes”, first
take off shoes, then socks.)

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 26 / 29
 C-Q25 — Composition of Bijections is Bijective [2/2]
Part 2 – g ◦ f is Surjective:
Let c ∈ C be arbitrary.
Since g is surjective: ∃ b ∈ B s.t. g (b) = c.
Since f is surjective: ∃ a ∈ A s.t. f (a) = b.
Then (g ◦ f )(a) = g (f (a)) = g (b) = c. ✓
g ◦ f is surjective.

Solution
Since g ◦ f is both injective and surjective, it is bijective. □

Key Idea
Bonus fact: (g ◦ f )−1 = f −1 ◦ g −1
(Reverse the composition order when inverting. Think: to undo “put on socks then shoes”, first
take off shoes, then socks.)

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 26 / 29
 C-Q25 — Composition of Bijections is Bijective [2/2]
Part 2 – g ◦ f is Surjective:
Let c ∈ C be arbitrary.
Since g is surjective: ∃ b ∈ B s.t. g (b) = c.
Since f is surjective: ∃ a ∈ A s.t. f (a) = b.
Then (g ◦ f )(a) = g (f (a)) = g (b) = c. ✓
g ◦ f is surjective.

Solution
Since g ◦ f is both injective and surjective, it is bijective. □

Key Idea
Bonus fact: (g ◦ f )−1 = f −1 ◦ g −1
(Reverse the composition order when inverting. Think: to undo “put on socks then shoes”, first
take off shoes, then socks.)

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 26 / 29
 C-Q25 — Composition of Bijections is Bijective [2/2]
Part 2 – g ◦ f is Surjective:
Let c ∈ C be arbitrary.
Since g is surjective: ∃ b ∈ B s.t. g (b) = c.
Since f is surjective: ∃ a ∈ A s.t. f (a) = b.
Then (g ◦ f )(a) = g (f (a)) = g (b) = c. ✓
g ◦ f is surjective.

Solution
Since g ◦ f is both injective and surjective, it is bijective. □

Key Idea
Bonus fact: (g ◦ f )−1 = f −1 ◦ g −1
(Reverse the composition order when inverting. Think: to undo “put on socks then shoes”, first
take off shoes, then socks.)

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 26 / 29
 C-Q25 — Composition of Bijections is Bijective [2/2]
Part 2 – g ◦ f is Surjective:
Let c ∈ C be arbitrary.
Since g is surjective: ∃ b ∈ B s.t. g (b) = c.
Since f is surjective: ∃ a ∈ A s.t. f (a) = b.
Then (g ◦ f )(a) = g (f (a)) = g (b) = c. ✓
g ◦ f is surjective.

Solution
Since g ◦ f is both injective and surjective, it is bijective. □

Key Idea
Bonus fact: (g ◦ f )−1 = f −1 ◦ g −1
(Reverse the composition order when inverting. Think: to undo “put on socks then shoes”, first
take off shoes, then socks.)

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 26 / 29
 Properties of Relations – Complete Reference

Property Definition Digraph clue Matrix clue

Reflexive (a, a) ∈ R for all a ∈ A Loops at every Diagonal all 1
node
Symmetric (a, b) ∈ R ⇒ (b, a) ∈ R All edges bidirec- MR = MR⊤
tional
Transitive (a, b), (b, c) ∈ R ⇒ (a, c) ∈ 2-hop paths have (MR )2 ≤ MR
R shortcuts
Anti-symm. (a, b)&(b, a) ∈ R ⇒ a = b No bidirectional No sym. off-
edges diagonal pair
Equivalence Reflexive + Symmetric + RST
Transitive
Partial Order Reflexive + Anti-symm. + RAST
Transitive

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 27 / 29
 Properties of Relations – Complete Reference

Property Definition Digraph clue Matrix clue

Reflexive (a, a) ∈ R for all a ∈ A Loops at every Diagonal all 1
node
Symmetric (a, b) ∈ R ⇒ (b, a) ∈ R All edges bidirec- MR = MR⊤
tional
Transitive (a, b), (b, c) ∈ R ⇒ (a, c) ∈ 2-hop paths have (MR )2 ≤ MR
R shortcuts
Anti-symm. (a, b)&(b, a) ∈ R ⇒ a = b No bidirectional No sym. off-
edges diagonal pair
Equivalence Reflexive + Symmetric + RST
Transitive
Partial Order Reflexive + Anti-symm. + RAST
Transitive

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 27 / 29
 Properties of Relations – Complete Reference

Property Definition Digraph clue Matrix clue

Reflexive (a, a) ∈ R for all a ∈ A Loops at every Diagonal all 1
node
Symmetric (a, b) ∈ R ⇒ (b, a) ∈ R All edges bidirec- MR = MR⊤
tional
Transitive (a, b), (b, c) ∈ R ⇒ (a, c) ∈ 2-hop paths have (MR )2 ≤ MR
R shortcuts
Anti-symm. (a, b)&(b, a) ∈ R ⇒ a = b No bidirectional No sym. off-
edges diagonal pair
Equivalence Reflexive + Symmetric + RST
Transitive
Partial Order Reflexive + Anti-symm. + RAST
Transitive

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 27 / 29
 Types of Functions – Complete Reference

Type Definition Example / Counter-example

Injective (1-1) f (a) = f (b) ⇒ a = b f : R → R, f (x) = 3x
Surjective (Onto) Range = Co-domain f : Z → Z, f (x) = x + 1
Bijective Injective + Surjective f (x) = 2x + 3 on R
Into (Not onto) Range ⊊ Co-domain f : R → R, f (x) = x 2
1-1, not onto Injective, not surjective f : N → Z, f (n) = 2n
Onto, not 1-1 Surjective, not injective f : Z → {0, 1}, f (n) = n mod
2

Inverse Functions
f −1 exists ⇔ f is bijective. Find it: set y = f (x), solve for x, rename y → x.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 28 / 29
 Types of Functions – Complete Reference

Type Definition Example / Counter-example

Injective (1-1) f (a) = f (b) ⇒ a = b f : R → R, f (x) = 3x
Surjective (Onto) Range = Co-domain f : Z → Z, f (x) = x + 1
Bijective Injective + Surjective f (x) = 2x + 3 on R
Into (Not onto) Range ⊊ Co-domain f : R → R, f (x) = x 2
1-1, not onto Injective, not surjective f : N → Z, f (n) = 2n
Onto, not 1-1 Surjective, not injective f : Z → {0, 1}, f (n) = n mod
2

Inverse Functions
f −1 exists ⇔ f is bijective. Find it: set y = f (x), solve for x, rename y → x.

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 28 / 29
 Unit III – Relations & Functions
Questions & Solutions: Complete

Study Strategy for Exams

1 For relations: check R, S/AS, T one by one – write each step.
2 Use a digraph or matrix to visualise and verify properties.
3 For injective proofs: start with f (x1 ) = f (x2 ), deduce x1 = x2 .
4 For surjective proofs: take arbitrary y , solve for x, verify.
5 For inverses: swap x ↔ y , solve, then verify by composing.
6 Composition: “g ◦ f ” means apply f first, g second.

Next: Unit IV – Mathematical Reasoning & Proof Techniques

Interactive Study Guide (BCA Programme · Second Semester) Unit III – Relations & Functions 29 / 29