Renaming Mapping is Bijection

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $r: S / \mathcal R_f \to \Img f$ be the renaming mapping, defined as:

$r: S / \mathcal R_f \to \Img f: \map r {\eqclass x {\mathcal R_f} } = \map f x$

where:

$\mathcal R_f$ is the equivalence induced by the mapping $f$
$S / \mathcal R_f$ is the quotient set of $S$ determined by $\mathcal R_f$
$\eqclass x {\mathcal R_f}$ is the equivalence class of $x$ under $\mathcal R_f$.


The renaming mapping is a bijection.


Proof

Proof of Injectivity

To show that $r: S / \mathcal R_f \to \Img f$ is an injection:

\(\displaystyle \map r {\eqclass x {\mathcal R_f} }\) \(=\) \(\displaystyle \map r {\eqclass y {\mathcal R_f} }\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f x\) \(=\) \(\displaystyle \map f y\) Definition of Renaming Mapping
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(\mathcal R_f\) \(\displaystyle y\) Definition of Equivalence Relation Induced by Mapping
\(\displaystyle \leadsto \ \ \) \(\displaystyle \eqclass x {\mathcal R_f}\) \(=\) \(\displaystyle \eqclass y {\mathcal R_f}\) Definition of Equivalence Class


Thus $r: S / \mathcal R_f \to \Img f$ is an injection.

$\Box$


Proof of Surjectivity

To show that $r: S / \mathcal R_f \to \Img f$ is a surjection:

Note that for all mappings $f: S \to T$, $f: S \to \Img f$ is always a surjection from Surjection by Restriction of Codomain.


Thus by definition:

$\forall y \in \Img f: \exists x \in S: \map f x = y$

So:

\(\, \displaystyle \forall x \in S: \, \) \(\displaystyle \exists \eqclass x {\mathcal R_f}: x\) \(\in\) \(\displaystyle \eqclass x {\mathcal R_f}\) Equivalence Class is not Empty
\(\displaystyle \leadsto \ \ \) \(\, \displaystyle \forall y \in \Img f: \exists \eqclass x {\mathcal R_f} \in S / \mathcal R_f: \, \) \(\displaystyle \map f x\) \(=\) \(\displaystyle y\) Definition of Equivalence Relation Induced by Mapping
\(\displaystyle \leadsto \ \ \) \(\, \displaystyle \forall y \in \Img f: \exists \eqclass x {\mathcal R_f} \in S / \mathcal R_f: \, \) \(\displaystyle \map r {\eqclass x {\mathcal R_f} }\) \(=\) \(\displaystyle y\) Definition of Renaming Mapping


Thus $r: S / \mathcal R_f \to \Img f$ is a surjection.

$\Box$


As $r: S / \mathcal R_f \to \Img f$ is both an injection and a surjection, it is by definition a bijection.

$\blacksquare$


Different approaches

Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts considers the case where $r$ is an injection, but does not stress its bijective aspects from this particular perspective:

This type of factorization of mappings ... is particularly useful when the set of inverse images $\map {\alpha^{-1} } {a'}$ coincides with $\overline S$; for, in this case, the mapping $\overline a$ is 1-1.
Thus if $\overline a \overline \alpha = \overline b \overline \alpha$, then $a \alpha = b \alpha$ and $a \sim b$. Hence $\overline a = \overline b$. Thus we obtain here a factorization $\alpha = \nu \overline \alpha$ where $\overline \alpha$ is 1-1 onto $T$ and $\nu$ is the natural mapping.


Note that in the above, Jacobson uses:

$\alpha$ for $f$
$a'$ for the image of a representative element $a$ of $S$ under $\alpha$
$\overline S$ for $S / \mathcal R_f$
$\nu$ for the quotient mapping $q_{\mathcal R_f}: S \to S / \mathcal R_f$
$\overline a$ and $\overline b$ for representative elements of $\overline S$
$\overline \alpha$ for the renaming mapping $r$.


T.S. Blyth: Set Theory and Abstract Algebra takes the approach of deducing the existence of the mapping $r$, and then determining under which conditions it is either injective or surjective. From there, the surjective restriction of $r$ is taken, and $\mathcal R$ is then identified with the equivalence induced by $f$.

Hence the bijective nature of $r$ is constructed rather than deduced.


Sources