Problem with Equivalence Relations

Question

Having some problems with this question and hoping someone could help.

Let $S$ and $S'$ be the following subsets of the plane: $$S = \{(x,y): y=x+1\text{ and }x\text{ a member of }(0,2)\},$$ $$S'= \{(x,y): y-x\text{ is an integer}\}.$$

A. Show that $S'$ is an equivalence relation on the real line and $S$ is a subset of $S'$. Describe the equivalence classes of $S'$.

B. Show that given any collection of equivalence relations on a set $A$, their intersection is an equivalence relation on $A$.

C. Describe the equivalence relation $T$ on the real line that is the intersection of all equivalence relations on the real line that contain $S$. Describe the equivalence classes of $T$.

C is the problem I am having the most difficulty with.

Answers so far:

a.

• EDIT: Symmetric: if (x,y) works then, $y-x=n \rightarrow x-y=-n$

• Reflexive because $x-x = 0$

• EDIT: Transitive $x-y=n$ and $y-z=k$ $\rightarrow y=k+z \rightarrow x-(k+z)=n \rightarrow x-z = k+n=p$

• $S: y=x+1 \rightarrow y-x=1$, 1 integer out of the set of all integers in $S'$.

• Equivalence classes of $S$ would be all diagonal lines with slope 1 through $y=n$ and $x=n$.

b. $E_1$ and $E_2$ equivalence relations. Intersections both contain $(x,y)$ and $(y,x)$ because if they are members of either $E_1$ or $E_2$ they are satisfy equivalence requirements.

c. I am not sure how to answer this. I thought the intersection of all equivalence relations on the real line containing $S$ would be $S$.

Any help would be greatly appreciated.

Answer 1

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.