Relations and their properties: reflexive, symmetric, antisymmetric, transitive
Equal to, at most, divides, has the same parity as. Each compares two things in order. What do all such comparisons have in common, and which habits decide whether one sorts things into groups or lines them up?
Where you are 15 in Sets
Why this exists
The statements 3 \le 5, 4 \mid 12 and \{1\} \subseteq \{1, 2\} each answer yes or no about two objects in order. A relation gathers every yes answer into one set of ordered pairs (Relations and functions). Four properties separate the comparisons that behave like equality, sorting a set into groups, from those that behave like \le, arranging it in layers, and say exactly where any other relation falls short.
Definition
Day 1: relations and their four properties
Relation. A relation from A to B is any subset R of the product A \times B (Cartesian product). A relation on A is a subset of A \times A. When (a, b) \in R we write a \mathrel{R} b and say a is related to b; when (a, b) \notin R, it is not. Order matters: a \mathrel{R} b and b \mathrel{R} a are different claims. The relation \le on \mathbb{R} is the set \{(x, y) \in \mathbb{R}^2 : x \le y\}, and 3 \le 5 says (3, 5) is in it.
Three pictures of a finite relation. A relation R on a finite set A can be given as
- the list of its pairs;
- an arrow diagram: a dot for each member of A, an arrow from a to b whenever a \mathrel{R} b, and a loop at a when a \mathrel{R} a;
- a matrix: a square table with one row and one column for each member of A, in the same order, holding 1 in row a, column b when a \mathrel{R} b and 0 otherwise.
The four properties. Let R be a relation on A. Each property is a universal statement, so it fails exactly when one counterexample exists (Negating a quantified statement).
- R is reflexive when \forall a \in A,\ a \mathrel{R} a. It fails when some a \in A has (a, a) \notin R: one missing loop.
- R is symmetric when \forall a, b \in A,\ a \mathrel{R} b \to b \mathrel{R} a. It fails when some a \mathrel{R} b has (b, a) \notin R: one arrow with no return arrow.
- R is antisymmetric when \forall a, b \in A,\ (a \mathrel{R} b \land b \mathrel{R} a) \to a = b. It fails when some a \neq b have a \mathrel{R} b and b \mathrel{R} a: two distinct members joined both ways.
- R is transitive when \forall a, b, c \in A,\ (a \mathrel{R} b \land b \mathrel{R} c) \to a \mathrel{R} c. It fails when some a \mathrel{R} b and b \mathrel{R} c have (a, c) \notin R: a two-step path with no shortcut.
In the last two, the letters need not name different members: transitivity with c = a says that a \mathrel{R} b and b \mathrel{R} a force a \mathrel{R} a.
Day 2: equivalence relations and partial orders
Equivalence relation. A relation that is reflexive, symmetric and transitive. Equality on any set is one; so is “has the same parity as” on \mathbb{Z}. An equivalence relation sorts its set into groups of mutually related members, its equivalence classes, which are the subject of Relations, equivalence classes and partitions.
Partial order. A relation that is reflexive, antisymmetric and transitive. A set with a partial order is a partially ordered set, written (A, \preceq). Examples: \le on \mathbb{R}; \subseteq on the Power set of a set; and divides on the positive integers, with its diagram of the divisors of 30 (Divisibility as a relation). Members a and b are comparable when a \preceq b or b \preceq a. A total order is a partial order in which every two members are comparable: \le is total, while \{1\} and \{2\} are not comparable under \subseteq. The strict relation < is not a partial order, since (1, 1) \notin {<}.
Hasse diagram. In a partial order, b covers a when a \preceq b, a \neq b, and no third member c has a \preceq c \preceq b. The Hasse diagram of a finite partial order draws a dot for each member, places b higher than a whenever a \preceq b and a \neq b, and draws a line only when b covers a. Loops and lines implied by chains are left off, since reflexivity and transitivity supply them: a \preceq b exactly when an upward path, possibly of length zero, runs from a to b.
Intuition
Figures 1 and 2 show one relation two ways (Example 1).
Each property is something visible.
- Reflexive: a loop at every dot; a 1 in every diagonal cell of the matrix.
- Symmetric: every arrow between distinct dots has a return arrow; the matrix is its own mirror image across the diagonal.
- Antisymmetric: no two distinct dots are joined both ways; no 1 off the diagonal has a 1 in its mirror cell. Loops are allowed.
- Transitive: every two-step path a \to b \to c has a direct arrow a \to c, and a round trip a \to b \to a needs a loop at a.
A relation on \mathbb{R} is a region of the plane, the point (x, y) standing for x \mathrel{R} y. Reflexive means the region contains the line y = x; symmetric means reflection in that line, which swaps the coordinates, leaves the region unchanged (Figure 3).
Results
Symmetric and antisymmetric together. Write \Delta_A = \{(a, a) : a \in A\}, the equality relation on A. A relation R on A is both symmetric and antisymmetric exactly when R \subseteq \Delta_A.
Counting relations. A set with n members has 2^{n^2} relations on it, and 2^{n^2 - n} of them are reflexive.
Why it is true
Symmetric and antisymmetric together.
Proof. Suppose R is symmetric and antisymmetric, and let (a, b) \in R. Symmetry gives b \mathrel{R} a, and then antisymmetry, applied to a \mathrel{R} b and b \mathrel{R} a, gives a = b. So every pair in R is some (a, a), and R \subseteq \Delta_A.
Conversely, suppose R \subseteq \Delta_A. If a \mathrel{R} b, then a = b. So b \mathrel{R} a is the statement a \mathrel{R} a, which holds, and R is symmetric; and the conclusion a = b of antisymmetry holds whenever a \mathrel{R} b, so R is antisymmetric. \square
Counting relations. The set A \times A has n \cdot n = n^2 pairs, and a relation on A is any subset of it, so there are 2^{n^2} (Power set). A reflexive relation must contain the n pairs of \Delta_A and may contain any choice of the other n^2 - n, giving 2^{n^2 - n}.
Worked examples
Examples 1 to 3 go with Day 1, Examples 4 to 7 with Day 2.
Three pictures of one relation
Let A = \{1, 2, 3, 4\} and R = \{(1, 1), (1, 2), (2, 1), (2, 3), (3, 3), (4, 2)\}. Draw the arrow diagram and the matrix of R. Is 2 \mathrel{R} 3? Is 3 \mathrel{R} 2? Which members a have a \mathrel{R} 2?
SolutionEach pair becomes one arrow, and (1, 1) and (3, 3) become loops (Figure 1). In the matrix, row a records the pairs that begin with a: row 2 has 1s in columns 1 and 3 because (2, 1) and (2, 3) are in R (Figure 2). There are six 1s, one per pair.
Since (2, 3) \in R, 2 \mathrel{R} 3 holds. Row 3, column 2 holds 0, so (3, 2) \notin R. The members related to 2 are read down column 2: 1 \mathrel{R} 2 and 4 \mathrel{R} 2.
Checking the four properties
On A = \{1, 2, 3, 4\}, take R from Example 1, S = \{(1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (3, 1)\} and T = \{(1, 2), (2, 3), (1, 3), (4, 4)\}. Decide all four properties for each, with a counterexample for every property that fails.
SolutionR fails all four. Not reflexive: (2, 2) \notin R. Not symmetric: 2 \mathrel{R} 3 but (3, 2) \notin R. Not antisymmetric: 1 \mathrel{R} 2 and 2 \mathrel{R} 1 with 1 \neq 2. Not transitive: 4 \mathrel{R} 2 and 2 \mathrel{R} 1, but (4, 1) \notin R.
S. Reflexive: all four loops are present. Symmetric: the only pairs of distinct members are (1, 3) and (3, 1), each the reverse of the other. Not antisymmetric: 1 \mathrel{S} 3 and 3 \mathrel{S} 1 with 1 \neq 3. Transitive: a chain through a loop returns its other pair, which is in S; the chains with no loop, 1 \to 3 \to 1 and 3 \to 1 \to 3, need (1, 1) and (3, 3), which are present. So S is an equivalence relation, with groups \{1, 3\}, \{2\}, \{4\}.
T. Not reflexive: (1, 1) \notin T. Not symmetric: 1 \mathrel{T} 2 but (2, 1) \notin T. Antisymmetric: no two distinct members are joined both ways. Transitive: list every chain. A chain through (1, 2) continues only with (2, 3), and the shortcut (1, 3) is in T. Nothing in T starts at 3, so (2, 3) and (1, 3) begin no chain. The loop (4, 4) chains only with itself and returns (4, 4). Every chain has its shortcut.
Symmetric, antisymmetric, both, neither
On B = \{1, 2, 3\}, find a relation that is both symmetric and antisymmetric, and one that is neither. Then decide all four properties for the empty relation \varnothing.
SolutionBy the first result, a relation is both exactly when all its pairs lie on the diagonal. So \{(1, 1), (3, 3)\} is both; it is not reflexive, since (2, 2) is missing, so neither property needs reflexivity.
For neither, take \{(1, 2), (2, 1), (2, 3)\}. The arrow 2 \to 3 has no return, so it is not symmetric; 1 and 2 are joined both ways with 1 \neq 2, so it is not antisymmetric.
For \varnothing, the conditionals defining symmetric, antisymmetric and transitive never have a true hypothesis, so all three hold vacuously (Truth table for the conditional). It is not reflexive: (1, 1) \notin \varnothing.
So “antisymmetric” is not “not symmetric”. Symmetry demands that every arrow between distinct members come back, and antisymmetry forbids it; with no such arrows both hold.
An equivalence relation on the rationals
On the nonzero rational numbers \mathbb{Q} \setminus \{0\}, let x \mathrel{R} y mean that xy = r^2 for some rational number r. Prove that R is an equivalence relation.
SolutionProof. Reflexive. For any nonzero rational x, x \cdot x = x^2 with x rational, so x \mathrel{R} x.
Symmetric. Suppose x \mathrel{R} y, so xy = r^2 for some rational r. Then yx = xy = r^2, so y \mathrel{R} x.
Transitive. Suppose x \mathrel{R} y and y \mathrel{R} z, so xy = r^2 and yz = s^2 for some rationals r and s. Multiplying gives x y^2 z = r^2 s^2, and since y \neq 0 we may divide by y^2:
A quotient of rationals with a nonzero divisor is rational, so \displaystyle \frac{rs}{y} is rational and x \mathrel{R} z. \square
Since xy \neq 0 and a square is never negative, related numbers have the same sign; the group of 1 holds exactly the squares of nonzero rationals, such as 4 and \displaystyle \frac{1}{9}. The step dividing by y^2 is where the set matters. On all of \mathbb{Q}, 2 \cdot 0 = 0^2 and 0 \cdot (-1) = 0^2, so 2 \mathrel{R} 0 and 0 \mathrel{R} (-1), yet 2 \cdot (-1) = -2 is no square: there the relation is reflexive and symmetric but not transitive.
A relation on the real line
On \mathbb{R}, let x \mathrel{R} y mean y - x \ge 1. Decide all four properties.
SolutionNot reflexive. x - x = 0 < 1, so no real number is related to itself; (0, 0) \notin R is one counterexample.
Not symmetric. 0 \mathrel{R} 1, but 0 - 1 = -1, so (1, 0) \notin R.
Antisymmetric. Suppose x \mathrel{R} y and y \mathrel{R} x. Then y - x \ge 1 and x - y \ge 1, and adding gives 0 \ge 2, which is false. The hypothesis of the conditional never holds, so the conditional is true for every x and y.
Transitive. If y - x \ge 1 and z - y \ge 1, then z - x = (z - y) + (y - x) \ge 2 \ge 1, so x \mathrel{R} z.
Lacking reflexivity, R is not a partial order.
In Figure 3 the region misses the line y = x, so it holds no pair (x, x), and its mirror image in that line lies on and below y = x - 1, never meeting it: no two numbers are related both ways.
Related, but not transitively
On the positive integers, let a \mathrel{R} b mean that the decimal numerals of a and b have at least one digit in common. Decide all four properties.
SolutionReflexive: every numeral shares its digits with itself. Symmetric: “a and b have a digit in common” says the same thing in either order. Not antisymmetric: 12 \mathrel{R} 21 and 21 \mathrel{R} 12, yet 12 \neq 21.
Not transitive: 13 \mathrel{R} 37 through the digit 3, and 37 \mathrel{R} 72 through 7, but 13 and 72 share no digit, so (13, 72) \notin R.
So R is reflexive and symmetric but not an equivalence relation: resemblance passed along a chain can be gone by the far end.
A partial order on pairs
On \mathbb{Z} \times \mathbb{Z}, let (a, b) \preceq (c, d) mean a \le c and b \le d. Prove that \preceq is a partial order, show that it is not total, and draw the Hasse diagram of its restriction to P = \{0, 1, 2\} \times \{0, 1\}.
SolutionProof. Reflexive: a \le a and b \le b, so (a, b) \preceq (a, b).
Antisymmetric: if (a, b) \preceq (c, d) and (c, d) \preceq (a, b), then a \le c \le a and b \le d \le b, so a = c and b = d, and the pairs are equal by the rule for equal pairs.
Transitive: if (a, b) \preceq (c, d) and (c, d) \preceq (e, f), then a \le c \le e and b \le d \le f. By transitivity of \le, a \le e and b \le f, so (a, b) \preceq (e, f). \square
Not total. (1, 0) \preceq (0, 1) would need 1 \le 0, and (0, 1) \preceq (1, 0) would need 1 \le 0 as well. So (1, 0) and (0, 1) are not comparable.
The Hasse diagram. In P, (c, d) covers (a, b) exactly when one coordinate goes up by 1 and the other stays put; a larger step has a pair strictly between, as (1, 0) lies between (0, 0) and (1, 1). Raising the first coordinate gives 4 lines and raising the second gives 3, so the diagram has 7 lines (Figure 4).
The order itself has 18 pairs, since each (a, b) lies below the (3 - a)(2 - b) pairs with both coordinates at least as large, and (3 + 2 + 1)(2 + 1) = 18; the diagram needs only 7 lines.
Boundaries
A relation includes its set. Divides is antisymmetric on the positive integers, but on \mathbb{Z}, 2 \mid -2 and -2 \mid 2.
Reflexive means every member. One loop is not enough, and on a nonempty set the empty relation is not reflexive though it has the other three properties (Example 3).
Hasse diagrams need covers. In \le on \mathbb{R} no number covers another, since \displaystyle \frac{x + y}{2} lies strictly between any x < y, so this order has no Hasse diagram.
Where this goes next
Relations, equivalence classes and partitions gathers the members related to one member into a class, and the classes split the set into nonoverlapping pieces. A function is a relation with exactly one arrow leaving each member, the subject of One-to-one, onto and bijective functions and Composing functions between sets, and when an inverse exists.
Exercises
Day 1: relations and their pictures
- Let A = \{p, q, r\} and R = \{(p, q), (q, q), (r, p)\}. Write the matrix of R, with rows and columns in the order p, q, r, and describe its arrow diagram. Is R a function from A to A?
- The matrix below gives a relation on \{1, 2, 3\}, rows and columns in the order 1, 2, 3. List its pairs, and name a familiar relation it equals.
- On \{1, 2, 3\}, let a \mathrel{R} b mean a + b \le 4. List R and decide all four properties.
- How many relations are there on a set with 3 members? On a set with 4 members?
Day 1: the four properties
- Decide all four properties for each relation on \{1, 2, 3\}, with a counterexample for each one that fails. (a) \{(1, 1), (2, 2), (3, 3), (1, 2)\} (b) \{(1, 2), (2, 1)\} (c) \{(1, 2), (2, 3), (3, 1)\} (d) \{1, 2, 3\} \times \{1, 2, 3\}
- Let R = \{(1, 2), (2, 3)\} on \{1, 2, 3\}. What is the fewest pairs that must be added to make R transitive? To make it reflexive and transitive?
- Give a relation on \{1, 2, 3\} that is reflexive and symmetric but not transitive.
- How many relations on \{1, 2, 3\} are symmetric? How many are reflexive? How many are both?
Day 1: reasoning
- Using quantifiers, write the negation of “R is transitive” and of “R is antisymmetric”.
- Explain how to read from the matrix of a relation whether it is reflexive, whether it is symmetric and whether it is antisymmetric.
Day 2: relations on infinite sets
- On \mathbb{Z}, let a \mathrel{R} b mean that ab is odd. Decide all four properties.
- On \mathbb{R}, let x \mathrel{R} y mean x^2 \le y^2. Decide all four properties. Which property of a partial order does R lack?
- On \mathbb{Z}, let a \mathrel{R} b mean a \le b + 1. Decide all four properties.
- On \mathbb{Z} \times \mathbb{Z}, let (a, b) \mathrel{R} (c, d) mean a + d = b + c. Prove that R is an equivalence relation, and describe the pairs related to (0, 0).
Day 2: partial orders
- A Hasse diagram has four dots: w at the bottom, x and y side by side above it, and z at the top, with lines w to x, w to y, x to z and y to z. List every pair of the partial order. Is it total?
- Let L be the set of strings of length at most 2 in the alphabet \{a, b\}, the empty string \lambda included, and let u \preceq v mean that v begins with u. Taking as given that this is a partial order, describe its Hasse diagram, and count its lines and the pairs of the order.
- On the positive integers, let a \preceq b mean b = 2^k a for some k \in \mathbb{N}, where \mathbb{N} = \{0, 1, 2, \dots\}. Prove that \preceq is a partial order, and describe its Hasse diagram on \{1, 2, \dots, 8\}.
Day 2: reasoning
- The inverse of a relation R on A is R^{-1} = \{(b, a) : (a, b) \in R\}. Prove that R is symmetric if and only if R = R^{-1}.
- Prove that the intersection of two transitive relations on A is transitive. Show by an example that their union need not be.
- Let R be reflexive and transitive on A, and let a \mathrel{S} b mean a \mathrel{R} b and b \mathrel{R} a. Prove that S is an equivalence relation.
- Prove that equality, \Delta_A, is the only relation on A that is both an equivalence relation and a partial order.
Answers
- The matrix is \begin{bmatrix} 0 & 1 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}. The diagram has arrows p \to q and r \to p and a loop at q. It is a function: exactly one arrow leaves each member, taking p to q, q to q and r to p.
- \{(1, 2), (1, 3), (2, 3)\}, the relation < on \{1, 2, 3\}.
- R = \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (3, 1)\}. Not reflexive: 3 + 3 = 6 > 4, so (3, 3) \notin R. Symmetric, since a + b = b + a. Not antisymmetric: 1 \mathrel{R} 2 and 2 \mathrel{R} 1. Not transitive: 3 \mathrel{R} 1 and 1 \mathrel{R} 3, but (3, 3) \notin R.
- 2^9 = 512 and 2^{16} = 65{,}536.
- (a) Reflexive; not symmetric, (2, 1) missing; antisymmetric; transitive, since every chain uses a loop. A partial order. (b) Not reflexive, (1, 1) missing; symmetric; not antisymmetric, 1 \mathrel{R} 2 and 2 \mathrel{R} 1; not transitive, since 1 \mathrel{R} 2, 2 \mathrel{R} 1 but (1, 1) is missing. (c) Not reflexive; not symmetric, (2, 1) missing; antisymmetric, as no pair has its reverse; not transitive, since 1 \mathrel{R} 2, 2 \mathrel{R} 3 but (1, 3) is missing. (d) Reflexive, symmetric and transitive, since every pair is present; not antisymmetric, 1 \mathrel{R} 2 and 2 \mathrel{R} 1. An equivalence relation.
- One pair: the chain 1 \to 2 \to 3 forces (1, 3), and \{(1, 2), (2, 3), (1, 3)\} is transitive. Four pairs for both: (1, 3), (1, 1), (2, 2), (3, 3).
- For example \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2)\}: 1 \mathrel{R} 2 and 2 \mathrel{R} 3, but (1, 3) is missing.
- Symmetric: the 3 loops are free, and each of the 3 sets \{a, b\} with a \neq b puts both (a, b) and (b, a) in or neither: 2^3 \cdot 2^3 = 64. Reflexive: 2^{9 - 3} = 64. Both: 2^3 = 8.
- Not transitive: \exists a, b, c \in A,\ a \mathrel{R} b \land b \mathrel{R} c \land (a, c) \notin R. Not antisymmetric: \exists a, b \in A,\ a \mathrel{R} b \land b \mathrel{R} a \land a \neq b.
- Reflexive: every diagonal entry is 1. Symmetric: row a, column b always equals row b, column a, so the matrix is its own mirror image across the diagonal. Antisymmetric: for a \neq b those two entries are never both 1; the diagonal is unrestricted.
- Not reflexive: 2 \cdot 2 = 4 is even. Symmetric: ab = ba. Not antisymmetric: 1 \cdot 3 = 3 is odd, so 1 \mathrel{R} 3 and 3 \mathrel{R} 1, with 1 \neq 3. Transitive: if ab is odd, then a and b are odd, since an even factor makes a product even; likewise bc odd makes c odd. Then ac, a product of odd numbers, is odd.
- Reflexive: x^2 \le x^2. Not symmetric: 0 \mathrel{R} 1, since 0 \le 1, but 1 \le 0 is false. Not antisymmetric: 1 \mathrel{R} (-1) and (-1) \mathrel{R} 1, since 1 \le 1, yet 1 \neq -1. Transitive: x^2 \le y^2 and y^2 \le z^2 give x^2 \le z^2 by transitivity of \le. So R is reflexive and transitive, and antisymmetry is the only property of a partial order it lacks.
- Reflexive: a \le a + 1. Not symmetric: 0 \mathrel{R} 5, since 0 \le 6, but 5 \le 1 is false. Not antisymmetric: 0 \mathrel{R} 1 and 1 \mathrel{R} 0, since 0 \le 2 and 1 \le 1. Not transitive: 2 \mathrel{R} 1 and 1 \mathrel{R} 0, but 2 \le 1 is false.
- Proof. Reflexive: a + b = b + a. Symmetric: from a + d = b + c, rearranging gives c + b = d + a. Transitive: if a + d = b + c and c + f = d + e, adding gives a + d + c + f = b + c + d + e, and cancelling c + d gives a + f = b + e. \square The pairs related to (0, 0) satisfy 0 + d = 0 + c: the pairs (c, c) with equal coordinates.
- (w, w), (x, x), (y, y), (z, z), (w, x), (w, y), (w, z), (x, z), (y, z): nine pairs. Not total: x and y are not comparable.
- A tree: \lambda at the bottom, a and b above it, aa and ab above a, ba and bb above b; each string covers itself minus its last letter, so 6 lines. A string of length n has n + 1 prefixes, so the pairs number 1 + 4 + 12 = 17.
- Proof. Reflexive: a = 2^0 a. Antisymmetric: if b = 2^k a and a = 2^j b, then a = 2^{j + k} a, and a > 0 gives 2^{j + k} = 1, so j = k = 0 and a = b. Transitive: if b = 2^k a and c = 2^j b, then c = 2^{j + k} a with j + k \in \mathbb{N}. \square On \{1, \dots, 8\}: a chain 1, 2, 4, 8, a chain 3, 6, and lone dots 5 and 7, so 4 lines.
- Proof. Suppose R is symmetric. If (a, b) \in R, then (b, a) \in R, so (a, b) \in R^{-1}. If (a, b) \in R^{-1}, then (b, a) \in R, and symmetry gives (a, b) \in R. So R = R^{-1}. Conversely, if R = R^{-1} and a \mathrel{R} b, then (b, a) \in R^{-1} = R. \square
- Proof. Let R and S be transitive, with (a, b) and (b, c) in R \cap S. Both pairs are in R, so (a, c) \in R; both are in S, so (a, c) \in S. Hence (a, c) \in R \cap S. \square For the union, \{(1, 2)\} and \{(2, 3)\} on \{1, 2, 3\} are each transitive, having no chains, but their union lacks the shortcut (1, 3).
- Proof. Reflexive: a \mathrel{R} a, so a \mathrel{S} a. Symmetric: the definition of a \mathrel{S} b reads the same with a and b swapped. Transitive: from a \mathrel{S} b and b \mathrel{S} c, a \mathrel{R} b and b \mathrel{R} c give a \mathrel{R} c, and c \mathrel{R} b and b \mathrel{R} a give c \mathrel{R} a. So a \mathrel{S} c. \square
- Proof. Equality is reflexive, symmetric, antisymmetric and transitive, so it is both. Now let R be both. Reflexivity gives \Delta_A \subseteq R, and symmetry with antisymmetry gives R \subseteq \Delta_A by the first result. So R = \Delta_A. \square