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, ..., 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 \subseteq S_{j + 1})\)
\(\lnot \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 \subseteq S_{j + 1}\), \(f_n \circ ... \circ f_1: S_1 \to S'_n\) is not necessarily any surjection.
3: Proof
Whole Strategy: Step 1: show a counterexample with the \(n = 2\) and \(S'_1 \subset S_2\) case.
Step 1:
It suffices to show a counterexample.
Let \(n = 2\). Let \(S_1 = \{1\}\), \(S'_1 = \{2\}\), \(S_2 = \{2, 3\}\), \(S'_2 = \{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.
