description/proof of that for permutation of finite sequence, sign of inverse of permutation is sign of permutation
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of permutation of sequence.
- The reader admits the proposition that any map is a bijection if and only if it has an inverse.
- The reader admits the proposition that the inverse of any bijection is a bijection.
Target Context
- The reader will have a description and a proof of the proposition that for any permutation of any finite sequence, the sign of the inverse of the permutation is the sign of the permutation.
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\): \(\in \{\text{ the finite subsets of } \mathbb{N}\}\)
\(f\): \(\in \{\text{ the sequences from } S\}\)
\(\sigma\): \(: S \to S\), \(\in \{\text{ the permutations of } f\}\)
//
Statements:
\(\sigma^{- 1} \in \{\text{ the permutations of } f\}\)
\(\land\)
\(sgn (\sigma) = sgn (\sigma^{- 1})\)
//
2: Proof
Whole Strategy: Step 1: see that \(\sigma^{- 1}\) is a bijection; Step 2: see that there is a bijection from \(\{(s_1, s_2) \in \{\text{ the ordered pairs of } S\} \vert s_1 \lt s_2 \land \sigma^{- 1} (s_2) \lt \sigma^{- 1} (s_1)\}\) to \(\{(s_1, s_2) \in \{\text{ the ordered pairs of } S\} \vert s_1 \lt s_2 \land \sigma (s_2) \lt \sigma (s_1)\}\).
Step 1:
\(\sigma\) has indeed \(\sigma^{- 1}: S \to S\), by the proposition that any map is a bijection if and only if it has an inverse.
\(\sigma^{- 1}\) is a bijection, by the proposition that the inverse of any bijection is a bijection.
So, \(\sigma^{- 1}\) is a permutation.
Step 2:
\(sgn (\sigma^{- 1})\) is determined by the cardinality of \(\{(s_1, s_2) \in \{\text{ the ordered pairs of } S\} \vert s_1 \lt s_2 \land \sigma^{- 1} (s_2) \lt \sigma^{- 1} (s_1)\}\) and \(sgn (\sigma)\) is determined by the cardinality of \(\{(s_1, s_2) \in \{\text{ the ordered pairs of } S\} \vert s_1 \lt s_2 \land \sigma (s_2) \lt \sigma (s_1)\}\).
Let us see that \(f: \{(s_1, s_2) \in \{\text{ the ordered pairs of } S\} \vert s_1 \lt s_2 \land \sigma^{- 1} (s_2) \lt \sigma^{- 1} (s_1)\} \to \{(s_1, s_2) \in \{\text{ the ordered pairs of } S\} \vert s_1 \lt s_2 \land \sigma (s_2) \lt \sigma (s_1)\}, (s_1, s_2) \mapsto (\sigma^{- 1} (s_2), \sigma^{- 1} (s_1))\) is a bijection.
\(f\) is indeed into \(\{(s_1, s_2) \in \{\text{ the ordered pairs of } S\} \vert s_1 \lt s_2 \land \sigma (s_2) \lt \sigma (s_1)\}\), because \(\sigma^{- 1} (s_2) \lt \sigma^{- 1} (s_1)\) and \((\sigma (\sigma^{- 1} (s_1)) = s_1 \lt s_2 = \sigma (\sigma^{- 1} (s_2))\).
\(f\) is an injection, obviously.
\(f\) is a surjection, because for each \((s_1, s_2) \in \{(s_1, s_2) \in \{\text{ the ordered pairs of } S\} \vert s_1 \lt s_2 \land \sigma (s_2) \lt \sigma (s_1)\}\), \((\sigma (s_2), \sigma (s_1)) \in \{(s_1, s_2) \in \{\text{ the ordered pairs of } S\} \vert s_1 \lt s_2 \land \sigma^{- 1} (s_2) \lt \sigma^{- 1} (s_1)\}\), because \(\sigma (s_2) \lt \sigma (s_1)\) and \(\sigma^{- 1} (\sigma (s_1)) = s_1 \lt s_2 = \sigma^{- 1} (\sigma (s_2))\), and \(f ((\sigma (s_2), \sigma (s_1))) = (\sigma^{- 1} (\sigma (s_1)), \sigma^{- 1} (\sigma (s_2))) = (s_1, s_2)\).
So, \(f\) is a bijection.
So, \(\vert \{(s_1, s_2) \in \{\text{ the ordered pairs of } S\} \vert s_1 \lt s_2 \land \sigma^{- 1} (s_2) \lt \sigma^{- 1} (s_1)\} \vert = \vert \{(s_1, s_2) \in \{\text{ the ordered pairs of } S\} \vert s_1 \lt s_2 \land \sigma (s_2) \lt \sigma (s_1)\} \vert\).
That implies that \(sgn (\sigma) = sgn (\sigma^{- 1})\).
