Suppose not. Then the set \(S\) of positive integers not having a prime factorization is nonempty. So, by the well-ordered axiom, Axiom 1.3, there exists a smallest element \(n\in S\). We’ve seen that \(1\) has a prime factorization, namely, the empty list or primes \([]\). So \(n {\gt} 1\). Obviously, \(n\) can’t be prime: otherwise \([n]\) would be a prime factorization of \(n\). As \(n {\gt} 1\) and \(n\) is not prime, \(n\) must be composite. Therefore \(n = ab\) with \(1 {\lt} a\le b {\lt} n\). As \(n\) is, by assumption, the smallest positive integer without a prime factorization, \(a\) and \(b\) both have prime factorizations \([p_1,\ldots , p_r]\) and \([q_1,\ldots , q_s]\) respectively. So

Sorting the list \([p_1,\ldots , p_r, q_1,\ldots , q_s]\) to arrange the elements in order, we get a prime factorization of \(n\). As this contradicts our assumption that \(n\) is the smallest integer without a prime factorization, Proposition 1.7 is proved.