We are given the set $E=\{d,e,f \}$, $d,e,f$ different from each other and the relation $I_{E}=\{ <x,x>: x \in E\}$. Prove that $I_{E}$ is a set. In addition, show that the relation $I_{E}$ is an equivalence relation in $E$ and find all the equivalence classes.

That's what I have tried:

We define $\phi(x)=<x,x>: x \in E$.

Then, we have that $\forall <x,x>(\phi(x)) \rightarrow <x,x> \in E \times E$.

$E \times E$ is a set. So, from the theorem: "Let $\phi$ a type. If there is a set $Y$, such that $\forall x(\phi(x)) \rightarrow x \in Y$, then there is the set $\{ x: \phi(x) \}$", we have that $I_{E}=\{ <x,x>: x \in E\}$ is a set.

The relation $I_{E}$ is an equivalence relation:

  • reflective: $<x,x> \in I_{E} \rightarrow <x,x> \in I_{E}$
  • symmetric: $<x,y> \in I_{E} \rightarrow x=y \rightarrow <y,x> \in I_{E}$
  • transitive: $<x,y> \in I_{E} \wedge <y,z> \in I_{E} \rightarrow x=y \wedge y=z \rightarrow <x,z> \in I_{E}$

Is it right so far? How could we find all the equivalence classes?

  • 1
    $\begingroup$ Correct. For $ x \in E $, What are the elements in the equivalence class containing $x$? $\endgroup$ – Thumbnail Nov 15 '14 at 11:42
  • $\begingroup$ @Thumbnail And how can we prove that $E \times E$ is a set? $$$$ The elements are of the form $\langle <x,x>\rangle: x \in E$, right ? $\endgroup$ – evinda Nov 15 '14 at 11:45
  • $\begingroup$ @Thumbnail Are the equivalence classes maybe these one: $\bigcup \{ \langle x,x \rangle: x \in E \}$ ? $\endgroup$ – evinda Nov 15 '14 at 11:48
  • $\begingroup$ No. The equivalence class containing $x$ under relation $R$ is $$ \{y \in E: x \ R \ y \} $$ Because R is an equivalence relation, such classes partition $E$. If you connect equivalent $x$ and $y$ with an edge, the equivalence classes are the connected components of the (unordered) graph. As for proving that $I_E$ is a set, I can't help. I guess you have rules that certain well-formed formulae involving sets are sets too. $\endgroup$ – Thumbnail Nov 15 '14 at 12:01

If $R$ is an equivalence relation then $\left[x\right]_{R}=\left\{ y\mid xRy\right\} =\left\{ y\mid\left\langle x,y\right\rangle \in R\right\} $.

Here $R=1_{E}$ leading to $xRy\iff x=y$.

So $\left[x\right]_{I_{E}}=\left\{ y\mid x=y\right\} =\left\{ x\right\} $.

  • $\begingroup$ drhab A ok.. So, would it be wrong to say that $[x]_{I_E}=\bigcup \{ \langle x,x \rangle: x \in E\}$ ? $\endgroup$ – evinda Nov 15 '14 at 11:53
  • $\begingroup$ Yes. On LHS $x$ is fixed and on RHS it ranges over $E$. $\endgroup$ – drhab Nov 15 '14 at 11:55
  • $\begingroup$ drhab A ok.. And could you also tell me if that's what I have tried is right? $\endgroup$ – evinda Nov 15 '14 at 11:57
  • 1
    $\begingroup$ Your proof that relation $1_E$ is an equivalence relation is correct. Further I am not familiar with what you call 'types'. To prove that $I_E$ is a set I would use the separation axiom: if $E\times E$ is a set then $\left\{ z\in E\times E\mid\psi\left(z\right)\right\} $ is a set, and for $\psi\left(z\right)$ I would take the sentence: $\exists x\left[x\in E\wedge z=\left\langle x,x\right\rangle \right]$. $\endgroup$ – drhab Nov 15 '14 at 12:07
  • $\begingroup$ drhab With type I mean the $\psi(z)$.. If we have to prove that $ \times E$ is a set, which else $Y$ could we use at the implication: $$\forall \langle x,x \rangle(\phi(x))\rightarrow \langle x,x \rangle \in Y$$ $\endgroup$ – evinda Nov 15 '14 at 12:12

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.