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 \operatorname{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 \ne 0$, $u \ne 1$ and, adding $-1$ to $0 < 1$, also $u \ne -1$.

If $q$ is a list of primes of length $s \ne 0$ then $q_t \mid \prod_{j<s} q_j$, where $s = \sigma(t)$: indeed the product equals $\bigl(\prod_{j<t} q_j\bigr) 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 = \bigl(\prod_{i<r} p_i\bigr) 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 \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{id}_{\varnothing} \in \operatorname{Sym}(0)$ since $0 = \varnothing$, and the condition "$q_i = p_{\pi(i)}$ for all $i < 0$" is vacuous.

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

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

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

Also $q'_t = q_{\tau(t)} = q_k = p_r$, so $N = \prod_{j<\sigma(t)} q'_j = \bigl(\prod_{j<t} q'_j\bigr) q'_t = \bigl(\prod_{j<t} q'_j\bigr) p_r$.

Comparing with step 1.4, $\bigl(\prod_{i<r} p_i\bigr) p_r = \bigl(\prod_{j<t} q'_j\bigr) p_r$, and $p_r \ne 0$ by step 1.1, so cancellation gives $\prod_{i<r} p_i = \prod_{j<t} q'_j$.

The restrictions of $p$ to $r$ and of $q'$ 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 \operatorname{Sym}(r)$ with $q'_i = p_{\rho(i)}$ for every $i < r$.

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

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

For $i < \sigma(r)$ we get $q_i = q_{\tau(\tau(i))} = q'_{\tau(i)}$. If $\tau(i) < r$ then $q'_{\tau(i)} = p_{\rho(\tau(i))} = p_{\hat\rho(\tau(i))} = p_{\pi(i)}$; and if $\tau(i) = r = t$ then $q'_{\tau(i)} = q'_t = p_r = p_{\hat\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 \operatorname{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.