Equivalent Characterizations of Finer Equivalence Relation

Theorem

Let $X$ be a set.

Let $\equiv$ and $\sim$ be equivalence relations on $X$.

The following are equivalent:

1. $\equiv$ is finer than $\sim$:
$\forall x, y \in X : x \equiv y \implies x \sim y$
2. The graph of $\equiv$ is contained in the graph of $\sim$.
3. Every $\equiv$-equivalence class is contained in a $\sim$-equivalence class.
4. Every $\sim$-equivalence class is saturated under $\equiv$.

Proof

1 implies 2

 $\displaystyle \tuple {x, y}$ $\in$ $\displaystyle \map \TT \equiv$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle x$ $\equiv$ $\displaystyle y$ Definition of Graph of Relation $\displaystyle \leadsto \ \$ $\displaystyle x$ $\sim$ $\displaystyle y$ from $1$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle \tuple {x, y}$ $\in$ $\displaystyle \map \TT \sim$ Definition of Graph of Relation

By definition of subset, $\map \TT \equiv \subseteq \map \TT \sim$.

$\Box$

2 implies 1

 $\displaystyle x$ $\equiv$ $\displaystyle y$ Definition of Equivalence Class $\displaystyle \leadstoandfrom \ \$ $\displaystyle \tuple {x, y}$ $\in$ $\displaystyle \map \TT \equiv$ Definition of Graph of Relation $\displaystyle$ $\subseteq$ $\displaystyle \map \TT \sim$ from $2$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle x$ $\sim$ $\displaystyle y$ Definition of Graph of Relation

$\Box$

1 implies 3

Let $x \in X$.

Then:

 $\displaystyle y$ $\in$ $\displaystyle \eqclass x \equiv$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle y$ $\equiv$ $\displaystyle x$ Definition of Equivalence Class $\displaystyle \leadsto \ \$ $\displaystyle y$ $\sim$ $\displaystyle x$ from $1$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle y$ $\in$ $\displaystyle \eqclass x \sim$ Definition of Equivalence Class

By definition of subset, $\eqclass x \equiv \subseteq \eqclass x \sim$.

$\Box$

3 implies 1

For this proof and the next, we use this result implied by $3$:

Let $y \in X$.

$3$ implies:

$\exists z \in X: \eqclass y \equiv \subseteq \eqclass z \sim$
$y \in \eqclass y \equiv \subseteq \eqclass z \sim$
$y \in \eqclass y \sim$
$\eqclass y \sim = \eqclass z \sim$

Hence $\eqclass y \equiv \subseteq \eqclass y \sim$.

Thus:

 $\displaystyle x$ $\equiv$ $\displaystyle y$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle x$ $\in$ $\displaystyle \eqclass y \equiv$ Definition of Equivalence Class $\displaystyle$ $\subseteq$ $\displaystyle \eqclass y \sim$ $\displaystyle \leadstoandfrom \ \$ $\displaystyle x$ $\sim$ $\displaystyle y$ Definition of Equivalence Class

$\Box$

3 implies 4

Let $x \in X$.

 $\displaystyle \bigcup_{y \mathop \in \eqclass x \sim} \eqclass y \equiv$ $\subseteq$ $\displaystyle \bigcup_{y \mathop \in \eqclass x \sim} \eqclass y \sim$ Set Union Preserves Subsets $\displaystyle$ $=$ $\displaystyle \bigcup_{\substack {y \mathop \in X \\ y \mathop \sim x} } \eqclass y \sim$ Definition of Equivalence Class $\displaystyle$ $=$ $\displaystyle \bigcup_{\substack {y \mathop \in X \\ y \mathop \sim x} } \eqclass x \sim$ Equivalence Class holds Equivalent Elements $\displaystyle$ $=$ $\displaystyle \eqclass x \sim$

so $\eqclass x \sim$ is a union of equivalence classes under $\equiv$.

Hence $\eqclass x \sim$ is saturated under $\equiv$.

$\Box$

4 implies 3

Let $x \in X$.

Then $\eqclass x \sim$ is saturated under $\equiv$:

$\displaystyle \exists S \subseteq X: \bigcup_{y \mathop \in S} \eqclass y \equiv = \eqclass x \sim$
$x \in \eqclass x \sim$
$x \in \eqclass x \equiv$

Hence by definition of Union of Family:

$\exists z \in S: x \in \eqclass z \equiv$
 $\displaystyle \eqclass x \equiv$ $=$ $\displaystyle \eqclass z \equiv$ $\displaystyle$ $\subseteq$ $\displaystyle \bigcup_{y \mathop \in S} \eqclass y \equiv$ Set is Subset of Union $\displaystyle$ $=$ $\displaystyle \eqclass x \sim$

$\blacksquare$