2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Namaste Feb 8 '18 at 23:15
  • $\begingroup$ Ya I figured those would be the cases for reflexivity and symmetry. Your answer for transitivity was superb. Thank you so much! $\endgroup$ – Wallace Feb 8 '18 at 23:19
  • $\begingroup$ Happy to help, Wallace. $\endgroup$ – Namaste Feb 8 '18 at 23:20
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.