In Relations we saw that a relation on a set A is simply a subset of A × A, and that we can draw it as a 0/1 matrix or as a directed graph. A random subset of A × A is not very interesting, though. The relations that matter in computer science (equality, ≤, "divides", "is reachable from", "has the same hash as") all obey a few simple rules. Those rules are the properties of relations.
Six properties do almost all the work: reflexive, irreflexive, symmetric, antisymmetric, asymmetric and transitive. Combinations of them define the two most important kinds of relation in discrete mathematics: equivalence relations (reflexive + symmetric + transitive) and partial orders (reflexive + antisymmetric + transitive), which get their own chapters next.
A property of a relation is a rule that must hold for every element or every pair of elements of the set. To prove a property you must check all cases; to disprove it, one counterexample is enough.
In this chapter we define each property precisely, learn how to spot it in a matrix and in a digraph, count how many relations have each property (a GATE favourite), and finish with closures, which is how you repair a relation that is missing a property. Every count in this chapter was checked by brute force over all relations on sets of size 1 to 4.
Running Notation
Throughout, R is a relation on a non-empty set A, and we write a R b (or (a, b) ∈ R) when a is related to b. The diagonal (or identity relation) is Δ = {(a, a) : a ∈ A}. The inverse of R is R−1 = {(b, a) : (a, b) ∈ R}.
We will keep coming back to one small set, A = {1, 2, 3}, so that you can check every claim by hand.
Reflexive and Irreflexive
R is reflexive if ∀a ∈ A, (a, a) ∈ R. R is irreflexive if ∀a ∈ A, (a, a) ∉ R.
Reflexive means "every element is related to itself": = , ≤ and ⊆ are reflexive because a = a, a ≤ a and S ⊆ S. Irreflexive means "no element is related to itself": < and ≠ are irreflexive.
Matrix test: reflexive ⇔ every diagonal entry is 1. Irreflexive ⇔ every diagonal entry is 0.
Digraph test: reflexive ⇔ a self-loop at every vertex. Irreflexive ⇔ no self-loop anywhere.
The most common exam trap: "not reflexive" does not mean "irreflexive". On A = {1, 2, 3}, the relation {(1, 1)} is neither: it has a loop at 1 (so it is not irreflexive) but no loops at 2 and 3 (so it is not reflexive). A relation on a non-empty set cannot be both reflexive and irreflexive, but it can easily be neither.
Symmetric, Antisymmetric and Asymmetric
R is symmetric if ∀a, b: (a, b) ∈ R → (b, a) ∈ R.
R is antisymmetric if ∀a, b: ((a, b) ∈ R ∧ (b, a) ∈ R) → a = b.
R is asymmetric if ∀a, b: (a, b) ∈ R → (b, a) ∉ R.
Think of an arrow a → b in the digraph:
Symmetric: every arrow has a return arrow. In the matrix, M = MT. Equivalently R = R−1.
Antisymmetric: between two different vertices there is never a pair of arrows going both ways. Self-loops are allowed. In the matrix, for i ≠ j, mij and mji are never both 1. Equivalently R ∩ R−1 ⊆ Δ.
Asymmetric: no two-way arrows at all, and (taking a = b) no self-loops either.
The useful way to read antisymmetry is through its contrapositive: if a ≠ b, then at most one of (a, b), (b, a) is in R. That is why ≤ is antisymmetric (if a ≤ b and b ≤ a then a = b) and ⊆ is antisymmetric (if S ⊆ T and T ⊆ S then S = T, which is exactly how we prove two sets equal).
Symmetric and antisymmetric are not opposites
A relation can be both symmetric and antisymmetric: on A = {1, 2, 3}, R = {(1, 1), (2, 2)} is symmetric (every pair is its own reverse) and antisymmetric (no two-way arrow between different elements). In fact a relation is both exactly when R ⊆ Δ. A relation can also be neither: {(1, 2), (2, 1), (1, 3)} has the two-way pair 1 ↔ 2 (not antisymmetric) and (1, 3) without (3, 1) (not symmetric).
Asymmetric = irreflexive + antisymmetric
Theorem. R is asymmetric if and only if R is both irreflexive and antisymmetric.
Proof. (⇒) Suppose R is asymmetric. If (a, a) ∈ R, then asymmetry with b = a says (a, a) ∉ R, a contradiction; so R is irreflexive. For antisymmetry, the hypothesis "(a, b) ∈ R and (b, a) ∈ R" can never be true, so the implication holds vacuously. (⇐) Suppose R is irreflexive and antisymmetric, and (a, b) ∈ R. If also (b, a) ∈ R, antisymmetry gives a = b, so (a, a) ∈ R, contradicting irreflexivity. Hence (b, a) ∉ R. ∎
Transitive
R is transitive if ∀a, b, c: ((a, b) ∈ R ∧ (b, c) ∈ R) → (a, c) ∈ R.
In the digraph: every path of length 2 has a "shortcut" arrow. Note that a, b, c need not be distinct. If (1, 2) and (2, 1) are both in R, transitivity demands (1, 1) and (2, 2) as well. Forgetting this is the number one mistake in transitivity checks.
Two equivalent tests that are handy in proofs and code:
Composition test: R is transitive ⇔ R ∘ R ⊆ R (every 2-step pair is already a 1-step pair).
Matrix test: compute the Boolean product M ⊙ M. R is transitive ⇔ wherever M ⊙ M has a 1, M also has a 1.
A relation with no 2-step paths at all is vacuously transitive. For example {(1, 3)} on {1, 2, 3} is transitive, because there is no pair (3, x) to chain with (1, 3). The empty relation is also transitive.
Worked Examples on A = {1, 2, 3}
Relation | Refl | Irrefl | Sym | Antisym | Asym | Trans |
|---|---|---|---|---|---|---|
R1 = {(1,1), (2,2), (3,3), (1,2), (2,1)} | Yes | No | Yes | No | No | Yes |
R2 = {(1,1), (1,2), (2,3)} | No | No | No | Yes | No | No |
R3 = {(1,3)} | No | Yes | No | Yes | Yes | Yes |
R4 = {(1,1), (2,2)} | No | No | Yes | Yes | No | Yes |
R5 = {(1,2), (2,1)} | No | Yes | Yes | No | No | No |
∅ (empty relation) | No | Yes | Yes | Yes | Yes | Yes |
Reasoning for the trickier cells:
R1 is transitive: the only 2-step chains are 1 → 2 → 1 (needs (1, 1), present), 2 → 1 → 2 (needs (2, 2), present) and chains through loops, which never need anything new.
R2 is not transitive: 1 → 2 → 3 needs (1, 3). It is not reflexive ((2, 2) missing) and not irreflexive ((1, 1) present).
R5 is not transitive: 1 → 2 → 1 needs (1, 1). This is the "a, b, c need not be distinct" trap.
∅ on a non-empty set satisfies every property except reflexivity: all the "for every pair in R" conditions are vacuously true.
Familiar relations
Relation | Properties it has | Fails because |
|---|---|---|
= on any set | Reflexive, symmetric, antisymmetric, transitive | (not irreflexive / asymmetric) |
≤ on ℤ | Reflexive, antisymmetric, transitive | Not symmetric: 1 ≤ 2 but 2 ≰ 1 |
< on ℤ | Irreflexive, asymmetric, antisymmetric, transitive | Not reflexive: 1 < 1 is false |
a | b on positive integers | Reflexive, antisymmetric, transitive | Not symmetric: 2 | 4 but 4 ∤ 2 |
a | b on non-zero integers | Reflexive, transitive | Not antisymmetric: 2 | −2 and −2 | 2 but 2 ≠ −2 |
⊆ on the power set P(S) | Reflexive, antisymmetric, transitive | Not symmetric |
a ≡ b (mod n) on ℤ | Reflexive, symmetric, transitive | Not antisymmetric: 1 ≡ 4 (mod 3) |
≠ on ℤ | Irreflexive, symmetric | Not transitive: 1 ≠ 2, 2 ≠ 1, but 1 = 1 |
ab ≥ 0 on ℤ | Reflexive, symmetric | Not transitive: 1·0 ≥ 0, 0·(−1) ≥ 0, but 1·(−1) < 0 |
|a − b| ≤ 1 on ℤ | Reflexive, symmetric | Not transitive: (1, 2), (2, 3) but |1 − 3| = 2 |
"is a parent of" on people | Irreflexive, asymmetric, antisymmetric | Not transitive: a grandparent is not a parent |
The "a | b on non-zero integers" row is a classic GATE-style trap: the same rule can have different properties on different sets.
Checking Properties by Program
The definitions translate directly into code. The function below checks all six properties, and warshall computes the transitive closure (explained later in this chapter).
def properties(A, R):
"""Return which of the six basic properties the relation R on set A has."""
return {
"reflexive": all((a, a) in R for a in A),
"irreflexive": all((a, a) not in R for a in A),
"symmetric": all((b, a) in R for (a, b) in R),
"antisymmetric": all(a == b or (b, a) not in R for (a, b) in R),
"asymmetric": all((b, a) not in R for (a, b) in R),
"transitive": all((a, d) in R for (a, b) in R for (c, d) in R if b == c),
}
def warshall(A, R):
"""Transitive closure using Warshall's algorithm on the 0/1 matrix."""
A = sorted(A)
n = len(A)
W = [[1 if (A[i], A[j]) in R else 0 for j in range(n)] for i in range(n)]
for k in range(n): # allow A[k] as an intermediate vertex
for i in range(n):
for j in range(n):
W[i][j] = W[i][j] or (W[i][k] and W[k][j])
return {(A[i], A[j]) for i in range(n) for j in range(n) if W[i][j]}
A = {1, 2, 3, 4}
R = {(1, 2), (2, 3), (3, 4), (2, 1)}
for name, value in properties(A, R).items():
print(f"{name:14}: {value}")
reflexive_closure = R | {(a, a) for a in A}
symmetric_closure = R | {(b, a) for (a, b) in R}
transitive_closure = warshall(A, R)
print("reflexive closure :", sorted(reflexive_closure))
print("symmetric closure :", sorted(symmetric_closure))
print("transitive closure:", sorted(transitive_closure))
print("closure is transitive?", properties(A, transitive_closure)["transitive"])Output:
reflexive : False
irreflexive : True
symmetric : False
antisymmetric : False
asymmetric : False
transitive : False
reflexive closure : [(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 3), (3, 4), (4, 4)]
symmetric closure : [(1, 2), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3)]
transitive closure: [(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4)]
closure is transitive? TrueNotice the transitivity check is O(|R|2) and the Warshall loop is O(n3). For exam-sized relations both are instant.
Counting Relations with a Given Property
On a set with n elements there are n2 ordered pairs: n diagonal pairs (a, a) and n2 − n off-diagonal pairs, which group into n(n − 1)/2 unordered couples {(a, b), (b, a)}. Every count below comes from deciding, piece by piece, which pairs to include (independent choices multiply: if one decision has x options and another, independent one has y, together they have x · y).
All relations: each of n2 pairs is in or out → 2n².
Reflexive: the n diagonal pairs are forced in; the other n2 − n are free → 2n² − n. Irreflexive is the same count (diagonal forced out).
Symmetric: each diagonal pair is free (2n); each off-diagonal couple is "both or neither" (2 choices) → 2n · 2n(n−1)/2 = 2n(n+1)/2.
Antisymmetric: diagonal free (2n); each couple has 3 allowed choices: neither, only (a, b), only (b, a) → 2n · 3n(n−1)/2.
Asymmetric: diagonal forced out; 3 choices per couple → 3n(n−1)/2.
Reflexive and symmetric: diagonal forced in; 2 choices per couple → 2n(n−1)/2.
Reflexive and antisymmetric: diagonal forced in; 3 choices per couple → 3n(n−1)/2.
Symmetric and antisymmetric: no off-diagonal pairs at all; diagonal free → 2n.
Neither reflexive nor irreflexive: total minus reflexive minus irreflexive (the two sets are disjoint for n ≥ 1) → 2n² − 2 · 2n² − n.
Property | Formula | n = 2 | n = 3 | n = 4 |
|---|---|---|---|---|
Any relation | 2n² | 16 | 512 | 65536 |
Reflexive (or irreflexive) | 2n² − n | 4 | 64 | 4096 |
Symmetric | 2n(n+1)/2 | 8 | 64 | 1024 |
Antisymmetric | 2n · 3n(n−1)/2 | 12 | 216 | 11664 |
Asymmetric | 3n(n−1)/2 | 3 | 27 | 729 |
Reflexive and symmetric | 2n(n−1)/2 | 2 | 8 | 64 |
Reflexive and antisymmetric | 3n(n−1)/2 | 3 | 27 | 729 |
Symmetric and antisymmetric | 2n | 4 | 8 | 16 |
Transitive | no closed formula | 13 | 171 | 3994 |
There is no simple formula for transitive relations; the counts must be computed (the table values come from brute force). Equivalence relations and partial orders are counted in the next two chapters.
Which Operations Preserve Which Properties?
If R and S both have a property, does R ∪ S? R ∩ S? This table was verified by trying every pair of relations on a 3-element set (a "No" means a counterexample exists).
Property of R and S | R ∪ S | R ∩ S | R−1 | R ∘ S | Complement of R |
|---|---|---|---|---|---|
Reflexive | Yes | Yes | Yes | Yes | No (it becomes irreflexive) |
Irreflexive | Yes | Yes | Yes | No | No (it becomes reflexive) |
Symmetric | Yes | Yes | Yes | No | Yes |
Antisymmetric | No | Yes | Yes | No | No |
Transitive | No | Yes | Yes | No | No |
The two "No"s for union are worth remembering with small counterexamples on {1, 2, 3}:
Antisymmetric: {(1, 2)} and {(2, 1)} are each antisymmetric, but their union has the two-way pair.
Transitive: {(1, 2)} and {(2, 3)} are each transitive (vacuously), but the union has 1 → 2 → 3 without (1, 3).
Intersection preserves transitivity: if (a, b) and (b, c) are in R ∩ S, they are in both R and S, so (a, c) is in both, so in R ∩ S. The same "it holds in both, so it holds in the intersection" argument works for every property in the table.
Closures: Repairing a Missing Property
Suppose R is not transitive. We cannot remove pairs (that would change what R says), but we can add the fewest pairs needed.
The closure of R with respect to a property P is the smallest relation that contains R and has property P: it contains R, has P, and is a subset of every relation that contains R and has P.
Closure | Formula | Idea |
|---|---|---|
Reflexive closure r(R) | R ∪ Δ | Add all missing self-loops |
Symmetric closure s(R) | R ∪ R−1 | Add the reverse of every arrow |
Transitive closure t(R) or R+ | R ∪ R2 ∪ … ∪ Rn (for |A| = n) | (a, b) ∈ R+ ⇔ there is a path from a to b of length ≥ 1 |
Why do powers up to Rn suffice? If there is a path from a to b, take a shortest one, say with m edges, and suppose m > n. Look at its first m vertex visits (all except the final arrival at b). That is m ≥ n + 1 visits among only n elements, so they cannot all be different and some vertex appears twice among them. Cutting out the loop between those two visits leaves a shorter path from a to b that still has at least one edge, contradicting "shortest". So m ≤ n.
Not every property has a closure. There is no "irreflexive closure" of a relation that contains (1, 1): adding pairs can never remove the loop. Likewise for antisymmetric and asymmetric closures.
Warshall's algorithm
Computing R ∪ R2 ∪ … ∪ Rn with Boolean matrix products costs O(n4). Warshall's algorithm does it in O(n3). Number the elements 1 … n. Let Wk[i][j] = 1 if there is a path from i to j whose intermediate vertices are all in {1, …, k}. Then
W0 = M (the matrix of R)
Wk[i][j] = W(k-1)[i][j] OR ( W(k-1)[i][k] AND W(k-1)[k][j] )In words: either we could already go from i to j without using k, or we go i → k and then k → j. A handy hand rule: in round k, for every row i that has a 1 in column k, OR row k into row i.
Worked example. A = {1, 2, 3, 4}, R = {(1, 2), (2, 1), (2, 3), (3, 4)} (the relation from the program above).
W0 W1 (k=1) W2 (k=2) W3 (k=3) W4 (k=4)
row 1: 0 1 0 0 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1
row 2: 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1
row 3: 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1
row 4: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0k = 1: column 1 has a 1 only in row 2, so row 2 := row 2 OR row 1 = 1 1 1 0 (the loop 2 → 1 → 2 gives (2, 2)).
k = 2: column 2 has 1s in rows 1 and 2. Row 1 := row 1 OR row 2 = 1 1 1 0.
k = 3: column 3 has 1s in rows 1 and 2. OR row 3 (0 0 0 1) into both: they become 1 1 1 1.
k = 4: row 4 is all zeros, so nothing changes.
The 9 ones of W4 are exactly the transitive closure printed by the program. The same algorithm on graphs answers "which vertices can reach which", and it is the Boolean version of the Floyd–Warshall shortest-path algorithm.
Combining closures
Closures do not always play nicely together:
The symmetric closure of a transitive relation need not be transitive: {(1, 2)} is transitive, but s(R) = {(1, 2), (2, 1)} is not (it lacks (1, 1)).
The transitive closure of a symmetric relation is symmetric (reverse every path), and the transitive closure of a reflexive relation is reflexive.
Therefore the smallest equivalence relation containing R is t(s(r(R))): first add loops, then reverse arrows, and take the transitive closure last.
Common Mistakes
Treating "not reflexive" as "irreflexive" (or "not symmetric" as "antisymmetric"). These pairs of words are not negations of each other.
Forgetting a = c in transitivity. If (a, b) and (b, a) are in R, then (a, a) must be in R too.
Claiming the empty relation is reflexive. On a non-empty set it is not: reflexivity needs every (a, a). It is, however, symmetric, antisymmetric, asymmetric, irreflexive and transitive.
Thinking antisymmetric forbids self-loops. It does not; asymmetric does.
Checking properties on the wrong set. Reflexivity depends on A, not only on R: {(1, 1), (2, 2)} is reflexive on {1, 2} but not on {1, 2, 3}.
Computing the equivalence closure in the wrong order, for example taking the transitive closure before the symmetric closure.
Practice and GATE-Style Questions
Q1. How many relations on a set of 4 elements are both reflexive and symmetric?
Diagonal forced in; each of the C(4, 2) = 6 unordered couples is "both or neither". Answer: 26 = 64.
Q2. How many antisymmetric relations are there on a set with 3 elements?
23 · 33 = 8 · 27 = 216 (2 choices for each of 3 diagonal pairs, 3 choices for each of 3 couples).
Q3. Let R be the relation on ℤ defined by a R b ⇔ a − b is odd. Which properties does R have?
Irreflexive (a − a = 0 is even) and symmetric (b − a = −(a − b) is odd too). Not transitive: 1 R 2 and 2 R 3, but 1 − 3 = −2 is even. Not antisymmetric (1 R 2 and 2 R 1). So only irreflexive and symmetric.
Q4. True or false: every asymmetric relation is antisymmetric.
True. Asymmetric = irreflexive + antisymmetric (proved above). The converse is false: {(1, 1)} is antisymmetric but not asymmetric.
Q5. Find the transitive closure of R = {(a, b), (b, c), (c, a)} on {a, b, c}.
The three arrows form a cycle, so every vertex reaches every vertex, including itself (a → b → c → a). The closure is all of A × A: 9 pairs.
Q6. Interview: R is symmetric and transitive. A classmate argues it must be reflexive: "if a R b then b R a, so by transitivity a R a". What is wrong?
The argument assumes that every a is related to some b. If an element a has no partner at all, nothing forces (a, a). Counterexample: R = ∅ on {1}, or R = {(1, 1)} on {1, 2}, which is symmetric and transitive but not reflexive. The argument only proves that every element that appears in some pair has a self-loop.
Summary
Reflexive: all loops. Irreflexive: no loops. A relation can be neither.
Symmetric: every arrow has a return arrow (M = MT). Antisymmetric: no two-way arrows between different elements. Asymmetric = irreflexive + antisymmetric.
Transitive: every 2-step path has a direct arrow; equivalently R ∘ R ⊆ R. Remember the case a = c.
Counts on n elements: reflexive 2n² − n, symmetric 2n(n+1)/2, antisymmetric 2n3n(n−1)/2, asymmetric 3n(n−1)/2.
Intersection and inverse preserve all five basic properties; union breaks antisymmetry and transitivity.
Closures add the fewest pairs: r(R) = R ∪ Δ, s(R) = R ∪ R−1, t(R) by Warshall's O(n3) algorithm.
Look at the loops for reflexivity, at the two-way arrows for symmetry, and at the 2-step paths for transitivity. Most relation questions are solved by these three glances.