691: Finite Composition of Surjections Is Not Necessarily Surjection

<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 not necessarily surjection

---

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 a finite composition of surjections is not necessarily any surjection.

---

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 }\subseteq S_{j+1})$
$\mathrm{\neg }⟹$
$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 }\subseteq S_{j+1}$, $f_n\circ ...\circ f_1:S_1\to S_n^{\prime }$ is not necessarily any surjection.

---

3: Proof

Whole Strategy: Step 1: show a counterexample with the $n=2$ and $S_1^{\prime }\subset S_2$ case.

Step 1:

It suffices to show a counterexample.

Let $n=2$. Let $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 not surjective, because $5$ is not mapped to from any element of $S_1$.

---

4: Note

It may seem a trick, but we should remember that composition is possible without the codomain of the 1st map equaling the domain of the 2nd map.

Compare with the proposition that any finite composition of injections is an injection, which holds even when the codomain of the 1st map does not equal the domain of the 2nd map.

Compare with 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.

---

References

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