Equivalence of Definitions of Bijection

From ProofWiki
Jump to: navigation, search

Theorem

The following definitions of the concept of Bijection are equivalent:

Definition 1

A mapping $f: S \to T$ is a bijection if and only if both:

$(1): \quad f$ is an injection

and:

$(2): \quad f$ is a surjection.

Definition 2

A mapping $f: S \to T$ is a bijection if and only if:

$f$ has both a left inverse and a right inverse.

Definition 3

A mapping $f: S \to T$ is a bijection if and only if:

the inverse $f^{-1}$ of $f$ is a mapping from $T$ to $S$.

Definition 4

A mapping $f \subseteq S \times T$ is a bijection if and only if:

for each $y \in T$ there exists one and only one $x \in S$ such that $\tuple {x, y} \in f$.

Definition 5

A relation $f \subseteq S \times T$ is a bijection if and only if:

$(1): \quad$ for each $x \in S$ there exists one and only one $y \in T$ such that $\tuple {x, y} \in f$
$(2): \quad$ for each $y \in T$ there exists one and only one $x \in S$ such that $\tuple {x, y} \in f$.


Proof

Definition 1 iff Definition 2

From Injection iff Left Inverse, $f$ is an injection if and only if $f$ has a left inverse mapping.

From Surjection iff Right Inverse, $f$ is a surjection if and only if $f$ has a right inverse mapping.

Putting these together, it follows that:

$f$ is both an injection and a surjection

if and only if:

$f$ has both a left inverse and a right inverse.

$\Box$


Definition 1 iff Definition 3

This is demonstrated in Mapping is Injection and Surjection iff Inverse is Mapping.

$\Box$


Definition 1 iff Definition 4

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

Then by definition:

$f$ is an injection
$f$ is a surjection


By definition of injection:

every element of $T$ is the image of at most $1$ element of $S$.

By definition of surjection:

every element of $T$ is the image of at least $1$ element of $S$.


So:

for each $y \in T$ there exists one and only one $x \in S$ such that $\tuple {x, y} \in f$.

Thus $f$ is a bijection by definition 4.

$\Box$


Let $f: S \to T$ be a bijection by definition 4.

Then by definition:

for each $y \in T$ there exists one and only one $x \in S$ such that $\tuple {x, y} \in f$.


But:

every element of $T$ is the image of at most $1$ element of $S$

defines an injection

and:

every element of $T$ is the image of at least $1$ element of $S$

defines a surjection.


From Injection iff Left Inverse, $f$ is an injection if and only if $f$ has a left inverse mapping.

From Surjection iff Right Inverse, $f$ is a surjection if and only if $f$ has a right inverse mapping.

Putting these together, it follows that:

$f$ is an injection
$f$ is a surjection

Thus $f$ is a bijection by definition 1.

$\Box$


Definition 3 iff Definition 4

Necessary Condition

Let $f^{-1}: T \to S$ be a mapping.

Then by definition:

$\forall y \in T: \exists x \in S: \tuple {y, x} \in f^{-1}$

Thus for all $y \in T$ there exists at least one $x \in S$ such that $\tuple {y, x} \in f^{-1}$.


Also by definition of mapping:

$\tuple {x_1, y} \in f^{-1} \land \tuple {x_2, y} \in f^{-1} \implies x_1 = x_2$

Thus for all $y \in T$ there exists at most one $x \in S$ such that $\tuple {y, x} \in f^{-1}$.


Hence it has been demonstrated that $y \in T$ there exists a unique $x \in S$ such that $\tuple {y, x} \in f^{-1}$.

$\Box$


Sufficient Condition

Let $f$ be such that for all $y \in T$ there exists a unique $x \in S$ such that $\tuple {y, x} \in f^{-1}$.

Then by definition $f^{-1}$ is a mapping.

$\Box$


Definition 3 iff Definition 5

Necessary Condition

Let $f: S \to T$ be a mapping such that $f^{-1}: T \to S$ is also a mapping.

Then as $f$ is a mapping:

for all $x \in S$ there exists a unique $y \in T$ such that $\tuple {x, y} \in f$.

Similarly, as $f^{-1}$ is also a mapping:

for all $y \in T$ there exists a unique $x \in S$ such that $\tuple {y, x} \in f^{-1}$.

$\Box$


Sufficient Condition

Let $f \subseteq S \times T$ be a relation such that:

$(1): \quad$ for each $x \in S$ there exists one and only one $y \in T$ such that $\tuple {x, y} \in f$
$(2): \quad$ for each $y \in T$ there exists one and only one $x \in S$ such that $\tuple {x, y} \in f$.

Then by definition:

from $(1)$, $f$ is a mapping.
from $(2)$, $f^{-1}$ is a mapping.