2.4 Properties of Relations

Chapter 1 made relations into sets: a relation on a set $X$ is a subset $R \subseteq X \times X$ , and $x \mathrel{R} y$ means $(x, y) \in R$ (Definition 1.3.3). It named the properties that make a relation an order or an equivalence and left them to this chapter. Equality, $\le$ , inclusion $\subseteq$ , divisibility $\mid$ , and “leaves the same remainder on division by $3$ ” are all relations, and they behave alike in some ways and differently in others. This section names four properties that sort them, proves the ones that divisibility has, and collects witnesses for every failure. Sections 2.5 and 2.6 then study the two combinations that matter most.

2.4.1. Four properties

Start from equality. Every $x$ equals itself; if $x = y$ , then $y = x$ ; and if $x = y$ and $y = z$ , then $x = z$ . The relation $\le$ on $\mathbb{R}$ keeps the first and third of these and loses the second, but it has a substitute: $x \le y$ and $y \le x$ together force $x = y$ . Each of these is a property a relation may or may not have.

Each property is one rule for what the relation must contain, given what it already contains.

Definition 2.4.1 (Properties of a Relation)

Let $X$ be a set and $R$ a relation on $X$ . Then $R$ is

reflexive on $X$ if $x \mathrel{R} x$ for every $x \in X$ : $\forall x \in X \ \ x \mathrel{R} x ;$
symmetric if $x \mathrel{R} y$ implies $y \mathrel{R} x$ , for all $x, y \in X$ : $\forall x \in X \ \forall y \in X \ \ \bigl( x \mathrel{R} y \to y \mathrel{R} x \bigr) ;$
antisymmetric if $x \mathrel{R} y$ and $y \mathrel{R} x$ together imply $x = y$ , for all $x, y \in X$ : $\forall x \in X \ \forall y \in X \ \ \bigl( (x \mathrel{R} y \wedge y \mathrel{R} x) \to x = y \bigr) ;$
transitive if $x \mathrel{R} y$ and $y \mathrel{R} z$ together imply $x \mathrel{R} z$ , for all $x, y, z \in X$ : $\forall x \in X \ \forall y \in X \ \forall z \in X \ \ \bigl( (x \mathrel{R} y \wedge y \mathrel{R} z) \to x \mathrel{R} z \bigr) .$

In words: reflexive says every element is related to itself. Symmetric says the relation can be read backwards: whenever it relates $x$ to $y$ , it also relates $y$ to $x$ . Antisymmetric says it can be read both ways only between an element and itself. Transitive says two steps can always be replaced by one.

Three of the four are implications, so a relation has them unless some related pair (or triple) makes the conclusion false: for symmetry and transitivity a pair is missing from $R$ , and for antisymmetry two different elements are related both ways. Negating with Logic and Proof, Proposition 6.2.3 and Logic and Proof, Proposition 6.2.2 turns each failure into a witness: $\begin{aligned} \text{not reflexive:} \quad & \exists x \in X \ \ \neg (x \mathrel{R} x) , \\ \text{not symmetric:} \quad & \exists x \in X \ \exists y \in X \ \ \bigl( x \mathrel{R} y \wedge \neg (y \mathrel{R} x) \bigr) , \\ \text{not antisymmetric:} \quad & \exists x \in X \ \exists y \in X \ \ \bigl( (x \mathrel{R} y \wedge y \mathrel{R} x) \wedge x \ne y \bigr) , \\ \text{not transitive:} \quad & \exists x \in X \ \exists y \in X \ \exists z \in X \ \ \bigl( (x \mathrel{R} y \wedge y \mathrel{R} z) \wedge \neg (x \mathrel{R} z) \bigr) . \end{aligned}$ So “not symmetric” is shown by one pair related in one direction only, and “not transitive” by one triple. A single witness settles a failure; a success needs an argument for all elements.

Reading a relation as a picture. Draw the elements of $X$ as points and an arrow from $x$ to $y$ whenever $x \mathrel{R} y$ . The relation $\le$ on $\{1, 2, 3\}$ is $\{ (1, 1), (2, 2), (3, 3), (1, 2), (1, 3), (2, 3) \}$ :

Reflexive means a loop at every point. Symmetric means every arrow has a return arrow. Antisymmetric means no two different points are joined in both directions. Transitive means every path of two arrows has a direct arrow from its start to its end. In the picture there are loops everywhere, no return arrows, and the two-arrow path $1 \to 2 \to 3$ has its shortcut $1 \to 3$ ; so $\le$ on $\{1, 2, 3\}$ is reflexive, antisymmetric and transitive, and not symmetric, with witness the pair $(1, 2)$ . A path may also return to its start: $x \to y \to x$ . Transitivity then demands the loop at $x$ . That case is the source of the warning below.

Why “reflexive on $X$ ”. The other three properties mention elements only when they are related, so they depend on the set $R$ alone. Reflexivity depends on $X$ too. The relation $\{(0, 0)\}$ is reflexive on $\{0\}$ , and the same set of pairs, viewed as a relation on $\{0, 1\}$ , is not reflexive on $\{0, 1\}$ , with witness $1$ . That is why the definition names the set.

2.4.2. Divisibility

Divisibility shows that the same rule can give an antisymmetric relation on one set and not on a larger one, because the larger set brings in more pairs: $\mid$ on $\mathbb{Z}$ contains both $(2, -2)$ and $(-2, 2)$ , which $\mid$ on $\mathbb{N}$ does not. Recall Definition 2.2.1: for integers $a, b$ , $a \mid b$ means $b = ka$ for some $k \in \mathbb{Z}$ .

Proposition 2.4.1 (Divisibility on the Natural Numbers)

The relation $\mid$ is reflexive, antisymmetric and transitive on $\mathbb{N}$ . On $\mathbb{Z}$ it is reflexive and transitive, and not antisymmetric.

Idea. Reflexivity and transitivity are one line each from Definition 2.2.1. For antisymmetry, $b = ka$ and $a = lb$ give $a = lka$ . If $a \ne 0$ , this forces $kl = 1$ , and for positive integers that means $k = l = 1$ . On $\mathbb{N}$ the multipliers are positive, so $b = a$ ; on $\mathbb{Z}$ they may both be $-1$ .

Proof. Reflexive. For every integer $a$ , $a = 1 \cdot a$ , so $a \mid a$ .

Transitive. Let $a \mid b$ and $b \mid c$ , say $b = ka$ and $c = lb$ with $k, l \in \mathbb{Z}$ . Then $c = (lk)a$ , and $lk \in \mathbb{Z}$ by Proposition 2.1.2 (a), so $a \mid c$ .

These two arguments work for all integers, so on $\mathbb{N}$ and on $\mathbb{Z}$ .

Antisymmetric on $\mathbb{N}$ . Let $a, b \in \mathbb{N}$ with $a \mid b$ and $b \mid a$ , say $b = ka$ and $a = lb$ with $k, l \in \mathbb{Z}$ .

Case 1: $a = 0$ or $b = 0$ . If $a = 0$ , then $b = k \cdot 0 = 0$ ; if $b = 0$ , then $a = l \cdot 0 = 0$ . Either way $a = b$ .

Case 2: $a \ne 0$ and $b \ne 0$ . By Lemma 2.1.1 (a), $a \ge 1$ and $b \ge 1$ , so both are positive. Since $ka = b > 0$ and $a > 0$ , we have $k > 0$ (if $k \le 0$ , then $ka \le 0$ ); likewise $l > 0$ . By Proposition 2.1.2 (b), $k, l \in \mathbb{Z}_{>0} = \{ n \in \mathbb{N} : n \ge 1 \}$ , so $k \ge 1$ and $l \ge 1$ . Now $a = lb = lka$ , and $a \ne 0$ , so $kl = 1$ . If $k > 1$ , then multiplying by $l > 0$ gives $kl > l \ge 1$ , contradicting $kl = 1$ . So $k \le 1$ , hence $k = 1$ , and $b = a$ .

Not antisymmetric on $\mathbb{Z}$ . $-2 = (-1) \cdot 2$ and $2 = (-1) \cdot (-2)$ , so $2 \mid -2$ and $-2 \mid 2$ , but $2 \ne -2$ .

The failure on $\mathbb{Z}$ is a non-example by minimal change: enlarging the set from $\mathbb{N}$ to $\mathbb{Z}$ keeps reflexivity and transitivity, and antisymmetry fails exactly because an integer and its negative divide each other. Two facts about $(\mathbb{N}, \mid)$ will matter in Section 2.6: every $a \in \mathbb{N}$ divides $0$ , since $0 = 0 \cdot a$ , and $1$ divides every $a$ , since $a = a \cdot 1$ . In the divisibility relation, $0$ sits above everything and $1$ below everything.

2.4.3. A table of examples

Here are eight relations checked against the four properties. Each “no” comes with its witness, which is how a failure is proved; each “yes” is a one-line argument given after the table.

Example (Eight relations, four properties)

Decide which of the four properties each relation has: $=$ , $\le$ and $<$ on $\mathbb{R}$ ; $\subseteq$ on $\mathcal{P}\left( X \right)$ for a set $X$ with at least one element; $\mid$ on $\mathbb{N}$ and on $\mathbb{Z}$ ; “ $x - y \in \mathbb{Z}$ ” on $\mathbb{R}$ ; and the empty relation $\emptyset$ on a set $X$ with at least one element.

Solution.

Relation	reflexive	symmetric	antisymmetric	transitive
$=$ on $\mathbb{R}$	yes	yes	yes	yes
$\le$ on $\mathbb{R}$	yes	no: $0, 1$	yes	yes
$<$ on $\mathbb{R}$	no: $0$	no: $0, 1$	yes	yes
$\subseteq$ on $\mathcal{P}\left( X \right)$	yes	no: $\emptyset, X$	yes	yes
$\mid$ on $\mathbb{N}$	yes	no: $1, 2$	yes	yes
$\mid$ on $\mathbb{Z}$	yes	no: $1, 2$	no: $2, -2$	yes
$x - y \in \mathbb{Z}$ on $\mathbb{R}$	yes	yes	no: $0, 1$	yes
$\emptyset$ on $X$	no: any $x$	yes	yes	yes

The witnesses. $0 \le 1$ and not $1 \le 0$ ; $0 < 1$ and not $1 < 0$ ; not $0 < 0$ . $\emptyset \subseteq X$ , since the empty set is a subset of every set (Section 1.1, after Proposition 1.1.3), and $X \not\subseteq \emptyset$ , since $X$ has an element and $\emptyset$ has none. $1 \mid 2$ , and $2 \nmid 1$ : $1 = 2k$ would give $0 < k < 1$ , and no integer lies there (Proposition 2.1.2 (c)). The pair $2, -2$ is from Proposition 2.4.1. For $x - y \in \mathbb{Z}$ : $0 - 1 = -1$ and $1 - 0 = 1$ are integers, and $0 \ne 1$ . For $\emptyset$ : no $x$ has $(x, x) \in \emptyset$ .

The “yes” entries. Equality is reflexive by $\mathrm{{=}I}$ (Logic and Proof, Definition 5.7.1), symmetric and transitive by Logic and Proof, Proposition 5.7.1, and antisymmetric because its conclusion $x = y$ is one of its hypotheses. For $\le$ and $<$ , antisymmetry and transitivity are order facts about $\mathbb{R}$ , and $\le$ is reflexive because $x = x$ gives $x \le x$ ; for $<$ , antisymmetry holds vacuously, since $x < y$ and $y < x$ never hold together. For $\subseteq$ , reflexivity is immediate from Definition 1.1.2, transitivity is Proposition 1.1.2, and antisymmetry is Proposition 1.1.1. For $\mid$ , see Proposition 2.4.1. For $x - y \in \mathbb{Z}$ : $x - x = 0 \in \mathbb{Z}$ ; $y - x = -(x - y)$ ; and $x - z = (x - y) + (y - z)$ ; these are integers by Proposition 2.1.2 (a). The empty relation is symmetric, antisymmetric and transitive vacuously: each property is an implication whose hypothesis requires a pair in $\emptyset$ .

Three degenerate cases are worth a sentence each, because each shows a property holding for a reason other than the one we expect.

The empty relation on a non-empty $X$ has every property except reflexivity, all vacuously. It is the standard witness that the three implication properties do not imply reflexivity.
The full relation $X \times X$ relates everything to everything. It is reflexive, symmetric and transitive; it is antisymmetric only if $X$ has at most one element.
If $X = \emptyset$ , then $\mathcal{P}\left( X \right) = \{\emptyset\}$ , and $\subseteq$ on it is $\{(\emptyset, \emptyset)\}$ : with only one element, it is symmetric. The non-emptiness of $X$ in the table is what the witness $\emptyset, X$ needs.

Quick check. On the set $\{2, 3, 4, \dots\}$ of integers $\ge 2$ , let $x \mathrel{C} y$ mean “ $x$ and $y$ have a common prime factor”, that is, some prime $p$ divides both. Which of the four properties does $C$ have?

Solution. Reflexive: every integer $x \ge 2$ has a prime factor $p$ (Theorem 2.2.5), and $p$ divides $x$ and $x$ . Symmetric: the condition “ $p \mid x$ and $p \mid y$ ” does not depend on the order of $x$ and $y$ . Not antisymmetric: $2 \mathrel{C} 4$ and $4 \mathrel{C} 2$ (both divisible by $2$ ), and $2 \ne 4$ . Not transitive: $2 \mathrel{C} 6$ (common factor $2$ ) and $6 \mathrel{C} 3$ (common factor $3$ ), but $2$ and $3$ have no common prime factor, since a prime dividing $2$ is a positive divisor of $2$ that is at least $2$ , hence is $2$ (the example after Definition 2.2.2), and $2 \nmid 3$ : $3 = 2k$ would give $1 < k < 2$ , and no integer lies there (Proposition 2.1.2 (c)). Sharing a factor with a middle element does not pass along, because the shared factor may change.

Warning. A false theorem: “symmetric and transitive imply reflexive.” The “proof”: let $x \in X$ , and take $y$ with $x \mathrel{R} y$ ; by symmetry $y \mathrel{R} x$ , and by transitivity $x \mathrel{R} x$ . The conclusion is false: the empty relation on $\{1\}$ is symmetric and transitive (vacuously) and not reflexive, with witness $1$ . The illegal step, “take $y$ with $x \mathrel{R} y$ ”, is an $\mathrm{\exists E}$ (Logic and Proof, Definition 5.6.1) on $\exists y \in X \ x \mathrel{R} y$ , which was never derived and need not be true: (N9) of Logic and Proof, Example (What is not allowed) (Exercise C2 gives the correct version).

Remark. “Antisymmetric” is not “not symmetric”. Equality is both symmetric and antisymmetric. And $\{ (1, 2), (2, 1), (2, 3) \}$ on $\{1, 2, 3\}$ is neither: it is not symmetric, since $2 \mathrel{R} 3$ and not $3 \mathrel{R} 2$ ; and it is not antisymmetric, since $1 \mathrel{R} 2$ , $2 \mathrel{R} 1$ and $1 \ne 2$ .

Two combinations of the properties organize the rest of the chapter. A relation that is reflexive, symmetric and transitive behaves like equality; Section 2.5 calls it an equivalence relation and shows that it cuts $X$ into classes. A relation that is reflexive, antisymmetric and transitive behaves like $\le$ ; Section 2.6 calls it a partial order; inclusion on $\mathcal{P}\left( X \right)$ and divisibility on $\mathbb{N}$ are examples that are not comparisons of sizes.

2.4.4. Exercises

A. Check your understanding

Exercise (A1)

(a) State in symbols what it means for a relation $R$ on $X$ to be antisymmetric, and write its negation in symbols.
(b) True or false, with a witness: every antisymmetric relation fails to be symmetric.
(c) Which of the four properties does the relation “ $\left| x - y \right| \le 1$ ” have on $\mathbb{R}$ ?
(d) Let $X = \{p, q\}$ with $p \ne q$ . How many relations on $X$ are reflexive on $X$ ?

Solution.

(a) $\forall x \in X \ \forall y \in X \ ((x \mathrel{R} y \wedge y \mathrel{R} x) \to x = y)$ . Its negation, by Logic and Proof, Proposition 6.2.3 and Logic and Proof, Proposition 6.2.2: $\exists x \in X \ \exists y \in X \ ((x \mathrel{R} y \wedge y \mathrel{R} x) \wedge x \ne y)$ .
(b) False. Equality on any set is antisymmetric and symmetric. So is the empty relation (vacuously).
(c) Reflexive: $\left| x - x \right| = 0 \le 1$ . Symmetric: $\left| y - x \right| = \left| x - y \right|$ . Not antisymmetric: $\left| 0 - 1 \right| \le 1$ both ways and $0 \ne 1$ . Not transitive: $\left| 0 - 1 \right| \le 1$ and $\left| 1 - 2 \right| \le 1$ , but $\left| 0 - 2 \right| = 2 > 1$ . “Close to” does not pass along a chain, because small differences add up.
(d) Four. A reflexive relation must contain $(p, p)$ and $(q, q)$ . The other two pairs of $X \times X$ , $(p, q)$ and $(q, p)$ , may each be in or out, independently, which gives $2 \cdot 2 = 4$ relations: $\{(p, p), (q, q)\}$ together with one of $\emptyset$ , $\{(p, q)\}$ , $\{(q, p)\}$ , $\{(p, q), (q, p)\}$ .

B. Practice

Exercise (B1: Five relations)

For each relation, determine which of the four properties it has. Justify your answer, with a witness for each failure.

(a) On $\mathbb{N} \times \mathbb{N}$ : $(a, b) \mathrel{E} (c, d)$ if and only if $a + d = b + c$ .
(b) On $\mathbb{R}$ : $x \mathrel{S} y$ if and only if $x^2 = y^2$ .
(c) On the set $\mathbb{R}^{\mathbb{R}}$ of functions $\mathbb{R} \to \mathbb{R}$ : $f \mathrel{L} g$ if and only if $f(x) \le g(x)$ for every $x \in \mathbb{R}$ .
(d) On $\mathbb{R}$ : $x \mathrel{P} y$ if and only if $xy > 0$ .
(e) On $\mathbb{Z}$ : $x \mathrel{N} y$ if and only if $y = x + 1$ .

Solution.

(a) Reflexive: $a + b = b + a$ . Symmetric: $a + d = b + c$ gives $c + b = d + a$ . Transitive: from $a + d = b + c$ and $c + f = d + e$ , adding gives $a + d + c + f = b + c + d + e$ , and canceling $c + d$ gives $a + f = b + e$ . Not antisymmetric: $(0, 0) \mathrel{E} (1, 1)$ both ways, and $(0, 0) \ne (1, 1)$ . (The pairs $(a, b)$ and $(c, d)$ are related exactly when $a - b = c - d$ ; Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Chapter 2 builds $\mathbb{Z}$ from the classes of this relation.)
(b) Reflexive, symmetric and transitive, because “ $x^2 = y^2$ ” is equality of the values $x^2$ and $y^2$ , and equality has those three properties. Not antisymmetric: $1^2 = (-1)^2$ and $1 \ne -1$ .
(c) Reflexive: $f(x) \le f(x)$ . Transitive: $f(x) \le g(x) \le h(x)$ at each $x$ . Antisymmetric: if $f \mathrel{L} g$ and $g \mathrel{L} f$ , then $f(x) = g(x)$ for every $x$ , and $f = g$ by Proposition 1.4.1 (same domain and codomain). Not symmetric: the constant functions $0$ and $1$ satisfy $0 \mathrel{L} 1$ and not $1 \mathrel{L} 0$ . In addition, two functions need not be comparable: for $f(x) = x$ and the constant $0$ , neither $f \mathrel{L} 0$ (fails at $x = 1$ ) nor $0 \mathrel{L} f$ (fails at $x = -1$ ).
(d) Symmetric: $xy = yx$ . Transitive: if $xy > 0$ and $yz > 0$ , then $(xy)(yz) = xz \, y^2 > 0$ , and $y^2 > 0$ (since $y \ne 0$ , as $xy \ne 0$ ), so $xz > 0$ . Not reflexive: $0 \cdot 0 = 0$ , so $0$ is not related to itself. Not antisymmetric: $1 \mathrel{P} 2$ and $2 \mathrel{P} 1$ (both products are $2 > 0$ ), and $1 \ne 2$ . This is the planted case: $P$ is symmetric and transitive, yet not reflexive on $\mathbb{R}$ , exactly at the one element related to nothing. On $\mathbb{R} \setminus \{0\}$ it is reflexive. Compare the warning before these exercises.
(e) Not reflexive: $0 \ne 0 + 1$ . Not symmetric: $0 \mathrel{N} 1$ and not $1 \mathrel{N} 0$ ( $0 \ne 2$ ). Not transitive: $0 \mathrel{N} 1$ and $1 \mathrel{N} 2$ , and not $0 \mathrel{N} 2$ . Antisymmetric, vacuously: $x \mathrel{N} y$ and $y \mathrel{N} x$ would give $y = x + 1$ and $x = y + 1 = x + 2$ , which is impossible, so no pair satisfies the hypothesis.

Exercise (B2: Example generation)

Give an example of a relation on $\{1, 2, 3\}$ that is reflexive and transitive, but neither symmetric nor antisymmetric. Check each property. Then list the properties that every correct answer must have.

Solution. One answer: $R = \{ (1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (1, 3), (2, 3) \} .$ Reflexive: the three loops are in $R$ . Not symmetric: $1 \mathrel{R} 3$ and not $3 \mathrel{R} 1$ . Not antisymmetric: $1 \mathrel{R} 2$ , $2 \mathrel{R} 1$ and $1 \ne 2$ . Transitive: we check every two-step path $x \mathrel{R} y \mathrel{R} z$ with $x \ne y$ and $y \ne z$ (a step along a loop changes nothing). They are $1 \to 2 \to 1$ , $1 \to 2 \to 3$ , $2 \to 1 \to 2$ and $2 \to 1 \to 3$ , and their shortcuts $(1, 1)$ , $(1, 3)$ , $(2, 2)$ , $(2, 3)$ are all in $R$ . Element $3$ has no arrow out except its loop, so no other path exists.

Every correct answer must: - contain the three pairs $(1, 1)$ , $(2, 2)$ , $(3, 3)$ ; - contain two different elements related both ways (to fail antisymmetry); - contain a pair related one way only (to fail symmetry); - contain the shortcut of every two-arrow path.

The second and fourth items together force more: if $a \mathrel{R} b$ , $b \mathrel{R} a$ and $b \mathrel{R} c$ , transitivity puts $a \mathrel{R} c$ in. First, there is only one two-way pair: two of them, say $\{a, b\}$ and $\{b, c\}$ , give $a \mathrel{R} c$ and $c \mathrel{R} a$ by transitivity, so $R$ is the full relation, which is symmetric. Call the two-way pair $\{a, b\}$ and the third element $c$ . Every arrow between $a$ and $b$ is two-way, so a one-way arrow must have $c$ at one end, and one such arrow is never enough: transitivity relates $c$ to the other element of the pair too, in the same direction. For example, $\{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (3, 1)\}$ fails transitivity, since $3 \mathrel{R} 1 \mathrel{R} 2$ and not $3 \mathrel{R} 2$ . If $c \mathrel{R} a$ , then $c \mathrel{R} a \mathrel{R} b$ gives $c \mathrel{R} b$ , and neither $a \mathrel{R} c$ nor $b \mathrel{R} c$ can hold, since that would make a second two-way pair; so both arrows point out of $c$ . Likewise $a \mathrel{R} c$ forces $b \mathrel{R} c$ , and both arrows point into $c$ . Conversely, each of these six relations is a correct answer. Those with $c$ above the pair are the answer above with the elements renamed. Those with $c$ below are obtained from them by reversing every arrow, which keeps the loops, the two-way pair and the one-way arrows, and keeps transitivity: a path $z \to y \to x$ of the reversed relation is the reverse of a path $x \to y \to z$ , and the reverse of its shortcut $(x, z)$ is $(z, x)$ . So $\{1, 2, 3\}$ carries exactly six correct answers: one for each choice of the two-way pair (three choices) and of whether the third element lies above the pair or below it (two choices); the answer above has $3$ above the pair $\{1, 2\}$ .

Exercise (B3: Intersections and unions)

Let $R$ and $S$ be transitive relations on a set $X$ . Prove that $R \cap S$ is transitive. Show by an example on $\{1, 2, 3\}$ that $R \cup S$ need not be transitive.

Solution. Let $x, y, z \in X$ with $(x, y) \in R \cap S$ and $(y, z) \in R \cap S$ . Then $(x, y), (y, z) \in R$ , so $(x, z) \in R$ because $R$ is transitive; likewise $(x, z) \in S$ . Hence $(x, z) \in R \cap S$ .

For the union, let $R = \{(1, 2)\}$ and $S = \{(2, 3)\}$ . Each is transitive, vacuously: in $R$ a two-step path would need a pair starting at $2$ , and there is none; in $S$ one would need a pair ending at $2$ . But $R \cup S = \{ (1, 2), (2, 3) \}$ contains $(1, 2)$ and $(2, 3)$ and not $(1, 3)$ , so it is not transitive. The intersection keeps both relations’ shortcuts; the union creates paths that neither relation contains, so neither supplies their shortcuts.

C. Going deeper

Exercise (C1: Properties as equations between sets)

Let $R$ be a relation on $X$ , let $R^{-1}$ be its inverse relation (Definition 1.3.3), and let $\Delta_X \mathrel{:=} \{ (x, x) : x \in X \}$ be the diagonal.

(a) Prove that $R$ is symmetric if and only if $R = R^{-1}$ , and that $R$ is antisymmetric if and only if $R \cap R^{-1} \subseteq \Delta_X$ .
(b) Deduce that a relation that is both symmetric and antisymmetric satisfies $R \subseteq \Delta_X$ . Is every subset of $\Delta_X$ both symmetric and antisymmetric?

Solution. Recall that $(x, y) \in R^{-1}$ if and only if $(y, x) \in R$ .

(a) Symmetric. $(\Rightarrow)$ Let $R$ be symmetric. If $(x, y) \in R$ , then $(y, x) \in R$ , that is, $(x, y) \in R^{-1}$ ; so $R \subseteq R^{-1}$ . If $(x, y) \in R^{-1}$ , then $(y, x) \in R$ , so $(x, y) \in R$ by symmetry; so $R^{-1} \subseteq R$ . By Proposition 1.1.1, $R = R^{-1}$ . $(\Leftarrow)$ If $R = R^{-1}$ and $x \mathrel{R} y$ , then $(x, y) \in R^{-1}$ , so $(y, x) \in R$ .
Antisymmetric. A pair $(x, y)$ lies in $R \cap R^{-1}$ exactly when $x \mathrel{R} y$ and $y \mathrel{R} x$ , and it lies in $\Delta_X$ exactly when $x = y$ (by the characteristic property of pairs, Definition 1.3.1). So “ $R \cap R^{-1} \subseteq \Delta_X$ ” says: for all $x, y \in X$ , if $x \mathrel{R} y$ and $y \mathrel{R} x$ , then $x = y$ . That is antisymmetry, word for word.
(b) If $R$ is symmetric and antisymmetric, then by (a), $R = R \cap R = R \cap R^{-1} \subseteq \Delta_X$ . Conversely, every $R \subseteq \Delta_X$ is symmetric (each of its pairs is $(x, x)$ , which is its own reverse) and antisymmetric ( $x \mathrel{R} y$ already forces $x = y$ ). So the relations with both properties are exactly the subsets of the diagonal; equality, $\Delta_X$ itself, is the largest of them, and $\emptyset$ the smallest.

Exercise (C2: What symmetry and transitivity do give)

Let $R$ be a symmetric and transitive relation on $X$ , and let $D \mathrel{:=} \{ x \in X : \exists y \in X \ \ x \mathrel{R} y \}$ be its domain. Prove that $R \subseteq D \times D$ and that $R$ , as a relation on $D$ , is reflexive on $D$ , symmetric and transitive.

Solution. $R \subseteq D \times D$ . Let $(x, y) \in R$ . Then $x \in D$ , with witness $y$ . By symmetry $y \mathrel{R} x$ , so $y \in D$ , with witness $x$ . Hence $(x, y) \in D \times D$ .

Reflexive on $D$ . Let $x \in D$ . By the definition of $D$ there is $y \in X$ with $x \mathrel{R} y$ ; fix one (an $\mathrm{\exists E}$ , legitimate now, because $x \in D$ is exactly the statement $\exists y \in X \ x \mathrel{R} y$ ). By symmetry $y \mathrel{R} x$ , and by transitivity, from $x \mathrel{R} y$ and $y \mathrel{R} x$ , $x \mathrel{R} x$ .

Symmetric and transitive on $D$ . These are implications about related elements, and every related pair lies in $D \times D$ ; so they hold on $D$ because they hold on $X$ .

This is the correct version of the false theorem in the warning: its argument proves reflexivity exactly on the set of elements for which “take $y$ with $x \mathrel{R} y$ ” is available. Elements outside $D$ are related to nothing, and there reflexivity fails. In the language of Section 2.5, $R$ is an equivalence relation on $D$ .

Marking scheme. (10 points) - 2: shows $R \subseteq D \times D$ , using symmetry to put the second coordinate in $D$ . - 4: for reflexivity on $D$ , obtains $y$ with $x \mathrel{R} y$ from $x \in D$ , and says why this step is now legitimate. - 2: applies symmetry and then transitivity, in that order, to get $x \mathrel{R} x$ . - 2: explains why symmetry and transitivity restrict to $D$ . Fatal errors (0 for the step): taking $y$ with $x \mathrel{R} y$ for an arbitrary $x \in X$ rather than $x \in D$ (the error of the warning); applying transitivity to $x \mathrel{R} y$ and $x \mathrel{R} y$ .