Relations as Sets of Ordered Pairs
A relation records which elements of one set are associated with which elements of another. The set-of-pairs viewpoint makes this precise: a relation contains exactly the ordered pairs for which the association holds. When both entries come from the same set, three useful tests ask whether every element is related to itself, whether pairs can be reversed, and whether two successive relations imply a third.
An ordered pair remembers which entry comes first. Thus \((x,y)\) and \((y,x)\) are not interchangeable: they are equal only when \(x=y\). The relation notation \(xRy\) is just another way to say that the particular ordered pair \((x,y)\) belongs to the subset \(R\). It does not, by itself, imply that \(yRx\), or that there is only one \(y\) associated with \(x\).
For a relation \(R\subseteq X\times Y\), its domain is the set of elements of \(X\) related to at least one element of \(Y\), and its range is the set of elements of \(Y\) related to at least one element of \(X\). In set notation these are \(\{x\in X:\text{there is }y\in Y\text{ with }(x,y)\in R\}\) and \(\{y\in Y:\text{there is }x\in X\text{ with }(x,y)\in R\}\), respectively. A relation need not include every element of either set in its domain or range.
Worked Example: Relating People to Courses
Let \(X=\{\text{Ada},\text{Ben}\}\) and \(Y=\{\text{Topology},\text{Algebra}\}\). Consider the relation \(R\) from \(X\) to \(Y\) in which a person is related to a course when that person is enrolled in it. Suppose Ada is enrolled in both courses and Ben is enrolled in Topology. The relation, written as a subset of \(X\times Y\), is
Membership can be checked pair by pair. The pair \((\text{Ada},\text{Algebra})\) is listed, so \(\text{Ada}\,R\,\text{Algebra}\). The pair \((\text{Ben},\text{Algebra})\) is not listed, so \(\text{Ben}\,R\,\text{Algebra}\) is false. The domain is \(\{\text{Ada},\text{Ben}\}\), because each person occurs as a first entry. The range is \(\{\text{Topology},\text{Algebra}\}\), because each course occurs as a second entry.
This relation is not a function from \(X\) to \(Y\): Ada is related to two different elements of \(Y\), so there is not exactly one output for each input. A relation with no pair beginning with some \(x\in X\) would also fail to be a function from \(X\) to \(Y\), because a function must assign an output to every input.
Check: there are four possible pairs in \(X\times Y\), namely the two choices of first entry paired with the two choices of second entry. The displayed relation contains three of them and omits exactly \((\text{Ben},\text{Algebra})\). This agrees with the enrollment description and confirms the stated domain and range.
Three Properties of Relations on One Set
Reflexivity, symmetry, and transitivity are properties of a relation on one set, meaning \(R\subseteq X\times X\). For a relation from \(X\) to a different set \(Y\), these tests are not defined in this form: for instance, reflexivity would ask whether \(xRx\) for every \(x\in X\), but the second entry is required to come from \(Y\).
Each condition has its own quantifiers and implication. Reflexivity requires all diagonal pairs \((x,x)\). Symmetry requires reversing every pair that is present. Transitivity concerns every two pairs whose second and first entries match, and asks that the pair joining their outside entries is also present.
Proof. For (1), suppose \(R\) is reflexive. For each \(x\in X\), \(xRx\), so \((x,x)\in R\). Therefore every element of the displayed diagonal set belongs to \(R\). Conversely, if that diagonal set is contained in \(R\), then \((x,x)\in R\) for each \(x\in X\), which says exactly that \(R\) is reflexive. If \(X=\varnothing\), both conditions hold: there are no diagonal pairs to omit and the requirement “for every \(x\in X\)” has no counterexample.
For (2), suppose \(R\) is symmetric. If \((x,y)\in R\), symmetry gives \((y,x)\in R\), so every pair in \(R\) belongs to \(R^{\mathrm{op}}\). Hence \(R\subseteq R^{\mathrm{op}}\). Reversing the same implication shows \(R^{\mathrm{op}}\subseteq R\), so the two sets are equal. Conversely, if \(R=R^{\mathrm{op}}\) and \((x,y)\in R\), then \((y,x)\in R^{\mathrm{op}}=R\). This is symmetry.
For (3), the stated condition is precisely the definition of transitivity, written using ordered-pair membership: \(xRy\) means \((x,y)\in R\), and \(yRz\) means \((y,z)\in R\). Thus the condition holds if and only if \(R\) is transitive. Each argument also covers \(X=\varnothing\), since there are no choices of \(x,y,z\) for which a condition could fail. \(\square\)
Worked Example: A Relation with All Three Properties
Let \(X=\{a,b,c\}\), and define \(R\subseteq X\times X\) by
Reflexivity. The required diagonal pairs for \(X\) are \((a,a)\), \((b,b)\), and \((c,c)\). All three occur in \(R\), so \(R\) is reflexive.
Symmetry. The pairs \((a,a)\), \((b,b)\), and \((c,c)\) reverse to themselves. The pair \((a,b)\) reverses to \((b,a)\), which is in \(R\), and \((b,a)\) reverses to \((a,b)\), also in \(R\). Every pair has its reverse, so \(R\) is symmetric.
Transitivity. The elements \(a\) and \(b\) are each related to both \(a\) and \(b\), and \(c\) is related only to \(c\). If \(xRy\) and \(yRz\), then either all of \(x,y,z\) lie in \(\{a,b\}\), or all three are \(c\). In the first case every ordered pair of elements of \(\{a,b\}\) belongs to \(R\), so \((x,z)\in R\). In the second case \((x,z)=(c,c)\in R\). Thus \(R\) is transitive.
Check: the four pairs whose entries lie in \(\{a,b\}\) are \((a,a),(a,b),(b,a),(b,b)\), and all four are listed. The only pair with an entry \(c\) is \((c,c)\). Therefore the case check above accounts for every possible composable pair and establishes transitivity without omitting a case.
The Converse and Symmetry
The converse reverses the order of each pair. This gives a set-level way to check symmetry: compare the relation with the set obtained by reversing all its pairs. The comparison must use the same underlying set \(X\), so that both \(R\) and \(R^{\mathrm{op}}\) are subsets of \(X\times X\).
Proof. Suppose \(R\) is symmetric. Take any \((x,y)\in R\). By symmetry, \((y,x)\in R\), and therefore \((x,y)\in R^{\mathrm{op}}\) by the definition of converse. This gives \(R\subseteq R^{\mathrm{op}}\). Now take any \((y,x)\in R^{\mathrm{op}}\). By definition, \((x,y)\in R\); symmetry gives \((y,x)\in R\). Hence \(R^{\mathrm{op}}\subseteq R\), and equality follows. Conversely, suppose \(R=R^{\mathrm{op}}\) and let \((x,y)\in R\). The definition of converse gives \((y,x)\in R^{\mathrm{op}}\). Since \(R^{\mathrm{op}}=R\), we have \((y,x)\in R\). Thus \(R\) is symmetric. \(\square\)
Worked Example: Testing the Three Properties Separately
Let \(X=\{1,2,3\}\) and let
Reflexivity. The diagonal pairs required for \(X\) are exactly \((1,1),(2,2),(3,3)\), and each is in \(R\). Hence \(R\) is reflexive.
Symmetry. Since \((1,2)\in R\), symmetry would require \((2,1)\in R\). That reverse pair is absent from the displayed set. Thus \(R\) is not symmetric. The pair \((2,3)\) also lacks its reverse \((3,2)\).
Transitivity. We have \((1,2)\in R\) and \((2,3)\in R\). Transitivity would require \((1,3)\in R\), but this pair is absent. Thus \(R\) is not transitive.
Check: the converse contains the reversed pairs, so it is \(\{(1,1),(2,2),(3,3),(2,1),(3,2)\}\). It differs from \(R\), confirming the failed symmetry test. The two listed pairs \((1,2)\) and \((2,3)\) give a specific failed transitivity test, so no search through other pairs can make \(R\) transitive.
A Common Mix-Up
Common pitfall. Do not confuse the test for symmetry with the test for transitivity. For the relation in the previous example, a mistaken check might say: “\((1,2)\) and \((2,3)\) are in \(R\), so the relation is symmetric.” Those two pairs do not check symmetry; symmetry asks for the reversed pair \((2,1)\) whenever \((1,2)\) is present. Since \((2,1)\notin R\), the relation is not symmetric. The two pairs instead test transitivity, which would require \((1,3)\); that pair is also absent, so the relation is not transitive either.
Another frequent error is to test only the pairs that happen to be present and forget what each property requires. Reflexivity requires a diagonal pair for every element of \(X\), including elements that appear in no other pair. For example, if \(X=\{a,b,c\}\) and \(R=\{(a,a),(b,b)\}\), then \(R\) is not reflexive because \((c,c)\notin R\). Symmetry and transitivity are implications: a missing required reverse or composite pair disproves the property, while an implication with a false premise does not create a failure.
These checks apply to arbitrary relations, not only relations described by a verbal rule. For a finite set, list the pairs, identify the diagonal pairs, reverse each listed pair to test symmetry, and inspect every pair of entries that can be joined to test transitivity. For an infinite set, use the defining quantifiers and a general argument rather than relying on a finite list of samples.
Check Your Understanding
For each relation, state which of reflexivity, symmetry, and transitivity hold, and justify your answers from the definitions.
- Let \(X=\{p,q\}\) and \(R=\{(p,p),(q,q),(p,q)\}\). Which properties does \(R\) have?
- Let \(X=\{1,2,3\}\) and \(S=\{(1,1),(2,2),(3,3),(1,3),(3,1)\}\). Write \(S^{\mathrm{op}}\), and use it to test symmetry.
- Give a relation on \(X=\{a,b\}\) that is symmetric but not reflexive. Verify both claims.
- Explain why reflexivity, symmetry, and transitivity as defined here concern relations on one set rather than arbitrary relations from \(X\) to \(Y\).
- For \(X=\varnothing\), which of the three properties does the empty relation on \(X\) satisfy? Explain using the quantifiers in the definitions.