description/proof of that map is bijection iff it has inverse
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of bijection.
- The reader knows a definition of inverse of map.
Target Context
- The reader will have a description and a proof of the proposition that any map is a bijection if and only if it has an inverse.
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\)
\(\exists f^{- 1}: S_2 \to S_1 \in \{\text{ the inverses of } f \}\)
//
2: Note
In fact, if an \(f^{- 1}\) exists, \(f^{- 1}\) is the unique inverse, by the proposition that for any map, if an inverse exists, the inverse is the unique inverse.
3: Proof
Whole Strategy: Step 1: suppose that \(f\) is a bijection; Step 2: construct an \(f^{- 1}\); Step 3: suppose that \(f\) has an \(f^{- 1}\); Step 4: see that \(f\) is a bijections.
Step 1:
Let us suppose that \(f\) is a bijection.
Step 2:
Let us construct the \(f^{- 1}: S_2 \to S_1\) as this: for each \(s_2 \in S_2\), as \(f\) is a surjection, there is an \(s_1 \in S_1\) such that \(f (s_1) = s_2\), but as \(f\) is an injection, there is only \(1\) such an \(s_1 \in S_1\), so, let \(f^{- 1} (s_2) = s_1\).
\(f^{- 1} \circ f = id_{S_1}\), because for each \(s_1 \in S_1\), \(f^{- 1} \circ f (s_1) = s_1\), because \(f^{- 1} (f (s_1))\) is \(s'_1 \in S_1\) such that \(f (s'_1) = f (s_1)\), which implies that \(s'_1 = s_1\).
\(f \circ f^{- 1} = id_{S_2}\), because for each \(s_2 \in S_2\), \(f \circ f^{- 1} (s_2) = s_2\), because \(f^{- 1} (s_2)\) is \(s'_1 \in S_1\) such that \(f (s'_1) = s_2\), so, \(f \circ f^{- 1} (s_2) = f (s'_1) = s_2\).
So, \(f^{- 1}\) is an inverse of \(f\), in fact, \(f^{- 1}\) is the inverse of \(f\).
Step 3:
Let us suppose that \(f\) has an inverse, \(f^{- 1}: S_2 \to S_1\).
\(f\) is an injection, because otherwise, there would be some \(s_1, s'_1 \in S_1\) such that \(s_1 \neq s'_1\) and \(f (s_1) = f (s'_1)\), but \(s_1 = id_{S_1} (s_1) = f^{- 1} \circ f (s_1) = f^{- 1} \circ f (s'_1) = id_{S_1} (s'_1) = s'_1\), a contradiction against \(s_1 \neq s'_1\).
\(f\) is a surjection, because otherwise, there would an \(s_2 \in S_2\) that was not mapped to by \(f\), but \(s_2 = id_{S_2} (s_2) = f \circ f^{- 1} (s_2) = f (f^{- 1} (s_2))\), so, \(f^{- 1} (s_2) \in S_1\) would be mapped to \(s_2\), a contradiction against that \(s_2\) is not mapped to by \(f\).
So, \(f\) is a bijection.
