690: Finite Composition of Injections Is Injection

<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 injections is injection

---

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 injection.

---

Target Context

• The reader will have a description and a proof of the proposition that any finite composition of injections is an injection.

---

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 injections }\}$
//

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

---

2: Natural Language Description

For any sets, $\{S_1,...,S_n\}$, any sets, $\{S_1^{\prime },...,S_n^{\prime }\}$, and any injections, $\{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 }\subseteq S_{j+1}$, $f_n\circ ...\circ f_1:S_1\to S_n^{\prime }$ is an injection.

---

3: Proof

Whole Strategy: prove it inductively with respect to $n$; Step 1: prove it for the $n=1$ case; Step 2: prove it for the $n=2$ case; Step 3: suppose it for the $n=1,...,n^{\prime }-1$ cases, and prove it for the $n=n^{\prime }$ case.

Let us prove it inductively with respect to $n$.

Step 1:

Let us suppose that $n=1$.

$f_1$ is an injection.

Step 2:

Let us suppose that $n=2$.

Let $p_1,p_2\in S_1$ be any such that $p_1\ne p_2$. $f_1(p_1)\ne f_1(p_2)$, by the injectiveness of $f_1$. $f_2\circ f_1(p_1)\ne f_2\circ f_1(p_2)$, by the injectiveness of $f_2$. So, $f_2\circ f_1$ is an injection.

Step 3:

Let us suppose that the proposition holds for the $n=1,...,n^{\prime }-1$ cases.

Let us suppose that $n=n^{\prime }$.

$f_{n^{\prime }}\circ ...\circ f_1=f_{n^{\prime }}\circ (f_{n^{\prime }-1}\circ ...\circ f_1)$. $f_{n^{\prime }-1}\circ ...\circ f_1$ is an injection, by the induction hypothesis for the $n=n^{\prime }-1$ case. $f_{n^{\prime }}\circ (f_{n^{\prime }-1}\circ ...\circ f_1)$ is an injection, by the induction hypothesis for the $n=2$ case.

---

4: Note

Do we really need Step 2? I think so: one may be tempted to do without Step 2 and just claim that $f_{n^{\prime }}\circ (f_{n^{\prime }-1}\circ ...\circ f_1)$ is an injection just because the proposition is suppose to hold for the $n=1,...,n^{\prime }-1$ cases, but when $n^{\prime }=2$, what is supposed is just the $n=1=n^{\prime }-1$ case.

---

References

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