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

• The equivalence relation is: $x\sim_S y\iff \text{ there exists a chain of pairs in } R \text{ connecting } x\text{ to }y$ – b00n heT Jun 4 '16 at 9:11
• ok how do you understand this notation? $(x_i,x_{i+1})$. Is it a short path of two elements that connects $x_i$ to $x_{i+1}$ – TheMathNoob Jun 4 '16 at 9:15
• @TheMathNoob: Recall that a relation is a set of pairs; $(x_i,x_{i+1})$ is just one particular such pair, consisting of the elements we call $x_i$ and $x_{i+1}$. – Henning Makholm Jun 4 '16 at 9:17

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$.

• I already tried to prove it , but my proof looks a bit informal – TheMathNoob Jun 4 '16 at 9:38

$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_+\}$$

• I already tried to prove it , but my proof looks a bit informal – TheMathNoob Jun 4 '16 at 9:38