692: Finite Composition of Surjections Is Surjection, if Codomains of Constituent Surjections Equal Domains of Succeeding Surjections

<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 surjections is surjection, if codomains of constituent surjections equal domains of succeeding surjections

---

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

---

Target Context

• The reader will have a description and a proof of 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.

---

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

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

---

2: Natural Language Description

For any sets, $\{S_1,...,S_n\}$, any sets, $\{S_1^{\prime },...,S_n^{\prime }\}$, and any surjections, $\{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 surjection.

---

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.

Step 1:

Let us suppose that $n=1$.

$f_1$ is a surjection.

Step 2:

Let us suppose that $n=2$.

For each $p\in S_2^{\prime }$, there is a $p^{\prime }\in S_2$ such that $f_2(p^{\prime })=p$, because $f_2$ is a surjection. As $p^{\prime }\in S_1^{\prime }=S_2$, there is a $p^{″}\in S_1$ such that $f_1(p^{″})=p^{\prime }$, because $f_1$ is a surjection. So, $f_2\circ f_1(p^{″})=p$. So, $f_2\circ f_1$ is a surjection.

Step 3:

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

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

$f_{n^{\prime }}\circ ...\circ f_1=f_{n^{\prime }}(f_{n^{\prime }-1}\circ ...\circ f_1)$. $f_{n^{\prime }-1}\circ ...\circ f_1$ is a surjection, by the induction hypothesis for the $n=n^{\prime }-1$ case. $f_{n^{\prime }}(f_{n^{\prime }-1}\circ ...\circ f_1)$ is a surjection, by the proposition 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 a surjection 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.

Compare with the proposition that a finite composition of surjections is not necessarily any surjection.

---

References

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