A hint for the last part of (A): $S'$ has one equivalence class for each real number in the interval $[0,1)$.
In (B) you have to consider completely arbitrary families of equivalence relations on $A$, so you want to begin something like this: Let $\mathcal E$ be a collection of equivalence relations on $A$, and let $E_0=\bigcap\mathcal E$. You must then show that $E_0$ is an equivalence relation on $A$. Certainly $E_0\subseteq A\times A$, so $E_0$ is a relation on $A$. To see that $E_0$ is reflexive, let $x\in A$. For every $E\in\mathcal E$, $E$ is reflexive, so $\langle x,x \rangle\in E$, and therefore $\langle x,x \rangle\in\bigcap\mathcal E=E_0$, i.e., $E_0$ is reflexive. The other properties of an equivalence relation are proved similarly.
To show that $E_0$ is symmetric, suppose that $x,y \in A$ and $\langle x,y \rangle \in E_0$. Let $E \in \mathcal E$; then $\langle x,y \rangle \in E$ (why?), so $\langle y,x \rangle \in E$ (why?). Hence $\langle y,x \rangle \in \bigcap\mathcal E = E_0$ (why?), and $E_0$ is symmetric.
To show that $E_0$ is transitive, suppose that $x,y,z \in A$ and $\langle x,y \rangle, \langle y,z \rangle \in E_0$. Now follow the same basic pattern as for symmetry and reflexivity to show that $\langle x,z \rangle \in E_0$.
(C) $S = \{\langle x,x+1 \rangle:x \in (0,2)\}$; if $E$ is an equivalence relation on $\mathbb R$ that contains $S$, what other ordered pairs absolutely have to belong to $E$ besides the ones that are already in $S$?
$E$ is reflexive, so $\langle x,x \rangle$ has to belong to $E$ for each $x \in \mathbb R$. What else? $\langle 1,2 \rangle \in E$, and $E$ is symmetric, so $\langle 2,1 \rangle$ has to belong to $E$. There’s nothing special about $\langle 1,2 \rangle$: you can make the same argument for every $\langle x,x+1 \rangle \in S$. Thus, for each $x \in (0,2)$, $E$ has to contain not only $\langle x,x+1 \rangle$, but also ...?
Finally, what does transitivity of $E$ say about which ordered pairs have to be in $E$ besides those that are already in $S$? For instance, $\langle 0.1,1.1 \rangle, \langle 1.1,2.1 \rangle \in S$, so $E$ has to contain $\langle 0.1,2.1 \rangle$, and symmetry requires that $E$ also contain $\langle 2.1,0.1 \rangle$. This also generalizes: for each $x \in (0,1)$, $S$ includes both $\langle x,x+1 \rangle$ and $\langle x+1,x+2 \rangle$, so $E$ has to contain what two ordered pairs that aren’t already in $S$?
If you follow through these ideas carefully, you should be able to find an equivalence relation $E$ containing $S$ that must be a subset of any equivalence relation containing $S$ and therefore must be the intersection of all such equivalence relations. Moreover, every equivalence class of $E$ except the one that contains $1$ will have either one or three members.
You are correct that the relation defined is an equivalence relation on A is an equivalence relation, essentially $$\forall x \in A, xRy \iff 3\mid (x - y) \iff x\equiv y \pmod 3$$
The relation $R$, i.e., defines congruence modulo $3$. So your task boils down to finding the congruence classes, $\pmod 3$.
Do you know how to find the equivalence classes of your set, $\pmod 3$?
- Class one: Which elements have are divisible by $3$? $\quad A_0 = \{-3, 0, 3\}$
- Class two: Which elements leave a remainder of $1$ when divided by $3$? $\quad A_1 =\{-2, 1, 4\}$
- Class three: Which elements leave a remainder of $2$ when divided by $3$? $\quad A_2 = \{-4, -1, 2, 5\}$
You're done: three equivalence classes.
$$A = A_0 \cup A_1 \cup A_2 = \{-4,-3,-2,-1,0,1,2,3,4,5\},$$ $$ \quad A_i \cap A_j = \varnothing, \;\text{when}\;\;i\neq j, \text{ for}\;\; i, j \in \{0, 1, 2\}$$
Best Answer
Equivalence relations on a set correspond one-to-one with partitions of that set.
The question can actually be rephrased as:
"If $P$ is a partition on set $A$ and has $4$ elements then how many partitions on $A$ exist that are coarser than $P$?"
A partition $Q$ is by definition coarser than partition $P$ if every element of $P$ is a subset of an element of $Q$.
The answer is $15$.