2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The equivalence relation is: $x\sim_S y\iff \text{ there exists a chain of pairs in } R \text{ connecting } x\text{ to }y$ $\endgroup$ – b00n heT Jun 4 '16 at 9:11
  • $\begingroup$ 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}$ $\endgroup$ – TheMathNoob Jun 4 '16 at 9:15
  • $\begingroup$ @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}$. $\endgroup$ – Henning Makholm Jun 4 '16 at 9:17
1
$\begingroup$

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

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.