Prove that $R$ is an equivalence relation and that $C = X/R$

46 Views Asked by At

Consider a non empty set $C$ with non empty elements such that, for all $x$ and $y$ belonging to $C$ , if $x \neq y$ then $x \cap y = \emptyset$.

Let $X = \bigcup C$ and define a relation $R$ as the set of pairs $(x, y) \in X^2$ that for such exist $z \in C$ s.t. $x \in z$ and $y \in z$.

$(i)$ Prove that $R$ is an equivalence relation on $X$

$(ii)$ Show that $C = X/R$

I have no idea how to approach this exercise.

1

There are 1 best solutions below

3
On

First, your statement of the problem is somewhat unclear. I guess you are saying $C$ is a non-empty set of non-empty sets, and $C$ has the property that any two distinct sets in $C$ are disjoint.

Your definition of $X$ is very unclear. However, I believe you mean to say $X = \bigcup_{x\in C} x $.

If this is what you mean to say, then we can proceed.

(i) To prove $R$ is an equivalence relation, you must show reflexivity, symmetry, and transitivity. Reflexivity and symmetry are immediate (if you need further explanation, comment so). For transitivity, let $x,y,u \in X$ be so that $(x,y), (y,u)\in R$. We wish to show $(x,u)\in R$. By definition of $R$, there is $z_1,z_2 \in C$ such that $x,y\in z_1$ and $y,u \in z_2$. By the property of $C$, $z_1$ and $z_2$ are either disjoint or equal. Since $y\in z_1 \cap z_2$, we have the latter case. Therefore $z_1 = z_2$ and therefore $x,u\in z_1$. Hence $(x,u) \in R$. This proves (i).

(ii) For this part, we just show set containment. Let $z \in C$. Since $z$ is not empty, there is $x \in z \subset X$. I claim $z = [x]$, where $[x]$ is the equivalence class of $x\in X$ with respect to $R$. This is another set equivalence argument. Let $y\in z$. Then since $x\in z$ as well, we have $(x,y)\in R$ and hence $y\in [x]$. Let $y\in [x]$. Then there is $z_1\in C$ so that $x,y\in z_1$. However, by the property of $C$, $z = z_1$, and hence $y\in z$. Thus $z = [x] \in X/R$. This shows $C \subset X/R$.

On the other hand, let $[x]\in X/R$. By definition of $X$, $x\in z$ for some $z\in C$. Use a similar argument as above to show $[x] = z$. Once you show this, then you have $[x] \in C$, and hence $X/R \subset C$. Thus giving $C = X/R$.