The definition of an equivalence relation

Question

I am reading a paper by Carlsson on Topological pattern recognition for point cloud data. I was having a little trouble understanding the formal definition of an equivalence relation and equivalence class in relation to persistent homology. Could someone please clarify the definition below. I have my own interpretation, listed below, but please correct me if I am wrong.

A (binary) relation on a set $X$ is a subset of $X × X$. We will often denote relations by $\sim$, and write $x ∼ x$ to indicate that $(x, x)$ is in the relation.

Definition 2.1. A relation ∼ on a set X is an equivalence relation if the following three conditions hold:

1. $x ∼ x$ for all $x \in X$,
2. $x ∼ x'$ if and only if $x' ∼ x$,
3. $x ∼ x'$ and $x' ∼ x''$ implies $x ∼ x''$

By the equivalence class of $x \in X$, denoted by $[x]$, we will mean the set $$\{x \mid x ∼ x \}$$

So as I interpret it, $\forall x \in X$, then $X \times X := \{(x,x)| x \in X\}$. If we denote $A = \{(x,x)| x \in X\}$, then there exists an equivalence relation between $x_1 \sim x_2$ if

1. both $ x_1, x_2 \in X$
2. $(x_1, x_2) \in A$
3. $(x_2, x_1) \in A$
4. if $(x_1, x_2) \in A$ and $(x_2, x3) \in A$, then $(x_1, x_3) \in A$.

I think this is the right interpretation, but just wanted to make sure I was on the right track.

Answer 1

A binary relation $R$ is a subset of $X \times Y$, often written $xRy$ if $(x,y) \in R $. You can generally identify a binary relation with its graph. For example, a relation you know a lot about is $x \le y$. You would graph everything below the 45 degree line in $\mathbb{R}^2$ to represent it.

If $x Ry$ or $yRx$ or both for all $(x,y) \in X \times Y$, $R$ is complete or total. If whenever $xRy$ and $yRz$ then $xRz$, then $R$ is transitive. A relation $R$ is reflexive if $xRx$ whenever $X=Y$; so $5 \ge 5$ is true but $5 >5$ is false, and $\ge$ is reflexive but $>$ is not. For example, all real numbers are completely ordered by $\ge$; in $\mathbb{R}^N$, vectors are partially ordered if $x_i \ge y_i$ for each $i$ or vice versa, and unordered otherwise. A reflexive, transitive relation $R$ is a preorder. So this kind of $R$ is about comparing objects and determining which one is "larger".

A relation $R$ is symmetric if $xRy$ iff $yRx$. This is where the idea of the equivalence relation comes into play. Where reflexive and transitive allows for relations like $x \ge y$, symmetry requires $xRy$ and $yRx$ whenever one is true. So $x \ge y$ is a preorder, but $x=y$ is an equivalence relation; every preorder can be broken into a symmetric equivalence relation $=$ and an anti-symmetric/irreflexive strict relation $>$. Often, a set of unique class representative $x$ are selected, and their equivalence classes denoted $[x]$. For example, if you fix a vector $x$ and a constant $c$, the set of all affine hyperplanes $a'x + c$ can be broken into equivalence classes by $a$: essentially, all the parallel hyperplanes that go through the origin the same way when $c$ is ignored. Or, functions that are almost everywhere/almost surely equal. Instead of ordering elements, $R$ is breaking $X \times X$ into classes of objects that are, from some perspective, equivalent.

Answer 2

Not quite.

• When you write $X \times X$ you need to have two variables in your set builder notation. $X \times X = \{(x,y) \mid x,y \in X\}$. Otherwise you're requiring that the components of each ordered pair be the same. You can say the same when defining the relation $A$, and you should say that $A \subset X \times X$.

Answer 3

So as I interpret it, ∀x∈X , then X×X:={(x,x)|x∈X}. If we denote A={(x,x)|x∈X}, then there exists an equivalence relation between x1∼x2 if

both x1,x2∈X

(x1,x2)∈A (x2,x1)∈A if (x1,x2)∈A and (x2,x3)∈A, then (x1,x3)∈A.

---

$\bullet$ The way you express the definition seems to indicate that , in your mind, this definition answers he question : is there an / some equivalence relation between these two given objects?

I think this way of considering the question is dangerous, since , arguably, there always exists $\underline{some}$ equivalence relation between any two given objets.

$\bullet $ Consider all the objects of the world, and take, in particular two objets , say my hat ( I got only one ) and the Eiffel Tower. Now define two categories of objects : Category$-1$, the category of objects that are neither my hat nor the Eiffel Tower; and Category$-2$ the category of objects that are either my hat or the Eiffel Tower. ( Note that these 2 categories actually exist, they are not fictitious).

Now define a relation $R_1$ by $xR_1y$ if and only if "$x$ belongs to the same category as $y$". This relation is certainly an equivalence relation for

(i) any object belongs to the same category as itself , that is, in symbols for all object $x$ , $xR_1x$ is true ; meaning that , always,

$$(x,x) \in R_1$$

(ii) belonging to the same category is symmetric ( or reciprocal ) ; in symbols , we always have :

$$xR_1y \rightarrow yR_1x$$

or

$$(x,y) \in R_1 \rightarrow (y,x)\in R_1$$

(iii) and finally, belonging to the same category is transitive, meaning that in case $x R_1y$ and $yR_1z$ are both true ( whatever $x,y$ and $z$ may be) $xR_1z$ is always true , or, equivalently

$$ [ (x,y) \in R_1 { \& } (y,z) \in R_1 ] \rightarrow (x,z) \in R_1$$

Now , does this equivalence relation hold between my hat and the Eiffel Tower? Yes it does ; my hat actually belongs to the same category as the Eiffel tower, namely the category called "Category 2". And, of course, the relation also holds between the Eiffel Tower and my hat ( since an equivalence relation is reciprocal) .

Note that this relation also holds between the Sun and my car ( since the Sun belongs to the same category as my car, namely, Category$-1$).

$\bullet$ Consequently, it would certainly be better to consider the question the other way round.

(1) You are given a determinate relation $R_2$ ( for example " the elements of set $X$ can be put in perfect 1-1 correspondence with the elements of set $Y$" , which is the relation of "equinumericity")

(2) You test the relation regarding equivalence-ness : is this particular relation $R_2$ an equivalence relation?

(3) You ask yourself the question : does this particular equivalence relation hold between object $a$ and objet $b$ , that is, does the ordered pair $(a, b)$ belong to $R_2$? Say, for example ,

does this relation hold between the set of multiples of 5 (namely the set $\{ 5, 10, 15, ...\}$) and the whole set of natural numbers ( namely the set $\{1, 2, 3, 4 ...\}$)?

In case you answer "yes", you can conclude that the first set has the same number of elements as the second one.