Lecture 23 — Relations on Sets; Reflexivity, Symmetry and Transitivity
Pre-work: Video 029 (Relations on sets) and Video 030 (Reflexivity, Symmetry and Transitivity). The reference notes are relations-on-sets for what a relation is and how to draw one, and reflexive-symmetric-and-transitive-relations for the three properties and how to prove or disprove them. A relation is a generalised function, so functions-on-general-sets is the starting point.
Learning goals
- Understand binary relations on sets.
- Know how to draw and interpret an arrow diagram (a “directed graph”) for a relation.
- Understand what it means for a relation to be reflexive, symmetric or transitive.
- Know how to prove or disprove that a relation is reflexive, symmetric or transitive.
One relation can be drawn two ways. First as two ellipses, both labelled \(A\), holding \(1, 2, 3, 4\), with arrows \(1 \to 1\), \(3 \to 3\), \(4 \to 1\), \(4 \to 3\), \(4 \to 4\). Then as a single set of four dots, with a loop at 1, 3 and 4, an arrow from 4 to 1 and from 4 to 3, and 2 on its own. Both are drawn as Figure 2 below.
Two questions to start with
The distinction between functions and relations (Q2 from video 29). Every function is a relation. A relation is not necessarily a function.
The definitions of reflexive, symmetric and transitive (Q1, Q2 and Q3 from video 30). The three questions are answered after the definitions.
Functions, then relations
Start from the definition of a function as a set of pairs (functions-on-general-sets). It has two conditions, for each \(a \in A\) and unique:
A subset \(f\) of \(A \times B\) is a function from a set \(A\) to a set \(B\) if for each \(a \in A\), there is a unique \(b \in B\) such that \((a,b) \in f\). \[f(a) = b \leftrightarrow (a,b) \in f, \qquad f = \{(1,0),(2,2),(3,4),(4,4)\}, \qquad f(1) = 0;\ f(2) = 2;\ f(3) = 4;\ f(4) = 4.\]
A relation drops both conditions:
Any subset \(\rho\) of \(A \times B\) is a binary relation from \(A\) to \(B\). \[\rho = \{(1,0),(3,4),(4,0),(4,4),(4,6)\}, \qquad 1 \mathrel{\rho} 0;\ 3 \mathrel{\rho} 4;\ 4 \mathrel{\rho} 0;\ 4 \mathrel{\rho} 4;\ 4 \mathrel{\rho} 6.\]
A relation on a set \(A\) is a binary relation from \(A\) to \(A\).
A relation \(\rho\) on \(A\) is often defined by a condition such as: \(x \mathrel{\rho} y \leftrightarrow x > y\) for all \(x, y \in A\), \(\quad X \mathrel{\rho} Y \leftrightarrow X \cap Y = \emptyset\) for all \(X, Y \in A\), \(\quad m \mathrel{\rho} n \leftrightarrow 6\) divides \(m - n\) for all \(m, n \in A\).
Reading the notation:
- \((1,0) \in \rho\) means the same as \(1 \mathrel{\rho} 0\), read “1 is related in \(\rho\) to 0”. The 1 of \((1,0)\) comes from the domain and the 0 from the co-domain. The first coordinate is where the arrow starts.
- \(\rho\) “rho”, \(\sigma\) “sigma”, \(\tau\) “tau” — the Greek letters relations are named with, as \(f, g, h\) are for functions.
- The one-set drawing of a relation on \(A\) uses a single copy of \(A\).
Figure 1: The same two sets, a function and a relation. Left: in the function \(f\) every element of \(A\) has exactly one arrow leaving it — that is the whole definition. Right: in the relation \(\rho\) there is no rule at all. 2 has no arrow, 4 has three, and 0 and 4 in \(B\) are each hit twice. Every function is a relation, the special kind with one arrow per element of the domain; a relation is just any set of arrows.
Figure 2: One relation on \(A = {1,2,3,4}\), \(\rho = {(1,1),(3,3),(4,1),(4,3),(4,4)}\), in its two drawings. Left: two copies of \(A\) with arrows from the left copy to the right, as for a function. Right: a single copy of \(A\), the directed graph. Each arrow keeps its start and end, and an arrow from an element to itself becomes a loop. The single-copy drawing is the one to use for a relation on one set, because the three properties below are all about loops, return arrows and short cuts, and those only show up when each element is drawn once.
Reflexivity, symmetry and transitivity
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\).
Each definition has a picture:
| Picture | In symbols | |
|---|---|---|
| reflexive | a loop at \(a\) | \(\forall a \in A,\ a \mathrel{\rho} a\) |
| symmetric | \(a \to b\) above, \(b \to a\) below | \(\forall a, b \in A,\ a \mathrel{\rho} b \to b \mathrel{\rho} a\) |
| transitive | \(a \to b \to c\) along the top, and \(a \to c\) underneath | \(\forall a, b, c \in A,\ a \mathrel{\rho} b \text{ and } b \mathrel{\rho} c \to a \mathrel{\rho} c\) |
Three points about the transitive definition:
- Could have \(x = z\). \(x, y, z\) are any elements of \(A\), not three different ones, so the transitive condition applies with \(z = x\).
- That gives if \(x \mathrel{\rho} y\) and \(y \mathrel{\rho} x\) then \(x \mathrel{\rho} x\), with the weight on the if. Transitivity applied to \(x \to y \to x\) demands the short cut from \(x\) to \(x\), a loop.
- In a transitive relation a two-way pair \(x \rightleftarrows y\) forces loops at both ends (\(y \to x \to y\) gives \(y \mathrel{\rho} y\) as well). So \(x \rightleftarrows y\) with no loops is, on its own, not transitive.
This observation is behind the transitivity counterexamples for disjoint sets (the first one), Diagram 1 and the relation mod 7, and behind the extra hypothesis in the last worked question. It is drawn as Figure 6.
Worked: proper subset on a power set
Questions 1, 2 and 3 from video 30.
Let \(S = \{1,2,3\}\) and consider the relation \(\rho\) defined on the power set of \(S\), \(\mathcal{P}(S)\), by \(X \mathrel{\rho} Y\) if and only if \(X \subset Y\), for all \(X, Y \in \mathcal{P}(S)\).
Q1. True or False: the relation \(\rho\) is reflexive. — False Q2. True or False: the relation \(\rho\) is symmetric. — False Q3. True or False: the relation \(\rho\) is transitive. — True
The reasons for Q2 and Q3: \(X \subset Y \nRightarrow Y \subset X\), and \(X \subset Y\) and \(Y \subset Z \to X \subset Z\) ✓. The power set is \(\mathcal{P}(S) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}\), eight sets. The arrow diagram has a dot for each, with arrows from \(\emptyset\) to all seven other sets, then \(\{1\} \to \{1,2\}\), \(\{1\} \to \{1,2,3\}\) and \(\{1,2\} \to \{1,2,3\}\), and so on: 19 arrows in total.
\(\subset\) is proper subset in this course (sets-and-set-notation), and that is what makes Q1 false. \(X \subset X\) is never true, so there is not a single loop. With \(\subseteq\) instead, Q1 would be true and there would be 27 arrows, the 19 plus a loop at each of the 8 sets. Q2 is false with one witness, \(\emptyset \subset \{1\}\) but \(\{1\} \not\subset \emptyset\).
Figure 3: The relation \(X \subset Y\) on \(\mathcal{P}({1,2,3})\) in full, with the sets in layers by size. Blue arrows add one element (12 of them), orange arrows add two (6), and the green arrow adds all three (1): 19 in total. There are no loops, since no set is a proper subset of itself, so the relation is not reflexive. Every arrow points upward and none comes back, so it is not symmetric. Every two-step path has its one-step short cut — the orange and green arrows are exactly those short cuts — so it is transitive.
Worked: disjoint sets
Let \(\rho\) be the relation on \(\mathcal{P}(\mathbb{Z}^{+})\) defined by \(X \mathrel{\rho} Y \leftrightarrow X \cap Y = \emptyset\).
Is \(\rho\) reflexive? \(X \cap X = X\). E.g. \(\{1,2\} \cap \{1,2\} = \{1,2\} \neq \emptyset\), so \(X \mathrel{\not\rho} X\). \(\rho\) is NOT reflexive.
Is \(\rho\) symmetric? Yes. \(X \cap Y = Y \cap X\), so \(\forall X, Y \in \mathcal{P}(\mathbb{Z}^{+})\), if \(X \mathrel{\rho} Y\) then \(Y \mathrel{\rho} X\).
Is \(\rho\) transitive? \(X = \{1\}\), \(Y = \{2\}\), \(Z = \{1\}\): here \(X \mathrel{\rho} Y\) and \(Y \mathrel{\rho} Z\) but \(X \mathrel{\not\rho} Z\). Not transitive. \(X = \{1,2\}\), \(Y = \{3,4\}\), \(Z = \{1,5\}\) also shows not transitive.
The reflexive definition starts \(\forall a \in A\). That quantifier is why one example settles the question. Reflexive is a “for all”, so it fails as soon as one element lacks its loop, even though some elements have one: \(\emptyset \cap \emptyset = \emptyset\), so \(\emptyset \mathrel{\rho} \emptyset\). The first transitivity counterexample uses \(Z = X\), the could have \(x = z\) case: \(\{1\}\) and \(\{2\}\) are related both ways, so transitivity would force \(\{1\} \mathrel{\rho} \{1\}\), which is false. The second shows the same failure with three different sets.
Worked: reading the properties off Diagram 1
Let \(\rho\) be the relation defined by the arrow diagram in Diagram 1.
Diagram 1 has four points \(a, b, c, d\). The arrows are a loop at \(a\), both \(a \to b\) and \(b \to a\), then \(a \to c\), \(a \to d\), \(b \to c\), \(b \to d\), \(c \to d\), and a loop at \(d\). As a set, \[\rho = \{(a,a), (a,b), (b,a), (a,c), (a,d), (b,c), (b,d), (c,d), (d,d)\}.\]
Is \(\rho\) reflexive? No. E.g. \(b \mathrel{\not\rho} b\), or \((b,b) \notin \rho\). Either notation is fine.
Is \(\rho\) symmetric? No. We have \(b \mathrel{\rho} c\) but \(c \mathrel{\not\rho} b\).
Is \(\rho\) transitive? No. We have \(b \mathrel{\rho} a\) and \(a \mathrel{\rho} b\) but \(b \mathrel{\not\rho} b\).
What is missing for each property:
- To make \(\rho\) reflexive: add \((b,b)\) and \((c,c)\).
- To make \(\rho\) symmetric: add \((c,a)\), \((d,a)\), \((c,b)\), \((d,c)\), \((d,b)\).
- To make \(\rho\) transitive: add \((b,b)\).
The three definitions each start with a quantifier, \(\forall a\), \(\forall a, b\) and \(\forall a, b, c\). Each “no” needs only the specific elements that break it.
Figure 4: Diagram 1 and what each property would need added, dashed in green. Reflexive: the two missing loops, at \(b\) and \(c\). Symmetric: a return arrow for each of the five one-way arrows. Transitive: only the loop at \(b\), forced by the round trip \(b \to a \to b\) — every other two-step path, such as \(a \to c \to d\) or \(b \to a \to d\), already has its short cut. The transitivity check is the slow one: it means looking at every two-step path, not just at pairs of points.
Worked: an arrow diagram mod 7
Draw an arrow diagram for the relation \(\rho\) on \(\{0,1,2,3,4,5,6\}\) defined by \(x \mathrel{\rho} y\) if and only if \(xy \equiv 1 \pmod 7\).
Working: numbers \(\equiv 1 \pmod 7\) are \(1, 8, 15, 22, 29, 36, \dots\). \(0 \cdot y \not\equiv 1 \pmod 7\), so 0 is related to nothing. \(1 \cdot y \equiv 1 \pmod 7\) (so 1 is related only to 1). The diagram has 0 on its own, loops at 1 and 6, arrows both ways between 2 and 4, and both ways between 3 and 5.
Is \(\rho\) reflexive? No, e.g. \(5 \mathrel{\not\rho} 5\).
Is \(\rho\) symmetric? Yes.
Is \(\rho\) transitive? No. For example \(2 \mathrel{\rho} 4\) and \(4 \mathrel{\rho} 2\) but \(2 \mathrel{\not\rho} 2\).
Figure 5: The relation \(xy \equiv 1 \pmod 7\) on \({0, 1, \dots, 6}\). The products that leave remainder 1 are \(1 \cdot 1 = 1\), \(2 \cdot 4 = 8\), \(3 \cdot 5 = 15\) and \(6 \cdot 6 = 36\). Each non-zero number is related to exactly one partner, the number it multiplies with to give 1, and 0 to nothing. Symmetric, because \(xy = yx\). Not reflexive: only 1 and 6 have loops. Not transitive: \(2 \to 4 \to 2\) would need a loop at 2.
Worked: symmetric and transitive, but not reflexive
Prove or disprove the following statement. If a relation \(\rho\) on a set \(A\) is both symmetric and transitive, then \(\rho\) is reflexive.
The statement is false. E.g. \(A = \{1,2\}\), \(\rho = \{(1,1)\}\). The diagram is a loop at 1, and 2 on its own.
\(\rho\) is symmetric and transitive but NOT reflexive (since \(2 \mathrel{\not\rho} 2\)).
- symmetric: \(\forall a, b \in A\) if \(a \mathrel{\rho} b\) then \(b \mathrel{\rho} a\) ✓
- transitive: \(\forall a, b, c \in A\) if \(a \mathrel{\rho} b\) and \(b \mathrel{\rho} c\) then \(a \mathrel{\rho} c\) ✓
The if is the point of the counterexample. Symmetry and transitivity are conditional. They say what must happen if some arrows are present, and they are satisfied without argument wherever those arrows are absent. The only arrow in \(\rho\) is the loop \((1,1)\). Its “return arrow” and its “short cut” are the same loop, so both conditions hold. Element 2 has no arrows at all, so neither condition ever mentions it, and nothing forces a loop there.
One more hypothesis repairs it:
If we also knew that for each \(x \in A\), \(x \mathrel{\rho} y\) for some \(y \in A\), then the statement becomes true.
With that extra hypothesis, take any \(x\). It has an arrow to some \(y\). Symmetry gives the arrow back, and transitivity on \(x \to y \to x\) gives the loop at \(x\). The picture is \(x \rightleftarrows y\) with a loop at each end. This is the if \(x \mathrel{\rho} y\) and \(y \mathrel{\rho} x\) then \(x \mathrel{\rho} x\) observation from the definitions above, and it is the proof that people write without the extra hypothesis. The step “take a \(y\) with \(x \mathrel{\rho} y\)” is exactly where it breaks, because such a \(y\) need not exist.
Figure 6: Why symmetric and transitive do not make a relation reflexive, and what would. Left: \(\rho = {(1,1)}\) on \({1, 2}\) is symmetric and transitive but not reflexive; 2 has no arrows, so neither condition ever says anything about it. Right: once \(x\) has an arrow to some \(y\), symmetry supplies \(y \to x\), and transitivity along \(x \to y \to x\) forces the loop at \(x\) (and along \(y \to x \to y\), the loop at \(y\)). The forced arrows are dashed. The loop depends on \(x\) being related to something.
See also
- relations-on-sets — relations as sets of pairs, the notation \(x \mathrel{\rho} y\), and the two ways to draw one
- reflexive-symmetric-and-transitive-relations — the three properties, their pictures, and how to prove and disprove each
- functions-on-general-sets — functions as the special relations with one arrow out of each element
- 2026-09-15-countable-and-uncountable-sets — Lecture 22 · 2026-09-21-equivalence-relations — Lecture 24
- practice-problems — §29 · practice-problems — §30, with full worked solutions