Exercise 1.1 · Q7: Books with the same number of pages

Basics you need

Solution

1. Give the page count a name

   For each book $x\in A$⁠, let

   $$p(x) = \text{the number of pages of } x.$$

   Each book has one definite number of pages, so $p(x)$ is a single natural number for every $x$⁠. The rule becomes

   $$(x,y)\in R \iff p(x) = p(y).$$
   A sentence like "$x$ and $y$ have the same number of pages" is hard to manipulate. The equation $p(x)=p(y)$ is easy: it is an equality between two numbers, and we know exactly how equality behaves (Basic 3). The fact that each book has exactly one page count matters: it means $p(x)$ is a well-defined number we can compare.
   $p$ is a function from $A$ to $\N$⁠: it assigns one natural number to each book. Basics: what a function is

2. Reflexive: every book has the same number of pages as itself

   Take any book $x\in A$⁠. Then $p(x) = p(x)$⁠, so $(x,x)\in R$⁠. Since $x$ was arbitrary, $R$ is reflexive.

   This looks too obvious to write down, but it is exactly what the definition asks: each element related to itself. It uses the reflexive property of equality, $m = m$⁠.
   Reflexive: $(x,x)\in R$ for every $x\in A$ (Definition 3(i), Section 1.2).

3. Symmetric: "same pages" reads the same both ways

   Suppose $(x,y)\in R$⁠. Then $p(x) = p(y)$⁠. Reading the equation from right to left, $p(y) = p(x)$⁠, so $(y,x)\in R$⁠. Hence $R$ is symmetric.

   We start from the "if" part, $(x,y)\in R$⁠, and derive $(y,x)\in R$⁠. The step uses the symmetric property of equality: if $m = n$ then $n = m$⁠. In words: if $x$ has as many pages as $y$⁠, then $y$ has as many pages as $x$⁠.
   Symmetric: $(x,y)\in R \Rightarrow (y,x)\in R$ (Definition 3(ii)).

4. Transitive: two equalities chain into one

   Suppose $(x,y)\in R$ and $(y,z)\in R$⁠. Then

   $$p(x) = p(y) \qquad\text{and}\qquad p(y) = p(z).$$

   Both $p(x)$ and $p(z)$ equal the same number $p(y)$⁠, so $p(x) = p(z)$⁠. Hence $(x,z)\in R$⁠, and $R$ is transitive.

   This uses the transitive property of equality. The middle book $y$ acts as a link: if $x$ and $y$ both have, say, 200 pages, and $y$ and $z$ both have 200 pages, then $x$ and $z$ both have 200 pages. Note that $x$⁠, $y$⁠, $z$ need not be different books; the argument works whether or not they are.
   Transitive: $(x,y)\in R$ and $(y,z)\in R \Rightarrow (x,z)\in R$ (Definition 3(iii)).

5. Conclude, and see the equivalence classes

   $R$ is reflexive, symmetric and transitive, so by Definition 4 $R$ is an equivalence relation.

   Its equivalence classes are the groups "all books with exactly $n$ pages", one group for each page count that occurs in the library. For a small shelf of eight books A to H with page counts 200, 350, 200, 120, 350, 200, 120, 480:

   An equivalence relation always sorts its set into non-overlapping groups. Here the grouping is by page count, and since each book has exactly one page count, each book lands in exactly one group. This is the same pattern as Example 21: whenever a relation is defined by "$f(x) = f(y)$" for some function $f$⁠, it is an equivalence relation.
   The equivalence classes of an equivalence relation are disjoint and their union is the whole set. Basics: equivalence classes

Every fact used, and where it comes from