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