description/proof of that finite composition of injections is injection
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 injection.
Target Context
- The reader will have a description and a proof of the proposition that any finite composition of injections is an injection.
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 injections }\}\)
//
Statements:
\(\forall j \in \{1, ..., n - 1\} (S'_j \subseteq S_{j + 1})\)
\(\implies\)
\(f_n \circ ... \circ f_1: S_1 \to S'_n \in \{\text{ the injections }\}\)
//
2: Natural Language Description
For any sets, \(\{S_1, ..., S_n\}\), any sets, \(\{S'_1, ..., S'_n\}\), and any injections, \(\{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 an injection.
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.
Let us prove it inductively with respect to \(n\).
Step 1:
Let us suppose that \(n = 1\).
\(f_1\) is an injection.
Step 2:
Let us suppose that \(n = 2\).
Let \(p_1, p_2 \in S_1\) be any such that \(p_1 \neq p_2\). \(f_1 (p_1) \neq f_1 (p_2)\), by the injectiveness of \(f_1\). \(f_2 \circ f_1 (p_1) \neq f_2 \circ f_1 (p_2)\), by the injectiveness of \(f_2\). So, \(f_2 \circ f_1\) is an injection.
Step 3:
Let us suppose that the proposition holds for the \(n = 1, ..., n' - 1\) cases.
Let us suppose that \(n = n'\).
\(f_{n'} \circ ... \circ f_1 = f_{n'} \circ (f_{n' - 1} \circ ... \circ f_1)\). \(f_{n' - 1} \circ ... \circ f_1\) is an injection, by the induction hypothesis for the \(n = n' - 1\) case. \(f_{n'} \circ (f_{n' - 1} \circ ... \circ f_1)\) is an injection, by the induction hypothesis 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 an injection 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.
