# Equivalence relation-equivalence classes

• MHB
• evinda
In summary, the conversation discusses the proof that the relation $I_E$ defined as $\{\langle x,x\rangle:x\in E\}$ is a set, and that it is also an equivalence relation in the set $E$. The steps to prove this are outlined, including the use of 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) \}$. Additionally, the group explores the concept of equivalence classes and how they can be determined by finding all elements that are equivalent to a given element with respect to the relation $I_E$.
evinda
Gold Member
MHB
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)

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?

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.

## 1. What is an equivalence relation?

An equivalence relation is a mathematical concept that defines a relationship between elements of a set. It is a binary relation that is reflexive, symmetric, and transitive. This means that every element is related to itself, if two elements are related, their order does not matter, and if two elements are related and one is related to a third element, then the first element is also related to the third element.

## 2. What are equivalence classes?

Equivalence classes are subsets of a set that contain elements that are related to each other by an equivalence relation. Elements in the same equivalence class are considered equivalent, while elements in different equivalence classes are not equivalent. Equivalence classes can be thought of as categories or groups of related elements.

## 3. How do you determine if a relation is an equivalence relation?

To determine if a relation is an equivalence relation, you must check if it satisfies the three properties: reflexivity, symmetry, and transitivity. If the relation satisfies all three properties, then it is an equivalence relation. If it fails to satisfy any of the properties, then it is not an equivalence relation.

## 4. What is the significance of equivalence relations and classes in mathematics?

Equivalence relations and classes are important concepts in mathematics because they allow us to categorize and classify elements based on their relationships. They also help us establish connections between seemingly unrelated elements, which can lead to new discoveries and insights in various fields, such as algebra, geometry, and topology.

## 5. Can you provide an example of an equivalence relation and its corresponding equivalence classes?

One example of an equivalence relation is "having the same birthday" on a set of people. This relation is reflexive (everyone has the same birthday as themselves), symmetric (if person A has the same birthday as person B, then person B also has the same birthday as person A), and transitive (if person A has the same birthday as person B, and person B has the same birthday as person C, then person A also has the same birthday as person C). The corresponding equivalence classes would be the groups of people who share the same birthday, such as "January 1st", "February 14th", "December 25th", etc.

• Set Theory, Logic, Probability, Statistics
Replies
0
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
9
Views
1K
• Special and General Relativity
Replies
1
Views
263
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
807
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
204
• Set Theory, Logic, Probability, Statistics
Replies
5
Views
919
• Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
4
Views
1K