Sets, relations and functions for NDA

This chapter sits at the start of the NDA algebra syllabus, and its ideas reappear across the paper: domains in calculus, one-one functions in inverse trigonometry, counting in probability. The questions themselves are usually short. Most can be solved in under a minute if you know a small set of results and the conditions attached to them.

Typical NDA question types here are:

• Venn-diagram counts with two or three sets;
• the number of subsets, relations or functions;
• identifying whether a relation is reflexive, symmetric or transitive;
• domain and range of a function;
• composition f(g(x)) and inverse functions;
• whether a function is one-one, onto or both.

Sets: operations and counting

For sets A and B inside a universal set U:

• A ∪ B (union): elements in A or B or both.
• A ∩ B (intersection): elements in both.
• A′ (complement): elements of U not in A.
• A − B (difference): elements in A but not in B. Note that A − B = A ∩ B′.

De Morgan's laws: (A ∪ B)′ = A′ ∩ B′ and (A ∩ B)′ = A′ ∪ B′. In words: the complement of "either" is "neither".

Counting formulas:

• 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(A ∩ C) + n(A ∩ B ∩ C)
• n(only A) = n(A) − n(A ∩ B), for two sets

The subtraction corrects for double counting: elements in both A and B are counted once in n(A) and again in n(B).

Subsets: a set with n elements has 2ⁿ subsets, because each element is either in a subset or not, giving 2 × 2 × … × 2 = 2ⁿ choices. Of these, 2ⁿ − 1 are proper subsets (all except the set itself).

Relations

A relation from A to B is any subset of the Cartesian product A × B. If n(A) = m and n(B) = n, then n(A × B) = mn, and so the number of relations from A to B is 2^(mn).

A relation R on a set A (from A to itself) can have these properties:

"a ≤ b" is reflexive and transitive but not symmetric; "a + b = 10" is symmetric but neither reflexive nor transitive (1 + 9 = 10 and 9 + 1 = 10, but 1 + 1 ≠ 10). An equivalence relation splits the set into non-overlapping classes; "a − b divisible by 5" splits the integers into five classes by remainder.

Counting relations on a set of n elements:

The reflexive count holds because the n diagonal pairs (a, a) must be included, leaving n² − n pairs free to include or exclude.

Functions

A function from A to B assigns exactly one element of B to each element of A. A is the domain, B the codomain, and the set of outputs actually produced is the range.

Finding the domain. List the restrictions and combine them:

• square root: the expression inside must be ≥ 0;
• denominator: must not be 0;
• logarithm: the argument must be > 0;
• square root in a denominator: the expression inside must be > 0.

Types of function:

• One-one (injective): different inputs give different outputs. Test: f(a) = f(b) forces a = b.
• Onto (surjective): every element of the codomain is an output, so range = codomain.
• Bijective: both. Only a bijection has an inverse.

Counting functions, with n(A) = m and n(B) = n:

• all functions from A to B: nᵐ (each of m inputs has n choices);
• one-one functions (m ≤ n): n × (n − 1) × … × (n − m + 1) = nPm;
• onto functions from A to a two-element set: 2ᵐ − 2 (all functions minus the two constant ones).

Composition: (f ∘ g)(x) = f(g(x)). Apply g first. In general f ∘ g ≠ g ∘ f.

Inverse: write y = f(x), solve for x in terms of y, then swap the letters.

Worked NDA-style MCQs

Q1. Of 100 cadets, 45 swim, 40 ride and 35 box. 15 swim and ride, 10 ride and box, 12 swim and box, and 5 do all three. How many do none of the three?
(a) 8 (b) 12 (c) 15 (d) 23

n(S ∪ R ∪ B) = 45 + 40 + 35 − 15 − 10 − 12 + 5 = 120 − 37 + 5 = 88. None = 100 − 88 = 12. Answer: (b).

As a check, the "only" regions are 45 − 15 − 12 + 5 = 23 (swim only), 40 − 15 − 10 + 5 = 20 (ride only) and 35 − 10 − 12 + 5 = 18 (box only). Exactly two activities: 10 + 5 + 7 = 22. Total 23 + 20 + 18 + 22 + 5 = 88.

Q2. How many reflexive relations are there on A = {1, 2, 3}?
(a) 8 (b) 27 (c) 64 (d) 512

n = 3, so 2^(9 − 3) = 2⁶ = 64. Answer: (c).

Q3. On A = {1, 2, 3}, let R = {(1, 1), (2, 2), (3, 3), (1, 2)}. Then R is:
(a) an equivalence relation (b) reflexive and symmetric only (c) reflexive and transitive but not symmetric (d) symmetric and transitive only

All three (a, a) pairs are present, so R is reflexive. (1, 2) is in R but (2, 1) is not, so it is not symmetric. For transitivity, the only chains are (1, 1) with (1, 2), and (1, 2) with (2, 2); both give (1, 2), which is in R. Answer: (c).

Q4. The domain of f(x) = √(x − 1) ÷ (x − 3) is:
(a) x ≥ 1 (b) x > 3 (c) x ≥ 1, x ≠ 3 (d) all real x except 3

The root needs x ≥ 1; the denominator needs x ≠ 3. Answer: (c).

Q5. If f(x) = (3x + 2)/(5x − 3), then f(f(x)) equals:
(a) x (b) −x (c) 1/x (d) f(x)

This has the form (ax + b)/(cx − a) with a = 3, so f(f(x)) = x. To verify: 3f + 2 = 19x/(5x − 3) and 5f − 3 = 19/(5x − 3), so their ratio is x. Answer: (a).

Q6. How many one-one functions are there from {1, 2, 3} to {a, b, c, d}?
(a) 12 (b) 24 (c) 64 (d) 81

4 × 3 × 2 = 24. (All functions would be 4³ = 64.) Answer: (b).

Common mistakes

• Forgetting the triple overlap in three-set problems. It is subtracted three times and added three times, so it must be added back once.
• Mixing up relations "from A to B" and "on A". The first is 2^(mn); the second is 2^(n²).
• Allowing zero under a square root in a denominator. 1/√(x − 2) needs x > 2, not x ≥ 2.
• Composing in the wrong order. f(g(x)) means g acts first.
• Assuming every function has an inverse. x² on all real numbers is not one-one, so it has none.

Practice set

1. If n(U) = 60, n(A) = 25, n(B) = 30 and n(A ∩ B) = 10, then n(A′ ∩ B′) is: (a) 5 (b) 15 (c) 20 (d) 45
2. The number of proper subsets of a set with 6 elements is: (a) 32 (b) 62 (c) 63 (d) 64
3. The number of relations on a set with 3 elements is: (a) 9 (b) 64 (c) 512 (d) 8
4. The domain of f(x) = 1/√(x² − 9) is: (a) x > 3 (b) −3 < x < 3 (c) x < −3 or x > 3 (d) x ≠ ±3
5. If f(x) = x² and g(x) = x + 1, then f(g(x)) − g(f(x)) equals: (a) 0 (b) 2x (c) 2x + 2 (d) x²
6. The inverse of f(x) = (x − 1)/(x + 2) is: (a) (1 + 2x)/(1 − x) (b) (x + 2)/(x − 1) (c) (2x − 1)/(x + 1) (d) (1 − 2x)/(1 + x)
7. Which function is one-one on the real numbers? (a) x² (b) the modulus of x (c) x³ (d) cos x
8. The number of onto functions from a 4-element set to a 2-element set is: (a) 8 (b) 14 (c) 16 (d) 6

Answers:

1. (b) 15. n(A ∪ B) = 25 + 30 − 10 = 45; by De Morgan, n(A′ ∩ B′) = 60 − 45 = 15.
2. (c) 63. 2⁶ − 1.
3. (c) 512. 2^(3²) = 2⁹.
4. (c). Need x² − 9 > 0, so x² > 9.
5. (b) 2x. (x + 1)² − (x² + 1) = 2x.
6. (a). y(x + 2) = x − 1 gives x(y − 1) = −1 − 2y, so x = (1 + 2y)/(1 − y).
7. (c) x³. The others give equal outputs for x and −x, or repeat every 2π.
8. (b) 14. 2⁴ − 2.

What to do next

• Write the three-set formula and the counting table from memory.
• Solve 30 mixed questions from old NDA papers on this chapter, timed at 60 seconds each.
• Move on to complex numbers, then quadratic equations; for counting ideas used here, see permutations and combinations.