description/proof of that finite composition of bijections is bijection, if codomains of constituent bijections equal domains of succeeding bijections
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 bijection.
- The reader admits the proposition that any finite composition of injections is an injection.
- The reader admits 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.
Target Context
- The reader will have a description and a proof of the proposition that any finite composition of bijections is a bijection, if the codomains of the constituent bijections equal the domains of the succeeding bijections.
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 bijections }\}\)
//
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 bijections }\}\)
//
2: Natural Language Description
For any sets, \(\{S_1, ..., S_n\}\), any sets, \(\{S'_1, ..., S'_n\}\), and any bijections, \(\{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 bijection.
3: Proof
Whole Strategy: Step 1: see that it is an injection; Step 2: see that it is a surjection; Step 3: conclude the proposition.
Step 1:
\(f_n \circ ... \circ f_1\) is an injection, by the proposition that any finite composition of injections is an injection.
Step 2:
\(f_n \circ ... \circ f_1\) is a surjection, by 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.
Step 3:
So, \(f_n \circ ... \circ f_1\) is a bijection.
4: Note
When \(S'_j \subset S_{j + 1}\) for a \(j\), \(f_n \circ ... \circ f_1\) is still valid, but is not any bijection. For example, let \(n = 2\), \(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 valid but is not surjective, because \(5\) is not mapped to from any element of \(S_1\).
