Proof of The Sign of a Permutation is Multiplicative

Throughout, for $r\in[n]$ with $S(r)\in[n]$, where $S$ is the successor map of Natural Numbers, we write $\tau_{r}=\theta_{r\,S(r)}$ for the adjacent transposition of Every Permutation is a Product of Adjacent Transpositions; since $S(r)=r+1$ by that definition, this is the map described there. By Every Permutation is a Product of Adjacent Transpositions every $\sigma\in S_{n}$ can be written as a composition $\tau_{r_{1}}\circ\cdots\circ\tau_{r_{N}}$ of $N$ adjacent transpositions with $N\ge0$, the case $N=0$ being the empty composition, that is, $\sigma=\mathrm{id}$; the composition is unambiguous by the associativity in claim 2 of Permutations of an Initial Segment Form a Group under Composition. By Sign of a Product of Adjacent Transpositions, whenever $\sigma$ is such a composition with $N\ge1$ we have $\mathrm{sgn}(\sigma)=(-1)^{N}$.

The identity. If $i,j\in[n]$ satisfy $i<j$ then $\mathrm{id}(i)=i<j=\mathrm{id}(j)$, so $\mathrm{id}$ has no inversion in the sense of Sign of a Permutation and $\mathrm{sgn}(\mathrm{id})=1$. This is the first assertion of claim 1.

Step A: composing with one adjacent transposition changes the sign. Let $\sigma\in S_{n}$ and let $r\in[n]$ with $S(r)\in[n]$. Write $\sigma=\tau_{r_{1}}\circ\cdots\circ\tau_{r_{N}}$ with $N\ge0$ as above. Then $\sigma\circ\tau_{r}$ is a composition of $S(N)$ adjacent transpositions, namely of $\tau_{r_{1}},\dots,\tau_{r_{N}},\tau_{r}$ in this order.

If $N=0$ then $\sigma=\mathrm{id}$ and $\sigma\circ\tau_{r}=\tau_{r}$ is a composition of one adjacent transposition, so $\mathrm{sgn}(\sigma\circ\tau_{r})=(-1)^{1}=-1=-\mathrm{sgn}(\sigma)$, using claim 1 of Properties of Natural Number Powers in a Field and the value $\mathrm{sgn}(\mathrm{id})=1$ just obtained.

If $N\ge1$ then $\mathrm{sgn}(\sigma)=(-1)^{N}$ and $\mathrm{sgn}(\sigma\circ\tau_{r})=(-1)^{S(N)}$, so claim 1 of Properties of Natural Number Powers in a Field gives

In both cases $\mathrm{sgn}(\sigma\circ\tau_{r})=-\mathrm{sgn}(\sigma)$. Taking $\sigma=\mathrm{id}$ also records that $\mathrm{sgn}(\tau_{r})=-1$ for every adjacent transposition $\tau_{r}$.

Step B: claim 2. If $\tau=\mathrm{id}$ then $\sigma\circ\tau=\sigma$ by claim 1 of Permutations of an Initial Segment Form a Group under Composition and $\mathrm{sgn}(\sigma)\mathrm{sgn}(\mathrm{id})=\mathrm{sgn}(\sigma)$, so the identity holds. Otherwise $\tau$ is a composition of $M$ adjacent transpositions with $M\ge1$, and it suffices to prove, by induction on $M$ using Principle of Induction for the Natural Numbers, the statement $Q(M)$: for every $\sigma\in S_{n}$ and every $\tau\in S_{n}$ that is a composition of $M$ adjacent transpositions, $\mathrm{sgn}(\sigma\circ\tau)=\mathrm{sgn}(\sigma)\mathrm{sgn}(\tau)$.

For $Q(1)$, let $\tau=\tau_{s}$. By Step A, $\mathrm{sgn}(\sigma\circ\tau_{s})=-\mathrm{sgn}(\sigma)$ and $\mathrm{sgn}(\tau_{s})=-1$, so $\mathrm{sgn}(\sigma)\mathrm{sgn}(\tau_{s})=-\mathrm{sgn}(\sigma)=\mathrm{sgn}(\sigma\circ\tau_{s})$.

Assume $Q(M)$ and let $\tau=\tau_{s_{1}}\circ\cdots\circ\tau_{s_{S(M)}}$. Put $\tau'=\tau_{s_{1}}\circ\cdots\circ\tau_{s_{M}}$, a composition of $M$ adjacent transpositions, so that $\tau=\tau'\circ\tau_{s_{S(M)}}$ and, by associativity, $\sigma\circ\tau=(\sigma\circ\tau')\circ\tau_{s_{S(M)}}$. Step A and the hypothesis $Q(M)$ give

while Step A applied to $\tau'$ gives $\mathrm{sgn}(\tau)=-\mathrm{sgn}(\tau')$, so that $\mathrm{sgn}(\sigma)\mathrm{sgn}(\tau)=-\mathrm{sgn}(\sigma)\mathrm{sgn}(\tau')$ as well. This proves $Q(S(M))$ and hence claim 2.

Step C: the rest of claim 1. Let $\sigma\in S_{n}$. If $\sigma=\mathrm{id}$ then $\mathrm{sgn}(\sigma)\mathrm{sgn}(\sigma)=1$. Otherwise $\mathrm{sgn}(\sigma)=(-1)^{N}$ for some $N\ge1$, and claims 3 and 2 of Properties of Natural Number Powers in a Field, together with the identity $(-1)(-1)=1$ of Zero Products and Elementary Identities in a Field, give

Writing $x=\mathrm{sgn}(\sigma)$, the elementary field identities of Zero Products and Elementary Identities in a Field turn $xx=1$ into $(x-1)(x+1)=0$, and that same lemma then gives $x-1=0$ or $x+1=0$, that is, $x=1$ or $x=-1$.

Step D: claim 3. By claim 3 of Permutations of an Initial Segment Form a Group under Composition and claim 2 above,

Multiplying by $\mathrm{sgn}(\sigma)$ and using claim 1 gives $\mathrm{sgn}(\sigma^{-1})=\mathrm{sgn}(\sigma)\mathrm{sgn}(\sigma)\mathrm{sgn}(\sigma^{-1})=\mathrm{sgn}(\sigma)$.

Step E: claim 4. Let $p,q\in[n]$ with $p\ne q$. From the definition of $\theta_{pq}$ one checks on each of the three cases $k=p$, $k=q$, and $k\notin\{p,q\}$ that $\theta_{pq}(\theta_{pq}(k))=k$; so $\theta_{pq}$ is a two-sided inverse of itself and is a bijection by claim 3 of Inverse of a Bijection, hence $\theta_{pq}\in S_{n}$. Also $\theta_{pq}=\theta_{qp}$, and by claim 3 of Properties of the Order on the Natural Numbers one of $p<q$ and $q<p$ holds, so we may assume $p<q$.

By claim 7 of Properties of the Order on the Natural Numbers there is exactly one $t\in\mathbb{N}$ with $q=p+t$. We prove by induction on $t$, using Principle of Induction for the Natural Numbers, the statement $R(t)$: for all $p,q\in[n]$ with $p<q$ and $q=p+t$ we have $\mathrm{sgn}(\theta_{pq})=-1$.

For $R(1)$: $q=p+1=S(p)$, so $\theta_{pq}=\tau_{p}$ is an adjacent transposition and $\mathrm{sgn}(\theta_{pq})=-1$ by Step A.

Assume $R(t)$ and let $q=p+S(t)$. By Natural Numbers we have $p+S(t)=S(p+t)$, so with $q'=p+t$ we get $q=S(q')$. By claim 6 of Properties of the Order on the Natural Numbers, $p<q'$ and $q'<q$; since $q\in[n]$ and $q'<q$, claim 1 of that lemma gives $q'\in[n]$. Thus $\theta_{pq'}$ and the adjacent transposition $\tau_{q'}=\theta_{q'q}$ are defined, and we claim

Indeed, evaluating the right-hand side at $p$ gives $\tau_{q'}(\theta_{pq'}(p))=\tau_{q'}(q')=q$, since $p\ne q'$ and $p\ne q$; at $q$ it gives $\tau_{q'}(\theta_{pq'}(q'))=\tau_{q'}(p)=p$; at $q'$ it gives $\tau_{q'}(\theta_{pq'}(q))=\tau_{q'}(q)=q'$, since $q\ne p$ and $q\ne q'$; and at any other $k\in[n]$ all three maps fix $k$. These are exactly the values of $\theta_{pq}$.

Applying claim 2 twice, and then claim 1 to $\tau_{q'}$,

the last equality by $R(t)$. This proves $R(S(t))$ and completes the proof.