Proof about equivalence relations

Question

Let $R$ be a reflexive and symmetric relation on a set $X$. A pair $x,y ∈ X$ are connected via $R$ if there are elements $x = x_0, x_1, . . . , x_k = y$ such that $(x_i, x_{i+1}) ∈ R$ for all $i = 0, 1, . . . , k − 1$. Let $S = \{(x, y)|x,y $ are connected via $R$ $\}$. Prove that S is an equivalence relation.

Approach: This time I don't have an approach because I don't understand how the relation R works on X. Is it basically saying $(x,y) \in R$ if x and y are different?

Proof

$(x,x)\in S$ because $(x,x) \in R$ hence are connected by definition, so S is reflexive

if $(x,y) \in S$, there exists a set of ordered pairs in R in the form $(x,z_i)........(z_k,y)$ which implies that there is also a path from y to x so $(y,x) \in S$ which implies that S is symmetric

if $(x,y),(y,z) \in S$ then there exists ordered pairs in R such that $(x,z_i),....,(z_k,y),(y_j,i),...,(j_k,z)$. This implies that there is a path from x to z, so $(x,z) \in S$. Therefore, S is transitive.

Does that make sense? I feel like I am being a little informal

Answer 1

Think of $R$ as defining a graph. $x$ and $y$ are related by $S$ if $x$ and $y$ if there is a path between $x$ and $y$, i.e. if $x$ and $y$ are in the same connected component. You just need to apply the definition of equivalence relation to $S$.

(i) Show that there is a path between $x$ and $x$ via $R$. (ii) Show that if there is a path from $x$ to $y$ then there is a path from $y$ to $x$. (iii) Show that if there is a path from $x$ to $y$ and a path from $y$ to $z$, then there's a path from $x$ to $z$.

Answer 2

$S$ is called the transitive closure of $R$, often written $R^+$.

If we write $a\rightsquigarrow b$ for $(a,b)\in R$, then $(a,x)$ is in $S$ if there is a path $$ a \rightsquigarrow b \rightsquigarrow c \rightsquigarrow \cdots\rightsquigarrow v\rightsquigarrow w \rightsquigarrow x$$

---

For example, if $R$ is $\{(x,y)\in\mathbb R^2\mid x+x = y\}$ (never mind that is not reflexive and symmetric), then $R^+$ would be $$ \{(x,y)\in\mathbb R^2 \mid x\cdot 2^n=y \text{ for some }n\in\mathbb N_+\}$$