# Problem with Equivalence Relations

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.

-
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. –  Jeff Jul 13 '11 at 23:33
I've added LaTeX formatting to your question. Apologies if I changed any intended meaning; feel free to edit further if you like. –  Zev Chonoles Jul 13 '11 at 23:35
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$ –  algebra_fan Jul 13 '11 at 23:38
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! –  Dylan Moreland Jul 13 '11 at 23:47
I think you meant $S$ is a subset of $S'$; the statement "$S'$ is a subset of $S$" is false. –  algebra_fan Jul 13 '11 at 23:58

## 1 Answer

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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9266762137413025, "perplexity": 106.2668741896798}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-22/segments/1432207927634.1/warc/CC-MAIN-20150521113207-00055-ip-10-180-206-219.ec2.internal.warc.gz"}