Cardinality of Set of Induced Equivalence Classes of Injection

From ProofWiki
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 an injection.

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


Proof

From Cardinality of Image of Injection we have that $\card {f \sqbrk S} = \card S$.

From the nature of an injection, for all $s \in S$, the $\mathcal R_f$-class of $s$ is a singleton.

Hence the result.

$\blacksquare$


Sources