## Relations

The following is the list of problems for sections 11.0 and 11.1 of the Book of Proof (pages 178 and 182). There is a forum open at the end, so you can ask questions. It is a great way to interact with the instructor and with other students in your class, should you need some assistance with any question. Please, do not post solutions.

### Exercises for Section 11.0

1. Let $$A = \{ 0, 1, 2, 3, 4, 5\}.$$ Write out the relation $$R$$ that expresses $$>$$ on $$A.$$ Then illustrate it with a diagram.
2. Let $$A = \{ 1, 2, 3, 4, 5, 6 \}.$$ Write out the relation $$R$$ that expresses $$\vert$$ (divides) on $$A.$$ Then illustrate it with a diagram.
3. Let $$A = \{ 0, 1, 2, 3, 4, 5 \}.$$ Write out the relation $$R$$ that expresses $$\geq$$ on $$A.$$ Then illustrate it with a diagram.
4. Here is a diagram for a relation $$R$$ on a set $$A.$$ Write the sets $$A$$ and $$R.$$
5. Here is a diagram for a relation $$R$$ on a set $$A.$$ Write the sets $$A$$ and $$R.$$
6. Congruence modulo 5 is a relation on the set $$A = \mathbb{Z}.$$ In this relation $$xRy$$ means $$x \equiv y \pmod{5}.$$ Write out the set $$R$$ in set-builder notation.
7. Write the relation $$<$$ on the set $$A = \mathbb{Z}$$ as a subset $$R$$ of $$\mathbb{Z} \times \mathbb{Z}.$$ This is an infinite set, so you will have to use set-builder notation.
8. Let $$A = \{ 1, 2, 3, 4, 5, 6\}.$$ Observe that $$\emptyset \subseteq A \times A,$$ so $$R = \emptyset$$ is a relation on $$A.$$ Draw a diagram of this relation.
9. Let $$A = \{ 1, 2, 3, 4, 5, 6\}.$$ How many different relations are there on the set $$A$$?
10. Consider the subset $$R = ( \mathbb{R} \times \mathbb{R} ) \setminus \{ (x,x) : x \in \mathbb{R} \} \subseteq \mathbb{R} \times \mathbb{R}.$$ What familiar relation on $$\mathbb{R}$$ is this?
11. Given a finite set $$A,$$ how many different relations are there on $$A$$?

### Exercises for Section 11.1

1. Consider the relation $$R = \{ (a,a), (b,b), (c,c), (d,d), (a,b), (b,a) \}$$ on set $$A = \{ a, b, c, d \}.$$ Is $$R$$ reflexive? Symmetric? Transitive? If a property does not hold, say why.
2. Consider the relation $$R = \{ (a,b), (a,c), (c,c), (b,b), (c,b), (b,c) \}$$ on set $$A = \{ a, b, c \}.$$ Is $$R$$ reflexive? Symmetric? Transitive? If a property does not hold, say why.
3. Consider the relation $$R = \{ (a,b), (a,c), (c,b), (b,c) \}$$ on set $$A = \{ a, b, c \}.$$ Is $$R$$ reflexive? Symmetric? Transitive? If a property does not hold, say why.
4. Let $$A = \{ a, b, c, d \}.$$ Suppose $$R$$ is the relation \begin{align} R = \{ &(a,a), (b,b), (c,c), (d,d), (a,b), (b,a), (a,c), (c,a), \cr &(a,d), (d,a), (b,c), (c,b), (d,b), (d,b), (c,d), (d,c) \}. \end{align}

Is $$R$$ reflexive? Symmetric? Transitive? If a property does not hold, say why.

5. Consider the relation $$R = \{ (0,0), (\sqrt{2},0), (0,\sqrt{2}), (\sqrt{2}, \sqrt{2}) \}$$ on $$\mathbb{R}.$$ Is $$R$$ reflexive? Symmetric? Transitive? If a property does not hold, say why.
6. Consider the relation $$R = \{ (x,x) : x \in \mathbb{Z} \}$$ on $$\mathbb{Z}.$$ Is $$R$$ reflexive? Symmetric? Transitive? If a property does not hold, say why. What familiar relation is this?
7. There are 16 possible different relations on the set $$A = \{ a, b \}.$$ Describe all of them. (A picture of each will suffice, but don’t forget to label the nodes.) Which ones are reflexive? Symmetric? Transitive?
8. Define a relation on $$\mathbb{Z}$$ as $$x\operatorname{R}y$$ if $$\lvert x-y \rvert < 1.$$
Is $$R$$ reflexive? Symmetric? Transitive? If a property does not hold, say why. What familiar relation is this?
9. Define a relation on $$\mathbb{Z}$$ by declaring $$x \operatorname{R} y$$ if and only if $$x$$ and $$y$$ have the same parity. Is $$R$$ reflexive? Symmetric? Transitive? If a property does not hold, say why. What familiar relation is this?
10. Suppose $$A \neq \emptyset.$$ Since $$\emptyset \subseteq A \times A,$$ the set $$R = \emptyset$$ is a relation on $$A.$$ Is $$R$$ reflexive? Symmetric? Transitive? If a property does not hold, say why.
11. Suppose $$A = \{ a, b, c, d \}$$ and $$R = \{ (a,a), (b,b), (c,c), (d,d) \}.$$ Is $$R$$ reflexive? Symmetric? Transitive? If a property does not hold, say why.
12. Prove that the relation $$\vert$$ (divides) on the set $$\mathbb{Z}$$ is reflexive and transitive. (Use example 11.8 as a guide if you are unsure on how to proceed.)
13. Consider the relation $$R = \{ (x,y) \in \mathbb{R} \times \mathbb{R} : x - y \in \mathbb{Z} \}$$ on $$\mathbb{R}.$$ Prove that this relation is reflexive, transitive and symmetric.
14. Suppose $$R$$ is a symmetric and transitive relation on a set $$A,$$ and there is an element $$a \in A$$ for which $$a \operatorname{R} x$$ for every $$x \in A.$$ Prove that $$R$$ is reflexive.
15. Prove or disprove: If a relation is symmetric and transitive, then it is also reflexive.
16. Define a relation $$R$$ on $$\mathbb{Z}$$ by declaring that $$x \operatorname{R} y$$ if and only if $$x^2 \equiv y^2 \pmod{4}.$$ Prove that $$R$$ is reflexive, symmetric and transitive.
17. Modifying the above exercise 8 slightly, define a relation $$R$$ on $$\mathbb{Z}$$ as $$x \operatorname{R} y$$ if and only if $$\lvert x-y \rvert \leq 1.$$ Say whether $$R$$ is reflexive. Is it symmetric? Transitive?
18. The table on page 179 shows that relations on $$\mathbb{Z}$$ may obey various combinations of the reflexive, symmetric and transitive properties. In all, there are $$2^3 = 8$$ possible combinations, and the table shows 5 of them. (There is some redundancy, as $$\leq$$ and $$\vert$$ have the same type.) Complete the table by finding examples of relations on $$\mathbb{Z}$$ for the three missing combinations.