description/proof of that map is bijection iff preimage of codomain point is 1 point subset
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
Starting Context
- The reader knows a definition of bijection.
Target Context
- The reader will have a description and a proof of the proposition that any map is a bijection iff the preimage of each codomain point is a 1 point subset.
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\): \(\in \{\text{ the sets }\}\)
\(S_2\): \(\in \{\text{ the sets }\}\)
\(f\): \(: S_1 \to S_2\)
//
Statements:
\(f \in \{\text{ the bijections }\}\)
\(\iff\)
\(\forall s \in S_2 (\vert f^{-1} (s) \vert = 1)\), where \(\vert \bullet \vert\) is the cardinality of the set
//
2: Natural Language Description
For any sets, \(S_1, S_2\), and any map, \(f: S_1 \to S_2\), \(f\) is a bijection if and only for each \(s \in S_2\), \(\vert f^{-1} (s) \vert = 1\).
3: Proof
Whole Strategy: Step 1: suppose that \(f\) is a bijection and see that \(\vert f^{-1} (s) \vert = 1\); Step 2: suppose that \(\vert f^{-1} (s) \vert = 1\) and see that \(f\) is a bijection.
Step 1:
Let us suppose that \(f\) is a bijection.
Let \(s \in S_2\) be any.
\(f^{-1} (s) \neq \emptyset\), because as \(f\) is surjective, there is at least 1 point in \(S_1\) that (the point) is mapped to \(s\), which means that \(0 \lt \vert f^{-1} (s) \vert\). \(\vert f^{-1} (s) \vert \lt 2\), because if \(2 \le \vert f^{-1} (s) \vert\), there would be some \(s_1, s_2 \in S_1\) such that \(f (s_1) = f (s_2) = s\), a contradiction against \(f\)'s being injective. So, \(0 \lt \vert f^{-1} (s) \vert \lt 2\), which implies that \(\vert f^{-1} (s) \vert = 1\).
Step 2:
Let us suppose that for each \(s \in S_2\), \(\vert f^{-1} (s) \vert = 1\).
\(f\) is surjective, because there is at least 1 point in \(S_1\) that (the point) is mapped to \(s\). \(f\) is injective, because if there were some \(s_1, s_2 \in S_1\) such that \(f (s_1) = f (s_2)\), \(2 \le \vert f^{-1} (f (s_1) ) \vert\), a contradiction against \(\vert f^{-1} (s) \vert = 1\) for \(s = f (s_1) = f (s_2)\). So, \(f\) is a bijection.
