Equivalent Characterizations of Finer Equivalence Relation

From ProofWiki
Jump to navigation Jump to search

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$

By Element in its own Equivalence Class:

$y \in \eqclass y \equiv \subseteq \eqclass z \sim$
$y \in \eqclass y \sim$

By contrapositive of Equivalence Classes are Disjoint:

$\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$

By Element in its own Equivalence Class:

$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$

By contrapositive of Equivalence Classes are Disjoint:

\(\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$


Sources