749: Finite Composition of Bijections Is Bijection, if Codomains of Constituent Bijections Equal Domains of Succeeding Bijections

<The previous article in this series | The table of contents of this series | The next article in this series>

description/proof of that finite composition of bijections is bijection, if codomains of constituent bijections equal domains of succeeding bijections

---

Topics

About: set

---

The table of contents of this article

• Starting Context
• Target Context
• Orientation
• Main Body
• 1: Structured Description
• 2: Natural Language Description
• 3: Proof
• 4: Note

---

Starting Context

• The reader knows a definition of bijection.
• The reader admits the proposition that any finite composition of injections is an injection.
• The reader admits the proposition that any finite composition of surjections is a surjection, if the codomains of the constituent surjections equal the domains of the succeeding surjections.

---

Target Context

• The reader will have a description and a proof of the proposition that any finite composition of bijections is a bijection, if the codomains of the constituent bijections equal the domains of the succeeding bijections.

---

Orientation

There is a list of definitions discussed so far in this site.

There is a list of propositions discussed so far in this site.

---

Main Body

---

1: Structured Description

Here is the rules of Structured Description.

Entities:
$\{S_1,...,S_n\}$: $S_j\in \{\text{ the sets }\}$
$\{S_1^{\prime },...,S_n^{\prime }\}$: $S_j^{\prime }\in \{\text{ the sets }\}$
$\{f_1,...,f_n\}$: $f_j:S_j\to S_j^{\prime }$, $\in \{\text{ the bijections }\}$
//

Statements:
$\mathrm{\forall }j\in \{1,...,n-1\}(S_j^{\prime }=S_{j+1})$
$⟹$
$f_n\circ ...\circ f_1:S_1\to S_n^{\prime }\in \{\text{ the bijections }\}$
//

---

2: Natural Language Description

For any sets, $\{S_1,...,S_n\}$, any sets, $\{S_1^{\prime },...,S_n^{\prime }\}$, and any bijections, $\{f_1,...,f_n\}$, such that $f_j:S_j\to S_j^{\prime }$, if for each $j\in \{1,...,n-1\}$, $S_j^{\prime }=S_{j+1}$, $f_n\circ ...\circ f_1:S_1\to S_n^{\prime }$ is a bijection.

---

3: Proof

Whole Strategy: Step 1: see that it is an injection; Step 2: see that it is a surjection; Step 3: conclude the proposition.

Step 1:

$f_n\circ ...\circ f_1$ is an injection, by the proposition that any finite composition of injections is an injection.

Step 2:

$f_n\circ ...\circ f_1$ is a surjection, by the proposition that any finite composition of surjections is a surjection, if the codomains of the constituent surjections equal the domains of the succeeding surjections.

Step 3:

So, $f_n\circ ...\circ f_1$ is a bijection.

---

4: Note

When $S_j^{\prime }\subset S_{j+1}$ for a $j$, $f_n\circ ...\circ f_1$ is still valid, but is not any bijection. For example, let $n=2$, $S_1=\{1\}$, $S_1^{\prime }=\{2\}$, $S_2=\{2,3\}$, $S_2^{\prime }=\{4,5\}$, $f_1:1\mapsto 2$, $f_2:2\mapsto 4,3\mapsto 5$. $f_2\circ f_1$ is valid but is not surjective, because $5$ is not mapped to from any element of $S_1$.

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>