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:


  • 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.

  • $\begingroup$ I'm not sure I understand your proof of symmetry. The point is that if $(x,y) \in S'$, so that $x-y = n$ is an integer, then $y-x=-n$ is an integer, so $(y,x) \in S'$. This shows symmetry. A similar comment can be made for transitivity. $\endgroup$ – Jeff Jul 13 '11 at 23:33
  • $\begingroup$ I've added LaTeX formatting to your question. Apologies if I changed any intended meaning; feel free to edit further if you like. $\endgroup$ – Zev Chonoles Jul 13 '11 at 23:35
  • $\begingroup$ the intersection of all equivalence relations on $\mathbb{R}$ containing $S$ would be $S$ if $S$ were an equivalence relation. but it is not (for example, it's not reflexive since no pair of the form $(x,x)$ is in $S$ $\endgroup$ – algebra_fan Jul 13 '11 at 23:38
  • $\begingroup$ I would try to think about the equivalence classes of $S'$ for a little while longer. These are subsets of $\mathbf{R}$, so are probably not diagonal lines! $\endgroup$ – Dylan Moreland Jul 13 '11 at 23:47
  • $\begingroup$ I think you meant $S$ is a subset of $S'$; the statement "$S'$ is a subset of $S$" is false. $\endgroup$ – algebra_fan Jul 13 '11 at 23:58

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.