I want to share my efforts on a (standard) exercise on generated equivalence relations, that I (surprisingly) struggled with at first. I took the exercise out of Lee's "Topological Manifolds", but you find it in many places of course. While part a) and the "if-part" of b) are real easy, I struggled substantially on the "only if"-implication of b) and was even worried after some thoughts, if this finite sequence transitivity statement might even be wrong (forming counterexamples in my mind - with uncountable partitions, where the transitivity might distribute over uncountably long connections ..).
Thus I started to google and found the statement confirmed (of course) - but surprisingly I did not find a proof of my problem implication in the net (sure there will be one, but I did not come across). So (luckily) I had to sit down and come up with a proof myself, that kind of convinces me now, that my worries / counterexamples had no substance. However, the argument got more involved (relatively...) than expected - thus I decided to share - and of course ask for feedback and simpler ways to see this! Thx!!
Exercise: Let $R\subseteq X\times X$ be any relation on $X$, and define $\sim$ to be the intersection of all equivalence relations in $X\times X$ that contain $R$.
a) Show that $\sim$ is an equivalence relation.
b) Show that $x\sim y$ if and only if at least one of the following statements is true: $x=y$ or $x\ R'\ y$, or there is a finite sequence of elements $z_1,\dots z_n\in X$ such that $x\ R'\ z_1\ R'\cdots R'\ z_n\ R'\ y$, where $x\ R'\ y$ means "$x\ R\ y$ or $y\ R\ x$".
Proof: a) Let $Q:=\displaystyle\bigcap_{\tilde{R}\supseteq R\text{ eq.rel.}}\tilde{R}$ the intersections of all equivalence relations on $X$ containing $R$. Since $\forall x\in X\,\forall\tilde{R}\supseteq R$ equivalence relation: $x\sim_{\tilde{R}}x\Leftrightarrow(x,x)\in\tilde{R}$ follows $(x,x)\in Q\Leftrightarrow x\sim_Q x$.
$x\sim_Q y\Leftrightarrow\,\forall \tilde{R}\supseteq R: (x,y)\in\tilde{R}$. Since $\tilde{R}$ is a equivalence relation, this implies that $(y,x)\in\tilde{R}$ for all $\tilde{R}$. Thus: $x\sim_Q y\Rightarrow y\sim_Q x\ \forall x,y\in X$.
Exactly analogously follows $x\sim_Q y$ and $y\sim_Q z\Rightarrow x\sim_Q z\ \forall x,y,z\in X$. Thus $Q$ is an equivalence relation.
b) $\Leftarrow$: Since $\sim$ is an equivalence relation: $x=y$ implies $x\sim x(=y)$ by reflexivity. If $x\ R'\ y$ then (w.l.o.g. $x\ R\ y$) implies, for all $\tilde{R}\supseteq R: (x,y)\in\tilde{R}\Rightarrow(y,x)\in\tilde{R}$ by symmetry of $\tilde{R}$, which implies $x\sim y$ and $y\sim x$, using that $\sim$ is the intersection over all these $\tilde{R}$.
If $x\ R'\ z_1\ R'\cdots R'\ z_n\ R'\ y$ for some $x,y,z_i\in X$, then for all $\tilde{R}\supseteq R:$ $(x,z_1),(z_n,y)\in\tilde{R}$ and $\forall i,j\le n:(z_i,z_j)\in\tilde{R}\ \Rightarrow(x,y)\in\tilde{R}$ by transitivity of $\tilde{R}$. Thus: $x\ R'\ z_1\ R'\cdots R'\ z_n\ R'\ y$ for some $x,y,z_i\in X$ implies $x\sim y$.
$\Rightarrow:$ By contraposition, let $x\neq y$ in $X$ such that neither $x\ R'\ y$ nor exist $z_1,\dots z_n\in X$ with $x\ R'\ z_1\ R'\cdots R'\ z_n\ R'\ y$. Let $Y:=\{y\}\cup\{z\in X:y R' z\text{ or }\exists n\in\mathbb{N},z_1\dots z_n:yR'z_1 R'\cdots R'z_n R' z\}$ and $Z:=X\setminus Y$, i.e. $Y$ contains all "to $y$ via $R$ connected" elements. By the assumption, we have $x\in Z, y\in Y$.
We claim first, that $R\subseteq(Y\!\times\!Y\cup Z\!\times\!Z)$: Indeed, assume there was $(y',z)\in R\cap (Y\!\times\!Z)$ - then since $y'\in Y$, exist $z_1,\dots z_n\in Y$ such that $yR'z_1 R'\cdots R'z_n R' y'$ and it follows $yR'z_1 R'\cdots R'z_n R' y' R' z$ which gives $z\in Y$ by definition of $Y$, a contradiction. Analogously $R\cap (Z\!\times\!Y)$ gives a contradiction, and the assertion $R\subseteq(Y\!\times\!Y\cup Z\!\times\!Z)$ follows.
Using a) now we define $Q_Y\subseteq Y\!\times\!Y$ as the smallest equivalence relation $\sim_Y$ on $Y$ generated by $R\cap(Y\!\times\!Y)$, $Q_Z\subseteq Z\!\times\!Z$ as the smallest equivalence relation $\sim_Z$ on $Z$ generated by $R\cap(Z\!\times\!Z)$ and $Q:=Q_Y\cup Q_Z\subseteq X\!\times\!X$. Then by the above $R\subseteq Q$ and $Q$ is an equivalence relation on $X=Y\cup Z$ as union of two disjoint equivalent relations (this is immediate from the 1:1 correspondence of equivalence relations with partitions of the underlying set).
Now $Q$ is one of the equivalence relations on $X$ containing $R$, that are intersected to form $\sim$ and $(x,y)\in Z\!\times Y$ implies $(x,y)\notin Q$. Thus follows $x\not\sim y$ which was to show. q.e.d