Proof of Existence and Uniqueness of the Falling Factorials

Throughout, every $k\in\mathbb{N}_{0}$ is $0$ or $j+1$ for some $j\in\mathbb{N}_{0}$, by Omega Is the Least Inductive Class: It Is a Set, Induction from Zero, the Peano Properties, and Transitivity (vii); maps on $\mathbb{N}_{0}$ are defined by recursion through The Recursion Theorem on Omega (i), read on $\mathbb{N}_{0}$ as in The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (ix); induction on $n$ is that of The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion (viii); $X=\mathbb{N}_{0}^{\mathbb{N}_{0}}$ is the set of maps from $\mathbb{N}_{0}$ to $\mathbb{N}_{0}$, a set by The Elements of the Class of Functions from a Set to a Set, and This Class Is a Set (ii); and the maps and the symbol $\sigma_{c}(r)$ formed below are predicative as in Routine Facts Used Without Citation: Arithmetic, Maps, Predicativity and Indices (iv). Since row $n+1$ of $F$ is determined by row $n$, the recursion is run on whole rows, that is, in $X$.

Shifting a row. Let $c\in\mathbb{N}_{0}$ and $r\in X$. The recursion theorem, applied with the set $\mathbb{N}_{0}$, the element $1$ and the map $(j,u)\mapsto c\,r(j)$ from $\mathbb{N}_{0}\times\mathbb{N}_{0}$ to $\mathbb{N}_{0}$, gives exactly one $z\in X$ with

$$z(0)=1\qquad\text{and}\qquad z(j+1)=c\,r(j)\quad\text{for every }j\in\mathbb{N}_{0}.$$

We write $\sigma_{c}(r)$ for this $z$. In the same way, with the element $1$ and the map $(j,u)\mapsto0$, there is exactly one $e\in X$ with $e(0)=1$ and $e(j+1)=0$ for every $j\in\mathbb{N}_{0}$.

Existence. Let $g:\mathbb{N}_{0}\times X\to X$ be the map $(n,r)\mapsto\sigma_{n+1}(r)$. The recursion theorem, applied with the set $X$, the element $e$ and the map $g$, gives a map $\Phi:\mathbb{N}_{0}\to X$ with

$$\Phi(0)=e\qquad\text{and}\qquad\Phi(n+1)=\sigma_{n+1}\bigl(\Phi(n)\bigr)\quad\text{for every }n\in\mathbb{N}_{0}.$$

Let $F:\mathbb{N}_{0}\times\mathbb{N}_{0}\to\mathbb{N}_{0}$ be the map $(n,k)\mapsto\Phi(n)(k)$. Then $F(0,0)=e(0)=1$ and $F(n+1,0)=\sigma_{n+1}(\Phi(n))(0)=1$, so $F(n,0)=1$ for every $n$. Next, $F(0,k+1)=e(k+1)=0$. Finally,

$$F(n+1,k+1)=\sigma_{n+1}\bigl(\Phi(n)\bigr)(k+1)=(n+1)\,\Phi(n)(k)=(n+1)\,F(n,k).$$

Uniqueness. Let $F':\mathbb{N}_{0}\times\mathbb{N}_{0}\to\mathbb{N}_{0}$ satisfy the same three conditions. We show by induction on $n$ that $F'(n,k)=F(n,k)$ for every $k\in\mathbb{N}_{0}$. For $n=0$: $F'(0,0)=1=F(0,0)$ and $F'(0,j+1)=0=F(0,j+1)$. If the claim holds for $n$, then $F'(n+1,0)=1=F(n+1,0)$ and

$$F'(n+1,j+1)=(n+1)\,F'(n,j)=(n+1)\,F(n,j)=F(n+1,j+1),$$

so it holds for $n+1$. Hence $F'$ and $F$ are maps on $\mathbb{N}_{0}\times\mathbb{N}_{0}$ with the same values, and $F'=F$.