Example 21: $f(a)=f(b)$ defines an equivalence relation

Basics you need

Solution

1. Read the rule

   By definition,

   $$(a,b)\in R \iff f(a) = f(b).$$

   Because $f$ is a function, $f(a)$ and $f(b)$ are definite elements of $Y$⁠, so for any $a, b\in X$ the question "is $f(a) = f(b)$⁠?" has a definite yes or no answer. Thus $R$ is a well-defined relation in $X$⁠.

   Every property we test will be turned into a statement about equality of images in $Y$⁠. This only works because each element has a single image (Basic 1). If $f$ were allowed to give two outputs for one input, "$f(a) = f(b)$" would be ambiguous.
   A function assigns exactly one image to each element of its domain. Basics: what a function is

2. Reflexive

   Take any $a\in X$⁠. Then $f(a) = f(a)$⁠, since any element equals itself. So $(a,a)\in R$ for every $a\in X$⁠, and $R$ is reflexive.

   $(a,a)\in R$ means $f(a) = f(a)$⁠, which compares an element of $Y$ with itself. That is always true, for every $a$⁠, whatever $f$ is.
   Equality is reflexive: $p = p$ (Basic 2).

3. Symmetric

   Suppose $(a,b)\in R$⁠. Then

   $$f(a) = f(b) \ \Longrightarrow\ f(b) = f(a) \ \Longrightarrow\ (b,a)\in R.$$

   So $R$ is symmetric.

   "$f(a) = f(b)$" and "$f(b) = f(a)$" are the same statement read in two directions. The first is the meaning of $(a,b)\in R$⁠, the second the meaning of $(b,a)\in R$⁠.
   Equality is symmetric: $p = q \Rightarrow q = p$ (Basic 2).

4. Transitive

   Suppose $(a,b)\in R$ and $(b,c)\in R$⁠. Then

   $$\begin{aligned} &f(a) = f(b) \ \text{ and } \ f(b) = f(c)\\ \Longrightarrow\ &f(a) = f(c) \ \Longrightarrow\ (a,c)\in R. \end{aligned}$$

   So $R$ is transitive.

   The middle element $b$ appears only through its image $f(b)$⁠, which is equal to both $f(a)$ and $f(c)$⁠. Two things equal to the same thing are equal to each other, so $f(a) = f(c)$⁠, and $b$ has disappeared, as transitivity requires.
   Equality is transitive: $p = q$ and $q = r \Rightarrow p = r$ (Basic 2).

5. Conclude

   $R$ is reflexive, symmetric and transitive. Hence $R$ is an equivalence relation in $X$, for every function $f : X\to Y$⁠.

   The question says "examine whether … or not", so the answer could have been "no". It is "yes", and the proof used nothing about $f$ except that it is a function. So the conclusion holds for every function, with no exceptions to look for.
   Definition 4: a relation that is reflexive, symmetric and transitive is an equivalence relation. Lesson: types of relations

6. See the classes on a concrete function

   Take $X = \{-2,-1,0,1,2\}$⁠, $Y = \{0,1,4\}$ and $f(x) = x^2$⁠. The images are $f(\pm2) = 4$⁠, $f(\pm1) = 1$⁠, $f(0) = 0$⁠. Two elements are related exactly when their squares are equal, so the equivalence classes are

   $$\{-2, 2\}, \qquad \{-1, 1\}, \qquad \{0\}.$$

   Two special cases are worth noting. If $f$ is one-one, then $f(a) = f(b)$ only when $a = b$⁠, so $R = \{(a,a) : a\in X\}$ and every class has a single element. If $f$ is constant, then all images are equal, so $R = X\times X$ and there is one class.

   This construction is how many equivalence relations in the chapter arise. In Example 5 and Example 6, take $f(a)$ to be the remainder of $a$ on division by 2: "same parity" is "same image". In Example 20, take $f(x)$ to be the remainder on division by 3. Seeing a relation as "same value of some function" is a quick way to know it is an equivalence relation.
   One-one means $f(a) = f(b)\Rightarrow a = b$⁠. Basics: one-one and onto The classes of an equivalence relation are disjoint and cover $X$⁠. Basics: equivalence classes

Every fact used, and where it comes from