Cardinality of Set of Induced Equivalence Classes of Injection
Jump to navigation
Jump to search
Theorem
Let $f: S \to T$ be a mapping.
Let $\RR_f \subseteq S \times S$ be the relation induced by $f$:
- $\tuple {s_1, s_2} \in \RR_f \iff \map f {s_1} = \map f {s_2}$
Let $f$ be an injection.
Then there are $\card S$ different $\RR_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 $\RR_f$-class of $s$ is a singleton.
Hence the result.
$\blacksquare$
Sources
- 1978: Thomas A. Whitelaw: An Introduction to Abstract Algebra ... (previous) ... (next): Chapter $4$: Mappings: Exercise $10 \ \text{(i) (a)}$