Reflexive, Symmetric and Transitive Relations

definitions
discrete-math
set-theory
relations
proof

The three properties a relation on a single set can have, what each looks like in an arrow diagram, and how to prove or disprove each one. Relations themselves are defined in relations-on-sets. The lecture is 2026-09-17-relations-reflexivity-symmetry-transitivity.

The definitions

A relation \(\rho\) on a set \(A\) is

(1) reflexive if and only if \(\forall x \in A,\ x \mathrel{\rho} x\).

(2) symmetric if and only if \(\forall x, y \in A,\ x \mathrel{\rho} y \to y \mathrel{\rho} x\).

(3) transitive if and only if \(\forall x, y, z \in A,\ (x \mathrel{\rho} y \text{ and } y \mathrel{\rho} z) \to x \mathrel{\rho} z\).

In the arrow diagram:

  • reflexive — every dot has a loop;
  • symmetric — every arrow has a return arrow;
  • transitive — every path of two arrows has a direct arrow from its start to its end, the short cut.

A relation fails a property when the diagram contains one of the patterns in Figure 1. Each is a witness — one specific element, pair or triple. Nothing more is needed to disprove a “for all”.

Figure 1: What a failure of each property looks like; any one such pattern in a diagram disproves the property. Not reflexive: one element without a loop. Not symmetric: one arrow whose return is missing. Not transitive: one path of two arrows whose short cut is missing. The fourth panel is the not-transitive pattern with \(z = x\): a round trip \(x \to y \to x\) needs the short cut \(x \to x\), a loop, so two elements joined both ways but without loops already break transitivity. The missing arrows are dashed.

Reading the definitions carefully

Reflexive is about every element. “\(\forall x \in A\)” means a single element without a loop is enough to make a relation not reflexive, even if every other element has one. Disjointness, \(X \mathrel{\rho} Y \leftrightarrow X \cap Y = \emptyset\) on \(\mathcal{P}(\mathbb{Z}^{+})\), is not reflexive, though \(\emptyset \mathrel{\rho} \emptyset\) holds.

Symmetric and transitive are conditional. They say what must happen if certain arrows are present. Where those arrows are absent, the condition holds automatically, by vacuous truth (conditional-statements). This is why a relation with very few arrows can be symmetric and transitive. The empty relation on any set is both, and so is \(\{(1,1)\}\) on \(\{1,2\}\).

\(x\), \(y\), \(z\) need not be different. In the transitive condition, \(z\) may equal \(x\). Then it reads: if \(x \mathrel{\rho} y\) and \(y \mathrel{\rho} x\), then \(x \mathrel{\rho} x\). In a transitive relation, any two elements related both ways both have loops. Three of the transitivity counterexamples in 2026-09-17-relations-reflexivity-symmetry-transitivity use exactly this: \(\{1\}\) and \(\{2\}\) are disjoint both ways but \(\{1\}\) is not disjoint from itself; in Diagram 1 \(b \to a \to b\) exists but the loop at \(b\) does not; and for \(xy \equiv 1 \pmod 7\), \(2 \to 4 \to 2\) exists but \(2 \mathrel{\not\rho} 2\).

Proving and disproving

Each property is a universal statement, so proving it needs a general argument about arbitrary elements, while disproving it needs one witness (quantified-statements, proof-techniques):

To prove it To disprove it
reflexive Let \(x \in A\). Show \(x \mathrel{\rho} x\). Find one \(x \in A\) with \(x \mathrel{\not\rho} x\).
symmetric Let \(x, y \in A\) and suppose \(x \mathrel{\rho} y\). Show \(y \mathrel{\rho} x\). Find \(x, y \in A\) with \(x \mathrel{\rho} y\) but \(y \mathrel{\not\rho} x\).
transitive Let \(x, y, z \in A\) and suppose \(x \mathrel{\rho} y\) and \(y \mathrel{\rho} z\). Show \(x \mathrel{\rho} z\). Find \(x, y, z \in A\) with \(x \mathrel{\rho} y\) and \(y \mathrel{\rho} z\) but \(x \mathrel{\not\rho} z\).

In every proof, unfold the definition of \(\rho\) — turn \(x \mathrel{\rho} y\) into the condition it stands for, work with that, and fold it back up at the end. For a disproof, give specific elements and check each of the stated facts about them.

Worked: \(m \mathrel{\rho} n \leftrightarrow 6 \mid (m - n)\) on \(\mathbb{Z}\)

All three hold. Unfold with the definition of divides (divisibility-and-factorisation): \(m \mathrel{\rho} n\) means \(m - n = 6k\) for some \(k \in \mathbb{Z}\).

  • Reflexive. Let \(m \in \mathbb{Z}\). Then \(m - m = 0 = 6 \cdot 0\), so \(6 \mid (m - m)\) and \(m \mathrel{\rho} m\).
  • Symmetric. Let \(m, n \in \mathbb{Z}\) with \(m \mathrel{\rho} n\), so \(m - n = 6k\) for some \(k \in \mathbb{Z}\). Then \(n - m = 6(-k)\) and \(-k \in \mathbb{Z}\), so \(6 \mid (n - m)\) and \(n \mathrel{\rho} m\).
  • Transitive. Let \(m, n, p \in \mathbb{Z}\) with \(m \mathrel{\rho} n\) and \(n \mathrel{\rho} p\), so \(m - n = 6k\) and \(n - p = 6\ell\) for some \(k, \ell \in \mathbb{Z}\). Adding, \(m - p = 6(k + \ell)\) with \(k + \ell \in \mathbb{Z}\), so \(m \mathrel{\rho} p\).

Its diagram on \(\{0, \dots, 11\}\) is drawn in relations-on-sets. The second divisibility gets a new variable \(\ell\): reusing \(k\) would claim that \(m - n\) and \(n - p\) are the same multiple of 6.

Worked: \(x \mathrel{\rho} y \leftrightarrow x > y\) on \(\mathbb{Z}\)

  • Not reflexive. \(0 > 0\) is false, so \(0 \mathrel{\not\rho} 0\).
  • Not symmetric. \(1 \mathrel{\rho} 0\) since \(1 > 0\), but \(0 \mathrel{\not\rho} 1\) since \(0 > 1\) is false.
  • Transitive. Suppose \(x > y\) and \(y > z\). Then \(x > z\), so \(x \mathrel{\rho} z\).

Worked: divides, on \(\{1, 2, \dots, 6\}\)

\(x \mathrel{\rho} y \leftrightarrow x \mid y\) is reflexive (\(x = x \cdot 1\)), not symmetric (\(1 \mid 2\) but \(2 \nmid 1\)), and transitive: if \(y = xk\) and \(z = y\ell\) then \(z = x(k\ell)\). The diagram shows all three at once.

Figure 2: The relation \(x \mid y\) on \({1, 2, \dots, 6}\), with the numbers placed so every arrow points upward. Reflexive: a loop at every number, since each number divides itself. Not symmetric: no arrow comes back down — \(1 \mid 2\), but \(2 \nmid 1\). Transitive: every two-step path has its short cut, such as \(1 \to 2 \to 4\) with the direct arrow \(1 \to 4\). There are 14 arrows: 6 loops and 8 others.

Checking a finite relation from its diagram

For a relation given as a diagram or a list of pairs:

  1. Reflexive: look for a loop at every element. Any element without one is the witness.
  2. Symmetric: for each non-loop arrow, look for its return. Any arrow without one is the witness.
  3. Transitive: for each arrow \(x \to y\), look at every arrow leaving \(y\), say \(y \to z\), and check that \(x \to z\) is there. Include the paths that come back, \(x \to y \to x\), whose short cut is a loop. This is the slow check, and the round trips are where it usually goes wrong.

The same procedure answers “what must be added to make it reflexive, symmetric, transitive”: the missing loops, the missing returns, and the missing short cuts. For transitivity, keep checking after adding, because a new arrow can create new two-step paths. This is worked on Diagram 1 in 2026-09-17-relations-reflexivity-symmetry-transitivity.

The examples side by side

Relation on Reflexive Symmetric Transitive
\(X \subset Y\) (proper subset) \(\mathcal{P}(\{1,2,3\})\) no no yes
\(X \cap Y = \emptyset\) \(\mathcal{P}(\mathbb{Z}^{+})\) no yes no
Diagram 1 \(\{a,b,c,d\}\) no no no
\(xy \equiv 1 \pmod 7\) \(\{0, \dots, 6\}\) no yes no
\(\{(1,1)\}\) \(\{1, 2\}\) no yes yes
\(6 \mid (m - n)\) \(\mathbb{Z}\) yes yes yes
\(x > y\) \(\mathbb{Z}\) no no yes
\(x \mid y\) \(\{1, \dots, 6\}\) yes no yes

The first five are worked in 2026-09-17-relations-reflexivity-symmetry-transitivity; the other three are worked above. The three properties are independent, and most of the eight combinations appear here. Relations with all three, like \(6 \mid (m - n)\), are equivalence relations (equivalence-relations). Relations like \(x \mid y\) — reflexive and transitive, with no two different elements related both ways — are partial orders (partial-order-relations). Those are the next two topics in the course.

Symmetric and transitive do not make reflexive

Claim. If a relation \(\rho\) on a set \(A\) is both symmetric and transitive, then \(\rho\) is reflexive. — False.

Counterexample. \(A = \{1, 2\}\), \(\rho = \{(1,1)\}\). Symmetric: the only pair is \((1,1)\), whose reverse is itself. Transitive: the only two-step path is \(1 \to 1 \to 1\), whose short cut \((1,1)\) is present. Not reflexive: \(2 \mathrel{\not\rho} 2\).

The tempting “proof” goes: let \(x \in A\); take \(y\) with \(x \mathrel{\rho} y\); by symmetry \(y \mathrel{\rho} x\); by transitivity \(x \mathrel{\rho} x\). Every step is valid except the second. Nothing guarantees there is any \(y\) with \(x \mathrel{\rho} y\). The element 2 in the counterexample is related to nothing, so there is nothing to start the argument from. Adding the missing hypothesis makes the claim true:

If \(\rho\) is symmetric and transitive, and for each \(x \in A\) there is some \(y \in A\) with \(x \mathrel{\rho} y\), then \(\rho\) is reflexive.

The proof is the tempting argument above, now legitimate. The picture is the right-hand panel of 2026-09-17-relations-reflexivity-symmetry-transitivity.

See also