CHAPTER 7

SETS, RELATIONS AND FUNCTIONS

CONCEPT & FUNDAMENTALS

SET
• A set is a collection of well-defined and distinct objects.
Example:
A = {1, 2, 3, 4, 5} — Set of first 5 natural numbers
B = {a, e, i, o, u} — Set of vowels
C = {2, 4, 6, 8} — Set of even numbers less than 10

SINGLETON SET
• A set containing only one element is called a singleton set.
Example:
A = {5} — contains only one element, so it is a singleton set
B = {0} — singleton set (note: {0} ≠ ∅, it has one element)

EQUAL SETS
• Two sets A and B are said to be equal if every element of A is in B and every element of B is in A.
A=B
Example:
A = {1, 2, 3} and B = {3, 1, 2}
→ A = B (order doesn't matter in sets)
A = {x : x is a letter in 'LISTEN'} and B = {x : x is a letter in 'SILENT'}
→ A = B (same elements: L, I, S, T, E, N)

NON-EMPTY SET
• A set having at least one element is called a non-empty set.
{0} ≠ ∅
Example:
A = {0} — Non-empty set (it has one element: zero)
B = {1, 2} — Non-empty set
∅ = {} — This IS the empty set (no elements)

EQUIVALENT SETS
• Two finite sets A and B are said to be equivalent if they have the same number of elements.
n(A) = n(B)
■ All equal sets are equivalent, but all equivalent sets are not equal.
Example:
A = {1, 2, 3} and B = {a, b, c}
→ n(A) = 3 = n(B), so they are EQUIVALENT but NOT EQUAL
A = {1, 2, 3} and B = {1, 2, 3}
→ BOTH equal and equivalent

NULL SET / VOID SET / EMPTY SET

• A set having no elements is called a null set.
∅
Example:
A = {x : x is a natural number less than 1} = ∅
B = {x : x² = -1, x ∈ Real} = ∅ (no real number has negative square)
C = {months with 32 days} = ∅

SUBSET
• If every element of set A is also an element of set B, then A is a subset of B.
A⊆B
Example:
A = {1, 2}, B = {1, 2, 3, 4}
→ A ⊆ B (every element of A is in B)
A = {2, 4, 6}, B = {1, 2, 3, 4, 5, 6}
→A⊆B✓

IMPORTANT RESULTS
• Every set is a subset of itself.
• Null set is a subset of every set.
Example:
If A = {1, 2, 3}: A ⊆ A ✓ (a set is always subset of itself)
∅ ⊆ A, ∅ ⊆ B, ∅ ⊆ any set ✓

POWER SET
CONCEPT
• The power set of a set A is the collection of all possible subsets of A.
• Denoted by: P(A)
Example:
A = {1, 2}
P(A) = { ∅, {1}, {2}, {1,2} }
→ Total subsets = 2² = 4

NUMBER OF SUBSETS
If a set has n elements, then number of subsets is: 2n
Example:
A = {a, b, c} → n = 3 → Total subsets = 2³ = 8
Subsets: ∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}

PROPER SUBSET
• All subsets excluding the set itself are called proper subsets.
Number of proper subsets = 2n - 1

Example:
A = {1, 2} → n = 2
Total subsets = 2² = 4 → { ∅, {1}, {2}, {1,2} }
Proper subsets = 4 - 1 = 3 → { ∅, {1}, {2} } (excluding {1,2} itself)

OPERATIONS ON SETS

UNION OF TWO SETS

n(A ∪ B) = n(A) + n(B) - n(A ∩ B)
Example:
In a class: 30 students play Cricket, 25 play Football, 10 play both.
Students playing Cricket or Football = 30 + 25 - 10 = 45

DISJOINT SETS
• If A and B are disjoint sets:
n(A ∩ B) = 0
n(A ∪ B) = n(A) + n(B)
Example:
A = {1, 3, 5} (odd), B = {2, 4, 6} (even)
→ A ∩ B = ∅, so n(A ∩ B) = 0
→ n(A ∪ B) = 3 + 3 = 6

UNION OF THREE SETS

n(P ∪ Q ∪ R) = n(P) + n(Q) + n(R) - n(P ∩ Q) - n(P ∩ R) - n(Q ∩ R) + n(P ∩ Q ∩ R)

Example:
In a survey of 100 students:
Maths=60, Science=50, English=40, M∩S=20, M∩E=15, S∩E=10, M∩S∩E=5
Total = 60+50+40-20-15-10+5 = 110
Students studying none = 100 - 110 = ... wait, this shows overlap counting!

WHEN THREE SETS ARE DISJOINT

n(P ∪ Q ∪ R) = n(P) + n(Q) + n(R)

 Example:
P = {1,2}, Q = {3,4}, R = {5,6} — all disjoint
n(P ∪ Q ∪ R) = 2 + 2 + 2 = 6

CARTESIAN PRODUCT OF SETS

CONCEPT
• If A and B are two non-empty sets, then the set of all ordered pairs (a, b) such that a ∈ A and b ∈ B is
called the Cartesian product of A and B.
NOTATION
A × B = {(a,b) : a ∈ A, b ∈ B}
SPECIAL CASE
If A = ∅ or B = ∅, then A × B = ∅

Example:
A = {1, 2}, B = {x, y}
A × B = {(1,x), (1,y), (2,x), (2,y)}
n(A × B) = n(A) × n(B) = 2 × 2 = 4
Note: (1,x) ≠ (x,1) — order matters in ordered pairs!

RELATIONS AND FUNCTIONS

RELATION
• Any subset of the Cartesian product X × Y is called a relation from X to Y.
Example:
A = {1, 2, 3}, B = {1, 4, 9}
R = {(1,1), (2,4), (3,9)} — relation 'x maps to x²'
R ⊆ A × B, so R is a valid relation from A to B

FUNCTION
• A relation in which no two ordered pairs have the same first element is called a function.
Example:
R1 = {(1,2), (2,4), (3,6)} — FUNCTION ✓ (each x has unique image)
R2 = {(1,2), (1,4), (3,6)} — NOT a function ✗ (x=1 has two images: 2 and 4)
f(x) = x² is a function (each x gives exactly one output)

FUNCTION NOTATION
If f is a function from A to B:
f:A→B
f(x) = y
Example:
f : A → B, f(x) = 2x
If x = 3, then f(3) = 2×3 = 6
So y = 6 is the IMAGE of x = 3
IMAGE AND PRE-IMAGE
• y is called the image of x.
• x is called the pre-image of y.
Example:
f(x) = x², f(4) = 16
→ 16 is the IMAGE of 4
→ 4 is the PRE-IMAGE of 16
(Note: -4 is also a pre-image of 16, since (-4)² = 16)

DOMAIN AND CO-DOMAIN

• Domain = Set A
• Co-domain = Set B
Example:
f : {1,2,3} → {1,4,9,16}, f(x) = x²
Domain = {1, 2, 3}
Co-domain = {1, 4, 9, 16}
Range = {1, 4, 9} (actual output values — may be ⊆ Co-domain)

TYPES OF FUNCTIONS

ONE-ONE (INJECTIVE) FUNCTION

• Different elements of A have different images in B.
Example:
f(x) = 2x from {1,2,3} to {2,4,6}
f(1)=2, f(2)=4, f(3)=6 → all images different → ONE-ONE ✓
f(x) = x² from {-1,1,2}: f(-1)=1=f(1) → NOT one-one ✗

ONTO (SURJECTIVE) FUNCTION

• Every element of B has at least one pre-image in A.
Example:
f : {1,2,3} → {1,4,9}, f(x) = x²
→ Every element of B (1,4,9) has a pre-image in A → ONTO ✓
f : {1,2} → {1,4,9}, f(x) = x²
→ 9 has no pre-image in {1,2} → NOT onto ✗

BIJECTIVE FUNCTION
• A function that is both one-one and onto.
• Also called one-to-one correspondence.
Example:
f : {1,2,3} → {2,4,6}, f(x) = 2x
One-one ✓ (different inputs → different outputs)
Onto ✓ (every element of {2,4,6} has a pre-image)
→ BIJECTIVE ✓
IDENTITY FUNCTION
If A is a non-empty set, then identity function I is defined as:
I:A→A
I(x) = x for all x ∈ A
Example:
A = {1, 2, 3}
I(1) = 1, I(2) = 2, I(3) = 3
→ Every element maps to itself

INVERSE FUNCTION
• If f is a one-one and onto function, then its inverse exists.
If f(x) = y, then f-1(y) = x

Example:
f(x) = 2x + 1
If f(3) = 7, then f■¹(7) = 3
Finding f■¹: y = 2x+1 → x = (y-1)/2 → f■¹(y) = (y-1)/2
Note: Inverse exists ONLY if f is bijective (one-one + onto)

RELATIONS: IMPORTANT TYPES

Let R ⊆ S × S

REFLEXIVE RELATION
If: (a, a) ∈ R for all a ∈ S
Example:
S = {1, 2, 3}, R = {(1,1), (2,2), (3,3), (1,2)}
→ (1,1), (2,2), (3,3) all present → REFLEXIVE ✓
R = {(1,2), (2,3)} → (1,1) missing → NOT reflexive ✗

SYMMETRIC RELATION
If: (a, b) ∈ R ■ (b, a) ∈ R
Example:
R = {(1,2), (2,1), (3,3)}
→ (1,2) present and (2,1) present → SYMMETRIC ✓
R = {(1,2), (2,3)} → (2,1) missing → NOT symmetric ✗

TRANSITIVE RELATION
If: (a, b) ∈ R and (b, c) ∈ R ■ (a, c) ∈ R
Example:
R = {(1,2), (2,3), (1,3)}
→ (1,2) and (2,3) present, and (1,3) also present → TRANSITIVE ✓
R = {(1,2), (2,3)} → (1,3) missing → NOT transitive ✗
EQUIVALENCE RELATION
• A relation which is: Reflexive + Symmetric + Transitive
Example:
R = 'has same birthday as' on a set of people
Reflexive: Every person has same birthday as themselves ✓
Symmetric: If A & B have same birthday, then B & A do too ✓
Transitive: If A=B and B=C (same bday), then A=C ✓
→ EQUIVALENCE RELATION ✓

DOMAIN AND RANGE OF A RELATION

If R is a relation from A to B:
• Domain of R = set of all first coordinates
• Range of R = set of all second coordinates
Example:
R = {(1,4), (2,5), (3,6)}
Domain of R = {1, 2, 3} ← all first elements
Range of R = {4, 5, 6} ← all second elements
Co-domain = Set B (may be larger than range)

ICAI TRAPS / STUDENT MISTAKES

• Confusing equal sets with equivalent sets — equal means same elements; equivalent means same count
• Writing 2■-1 instead of 2■ for total subsets (2■-1 is for PROPER subsets only)
• Forgetting intersection term in union formula: n(A∪B) = n(A)+n(B)-n(A∩B)
• Assuming inverse exists for every function — inverse exists ONLY for bijective functions
• Mixing domain, co-domain, and range — range ⊆ co-domain
• Writing relations without ordered pairs — always write as (a,b) pairs
• Poor notation (major ICAI penalty) — use proper set-builder and interval notation

FORMULA SHEET
Formula Description

n(A ∪ B) = n(A) + n(B) - n(A ∩ B) Union of 2 sets

n(A ∩ B) = 0 Disjoint sets

n(P ∪ Q ∪ R) = n(P)+n(Q)+n(R)-n(P∩Q)-n(P∩R)-n(Q∩R)+n(P∩Q∩R) Union of 3 sets

Total subsets = 2■ If n elements

Proper subsets = 2■ - 1 Excluding the set itself

A × B = {(a,b): a∈A, b∈B} Cartesian product

n(A × B) = n(A) × n(B) Size of Cartesian product

f: A→B, f(x)=y ■ f■¹(y)=x Inverse function