# Cardinality of Set of Induced Equivalence Classes of Surjection

Jump to navigation
Jump to search

## Theorem

Let $f: S \to T$ be a mapping.

Let $\mathcal R_f \subseteq S \times S$ be the relation induced by $f$:

- $\tuple {s_1, s_2} \in \mathcal R_f \iff \map f {s_1} = \map f {s_2}$

Let $f$ be a surjection.

Then there are $\card T$ different $\mathcal R_f$-classes.

## Proof

From the definition of a surjection:

- $\forall t \in T: \exists s \in S: \map f s = t$

Thus there are as many $\mathcal R_f$-classes of $f$ as there are elements of $T$.

Hence the result.

$\blacksquare$

## Sources

- 1978: Thomas A. Whitelaw:
*An Introduction to Abstract Algebra*... (previous) ... (next): Chapter $4$: Mappings: Exercise $10 \ \text{(i) (b)}$