Proof of Extending a Permutation of [n-1] to a Permutation of [n] with a Prescribed Value, and Its Sign

Each result cited is universally quantified over the data in its own statement.

Conventions. By The Index Map Skipping One Element of [n] §difference, $m\in\mathbb{N}$ and $m+1=n$. For $q\in\{m,n\}$, the elements of $S_{q}$ are the bijections $[q]\to[q]$ by Permutations of a Set and the Set of Permutations of [n] §membership, and $[q]$ is finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §naturals. Subsets, unions and products of finite sets are finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §subset and Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice §union; Boolean identities between classes follow from The Boolean Operations on Classes, Disjointness, and the Universal Class §operations and Axiom of Extensionality for Classes; and $(x,y)=(x',y')$ if and only if $x=x'$ and $y=y'$, by The Characteristic Property of Ordered Pairs and Nested Tuples of Sets §characteristic. For finite sets $D,E$ we count with: (N1) $\#(D\cup E)=\#D+\#E$ if $D\cap E=\emptyset$, by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products §union; (N2) $\#(D\times E)=\#D\cdot\#E$ and $\#\{x\}=1$, by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products §product and Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products §empty; (N3) $\#f(D)=\#D$ for every injective map $f:D\to C$ to a set $C$, by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products §image; (N4) $\#[k]=k$ for $k\in\mathbb{N}_{0}$, by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products §intervals. For $q\in\{m,n\}$ and $\sigma\in S_{q}$, $\operatorname{sgn}(\sigma)=(-1)^{\#\mathrm{Inv}(\sigma)}$ by Sign of a Permutation §sign with $q$ in place of $n$, where $\mathrm{Inv}(\sigma)$ is the set of Inversions of a Permutation of [n] §inversions with $q$ in place of $n$, a finite subset of $[q]\times[q]$ by Inversions of a Permutation Form a Finite Set, and the Sign Map Exists §inversions; by Inversions of a Permutation of [n] §membership, its elements are the pairs $(p,r)$ with $p,r\in[q]$, $p<r$ and $\sigma(r)<\sigma(p)$.

Step 0: the maps $s_{j}$. For $j\in[n]$, $s_{j}:[m]\to[n]$ is the map $s$ of The Index Map Skipping One Element of [n] §map with $j$ in place of $i$, by The Deletion Index Map §deletion-index. Let $j\in[n]$.

(D1) By The Index Map Skipping One Element of [n] §range with $j$ in place of $i$, $s_{j}(k)\neq j$ for every $k\in[m]$, and $s_{j}:[m]\to[n]\setminus\{j\}$ is a bijection; so $s_{j}$ is injective, and every $p\in[n]$ with $p\neq j$ is $s_{j}(k)$ for some $k\in[m]$. By Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §inverse and Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §composition, its inverse is a bijective map $s_{j}^{-1}:[n]\setminus\{j\}\to[m]$ with $s_{j}^{-1}(s_{j}(k))=k$ for $k\in[m]$ and $s_{j}(s_{j}^{-1}(p))=p$ for $p\in[n]\setminus\{j\}$.

(D2) For $k,l\in[m]$: $k<l$ if and only if $s_{j}(k)<s_{j}(l)$, by The Index Map Skipping One Element of [n] §increasing with $j$ in place of $i$.

Step 1: extending a permutation. Let $j\in[n]$ and $\tau\in S_{m}$. For $p\in[n]$ with $p\neq i$, $s_{i}^{-1}(p)\in[m]$, so $s_{j}(\tau(s_{i}^{-1}(p)))\in[n]$. By Maps Defined by Cases §cases, with the sets $[n]$ and $[n]$, the property $p=i$ and the expressions $j$ and $s_{j}(\tau(s_{i}^{-1}(p)))$, there is exactly one map $\sigma_{j,\tau}:[n]\to[n]$ with $\sigma_{j,\tau}(i)=j$ and $\sigma_{j,\tau}(p)=s_{j}(\tau(s_{i}^{-1}(p)))$ for $p\in[n]$ with $p\neq i$. Then: (E1) $\sigma_{j,\tau}(s_{i}(k))=s_{j}(\tau(k))$ for $k\in[m]$, since $s_{i}(k)\neq i$ and $s_{i}^{-1}(s_{i}(k))=k$ by (D1); (E2) $\sigma_{j,\tau}(p)\neq j$ for $p\in[n]$ with $p\neq i$, by (D1) for $s_{j}$; (E3) $\sigma_{j,\tau}\in S_{n}$. Indeed let $p,p'\in[n]$ with $\sigma_{j,\tau}(p)=\sigma_{j,\tau}(p')$. By (E2) and $\sigma_{j,\tau}(i)=j$, $p=i$ if and only if $p'=i$. If $p\neq i$ and $p'\neq i$, then $s_{j}(\tau(s_{i}^{-1}(p)))=s_{j}(\tau(s_{i}^{-1}(p')))$, so $s_{i}^{-1}(p)=s_{i}^{-1}(p')$ as $s_{j}$ and $\tau$ are injective, and $p=p'$ by (D1). So $\sigma_{j,\tau}$ is injective by Injective, Surjective and Bijective Functions between Classes §injective, hence a bijection by Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples §injective-self-map, $[n]$ being finite, and $\sigma_{j,\tau}\in S_{n}$ by Permutations of a Set and the Set of Permutations of [n] §membership.

Step 2: clause map. By (E3), $\Phi_{i}:[n]\times S_{m}\to S_{n}$, $(j,\tau)\mapsto\sigma_{j,\tau}$, is a map, $\sigma_{j,\tau}$ being the only set with the properties of Step 1. By Step 1 and (E1), $\Phi_{i}(j,\tau)(i)=j$ and $\Phi_{i}(j,\tau)(s_{i}(k))=s_{j}(\tau(k))$ for all $j\in[n]$, $\tau\in S_{m}$ and $k\in[m]$. Let $\Psi:[n]\times S_{m}\to S_{n}$ be a map with the same two properties, and let $j\in[n]$ and $\tau\in S_{m}$. Then $\Psi(j,\tau)$ and $\Phi_{i}(j,\tau)$ have the value $j$ at $i$, and every $p\in[n]$ with $p\neq i$ is $s_{i}(k)$ for some $k\in[m]$, by (D1), where both have the value $s_{j}(\tau(k))$. So $\Psi(j,\tau)=\Phi_{i}(j,\tau)$, and $\Psi=\Phi_{i}$. This proves clause map. Below, $\Phi=\Phi_{i}$.

Step 3: clause bijection. $\Phi$ is injective: if $\Phi(j,\tau)=\Phi(j',\tau')$, then $j=\Phi(j,\tau)(i)=\Phi(j',\tau')(i)=j'$, and for $k\in[m]$, $s_{j}(\tau(k))=s_{j}(\tau'(k))$, so $\tau(k)=\tau'(k)$ as $s_{j}$ is injective; hence $\tau=\tau'$, and $(j,\tau)=(j',\tau')$. $\Phi$ is surjective: let $\sigma\in S_{n}$ and $j=\sigma(i)\in[n]$. For $k\in[m]$, $s_{i}(k)\neq i$ by (D1), so $\sigma(s_{i}(k))\neq\sigma(i)=j$ as $\sigma$ is injective. Let $\tau:[m]\to[m]$, $k\mapsto s_{j}^{-1}(\sigma(s_{i}(k)))$, with values in $[m]$ by (D1) for $s_{j}$. Then $s_{j}(\tau(k))=\sigma(s_{i}(k))$ for $k\in[m]$, by (D1) for $s_{j}$. If $\tau(k)=\tau(l)$, then $\sigma(s_{i}(k))=\sigma(s_{i}(l))$, so $k=l$, as $\sigma$ and $s_{i}$ are injective; thus $\tau$ is injective, hence a bijection by Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples §injective-self-map, and $\tau\in S_{m}$. Now $\Phi(j,\tau)(i)=j=\sigma(i)$, and every $p\in[n]$ with $p\neq i$ is $s_{i}(k)$ for some $k\in[m]$, by (D1), where $\Phi(j,\tau)(s_{i}(k))=s_{j}(\tau(k))=\sigma(s_{i}(k))$; so $\Phi(j,\tau)=\sigma$. Hence $\Phi$ is a bijection by Injective, Surjective and Bijective Functions between Classes §bijective.

Step 4: clause sign. Let $j\in[n]$, $\tau\in S_{m}$ and $\sigma=\Phi(j,\tau)$, so $\sigma(i)=j$ and $\sigma(s_{i}(k))=s_{j}(\tau(k))$ for $k\in[m]$. Let $N_{\sigma}=\#\mathrm{Inv}(\sigma)$ and $N_{\tau}=\#\mathrm{Inv}(\tau)$. Let $I_{0}=\mathrm{Inv}(\sigma)\cap\bigl(([n]\setminus\{i\})\times([n]\setminus\{i\})\bigr)$, $I_{1}=\mathrm{Inv}(\sigma)\cap([n]\times\{i\})$ and $I_{2}=\mathrm{Inv}(\sigma)\cap(\{i\}\times[n])$, finite as subsets of $\mathrm{Inv}(\sigma)$. A pair $(p,q)\in\mathrm{Inv}(\sigma)$ lies in $I_{1}$ if $q=i$, in $I_{2}$ if $p=i$, and in $I_{0}$ otherwise; no pair lies in two of these sets, since the pairs of $I_{0}$ have no entry $i$ and $(i,i)\notin\mathrm{Inv}(\sigma)$. So $\mathrm{Inv}(\sigma)=(I_{0}\cup I_{1})\cup I_{2}$ with $I_{0}\cap I_{1}=\emptyset$ and $(I_{0}\cup I_{1})\cap I_{2}=\emptyset$, and by (N1)

$$N_{\sigma}=\#I_{0}+\#I_{1}+\#I_{2}.\tag{1}$$

The set $I_{0}$. Let $h_{0}:\mathrm{Inv}(\tau)\to[n]\times[n]$, $(k,l)\mapsto(s_{i}(k),s_{i}(l))$; it is injective, by the characteristic property of pairs and the injectivity of $s_{i}$. We show that its image is $I_{0}$. If $(k,l)\in\mathrm{Inv}(\tau)$, then $k<l$ and $\tau(l)<\tau(k)$, so $p=s_{i}(k)$ and $q=s_{i}(l)$ lie in $[n]\setminus\{i\}$ by (D1), $p<q$ by (D2), and $\sigma(q)=s_{j}(\tau(l))<s_{j}(\tau(k))=\sigma(p)$ by (D2) for $s_{j}$; so $h_{0}(k,l)=(p,q)\in I_{0}$. Conversely, if $(p,q)\in I_{0}$, let $k=s_{i}^{-1}(p)$ and $l=s_{i}^{-1}(q)$, so $s_{i}(k)=p$ and $s_{i}(l)=q$ by (D1); then $p<q$ gives $k<l$ by (D2), and $s_{j}(\tau(l))=\sigma(q)<\sigma(p)=s_{j}(\tau(k))$ gives $\tau(l)<\tau(k)$ by (D2) for $s_{j}$; so $(k,l)\in\mathrm{Inv}(\tau)$ and $h_{0}(k,l)=(p,q)$. By (N3), $\#I_{0}=N_{\tau}$. The sets $I_{1}$ and $I_{2}$. Let $L=\{p\in[n]:p<i\}$ and $G=\{q\in[n]:\sigma(q)<j\}$; then $i\notin L$, and $i\notin G$ as $\sigma(i)=j$. The elements of $I_{1}$ are the pairs $(p,i)$ with $p\in L$ and $j=\sigma(i)<\sigma(p)$. For $p\in L$, $p\neq i$, so $\sigma(p)\neq j$, and $j<\sigma(p)$ if and only if $p\notin G$. Hence $I_{1}=(L\setminus G)\times\{i\}$. Likewise, the elements of $I_{2}$ are the pairs $(i,q)$ with $q\in G$ and $i<q$; for $q\in G$, $q\neq i$, so $i<q$ if and only if $q\notin L$. Hence $I_{2}=\{i\}\times(G\setminus L)$. By (N2), $\#I_{1}=\#(L\setminus G)$ and $\#I_{2}=\#(G\setminus L)$. Counting $L$ and $G$. As $1\le i$, $i-1\in\mathbb{N}_{0}$ and $(i-1)+1=i$, by The Difference of Two Natural Numbers with Zero §difference, and $(i-1)+1$ is the successor of $i-1$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication §plus-one; so for $p\in\mathbb{N}$, $p<i$ if and only if $p\le i-1$, by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §successor. As $i\le n$, $L=[i-1]$, and $\#L=i-1$ by (N4). Likewise, for $r\in\mathbb{N}$, $r<j$ if and only if $r\le j-1$. The restriction $\sigma|_{G}:G\to[n]$ is injective, and its image is $[j-1]$: for $q\in G$, $\sigma(q)<j$, so $\sigma(q)\in[j-1]$; for $r\in[j-1]$, $r<j\le n$, and as $\sigma$ is surjective there is $q\in[n]$ with $\sigma(q)=r<j$, that is $q\in G$. By (N3) and (N4), $\#G=j-1$. Parity. $L=(L\setminus G)\cup(L\cap G)$ and $G=(G\setminus L)\cup(L\cap G)$, both unions disjoint. With $a=\#(L\cap G)$, (N1) gives $\#(L\setminus G)+a=i-1$ and $\#(G\setminus L)+a=j-1$, so $\#I_{1}+(a+1)=i$ and $\#I_{2}+(a+1)=j$. With (1) and $\#I_{0}=N_{\tau}$, in $\mathbb{N}_{0}$,

$$N_{\sigma}+(a+1)+(a+1)=N_{\tau}+\bigl(\#I_{1}+(a+1)\bigr)+\bigl(\#I_{2}+(a+1)\bigr)=N_{\tau}+(i+j).$$

Write $e=-1\in\mathbb{R}$. By Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §exponents, $e^{N_{\sigma}}e^{a+1}e^{a+1}=e^{N_{\tau}}e^{i+j}$. By Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product, $e^{a+1}e^{a+1}=(e\,e)^{a+1}=1^{a+1}=1$, as $e\,e=1$. Hence $e^{N_{\sigma}}=e^{i+j}e^{N_{\tau}}$, that is, $\operatorname{sgn}(\Phi_{i}(j,\tau))=(-1)^{i+j}\operatorname{sgn}(\tau)$ by Sign of a Permutation §sign, applied with $n$ and with $m$.