In plain words
A set is a collection of distinct objects. A relation records which pairs of objects are linked, such as “divides”, “is a prerequisite of” or “lives in the same city as”. Some relations sort objects into groups of equals (equivalence relations); others rank them (partial orders). A function is a special relation that gives each input exactly one output. These ideas are the language of databases (a table is a relation), compilers (dependency orders), algorithms (hash functions) and much of Unit 1.
Why it matters for NET
This topic yields direct questions almost every cycle. The dominant sub-topics are: counting relations with a property (reflexive, symmetric, antisymmetric and combinations); counting functions, injections and surjections; equivalence relations and partitions (Bell and Stirling numbers); identifying properties of a given relation; Hasse diagrams with maximal, minimal, greatest and least elements; lattices, complements and distributivity in divisor lattices; and composition and inverses of functions. The questions are short, and the options are close numbers, so you need the exact formula.
Concepts in depth: sets and operations
For sets A and B inside a universe U: union A ∪ B, intersection A ∩ B, difference A − B (in A, not in B), complement A′ = U − A, and symmetric difference A ⊕ B = (A − B) ∪ (B − A) = (A ∪ B) − (A ∩ B). The identities mirror the logic laws of lesson 1.1: De Morgan ((A ∪ B)′ = A′ ∩ B′), distributive, absorption (A ∪ (A ∩ B) = A). Useful difference laws are A − (B ∪ C) = (A − B) ∩ (A − C) and A − (B ∩ C) = (A − B) ∪ (A − C).
The power set P(A) has 2|A| elements, since each element is either in or out of a subset. P(A ∩ B) = P(A) ∩ P(B), but P(A ∪ B) is usually larger than P(A) ∪ P(B). The Cartesian product A × B = {(a, b)} has |A|·|B| elements, and it distributes over ∪, ∩ and −. For two sets, |A ∪ B| = |A| + |B| − |A ∩ B| and |A ⊕ B| = |A| + |B| − 2|A ∩ B|. A set is countable if it is finite or can be listed as a sequence: ℕ, ℤ, ℚ, ℤ × ℤ and the set of finite strings over an alphabet are countable, while ℝ and P(ℕ) are not (Cantor’s diagonal argument).
Concepts in depth: relations and their properties
A relation R on A is a subset of A × A, written a R b when (a, b) ∈ R. It can be drawn as a 0–1 matrix M (rows and columns indexed by A) or as a directed graph.
| Property | Definition | Matrix test |
|---|---|---|
| Reflexive | a R a for every a | every diagonal entry is 1 |
| Irreflexive | a R a for no a | every diagonal entry is 0 |
| Symmetric | a R b ⇒ b R a | M = Mᵀ |
| Antisymmetric | a R b and b R a ⇒ a = b | no off-diagonal pair has both entries 1 |
| Asymmetric | a R b ⇒ not b R a | antisymmetric and irreflexive |
| Transitive | a R b and b R c ⇒ a R c | M² (Boolean) ≤ M |
Two points cause most errors. First, antisymmetric is not “not symmetric”: the identity relation {(a, a)} is both symmetric and antisymmetric, and {(1, 2), (2, 1), (1, 3)} is neither. Second, properties that are “if … then” statements hold vacuously when nothing triggers them: the empty relation on a non-empty set is symmetric, antisymmetric, asymmetric and transitive, but not reflexive.
Concepts in depth: counting relations
Think of the n × n matrix as n diagonal cells plus n(n − 1)/2 unordered off-diagonal pairs {(a, b), (b, a)}. Each property restricts each part independently, so the count is a product.
| Relations on an n-set | Diagonal choices | Per off-diagonal pair | Count | n = 3 |
|---|---|---|---|---|
| All | 2 each | 4 | 2^(n²) | 512 |
| Reflexive (or irreflexive) | 1 each | 4 | 2^(n² − n) | 64 |
| Symmetric | 2 each | 2 (both or neither) | 2^(n(n+1)/2) | 64 |
| Antisymmetric | 2 each | 3 (not both) | 2^n · 3^(n(n−1)/2) | 216 |
| Asymmetric | 1 (all 0) | 3 | 3^(n(n−1)/2) | 27 |
| Reflexive and symmetric | 1 | 2 | 2^(n(n−1)/2) | 8 |
| Reflexive and antisymmetric | 1 | 3 | 3^(n(n−1)/2) | 27 |
| Symmetric and antisymmetric | 2 | 1 (neither) | 2^n | 8 |
| Equivalence | Bell number Bₙ | 5 | ||
| Partial orders | no closed form: 1, 3, 19, 219 for n = 1 to 4 | 19 | ||
| Transitive | no closed form: 2, 13, 171, 3994 for n = 1 to 4 | 171 | ||
| Total (linear) orders | n! | 6 | ||
From an m-set to an n-set there are 2mn relations. On an n-set there are nn² binary operations and nn(n+1)/2 commutative ones (only the diagonal and one cell of each off-diagonal pair are free).
Concepts in depth: closures and composition
The closure of R under a property is the smallest relation containing R that has the property. The reflexive closure is R ∪ Δ (add the diagonal); the symmetric closure is R ∪ R⁻¹; the transitive closure R⁺ is R ∪ R² ∪ R³ ∪ … ∪ Rⁿ, the pairs (a, b) joined by a path of length at least 1 in the digraph. Warshall’s algorithm computes R⁺ in O(n³): for each k, set M[i][j] = 1 whenever M[i][k] and M[k][j] are 1. Composition: (a, c) ∈ S ∘ R when a R b and b S c for some b; with matrices, M(S∘R) = M(R) ⊙ M(S) (Boolean product). There is no “antisymmetric closure”, because adding pairs can never remove a violation.
Concepts in depth: equivalence relations and partitions
An equivalence relation is reflexive, symmetric and transitive. The equivalence class [a] = {x : x R a}. Classes are either identical or disjoint and together cover A, so they form a partition; conversely “in the same block” is an equivalence relation. Congruence modulo m on ℤ has exactly m classes [0], [1], …, [m − 1]. The number of partitions of an n-set into exactly k non-empty blocks is the Stirling number S(n, k), with S(n, k) = S(n − 1, k − 1) + k·S(n − 1, k) (element n either forms its own block or joins one of k blocks). The Bell number Bₙ = Σₖ S(n, k) counts all partitions: 1, 1, 2, 5, 15, 52, 203, 877 for n = 0 to 7. Useful values: S(n, 2) = 2^(n−1) − 1 and S(n, n − 1) = C(n, 2).
Concepts in depth: partial orders and Hasse diagrams
A partial order ⪯ is reflexive, antisymmetric and transitive; (A, ⪯) is a poset. Examples: ≤ on numbers, ⊆ on sets, divisibility on positive integers. Elements a and b are comparable if a ⪯ b or b ⪯ a. A total order (chain) makes every pair comparable. A Hasse diagram draws the poset without clutter: remove the loops (reflexivity), remove every edge implied by transitivity, and draw each remaining “covering” edge upward, so b sits above a when b covers a (a ≺ b with nothing in between).
- Maximal: nothing is strictly above it. Greatest: above every element. A finite poset always has a maximal element; a greatest element exists only if there is exactly one maximal element that sits above everything. The same holds for minimal and least.
- Upper bound of a subset S: an element ⪰ every element of S. The least upper bound (lub, supremum, join ∨) is the least of the upper bounds, if it exists; the greatest lower bound (glb, infimum, meet ∧) is defined dually.
- A topological sort lists the elements in a total order compatible with ⪯; every finite poset has one.
Concepts in depth: lattices
A lattice is a poset in which every pair has a join and a meet. In (P(S), ⊆) join is ∪ and meet is ∩; in the divisor lattice (Dn, |) join is lcm and meet is gcd. Every finite lattice is bounded, with a least element 0 and greatest element 1. A lattice is distributive if a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c); P(S), Dn and every chain are distributive. The two smallest non-distributive lattices are the diamond M₃ and the pentagon N₅; a lattice is distributive exactly when it contains neither as a sublattice. A bounded lattice is complemented if every a has some b with a ∨ b = 1 and a ∧ b = 0. In a distributive lattice a complement, if it exists, is unique. A complemented distributive lattice is a Boolean algebra; every finite one is isomorphic to some P(S) and has 2k elements. For divisor lattices, Dn is a Boolean algebra exactly when n is square-free (for example D30), and then the complement of a is n/a.
Concepts in depth: functions
A function f : A → B assigns to every a ∈ A exactly one f(a) ∈ B. A is the domain, B the codomain, f(A) the range. f is injective (one-to-one) if different inputs give different outputs, surjective (onto) if the range is all of B, and bijective if both, in which case the inverse f⁻¹ : B → A exists. For finite sets with |A| = |B|, injective ⇔ surjective ⇔ bijective. This fails for infinite sets: n ↦ n + 1 on ℕ is injective but not onto.
| From an m-set to an n-set | Count | Reason |
|---|---|---|
| Functions | n^m | n choices for each of m inputs |
| Injective (m ≤ n) | n!/(n − m)! | n, n − 1, … choices |
| Surjective (m ≥ n) | Σₖ (−1)^k C(n, k)(n − k)^m = n!·S(m, n) | inclusion–exclusion on the missed elements |
| Bijective (m = n) | n! | permutations |
| Partial functions | (n + 1)^m | each input: an output or “undefined” |
Composition (g ∘ f)(x) = g(f(x)) is associative but not commutative. Compositions of injections are injective, of surjections surjective. If g ∘ f is injective, then f is injective; if g ∘ f is surjective, then g is surjective. For bijections, (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹ (“socks and shoes”).
Worked examples
Example 1: counting relations on A = {a, b, c}. Find the number of antisymmetric relations and the number of relations that are reflexive and antisymmetric.
- The matrix has 3 diagonal cells and 3 off-diagonal pairs: {ab, ba}, {ac, ca}, {bc, cb}.
- Antisymmetric: each diagonal cell is free (2 ways). Each pair may hold neither, only the first, or only the second (3 ways), but not both. Count = 2³ × 3³ = 8 × 27 = 216.
- Reflexive and antisymmetric: the diagonal is forced to 1 (1 way), the pairs still have 3 ways: 3³ = 27.
A brute-force count over all 512 relations gives the same numbers.
Example 2: equivalence relations on a 4-element set. Count the equivalence relations on {1, 2, 3, 4} by the shape of the partition.
| Block sizes | How many partitions |
|---|---|
| 4 | 1 |
| 3 + 1 | C(4, 1) = 4 |
| 2 + 2 | C(4, 2)/2 = 3 |
| 2 + 1 + 1 | C(4, 2) = 6 |
| 1 + 1 + 1 + 1 | 1 |
Total B₄ = 1 + 4 + 3 + 6 + 1 = 15. Grouped by the number of blocks: S(4, 1) = 1, S(4, 2) = 4 + 3 = 7, S(4, 3) = 6, S(4, 4) = 1. The relation with blocks {1, 2}, {3}, {4} has 2² + 1 + 1 = 6 ordered pairs.
Example 3: the Hasse diagram of D36. Draw it, count the edges, and find the extremal elements of the subset {4, 6, 9}.
36
/ \
12 18
/ \ / \
4 6 9
\ / \ /
2 3
\ /
1
The 9 divisors 2i3j (0 ≤ i, j ≤ 2) form a 3 × 3 grid. Covering edges multiply by one prime: 6 edges for “× 2” and 6 for “× 3”, 12 in all. D36 has least element 1 and greatest element 36. For S = {4, 6, 9}: the upper bounds are the common multiples inside D36, which is only 36, so lub(S) = 36; the lower bounds are the common divisors, only 1, so glb(S) = 1. Inside S itself all three elements are both maximal and minimal (no two are comparable), so S is an antichain.
Example 4: onto functions. Count the surjections from A = {1, 2, 3, 4, 5} onto B = {x, y, z}.
- All functions: 3⁵ = 243.
- Functions missing a given element of B: 2⁵ = 32; there are C(3, 1) = 3 such elements.
- Functions missing two given elements: 1⁵ = 1; C(3, 2) = 3 choices.
- Inclusion–exclusion: 243 − 3 × 32 + 3 × 1 − 0 = 150.
Check: S(5, 3) = 25 partitions of A into 3 blocks, and 3! = 6 ways to assign the blocks to x, y, z: 25 × 6 = 150. The common wrong answer 243 − 3 = 240 subtracts only the constant functions.
Example 5: transitive closure with Warshall. R = {(1, 2), (2, 3), (3, 4)} on {1, 2, 3, 4}.
- k = 1: no pair ends at 1, nothing changes.
- k = 2: (1, 2) and (2, 3) give (1, 3).
- k = 3: (1, 3), (2, 3) with (3, 4) give (1, 4) and (2, 4).
- k = 4: no pair starts at 4, nothing changes.
R⁺ = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}: 6 pairs, exactly the strict order 1 < 2 < 3 < 4. Its reflexive-transitive closure adds the 4 loops and has 10 pairs.
Example 6: complements in divisor lattices. Compare D30 and D12.
D30: 30 = 2·3·5 is square-free. Each divisor a has complement 30/a: 2 and 15, 3 and 10, 5 and 6, 1 and 30. Every complement is unique, and D30 is isomorphic to P({2, 3, 5}): a Boolean algebra with 8 elements and a cube-shaped Hasse diagram (12 edges).
D12 = {1, 2, 3, 4, 6, 12}: 3 and 4 are complements (gcd 1, lcm 12), and 1 and 12 are complements, but 2 and 6 have none, because any b with lcm(2, b) = 12 is a multiple of 4 and then gcd(2, b) = 2. D12 is distributive but not complemented.
Formula and fact sheet
| Item | Result |
|---|---|
| |P(A)|, |A × B| | 2^n; |A|·|B| |
| |A ⊕ B| | |A| + |B| − 2|A ∩ B| |
| Relations from m-set to n-set | 2^(mn) |
| Reflexive / symmetric / antisymmetric (n-set) | 2^(n²−n) / 2^(n(n+1)/2) / 2^n·3^(n(n−1)/2) |
| Asymmetric; reflexive and symmetric | 3^(n(n−1)/2); 2^(n(n−1)/2) |
| Equivalence relations | Bell: 1, 2, 5, 15, 52, 203 (n = 1 to 6) |
| Partial orders (n = 1 to 4) | 1, 3, 19, 219 |
| S(n, k) | S(n − 1, k − 1) + k·S(n − 1, k); S(n, 2) = 2^(n−1) − 1 |
| Functions / injections / surjections | n^m / n!/(n − m)! / n!·S(m, n) |
| Binary operations on n-set; commutative | n^(n²); n^(n(n+1)/2) |
| Dn | τ(n) elements; join = lcm, meet = gcd; complemented ⇔ n square-free |
| Composition | g∘f injective ⇒ f injective; g∘f onto ⇒ g onto; (g∘f)⁻¹ = f⁻¹∘g⁻¹ |
NTA traps
- Antisymmetric as “not symmetric”. Wrong: a symmetric relation cannot be antisymmetric. Fix: the diagonal relation is both; 2^n relations are both.
- Forgetting vacuous truth. Wrong: the empty relation is not transitive. Fix: there are no pairs to break transitivity; it is symmetric, antisymmetric and transitive, but not reflexive on a non-empty set.
- Onto count. Wrong: n^m − n. Fix: use the full inclusion–exclusion or n!·S(m, n).
- Maximal versus greatest. Wrong: a poset with maximal elements 8, 9 and 12 has greatest element 12. Fix: a greatest element must be above everything; with several maximal elements there is none.
- Complement in Dn. Wrong: every element of D12 has complement 12/a. Fix: n/a is a complement only when gcd(a, n/a) = 1.
- Composition order. Wrong: (f ∘ g)(x) = g(f(x)). Fix: f ∘ g applies g first.
- Inverse of a composition. Wrong: (g ∘ f)⁻¹ = g⁻¹ ∘ f⁻¹. Fix: f⁻¹ ∘ g⁻¹.
- Power sets. Wrong: P(A ∪ B) = P(A) ∪ P(B). Fix: only the intersection law holds.
How NTA asks this
- Numerical MCQ: the number of relations, functions, onto functions or equivalence relations; |P(…)|; Hasse-diagram edges; lub and glb in Dn. Write the formula, then substitute; the distractors are usually the neighbouring formulas (2^(n²) instead of 2^(n²−n)).
- Match the following: relation types with their counts, example relations with their properties, functions with injective/surjective/bijective.
- Assertion–Reason and Statement I/II: complemented and distributive lattices, equivalence classes and partitions, finite versus infinite injections.
- Multiple select: properties of a given relation, set identities, composition facts.
- Order: ranking counts for a small n.
Mini-example (A-R). A: Every function from a finite set A to itself that is injective is also surjective. R: Every injective function from ℕ to ℕ is surjective. A is true (n distinct images inside an n-set fill it). R is false (n ↦ n + 1 misses 0). Answer: option 3.