MHB Equivalence relation-equivalence classes

AI Thread Summary
The discussion centers on proving that the relation \( I_E = \{<x,x> : x \in E\} \) is a set and an equivalence relation on the set \( E = \{d,e,f\} \). Participants clarify that \( I_E \) is reflexive, symmetric, and transitive, confirming it as an equivalence relation. They explore the equivalence classes, concluding that each element in \( E \) is only equivalent to itself, resulting in the classes \( [d] = \{d\} \), \( [e] = \{e\} \), and \( [f] = \{f\} \). The discussion emphasizes the need for precise definitions and understanding of reflexivity and the nature of equivalence classes.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Physics news on Phys.org
evinda said:
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.

evinda said:
  • 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.

evinda said:
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?
 
Evgeny.Makarov said:
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)

Evgeny.Makarov said:
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)

Evgeny.Makarov said:
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)
 
evinda said:
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.

evinda said:
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.

evinda said:
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$.
 
Evgeny.Makarov said:
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)

Evgeny.Makarov said:
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? :confused:

Evgeny.Makarov said:
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)
 
evinda said:
Isn't a relation $R$ reflective, if $xRx$ ? In our case, it is always $xI_{E}x$, or am I wrong?
Yes.

evinda said:
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.
 

Similar threads

Back
Top