Exercise 1.1 · Q10: Relations with exactly the properties asked for

Basics you need

Part (i): symmetric, not reflexive, not transitive

1. The example

   $$R_1 = \{(1,2),\ (2,1)\}.$$
   A single two-way arrow is the simplest way to get symmetry. Leaving out every loop kills reflexivity, and, as Step 3 shows, the missing loops also kill transitivity. This is the relation of Exercise 1.1 Q6.

2. Symmetric: yes

   The pairs in $R_1$ are $(1,2)$ and $(2,1)$⁠. The reverse of $(1,2)$ is $(2,1)\in R_1$⁠; the reverse of $(2,1)$ is $(1,2)\in R_1$⁠. Every pair passes, so $R_1$ is symmetric.

   Symmetry is a condition on the pairs that are in $R_1$⁠, and there are only two, so two checks complete the proof.

3. Not reflexive, not transitive

   Not reflexive: $(1,1)\notin R_1$⁠.

   Not transitive: $(1,2)\in R_1$ and $(2,1)\in R_1$ form the chain $1\to2\to1$⁠, so transitivity would need $(1,1)\in R_1$⁠. It is not there, so $R_1$ is neither reflexive nor transitive.

   The failing chain uses $a = 1$⁠, $b = 2$⁠, $c = 1$⁠. The definition allows $c = a$⁠, and that is where the relation breaks. A familiar relation with the same pattern is "$L_1$ is perpendicular to $L_2$" on lines (Example 3).
   One failing check disproves a property (Basic 3).

Part (ii): transitive, not reflexive, not symmetric

1. The example

   $$R_2 = \{(1,2)\}.$$
   A single one-way arrow already fails symmetry and reflexivity. The question is whether it is transitive, and Step 2 shows it is, for a perhaps unexpected reason.

2. Transitive: yes (there are no chains)

   A chain needs $(a,b)\in R_2$ and $(b,c)\in R_2$⁠. The only pair is $(1,2)$⁠, so $b$ would have to be 2, and we would need a pair in $R_2$ starting with 2. There is none. So there are no chains, nothing can fail, and $R_2$ is transitive.

   The transitive condition only says something when a chain exists. With no chains, the statement "every chain closes" has no cases to check and is true (Basic 4). This is a valid proof, not a loophole.
   "For all chains, $(a,c)\in R$" is vacuously true when there are no chains.

3. Not reflexive, not symmetric

   Not reflexive: $(1,1)\notin R_2$⁠.

   Not symmetric: $(1,2)\in R_2$ but $(2,1)\notin R_2$⁠. So $R_2$ is neither reflexive nor symmetric.

   A familiar relation of the same kind is "$a < b$" on $\R$⁠: it is transitive ($a < b$ and $b < c$ give $a < c$⁠), not reflexive ($1 < 1$ is false) and not symmetric ($1 < 2$ but not $2 < 1$⁠).

Part (iii): reflexive, symmetric, not transitive

1. The example

   $$R_3 = \{(1,1),(2,2),(3,3),\ (1,2),(2,1),\ (2,3),(3,2)\}.$$
   Think of "is a neighbour of, or equal to": 1 and 2 are neighbours, 2 and 3 are neighbours, but 1 and 3 are not. All loops give reflexivity, two-way arrows give symmetry, and the gap between 1 and 3 breaks transitivity. (The relation "$|x - y| \le 1$" on $\Z$ works the same way.)

2. Reflexive and symmetric: yes

   Reflexive: $(1,1)$⁠, $(2,2)$ and $(3,3)$ are all in $R_3$⁠.

   Symmetric: check every pair. Each loop $(a,a)$ is its own reverse. The other four pairs come in reversed couples: $(1,2)\leftrightarrow(2,1)$ and $(2,3)\leftrightarrow(3,2)$⁠, all in $R_3$⁠. So $R_3$ is reflexive and symmetric.

   Every one of the 7 pairs has been accounted for: 3 loops and 2 reversed couples.

3. Not transitive

   $(1,2)\in R_3$ and $(2,3)\in R_3$⁠, so transitivity would need $(1,3)\in R_3$⁠. But $(1,3)\notin R_3$⁠. So $R_3$ is not transitive.

   (The reversed chain $(3,2),(2,1)$ fails too, since $(3,1)\notin R_3$⁠; one failure is enough.)

   You cannot make this example any smaller: on a set with only two elements, every reflexive and symmetric relation is transitive (a check of all 16 relations on $\{1,2\}$ confirms it). Three elements are needed so that 1 and 3 can both be linked to 2 without being linked to each other. In fact, on $\{1,2,3\}$ there are exactly 3 relations with this combination of properties; the other two use 1 or 3 as the middle element instead of 2.

Part (iv): reflexive, transitive, not symmetric

1. The example

   $$R_4 = \{(1,1),(2,2),(3,3),\ (1,2)\}.$$
   Start from the loops (reflexive) and add one one-way arrow (breaks symmetry). One arrow cannot create a new chain that needs another pair, so transitivity survives.

2. Reflexive and transitive: yes

   Reflexive: $(1,1),(2,2),(3,3)\in R_4$⁠.

   Transitive: list every chain $(a,b),(b,c)$ in $R_4$ and the pair $(a,c)$ it needs:

   $(a,b)$	$(b,c)$	Needs $(a,c)$	In $R_4$⁠?
   $(1,1)$	$(1,1)$	$(1,1)$	yes
   $(1,1)$	$(1,2)$	$(1,2)$	yes
   $(1,2)$	$(2,2)$	$(1,2)$	yes
   $(2,2)$	$(2,2)$	$(2,2)$	yes
   $(3,3)$	$(3,3)$	$(3,3)$	yes

   These are all 5 chains, and each closes, so $R_4$ is reflexive and transitive.

   To find every chain, take each pair $(a,b)$ and look for all pairs that start with $b$⁠. For $(1,2)$⁠, the only pair starting with 2 is $(2,2)$⁠. For $(1,1)$⁠, the pairs starting with 1 are $(1,1)$ and $(1,2)$⁠. And so on. A chain through a loop always closes, because it just repeats a pair already in the list.

3. Not symmetric

   $(1,2)\in R_4$ but $(2,1)\notin R_4$⁠. So $R_4$ is not symmetric.

   A familiar relation of this kind is "$a \le b$" on $\R$ (Exercise 1.1 Q4). In fact $R_4$ is the relation $\le$ restricted to the pairs with entries in $\{1,2\}$⁠, plus the loop $(3,3)$⁠.

Part (v): symmetric, transitive, not reflexive

1. The example

   $$R_5 = \{(1,1),(1,2),(2,1),(2,2)\} = \{1,2\}\times\{1,2\}.$$
   Take the relation of part (i) and add the two loops that transitivity demanded. That repairs transitivity. Reflexivity still fails, because one element, 3, is left out entirely.

2. Symmetric and transitive: yes

   Symmetric: $(1,1)$ and $(2,2)$ are their own reverses, and $(1,2)\leftrightarrow(2,1)$ are both in $R_5$⁠.

   Transitive: every pair in $R_5$ has both entries in $\{1,2\}$⁠. In any chain $(a,b),(b,c)$⁠, therefore, $a$ and $c$ are both in $\{1,2\}$⁠, so $(a,c)\in\{1,2\}\times\{1,2\} = R_5$⁠. (There are 8 chains in all, since each of the 4 pairs $(a,b)$ can be followed by 2 pairs starting with $b$⁠, and every one closes.) So $R_5$ is symmetric and transitive.

   Writing $R_5$ as $\{1,2\}\times\{1,2\}$ means "every element of $\{1,2\}$ is related to every element of $\{1,2\}$". A chain can never leave $\{1,2\}$⁠, and every pair inside $\{1,2\}$ is already present, so no chain can fail.

3. Not reflexive

   $3\in A$ but $(3,3)\notin R_5$⁠. So $R_5$ is not reflexive.

   A tempting "proof" says symmetric plus transitive gives reflexive: from $(a,b)$ get $(b,a)$ by symmetry, then $(a,a)$ by transitivity. The flaw is that it needs some $b$ with $(a,b)\in R$ to start with. The element 3 is related to nothing, so the argument never gets going for 3. That is exactly why reflexivity has to be listed separately in the definition of an equivalence relation.
   Reflexive means $(a,a)\in R$ for every $a\in A$⁠, including elements that appear in no other pair (Definition 3(i)).

Every fact used, and where it comes from