Exercise 1.1 · Q1: Reflexive, symmetric, transitive: nine relations

Basics you need

Part (i): $3x - y = 0$ on $\{1, \dots, 14\}$

1. (i) Rewrite the rule and list $R$

   $3x - y = 0$ means $y = 3x$⁠: the second number is three times the first. Run through $x = 1, 2, 3, \dots$ and keep the pair only if $3x$ is also in $A = \{1,\dots,14\}$⁠:

   $x=1 \to y=3$⁠, $\ x=2\to y=6$⁠, $\ x=3\to y=9$⁠, $\ x=4\to y=12$⁠, but $x=5 \to y=15 \notin A$⁠.

   Every larger $x$ gives a larger $y$⁠, also outside $A$⁠. So

   $$R = \{(1,3),\ (2,6),\ (3,9),\ (4,12)\}.$$
   An equation like $3x - y = 0$ is easier to use once it is solved for one letter. Because $A$ is finite and small, listing every pair is the most reliable way to answer all three questions: each test then becomes a search through four pairs.
   A relation in $A$ can only contain pairs with both entries in $A$ (Basic 1). That is why $(5,15)$ is excluded.

2. (i) Reflexive? No

   Reflexive needs $(a,a)\in R$ for every $a\in A$⁠. Test $a = 1$⁠: $3\cdot 1 - 1 = 2 \ne 0$⁠, so $(1,1)\notin R$⁠. Hence $R$ is not reflexive.

   In fact $(a,a)$ is never in $R$⁠: $3a - a = 2a$⁠, and $2a \ne 0$ because every element of $A$ is at least 1.

   One element that is not related to itself is enough to break "for every $a$". The general line $3a - a = 2a \ne 0$ shows the failure is not special to $a=1$⁠. You can also see it from the list: no pair in $R$ has equal entries.
   One counterexample disproves a "for all" statement (Basic 3).

3. (i) Symmetric? No

   Take $(1,3)\in R$ (since $3\cdot1 - 3 = 0$⁠). Its reverse $(3,1)$ would need $3\cdot 3 - 1 = 0$⁠, but $3\cdot 3 - 1 = 8 \ne 0$⁠. So $(1,3)\in R$ but $(3,1)\notin R$⁠, and $R$ is not symmetric.

   For symmetry to fail we need a pair that is in $R$ whose reverse is not. Taking the pair from the list guarantees the first half; the arithmetic $9 - 1 = 8$ settles the second. The reverse of "$y$ is three times $x$" would be "$x$ is three times $y$", and both can hold only if $x = 9x$⁠, that is $x = 0$⁠, which is not in $A$⁠.

4. (i) Transitive? No

   We need two linked pairs whose shortcut is missing. $(1,3)\in R$ and $(3,9)\in R$ (since $3\cdot 3 - 9 = 0$⁠). Transitivity would need $(1,9)\in R$⁠, but $3\cdot 1 - 9 = -6 \ne 0$⁠. So $R$ is not transitive.

   For a chain, the second pair must start where the first ends, here at 3. Scanning the list, $1\to3\to9$ is the only chain in $R$ (no pair starts at 6 or 12, and 9 leads nowhere because $27\notin A$⁠), and it fails. Going "times 3" twice gives "times 9", not "times 3".
   Transitivity: $(a_1,a_2),(a_2,a_3)\in R \Rightarrow (a_1,a_3)\in R$ (Basic 2). A counterexample is one chain with a missing shortcut.

Verdict (i): neither reflexive nor symmetric nor transitive.

Part (ii): $y = x + 5$ and $x < 4$ on $\N$

1. (ii) List $R$

   The condition $x < 4$ with $x\in\N = \{1,2,3,\dots\}$ leaves only $x = 1, 2, 3$⁠. For each, $y = x+5$⁠:

   $$R = \{(1,6),\ (2,7),\ (3,8)\}.$$

   So although $\N$ is infinite, $R$ has only three pairs. Every pair starts at 1, 2 or 3 and ends at 6, 7 or 8.

   The rule has two conditions joined by "and", so a pair must satisfy both. The condition $x < 4$ is what makes $R$ finite. Noting which numbers can appear first and which can appear second is the key to the transitivity test below.

2. (ii) Reflexive? No

   Test $a = 1$⁠: $(1,1)\in R$ would need $1 = 1+5 = 6$⁠, which is false. So $(1,1)\notin R$ and $R$ is not reflexive. (No $(a,a)$ is in $R$⁠: $a = a+5$ would give $0 = 5$⁠.)

   A single natural number not related to itself breaks "for every $a\in\N$".

3. (ii) Symmetric? No

   $(1,6)\in R$⁠, since $6 = 1+5$ and $1 < 4$⁠. The reverse $(6,1)$ would need $1 = 6+5 = 11$ and $6 < 4$⁠. Both conditions are false. So $(6,1)\notin R$ and $R$ is not symmetric.

   For an "and" condition, one false part is enough to exclude a pair; here both parts fail, which makes the conclusion doubly clear.

4. (ii) Transitive? Yes, because no chain exists

   Transitivity says: if $(x,y)\in R$ and $(y,z)\in R$⁠, then $(x,z)\in R$⁠. To have both pairs, the middle number $y$ must be

   • the second entry of a pair of $R$⁠, so $y\in\{6,7,8\}$⁠, and
   • the first entry of a pair of $R$⁠, so $y\in\{1,2,3\}$⁠.

   These sets have no element in common, so no such $y$ exists. The "if" part of transitivity is never true, so it is never violated, and $R$ is transitive.

   Think about what a counterexample to transitivity would have to be: a chain $(x,y),(y,z)$ in $R$ with $(x,z)$ missing. We have just shown there is no chain at all, so there can be no counterexample. A "for all" statement with no counterexample is true. This is the "vacuous" truth of Basic 4, and it is how the textbook's answer, "transitive", is reached. It is not a loophole: the definition of transitivity asks only that chains close up, and there are none.
   An "if … then" statement whose "if" part never happens is true (Basic 4).

Verdict (ii): neither reflexive nor symmetric, but transitive.

Part (iii): $y$ divisible by $x$ on $\{1, \dots, 6\}$

1. (iii) Rewrite the rule and list $R$

   "$y$ is divisible by $x$" means $y = kx$ for some integer $k$ (Basic 5). Going through $x = 1,\dots,6$⁠, the multiples of $x$ inside $A$ are:

   $$\begin{aligned} x=1&:\ y = 1,2,3,4,5,6\\ x=2&:\ y = 2,4,6\\ x=3&:\ y=3,6\\ x=4&:\ y = 4\\ x=5&:\ y = 5\\ x=6&:\ y = 6 \end{aligned}$$

   So $R$ has $6+3+2+1+1+1 = 14$ pairs:

   $$\begin{aligned} R = \{&(1,1),(1,2),(1,3),(1,4),(1,5),\\ &(1,6),(2,2),(2,4),(2,6),(3,3),\\ &(3,6),(4,4),(5,5),(6,6)\}.\end{aligned}$$
   Divisibility is a statement we can only calculate with once it is turned into an equation, $y = kx$⁠. The table of pairs also gives a picture: reflexive means the whole diagonal is in $R$⁠, and symmetric means the pattern is a mirror image of itself across the diagonal.

2. (iii) Reflexive? Yes

   Take any $x\in A$⁠. Then $x = 1\cdot x$⁠, and $1$ is an integer, so $x$ is divisible by $x$⁠, that is $(x,x)\in R$⁠. Since $x$ was arbitrary, $R$ is reflexive.

   Reflexivity is a "for every $x$" claim, so we argue with a letter. The equation $x = 1\cdot x$ holds whatever $x$ is, which is what makes the proof cover all six elements at once. (On a set of six elements you could also check the six diagonal pairs one by one; the grid shows all six are filled.)
   $y = kx$ with $k$ an integer (Basic 5); here $y = x$ and $k = 1$⁠.

3. (iii) Symmetric? No

   $(2,4)\in R$ because $4 = 2\cdot 2$⁠. The reverse $(4,2)$ would need 2 to be divisible by 4, that is $2 = 4k$ for an integer $k$⁠. But $2 = 4\cdot\tfrac12$⁠, and $\tfrac12$ is not an integer (equivalently, $2 = 4\cdot 0 + 2$ leaves remainder 2). So $(4,2)\notin R$ and $R$ is not symmetric.

   If $x$ divides $y$ and $x \ne y$⁠, then $x < y$ here (all numbers are positive), and a larger number cannot divide a smaller positive one. So every one of the 8 off-diagonal pairs in $R$ is a counterexample; we only need one.

4. (iii) Transitive? Yes

   Suppose $(x,y)\in R$ and $(y,z)\in R$⁠. Then there are integers $k$ and $m$ with

   $$y = kx \qquad\text{and}\qquad z = my.$$

   Substitute the first into the second:

   $$z = m(kx) = (mk)\,x.$$

   Since $m$ and $k$ are integers, $mk$ is an integer. So $z$ is divisible by $x$⁠, that is $(x,z)\in R$⁠. Hence $R$ is transitive.

   We need a statement about $x$ and $z$⁠, and the given facts both mention $y$⁠. Substituting $y = kx$ into $z = my$ removes $y$⁠. Use two different letters $k$ and $m$⁠: the two multipliers need not be equal (for example $2 = 2\cdot 1$ and $6 = 3\cdot 2$⁠, giving $6 = 6\cdot 1$⁠).
   The product of two integers is an integer (Basic 5).

Verdict (iii): reflexive and transitive, but not symmetric.

Part (iv): $x - y$ is an integer, on $\Z$

1. (iv) See that every pair is in $R$

   If $x$ and $y$ are integers, then $x - y$ is an integer, because the integers are closed under subtraction. So every pair of integers satisfies the rule, and

   $$R = \Z\times\Z,$$

   the universal relation on $\Z$⁠.

   The condition "$x-y$ is an integer" sounds like a restriction, but in the set $\Z$ it never excludes anything. Noticing this first makes the three tests short. (It would be a real restriction on $\R$⁠: there, $(1.5, 1)$ is not in the relation, since $0.5$ is not an integer.)
   Closure under subtraction (Basic 5). The universal relation is Definition 2 of Section 1.2: each element is related to every element, $R = A\times A$⁠.

2. (iv) Reflexive, symmetric, transitive: all yes

   Reflexive. For any $x\in\Z$⁠, $x - x = 0$⁠, an integer, so $(x,x)\in R$⁠.

   Symmetric. If $(x,y)\in R$⁠, then $y - x = -(x-y)$⁠, the negative of an integer, which is an integer. So $(y,x)\in R$⁠.

   Transitive. If $(x,y)\in R$ and $(y,z)\in R$⁠, then $x - z = (x-y) + (y-z)$⁠, a sum of two integers, which is an integer. So $(x,z)\in R$⁠.

   Hence $R$ is reflexive, symmetric and transitive, an equivalence relation.

   Each property here asks whether a certain pair is in $R$⁠, and by Step 1 every pair is. The three one-line arguments give the same conclusion directly from the rule, in the same style as Example 5 ($2 \mid (a-b)$⁠), so they would still work if you had not noticed that $R$ is universal. For instance $7 - (-3) = 10$ and $-3 - 7 = -10$ are both integers.
   A universal relation always has all three properties, because each property only asks for certain pairs to be present, and all pairs are.

Verdict (iv): reflexive, symmetric and transitive.

Part (v)(a): work at the same place

1. (v)(a) Make the rule precise

   The textbook intends that each person in the town works at exactly one place. Write $w(x)$ for the workplace of person $x$⁠. Then

   $$(x,y)\in R \iff w(x) = w(y).$$
   Turning "the same place" into an equation $w(x) = w(y)$ lets us use the properties of "=", which are exactly reflexive, symmetric and transitive. The assumption matters, and we return to it at the end of this part.

2. (v)(a) Reflexive, symmetric, transitive: all yes

   Reflexive. For any person $x$⁠, $w(x) = w(x)$⁠: everyone works at the same place as themselves. So $(x,x)\in R$⁠.

   Symmetric. If $(x,y)\in R$⁠, then $w(x) = w(y)$⁠, so $w(y) = w(x)$⁠, that is $(y,x)\in R$⁠.

   Transitive. If $(x,y)\in R$ and $(y,z)\in R$⁠, then $w(x) = w(y)$ and $w(y) = w(z)$⁠, so $w(x) = w(z)$⁠, that is $(x,z)\in R$⁠.

   Hence $R$ is reflexive, symmetric and transitive.

   The transitive step quietly uses "exactly one" workplace: $y$ has a single workplace $w(y)$⁠, so the place $x$ shares with $y$ and the place $y$ shares with $z$ are the same place. If people could have two jobs, this breaks. Say $x$ works only at a bank, $z$ only at a school, and $y$ at both: then $(x,y)$ and $(y,z)$ are in $R$ but $(x,z)$ is not. Likewise a person with no workplace (a small child, say) would not be related to themselves. The answer key's verdict assumes, as the question intends, that every person works at exactly one place.
   Equality is reflexive ($p = p$⁠), symmetric ($p = q \Rightarrow q = p$⁠) and transitive ($p = q,\ q = r \Rightarrow p = r$⁠). Any relation of the form "$f(x) = f(y)$" inherits all three. The textbook proves this in general in Example 21.

Verdict (v)(a): reflexive, symmetric and transitive (an equivalence relation).

Part (v)(b): live in the same locality

1. (v)(b) The same argument with localities

   Each person lives in exactly one locality. Write $\ell(x)$ for the locality of $x$⁠, so $(x,y)\in R \iff \ell(x) = \ell(y)$⁠.

   Reflexive: $\ell(x) = \ell(x)$⁠, so $(x,x)\in R$⁠. Symmetric: $\ell(x) = \ell(y) \Rightarrow \ell(y) = \ell(x)$⁠. Transitive: $\ell(x) = \ell(y)$ and $\ell(y) = \ell(z) \Rightarrow \ell(x) = \ell(z)$⁠.

   Hence $R$ is reflexive, symmetric and transitive.

   This has exactly the shape of part (v)(a): "$x$ and $y$ have the same $\ell$". The assumption "exactly one locality per person" is more natural here than in (a), since everyone lives somewhere and, at a particular time, in one place. The words "at a particular time" in the question fix the town's people, their workplaces and their localities, so the relations do not change while we test them. The equivalence classes are the localities themselves: each locality's residents form one class.
   "Same something" relations are equivalence relations (properties of equality, as in (v)(a)). Lesson: equivalence relations

Verdict (v)(b): reflexive, symmetric and transitive (an equivalence relation).

Part (v)(c): exactly 7 cm taller

1. (v)(c) Translate into heights

   Write $h(x)$ for the height of $x$ in cm. Then

   $$(x,y)\in R \iff h(x) = h(y) + 7.$$

   For the counterexamples, suppose the town has three people with heights 180 cm (Gopal), 173 cm (Ravi) and 166 cm (Arun). Then $(\text{Gopal},\text{Ravi})\in R$ since $180 = 173 + 7$⁠, and $(\text{Ravi},\text{Arun})\in R$ since $173 = 166 + 7$⁠.

   The rule is about heights, so we turn it into an equation between heights. To disprove symmetry and transitivity we need actual people standing in the relation, so we name some. The answer key takes it for granted that a town contains such people.

2. (v)(c) Reflexive? No

   $(x,x)\in R$ would need $h(x) = h(x) + 7$⁠, that is $0 = 7$ after subtracting $h(x)$⁠. This is impossible, so no person is exactly 7 cm taller than themselves, and $R$ is not reflexive.

   Any one person is a counterexample, for instance Gopal: $180 \ne 180 + 7 = 187$⁠.

3. (v)(c) Symmetric? No

   $(\text{Gopal},\text{Ravi})\in R$⁠. The reverse would need $h(\text{Ravi}) = h(\text{Gopal}) + 7$⁠, that is $173 = 187$⁠, which is false. So $R$ is not symmetric.

   In general, if $h(x) = h(y)+7$ then $x$ is the taller one, and $(y,x)\in R$ would need $y$ to be the taller one. Both together give $h(x) = h(x) + 14$⁠, that is $0 = 14$⁠. So whenever $R$ has a pair at all, its reverse is missing.

4. (v)(c) Transitive? No

   $(\text{Gopal},\text{Ravi})\in R$ and $(\text{Ravi},\text{Arun})\in R$⁠. Then Gopal is $180 - 166 = 14$ cm taller than Arun, not 7 cm, so $(\text{Gopal},\text{Arun})\notin R$⁠. Hence $R$ is not transitive.

   In general $h(x) = h(y) + 7$ and $h(y) = h(z) + 7$ give $h(x) = h(z) + 14$⁠, and $h(z) + 14 \ne h(z) + 7$⁠. Two steps of 7 cm make 14 cm, never 7. This has the same structure as Q3 ($b = a+1$⁠): a "fixed non-zero step" relation is not reflexive, is not symmetric once it contains a pair, and is not transitive as soon as one chain exists. (Part (ii), $y = x+5$ with $x<4$⁠, is also a fixed step, but there no chain exists, so it is transitive.)

Verdict (v)(c): neither reflexive nor symmetric nor transitive.

Part (v)(d): $x$ is wife of $y$

1. (v)(d) What the textbook assumes

   The answer key works with the traditional meaning of marriage that the textbook assumes: a wife is a woman, and the person she is wife of is her husband, a man. So whenever $(x,y)\in R$⁠, $x$ is a woman and $y$ is a man.

   We also assume the town has at least one married couple, say Asha is the wife of Ravi, so $(\text{Asha},\text{Ravi})\in R$⁠.

   Every verdict in this part depends on this reading, so we state it before using it. At the end of the part we note what changes if it is dropped.

2. (v)(d) Reflexive? No

   Nobody is their own wife: a marriage involves two different people. For example $(\text{Ravi},\text{Ravi})\notin R$⁠, and $(\text{Asha},\text{Asha})\notin R$⁠. So $R$ is not reflexive.

   One person not related to themselves is enough. (Men are never the first entry of any pair, so every man is a counterexample.)

3. (v)(d) Symmetric? No

   $(\text{Asha},\text{Ravi})\in R$⁠. The reverse $(\text{Ravi},\text{Asha})$ would say Ravi is the wife of Asha. But Ravi is a man (Asha's husband), and only women are wives. So $(\text{Ravi},\text{Asha})\notin R$ and $R$ is not symmetric.

   The relation is one-directional: the first entry is always the wife and the second always the husband. Swapping them puts the husband in the "wife" position.

4. (v)(d) Transitive? Yes, because no chain exists

   Suppose $(x,y)\in R$ and $(y,z)\in R$⁠. The first pair says $y$ is a man ($x$'s husband). The second says $y$ is a woman ($z$'s wife). No person is both, so no such chain exists. The "if" part of transitivity is never true, so transitivity cannot fail, and $R$ is transitive.

   This is the same situation as part (ii): the people who can appear second (husbands, men) and the people who can appear first (wives, women) form two groups with nobody in common, so no pair can be followed by another. A counterexample to transitivity would need such a chain, so there is none, and the "for all" statement holds vacuously (Basic 4). This is the reasoning behind the answer key's "Neither reflexive nor symmetric but transitive".
   
   Note how much rests on the assumption in Step 1. If the town included a marriage between two women, Lata and Uma, then $(\text{Lata},\text{Uma})\in R$ and $(\text{Uma},\text{Lata})\in R$ form a chain, and transitivity would demand $(\text{Lata},\text{Lata})\in R$⁠, which is false. Under that reading $R$ would not be transitive. The textbook's answer is correct for the reading it intends.
   An "if … then" statement whose "if" part can never be met is true (Basic 4).

Verdict (v)(d): neither reflexive nor symmetric, but transitive.

Part (v)(e): $x$ is father of $y$

1. (v)(e) Set up an example family

   Suppose the town has three generations of one family: Gopal is the father of Ravi, and Ravi is the father of Arun. So $(\text{Gopal},\text{Ravi})\in R$ and $(\text{Ravi},\text{Arun})\in R$⁠. We use two facts: a father is older than his child, and each person has exactly one father.

   As in (v)(c), counterexamples need real pairs in $R$⁠. The answer key assumes such a family lives in the town.

2. (v)(e) Reflexive? No

   No one is their own father (a father is older than his child, and no one is older than themselves). For example $(\text{Ravi},\text{Ravi})\notin R$⁠. So $R$ is not reflexive.

3. (v)(e) Symmetric? No

   $(\text{Gopal},\text{Ravi})\in R$⁠, so Gopal is older than Ravi. If $(\text{Ravi},\text{Gopal})$ were in $R$⁠, Ravi would be older than Gopal. Both cannot be true, so $(\text{Ravi},\text{Gopal})\notin R$⁠, and $R$ is not symmetric.

   The "older than" fact turns the question into a comparison of ages, and "$p$ older than $q$" and "$q$ older than $p$" contradict each other.

4. (v)(e) Transitive? No

   $(\text{Gopal},\text{Ravi})\in R$ and $(\text{Ravi},\text{Arun})\in R$⁠. Is Gopal the father of Arun? Arun has exactly one father, Ravi, and Gopal is a different person from Ravi. So Gopal is not Arun's father (he is his grandfather), and $(\text{Gopal},\text{Arun})\notin R$⁠. Hence $R$ is not transitive.

   Compare (v)(d): there no chain could exist, so transitivity held vacuously. Here chains do exist (grandfather, father, child), and they fail to close up. Whether chains exist at all is the first thing to ask in any transitivity test.

Verdict (v)(e): neither reflexive nor symmetric nor transitive.

Every fact used, and where it comes from