Equivalence of Definitions of Injection/Definition 1 iff Definition 1 a

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Injection are equivalent:

Definition 1

A mapping $f$ is an injection, or injective if and only if:

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


That is, an injection is a mapping such that the output uniquely determines its input.

Definition 1 a

$\forall x_1, x_2 \in \Dom f: x_1 \ne x_2 \implies \map f {x_1} \ne \map f {x_2}$


Proof

Let $f: S \to T$ be an injection by definition 1.

Thus:

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

Let $x_1 \ne x_2$.

Aiming for a contradiction, suppose that:

$\map f {x_1} = \map f {x_2}$

Then by definition 1:

$x_1 = x_2$

This contradicts the assumption that $x_1 \ne x_2$.

Thus by Proof by Contradiction:

$\forall x_1, x_2 \in S: x_1 \ne x_2 \implies \map f {x_1} \ne \map f {x_2}$

Thus $f$ is an injection by definition 1 a.

$\Box$


Let $f: S \to T$ be an injection by definition 1 a.

Thus:

$\forall x_1, x_2 \in S: x_1 \ne x_2 \implies \map f {x_1} \ne \map f {x_2}$

Let $\map f {x_1} = \map f {x_2}$.

Aiming for a contradiction, suppose that:

$x_1 \ne x_2$

Then by definition 1 a:

$\map f {x_1} \ne \map f {x_2}$

This contradicts the assumption that $\map f {x_1} = \map f {x_2}$.

Thus by Proof by Contradiction:

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

Thus $f$ is an injection by definition 1.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Equivalence_of_Definitions_of_Injection/Definition_1_iff_Definition_1_a&oldid=417484"