Equivalence relation generated by a relation: concrete characterization

476 Views Asked by At

Let $R$ be a relation on a set $X$. The equivalence relation $\sim_R$ generated by $R$ is defined as $\bigcap A$ for $A$ being the set of all equivalence relations containing $R$ ($A$ is not empty as $X\times X \in A$).

Different sources claim that it's possible to give a concrete definition of two elements $x$ and $y$ being in relation $\sim_R$ to each other:

For any $x,y \in X, x \sim_R y$ if and only if there is a $n \in \mathbb{N}_{>0}$ and $x_1,...,x_n \in X$ so that

  • $x_1 = x$,

  • $x_n = y$,

  • for any $1 \leq k < n$ we have either $(x_k,x_{k+1}) \in R$ or $(x_{k+1},x_k) \in R$.

The "only if" part of the proof is carefully explained in this answer. However, I can't understand why having $n \in \mathbb{N}_{>0}$ and $x_1,...,x_n \in X$ so that $x_1 = x, x_n = y$ and for any $1 \leq k < n$ having either $(x_k,x_{k+1}) \in R$ or $(x_{k+1},x_k) \in R$ implies that $(x,y) \in {\sim_R}$.

1

There are 1 best solutions below

3
On BEST ANSWER

Why having $n \in \mathbb{N}_{>0}$ and $x_1,...,x_n \in X$ so that $x_1 = x, x_n = y$ and for any $1 \leq k < n$ having either $(x_k,x_{k+1}) \in R$ or $(x_{k+1},x_k) \in R$ implies that $(x,y) \in {\sim_R}$.

This is easy. It suffices to show that $(x,y) \in A$ for any all equivalence relation $A$ containing $R$. We have $(x_k,x_{k+1}) \in A$ for any $1 \leq k < n$, so $(x,y)=(x_1,x_n)\in A$ by transitivity of $A$.