The fundamental theorem of arithmetic: every integer $n\ge 1$ is a product of primes, and the factorisation is unique up to order — if ${\prod }_{i<r}{p}_i={\prod }_{j<s}{q}_j$ with every $p_i$ and $q_j$ prime, then $r=s$ and $q_i=p_{\pi (i)}$ for some $\pi \in \mathrm{Sym}(r)$

$0<1$: $1=\iota (1)$ is nonnegative and differs from $0=\iota (0)$ by injectivity of $\iota$. Hence every prime $u$ satisfies $u>1>0$, so $u\mathrm{\ne }0$, $u\mathrm{\ne }1$ and, adding $-1$ to $0<1$, also $u\mathrm{\ne }-1$.

If $q$ is a list of primes of length $s\mathrm{\ne }0$ then $q_t\mid {\prod }_{j<s}{q}_j$, where $s=\sigma (t)$: indeed the product equals $\left({\prod }_{j<t}{q}_j\right)q_t$.

Let $r\in \mathbb{N}$ and assume $U(r)$.

Let $p$ be a list of primes of length $\sigma (r)$ and $q$ one of length $s$, with $N:={\prod }_{i<\sigma (r)}{p}_i={\prod }_{j<s}{q}_j$. Then $N=\left({\prod }_{i<r}{p}_i\right)p_r$, so $p_r\mid N$.

A prime never divides $1$: $u\mid 1$ would force $u=1$ or $u=-1$, both excluded by step 1.1.

By [L3] there is $k<s$ with $p_r\mid q_k$. Since $p_r>1>0$, $p_r$ is a positive divisor of the prime $q_k$ other than $1$, so $p_r=q_k$.

$U(0)$ holds. Let $q$ be a list of primes of length $s$ with ${\prod }_{i<0}{p}_i={\prod }_{j<s}{q}_j$, so ${\prod }_{j<s}{q}_j=1$. If $s\mathrm{\ne }0$, then $s=\sigma (t)$ and step 1.2 gives $q_t\mid 1$, contradicting step 2.1; so $s=0$. Then $r=s=0$, ${\mathrm{i}\mathrm{d}}_{\mathrm{\varnothing }}\in \mathrm{Sym}(0)$ since $0=\mathrm{\varnothing }$, and the condition "$q_i=p_{\pi (i)}$ for all $i<0$" is vacuous.

$s\mathrm{\ne }0$: otherwise $N=1$ and $p_r\mid 1$, contradicting step 2.1. Write $s=\sigma (t)$.

Define $\tau \in \mathrm{Sym}(s)$ by $\tau :={\mathrm{i}\mathrm{d}}_s$ if $k=t$ and $\tau :=(kt)$ otherwise; in both cases $\tau$ is a permutation of $s$ with $\tau \circ \tau ={\mathrm{i}\mathrm{d}}_s$ and $\tau (t)=k$. Note $t<s$ and $k<s$, so both lie in $s$.

Put $q_j^{\mathrm{\prime }}:=q_{\tau (j)}$ for $j<s$; every $q_j^{\mathrm{\prime }}$ is prime, and ${\prod }_{j<s}{q}_j^{\mathrm{\prime }}={\prod }_{j<s}{q}_j=N$ by the commutative clause [L2], the monoid $(\mathbb{Z},\cdot ,1)$ being commutative.

Also $q_t^{\mathrm{\prime }}=q_{\tau (t)}=q_k=p_r$, so $N={\prod }_{j<\sigma (t)}{q}_j^{\mathrm{\prime }}=\left({\prod }_{j<t}{q}_j^{\mathrm{\prime }}\right)q_t^{\mathrm{\prime }}=\left({\prod }_{j<t}{q}_j^{\mathrm{\prime }}\right)p_r$.

Comparing with step 1.4, $\left({\prod }_{i<r}{p}_i\right)p_r=\left({\prod }_{j<t}{q}_j^{\mathrm{\prime }}\right)p_r$, and $p_r\mathrm{\ne }0$ by step 1.1, so cancellation gives ${\prod }_{i<r}{p}_i={\prod }_{j<t}{q}_j^{\mathrm{\prime }}$.

The restrictions of $p$ to $r$ and of $q^{\mathrm{\prime }}$ to $t$ are lists of primes of lengths $r$ and $t$, and their products are the two sides of step 7.1, since a finite product depends only on the entries it names. So $U(r)$ applies: $r=t$, hence $s=\sigma (t)=\sigma (r)$, and there is $\rho \in \mathrm{Sym}(r)$ with $q_i^{\mathrm{\prime }}=p_{\rho (i)}$ for every $i<r$.

Define $\widehat{\rho }:\sigma (r)\to \sigma (r)$ by $\widehat{\rho }(i):=\rho (i)$ for $i<r$ and $\widehat{\rho }(r):=r$. Since $\sigma (r)=r\cup \{r\}$ with $r\mathrm{\notin }r$, and $\rho$ is a bijection of $r$, the map $\widehat{\rho }$ is a bijection of $\sigma (r)$, that is $\widehat{\rho }\in \mathrm{Sym}(\sigma (r))$.

Put $\pi :=\widehat{\rho }\circ \tau$, a permutation of $s=\sigma (r)$ because $\mathrm{Sym}(\sigma (r))$ is closed under composition.

For $i<\sigma (r)$ we get $q_i=q_{\tau (\tau (i))}=q_{\tau (i)}^{\mathrm{\prime }}$. If $\tau (i)<r$ then $q_{\tau (i)}^{\mathrm{\prime }}=p_{\rho (\tau (i))}=p_{\widehat{\rho }(\tau (i))}=p_{\pi (i)}$; and if $\tau (i)=r=t$ then $q_{\tau (i)}^{\mathrm{\prime }}=q_t^{\mathrm{\prime }}=p_r=p_{\widehat{\rho }(r)}=p_{\pi (i)}$. Since $\tau (i)<\sigma (r)$ these two possibilities are exhaustive, so $q_i=p_{\pi (i)}$ throughout.

Steps 8.1 and 11.1 give $s=\sigma (r)$ and a permutation $\pi \in \mathrm{Sym}(\sigma (r))$ with $q_i=p_{\pi (i)}$ for all $i<\sigma (r)$, so $U(\sigma (r))$ holds; with step 3.1 as base, induction gives $U(r)$ for every $r\in \mathbb{N}$, which is clause 2. Clause 1 is Every integer $n\ge 1$ is a finite product of primes: there are $r\in \mathbb{N}$ and a list $p:r\to \mathbb{Z}$ of primes with $n={\prod }_{i<r}{p}_i$, the case $n=1$ being the empty product.