Paper 4, Section I, E

Let $R_{1}$ and $R_{2}$ be relations on a set $A$. Let us say that $R_{2}$ extends $R_{1}$ if $x R_{1} y$ implies that $x R_{2} y$. If $R_{2}$ extends $R_{1}$, then let us call $R_{2}$ an extension of $R_{1}$.

Let $Q$ be a relation on a set $A$. Let $R$ be the extension of $Q$ defined by taking $x R y$ if and only if $x Q y$ or $x=y$. Let $S$ be the extension of $R$ defined by taking $x S y$ if and only if $x R y$ or $y R x$. Finally, let $T$ be the extension of $S$ defined by taking $x T y$ if and only if there is a positive integer $n$ and a sequence $\left(x_{0}, x_{1}, \ldots, x_{n}\right)$ such that $x_{0}=x, x_{n}=y$, and $x_{i-1} S x_{i}$ for each $i$ from 1 to $n$.

Prove that $R$ is reflexive, $S$ is reflexive and symmetric, and $T$ is an equivalence relation.

Let $E$ be any equivalence relation that extends $Q$. Prove that $E$ extends $T$.

*Typos? Please submit corrections to this page on GitHub.*