Equivalence of Definitions of Injection

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}$

Definition 2

An injection is a relation which is both one-to-one and left-total.

Definition 3

Let $f$ be a mapping.

Then $f$ is an injection if and only if:

$f^{-1} {\restriction_{\Img f} }: \Img f \to \Dom f$ is a mapping

where $f^{-1} {\restriction_{\Img f} }$ is the restriction of the inverse of $f$ to the image set of $f$.

Definition 4

Let $f$ be a mapping.

$f$ is an injection if and only if:

$\forall y \in \Img f: \card {\map {f^{-1} } y} = \card {\set {f^{-1} \sqbrk {\set y} } } = 1$

where:

$\Img f$ denotes the image set of $f$
$\card {\, \cdot \,}$ denotes the cardinality of a set
$\map {f^{-1} } y$ is the preimage of $y$
$f^{-1} \sqbrk {\set y}$ is the preimage of the subset $\set y \subseteq \Img f$.

Definition 5

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

Then $f$ is an injection if and only if:

$\exists g: T \to S: g \circ f = I_S$

where $g$ is a mapping.


That is, if and only if $f$ has a left inverse.

Definition 6

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

Then $f$ is an injection if and only if $f$ is left cancellable:

$\forall X: \forall g_1, g_2: X \to S: f \circ g_1 = f \circ g_2 \implies g_1 = g_2$

where $g_1$ and $g_2$ are arbitrary mappings from an arbitrary set $X$ to the domain $S$ of $f$.


Proof

Definition $1$ iff Definition $1 \ \text{a}$

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$


Definition $1$ iff Definition $2$

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

Thus:

$(1): \quad \forall x_1, x_2 \in S: f \left({x_1}\right) = f \left({x_2}\right) \implies x_1 = x_2$

Let $y \in T: y = f \left({x_1}\right) = f \left({x_2}\right)$.

Thus $(1)$ can be rewritten in the language of relations as:

$\forall x_1, x_2 \in S: \left({x_1, y}\right) \in f \land f \left({x_2, y}\right) \in f \implies x_1 = x_2$

So, by definition, $f$ is a one-to-many relation.


By definition, $f$ is also mapping.

So, by definition, $f$ is a relation which is both many-to-one and left-total.

A relation which is both many-to-one and one-to-many is by definition a one-to-one relation.

Thus $f$ is a relation which is one-to-one and left-total.

So $f$ is an injection by definition 2.

$\Box$


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

That is, $f$ is a relation which is one-to-one and left-total.

A one-to-one relation is a relation which is both many-to-one and one-to-many.

So $f$ is a relation which is both many-to-one and left-total.

Thus $f$ is a mapping which is one-to-many:

$\forall x_1, x_2 \in S: \left({x_1, y}\right) \in f \land f \left({x_2, y}\right) \in f \implies x_1 = x_2$

Setting $y = f \left({x_1}\right) = f \left({x_2}\right)$:

$\forall x_1, x_2 \in S: f \left({x_1}\right) = f \left({x_2}\right) \implies x_1 = x_2$

So $f$ is an injection by definition 1.

$\blacksquare$


Definition $1$ iff Definition $3$

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$

First we note that:

$t \in \Img f \implies \exists x \in \Dom f: \map f x = t$

thus fulfilling the condition for $f^{-1} {\restriction_{\Img f} }$ to be left-total.


Now let:

$t \in \Img f: \tuple {t, y}, \tuple {t, z} \in f^{-1}$

Thus:

\(\displaystyle \tuple {t, y}, \tuple {t, z}\) \(\in\) \(\displaystyle f^{-1} {\restriction_{\Img f} }\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {y, t}, \tuple {z, t}\) \(\in\) \(\displaystyle f\) Definition of Inverse of Mapping
\(\displaystyle \leadsto \ \ \) \(\displaystyle \map f y = t\) \(=\) \(\displaystyle \map f z\) Equality of Elements in Range of Mapping
\(\displaystyle \leadsto \ \ \) \(\displaystyle y\) \(=\) \(\displaystyle z\) as $f$ is injective


So by the definition of mapping, $f^{-1} {\restriction_{\Img f} }$ is a mapping.

So $f$ is an injection by definition 3.

$\Box$


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

Then:

$f^{-1} {\restriction_{\Img f} }: \Img f \to \Dom f$ is a mapping

where $f^{-1} {\restriction_{\Img f} }$ is the restriction of the inverse of $f$ to the image set of $f$.


We need to show that:

$\forall x, z \in \Dom f: \map f x = \map f z \implies x = z$

So, pick any $x, z \in \Dom f$ such that:

$\map f x = \map f z$

Then:

\(\displaystyle \map f x\) \(=\) \(\displaystyle \map f z\)
\(\displaystyle \leadsto \ \ \) \(\displaystyle \exists y \in \Dom f: \tuple {x, y}, \tuple {z, y}\) \(\in\) \(\displaystyle f\) Definition of Mapping
\(\displaystyle \leadsto \ \ \) \(\displaystyle \tuple {y, x}, \tuple {y, z}\) \(\in\) \(\displaystyle f^{-1} {\restriction_{\Img f} }\) Definition of Inverse of Mapping
\(\displaystyle \leadsto \ \ \) \(\displaystyle x\) \(=\) \(\displaystyle z\) as it is specified that $f^{-1} {\restriction_{\Img f} }$ is a mapping


So $f$ is an injection by definition 1.

$\blacksquare$


Definition $1$ iff Definition $4$

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$


Aiming for a contradiction, suppose $f^{-1} \sqbrk {\set y}$ has more than one element.

That is:

$\exists y \in T: x_1, x_2 \in \map {f^{-1} } y, x_1 \ne x_2$

Then we have:

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

but:

$x_1 \ne x_2$

This contradicts our initial hypothesis that $f$ is an injection by definition 1.

From this contradiction it follows that $f^{-1} \sqbrk {\set y}$ has no more than one element.

That is, $f$ is an injection by definition 4.

$\Box$


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

That is, let $\map {f^{-1} } y$ be a singleton for all $y \in T$.

Aiming for a contradiction, suppose it is not the case that:

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

Then by definition:

$\exists x_1, x_2 \in S, x_1 \ne x_2: \map f {x_1} = \map f {x_2} = y$

By definition of preimage of $y \in T$:

$x_1 \in \map {f^{-1} } y, x_2 \in \map {f^{-1} } y$

and so: $\set {x_1, x_2} \subseteq \map {f^{-1} } y$

Thus $\map {f^{-1} } y$ has more than one element for at least one $y \in T$.

This contradicts our initial hypothesis that $f$ is an injection by definition 4.

Thus:

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

So $f$ is an injection by definition 1.

$\blacksquare$


Definition $1$ iff Definition $5$

This is demonstrated in Injection iff Left Inverse.

$\blacksquare$


Definition $1$ iff Definition $6$

This is demonstrated in Injection iff Left Cancellable.

$\blacksquare$