# Exercise on Relations

Let S and S‘ be the following subsets of the plane: $S = \{(x,y) | y = x+1, 0 and $S'= \{(x,y) | y-x \in \mathbb{Z} \}$

a) Show that S’ is an equivalence relation on the real line and that $S \subset S'$.

Proof: Reflexivity$x-x \in \mathbb{Z}, \forall x \in \mathbb{R}$

Symmetry$z \in \mathbb{Z} \Rightarrow -z \in \mathbb{Z}$

Transitivity- If $x~y, y~z$ then $z-y=(z-x)-(x-y)$ and thus z-y is the difference of two integers which implies that z-y is itself an integer.

To show that $S \subset S'$ we note that $y=x+1 \Rightarrow y-x=1$ which $\in \mathbb{Z}$

b) Show that given any collection of equivalence relations on a set A, their intersection is an equivalence relation in A.

Proof: Let $\{R_\alpha\}_\alpha\in A$ be a nonempty class of equivalence relations and let $\Omega = \cap_{\alpha \in A}R_\alpha$

Reflexivity- If $(x,y) \in R_\alpha, \forall_\alpha \in A$ then $(x,y) \in \Omega \Rightarrow (y,x) \in R_\alpha, \forall_\alpha \in a \Rightarrow (y,x) \in \Omega$.

Symmetry$(x,x) \in R_\alpha, \forall_\alpha \in A \Rightarrow (x,x) \in \Omega$.

Transitivity– If $(x,y), (y,z) \in R_\alpha, \forall_\alpha \in A$ then $(x,y), (y,z) \in \Omega \Rightarrow (x,z) \in R_\alpha, \forall_{\alpha \in A} \Rightarrow (x,z) \in \Omega \therefore$ the intersection is an equivalence relation on A.