# Injection/Examples/Non-Injection/Arbitrary Mapping on Sets

Jump to navigation
Jump to search

## Example of Mapping which is Not an Injection

Let $A = \set {a, b, c, d}$.

Let $B = \set {1, 2, 3, 4, 5}$.

Let $f \subseteq {A \times B}$ be the mapping defined as:

- $f = \set {\tuple {a, 1}, \tuple {b, 4}, \tuple {c, 5}, \tuple {d, 4} }$

Then $f$ is not a injection.

## Proof

For $f$ to be an injection, it would be necessary that:

- $\forall x_1, x_2 \in A: \map f {x_1} = \map f {x_2} \implies x_1 = x_2$

By definition of the squaring operation, we have:

- $\map f b = \map f d$

But unless $b \ne d$.

Hence $f$ is not an injection.

$\blacksquare$

## Sources

- 1977: Gary Chartrand:
*Introductory Graph Theory*... (previous) ... (next): Appendix $\text{A}.4$: Functions