Question

X be a non-empty set and let R be an equivalence relation on X. For each x ∈ X, define
[x]={y∈X suchthatxRy}
to be the equivalence class of x. Here x R y means (x, y) ∈ R.
SupposethatA=[x]andB=[y]. ProvethatifA∩B̸=∅,thenA=B.

Answer 1

Answer provided by https://www.AssignmentExpert.com

Answer on Question #75995 – Math – Discrete Mathematics

Question

X be a non-empty set and let $R$ be an equivalence relation on $X$.

For each $x \in X$, define $[x] = \{y \in X \mid x R y\}$ to be the equivalence class of $x$. Here $x R y$ means $(x, y) \in R$.

Suppose that $A = [x]$ and $B = [y]$. Prove that if $A \cap B \neq \emptyset$, then $A = B$.

Solution

$A \cap B \neq \emptyset$. It means that $\exists z \in A \cap B$ i.e. $(z \in A) \land (z \in B) \sim (z R x) \land (z R y)$. Because of the symmetry of the relation $R (x R z) \land (z R y)$. According to transitivity of the relation $R$ we obtain that $x R y$.

1) We choose and fix $\forall h \in A$. Let's prove that $h \in B$.

$$h \in A \Rightarrow (h R x) \land (x R y) \Rightarrow h R y \text{ i.e. } h \in B.$$

2) We choose and fix $\forall h \in B$. Similarly we can prove that $h \in A$.

$$h \in B \Rightarrow (h R y) \land (x R y) \Rightarrow (\text{according to symmetry of } R) \Rightarrow (h R y) \land (y R x) \Rightarrow (\text{according to transitivity of } R) \Rightarrow h R x,$$

i.e. $h \in A$.