Counting Relations on a Set with $n$ Elements

Let $A$ be a finite set containing $n$ elements. The number of relations on $A$ is:

$\boxed{2^{n^2}}$

Therefore, the correct answer is:

$\boxed{\text{(ii) }2^{n^2}}$

A relation on $A$ is any subset of the Cartesian product $A \times A$. Since $A$ has $n$ elements, $A \times A$ contains $n^2$ ordered pairs. Each ordered pair may either belong to the relation or not belong to it, giving two choices for each pair.

Cartesian product

Binary relation

Power set

Footnotes

1. Cartesian Products and Relations Definition - Defines relations as subsets of Cartesian products and derives the counting formula. ↩

2. Cartesian Products and Relations Definition - Explains that each ordered pair has two choices: inclusion or exclusion. ↩

1. What Is a Relation on $A$?

A relation $R$ on a set $A$ is defined as a subset of $A \times A$:

$R \subseteq A \times A$

The phrase “on $A$” means that both components of every ordered pair come from $A$.

If

$A=\{a_1,a_2,\ldots,a_n\},$

then

$A\times A=\{(a_i,a_j):1\leq i,j\leq n\}.$

For example, if

$A=\{1,2,3\},$

then

\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}.$$ Thus, $A\times A$ contains $9=3^2$ ordered pairs. Ordered pair Domain Range

2. Counting the Ordered Pairs

The first component of an ordered pair can be selected in $n$ ways, because there are $n$ elements in $A$.

For each first component, the second component can also be selected in $n$ ways.

By the multiplication principle:

$|A\times A|=n\cdot n=n^2.$

This is the key observation. There are $n^2$ possible ordered pairs that could potentially be included in a relation.

3. Why the Exponent Is $n^2$

A common mistake is to use $n$ as the exponent. However, a relation is made from ordered pairs, not individual elements.

There are:

• $n$ choices for the first member of a pair;
• $n$ choices for the second member;
• therefore $n^2$ possible ordered pairs.

The relation is then chosen from these $n^2$ pairs. In other words, every relation is one subset of $A\times A$:

$R\in\mathcal{P}(A\times A).$

The power set of a set containing $m$ elements has $2^m$ subsets. Taking $m=n^2$ gives:

$|\mathcal{P}(A\times A)|=2^{|A\times A|}=2^{n^2}.$

Footnotes

1. Ch. 1 Key Concepts - OpenStax Contemporary Mathematics - States that a finite set with $m$ elements has $2^m$ subsets. ↩

4. Examples

Example 1: $n=1$

Let

$A=\{a\}.$

Then

$A\times A=\{(a,a)\}.$

There is one possible ordered pair, and it can either be included or excluded:

• $R=\varnothing$;
• $R=\{(a,a)\}$.

Therefore:

$2^{1^2}=2.$

---

Example 2: $n=2$

Let

$A=\{a,b\}.$

Then:

$A\times A=\{(a,a),(a,b),(b,a),(b,b)\}.$

There are $4=2^2$ possible ordered pairs. Each can be selected or not selected, so:

$2^4=16.$

Thus, a two-element set has $16$ relations on it.

---

Example 3: $n=3$

For a set with three elements:

$|A\times A|=3^2=9.$

Hence:

$\text{Number of relations}=2^9=512.$

---

Example 4: $n=4$

For a set with four elements:

$|A\times A|=4^2=16.$

Therefore:

$\text{Number of relations}=2^{16}=65,\!536.$

5. Distinguishing the Answer Choices

The expression $n^2$ counts the possible ordered pairs, but not the possible relations. A relation is a subset of those pairs, and the number of subsets of a set with $n^2$ elements is $2^{n^2}$.

Subset

Cardinality

Multiplication principle

6. Relation Properties Do Not Change the Basic Definition

The formula $2^{n^2}$ counts every possible relation on $A$. Additional conditions produce smaller classes of relations.

• A relation is reflexive if every $(a,a)$ must be included.
• A relation is symmetric if including $(a,b)$ requires including $(b,a)$.
• A relation is antisymmetric if distinct elements cannot relate in both directions.
• A relation is transitive if two successive relationships imply a direct relationship.

These restrictions affect the count. For example, the number of reflexive relations on an $n$-element set is:

$2^{n^2-n},$

because the $n$ diagonal pairs $(a,a)$ are forced to be included, while the remaining $n^2-n$ pairs may be chosen freely.

However, unless the question specifies a property, use the unrestricted count:

$\boxed{2^{n^2}}.$

7. Final Derivation

$$\begin{aligned} |A|&=n,\\ |A\times A|&=n\cdot n=n^2,\\ R&\subseteq A\times A,\\ \#\{\text{relations on }A\} &=\#\{\text{subsets of }A\times A\}\\ &=2^{|A\times A|}\\ &=2^{n^2}. \end{aligned}$$

Therefore:

$\boxed{\text{(ii) }2^{n^2}}$