The set of divisors of 12 under the relation "divides" is:

A lattice, with join = lcm and meet = gcd

A partial order but not a lattice

A lattice, with join = lcm and meet = gcd

Not a partial order, because divisibility is not antisymmetric

A relation R on a set A is antisymmetric if:

Whenever (a, b) and (b, a) are both in R, a = b

For no a, b are both (a, b) and (b, a) in R

Whenever (a, b) and (b, a) are both in R, a = b

Whenever (a, b) is in R, (b, a) is not

Let A be a set with 4 elements. Which of the following are correct? (More than one option may be correct.)

The power set of A has 16 elements

There are 2¹⁶ relations on A

There are 4! bijections from A to itself

The power set of A has 16 elements

There are 2¹⁶ relations on A

There are 16 equivalence relations on A

There are 4! bijections from A to itself

Sets, Relations, Functions, Partial Orders and Lattices

This is the counting chapter of the section, and the counts are worth memorising because deriving them under a clock is where the time goes. A relation on an n-element set is just a subset of the n² ordered pairs, so there are 2^(n²) relations in total — and each property fixes some of those pairs and leaves the rest free, which is where every other formula comes from. Reflexivity fixes the n diagonal pairs to 1, leaving n² − n free: 2^{(n² − n)} reflexive relations. Symmetry ties each off-diagonal pair to its mirror, leaving the n diagonal entries and the n(n − 1)/2 pairs above it free: 2^(n(n+1)/2) symmetric relations. Both formulas are the same idea — count the free choices — and a candidate who reconstructs them that way never has to remember which exponent goes with which. The one count that is not a power of two is the number of equivalence relations, because an equivalence relation on a set is the same thing as a partition of it: they are the Bell numbers, and on three elements there are 5, not 8. That correspondence is the most useful single fact in the chapter, and it is why "how many equivalence relations" and "how many ways to partition" are the same question wearing different clothes. On the order side, a partial order is reflexive, antisymmetric and transitive, and a lattice is a partial order in which every pair of elements has both a least upper bound and a greatest lower bound. The divisors of a number under divisibility are the standard example and the one GATE keeps setting: for 12, the lub is the lcm and the glb is the gcd, both of which stay inside the set, so it is a lattice. Antisymmetry is the condition candidates misread most: it does not forbid a ≤ b and b ≤ a, it says that when both hold, a and b are the same element.

Counting Relations by Counting Free Choices

On a set of n elements, and worked at n = 3
Kind	Count, and where it comes from	At n = 3
All relations	2^(n²) — every one of the n² ordered pairs is in or out	2⁹ = 512
Reflexive	2^{(n² − n)} — the n diagonal pairs are forced in, the rest are free	2⁶ = 64
Symmetric	2^(n(n+1)/2) — the diagonal plus one of each mirror pair is free	2⁶ = 64 (a coincidence at n = 3; the two formulas differ elsewhere)
Reflexive and symmetric	2^(n(n−1)/2) — only the pairs above the diagonal are free	2³ = 8
Equivalence	The Bell number Bₙ — not a power of two, because transitivity is not a per-pair condition	B₃ = 5 (and B₄ = 15)

🎯 Why an equivalence relation is a partition

Reflexivity puts every element in its own class, symmetry makes the classes mutual, and transitivity welds overlapping classes into one. What is left is a family of non-empty, disjoint blocks covering the set — a partition. The correspondence runs both ways and loses nothing, so counting equivalence relations is counting partitions, and that is why the answer is a Bell number rather than a power of two. For a three-element set the five partitions are: all three together; each element alone; and the three ways to pair two elements and leave one out. Enumerating those five by hand is faster than any formula, and it is the check to run when a question gives a small set.

Functions — Three Counts

All functions from an m-set to an n-set: nᵐ. Each of the m inputs independently picks one of n outputs. From a 3-set to a 2-set that is 2³ = 8. Note which letter is the exponent — the domain size is up top, and reversing it is the standard slip.
Injections (one-to-one): n·(n − 1)···(n − m + 1). Each input takes a fresh output, so the choices run down. From a 2-set to a 4-set: 4 × 3 = 12. There are none at all when m > n, which is the pigeonhole principle stated as a count.
Surjections (onto) need inclusion–exclusion. Onto a 2-set from an m-set it is 2ᵐ − 2, since the two constant functions are the only ones that miss a value: from a 3-set that is 8 − 2 = 6, and from a 4-set 16 − 2 = 14. For a larger codomain the general form is a sum with alternating signs, and GATE keeps the codomain small precisely so the subtraction stays visible.
A bijection needs m = n, and then there are n! of them. On a finite set of equal sizes, injective, surjective and bijective coincide — a fact that is false for infinite sets and is asked about precisely because of that.

Partial Orders and Lattices

A partial order is reflexive, antisymmetric and transitive. Antisymmetry is the condition to read carefully: it says that if a ≤ b and b ≤ a then a = b, which does not forbid the two-way case but restricts it to an element and itself. A partial order becomes a lattice when every pair has a least upper bound (join) and a greatest lower bound (meet); it is a total order when every two elements are comparable, which is a much stronger condition and rare in the examples GATE sets.

🧠 The divisors of n under divisibility are the example to know

Take the divisors of 12 — {1, 2, 3, 4, 6, 12} — ordered by "divides". Reflexive (every number divides itself), antisymmetric (if a divides b and b divides a then a = b, for positive integers), transitive. The join of two divisors is their lcm and the meet is their gcd, and for divisors of a fixed n both stay among the divisors of n — so it is a lattice, with 1 at the bottom and n at the top. The divisor lattice of 30 has 8 elements and is the Boolean lattice on the three primes 2, 3 and 5, which is why questions about D₃₀ and questions about the power set of a 3-set have the same answers.

Key takeaways

Count relations by counting free pairs: 2^(n²) in all, 2^{(n² − n)} reflexive, 2^(n(n+1)/2) symmetric. Reconstructing them beats remembering them.
Equivalence relations are partitions, so their count is a Bell number and not a power of two: 5 on a 3-set, 15 on a 4-set.
Functions from an m-set to an n-set number nᵐ — the domain size is the exponent, and reversing it is the standard slip.
Injections run n(n−1)···(n−m+1) and vanish when m > n, which is the pigeonhole principle as a count. Onto a 2-set there are 2ᵐ − 2.
A partial order is reflexive, antisymmetric and transitive. Antisymmetry restricts the two-way case to an element and itself; it does not forbid it.
A lattice needs a join and a meet for every pair. For the divisors of n these are lcm and gcd, both of which stay inside the set.
The divisor lattice of a product of k distinct primes is the Boolean lattice on k elements — D₃₀ and the power set of a 3-set answer alike.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

The number of reflexive relations on a set of 3 elements is:
1. 8
2. 64
3. 512
4. 5
Show answer
Answer: B — 64
There are 3² = 9 ordered pairs. Reflexivity forces the 3 diagonal pairs to be present, leaving 9 − 3 = 6 pairs each free to be in or out: 2⁶ = 64. Enumerating all 512 relations and filtering gives 64 as well, which is how the figure in this chapter was checked. Option C is the total number of relations, 2⁹, and option D is the number of equivalence relations on three elements — both appear as distractors in this family, so read which property was asked. The general formula 2^{(n² − n)} is worth reconstructing rather than memorising: fix what the property forces, count what is left free.
The number of equivalence relations on the set {a, b, c} is:
1. 5
2. 8
3. 64
4. 512
Show answer
Answer: A — 5
An equivalence relation on a set is exactly a partition of it, so count the partitions of three elements: all three in one block; each element alone; and the three ways to put two together and leave one out. That is 1 + 1 + 3 = 5, the Bell number B₃, and enumerating all 512 relations and filtering by all three properties returns 5. Options B, C and D are powers of two, and the point of the question is that this count is not one: reflexivity and symmetry are per-pair conditions and multiply into a power of two, but transitivity is not — it constrains triples, so it cannot be counted by free choices. For four elements the answer is 15, not 16.
The number of onto (surjective) functions from a set of 4 elements to a set of 2 elements is:
1. 16
2. 14
3. 8
4. 12
Show answer
Answer: B — 14
There are 2⁴ = 16 functions in all. A function fails to be onto only by missing one of the two outputs, and the only ways to do that are the two constant functions. So 16 − 2 = 14. Option A is the total, offered because forgetting the surjectivity condition is the whole error available here. Option D is the number of injections from a 2-set to a 4-set, which is the mirror-image question — from a 4-set to a 2-set there are no injections at all, because 4 > 2 and the pigeonhole principle forbids them. Notice the direction of the arrow before choosing a formula: onto and one-to-one point opposite ways, and the option list will usually contain both answers.
The set of divisors of 12 under the relation "divides" is:
1. A partial order but not a lattice
2. A lattice, with join = lcm and meet = gcd
3. A total order
4. Not a partial order, because divisibility is not antisymmetric
Show answer
Answer: B — A lattice, with join = lcm and meet = gcd
Divisibility on the positive integers is reflexive, antisymmetric and transitive, so this is a partial order — and for the divisors {1, 2, 3, 4, 6, 12} the lcm and gcd of any two members are themselves divisors of 12, so every pair has a join and a meet: it is a lattice. Option C fails because 2 and 3 are incomparable — neither divides the other — and a total order requires every pair to be comparable. Option D is a real trap worth pausing on: divisibility on the positive integers is antisymmetric, since a | b and b | a force a = b; it stops being antisymmetric once negatives are allowed, where 2 and −2 divide each other without being equal. The domain is part of the claim.
A relation R on a set A is antisymmetric if:
1. For no a, b are both (a, b) and (b, a) in R
2. Whenever (a, b) and (b, a) are both in R, a = b
3. Whenever (a, b) is in R, (b, a) is not
4. R contains no pair (a, a)
Show answer
Answer: B — Whenever (a, b) and (b, a) are both in R, a = b
Antisymmetry permits the two-way case and restricts it: if both directions hold, the two elements are the same. That is what lets a partial order be reflexive at the same time, since (a, a) going both ways is no contradiction. Options A and C describe asymmetry, a strictly stronger condition that rules out (a, a) entirely and is therefore incompatible with reflexivity — and mistaking one for the other is the reason candidates conclude that ≤ on the integers is not antisymmetric. Option D is the definition of an irreflexive relation, a different property again. Divisibility, ≤ and set inclusion are all antisymmetric and all reflexive, and each of the three is a standard example in this topic.
Let A be a set with 4 elements. Which of the following are correct? (More than one option may be correct.)
1. The power set of A has 16 elements
2. There are 2¹⁶ relations on A
3. There are 16 equivalence relations on A
4. There are 4! bijections from A to itself
Show answer
Answer: A — The power set of A has 16 elements; B — There are 2¹⁶ relations on A; D — There are 4! bijections from A to itself
Three of the four hold. The power set of an n-set has 2ⁿ members, so 2⁴ = 16 — option A. A relation is a subset of the 4² = 16 ordered pairs, so there are 2¹⁶ of them — option B. And a bijection from a finite set to itself is a permutation, so there are 4! = 24 — option D. Option C is the trap and the reason this is an MSQ: the number of equivalence relations is the Bell number B₄ = 15, not 16. Fifteen and sixteen are one apart, the surrounding options are all powers of two, and a candidate moving quickly will assume this count follows the same pattern. It does not, because transitivity constrains triples rather than pairs — the one structural fact this chapter keeps returning to.
The number of symmetric relations on a set of 3 elements is _____.
Numerical answer — type the value.
Show answer
Answer: 64
Symmetry ties (a, b) to (b, a), so the free choices are the 3 diagonal entries plus one from each of the 3 mirror pairs above the diagonal: 3 + 3 = 6 free choices, giving 2⁶ = 64. The general formula is 2^(n(n+1)/2), and n(n + 1)/2 is exactly the count of cells on and above the diagonal. Enumerating all 512 relations and filtering for symmetry returns 64, which is how this was checked. Note that 64 is also the number of reflexive relations on three elements — a coincidence at n = 3, where n² − n and n(n + 1)/2 are both 6, and one that stops at n = 4, where they are 12 and 10. A question set at n = 4 is often set there for exactly that reason.
The number of elements in the divisor lattice of 30 (the divisors of 30 ordered by divisibility) is _____.
Numerical answer — type the value.
Show answer
Answer: 8
30 = 2 × 3 × 5, three distinct primes each to the first power, so a divisor is any subset of those primes: 2³ = 8 of them — 1, 2, 3, 5, 6, 10, 15, 30. That correspondence is the useful part: the divisor lattice of a product of k distinct primes is the Boolean lattice on k elements, so a question about D₃₀ and a question about the power set of a 3-set have the same answer, the same Hasse diagram and the same height. In general the number of divisors of n = p₁^a₁···p_k^a_k is (a₁ + 1)···(a_k + 1), which gives 8 here and 6 for 12 = 2² × 3. As a numerical-answer question this carries no negative marking, so it should never be left blank.