Sets, Relations & Functions
Complete Guide for GATE CS — Set Theory, Relation Properties, Equivalence Classes, POSETs & Function Types
Last Updated: April 2026
📌 Key Takeaways
- Set: An unordered collection of distinct objects. If |A| = n, the power set |P(A)| = 2n and total relations on A = 2n².
- Relation properties: Reflexive (every element related to itself), Symmetric (aRb ⟹ bRa), Antisymmetric (aRb ∧ bRa ⟹ a = b), Transitive (aRb ∧ bRc ⟹ aRc).
- Equivalence relation: Reflexive + Symmetric + Transitive → partitions the set into disjoint equivalence classes.
- Partial order (POSET): Reflexive + Antisymmetric + Transitive → not all elements need to be comparable. If all elements are comparable, it is a total order.
- Function types: Injective (one-to-one, no two inputs share output), Surjective (onto, every output is covered), Bijective (both) → only bijections have inverses.
- Composition: (g ∘ f)(x) = g(f(x)) — apply f first, then g. Composition of bijections is bijective.
- GATE CS typically tests: counting relations with given properties, identifying function types, equivalence class problems, and POSET/Hasse diagram questions — typically 1–2 marks per paper.
1. Sets — Notation, Types & Power Set
A set is a well-defined, unordered collection of distinct objects called elements or members. Sets are typically denoted by capital letters (A, B, S) and their elements by curly braces: A = {1, 2, 3}.
1.1 Set Notation
| Notation | Meaning | Example |
|---|---|---|
| x ∈ A | x is an element of A | 3 ∈ {1,2,3} |
| x ∉ A | x is NOT an element of A | 4 ∉ {1,2,3} |
| A ⊆ B | A is a subset of B (every element of A is in B) | {1,2} ⊆ {1,2,3} |
| A ⊂ B | A is a proper subset of B (A ⊆ B and A ≠ B) | {1,2} ⊂ {1,2,3} |
| |A| | Cardinality — number of elements in A | |{a,b,c}| = 3 |
| ∅ or {} | Empty set — no elements | |∅| = 0 |
1.2 Special Sets
| Set | Name | Description |
|---|---|---|
| ∅ | Empty Set / Null Set | Contains no elements. ∅ ⊆ every set. |
| U | Universal Set | Contains all elements under discussion. |
| ℕ | Natural Numbers | {0, 1, 2, 3, …} or {1, 2, 3, …} (context-dependent) |
| ℤ | Integers | {…, -2, -1, 0, 1, 2, …} |
| P(A) | Power Set of A | Set of ALL subsets of A |
| A × B | Cartesian Product | Set of all ordered pairs (a, b) where a ∈ A, b ∈ B |
Power Set & Cartesian Product Sizes
If |A| = m and |B| = n:
|P(A)| = 2m (number of all subsets of A, including ∅ and A itself)
|A × B| = m × n (number of ordered pairs)
|A × A| = m² (number of possible ordered pairs from A to A)
Example: A = {1, 2, 3} → |P(A)| = 2³ = 8, |A × A| = 9
2. Set Operations
| Operation | Symbol | Definition | Example (A={1,2,3}, B={2,3,4}) |
|---|---|---|---|
| Union | A ∪ B | All elements in A or B (or both) | {1,2,3,4} |
| Intersection | A ∩ B | Elements in both A and B | {2,3} |
| Difference | A − B (or A \ B) | Elements in A but not in B | {1} |
| Complement | A’ or Ā | Elements in U not in A | U − A |
| Symmetric Difference | A ⊕ B | (A − B) ∪ (B − A) — elements in exactly one of A or B | {1,4} |
Key Identities (GATE Favorites)
De Morgan’s Laws:
(A ∪ B)’ = A’ ∩ B’ | (A ∩ B)’ = A’ ∪ B’
Inclusion-Exclusion (2 sets):
|A ∪ B| = |A| + |B| − |A ∩ B|
Inclusion-Exclusion (3 sets):
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |B∩C| − |A∩C| + |A∩B∩C|
Symmetric Difference:
A ⊕ B = (A ∪ B) − (A ∩ B) | |A ⊕ B| = |A| + |B| − 2|A ∩ B|
3. Relations — Definition & Representation
A binary relation R from set A to set B is a subset of the Cartesian product A × B. If (a, b) ∈ R, we write aRb and say “a is related to b.”
A relation on A (or relation from A to A) is a subset of A × A.
Counting Relations on a Set A with |A| = n
Total ordered pairs in A × A = n²
Total number of relations on A = 2n²
Example: |A| = 3 → 2⁹ = 512 possible relations on A
3.1 Representing Relations
A relation can be represented as:
- Set of ordered pairs: R = {(1,1), (1,2), (2,2), (3,3)}
- Relation matrix (Boolean matrix): M[i][j] = 1 if (ai, aj) ∈ R, else 0
- Directed graph (digraph): Nodes represent elements; directed edge a→b if (a,b) ∈ R
4. Relation Properties
| Property | Definition | Matrix Test | Digraph Test |
|---|---|---|---|
| Reflexive | ∀a ∈ A: (a,a) ∈ R | All diagonal entries = 1 | Self-loop at every node |
| Irreflexive | ∀a ∈ A: (a,a) ∉ R | All diagonal entries = 0 | No self-loops anywhere |
| Symmetric | aRb ⟹ bRa | Matrix = its own transpose (M = Mᵀ) | Every edge has reverse edge |
| Antisymmetric | aRb ∧ bRa ⟹ a = b | M[i][j]=1 ∧ M[j][i]=1 only on diagonal | No pair of opposite edges between distinct nodes |
| Asymmetric | aRb ⟹ ¬(bRa) | Irreflexive + Antisymmetric | No self-loops; no pair of opposite edges |
| Transitive | aRb ∧ bRc ⟹ aRc | M² ≤ M (Boolean) | Shortcut exists for every 2-step path |
Counting Relations with Specific Properties (n-element set)
Reflexive relations: 2n²−n (diagonal is fixed to 1; choose freely from n²−n off-diagonal)
Symmetric relations: 2n(n+1)/2 (diagonal + upper triangle fixed; lower mirrors upper)
Reflexive + Symmetric: 2n(n−1)/2 (diagonal fixed to 1; choose upper triangle freely)
Antisymmetric relations: 2n × 3n(n−1)/2
For each off-diagonal pair {i,j}: either (i,j) ∈ R only, or (j,i) ∈ R only, or neither — 3 choices. Diagonal: 2 choices each (n elements).
4.1 Transitive Closure
The transitive closure R⁺ of a relation R is the smallest transitive relation containing R. It is computed by Warshall’s algorithm (similar to Floyd-Warshall for shortest paths):
Starting with M (the relation matrix), for each intermediate vertex k: M[i][j] = M[i][j] OR (M[i][k] AND M[k][j])
5. Equivalence Relations & Equivalence Classes
A relation R on set A is an equivalence relation if and only if it is:
- Reflexive: aRa for all a ∈ A
- Symmetric: aRb ⟹ bRa
- Transitive: aRb ∧ bRc ⟹ aRc
An equivalence relation partitions the set A into disjoint, non-empty subsets called equivalence classes. The equivalence class of element a is: [a] = {x ∈ A | xRa}
Partition Properties
Every equivalence relation on A corresponds to exactly one partition of A, and vice versa.
The equivalence classes are: disjoint (no overlap), non-empty, and their union equals A.
Number of equivalence relations on a set of n elements = Bell number B(n)
B(1)=1, B(2)=2, B(3)=5, B(4)=15, B(5)=52
Each Bell number equals the number of ways to partition n elements into non-empty subsets.
5.1 Common Equivalence Relations in CS
| Relation | On Set | Description |
|---|---|---|
| a ≡ b (mod m) | ℤ | Congruence modulo m — a and b leave same remainder when divided by m |
| Strings with same length | Σ* | All strings of length k form one equivalence class |
| Graph isomorphism | Graphs | Two graphs in same class if isomorphic to each other |
| Same DFA-recognizable language | DFAs | Used in Myhill-Nerode theorem (TOC) |
6. Partial Order & Hasse Diagrams (POSET)
A relation R on set A is a partial order if it is Reflexive, Antisymmetric, and Transitive. The pair (A, R) is called a Partially Ordered Set (POSET).
| Type | Properties | All Elements Comparable? | Example |
|---|---|---|---|
| Partial Order (POSET) | Reflexive + Antisymmetric + Transitive | Not necessarily | (℘({a,b,c}), ⊆) |
| Total Order (Chain) | Partial Order + every pair is comparable | Yes | (ℤ, ≤) |
| Strict Partial Order | Irreflexive + Antisymmetric + Transitive | Not necessarily | (ℕ, <) |
6.1 Hasse Diagram
A Hasse diagram is a simplified diagram of a POSET that removes:
- Self-loops (reflexivity is implied)
- Edges implied by transitivity (if a < b < c, the edge a→c is omitted)
- Arrows (direction is implied by “upward” position — greater elements are drawn higher)
6.2 Special Elements in a POSET
| Element | Definition | Note |
|---|---|---|
| Maximal | No element is greater than it | May be multiple; need not be unique |
| Minimal | No element is less than it | May be multiple; need not be unique |
| Greatest (Maximum) | Greater than ALL other elements | Unique if exists |
| Least (Minimum) | Less than ALL other elements | Unique if exists |
| Upper Bound of S | An element u: ∀x ∈ S, x ≤ u | May not exist |
| Least Upper Bound (LUB/Join) | Smallest of all upper bounds of S | Used in Lattice theory |
| Lower Bound of S | An element l: ∀x ∈ S, l ≤ x | May not exist |
| Greatest Lower Bound (GLB/Meet) | Largest of all lower bounds of S | Used in Lattice theory |
Lattice
A POSET is a Lattice if every pair of elements has both a LUB (join, ∨) and a GLB (meet, ∧).
Example: (P(A), ⊆) is a lattice — join = ∪, meet = ∩.
Example: Divisors of 12 under divisibility = {1,2,3,4,6,12} is a lattice — join = LCM, meet = GCD.
7. Functions — Types & Counting
A function f: A → B is a relation from A to B such that every element of A (the domain) is related to exactly one element of B (the codomain). The set of all actual output values is the range (range ⊆ codomain).
| Type | Condition | Also Called | Inverse Exists? |
|---|---|---|---|
| Injective | f(a₁)=f(a₂) ⟹ a₁=a₂ (no two inputs share an output) | One-to-one | Only if also surjective |
| Surjective | ∀b ∈ B, ∃a ∈ A: f(a)=b (every output is hit) | Onto | Only if also injective |
| Bijective | Both injective and surjective | One-to-one correspondence | Yes — always |
| Total Function | Every element of domain A has an image | (Standard definition) | — |
| Partial Function | Some elements of A may have no image | — | — |
Counting Functions from A to B (|A|=m, |B|=n)
Total functions: nm (each of m elements has n choices)
Injective functions: n × (n−1) × (n−2) × … × (n−m+1) = P(n, m) = n! / (n−m)! (requires n ≥ m)
Surjective functions: Inclusion-exclusion: ∑k=0n (−1)k C(n,k) (n−k)m
Bijective functions: n! (requires n = m)
8. Composition & Inverse Functions
8.1 Composition of Functions
If f: A → B and g: B → C, the composition (g ∘ f): A → C is defined as:
Composition Rule
(g ∘ f)(x) = g(f(x))
Apply f first, then apply g to the result.
Note: g ∘ f ≠ f ∘ g in general (composition is not commutative).
Composition IS associative: h ∘ (g ∘ f) = (h ∘ g) ∘ f
If f and g are both bijective, then g ∘ f is bijective.
If g ∘ f is injective, then f must be injective.
If g ∘ f is surjective, then g must be surjective.
8.2 Inverse Function
A function f: A → B has an inverse f⁻¹: B → A if and only if f is bijective. The inverse satisfies: f⁻¹(f(a)) = a and f(f⁻¹(b)) = b for all a ∈ A, b ∈ B.
8.3 Composition of Relations
If R ⊆ A × B and S ⊆ B × C, the composition S ∘ R ⊆ A × C is:
S ∘ R = {(a, c) | ∃b ∈ B: (a, b) ∈ R and (b, c) ∈ S}
In matrix form: MS∘R = MR · MS (Boolean matrix multiplication)
9. Worked Examples (GATE CS Level)
Example 1 — Counting Relations with Properties
Problem: Let A = {1, 2, 3, 4}. How many relations on A are (a) reflexive? (b) symmetric? (c) both reflexive and symmetric? (d) antisymmetric?
Solution: |A| = n = 4. Total pairs in A × A = n² = 16. Diagonal pairs (self-loops): n = 4. Off-diagonal pairs: n² − n = 12.
(a) Reflexive relations:
All 4 diagonal pairs MUST be included (no choice). The remaining 12 off-diagonal pairs can be freely included or excluded.
Reflexive relations = 2n²−n = 212 = 4096
(b) Symmetric relations:
The 4 diagonal entries can each be 0 or 1 (4 free choices). For the 12 off-diagonal entries, they come in 6 symmetric pairs {(i,j),(j,i)} — each pair can independently be both-in or both-out (2 choices per pair).
Symmetric relations = 2n × 2n(n−1)/2 = 24 × 26 = 210 = 1024
General formula: 2n(n+1)/2 = 24×5/2 = 210 = 1024 ✓
(c) Reflexive + Symmetric:
Diagonal entries are all 1 (fixed). Only the 6 symmetric off-diagonal pairs are free (2 choices each).
Reflexive + Symmetric = 2n(n−1)/2 = 26 = 64
(d) Antisymmetric relations:
Diagonal: 2 choices each (4 entries → 2⁴ = 16 ways). For each off-diagonal pair {(i,j),(j,i)}: either (i,j) ∈ R only, or (j,i) ∈ R only, or neither (but NOT both) → 3 choices for each of the 6 pairs.
Antisymmetric relations = 2n × 3n(n−1)/2 = 24 × 36 = 16 × 729 = 11,664
Example 2 — Equivalence Classes & Partition
Problem: Consider the relation R on ℤ defined by: aRb if and only if (a − b) is divisible by 5 (i.e., a ≡ b (mod 5)). (a) Verify R is an equivalence relation. (b) List all equivalence classes. (c) How many equivalence classes does R define on {0, 1, 2, …, 14}?
Solution:
(a) Verification:
- Reflexive: a − a = 0, and 5 | 0 ✓ → aRa for all a ∈ ℤ
- Symmetric: If 5 | (a−b), then 5 | (−(a−b)) = (b−a) ✓ → aRb ⟹ bRa
- Transitive: If 5 | (a−b) and 5 | (b−c), then 5 | ((a−b)+(b−c)) = (a−c) ✓ → aRb ∧ bRc ⟹ aRc
All three properties hold → R is an equivalence relation.
(b) Equivalence classes on ℤ (5 classes total):
| Class | Representative | Members (residue mod 5) |
|---|---|---|
| [0] | 0 | {…, −10, −5, 0, 5, 10, 15, …} |
| [1] | 1 | {…, −9, −4, 1, 6, 11, 16, …} |
| [2] | 2 | {…, −8, −3, 2, 7, 12, 17, …} |
| [3] | 3 | {…, −7, −2, 3, 8, 13, 18, …} |
| [4] | 4 | {…, −6, −1, 4, 9, 14, 19, …} |
(c) On {0, 1, 2, …, 14}: The 15 elements partition into 5 equivalence classes (one for each residue 0–4), each containing exactly 3 elements: {0,5,10}, {1,6,11}, {2,7,12}, {3,8,13}, {4,9,14}.
Answer: 5 equivalence classes, each of size 3. Partition: {{0,5,10},{1,6,11},{2,7,12},{3,8,13},{4,9,14}}
Example 3 — Function Types & Counting
Problem: Let A = {1, 2, 3} and B = {a, b, c, d}. (a) How many total functions exist from A to B? (b) How many are injective? (c) Can any function from A to B be surjective? Why? (d) Let f: A→A be defined by f(1)=2, f(2)=3, f(3)=1. Is f bijective? Find f ∘ f.
Solution: |A| = m = 3, |B| = n = 4.
(a) Total functions from A to B:
Total = nm = 43 = 64
(b) Injective functions from A to B:
First element: 4 choices. Second element: must differ → 3 choices. Third: must differ from both → 2 choices.
Injective = P(4,3) = 4 × 3 × 2 = 24
(c) Surjective from A to B?
Surjective requires every element of B to be covered. But |A| = 3 < |B| = 4 — with only 3 inputs, at most 3 outputs can be reached, so at least one element of B is always uncovered.
No surjective function from A to B is possible when |A| < |B|.
Surjection requires |A| ≥ |B|. Injection requires |A| ≤ |B|. Bijection requires |A| = |B|.
(d) f(1)=2, f(2)=3, f(3)=1 — is it bijective?
- Injective? f(1)=2, f(2)=3, f(3)=1 — all outputs distinct ✓
- Surjective? Range = {1,2,3} = A = codomain ✓
Yes, f is bijective (it is a cyclic permutation: 1→2→3→1).
f ∘ f: (f ∘ f)(x) = f(f(x))
- (f∘f)(1) = f(f(1)) = f(2) = 3
- (f∘f)(2) = f(f(2)) = f(3) = 1
- (f∘f)(3) = f(f(3)) = f(1) = 2
f ∘ f: 1→3, 2→1, 3→2 (another cyclic permutation, also bijective)
f ∘ f ∘ f = identity: 1→1, 2→2, 3→3 (since f is a 3-cycle, f³ = identity)
10. 5 Common Mistakes in Sets, Relations & Functions
Mistake 1 — Confusing Antisymmetric with “Not Symmetric”
What happens: Students eliminate a relation as non-antisymmetric if it lacks symmetry, or think antisymmetric = opposite of symmetric.
Root cause: The terms sound like opposites but are not. A relation can be BOTH symmetric and antisymmetric (e.g., equality on A: only {(a,a)} pairs). A relation can also be NEITHER symmetric nor antisymmetric.
Correct approach: Antisymmetric means: if (a,b) ∈ R AND (b,a) ∈ R, THEN a = b. It does NOT forbid all pairs like (a,b) — it forbids both directions for distinct elements.
Mistake 2 — Forgetting the Empty Relation is Transitive (and Symmetric)
What happens: Students say the empty relation ∅ on A is not transitive or not symmetric because “there are no pairs to check.”
Root cause: Vacuous truth — when the antecedent of a conditional is never satisfied, the conditional is true by default.
Correct approach: ∅ is symmetric (no pairs exist to violate symmetry), transitive (no pairs exist to form a counterexample), and antisymmetric — but NOT reflexive (unless A = ∅).
Mistake 3 — Overcounting Injective Functions
What happens: For injective f: A → B, students compute nm (total functions) or n! (instead of P(n,m)).
Root cause: Forgetting that injection means once an output is used, it cannot be reused — so it’s sampling without replacement.
Correct approach: Injective functions = P(n, m) = n!/(n−m)! = n × (n−1) × … × (n−m+1), valid only when n ≥ m.
Mistake 4 — Confusing Maximal with Maximum Elements in a POSET
What happens: Students say a POSET has a “maximum” when it actually only has a “maximal” element.
Root cause: A maximum element must be ≥ ALL other elements. A maximal element just has no element above it — but other maximal elements may be incomparable to it.
Correct approach: In a POSET, there can be multiple maximal elements (all incomparable to each other). A maximum element is a maximal element that also dominates all others — it is unique if it exists.
Mistake 5 — Applying Composition in the Wrong Order
What happens: For (g ∘ f)(x), students apply g first and then f.
Root cause: The notation g ∘ f reads “g after f” — but visually, g appears first on the left.
Correct approach: (g ∘ f)(x) = g(f(x)) — apply f first (the rightmost function), then apply g. Think: “inside out” or “right to left.”
11. Frequently Asked Questions
Q1. What is the difference between a relation and a function?
A relation R from A to B is any subset of A × B — there is no restriction on how many elements of B each element of A can map to (or whether it maps to any at all). A function is a special relation with the constraint that every element of the domain A maps to exactly one element in the codomain B — no element is unmapped, and no element maps to two different outputs. Formally: f is a function iff for all a ∈ A, there exists a unique b ∈ B with (a, b) ∈ f. This means all functions are relations, but most relations are not functions.
Q2. How many relations are possible on a set with n elements?
A set A with n elements has n² ordered pairs in A × A (the Cartesian product). A relation on A is any subset of A × A. Since each of the n² pairs can independently be included (1) or excluded (0), the total number of distinct relations on A is 2n². For example: n=1 → 2 relations; n=2 → 16 relations; n=3 → 512 relations; n=4 → 65,536 relations.
Q3. What is the difference between equivalence relation and partial order?
Both are special types of relations, but they have different properties and different purposes. An equivalence relation is Reflexive + Symmetric + Transitive — it classifies elements into groups (equivalence classes) that are interchangeable with respect to some property (like congruence mod n, or “same degree” in a graph). A partial order is Reflexive + Antisymmetric + Transitive — it establishes a ranking or hierarchy, but not all elements need to be comparable (e.g., subsets under ⊆: {1} and {2} are not comparable). If all elements ARE comparable under a partial order, it becomes a total order (like ≤ on integers).
Q4. What is the power set of a set with n elements?
The power set P(A) of a set A is the set of ALL subsets of A, including the empty set ∅ and A itself. If |A| = n, then |P(A)| = 2n, because each element can independently be included or excluded from a subset. For example: A = {a, b, c} has P(A) = {∅, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}} with 2³ = 8 elements. This is a crucial formula in GATE CS for counting problems — power sets appear in automata theory (subset construction for NFA→DFA), database theory (functional dependencies), and algorithm analysis (subset-sum, backtracking complexity).