how many equivalance classes are in the function

Question

My Discrete Math textbook has this example of a function: There's a set $A=\text{{1,2,3}}$. Also: $f: P(A) \to P(A)$. The function is defined as follows: $$f(x)=\begin{cases} A-x;x\cap\{3\}\neq\emptyset\\ x\cup\{3\};x\cap\{3\}=\emptyset\\ \end{cases}$$ Lastly we set a relation $R=A\times A$ based on the function we defined above: $$xRy \iff f(x)=f(y)$$ The textbook then asks if the relation is an equivalence relation and if yes then how many equivalence classes there are. The answer is that yes it's an equivalence relation and there're 8 classes. Can you please help understand why? The way I see it let's take for example: $f(\{1\})=\{1,3\}$ while $ f(\{1,3\})=\{2\}$. In this example $f(x)\neq f(y)$ so $xRy$ is not (part of) the relation because it doesn't conform to the conditions. Same goes for all other members of the set.

Answer 1

Hint: $f$ is injective. $\phantom{yadayadayada}$.

---

Edit: I'll give some more details on how to solve this problem.

Let's show that $R$ is transitive: Suppose $x,y,z\in P(A)$ satisfying $xRy$ and $yRz$. We need to show that $xRz$.

By definition of $R$, $xRy$ means that $f(x)=f(y)$, and from $yRz$ we obtain $f(y)=f(z)$. Therefore, $f(x)=f(y)=f(z)$, which in turn implies $xRz$ as we wanted. Therefore $R$ is transitive. (If you think this is too pedantic, you can probably write a slicker version.)

Reflexivity and symmetry of $R$ are proved similarly, and I'll leave that to you.

As for the equivalence classes, you have to answer the question: "given $x\in P(A)$, what are the elements $y\in P(A)$ for which $xRy$?". The equivalence class of $x$ is then $R(x)=\left\{y\in P(A): xRy\right\}$. The number of equivalence classes is the number of distinct sets of the form $R(x)$, for $x\in P(A)$.

Answer 2

Note that ${\cal P}(A) = 2^3 = 8$, so each subset is on its own. There are no subsets $x \not= y$ such that $f(x) = f(y)$, but that doesn't mean it's not an equivalence relation.

---

ETA: We may need to go a little more basic here. First, what are the elements of ${\cal P}(A)$? They are:

$$ \emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\} $$

The function $f$ maps each of those sets into another set; respectively, they are

$$ \{3\}, \{1, 3\}, \{2, 3\}, \{1, 2\}, \{1, 2, 3\}, \{2\}, \{1\}, \emptyset $$

The definition of the relation $R$ says that $xRy$ whenever $f(x) = f(y)$. So let's suppose, just for example, that $x = \{1, 3\}$. Then $f(x) = \{2\}$. We ask ourselves, is there any $y$ such that $f(y)$ also equals $\{2\}$? We find that the only such $y$ is $x = \{1, 3\}$ itself. That is,

$$ \{1, 3\}Ry $$

only when $y = x = \{1, 3\}$ and for no other choice of $y$.

If we go through this exercise for all eight possible choices of $x$ (left to the reader), we find that this is true for all $x$: The only $y$ such that $f(y) = x$ is that $x$ itself. (This is because there are no two elements of ${\cal P}(A)$ that map to the same result.)

Is this an equivalence relation? Well, do we have $xRx$? Yes, if you go through the above exercise, you verify that. And is it the case that $xRy$ whenever $yRx$? You should be able to convince yourself that that is true, too, since the only relations are of the form $xRx$ anyway. And finally, if $xRy$ and $yRz$, is it also the case that $xRz$? Yes, for the same reason: we only have relations of the form $xRx$.