Composition of 3 Mappings where Pairs of Mappings are Bijections

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $A$, $B$, $C$ and $D$ be sets.

Let:

$f: A \to B$
$g: B \to C$
$h: C \to D$

be mappings.

Let $g \circ f$ and $h \circ g$ be bijections.


Then $f$, $g$ and $h$ are all bijections.


Proof

We note that both $g \circ f$ and $h \circ g$ are both injections and surjections by definition of bijection.


First it is shown that $g$ is a bijection.

We are given that:

$g \circ f$ is a bijection.

From Injection if Composite is Injection it follows that $f$ is an injection.

From Surjection if Composite is Surjection it follows that $g$ is a surjection.


Similarly, we are given that:

$h \circ g$ is a bijection.

From Injection if Composite is Injection it follows that $g$ is an injection.

From Surjection if Composite is Surjection it follows that $h$ is a surjection.


Thus we have that $g$ is a bijection.

$\Box$


Next it is shown that $f$ is a bijection.

Aiming for a contradiction, suppose $f$ is not a surjection.

Then:

$\exists y \in B: \neg \exists x \in A: \map f x = y$

But then $g$ is a surjection and so:

$\forall z \in C: \exists y \in B: z = \map g y$

and so:

$\exists z \in C: \neg \exists x \in A: \map g {\map f x} = z$

and so $g \circ f$ is not a surjection.

This contradicts our assertion that $g \circ f$ is a bijection and so a surjection.

Hence by Proof by Contradiction $f$ must be a surjection

So $f$ is both an injection and a surjection, and so a bijection.

$\Box$


Next it is shown that $h$ is a bijection.

Aiming for a contradiction, suppose $h$ is not an injection.

Then:

$\exists y_1, y_2 \in C: \map h {y_1} = \map h {y_2}$

But then $g$ is a bijection and so:

$\exists x_1, x_2 \in B: y_1 = \map g {x_1} \ne \map g {x_2} = y_2$

and so:

$\exists x_1, x_2 \in B: \map h {\map g {x_1} } = \map h {\map g {x_2} }$

and so $h \circ g$ is not an injection.

This contradicts our assertion that $h \circ g$ is a bijection and so an injection.

Hence by Proof by Contradiction $h$ must be an injection

So $h$ is both an injection and a surjection, and so a bijection.

$\Box$


Hence the result.

$\blacksquare$


Sources