UNIT I

Set, Relation and Function

Mathematics Foundation to Computer Science – I (CC101)

BCA Semester I

This document covers all topics of Unit I with detailed explanations and examples. Topics include:
Sets & Set Operations, Venn Diagrams, Cartesian Products, Relations, Properties of Relations,
Equivalence Relations, Closures, Warshall's Algorithm, Functions, Types of Functions, and Special
Functions used in Computer Science.

1. Sets
A set is a well-defined collection of distinct objects, called elements or members. Sets are usually
denoted by capital letters (A, B, C…) and elements by small letters (a, b, c…).

If an element x belongs to set A, we write x ∈ A. If not, we write x ∉ A.

Example: A = {1, 2, 3, 4, 5} — Set of first five natural numbers.

B = {a, e, i, o, u} — Set of vowels.
C = {x | x is an even number less than 10} = {2, 4, 6, 8} — Set-builder form.

1.1 Types of Sets

Empty Set (∅): A set with no elements. e.g., A = {} = ∅

Singleton Set: A set with exactly one element. e.g., A = {5}

Finite Set: A set with countable elements. e.g., A = {1, 2, 3}

Infinite Set: A set with uncountable elements. e.g., N = {1, 2, 3, …}

Universal Set (U): The set containing all elements under consideration.

Subset (⊆): A ⊆ B if every element of A is also in B.

Example: A = {1, 2}, B = {1, 2, 3} → A ⊆ B (A is a subset of B).

Every set is a subset of itself. ∅ is a subset of every set.

Power Set P(A): The set of all subsets of A.

Example: A = {1, 2} → P(A) = {∅, {1}, {2}, {1,2}} — 4 subsets (2² = 4).

1.2 Set Operations

Union (A ∪ B): All elements in A or B or both.

Example: A = {1,2,3}, B = {3,4,5} → A ∪ B = {1,2,3,4,5}

Intersection (A ∩ B): Elements common to both A and B.

Example: A = {1,2,3}, B = {3,4,5} → A ∩ B = {3}

Difference (A − B): Elements in A but not in B.

Example: A = {1,2,3}, B = {3,4,5} → A − B = {1,2}

Complement (A'): All elements in the Universal Set that are not in A.

Example: U = {1,2,3,4,5}, A = {1,2} → A' = {3,4,5}

Symmetric Difference (A ■ B): Elements in A or B but not both.

Example: A = {1,2,3}, B = {3,4,5} → A ■ B = {1,2,4,5}

1.3 Properties of Set Operations

• Commutative: A ∪ B = B ∪ A, A ∩ B = B ∩ A

• Associative: (A ∪ B) ∪ C = A ∪ (B ∪ C)

• Distributive: A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

• De Morgan's Laws: (A ∪ B)' = A' ∩ B' and (A ∩ B)' = A' ∪ B'

Example: U={1,2,3,4,5}, A={1,2,3}, B={2,3,4}

A ∪ B = {1,2,3,4} → (A ∪ B)' = {5}
A' = {4,5}, B' = {1,5} → A' ∩ B' = {5} ✓

1.4 Venn Diagrams

A Venn Diagram visually represents sets and their relationships using overlapping circles inside a
rectangle (Universal Set).

Example: A = {1,2,3,4}, B = {3,4,5,6}, U = {1,2,3,4,5,6,7}

Draw two overlapping circles: Left circle = A, Right circle = B.
The overlapping region = A ∩ B = {3,4}.
Left only = A − B = {1,2}. Right only = B − A = {5,6}. Outside = {7}.

1.5 Cartesian Product

The Cartesian Product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B.

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

A × B = {(1,x), (1,y), (2,x), (2,y)}
|A × B| = |A| × |B| = 2 × 2 = 4

Note: A × B ≠ B × A (order matters in ordered pairs).

2. Relations
A relation R from set A to set B is a subset of the Cartesian Product A × B. It defines how elements
of A are related to elements of B.
 Example: A = {1,2,3}, B = {1,4,9}
R = {(1,1), (2,4), (3,9)} — 'a is related to b if b = a²'

2.1 Representing Relations

Using a Matrix (Boolean Matrix): For sets A and B of size m and n, create an m×n matrix M where
M[i][j] = 1 if (a_i, b_j) ∈ R, else 0.

Example: A = {1,2,3}, R = {(1,1),(1,2),(2,3),(3,3)} (relation on A)

Matrix:
123
1: [ 1 1 0 ]
2: [ 0 0 1 ]
3: [ 0 0 1 ]

Using a Digraph: Each element is a node; draw an arrow from a to b if (a,b) ∈ R.

2.2 Properties of Relations

Reflexive: (a, a) ∈ R for all a ∈ A. Every element is related to itself.

Example: R = {(1,1),(2,2),(3,3),(1,2)} on A={1,2,3} → Reflexive ✓

Irreflexive: (a, a) ∉ R for all a ∈ A.

Symmetric: If (a, b) ∈ R then (b, a) ∈ R.

Example: R = {(1,2),(2,1),(3,3)} → Symmetric ✓

Antisymmetric: If (a,b) ∈ R and (b,a) ∈ R, then a = b.

Example: The 'less than or equal to (≤)' relation is antisymmetric.

Transitive: If (a,b) ∈ R and (b,c) ∈ R, then (a,c) ∈ R.

Example: R = {(1,2),(2,3),(1,3)} → Transitive ✓

R = {(1,2),(2,3)} → NOT Transitive (missing (1,3))

2.3 Types of Relations

Equivalence Relation: A relation that is Reflexive, Symmetric, AND Transitive.

Example: R = {(1,1),(2,2),(3,3),(1,2),(2,1)} on A={1,2,3}

Reflexive ✓, Symmetric ✓, Transitive ✓ → Equivalence Relation ✓

Partial Order: A relation that is Reflexive, Antisymmetric, and Transitive. e.g., ≤ on integers.

Total Order: A partial order where every pair is comparable.

2.4 Equivalence Classes and Partition

If R is an equivalence relation on A, the equivalence class of element a is:
[a] = {x ∈ A | (x, a) ∈ R} — all elements related to a.

Example: A = {1,2,3,4,5,6}, R = 'same remainder when divided by 3'

[0]: {3,6} — remainder 0
[1]: {1,4} — remainder 1
 [2]: {2,5} — remainder 2
These classes partition A into disjoint subsets.

A partition of set A is a collection of non-empty, disjoint subsets whose union is A.

2.5 Closures of Relations

The closure of a relation R is the smallest relation containing R that has a certain property.

Reflexive Closure: Add all pairs (a,a) to R.

Example: R = {(1,2),(2,3)} → Reflexive Closure = {(1,1),(2,2),(3,3),(1,2),(2,3)}

Symmetric Closure: For every (a,b) ∈ R, add (b,a).

Example: R = {(1,2),(2,3)} → Symmetric Closure = {(1,2),(2,1),(2,3),(3,2)}

Transitive Closure: Add (a,c) whenever (a,b) and (b,c) are in R. Repeat until stable.

Example: R = {(1,2),(2,3)} → Transitive Closure = {(1,2),(2,3),(1,3)}

2.6 Warshall's Algorithm

Warshall's Algorithm efficiently computes the transitive closure of a relation using its Boolean
matrix.

Algorithm:
For k = 1 to n:
For i = 1 to n:
For j = 1 to n:
M[i][j] = M[i][j] OR (M[i][k] AND M[k][j])

Example: A={1,2,3}, R={(1,2),(2,3)}

Initial Matrix: After Warshall:
123123
1[0 1 0] 1[ 0 1 1 ]
2[0 0 1] 2[ 0 0 1 ]
3[0 0 0] 3[ 0 0 0 ]
The (1,3) entry becomes 1, representing the transitive closure path 1→2→3.

Note: Warshall's algorithm runs in O(n³) time and is widely used in network routing.

3. Functions
A function (or mapping) f from set A to set B, written f: A → B, is a relation where every element of A
is related to exactly one element of B.

• Domain: The set A (inputs of the function).

• Codomain: The set B (possible outputs).

• Range: The actual set of output values {f(a) | a ∈ A} ⊆ B.

 Example: f: {1,2,3} → {a,b,c,d} defined by f(1)=a, f(2)=a, f(3)=b
Domain = {1,2,3}, Codomain = {a,b,c,d}, Range = {a,b}

Note: Not a function: if an element in A maps to two different elements in B, or if some element in A has
no mapping.

3.1 Types of Functions

Injective (One-to-One): Different elements in A map to different elements in B. f(a■) = f(a■) ■ a■ =
a■.

Example: f: {1,2,3} → {a,b,c,d}, f(1)=a, f(2)=b, f(3)=c → Injective ✓ (no two inputs share an output)
f(1)=a, f(2)=a, f(3)=b → NOT Injective (1 and 2 both map to a)

Surjective (Onto): Every element in B is the image of at least one element of A. Range = Codomain.

Example: f: {1,2,3} → {a,b}, f(1)=a, f(2)=b, f(3)=a → Surjective ✓ (both a and b are covered)
f: {1,2,3} → {a,b,c,d} cannot be surjective since |A| < |B|.

Bijective (One-to-One Correspondence): Both Injective AND Surjective. Every element of A maps
to a unique element of B, and every element of B is covered.

Example: f: {1,2,3} → {a,b,c}, f(1)=a, f(2)=b, f(3)=c → Bijective ✓

Bijections allow a perfect pairing between two sets.

3.2 Composition of Functions

If f: A → B and g: B → C, then the composition g■f: A → C is defined as (g■f)(x) = g(f(x)).

Example: f(x) = x + 2, g(x) = 3x (functions on integers)

(g■f)(x) = g(f(x)) = g(x+2) = 3(x+2) = 3x + 6
(f■g)(x) = f(g(x)) = f(3x) = 3x + 2
Note: g■f ≠ f■g in general (composition is NOT commutative).

3.3 Inverse of a Function

The inverse of a function f: A → B, denoted f■¹: B → A, exists only if f is bijective. It 'reverses' f: if
f(a) = b, then f■¹(b) = a.

Example: f: R → R, f(x) = 2x + 3
To find f■¹: let y = 2x+3 → x = (y−3)/2
So f■¹(y) = (y−3)/2
Verify: f(f■¹(y)) = f((y−3)/2) = 2·(y−3)/2 + 3 = y ✓

4. Special Functions in Computer Science

4.1 Exponential Function
f(x) = a■ where a > 0, a ≠ 1. In CS, base 2 is most common: f(x) = 2■.

Example: 2■=1, 2¹=2, 2²=4, 2³=8, 2■=16, 2¹■=1024

Used in: binary representation, time complexity (2■ for brute-force algorithms), memory sizes (1 KB
= 2¹■ bytes, 1 MB = 2²■ bytes).
4.2 Logarithmic Function
f(x) = log_a(x) is the inverse of the exponential. log_a(x) = y means a■ = x.
In CS, log base 2 (log■ or lg) is most commonly used.

Example: log■(8) = 3 because 2³ = 8

log■(1024) = 10
Used in: Binary search runs in O(log■ n) steps. A sorted array of 1,000,000 elements needs at most
log■(1,000,000) ≈ 20 comparisons.

4.3 Polynomial Functions

f(x) = a■x■ + a■■■x■■¹ + … + a■x + a■ where n is a non-negative integer.

Example: f(x) = 3x² + 2x + 1 — degree 2 (quadratic)

g(x) = x³ − 4x + 7 — degree 3 (cubic)
Bubble Sort has time complexity O(n²) — a polynomial. Matrix multiplication is O(n³) — also
polynomial.

4.4 Floor and Ceiling Functions

Floor Function ■x■: The greatest integer less than or equal to x.

Example: ■3.7■ = 3, ■−2.3■ = −3, ■5■ = 5

Ceiling Function ■x■: The smallest integer greater than or equal to x.

Example: ■3.2■ = 4, ■−2.7■ = −2, ■5■ = 5

CS Applications:

• Integer division: 17 ÷ 5 = ■17/5■ = 3 (quotient)

• Number of pages needed for n items with k per page: ■n/k■

Example: 100 students, 12 per bus → ■100/12■ = ■8.33■ = 9 buses needed.

• In binary search: mid = ■(low + high)/2■

• In hash tables: index = ■h(key) mod table_size■

5. Quick Reference Summary

Topic Key Concept Example

Set Collection of distinct objects A = {1,2,3}

Subset A ⊆ B if all A-elements are in B {1,2} ⊆ {1,2,3}

Power Set Set of all subsets P({a,b}) = {∅,{a},{b},{a,b}}

Union A ∪ B — elements in A or B {1,2}∪{2,3} = {1,2,3}

Intersection A ∩ B — elements in both {1,2}∩{2,3} = {2}

Cartesian Product A×B — all ordered pairs {1}×{a,b} = {(1,a),(1,b)}

Topic Key Concept Example

Relation Subset of A×B R = {(1,1),(2,4),(3,9)}

Reflexive (a,a)∈R for all a ≤ on integers

Symmetric (a,b)∈R ■ (b,a)∈R = (equals) relation

Transitive (a,b),(b,c)∈R ■ (a,c)∈R < on integers

Equivalence Reflexive+Symmetric+Transitive Same parity relation

Warshall's Algo Computes transitive closure O(n³) Path reachability

Function Each input has exactly one output f(x) = x²

Injective Distinct inputs → distinct outputs f(x) = 2x

Surjective Every output is reached f(x) = x³ on R

Bijective Injective + Surjective f(x) = x+1 on Z

Floor ■x■ Round down to integer ■3.9■ = 3

Ceiling ■x■ Round up to integer ■3.1■ = 4

— End of Unit I —