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, ..., S'_n\}\): \(S'_j \in \{\text{ the sets }\}\)
\(\{f_1, ..., f_n\}\): \(f_j: S_j \to S'_j\), \(\in \{\text{ the surjections }\}\)
//
Statements:
\(\forall j \in \{1, ..., n - 1\} (S'_j = S_{j + 1})\)
\(\implies\)
\(f_n \circ ... \circ f_1: S_1 \to S'_n \in \{\text{ the surjections }\}\)
//
2: Natural Language Description
For any sets, \(\{S_1, ..., S_n\}\), any sets, \(\{S'_1, ..., S'_n\}\), and any surjections, \(\{f_1, ..., f_n\}\), such that \(f_j: S_j \to S'_j\), if for each \(j \in \{1, ..., n - 1\}\), \(S'_j = S_{j + 1}\), \(f_n \circ ... \circ f_1: S_1 \to S'_n\) 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' - 1\) cases, and prove it for the \(n = n'\) 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\), there is a \(p' \in S_2\) such that \(f_2 (p') = p\), because \(f_2\) is a surjection. As \(p' \in S'_1 = S_2\), there is a \(p'' \in S_1\) such that \(f_1 (p'') = p'\), 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' - 1\).
Let us suppose that \(n = n'\).
\(f_{n'} \circ ... \circ f_1 = f_{n'} (f_{n' - 1} \circ ... \circ f_1)\). \(f_{n' - 1} \circ ... \circ f_1\) is a surjection, by the induction hypothesis for the \(n = n' - 1\) case. \(f_{n'} (f_{n' - 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'} \circ (f_{n' - 1} \circ ... \circ f_1)\) is a surjection just because the proposition is suppose to hold for the \(n = 1, ..., n' - 1\) cases, but when \(n' = 2\), what is supposed is just the \(n = 1 = n' - 1\) case.
Compare with the proposition that a finite composition of surjections is not necessarily any surjection.
