Bijection iff Left and Right Inverse

Theorem

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

$f$ is a bijection iff:

• $\exists g_1: T \to S: g_1 \circ f = I_S$
• $\exists g_2: T \to S: f \circ g_2 = I_T$

where both $g_1$ and $g_2$ are mappings.

It also follows that it is necessarily the case that $g_1 = g_2$ for such to be possible.

Corollary

Let $f: S \to T$ and $g: T \to S$ be mappings such that:

• $g \circ f = I_S$
• $f \circ g = I_T$

Then both $f$ and $g$ are bijections.

Proof 1

Necessary Condition

Suppose:

• $\exists g_1: T \to S: g_1 \circ f = I_S$;
• $\exists g_2: T \to S: f \circ g_2 = I_T$.

From Injection iff Left Inverse, it follows that $f$ is an injection.

From Surjection iff Right Inverse, it follows that $f$ is a surjection.

So $f$ is both an injection and a surjection and, by definition, therefore also a bijection.

Sufficient Condition

Suppose $f$ is a bijection.

Then it is both an injection and a surjection, thus both the described $g_1$ and $g_2$ must exist from Injection iff Left Inverse and Surjection iff Right Inverse.

Now we need to show that $g_1 = g_2$.

Thus:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle g_2\)	\(=\)	\(\displaystyle I_S \circ g_2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Identity Mapping
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({g_1 \circ f}\right) \circ g_2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	We have proved existence of such a $g_1$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle g_1 \circ \left({f \circ g_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Composition of Mappings Associative
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle g_1 \circ I_T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	We have proved that $g_2$ has this proeprty
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle g_1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Identity Mapping

$\blacksquare$

Proof 2

Necessary Condition

Suppose:

• $\exists g_1: T \to S: g_1 \circ f = I_S$
• $\exists g_2: T \to S: f \circ g_2 = I_T$.

We have that the Identity Mapping is a Bijection, thus $I_S$ and $I_T$ are both bijections.

From Injection if Composite is an Injection, if $I_S = g_1 \circ f$ is an injection, then so is $f$.

From Surjection if Composite is a Surjection, if $I_T = f \circ g_2$ is a surjection, then so is $f$.

So $f$ is both an injection and a surjection and, by definition, therefore also a bijection.

Now we need to show that $g_1 = g_2$.

Thus:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle g_2\)	\(=\)	\(\displaystyle I_S \circ g_2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Identity Mapping
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({g_1 \circ f}\right) \circ g_2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by hypothesis
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle g_1 \circ \left({f \circ g_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Composition of Mappings Associative
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle g_1 \circ I_T\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	by hypothesis
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle g_1\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of Identity Mapping

$\Box$

Sufficient Condition

Suppose $f$ is a bijection.

From Bijection iff Inverse is Bijection and Bijection Composite with Inverse, it is shown that the inverse mapping $f^{-1}$ such that:

• $f^{-1} \circ f = I_S$
• $f \circ f^{-1} = I_T$

is a bijection.

$\blacksquare$

Proof 3

From Inverse Relation is Left and Right Inverse iff Bijection:

Let $\mathcal R \subseteq S \times T$ be a relation on a cartesian product $S \times T$.

Then $\mathcal R$ is a bijection iff:

• $\mathcal R^{-1} \circ \mathcal R = I_S$ and
• $\mathcal R \circ \mathcal R^{-1} = I_T$

where $\circ$ denotes composition of relations.

As a mapping is a relation, the result follows.

$\blacksquare$

Proof of Corollary

Suppose we have such mappings $f$ and $g$ with the given properties.

From the main result, we have that $f$ is a bijection, by considering $g = g_1$ and $g = g_2$.

It directly follows that by setting $g = f, f = g_1, f = g_2$, the same result can be used the other way about.

$\blacksquare$

Also see

• Two-Sided Inverse

As a result of refactoring in progress:

• Left and Right Inverse Mappings Implies Bijection
• Left and Right Inverses of Mapping are Inverse Mapping

Sources

• Nathan Jacobson: Lectures in Abstract Algebra: I. Basic Concepts (1951): Introduction $\S 2$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.7$: Proposition $\text{A}.7.4$