Exercise 3.5

Proof. First note that $S^{\prime }\subset ℝ\times ℝ$ and so is a relation on $ℝ$. We show that $S^{\prime }$ has the three properties required of an equivalence relation.

(Reflexivity) Consider any $x\in ℝ$ so that clearly $x-x=0$ is an integer. Hence $(x,x)\in S^{\prime }$ by definition. This shows that $S^{\prime }$ is reflexive since $x$ was arbitrary.

(Symmetry) Suppose that $x,y\in ℝ$ and $x{S}^{\prime }y$. Then $n=y-x$ is an integer so that $x-y=-(y-x)=-n$ is also clearly an integer. Therefore $y{S}^{\prime }x$ as well, which shows that $S^{\prime }$ is symmetric.

(Transitivity) Consider $x,y,z\in ℝ$ and suppose that both $x{S}^{\prime }y$ and $y{S}^{\prime }z$. Then $n=y-x$ and $m=z-y$ are both integers. We then have

$$\begin{array}{cc}z-x=z-x+y-y=(z-y)+(y-x)=m+n,& \end{array}$$

which is clearly an integer since $m$ and $n$ are. Hence $x{S}^{\prime }z$ so that $S^{\prime }$ is transitive.

It is easy to show that $S^{\prime }\supset S$. Consider any $(x_{},y_{})\in S$ so that $0<x<2$ and $y=x+1$. Then $y-x=(x+1)-x=1$, which is of course an integer. Hence $(x_{},y_{})\in S^{\prime }$, and thus $S^{\prime }\supset S$ since $(x_{},y_{})$ was arbitrary. □

Proof. Let $A^{\text{∗}}$ be a collection of equivalence relations on $A$ so that we must show that $C={\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{D\in A^{\text{∗}}}D$ is also an equivalence relation on $A$. First, suppose that any $(x_{},y_{})\in C$ and consider any $D\in A^{\text{∗}}$ so that $(x_{},y_{})\in D$. Then also $(x_{},y_{})\in A\times A$ since $D$ is a relation on $A$ so that $D\subset A\times A$. This shows that $C\subset A\times A$ since $(x_{},y_{})$ was arbitrary, and so $C$ is a relation on $A$. Now we show the three required properties of an equivalence relation:

• (Reflexivity) Consider any $x\in A$ so that $(x,x)\in D$ for every $D\in A^{\text{∗}}$ since each $D$ is an equivalence relation and so is reflexive. It then follows that $(x,x){\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{D\in A^{\text{∗}}}D=C$, which shows that $C$ is reflexive.
• (Symmetric) Suppose that $(x_{},y_{})\in C$ and consider any $D\in A^{\text{∗}}$ so that also $(x_{},y_{})\in D$. Then also $(y,x)\in D$ since $D$ is an equivalence relation and so is symmetric. Since $D$ was arbitrary, this shows that $(y,x)\in {\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{D\in A^{\text{∗}}}D=C$ so that $C$ is symmetric. □

Proof. Let $S^{\text{∗}}$ denote the collection of all equivalence relations on $ℝ$ that contain $S$ so that we must show that $T={\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{R\in S^{\text{∗}}}R$.

$\text{(⊂)}$ Consider any $(x_{},y_{})\in T$ and any $R\in S^{\text{∗}}$ so that $R$ is an equivalence relation on $ℝ$ that contains $S$. We then have the following cases:

Case: $(x_{},y_{})\in S_1$. Then of course $y=x$ so that $(x_{},y_{})=(x,x)\in R$ since it is an equivalence relation and thus reflexive.

Case: $(x_{},y_{})\in S_2=S$. Then of course $(x_{},y_{})\in R$ since $R$ contains $S$.

Case: $(x_{},y_{})\in S_3$. Then we have that $y=x-1$ with $1<x<3$, from which it follows that $x=y+1$ and $0<y=x-1<2$. Therefore $(y,x)\in S$ so that $(y,x)\in R$ since $R$ contains $S$. We then have that $(x_{},y_{})\in R$ as well since $R$ is an equivalence relation and therefore symmetric.

Case: $(x_{},y_{})\in S_4$. Then $y=x+2$ with $0<x<1$. Let $z=x+1$ so that $(x,z)\in S=S_4$ since we also have $0<x<1<2$. We then know that $(x,z)\in R$ since $R$ contains $S$. We also then have that $y=x+2=(x+1)+1=z+1$ with $0<1<z=x+1<2$ since $0<x<1$. Thus $(z,y)\in S=S_4$ so that also $(z,y)\in R$. Since $R$ is an equivalence relation and therefore transitive, we have that $(x_{},y_{})\in R$ as well.

Case: $(x_{},y_{})\in S_5$. Then we have $y=x-2$ and $2<x<3$. It then follows that $x=y+2$ and $0<y=x-2<1$ so that $(y,x)\in S_4$. Then of course $(y,x)\in R$ by the previous case so that also $(x_{},y_{})\in R$ since $R$ is an equivalence relation and therefore symmetric.

Thus in every case $(x_{},y_{})\in R$ so that also $(x_{},y_{})\in {\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{R\in S^{\text{∗}}}R$ since $R$ was arbitrary. It then follows that $T\subset {\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{R\in S^{\text{∗}}}R$ since $(x_{},y_{})$ was arbitrary.

$\text{(⊃)}$ All we really need to show is that $T$ is an equivalence relation on $ℝ$ that contains $S$. From this it follows that $T\in S^{\text{∗}}$ so that of course $T\supset {\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{R\in S^{\text{∗}}}R$. First, we note that clearly, $T\subset {ℝ}^2$ so that it is a relation on $ℝ$. Also clearly it contains $S$ since $S=S_2\subset T$. Now we show that it has the three properties that an equivalence relation requires.

(Reflexivity) For any $x\in ℝ$ clearly $(x,x)\in S_1\subset T$ so that $T$ is reflexive.

(Symmetry) Suppose that $\mathit{xTy}$ so that $(x_{},y_{})\in T$. We then have the following cases:

Case: $(x_{},y_{})\in S_1$. Then of course $y=x$ so $(y,x)=(x,x)=(x_{},y_{})\in S_1\subset T$.

Case: $(x_{},y_{})\in S_2=S$. Then $y=x+1$ and $0<x<2$ so that $x=y-1$ and $1<y=x+1<3$. Hence $(y,x)\in S_3\subset T$.

Case: $(x_{},y_{})\in S_3$. Then we have that $y=x-1$ with $1<x<3$, from which it follows that $x=y+1$ and $0<y=x-1<2$. Therefore $(y,x)\in S=S_2\subset T$.

Case: $(x_{},y_{})\in S_4$. Then $y=x+2$ with $0<x<1$ so that $x=y-2$ and $2<y=x+2<3$. Hence $(y,x)\in S_5\subset T$.

Case: $(x_{},y_{})\in S_5$. Then we have $y=x-2$ and $2<x<3$ so that $x=y+2$ and $0<y=x-2<1$. Hence $(y,x)\in S_4\subset T$.

So in all cases $(y,x)\in T$, which shows that $T$ is symmetric.

(Transitivity) Now suppose that $\mathit{xTy}$ and $\mathit{yTz}$. If $x=y$ then of course we have $(x,z)=(y,z)\in T$. Similarly if $y=z$ then $(x,z)=(x_{},y_{})\in T$. So assume that $x\ne y$ and $y\ne z$ so that it can neither be that $(x_{},y_{})\in S_1$ nor $(y,z)\in S_1$. Thus there are four sets (i.e. $S_i$ where $i\in \left\{2,3,4,5\right\}$) that $(x_{},y_{})$ and $(y,z)$ can be in, which results in sixteen different possibilities, though not all are possible:

Case: $(x_{},y_{})\in S_2$. Then $y=x+1$ and $0<x<2$ so that $1<y=x+1<3$.

• Case: $(y,z)\in S_2$. Then also $z=y+1$ and $0<y<2$ so that $z=y+1=(x+1)+1=x+2$ and $y=x+1<2$ means that $x<1$. Hence $z=x+2$ and $0<x<1$ so that $(x,z)\in S_4\subset T$.
• Case: $(y,z)\in S_3$. Then $z=y-1$ and $1<y<3$ so that $z=y-1=(x+1)-1=x$, and hence $(x,z)=(x,x)\in S_1\subset T$.
• Case: $(y,z)\in S_4$. This case is not possible because $1<y<3$ so that it cannot be that $0<y<1$ and hence $(y,z)$ cannot be in $S_4$.
• Case: $(y,z)\in S_5$. Then $z=y-2$ and $2<y<3$ so that $z=y-2=(x+1)-2=x-1$ and $2<y=x+1<3$ means that $1<x<2<3$. Hence $z=x-1$ and $1<x<3$ so that $(x,z)\in S_3\subset T$.

Case: $(x_{},y_{})\in S_3$. Then $y=x-1$ and $1<x<3$ so that $0<y=x-1<2$.

• Case: $(y,z)\in S_2$. Then $z=y+1$ and $0<y<2$ so that $z=y+1=(x-1)+1=x$ and hence $(x,z)=(x,x)\in S_1\subset T$.
• Case: $(y,z)\in S_3$. Then $z=y-1$ and $1<y<3$ so that $z=y-1=(x-1)-1=x-2$ and $1<y=x-1$ and hence $2<x$. Therefore $z=x-2$ and $2<x<3$ so that $(x,z)\in S_5\subset T$.
• Case: $(y,z)\in S_4$. Then $z=y+2$ and $0<y<1$ so that $z=y+2=(x-1)+2=x+1$ and $y=x-1<1$ and hence $x<2$. Thus $z=x+1$ and $0<1<x<2$ so that $(x,z)\in S_2\subset T$.
• Case: $(y,z)\in S_5$. This is case is not possible because $y<2$ so that it cannot be that $2<y<3$, and hence $(y,z)$ cannot be in $S_5$.

Case: $(x_{},y_{})\in S_4$. Then $y=x+2$ and $0<x<1$ so that $2<y=x+2<3$.

• Case: $(y,z)\in S_2$. This case is also impossible because $2<y$ so that it cannot be that $0<y<2$, and hence $(y,z)$ cannot be in $S_2$.
• Case: $(y,z)\in S_3$. Then $z=y-1$ and $1<y<3$ so that $z=y-1=(x+2)-1=x+1$ and $y=x+2<3$ so that $x<1<2$. Thus $z=x+1$ and $0<x<2$ so that $(x,z)\in S_2\subset T$.
• Case: $(y,z)\in S_4$. This case is not possible because again $2<y$ so that it cannot be that $0<y<1$, and hence $(y,z)$ cannot be in $S_4$.
• Case: $(y,z)\in S_5$. Then $z=y-2$ and $0<y<1$ so that $z=y-2=(x+2)-2=x$ and hence $(x,z)=(x,x)\in S_1\subset T$.

Case: $(x_{},y_{})\in S_5$. Then $y=x-2$ and $2<x<3$ so that $0<y=x-2<1$.

• Case: $(y,z)\in S_2$. Then $z=y+1$ and $0<y<2$ so that $z=y+1=(x-2)+1=x-1$ and $0<y=x-2$ so that $1<2<x$. Therefore $z=x-1$ and $1<x<3$ so that $(x,z)\in S_3\subset T$.
• Case: $(y,z)\in S_3$. This case is not possible because $y<1$ so that it cannot be that $1<y<3$, and hence $(y,z)$ cannot be in $S_3$.
• Case: $(y,z)\in S_4$. Then $z=y+2$ and $0<y<1$ so that $z=y+2=(x-2)+2$ and hence $(z,x)=(x,x)\in S_1\subset T$.
• Case: $(y,z)\in S_5$. This case is also not possible because again $y<1$ so that it cannot be that $2<y<3$, and hence $(y,z)$ cannot be in $S_5$.

Thus in every case that is actually possible, we have that $(x,z)\in T$, which shows that $T$ is transitive.

Therefore $T$ is an equivalence relation that contains $S$ so that $T\supset {\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{R\in S^{\text{∗}}}R$ as discussed above, which of course completes the proof that $T={\bigcap <!--\; FUNCTION\; APPLICATION\; -->}_{R\in S^{\text{∗}}}R$. □