Equivalence relation-equivalence classes

[evinda]

Hello! (Smile)

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? (Thinking)

 

[Evgeny.Makarov]

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

It is not clear what this means. $\phi(x)$ must be a property, i.e., something that is either true or false for every $x$. How is what you wrote true or false for a given $x$?

Recall that the notation $\{\langle x,x\rangle:x\in E\}$ is a contraction for $\{y:\exists x\in E\;y=\langle x,x\rangle\}$. Then it make sense to define $\phi(y)$ to be $\exists x\in E\;y=\langle x,x\rangle$. Then $\phi(y)$ is indeed true or false for every $y$. Next, we indeed have that $\forall y\;(\phi(y)\to y\in E\times E)$, and since $E\times E$ is a set, $\{y:\phi(y)\}$ is also a set.

• 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}$

Symmetry and transitivity make sense, but the definition of reflexivity does not involve an implication.

How could we find all the equivalence classes?

The equivalence class of $d$ consists of all elements that are equivalent to $d$ with respect to this relation. What are those elements?

 

[evinda]

Recall that the notation $\{\langle x,x\rangle:x\in E\}$ is a contraction for $\{y:\exists x\in E\;y=\langle x,x\rangle\}$. Then it make sense to define $\phi(y)$ to be $\exists x\in E\;y=\langle x,x\rangle$. Then $\phi(y)$ is indeed true or false for every $y$. Next, we indeed have that $\forall y\;(\phi(y)\to y\in E\times E)$, and since $E\times E$ is a set, $\{y:\phi(y)\}$ is also a set.

I understand.. (Nod) Do we have to prove that $E \times E$ is a set? If so, how could we do this? (Thinking)

Symmetry and transitivity make sense, but the definition of reflexivity does not involve an implication.

So, can we just say that it is obvious that the relation is reflective? (Thinking)

The equivalence class of $d$ consists of all elements that are equivalent to $d$ with respect to this relation. What are those elements?

Do these elements belong maybe to this set: $\{ \langle x,y \rangle : x,y \in E \}=\{ \langle x,y \rangle: x=y \wedge x \in E\}=\{ \langle x,x \rangle: x \in E\}=\bigcup \{ \langle x,x \rangle: x \in E\} $

Or am I wrong? (Worried)

 

[Evgeny.Makarov]

Do we have to prove that $E \times E$ is a set? If so, how could we do this?

You proved in another thread that the Cartesian product of two sets is a set.

So, can we just say that it is obvious that the relation is reflective?

You write that something is obvious if, first, you personally are able to explain this fact at any level of detail, up to axioms, and, second, you think that it is clear to the reader as well. It's hard for me to say if you can explain this fact at any level of detail.

Do these elements belong maybe to this set: $\{ \langle x,y \rangle : x,y \in E \}=\{ \langle x,y \rangle: x=y \wedge x \in E\}=\{ \langle x,x \rangle: x \in E\}=\bigcup \{ \langle x,x \rangle: x \in E\} $

You have three elements: $d$, $e$ and $f$. What is equivalent to $d$, i.e., what is related to $d$ by the relation $I_E$? Well, $e$ is not because $\langle d,e\rangle\notin I_E$. Is $f$ equivalent to $d$? Is $d$? Those elements for which the answer is yes form the equivalence class of $d$, often denoted by $[d]$. Do the same thing with $e$ and $f$.

 

[evinda]

You proved in another thread that the Cartesian product of two sets is a set.

So, since we know that the Cartesian product of two sets is a set, can we just say that $E \times E$ is a set, as it is a Cartesian product? (Thinking)

You write that something is obvious if, first, you personally are able to explain this fact at any level of detail, up to axioms, and, second, you think that it is clear to the reader as well. It's hard for me to say if you can explain this fact at any level of detail.

Isn't a relation $R$ reflective, if $xRx$ ? In our case, it is always $xI_{E}x$, or am I wrong?

You have three elements: $d$, $e$ and $f$. What is equivalent to $d$, i.e., what is related to $d$ by the relation $I_E$? Well, $e$ is not because $\langle d,e\rangle\notin I_E$. Is $f$ equivalent to $d$? Is $d$? Those elements for which the answer is yes form the equivalence class of $d$, often denoted by $[d]$. Do the same thing with $e$ and $f$.

The only element that is equivalent to $d$ is $d$, right?
So, is it like that?
$$[d]=d, \ [e]=e \ , [f]=f$$

Or am I wrong? (Thinking)

 

[Evgeny.Makarov]

Isn't a relation $R$ reflective, if $xRx$ ? In our case, it is always $xI_{E}x$, or am I wrong?

Yes.

The only element that is equivalent to $d$ is $d$, right?
So, is it like that?
$$[d]=d, \ [e]=e \ , [f]=f$$

Correct, but the equivalence class is a set because in general it consists of several elements, so the right-hand sides should be surrounded by curly braces.