Equivalence of Definitions of Bijection
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:
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
- $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:
By definition of surjection:
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:
defines an injection
and:
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: