description/proof of that maps composition preimage is composition of map preimages in reverse order
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of composition of maps.
Target Context
- The reader will have a description and a proof of the proposition that for any maps composition, the preimage under the composition is the composition of the map preimages in the reverse order.
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\}\): \(\subseteq \{\text{ the sets }\}\)
\(\{S_2, ..., S_{n + 1}\}\): \(\subseteq \{\text{ the sets }\}\), such that \(\forall j \in \{2, ..., n\} (S_j \subseteq S'_j)\)
\(\{f_1, ..., f_n\}\): \(f_j: S'_j \to S_{j + 1}\), \(\in \{\text{ the maps }\}\)
\(f_n \circ ... \circ f_1\): \(S'_1 \to S_{n + 1}, s \mapsto f_n (f_{n - 1} (... (f_1 (s)) ... ))\)
\(S\): \(\subseteq S_{n + 1}\)
//
Statements:
\((f_n \circ ... \circ f_1)^{-1} (S) = f_1^{-1} (f_2^{-1} (... f_{n - 1}^{-1} (f_n^{-1} (S) \cap S_n) ...) \cap S_2))\)
//
2: Note
"\(\cap S_j\)" s are added because for example, \(f_{n - 1}^{-1} (f_n^{-1} (S))\) would not necessarily make sense, because \(f_n^{-1} (S) \subseteq S'_n\) but the codomain of \(f_{n - 1}\) is \(S_n \subseteq S'_n\).
3: Proof
Whole Strategy: prove it inductively; Step 1: see it for \(n = 2\); Step 2: suppose that it holds for any \(n\) and see that it holds for \(n + 1\); Step 3: conclude the proposition.
Step 1:
Let \(n = 2\).
Let us see that \((f_2 \circ f_1)^{-1} (S) = f_1^{-1} (f_2^{-1} (S) \cap S_2)\) holds.
Let \(p \in (f_2 \circ f_1)^{-1} (S)\) be any.
\(f_2 \circ f_1 (p) \in S\).
\(f_1 (p) \in f_2^{-1} (S)\), but as \(f_1 (p) \in S_2\), \(f_1 (p) \in f_2^{-1} (S) \cap S_2\).
So, \(p \in f_1^{-1} (f_2^{-1} (S) \cap S_2)\).
Let \(p \in f_1^{-1} (f_2^{-1} (S) \cap S_2)\) be any.
\(f_1 (p) \in f_2^{-1} (S) \cap S_2\).
\(f_2 \circ f_1 (p) \in S\).
So, \(p \in (f_2 \circ f_1)^{-1} (S)\).
Step 2:
Let us suppose that \((f_n \circ ... \circ f_1)^{-1} (S) = f_1^{-1} (f_2^{-1} (... f_{n - 1}^{-1} (f_n^{-1} (S) \cap S_n) ...) \cap S_2))\) holds for any \(n\).
Let us see that \((f_{n + 1} \circ ... \circ f_1)^{-1} (S) = f_1^{-1} (f_2^{-1} (... f_n^{-1} (f_{n + 1}^{-1} (S) \cap S_{n + 1}) ...) \cap S_2))\).
\(f_{n + 1} \circ ... \circ f_1 = f_{n + 1} (f_n \circ ... \circ f_1)\).
So, by Step 1, \((f_{n + 1} \circ ... \circ f_1)^{-1} (S) = (f_n \circ ... \circ f_1)^{-1} (f_{n + 1}^{-1} (S) \cap S_{n + 1})\).
By the induction hypothesis, \(= f_1^{-1} (f_2^{-1} (... f_{n - 1}^{-1} (f_n^{-1} (f_{n + 1}^{-1} (S) \cap S_{n + 1}) \cap S_n) ...) \cap S_2))\), which is exactly what we needed to see.
Step 3:
So, by the induction principle, the proposition holds.
