Sets, Relations and Functions

NDA Paper I gives 120 questions in 150 minutes (2.5 marks each, −0.83 penalty). Sets, relations and functions is a foundation chapter worth 3–5 questions and, more importantly, it underpins calculus, probability and trigonometry. These are near-guaranteed marks because the questions are short and formula-driven.

Core ideas

Sets: A set is a well-defined collection. Key operations — union A∪B, intersection A∩B, difference A−B, complement A'. For a set with n elements, the power set has 2^n subsets.

Counting formula (inclusion–exclusion):
n(A∪B) = n(A) + n(B) − n(A∩B)
n(A∪B∪C) = n(A)+n(B)+n(C) − n(A∩B) − n(B∩C) − n(C∩A) + n(A∩B∩C)

Relations: A relation R on set A is reflexive if aRa for all a; symmetric if aRb ⇒ bRa; transitive if aRb and bRc ⇒ aRc. All three together = equivalence relation.

Functions: f: A→B assigns each element of A exactly one image in B.

• One-one (injective): different inputs give different outputs.
• Onto (surjective): every element of B is an image.
• Bijective: both — then f⁻¹ exists.
  Number of functions from a set of m elements to n elements = n^m. Number of one-one functions (m ≤ n) = n!/(n−m)!.

Exam Tricks & Tips

• 🎯 For "n(exactly one of A, B)" use n(A)+n(B)−2·n(A∩B); "at least one" is just n(A∪B).
• 🎯 A relation on a set of n elements has n² ordered pairs, so 2^(n²) possible relations and 2^(n²−n) reflexive-allowed patterns — memorise the 2^(n²) count.
• 🎯 Bijective ⇒ |A| = |B| for finite sets; if domains differ in size, one-one-onto is impossible.
• 🎯 To test onto for a real function, check its range equals the co-domain, not just that it looks 'full'.
• 🎯 Composition (f∘g)(x) = f(g(x)); it is NOT commutative — order matters.
• ❌ Common mistake: treating the empty set ∅ as an element of every set. ∅ is a SUBSET of every set, not a member; {∅} has one element.

Expected exam pattern

Expect one Venn-diagram counting problem (survey of students liking tea/coffee), one relation-type identification, and one 'find the number of functions/one-one functions'. All are 30–60 second problems.

Quick recap

Memorise 2^n subsets, inclusion–exclusion, the three relation properties, and n^m / n!/(n−m)! function counts. Distinguish subset from element, and remember composition is order-sensitive.

Cover the answer, recall, then check. 11 cards on the set/relation/function facts NDA repeats.

Q1. Number of subsets and proper subsets of a set with n elements?
A1. Subsets = 2^n; proper subsets = 2^n − 1 (excludes the set itself).

Q2. n(A∪B) formula?
A2. n(A) + n(B) − n(A∩B).

Q3. n(A∪B∪C) formula?
A3. n(A)+n(B)+n(C) − n(A∩B) − n(B∩C) − n(C∩A) + n(A∩B∩C).

Q4. Define an equivalence relation.
A4. A relation that is reflexive, symmetric AND transitive.

Q5. Number of relations from a set of n elements to itself?
A5. 2^(n²), since there are n² ordered pairs each in-or-out.

Q6. Number of functions from a set with m elements to one with n elements?
A6. n^m.

Q7. Number of one-one (injective) functions, m ≤ n?
A7. n!/(n−m)! = ⁿPₘ.

Q8. When does f⁻¹ (inverse function) exist?
A8. Only when f is bijective (one-one and onto).

Q9. Is ∅ an element or a subset of every set?
A9. A SUBSET of every set. {∅} has one element, not zero.

Q10. (f∘g)(x) equals?
A10. f(g(x)) — apply g first, then f. Not commutative.

Q11. Number of elements liking exactly one of A or B?
A11. n(A) + n(B) − 2·n(A∩B).

Every branch of NDA Mathematics — from probability to calculus — is built on the language of sets, relations and functions. Master this and the rest of the paper reads more clearly.

Core idea / what this tests: Your ability to manipulate collections (sets), pair elements between them (relations), and recognise the special pairings that qualify as functions — plus counting formulas that reappear in probability.

Deep explanation

Beginner — Sets and operations

A set is a well-defined collection of distinct objects. Key operations:

• Union A ∪ B: all elements in A or B.
• Intersection A ∩ B: elements common to both.
• Difference A − B: in A but not B.
• Complement A′ = U − A (U = universal set).

For finite sets the counting law is n(A ∪ B) = n(A) + n(B) − n(A ∩ B), and for three sets
n(A ∪ B ∪ C) = n(A)+n(B)+n(C) − n(A∩B) − n(B∩C) − n(C∩A) + n(A∩B∩C).

If n(A) = m, the number of subsets is 2^m and proper subsets 2^m − 1.

Intermediate — Relations

A relation R from A to B is any subset of A × B. On a single set A, R may be:

• Reflexive: (a,a) ∈ R for all a.
• Symmetric: (a,b) ∈ R ⇒ (b,a) ∈ R.
• Transitive: (a,b),(b,c) ∈ R ⇒ (a,c) ∈ R.
  A relation that is reflexive, symmetric and transitive is an equivalence relation — it partitions A into disjoint classes.

Advanced — Functions

A function f: A → B assigns to every element of A exactly one element of B. Classifications:

• One-one (injective): distinct inputs → distinct outputs.
• Onto (surjective): every element of B is hit.
• Bijective: both — only then does f have an inverse.

Number of functions from A (m elements) to B (n elements) = n^m. Number of one-one functions (m ≤ n) = n·(n−1)···(n−m+1).

Worked example

Let A = {1,2,3}. How many relations on A are reflexive?
A × A has 3×3 = 9 ordered pairs. A reflexive relation must contain the 3 diagonal pairs (1,1),(2,2),(3,3); the remaining 6 pairs are free. So the count is 2^6 = 64.

NDA relevance

Set counting (the union formula) is a standing favourite — often disguised as "students who play cricket or football". Function-counting (n^m) feeds directly into permutation and probability questions. Equivalence-relation identification appears as a one-mark reasoning MCQ.

Exam tricks & shortcuts

• Draw a Venn diagram and fill from the innermost region outward.
• For "exactly two of three" use the middle terms only; subtract 3·(centre) when needed.
• Mnemonic for relation properties: R-S-T = Reflexive-Symmetric-Transitive → all three = equivalence.

Key formulas

• n(A∪B) = n(A) + n(B) − n(A∩B); n(A∪B∪C) = Σn − Σpairwise + n(A∩B∩C).
• Subsets of a set with n elements: 2ⁿ; proper subsets 2ⁿ − 1.
• Number of relations from A(m) to B(n): 2^{mn}; functions: nᵐ.
• De Morgan: (A∪B)' = A'∩B', (A∩B)' = A'∪B'.
• Reflexive/symmetric/transitive define equivalence relations.
• One-one functions A(m)→B(n): n!/(n−m)!; bijections on n-set: n!.

Usage: use the inclusion–exclusion formula for overlapping-set counting problems.

Worked Example

Problem: In a class of 60 students, 25 play cricket, 30 play hockey and 12 play both games. Find (a) how many play at least one of the two games, (b) how many play neither, and (c) how many play exactly one game.

Solution:
Let C be the set of cricket players and H the set of hockey players.
Given n(C) = 25, n(H) = 30, n(C ∩ H) = 12, and the universal set has 60 students.

(a) By the inclusion–exclusion principle for two sets:
n(C ∪ H) = n(C) + n(H) − n(C ∩ H)
n(C ∪ H) = 25 + 30 − 12 = 43.
So 43 students play at least one game.

(b) Students who play neither game lie outside C ∪ H:
n(neither) = Total − n(C ∪ H) = 60 − 43 = 17.

(c) "Exactly one" means in the union but not in the intersection:
n(exactly one) = n(C ∪ H) − n(C ∩ H) = 43 − 12 = 31.
(Cross-check: only cricket = 25 − 12 = 13, only hockey = 30 − 12 = 18, and 13 + 18 = 31.)

Answer: (a) 43, (b) 17, (c) 31.