Reflexive and Irreflexive Relations: Counts, Properties and Worked Examples

Learn to classify a relation from its diagonal, count the possible relations on an n-element set, and avoid the common confusion between irreflexive and not reflexive.

KnowledgeGate Team

Exam prep & CS education

Updated 17 Nov 20266 min read
Reflexive and Irreflexive Relations: Counts, Properties and Worked Examples

One self-loop is enough to reject irreflexivity, but it is not enough to prove reflexivity. You must inspect every possible self-loop, and a mixed result means the relation is neither. Always start with the diagonal. This method works for ordered pairs, matrices and directed graphs. On the running set A = {1,2,3}, three diagonal pairs and six off-diagonal pairs will also explain why each class contains 2^6 = 64 relations.

Reflexive and irreflexive relations: inspect the diagonal first

A binary relation R on a set A is a subset of A × A. Use Cartesian Product and Relations: Inverse, Complement and Worked Examples for the product universe and general inverse/complement mechanics; then use the diagonal to decide reflexivity and irreflexivity.

The relation is reflexive when (a,a) ∈ R for every a ∈ A. It is irreflexive when (a,a) ∉ R for every a ∈ A. Define the identity relation as

I_A = {(a,a) : a ∈ A}.

This gives two mechanical tests:

  • R is reflexive if and only if I_A ⊆ R.

  • R is irreflexive if and only if R ∩ I_A = ∅.

In an adjacency matrix, inspect the main diagonal. All 1s means reflexive, while all 0s means irreflexive. In a directed graph, the same test asks whether every vertex has a loop or no vertex has a loop. On a nonempty set, no relation can satisfy both definitions.

Worked classification on A = {1,2,3}

Let

R = {(1,1),(2,2),(3,3),(1,2),(2,1),(2,3)}.

Its diagonal contains every pair in I_A, so R is reflexive. Now let

S = {(1,2),(2,1),(2,3)}.

It contains none of (1,1), (2,2) and (3,3), so S is irreflexive.

Finally, take T = {(1,1),(1,2),(2,3)}. It is not reflexive because (2,2) and (3,3) are missing. It is not irreflexive because (1,1) is present. Therefore, T is neither reflexive nor irreflexive.

With rows and columns ordered as 1,2,3, the matrices are:

  • M_R = [[1,1,0],[1,1,1],[0,0,1]], with diagonal 111.

  • M_S = [[0,1,0],[1,0,1],[0,0,0]], with diagonal 000.

  • M_T = [[1,1,0],[0,0,1],[0,0,0]], with diagonal 100.

Three-panel directed graph comparison of relations on A = {1,2,3}: R has loops at all vertices, S none, and T only at 1.

Count reflexive and irreflexive relations on an n-element set

The set A × A contains n^2 ordered pairs. Exactly n are diagonal pairs of the form (a,a), leaving n^2 - n off-diagonal pairs.

For a reflexive relation, all n diagonal pairs are fixed in the relation. Each off-diagonal pair may independently be included or excluded. The count is therefore

2^(n^2-n).

For an irreflexive relation, all diagonal pairs are fixed out, but the same off-diagonal choices remain free. Its count is also 2^(n^2-n). Equal counts do not mean overlap when n ≥ 1.

For n = 3, there are 3^2 = 9 possible pairs: three diagonal and six off-diagonal. List the free pairs in the order (1,2),(1,3),(2,1),(2,3),(3,1),(3,2). The pattern 101100, for example, selects (1,2),(2,1),(2,3). Since each of the six bits has two choices, both counts are 2^6 = 64.

3x3 ordered-pair grid highlighting diagonal cells and six off-diagonal choices for 64 reflexive or irreflexive relations.

Not reflexive is not the same as irreflexive

Negating the definitions exposes the difference. Not reflexive means at least one required loop is missing. Not irreflexive means at least one loop is present. A mixed diagonal such as 100 satisfies both negations, so T has neither property.

For a nonempty n-element set, there are 2^(n^2) relations in total. The reflexive and irreflexive classes are disjoint, and each has 2^(n^2-n) members. Inclusion-exclusion therefore gives

N_neither = 2^(n^2) - 2 × 2^(n^2-n).

At n = 3, this is 512 - 64 - 64 = 384. More generally, the number of relations with exactly k loops is C(n,k)2^(n^2-n). Exactly one loop gives C(3,1)2^6 = 3 × 64 = 192, and exactly two gives C(3,2)2^6 = 3 × 64 = 192. Their sum is 384.

There is one edge case. On A = ∅, the empty relation is vacuously both reflexive and irreflexive because there is no element that can violate either universal statement.

Properties under complement, inverse and relation operations

Take complements relative to A × A. If R is reflexive, its complement contains no diagonal pair and is irreflexive. If S is irreflexive, its complement contains every diagonal pair and is reflexive. The running R and S share three off-diagonal arrows but make opposite diagonal choices. They are not complements because a full complement also reverses every off-diagonal choice.

The inverse operation preserves both properties because reversing (a,a) produces (a,a) again. Unions and intersections of reflexive relations remain reflexive. Unions and intersections of irreflexive relations remain irreflexive.

Composition needs more care. Define P ∘ Q by first following a pair in Q, then a pair in P. The composition of two reflexive relations is reflexive: for each a, use the loop at a in both relations. However, let U = {(1,2),(2,1)} on {1,2}. Although U is irreflexive, following U twice gives U ∘ U = {(1,1),(2,2)}, which is reflexive and not irreflexive.

How exam-style questions test the diagonal and the count

Typical tasks ask you to classify a set or matrix, supply missing loops, count relations under a diagonal restriction, or test an operation. Try these checks:

  1. On a four-element set, n^2-n = 16-4 = 12. There are 2^12 = 4096 reflexive relations and 4096 irreflexive relations.

  2. A 4 × 4 matrix with diagonal 1010 represents a relation that is neither, because some but not all loops are present.

  3. For V = {(1,1),(2,2),(1,2)} on {1,2,3}, adding (3,3) is the one-pair change that makes V reflexive. Removing (1,1) and (2,2) makes it irreflexive.

Apply the same diagonal decisions in targeted practice on this subtopic. For nearby problems across the wider topic, use the Set Theory and Relations MCQ collection as adjacent practice.

Avoid the traps that reverse a correct answer

  • Checking one vertex only: one loop disproves irreflexivity, but reflexivity needs every loop. T is still not reflexive.

  • Equating not reflexive with irreflexive: a mixed diagonal such as 100 means neither.

  • Leaving all n^2 pairs free: once the diagonal is fixed, only n^2-n choices remain. At n = 3, the count is 2^6, not 2^9.

  • Merging opposite ordered pairs: (a,b) and (b,a) are separate choices unless a = b.

  • Using another property as evidence: symmetry or transitivity cannot establish reflexivity. Check the loops directly.

  • Assuming composition preserves irreflexivity: the opposite arrows in U create loops in U ∘ U.

Use a five-second method: write the diagonal list, mark every pair present or absent, classify the result as all, none or mixed, and only then inspect any other requested property.

Remember the short version and choose the next step

All loops means reflexive. No loops means irreflexive. A mixed diagonal means neither. On n elements, each of the first two classes has 2^(n^2-n) relations because only off-diagonal pairs remain free. For n = 3, that is 2^6 = 64 reflexive relations and 64 irreflexive relations.

For focused mathematics teaching, continue with Engineering Mathematics for GATE. For a structured CS route, consider GATE Guidance by Sanchit Sir. You can also browse the broader CS Fundamentals category. Choose the optional route that matches your gap.

On A = {1,2,3,4}, a relation with exactly two loops has C(4,2) choices for those loops and 2^(16-4) choices for the off-diagonal pairs:

C(4,2)2^(16-4) = 6 × 4096 = 24576.

Explain why every such relation is neither reflexive nor irreflexive: two of the four loops are present, and two are absent.