1

As part of a proof I have to show that: For $ \phi, \psi $ equivalence relations ($\in Eq(A)$):

$$ \phi \cup (\phi \circ \psi ) \cup (\phi \circ \psi \circ \phi )\cup (\phi \circ \psi \circ\phi \circ \psi ) \cup \ldots $$ Is also an equivalence relation.

Reflexivity is pretty simple, since for all $ a \in A: (a,a)\in\phi$ . But I have troubles showing symmetry and transitivity...

Tanks for the help!

M-S-R
  • 335

1 Answers1

2

Let $\theta:=\phi\cup(\phi\circ\psi)\cup(\phi\circ\psi\circ\phi)\cup\dots$.
Assume $x\,\theta\,y$, then there are elements $z_i$ such that $x\,\phi\,z_1\, \psi\, \dots\, z_n\, \rho\,y$ where $\rho$ is either $\phi$ or $\psi$, according to the parity of $n$.

Even if $n$ is odd (whence $\rho=\psi$), we can make it even by adding $z_{n+1}:=y$ and noting that $y\,\phi\,y$.
But then, we get $y\,\phi\,z_n\,\psi\,\dots\,z_1\,\phi\,x$ showing that $y\,\theta\, x$.

Transitivity can be proved similarly, perhaps reducing to the case when the above $n$ is odd eases it up.

Berci
  • 90,745