Proof of Rules for the Sign of a Permutation

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

Preliminaries. The adopted setting extends Sets and Maps: Ordinary Notation, The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion, Commutative Rings, Fields and Ordered Fields: Standard Notation and The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness, through the base clauses of the settings it extends, starting from Metric Spaces: Balls, the Metric Topology, and the Real and Complex Numbers as Metric Spaces §base. By Intervals of Natural Numbers §segment and Intervals of Natural Numbers §interval, $[n]=\{k\in\mathbb{N}_{0}:1\le k\le n\}$, a set by Sets and Maps: Ordinary Notation §set-builder, its defining formula being predicative by Commutative Rings, Fields and Ordered Fields: Standard Notation §notation-sources, and 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; $[n]\times[n]$ is a set by Sets and Maps: Ordinary Notation §sets and 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 §union. Every map between sets is a set by Sets and Maps: Ordinary Notation §maps, and by Permutations of a Set and the Set of Permutations of [n] §membership every $\sigma\in S_{n}$ is a bijective map $\sigma:[n]\to[n]$. A map $F:A\to Y$ has domain $A$ by Functions, Values of a Function, and Functions from One Class to Another §map, so by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §equality two maps $F,G:A\to Y$ are equal as soon as $F(u)=G(u)$ for every $u\in A$; we refer to this as (E).

$\mathbb{R}$ is an ordered field by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §reals, hence a field and a commutative ring; by Commutative Rings, Fields and Ordered Fields: Standard Notation §rings its multiplication is associative and commutative with neutral element $1$, and products over finite sets are those of Sums and Products over a Finite Set and over an Interval §operation, Sums and Products over a Finite Set and over an Interval §empty and Sums and Products over a Finite Set and over an Interval §subsets, the empty product being $1$. An element of $\mathbb{N}_{0}$ standing where a real number is required denotes a real number by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §identification, and equality and the order agree in $\mathbb{N}_{0}$ and in $\mathbb{R}$ by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §agreement; differences below are formed in $\mathbb{R}$.

For $\sigma\in S_{n}$, $\operatorname{sgn}(\sigma)=(-1)^{\#\mathrm{Inv}(\sigma)}$ by Sign of a Permutation §sign, with $\mathrm{Inv}(\sigma)$ the set of Inversions of a Permutation of [n] §inversions, finite by Inversions of a Permutation Form a Finite Set, and the Sign Map Exists §inversions. By Inversions of a Permutation of [n] §membership every element of $\mathrm{Inv}(\sigma)$ is a pair $(i,j)$ with $i,j\in[n]$, $i<j$ and $\sigma(j)<\sigma(i)$, every such pair lies in $\mathrm{Inv}(\sigma)$, and so, by The Characteristic Property of Ordered Pairs and Nested Tuples of Sets §characteristic, for $i,j\in[n]$ we have $(i,j)\in\mathrm{Inv}(\sigma)$ if and only if $i<j$ and $\sigma(j)<\sigma(i)$. Order facts in $\mathbb{N}_{0}$: by The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §order, $\le$ and $<$ are the order and the strict order of $\mathbb{N}_{0}$; $\le$ is a well-order on the set $\mathbb{N}_{0}$ by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §well-order, hence a total order by Well-Orders on a Set §well-order, and $<$ is the strict relation associated with $\le$ by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §strict. Hence $<$ is irreflexive and transitive on $\mathbb{N}_{0}$ by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §strict-irreflexive and Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §strict-transitive, and, $\le$ being total, for all $u,v\in\mathbb{N}_{0}$ exactly one of $u<v$, $u=v$ and $v<u$ holds by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §trichotomy (trichotomy).

A product of constant factors. We use the following fact (C): if $D$ is a finite set, $c\in\mathbb{R}$, and $g$ is a map from a set containing $D$ to $\mathbb{R}$ with $g(x)=c$ for every $x\in D$, then $\prod_{x\in D}g(x)=c^{\#D}$. By Sums and Products over a Finite Set and over an Interval §subsets the product is that of the restriction $g|_{D}$, which by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §restriction is a function with domain $D\cap\operatorname{dom}g=D$, as $D\subseteq\operatorname{dom}g$, and with $(g|_{D})(x)=g(x)=c$ for $x\in D$; since $\operatorname{ran}(g|_{D})\subseteq\operatorname{ran}g\subseteq\mathbb{R}$, it is a map $D\to\mathbb{R}$. If $D=\emptyset$, the product is $1$ by Sums and Products over a Finite Set and over an Interval §empty, $\#D=0$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products §empty, and $c^{0}=1$ by Powers with Exponents in the Natural Numbers with Zero §zero. If $D\neq\emptyset$, then by Sums and Products over a Finite Set and over an Interval §operation, with $\#D\in\mathbb{N}$ and a bijection $\varphi$ from $[\#D]$ onto $D$ as provided there, $\prod_{x\in D}g(x)=\prod_{k=1}^{\#D}g|_{D}(\varphi(k))$, the iterated product, by Iterated Operations: Finite Sums and Finite Products §iterated, of the map $k\mapsto g|_{D}(\varphi(k))$ on $[\#D]$; this map has the value $c$ at every $k$, so by (E) it is the map $k\mapsto c$, whose iterated product is $c^{\#D}$ by Powers with Exponents in the Natural Numbers with Zero §power and Iterated Operations: Finite Sums and Finite Products §iterated.

A square of a power. For every $k\in\mathbb{N}_{0}$, $(-1)^{k}(-1)^{k}=1$: by Rules of Arithmetic in a Commutative Ring: Zero, Signs and Squares, and No Zero Divisors in a Field §signs, $(-1)(-1)=1\cdot1=1$, so by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product, $(-1)^{k}(-1)^{k}=((-1)(-1))^{k}=1^{k}=1$. We refer to this as (Q).

Clause values. Let $\sigma\in S_{n}$ and $y=\operatorname{sgn}(\sigma)=(-1)^{\#\mathrm{Inv}(\sigma)}$. By (Q), $y\,y=1$. Since $2=1+1$ by Arithmetic and Order of the Natural Numbers §digits, Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §exponents and Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product give $y^{2}=y^{1}y^{1}=y\,y$, and $1^{2}=1$ by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product. Hence, by Rules of Arithmetic in a Commutative Ring: Zero, Signs and Squares, and No Zero Divisors in a Field §squares, $(y-1)(y+1)=y^{2}-1^{2}=y\,y-1=1-1=0$. By Rules of Arithmetic in a Commutative Ring: Zero, Signs and Squares, and No Zero Divisors in a Field §field, applicable as $\mathbb{R}$ is a field, $y-1=0$ or $y+1=0$, that is, $y=1$ or $y=-1$. Also $\operatorname{sgn}(\sigma)\operatorname{sgn}(\sigma)=y\,y=1$.

Clause identity. $\mathrm{id}_{[n]}\in S_{n}$ by Permutations of [n]: Identity, Composition, Inverses, Translations and Transpositions §identity, and $\mathrm{id}_{[n]}(k)=k$ for $k\in[n]$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §identity. By Inversions of a Permutation of [n] §membership, an element of $\mathrm{Inv}(\mathrm{id}_{[n]})$ would be a pair $(i,j)$ with $i<j$ and $j=\mathrm{id}_{[n]}(j)<\mathrm{id}_{[n]}(i)=i$, which is impossible. So $\mathrm{Inv}(\mathrm{id}_{[n]})=\emptyset$, $\#\mathrm{Inv}(\mathrm{id}_{[n]})=0$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products §empty, and $\operatorname{sgn}(\mathrm{id}_{[n]})=(-1)^{0}=1$ by Powers with Exponents in the Natural Numbers with Zero §zero.

Clause multiplicative. Step 1: the set $P$ of increasing pairs. Let

$$P=\{r\in[n]\times[n]:\exists i\,\exists j\,(r=(i,j)\wedge i<j)\},$$

formed by Class Abstraction: the Class of All Sets Satisfying a Predicative Formula §restricted from a formula that applies no quantifier to a class variable, the ordered pair being a defined set symbol, and hence predicative by Predicativity of Expressions with Abbreviations, and Symbol-Free Forms of the Basic Defined Set Symbols §closure. By Class Abstraction: the Class of All Sets Satisfying a Predicative Formula §abstraction it is a subclass of $[n]\times[n]$, so a set by Sets and Maps: Ordinary Notation §set-builder and 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. As in the preliminaries, by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set §membership and The Characteristic Property of Ordered Pairs and Nested Tuples of Sets §characteristic, every element of $P$ is a pair $(i,j)$ with $i,j\in[n]$ and $i<j$, and for $i,j\in[n]$, $(i,j)\in P$ if and only if $i<j$. In particular $\mathrm{Inv}(\tau)\subseteq P$ for every $\tau\in S_{n}$, since by Inversions of a Permutation of [n] §membership every element of $\mathrm{Inv}(\tau)$ is a pair $(i,j)$ with $i,j\in[n]$ and $i<j$.

Step 2: the maps $D_{\rho}$ and the numbers $\Delta(\rho)$. Let $\rho\in S_{n}$. For $v,w\in[n]$, the expression $\rho(w)-\rho(v)$ is built from the values $\rho(v)$ and $\rho(w)$, defined set symbols by Functions, Values of a Function, and Functions from One Class to Another §value used properly as $v,w\in[n]=\operatorname{dom}\rho$, read as real numbers through the identifying map of The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §identification, and from the difference of $\mathbb{R}$, which is given by a predicative formula by Predicative Substitution of Values of Functions and Binary Operations, and Predicative Formulas for Negatives, Differences, Absolute Values, Distances, Reciprocals and Quotients in an Ordered Field §difference-formula; it lies in $\mathbb{R}$. By Maps and Relations Given by Formulas §binary there is exactly one map $D_{\rho}:[n]\times[n]\to\mathbb{R}$ with $D_{\rho}(v,w)=\rho(w)-\rho(v)$ for all $v,w\in[n]$. Put $\Delta(\rho)=\prod_{r\in P}D_{\rho}(r)$, the product of $D_{\rho}|_{P}$ by Sums and Products over a Finite Set and over an Interval §subsets.

Step 3: $\Delta(\rho)\neq0$ for every $\rho\in S_{n}$. For $(i,j)\in P$ we have $i<j$, so $i\neq j$, so $\rho(i)\neq\rho(j)$ as $\rho$ is injective, also as real numbers by The Real Numbers, with the Natural Numbers, Integers and Rationals Identified with Subsets of the Reals, and Completeness §agreement; and $\rho(j)-\rho(i)\neq0$, since $\rho(j)-\rho(i)=0$ would give $\rho(j)=(\rho(j)-\rho(i))+\rho(i)=\rho(i)$ by the ring laws. By Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §restriction the factors of $\Delta(\rho)$ are these values, so $\Delta(\rho)\neq0$ by Products over Finite Sets: a Single Factor, Vanishing in a Field, and Signs and Monotonicity in an Ordered Ring §zero, applicable as $\mathbb{R}$ is a field and $P$ is finite.

Step 4: the signs $\varepsilon_{\tau}$. Let $\tau\in S_{n}$. The property $r\in\mathrm{Inv}(\tau)$ of elements $r$ of $P$ is atomic, with the set $\mathrm{Inv}(\tau)$ of Inversions of a Permutation of [n] §inversions as a parameter, hence predicative; and $-1,1\in\mathbb{R}$. By Maps Defined by Cases §cases with $A=P$ and target $\mathbb{R}$ there is a map $\varepsilon_{\tau}:P\to\mathbb{R}$ with $\varepsilon_{\tau}(r)=-1$ for $r\in\mathrm{Inv}(\tau)$ and $\varepsilon_{\tau}(r)=1$ for $r\in P\setminus\mathrm{Inv}(\tau)$. The sets $\mathrm{Inv}(\tau)$ and $P\setminus\mathrm{Inv}(\tau)$ are finite subsets of $P$ 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, disjoint, with union $P$ by Step 1. By Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals §disjoint-union, (C) and Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product,

$$\prod_{r\in P}\varepsilon_{\tau}(r)=\Bigl(\prod_{r\in\mathrm{Inv}(\tau)}\varepsilon_{\tau}(r)\Bigr)\Bigl(\prod_{r\in P\setminus\mathrm{Inv}(\tau)}\varepsilon_{\tau}(r)\Bigr)=(-1)^{\#\mathrm{Inv}(\tau)}\cdot1^{\#(P\setminus\mathrm{Inv}(\tau))}=\operatorname{sgn}(\tau).$$

Step 5: the bijection $\varphi_{\tau}:P\to P$. Let $\tau\in S_{n}$. For $r\in P$, with components $r_{1}$ and $r_{2}$ as in The Components of an Ordered Pair §components, let $t_{1}(r)=(\tau(r_{2}),\tau(r_{1}))$ and $t_{2}(r)=(\tau(r_{1}),\tau(r_{2}))$; these expressions are built from defined set symbols (components, values, ordered pairs) used properly, as $r\in P$ is an ordered pair with components in $[n]=\operatorname{dom}\tau$. Write $r=(i,j)$ with $i,j\in[n]$ and $i<j$, so $r_{1}=i$ and $r_{2}=j$. If $r\in\mathrm{Inv}(\tau)$, then $\tau(j)<\tau(i)$, so $t_{1}(r)=(\tau(j),\tau(i))\in P$ by Step 1. If $r\notin\mathrm{Inv}(\tau)$, then $\tau(j)<\tau(i)$ fails, and $\tau(i)\neq\tau(j)$ as $\tau$ is injective, so $\tau(i)<\tau(j)$ by trichotomy and $t_{2}(r)=(\tau(i),\tau(j))\in P$. With the predicative property of Step 4, Maps Defined by Cases §cases with $A=B=P$ gives a map $\varphi_{\tau}:P\to P$ with $\varphi_{\tau}(i,j)=(\tau(j),\tau(i))$ if $(i,j)\in\mathrm{Inv}(\tau)$ and $\varphi_{\tau}(i,j)=(\tau(i),\tau(j))$ otherwise. In both cases $\varphi_{\tau}(i,j)=(a,b)$ with either $a=\tau(i)$ and $b=\tau(j)$, or $a=\tau(j)$ and $b=\tau(i)$.

$\varphi_{\tau}$ is injective. Let $(i,j),(i',j')\in P$ with $\varphi_{\tau}(i,j)=\varphi_{\tau}(i',j')=(a,b)$. Then each of $\tau(i)$ and $\tau(j)$ is $a$ or $b$, and each of $a$ and $b$ is $\tau(i')$ or $\tau(j')$; as $\tau$ is injective by Injective, Surjective and Bijective Functions between Classes §bijective and Injective, Surjective and Bijective Functions between Classes §injective, $i\in\{i',j'\}$ and $j\in\{i',j'\}$. If $i=j'$, then $j\neq i=j'$ forces $j=i'$, and $i<j=i'<j'=i$ is impossible. So $i=i'$, and then $j\neq i=i'$ forces $j=j'$; thus $(i,j)=(i',j')$. Since $P$ is finite, $\varphi_{\tau}$ is a bijection by Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples §injective-self-map.

Step 6: $\Delta(\sigma)=\operatorname{sgn}(\tau)\,\Delta(\sigma\circ\tau)$ for all $\sigma,\tau\in S_{n}$. Let $\sigma,\tau\in S_{n}$; then $\sigma\circ\tau\in S_{n}$ by Permutations of [n]: Identity, Composition, Inverses, Translations and Transpositions §composition, with $(\sigma\circ\tau)(k)=\sigma(\tau(k))$ for $k\in[n]$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §composition. Let $f=D_{\sigma}|_{P}$, a map $P\to\mathbb{R}$ with $f(r)=D_{\sigma}(r)$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §restriction. By Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals §reindexing with the bijection $\varphi_{\tau}:P\to P$,

$$\prod_{r\in P}f(\varphi_{\tau}(r))=\prod_{x\in P}f(x)=\Delta(\sigma).$$

Let $r=(i,j)\in P$. If $r\in\mathrm{Inv}(\tau)$, then by Rules of Arithmetic in a Commutative Ring: Zero, Signs and Squares, and No Zero Divisors in a Field §signs (the rules $-(x-y)=y-x$ and $(-x)y=-(xy)$),

$$f(\varphi_{\tau}(r))=D_{\sigma}(\tau(j),\tau(i))=\sigma(\tau(i))-\sigma(\tau(j))=-\bigl((\sigma\circ\tau)(j)-(\sigma\circ\tau)(i)\bigr)=(-1)\,D_{\sigma\circ\tau}(r)=\varepsilon_{\tau}(r)\,D_{\sigma\circ\tau}(r);$$

otherwise $f(\varphi_{\tau}(r))=D_{\sigma}(\tau(i),\tau(j))=(\sigma\circ\tau)(j)-(\sigma\circ\tau)(i)=1\cdot D_{\sigma\circ\tau}(r)=\varepsilon_{\tau}(r)\,D_{\sigma\circ\tau}(r)$. The map $r\mapsto\varepsilon_{\tau}(r)\,D_{\sigma\circ\tau}(r)$ on $P$ exists by Maps and Relations Given by Formulas §map, its expression being built from values of maps and of the multiplication, which are predicative by Commutative Rings, Fields and Ordered Fields: Standard Notation §notation-sources; and $r\mapsto f(\varphi_{\tau}(r))$ is the map $f\circ\varphi_{\tau}:P\to\mathbb{R}$ of Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §composition. By (E) the two maps are equal, so by Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals §termwise, applied to $\varepsilon_{\tau}$ and $D_{\sigma\circ\tau}|_{P}$, and by Step 4,

$$\Delta(\sigma)=\prod_{r\in P}\varepsilon_{\tau}(r)\,D_{\sigma\circ\tau}(r)=\Bigl(\prod_{r\in P}\varepsilon_{\tau}(r)\Bigr)\Bigl(\prod_{r\in P}D_{\sigma\circ\tau}(r)\Bigr)=\operatorname{sgn}(\tau)\,\Delta(\sigma\circ\tau).$$

Step 7: conclusion. For $\rho\in S_{n}$, Step 6 with $\mathrm{id}_{[n]}$ and $\rho$ in place of $\sigma$ and $\tau$, together with $\mathrm{id}_{[n]}\circ\rho=\rho$ from Permutations of [n]: Identity, Composition, Inverses, Translations and Transpositions §identity, gives $\Delta(\mathrm{id}_{[n]})=\operatorname{sgn}(\rho)\,\Delta(\rho)$. Let $\sigma,\tau\in S_{n}$. Applying this to $\rho=\sigma\circ\tau$ and to $\rho=\sigma$, and then Step 6,

$$\operatorname{sgn}(\sigma\circ\tau)\,\Delta(\sigma\circ\tau)=\Delta(\mathrm{id}_{[n]})=\operatorname{sgn}(\sigma)\,\Delta(\sigma)=\operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)\,\Delta(\sigma\circ\tau).$$

Hence $\bigl(\operatorname{sgn}(\sigma\circ\tau)-\operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)\bigr)\Delta(\sigma\circ\tau)=0$ by Rules of Arithmetic in a Commutative Ring: Zero, Signs and Squares, and No Zero Divisors in a Field §signs. As $\Delta(\sigma\circ\tau)\neq0$ by Step 3, Rules of Arithmetic in a Commutative Ring: Zero, Signs and Squares, and No Zero Divisors in a Field §field gives $\operatorname{sgn}(\sigma\circ\tau)-\operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)=0$, that is, $\operatorname{sgn}(\sigma\circ\tau)=\operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)$.

Clause inverse. Let $\sigma\in S_{n}$. By Permutations of [n]: Identity, Composition, Inverses, Translations and Transpositions §inverse, $\sigma^{-1}\in S_{n}$ and $\sigma\circ\sigma^{-1}=\mathrm{id}_{[n]}$. By the clauses multiplicative and identity, $\operatorname{sgn}(\sigma)\operatorname{sgn}(\sigma^{-1})=\operatorname{sgn}(\mathrm{id}_{[n]})=1$. Multiplying by $\operatorname{sgn}(\sigma)$ and using $\operatorname{sgn}(\sigma)\operatorname{sgn}(\sigma)=1$ from the clause values gives $\operatorname{sgn}(\sigma^{-1})=\operatorname{sgn}(\sigma)$.

Clause transposition. Let $p,q\in[n]$ with $p\neq q$, and write $\theta=\theta_{pq}$; by Transpositions of [n] §transposition it is the map of Permutations of [n]: Identity, Composition, Inverses, Translations and Transpositions §transposition, so $\theta(p)=q$, $\theta(q)=p$ and $\theta(k)=k$ for every other $k\in[n]$. The map $\theta_{qp}$ has the same three properties, so $\theta_{qp}=\theta_{pq}$ by the uniqueness in Permutations of [n]: Identity, Composition, Inverses, Translations and Transpositions §transposition; exchanging the names $p$ and $q$ if necessary, we may therefore assume $p<q$, by trichotomy.

Three sets. Let $M=\{k\in[n]:p<k\wedge k<q\}$, formed by Class Abstraction: the Class of All Sets Satisfying a Predicative Formula §restricted from a formula predicative by Predicativity of Expressions with Abbreviations, and Symbol-Free Forms of the Basic Defined Set Symbols §closure; it is a subset of $[n]$, so a set by Sets and Maps: Ordinary Notation §set-builder and 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. Let $m=\#M\in\mathbb{N}_{0}$. For $k\in M$ the pairs $(p,k)$ and $(k,q)$ lie in $[n]\times[n]$ by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set §membership, so by Maps and Relations Given by Formulas §map, the ordered pair being a defined set symbol used properly, there are maps $\alpha,\beta:M\to[n]\times[n]$ with $\alpha(k)=(p,k)$ and $\beta(k)=(k,q)$. Both are injective by The Characteristic Property of Ordered Pairs and Nested Tuples of Sets §characteristic. Let $U_{1}=\{(p,q)\}$, $U_{2}=\alpha(M)$ and $U_{3}=\beta(M)$, the images being sets as in Sets and Maps: Ordinary Notation §images; by The Image and the Preimage of a Class under a Class §image and Functions, Values of a Function, and Functions from One Class to Another §value, the elements of $U_{2}$ are the pairs $(p,k)$ and those of $U_{3}$ the pairs $(k,q)$ with $k\in M$. They 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 §small 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 §image, and $\#U_{1}=1$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products §empty and $\#U_{2}=\#U_{3}=m$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products §image. They are pairwise disjoint, by The Characteristic Property of Ordered Pairs and Nested Tuples of Sets §characteristic: $(p,q)=(p,k)$ or $(p,q)=(k,q)$ would give $k=q$ or $k=p$, and $(p,k)=(k',q)$ would give $k=q$, each impossible for $k,k'\in M$.

$\mathrm{Inv}(\theta)=U_{1}\cup U_{2}\cup U_{3}$. The order facts used are the irreflexivity, transitivity and trichotomy of $<$ on $\mathbb{N}_{0}$ from the preliminaries, and the values of $\theta$ are those of Transpositions of [n] §transposition. By the preliminaries, for $i,j\in[n]$, $(i,j)\in\mathrm{Inv}(\theta)$ if and only if $i<j$ and $\theta(j)<\theta(i)$. First, $(p,q)\in\mathrm{Inv}(\theta)$, as $p<q$ and $\theta(q)=p<q=\theta(p)$. For $k\in M$, $k\neq p$ and $k\neq q$, so $\theta(k)=k$; then $(p,k)\in\mathrm{Inv}(\theta)$, as $p<k$ and $\theta(k)=k<q=\theta(p)$, and $(k,q)\in\mathrm{Inv}(\theta)$, as $k<q$ and $\theta(q)=p<k=\theta(k)$. Conversely, every element of $\mathrm{Inv}(\theta)$ is, by Inversions of a Permutation of [n] §membership as in the preliminaries, a pair $(i,j)$ with $i,j\in[n]$, $i<j$ and $\theta(j)<\theta(i)$; let $(i,j)$ be such an element. If $i=p$: either $j=q$ and $(i,j)\in U_{1}$, or $j\neq q$, and $j\neq p$ as $p<j$, so $j=\theta(j)<\theta(p)=q$, whence $j\in M$ and $(i,j)\in U_{2}$. If $i=q$: then $j\neq q$ and $j\neq p$ (as $p<q<j$), so $j=\theta(j)<\theta(q)=p<q<j$, impossible. If $i\neq p$ and $i\neq q$, then $\theta(i)=i$: for $j=p$, $q=\theta(j)<i<j=p<q$ is impossible; for $j=q$, $p=\theta(j)<i<q$, so $i\in M$ and $(i,j)\in U_{3}$; and for $j\neq p$, $j\neq q$, $j=\theta(j)<i<j$ is impossible.

The count. $U_{2}\cup U_{3}$ 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 §union and disjoint from $U_{1}$, so by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products §union twice, $\#\mathrm{Inv}(\theta)=\#U_{1}+\#(U_{2}\cup U_{3})=1+(m+m)$. Hence, by Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §exponents, Powers in a Commutative Ring, a Field and an Ordered Field: Exponent Laws, Factorisation, Geometric Sums, Monotonicity and Bernoulli's Inequality §product ($x^{1}=x$) and (Q),

$$\operatorname{sgn}(\theta)=(-1)^{1+(m+m)}=(-1)^{1}\bigl((-1)^{m}(-1)^{m}\bigr)=(-1)\cdot1=-1.$$