Determine if a relation is reflexive, symmetric, transitive - Discrete Math

SECTION 1

Historical Context & Motivation

The formal study of relations emerged from the broader effort to place mathematics on rigorous logical foundations during the nineteenth and early twentieth centuries. Before relations were formalized, mathematicians used notions like 'equality,' 'congruence,' and 'similarity' without a unifying framework. The drive to axiomatize these intuitive ideas — to specify exactly what makes two objects 'equivalent' in a given context — led directly to the identification of the reflexive, symmetric, and transitive properties. Understanding these properties is not merely an exercise in abstraction; they form the backbone of equivalence relations, partial orders, database normalization, compiler design, and the classification of algebraic structures.

1847 • De Morgan's Formal Logic

Augustus De Morgan published Formal Logic, one of the first systematic treatments of relations as mathematical objects, distinguishing properties like transitivity in logical inference.

1870 • Peirce's Logic of Relatives

Charles Sanders Peirce developed an algebraic calculus of relations, introducing notation for composition and inversion of relations and classifying their structural properties.

1895 • Cantor's Set Theory Foundations

Georg Cantor's set-theoretic framework provided the language of ordered pairs and Cartesian products, enabling the modern definition of a relation as a subset of A × B.

1921 • Hausdorff and the Equivalence Relation

Felix Hausdorff's foundational topology text crystallized the definition of an equivalence relation as one satisfying reflexivity, symmetry, and transitivity, establishing the triad as a standard classification tool.

1970s • Relations in Computer Science

E.F. Codd's relational model of databases and formal verification methods brought relation properties into applied computer science, where reflexive and transitive closures became algorithmic primitives.

The central question this lesson addresses is deceptively simple: given a binary relation R on a set A, how do we systematically determine whether R is reflexive, symmetric, or transitive? Answering this question requires precise definitions, a toolkit of verification strategies, and practice recognizing these properties across different representations — set-roster notation, matrices, and directed graphs.

SECTION 2

Core Definitions & Principles

A binary relation R on a set A is a subset of the Cartesian product A × A. We write (a, b) ∈ R or equivalently aRb to indicate that a is related to b under R. The three properties — reflexive, symmetric, and transitive — describe structural constraints on which ordered pairs may or must appear in R. Each property corresponds to a universally quantified logical statement that must hold for every relevant element or pair in A; a single counterexample suffices to show a property fails.

Reflexive

A relation R on A is reflexive if for every element a ∈ A, the pair (a, a) ∈ R. In other words, every element is related to itself. To verify: check that every element of A appears in a self-loop.

Symmetric

A relation R on A is symmetric if for all a, b ∈ A, whenever (a, b) ∈ R then (b, a) ∈ R. Every directed edge between distinct elements must have a matching reverse edge. To disprove: find a pair (a, b) ∈ R where (b, a) ∉ R.

Transitive

A relation R on A is transitive if for all a, b, c ∈ A, whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R. If you can 'chain' two steps from a to b to c, the shortcut from a to c must also exist. To disprove: find a, b, c with aRb and bRc but not aRc.

Equivalence Relation

When a relation satisfies all three properties — reflexive, symmetric, and transitive — it is called an equivalence relation. Such a relation partitions A into disjoint equivalence classes. Familiar examples include equality (=), congruence modulo n, and similarity of triangles.

✦

KEY TAKEAWAY

Think of a relation as a social network. Reflexive means everyone follows themselves (self-loops). Symmetric means every 'follow' is mutual — like a friendship on Facebook rather than a one-way follow on Twitter. Transitive means if Alice is friends with Bob, and Bob is friends with Carol, then Alice must also be friends with Carol. A network satisfying all three forms perfectly isolated friend groups with no cross-connections — that's a partition into equivalence classes.

SECTION 3

Visual Explanation — Directed Graphs of Relations

A powerful way to visualize a relation on a finite set is through a directed graph (digraph). Each element of the set becomes a vertex, and each ordered pair (a, b) in the relation becomes a directed edge from a to b. Self-loops represent pairs of the form (a, a). The three properties then have immediate visual signatures: reflexivity corresponds to a self-loop at every vertex, symmetry corresponds to every edge being bidirectional, and transitivity corresponds to the existence of a 'shortcut' edge whenever a two-step path exists.

Left panels show relations satisfying reflexivity (all self-loops present) and symmetry (all edges bidirectional). Right panels show violations: a missing self-loop breaks reflexivity, and a one-way edge breaks symmetry.

In the diagram above, the left-hand panels illustrate relations that satisfy the given property, while the right-hand panels show violations. For reflexivity, observe that every vertex in the left graph has a curved self-loop, while vertex 2 in the right graph lacks one — a single missing self-loop is enough to destroy reflexivity. For symmetry, the left pair of nodes shows edges in both directions, whereas the right pair has only a→b with no return edge b→a. The visual pattern for transitivity is harder to spot visually — you must check that whenever a two-hop path exists from vertex a through vertex b to vertex c, a direct edge from a to c is also present.

SECTION 4

Formal Definitions & Matrix Representation

Let A = {a₁, a₂, …, aₙ} be a finite set and R ⊆ A × A a binary relation on A. The three properties can be stated precisely using first-order logic. Additionally, each property has a clean characterization in terms of the relation matrix $M_R$ , an n × n Boolean matrix where entry $m_{ij}$ = 1 if and only if (aᵢ, aⱼ) ∈ R.

REFLEXIVE

∀a ∈ A : (a, a) ∈ R

Matrix test: every diagonal entry of M_R equals 1, i.e., m_ii = 1 for all i. Equivalently, I_n ≤ M_R (the identity matrix is entry-wise ≤ the relation matrix).

SYMMETRIC

∀a, b ∈ A : (a, b) ∈ R → (b, a) ∈ R

Matrix test: M_R = M_R^T. That is, the relation matrix equals its transpose. If m_ij = 1 then m_ji = 1.

TRANSITIVE

∀a, b, c ∈ A : [(a, b) ∈ R ∧ (b, c) ∈ R] → (a, c) ∈ R

Matrix test: M_R² ≤ M_R (entry-wise), where M_R² denotes Boolean matrix multiplication. Any 1 in M_R² must also appear as a 1 in M_R.

The matrix perspective is especially useful for computational verification. For a relation on an n-element set, checking reflexivity takes O(n) time (inspect the diagonal), checking symmetry takes O(n²) time (compare M with M^T), and checking transitivity via Boolean matrix multiplication takes O(n³) time. While these complexities are modest for small sets encountered in homework problems, they become relevant in database theory and graph algorithms operating on large relation matrices.

⚠

Negation Strategy

To prove a property holds, you must verify the universal quantifier for all elements. To prove a property fails, you only need one counterexample. For reflexivity: find one a ∈ A with (a, a) ∉ R. For symmetry: find one pair (a, b) ∈ R with (b, a) ∉ R. For transitivity: find a, b, c with (a, b) ∈ R and (b, c) ∈ R but (a, c) ∉ R.

SECTION 5

Matrix and Digraph Verification Methods

Consider the set A = {1, 2, 3} and the relation R = {(1,1), (1,2), (2,1), (2,2), (3,3)}. We will construct both the relation matrix and the directed graph, then systematically check each property. This dual representation reinforces the connection between algebraic and graphical perspectives, and it illustrates the standard verification workflow used in discrete mathematics.

The relation R = {(1,1), (1,2), (2,1), (2,2), (3,3)} on A = {1, 2, 3} shown as both a matrix and a digraph. Cyan highlights mark diagonal entries (reflexive self-loops), violet highlights mark symmetric off-diagonal pairs. This relation is an equivalence relation, partitioning A into classes {1, 2} and {3}.

Property	Matrix Test	Digraph Test
Reflexive	All diagonal entries = 1	Self-loop at every vertex
Symmetric	M = Mᵀ (matrix equals its transpose)	Every edge is bidirectional (or absent)
Transitive	M² ≤ M (Boolean product entry-wise)	Every 2-hop path has a direct shortcut edge

Quick-reference tests for each property

SECTION 6

Worked Example

Let A = {a, b, c, d} and define the relation R = {(a, a), (a, b), (b, a), (b, b), (c, c), (c, d), (d, d)}. Determine whether R is reflexive, symmetric, and transitive.

Full Property Analysis of R on {a, b, c, d}

1
Step 1 — List the set and relation explicitly

We have A = {a, b, c, d} with |A| = 4. The relation R contains 7 ordered pairs: (a,a), (a,b), (b,a), (b,b), (c,c), (c,d), (d,d). Note that R ⊆ A × A, and |A × A| = 16, so R includes 7 of the 16 possible pairs.
2
Step 2 — Check Reflexivity

Reflexivity requires (x, x) ∈ R for every x ∈ A. We check each element: (a, a) ∈ R ✓, (b, b) ∈ R ✓, (c, c) ∈ R ✓, (d, d) ∈ R ✓. All four elements have self-pairs in R.

R is reflexive ✓
3
Step 3 — Check Symmetry

Symmetry requires that whenever (x, y) ∈ R, then (y, x) ∈ R. We only need to check the off-diagonal pairs (pairs where x ≠ y). The off-diagonal pairs in R are: (a, b) — is (b, a) ∈ R? Yes ✓. (b, a) — is (a, b) ∈ R? Yes ✓. (c, d) — is (d, c) ∈ R? We search R and find that (d, c) is NOT in R.

R is NOT symmetric ✗ — counterexample: (c, d) ∈ R but (d, c) ∉ R
4
Step 4 — Check Transitivity

Transitivity requires that whenever (x, y) ∈ R and (y, z) ∈ R, then (x, z) ∈ R. We systematically check all chains. Starting from each pair (x, y) ∈ R, we look for pairs (y, z) ∈ R and verify (x, z) ∈ R. Chain (a, b), (b, a): need (a, a) ∈ R ✓. Chain (a, b), (b, b): need (a, b) ∈ R ✓. Chain (b, a), (a, a): need (b, a) ∈ R ✓. Chain (b, a), (a, b): need (b, b) ∈ R ✓. Chain (c, d), (d, d): need (c, d) ∈ R ✓. All other chains involve self-pairs which trivially satisfy transitivity (e.g., (a,a),(a,a) → (a,a), (a,a),(a,b) → (a,b), etc.).

R is transitive ✓
5
Step 5 — Conclusion

R is reflexive and transitive but not symmetric. Since it fails one of the three properties, R is not an equivalence relation. It is also not a partial order because partial orders require antisymmetry, and R contains both (a, b) and (b, a) with a ≠ b, violating antisymmetry. This relation is an example of a preorder (also called a quasi-order) — a reflexive and transitive relation that need not be symmetric or antisymmetric.

R is a preorder: reflexive ✓, not symmetric ✗, transitive ✓

SECTION 7

Common Pitfalls & Comparative Analysis

Students frequently encounter subtle errors when checking relation properties. Some mistakes arise from confusing the quantifiers (universal vs. existential), while others stem from misunderstanding the logical structure of conditional statements. The table below catalogs the most common pitfalls alongside the correct reasoning.

Pitfall	Why It's Wrong	Correct Approach
"(a, a) appears once, so R is reflexive."	Reflexivity requires (x, x) ∈ R for ALL x ∈ A, not just one.	Check every element of A for a self-pair in R.
"R has no pair (a, b) with a ≠ b, so R is not symmetric."	Symmetry uses a conditional: IF (a,b) ∈ R THEN (b,a) ∈ R. When the hypothesis is never satisfied, the conditional is vacuously true.	A relation with no off-diagonal pairs (e.g., the identity) IS symmetric.
"I found (a,b) and (b,c) with (a,c) ∈ R, so R is transitive."	You verified one chain. Transitivity requires ALL chains to have shortcuts.	Enumerate every pair of composable edges and verify each shortcut.
"The empty relation is not reflexive, not symmetric, and not transitive."	The empty relation ∅ on a non-empty set is symmetric and transitive (vacuously), but not reflexive.	Apply vacuous truth: if no pairs exist, conditionals in symmetry and transitivity are trivially satisfied.
"Symmetric + transitive implies reflexive."	This would require every element to appear in at least one pair. If some a ∈ A has no (a, x) ∈ R for any x, you can never derive (a, a).	Each property is independent. Always check all three separately.

Five common mistakes and corrections

✦

KEY TAKEAWAY — VACUOUS TRUTH

In formal logic, a conditional statement 'if P then Q' is true whenever P is false, regardless of Q. This is vacuous truth. Think of it like a contract: 'If it rains, the game is canceled' is not violated on a sunny day, even if the game goes ahead. Similarly, the empty relation satisfies symmetry and transitivity because there are no pairs to violate the conditions — the hypotheses of the conditionals are never true. However, reflexivity is an unconditional requirement (every element MUST have a self-pair), so it cannot be vacuously satisfied.

SECTION 8

Connections to Equivalence Relations & Partial Orders

The properties of reflexivity, symmetry, and transitivity do not exist in isolation — they combine to form the definitions of the most important classes of relations in mathematics. An equivalence relation (reflexive + symmetric + transitive) partitions a set into disjoint equivalence classes via the Fundamental Theorem of Equivalence Relations. A partial order (reflexive + antisymmetric + transitive) provides a hierarchy for comparing elements, as in the divisibility relation on integers or the subset relation on sets. Recognizing which combination of properties a relation satisfies immediately tells you what structural theorems and algorithms apply.

Relation Type	Reflexive	Symmetric	Antisymmetric	Transitive	Example
Equivalence	✓	✓	—	✓	≡ (mod n)
Partial Order	✓	—	✓	✓	⊆ on sets, ≤ on ℤ
Strict Partial Order	✗ (irrefl.)	—	✓ (asym.)	✓	< on ℤ, ⊂ on sets
Preorder	✓	—	—	✓	"reachable from" in a graph
Tolerance	✓	✓	—	—	"within distance ε"

Taxonomy of common relation types by their properties

Looking ahead, the concepts from this lesson extend naturally to closures — the reflexive closure, symmetric closure, and transitive closure of a relation R are the smallest relations containing R that satisfy the respective property. The transitive closure, computed via Warshall's algorithm in O(n³), has major applications in graph reachability, database query optimization, and formal language theory. Equivalence classes reappear in abstract algebra as cosets of normal subgroups, in topology as quotient spaces, and in programming language theory as α-equivalence of lambda terms.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Let A = {1, 2, 3} and R = ∅ (the empty relation on A). Is R reflexive? Symmetric? Transitive? Justify each answer using the definitions.

Show answer

R is not reflexive because reflexivity requires (1,1), (2,2), and (3,3) to be in R, but R = ∅ contains no pairs. R is symmetric because the conditional 'if (a,b) ∈ R then (b,a) ∈ R' is vacuously true — no pair (a,b) exists to violate it. Similarly, R is transitive because there exist no pairs (a,b) and (b,c) in R, so the transitivity conditional is vacuously true. The empty relation on a non-empty set is always symmetric and transitive but never reflexive.

Question 2: BASIC CALCULATION

Let A = {1, 2, 3, 4} and R = {(1,1), (2,2), (3,3), (4,4), (1,2), (2,3)}. Determine whether R is reflexive, symmetric, and transitive.

Show answer

Reflexive: Yes — (1,1), (2,2), (3,3), (4,4) are all in R, covering every element of A. Symmetric: No — (1,2) ∈ R but (2,1) ∉ R. This single counterexample suffices. Transitive: No — (1,2) ∈ R and (2,3) ∈ R, but (1,3) ∉ R. The chain from 1 to 2 to 3 lacks the required shortcut from 1 to 3. Therefore R is reflexive but neither symmetric nor transitive.

Question 3: INTERMEDIATE

Let A = {1, 2, 3} and R = {(1,1), (1,2), (1,3), (2,2), (2,3), (3,3)}. Verify each property. What named type of relation is R?

Show answer

Reflexive: Yes — diagonal pairs (1,1), (2,2), (3,3) are all present. Symmetric: No — (1,2) ∈ R but (2,1) ∉ R. Antisymmetric: Yes — for all distinct a, b, we never have both (a,b) and (b,a) in R. Transitive: Yes — checking all chains: (1,2)&(2,3) → (1,3) ✓, (1,2)&(2,2) → (1,2) ✓, (1,3)&(3,3) → (1,3) ✓, (2,3)&(3,3) → (2,3) ✓. Since R is reflexive, antisymmetric, and transitive, it is a partial order. In fact, this is a total order isomorphic to 1 ≤ 2 ≤ 3.

Question 4: APPLIED

In a database, a relation 'SameProject' on the set of employees is defined as: aPb if and only if employees a and b have worked on at least one common project. Assume every employee has worked on at least one project. Is this relation reflexive? Symmetric? Transitive? Explain with concrete scenarios.

Show answer

Reflexive: Yes — every employee shares a project with themselves (they've worked on at least one project, and they share it with themselves). Symmetric: Yes — if employee a shares a project with employee b, then b also shares that same project with a. The 'sharing a project' relationship is inherently bidirectional. Transitive: No — consider Alice (projects X, Y), Bob (projects Y, Z), and Carol (project Z only). Alice and Bob share project Y, Bob and Carol share project Z, but Alice and Carol share no projects. So transitivity fails. This relation is reflexive and symmetric but not transitive — it is a tolerance relation, not an equivalence relation.

Question 5: CRITICAL THINKING

Prove or disprove: If a relation R on a non-empty set A is both symmetric and transitive, and for every a ∈ A there exists some b ∈ A such that (a, b) ∈ R, then R is reflexive. (Hint: combine symmetry and transitivity to derive self-pairs.)

Show answer

Proof: Let a ∈ A be arbitrary. By hypothesis, there exists some b ∈ A with (a, b) ∈ R. Since R is symmetric, (b, a) ∈ R. Now we have (a, b) ∈ R and (b, a) ∈ R. By transitivity, (a, a) ∈ R. Since a was arbitrary, (a, a) ∈ R for all a ∈ A, so R is reflexive. Therefore the statement is true. The key insight is that the condition 'every element is related to something' (sometimes called 'serial' or 'left-total') fills the gap that ordinarily prevents symmetric + transitive from implying reflexive. Without this condition, an element might be completely unrelated to everything, and we could never derive its self-pair.

SUMMARY

Lesson Summary

Summary

A binary relation R on a set A is a subset of A × A. To determine whether R possesses fundamental properties, apply three tests: reflexivity requires (a, a) ∈ R for every a ∈ A — check every diagonal entry or self-loop. Symmetry requires that (a, b) ∈ R implies (b, a) ∈ R — verify that the relation matrix equals its transpose or that every directed edge is bidirectional. Transitivity requires that (a, b) ∈ R and (b, c) ∈ R together imply (a, c) ∈ R — check that every two-hop path has a direct shortcut. A single counterexample disproves any property, while proving a property requires exhaustive verification of all cases.

When all three properties hold, R is an equivalence relation that partitions A into disjoint equivalence classes. When R is reflexive, antisymmetric, and transitive, it forms a partial order. Understanding these properties and their interactions is essential for discrete mathematics, abstract algebra, database design, and formal verification. Always watch for vacuous truth — the empty relation is symmetric and transitive (vacuously) but not reflexive on a non-empty set. Use relation matrices and directed graphs as complementary tools to visualize and verify these properties systematically.