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

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:
Ris reflexive if and only ifI_A ⊆ R.Ris irreflexive if and only ifR ∩ 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 diagonal111.M_S = [[0,1,0],[1,0,1],[0,0,0]], with diagonal000.M_T = [[1,1,0],[0,0,1],[0,0,0]], with diagonal100.

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.

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:
On a four-element set,
n^2-n = 16-4 = 12. There are2^12 = 4096reflexive relations and4096irreflexive relations.A
4 × 4matrix with diagonal1010represents a relation that is neither, because some but not all loops are present.For
V = {(1,1),(2,2),(1,2)}on{1,2,3}, adding(3,3)is the one-pair change that makesVreflexive. 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.
Tis still not reflexive.Equating not reflexive with irreflexive: a mixed diagonal such as
100means neither.Leaving all
n^2pairs free: once the diagonal is fixed, onlyn^2-nchoices remain. Atn = 3, the count is2^6, not2^9.Merging opposite ordered pairs:
(a,b)and(b,a)are separate choices unlessa = b.Using another property as evidence: symmetry or transitivity cannot establish reflexivity. Check the loops directly.
Assuming composition preserves irreflexivity: the opposite arrows in
Ucreate loops inU ∘ 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.
Keep learning
Reflexive and Irreflexive Relation MCQs: 10 Solved Questions on Counts and Properties
Solve 10 practice questions on reflexive and irreflexive relations. Learn diagonal tests, counting, probability, closure, and property proofs.
Transitive Relation MCQs: 12 Solved Questions on Definition, Count, Properties and Closure
Test transitivity by finding required shortcut pairs, decisive counterexamples and reachable paths. These 12 MCQs cover relation audits, properties and closure.
Equivalence Relations, Equivalence Classes and Set Partitions: Worked Examples
Follow a finite modulo-3 relation from its ordered pairs to three classes and one partition, then reverse the process and practise fast exam checks.
Cartesian Product and Relations: Inverse, Complement and Worked Examples
Learn how a Cartesian product defines the universe of a relation, then compute inverse and complement operations through small, fully checked examples.





