Properties of Relations: Reflexive, Symmetric, Transitive

The four properties are the entry point to two of the most heavily used structures in mathematics: an Equivalence Relation (reflexive + symmetric + transitive) underlies every construction that partitions objects into "the same" classes — modular arithmetic ($a \equiv b \pmod n$), rational numbers as equivalence classes of fraction pairs, isomorphism classes of groups or graphs, and the equality of cardinalities in set theory. A partial order (reflexive + antisymmetric + transitive) underlies subset inclusion in set theory, divisibility in number theory, componentwise comparison of vectors, and the specialization order in topology; antisymmetry specifically is what allows a partial order to be drawn as a Hasse diagram without ambiguity. In computer science, transitive relations govern reachability in graphs and the correctness of algorithms computing transitive closure (used in database query optimization for recursive joins, and in compiler dataflow analysis); reflexive-transitive closures appear as the kernel of regular-expression and automaton theory. In type theory and functional programming, equivalence relations model observational equivalence between programs, while preorders (reflexive + transitive, without requiring antisymmetry) model refinement and subtyping relations where "ties" between distinct types are meaningful. In statistics and machine learning, symmetric relations model similarity/distance matrices used in clustering, while the failure of transitivity in "indistinguishability" relations (as in Example 2) is a standard cautionary example in decision theory, where intransitive preferences ($A \succ B \succ C \succ A$) are studied as genuine paradoxes of rational choice. In cryptography and complexity theory, reductions between problems form a preorder (reflexive and transitive but generally not antisymmetric, since two problems can reduce to each other without being identical), which is exactly the structure underlying the definition of NP-completeness. Antisymmetric-but-not-total orders also appear in scheduling and dependency resolution (e.g. build systems, package managers), where task $A$ must precede task $B$ without every pair of tasks being comparable — precisely the divisibility-style structure of Example 1.

Ask the tutor: Can you show me why "differ by at most $k$" relations are never transitive for finite $k$ on an unbounded set, using a general argument instead of one example?

Picture $A$ as a finite set of dots and $R$ as a collection of arrows: draw an arrow from $a$ to $b$ whenever $(a,b) \in R$. Reflexivity says every dot has a loop back to itself. Symmetry says arrows always come in back-and-forth pairs — if you can travel from $a$ to $b$, you can always travel back. Antisymmetry says the opposite extreme for the reflexive pairs: the only two-way loops allowed are the trivial loops at a single dot; distinct dots never have arrows going both directions. Transitivity says arrows compose: any two-step journey $a \to b \to c$ must already have a direct shortcut arrow $a \to c$. A second useful picture, especially for finite $A$, is the relation matrix: index rows and columns by elements of $A$, and place a $1$ in position $(a,b)$ if $aRb$, else a $0$. Reflexivity means the diagonal is all $1$s. Symmetry means the matrix equals its own transpose. Antisymmetry means that off the diagonal, you never see a $1$ in both position $(a,b)$ and position $(b,a)$. Transitivity is a genuine combinatorial condition on the pattern of $1$s that does not reduce to a simple visual symmetry, which is why it is the hardest of the four to check by eye and the one most often gotten wrong.

The left picture shows a relation that is perfectly symmetric (every arrow has a return arrow) yet fails transitivity: $1R2$ and $2R3$ hold, but there is no arrow directly from $1$ to $3$. The right picture shows the reverse failure mode: it is transitive (the one nontrivial chain $1\to2\to3$ does have its shortcut $1\to3$ present), but it is not symmetric, since $1R2$ holds while $2R1$ does not. These two pictures already prove that symmetry and transitivity are logically independent properties — neither implies the other.

Each direction above is a direct translation between a quantified logical statement and a set membership statement, using only the definitions of $\Delta_A$, $R^{-1}$, $R \circ R$, and the four relation properties; no part of the argument in either direction assumes the conclusion being proved, so the proof is non-circular, and it uses only the technique of mutual set inclusion (showing $X \subseteq Y$ and $Y \subseteq X$) together with direct unwinding of quantifiers — no external machinery from equivalence relations or order theory is invoked.

Example 1: Divisibility on the positive integers, restricted to a finite set. Let $A = \{1,2,3,4,6,8,12\}$ and define $R$ on $A$ by

We determine which of the four properties $R$ has, with full justification. Reflexivity. For every $a \in A$, $a \mid a$ since $a = a \cdot 1$. This holds for all seven elements of $A$ (checking: $1\mid1,\,2\mid2,\,3\mid3,\,4\mid4,\,6\mid6,\,8\mid8,\,12\mid12$ — all true). So $R$ is reflexive. Symmetry. We claim $R$ is not symmetric, and a single counterexample pair suffices: $2 \mid 4$ (since $4 = 2\cdot 2$), but $4 \nmid 2$ (there is no integer $k$ with $2 = 4k$, since $4k \geq 4 > 2$ for $k \geq 1$ and $4k \le 0$ for $k \le 0$). Since $\exists a,b$ with $aRb$ and $\neg(bRa)$, the universally quantified symmetry statement is false. Antisymmetry. Suppose $a \mid b$ and $b \mid a$ with $a, b$ positive integers. Then $b = a k$ and $a = b m$ for some positive integers $k, m$ (positivity follows since all elements of $A$ are positive, so quotients are positive integers). Substituting, $a = a k m$, so (since $a \neq 0$) $km = 1$. As $k, m$ are positive integers, the only solution is $k = m = 1$, giving $a = b$. This argument is valid for arbitrary positive integers, hence in particular for all $a, b \in A$, so $R$ is antisymmetric. Transitivity. Suppose $a \mid b$ and $b \mid c$, i.e. $b = ak$, $c = bl$ for positive integers $k, l$. Then $c = (ak)l = a(kl)$, and $kl$ is a positive integer, so $a \mid c$. This holds for arbitrary positive integers $a,b,c$, hence for all triples in $A$, so $R$ is transitive. Conclusion. $R$ is reflexive, antisymmetric, and transitive, but not symmetric. (This is exactly the pattern required for a partial order — divisibility is the textbook example of a non-total partial order, foreshadowed further below.)

Example 2: "Differ by at most 3" on a finite set of integers. Let $A = \{0, 1, 2, 5, 9\}$ and define

We again check all four properties, and this example is chosen so that transitivity genuinely fails, which requires producing an explicit witnessing triple. Reflexivity. For every $a \in A$, $|a - a| = 0 \leq 3$. True for all five elements, so $R$ is reflexive. Symmetry. If $|a-b| \le 3$ then since $|b - a| = |a-b|$ (absolute value is symmetric under negation: $|-x|=|x|$), we get $|b-a| \le 3$ too. This holds for arbitrary $a, b \in A$ (indeed for arbitrary reals), so $R$ is symmetric. Antisymmetry. Consider $a = 1, b = 2$. Then $|1-2| = 1 \le 3$, so $1R2$; and $|2-1| = 1 \le 3$, so $2R1$. Both hold, yet $1 \neq 2$. This single witness refutes the universally quantified antisymmetry condition, so $R$ is not antisymmetric. Transitivity. Consider $a = 0,\ b = 2,\ c = 5$, all in $A$. We compute $|0 - 2| = 2 \le 3$, so $0R2$. We compute $|2-5| = 3 \le 3$, so $2R5$. But $|0 - 5| = 5 \not\le 3$, so $\neg(0 R 5)$. Thus $0R2$ and $2R5$ hold while $0R5$ fails — an explicit witnessing triple $(a,b,c) = (0,2,5)$ that refutes transitivity. So $R$ is not transitive. Conclusion. $R$ is reflexive and symmetric, but neither antisymmetric nor transitive. This shows that reflexive + symmetric alone is far from sufficient for equivalence-relation behavior: transitivity is doing genuine work, and this example is exactly the standard illustration that "closeness" relations (differ by at most $k$) typically fail to be transitive, which is why they are not equivalence relations despite looking superficially similar to one.