Every introductory chapter on relations sneaks in a counting question: "how many relations can you form on a set with n elements?" The answer — 2^{n^2} — is one of those numbers that feels too big to be right. For n = 5, it is 2^{25} = 33{,}554{,}432 relations. For n = 10, it is 2^{100}, which is more than the number of atoms in a human body. The count is correct, and the why is a clean two-step argument that also locks in the formula for general relations from A to B.

The two-step count

Here is the argument in its simplest form.

The $2^{n^2}$ count

Let A be a set with n elements. The number of relations on A is

2^{n^2}

because (a) a relation on A is a subset of A \times A, (b) A \times A has n \cdot n = n^2 ordered pairs, and (c) a set with k elements has 2^k subsets.

Steps (a), (b), (c) are each standard results. The trick is seeing how they compose.

Step 1: a relation is a subset

The definition says a relation on A is any subset of A \times A. That is not a property of a relation — it is literally what a relation is. So counting relations means counting subsets of A \times A. You do not need to worry about properties like reflexivity or symmetry at this stage; every subset, however weird, is a valid relation.

Step 2: the Cartesian product has n^2 elements

For every ordered pair (a, b) \in A \times A, the first coordinate a can be any of the n elements of A and the second coordinate b can independently be any of the n elements. So the number of ordered pairs is

n \cdot n = n^2

This is just the "row times column" count of a square grid. Laying A along both axes gives an n \times n grid with n^2 cells — one cell per ordered pair.

A by A grid showing n squared pairsA 4 by 4 grid of cells with rows labelled 1, 2, 3, 4 and columns also labelled 1, 2, 3, 4. Each of the 16 cells contains a small dot representing an ordered pair. The caption notes that A times A has 4 squared equals 16 pairs. b a 1 2 3 4 1 2 3 4 |A × A| = 4 × 4 = 16 cells — a relation picks any subset of these 16
For $A = \{1, 2, 3, 4\}$, the product $A \times A$ has $16 = 4^2$ ordered pairs, one per cell. A relation is any subset of these $16$ cells. With $16$ cells, the number of distinct subsets is $2^{16} = 65{,}536$.

Step 3: each cell is an independent in/out choice

For every cell in the grid, you have a binary choice: include this pair in your relation, or do not.

Each choice is independent of the others — there is no constraint forcing one pair in or out based on the others (you are counting all relations, not just equivalence relations or functions). So by the multiplication principle:

\underbrace{2 \cdot 2 \cdot 2 \cdots 2}_{n^2 \text{ factors}} = 2^{n^2}

distinct ways to pick your subset. This matches the general fact that a set with k elements has 2^k subsets — here k = n^2.

Interactive: watch the count explode

Interactive relation count for small nA horizontal slider from 1 to 6 with a draggable red point. The readout shows the current n value from 1 to 6 and the corresponding count 2 to the power of n squared, ranging from 2 to over 68 billion. The caption explains the explosive growth. n=1 → 2 n=2 → 16 n=3 → 512 n=4 → 65536 n=5 → 33.5M n=6 → 68.7B every extra element quadruples the exponent drag to see how the count grows
The count $2^{n^2}$ grows very fast. Going from $n = 5$ to $n = 6$ multiplies the count by $2^{11} = 2048$, not by $2$. For $n = 10$, the number of relations is $2^{100}$, which has $31$ digits — more than the number of grains of sand on Earth.

The general formula for relations from A to B

The same argument gives the count for relations between two (possibly different) sets.

If |A| = m and |B| = n, then A \times B has mn ordered pairs, and the number of subsets is 2^{mn}.

So a relation from A to B — with |A| = m and |B| = n — is one of 2^{mn} possibilities. When A = B and m = n, this collapses to 2^{n \cdot n} = 2^{n^2}.

Summary table:

Setup Number of relations
From A (size m) to B (size n) 2^{mn}
On A (size n) 2^{n^2}
On A (size n), reflexive 2^{n^2 - n}
On A (size n), symmetric 2^{n(n+1)/2}

The last two are what you would count after imposing a property — interesting, but not the base count 2^{n^2} that the chapter asks for first.

The common error: 2^n instead of 2^{n^2}

Students sometimes write 2^n for the number of relations on a set of n elements. The mistake is forgetting step 2 — confusing the number of elements in A (which is n) with the number of pairs in A \times A (which is n^2).

A set of subsets of A has 2^n members. A set of subsets of A \times A has 2^{n^2} members. The distinction shows up whenever the ambient set is itself a Cartesian product.

Why the right size is n^2: each ordered pair has two independent slots, each with n choices. It is like counting the cars on a chessboard — there are 8 \times 8 = 64 squares, not 8. A relation picks squares, not rows.

Sanity check: n = 1 and n = 2

Always try tiny cases to trust a formula.

n = 1: A = \{a\}. Then A \times A = \{(a, a)\}, a one-element set. Its subsets are \varnothing and \{(a, a)\} — exactly 2. Formula: 2^{1^2} = 2^1 = 2. Match.

n = 2: A = \{a, b\}. Then A \times A has 4 pairs: (a,a), (a,b), (b,a), (b,b). Subsets count: 2^4 = 16. Formula: 2^{2^2} = 2^4 = 16. Match.

The formula survives small cases, which is strong evidence it is correct for all n.

The one-line derivation

A relation on A is a subset of A \times A; A \times A has n^2 pairs; a set with n^2 elements has 2^{n^2} subsets. Therefore the number of relations on A is 2^{n^2}.

Related: Relations · How Many Subsets? 2ⁿ · Cartesian Product Grid · Sets — Introduction