Proof of Counting Maps, Injections, Bijections and Permutations

Throughout, sets of maps between finite sets, their subsets and products of finite sets are finite (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 (ix), 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 (iv), 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 (v)), and so is $C\cup\{x\}$ for a finite set $C$ (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 (iii)); the properties proved by induction over finite sets are predicative, finiteness and $\#$ being expressed by Induction over Finite Sets, and Predicative Formulas for the Segments [n] and for Finiteness (ii) and The Maps i ↦ #C(i) and S ↦ #S (iii); and sums and products in $\mathbb{N}_{0}$ are rearranged and cancelled by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (iv), Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (v) and Arithmetic of Multiplication on Omega: Recursion Rules, Distributivity, Associativity, Commutativity, No Zero Divisors, Cancellation and Compatibility with the Order (vi). If $C$ is finite and $x\notin C$, then $(C\cup\{x\})\setminus\{x\}=C$, so

$$\#(C\cup\{x\})=\#C+1$$

by Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples (i). Both counting steps below use induction over finite sets (Induction over Finite Sets, and Predicative Formulas for the Segments [n] and for Finiteness (iii)), the counts of the empty set and of a singleton, $\#\emptyset=0$ and $\#\{u\}=1$ (Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (ii)), and the fact that the only map from $\emptyset$ to a set $B$ is the empty map, which is injective: a map from $\emptyset$ is a subset of $\emptyset\times B=\emptyset$.

Step 1: all maps ((i)). Fix $B$ with $\#B=n$; we show $\#(B^{C})=n^{\#C}$ for every finite set $C$ by induction over $C$.

Base. $B^{\emptyset}=\{\emptyset\}$ has one element, and $n^{0}=1$ (Powers of Natural Numbers with Zero (ii)); this includes $n=0$, where $0^{0}=1$.

Induction step. Let $C$ be finite with $\#(B^{C})=n^{j}$, where $j=\#C$, and let $x\notin C$; put $C'=C\cup\{x\}$, so $\#C'=j+1$. The map $\varphi\mapsto(\varphi|_{C},\varphi(x))$ is a bijection from $B^{C'}$ onto $B^{C}\times B$ (Maps on a Set Enlarged by One Point (i)), so by Counting through Bijections, Injections and Surjections (i), Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (vi), the induction hypothesis and Powers of Natural Numbers with Zero (ii),

$$\#(B^{C'})=\#(B^{C}\times B)=\#(B^{C})\cdot n=n^{j}\cdot n=n^{j+1}.$$

Taking $C=A$ gives $\#(B^{A})=n^{k}$.

Step 2: injections ((ii)). We show, by induction over the finite set $C$, that $\#\operatorname{Inj}(C,D)=(\#D)_{\#C}$ for every finite set $D$; the falling factorials are the values $(m)_{i}=F(m,i)$ of the map $F$ of Existence and Uniqueness of the Falling Factorials (i) (The Falling Factorial (i)).

Base. $\operatorname{Inj}(\emptyset,D)=\{\emptyset\}$ has one element, and $(\#D)_{0}=F(\#D,0)=1$ (Existence and Uniqueness of the Falling Factorials (i)).

Induction step. Let $C$ be finite with $j=\#C$, such that $\#\operatorname{Inj}(C,D)=(\#D)_{j}$ for every finite set $D$; let $x\notin C$ and $C'=C\cup\{x\}$, so $\#C'=j+1$. Let $D$ be a finite set.

Case $D=\emptyset$. There is no map $C'\to\emptyset$, since it would have a value at $x$; so $\operatorname{Inj}(C',\emptyset)=\emptyset$ has $0$ elements, and $(0)_{j+1}=F(0,j+1)=0$ (Existence and Uniqueness of the Falling Factorials (i)).

Case $D\neq\emptyset$. Choose $d_{0}\in D$ and put $n'=\#(D\setminus\{d_{0}\})$, so that $\#D=n'+1$ (Finite Sets: Removing an Element, Injective Self-Maps, Infinite Sets, Sets of Permutations, Pairs and Extended Tuples (i)). For every $b\in D$ the same clause gives $\#(D\setminus\{b\})+1=\#D=n'+1$, hence $\#(D\setminus\{b\})=n'$, which does not depend on $b$. Let $e:\operatorname{Inj}(C',D)\to D$ be evaluation at $x$, $e(\varphi)=\varphi(x)$, and fix $b\in D$. Restriction to $C$ is a bijection from the fibre $e^{-1}\{b\}=\{\varphi\in\operatorname{Inj}(C',D):\varphi(x)=b\}$ onto $\operatorname{Inj}(C,D\setminus\{b\})$ (Maps on a Set Enlarged by One Point (ii)). By the induction hypothesis, applied to the finite set $D\setminus\{b\}$, every fibre of $e$ therefore has $\#\operatorname{Inj}(C,D\setminus\{b\})=(n')_{j}$ elements (Counting through Bijections, Injections and Surjections (i)). By Counting by Fibres, Double Counting and the Pigeonhole Principle (iv) and the recursion $F(n'+1,j+1)=(n'+1)\,F(n',j)$,

$$\#\operatorname{Inj}(C',D)=(n')_{j}\cdot\#D=(n'+1)\,(n')_{j}=(n'+1)_{j+1}=(\#D)_{j+1}.$$

Taking $C=A$ and $D=B$ gives $\#\operatorname{Inj}(A,B)=(n)_{k}$.

Step 3: bijections ((iii)). If there is a bijection $\varphi:A\to B$, then $\#B=\#A$ (Counting through Bijections, Injections and Surjections (i)); so $\operatorname{Bij}(A,B)=\emptyset$ when $k\neq n$. Let now $k=n$. Every bijection is injective (Injective, Surjective and Bijective Functions between Classes (iii)), so $\operatorname{Bij}(A,B)\subseteq\operatorname{Inj}(A,B)$ (The Sets of Injections, Surjections and Bijections between Two Sets (iii), The Sets of Injections, Surjections and Bijections between Two Sets (i)). Conversely, let $\varphi:A\to B$ be injective. Its image $\varphi(A)\subseteq B$ has $\#\varphi(A)=\#A=n=\#B$ elements (Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iii)), so $\varphi(A)=B$ (Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iv)). Thus every element of $B$ is a value of $\varphi$, that is, $\varphi$ is surjective (Injective, Surjective and Bijective Functions between Classes (ii)), and hence bijective. So $\operatorname{Bij}(A,B)=\operatorname{Inj}(A,B)$, and by Step 2 and Properties of the Falling Factorial (i),

$$\#\operatorname{Bij}(A,B)=(n)_{n}=n!.$$

Step 4: permutations ((iv)). A set lies in $S_{n}$ exactly when it is a bijection $[n]\to[n]$ (Permutations of a Set and the Set of Permutations of [n] (iii)), that is, exactly when it lies in $\operatorname{Bij}([n],[n])$ (The Sets of Injections, Surjections and Bijections between Two Sets (iii)); so $S_{n}=\operatorname{Bij}([n],[n])$. Since $\#[n]=n$ (Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (i)), (iii) with $A=B=[n]$ gives $\#S_{n}=n!$.