# Union of disjoint sets : Equivalence relations

I'm not exactly sure how to go about doing this question. I've attempted it but I'm not exactly sure if it's correct.

Question: Let $S$ be the union of disjoint sets $A_1, \cdots, A_k$. Let $R$ be the relation consisting of pairs $(x, y) \in S \times S$ such that $x, y$ belong to the same member of $\{A1, \cdots, A_k\}$. Prove that $R$ is an equivalence relation on $S$.

The three axioms are: reflexivity, symmetry, transitivity,

I have a brief idea of how to do the first 2, however, for transitivity, I don't have any ideas. Could anyone help out on this please?

Transitivity:

For all $x, y, z \in S,$ suppose $(x, y) \in R,$ and $(y, z) \in R$.

That means that $x$ and $y$ are contained within the same $A_i$, among the disjoint sets, and that $y, z$ are contained within the same $A_j$, among the disjoint sets. Because the sets are disjoint, there is no way that $y$ can appear in more than one of the sets whose union is $S$, (i.e., it is not possible that $x, y,$ are in $A_i,$ while $y, z$ are both in $A_j,$ and $i\neq j$). Hence, $A_i = A_j$ for some $i$.

We must conclude that $x, y, z$ are in the same set, disjoint from all other sets in the union that is $S$, and so $(x, z) \in R.$

• I suggest you post your ideas, Wallace, re reflexivity. They are much simpler. For all $x \in S$, we have $(x, x) \in R$, because if x is in one of the disjoint sets, x is in the same set with itself. Similarly with symmetry: if $(x, y) \in R,$ then $x, y$ are both elements in the same A_i. So clearly, y and x are both elements in the same A_i. So symmetry holds. – Namaste Feb 8 '18 at 23:15
• Ya I figured those would be the cases for reflexivity and symmetry. Your answer for transitivity was superb. Thank you so much! – Wallace Feb 8 '18 at 23:19
• Happy to help, Wallace. – Namaste Feb 8 '18 at 23:20

The disjoint sets $A_1,...,A_k$ form the parts of a partition of $S$.   So every elements of $S$ belongs to exactly one part.

Let $[x]$ be the set of elements in the same part as $x$. $$[x]:=\{y\in S:\exists A\in\{A_1,..,A_k\}~(x\in A \wedge y\in A)\}$$

The relation $\operatorname R$ is thus defined as $x\operatorname Ry \iff x\in [y]$. ie: $$x\operatorname Ry ~\iff~ \exists A\in\{A_1,..,A_k\}~(x\in A\wedge y\in A)$$

Then you must show ${\;\\\begin{split}&\text{Reflexivity: }&\forall x~ (x\operatorname Rx)\\&\text{Symmetry:}&\forall x~\forall y~ (x\operatorname Ry\to y\operatorname Rx)\\&\text{Transitivity: }&\forall x~\forall y~\forall z~ ((x\operatorname Ry~\wedge~y\operatorname Rz)~\to~x\operatorname Rz)\end{split}}$

That is: $\forall x~ (x\in[x])\\\forall x~\forall y~ (x\in[y]\to y\in[x])\\\forall x~\forall y~\forall z~ ((x\in[y]~\wedge~y\in[z])~\to~x\in[z])$

I have a brief idea of how to do the first 2, however, for transitivity, I don't have any ideas. Could anyone help out on this please?

Every elements of $S$ belongs to exactly one part.   So if any $x$ is in the same part as any $y$, and that $y$ is in the same part as any $z$, then ...