1

I am currently stuck on the second part of the following exercise (Exercise A.3 from Introduction to Topological Manifolds):
“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$.

  • Show that $\sim$ is an equivalence relation.
  • Show that $x \sim y$ if and only if at least one of the following statements is true:
    1. $x = y,$
    2. $x R’ y,$
    3. there is a finite sequence of elements ${z_1, \dots, z_n} \in X$ such that $xR’z_1R’ \dots R’z_nR’ y,$
    where $xR’y$ means $xRy$ or $yRx$.

I am comfortable proving that LHS $\impliedby$ RHS by showing that RHS is contained in any equivalence relation on $X$ containing $R$. However, I am struggling to deduce RHS from LHS. Any help would be greatly appreciated.

Theo Bendit
  • 50,900
VillainousPie
  • 13
  • Welcome. I suggest that you give a more descriptive title (especially since this has nothing to do with topology or manifolds) – FShrike Jun 15 '22 at 22:46
  • One way to proceed is by showing that if none of 1, 2, or 3 are true, then there exists an equivalence relation on $X$ under which $x$ and $y$ are non-equivalent. Another way is to show that the smallest relation closed under 1, 2, and 3 is itself an equivalence relation. (These are probably the same method in dishuise.) – Greg Martin Jun 15 '22 at 23:23

1 Answers1

0

Since I do not want to write some unusual notation such as $\sim_1 \subseteq \sim_2$, I will use this notation:

  • $E_1$ is the equivalence relation defined by the intersection;
  • $E_2$ is the relation defined by the three conditions.

As you rightly said, $E_2$ is is a subset of any equivalence relation containing $R$, and thus $E_2\subseteq E_1$.

It remains to show $E_1\subseteq E_2$. To see this, it is enough to show that $E_2$ is an equivalence relation and that it contains $R$. (Since then $E_2$ is one of the relations used in the intersection.)

You might have a look at some results about transitive (and maybe reflexive and symmetric closure, too):

Martin Sleziak
  • 53,687