(related to Lemma: The Proving Principle by Complete Induction)
The following proof does without the Peano axioms. Instead, it uses the well-ordering principle of set-theoretical definition of natural numbers. * Let a premise $p(n)$ be given which can be proven by the principle of complete induction to be true for all natural numbers $n\ge m,$ given some base case natural number $m.$ * Assume, the set $N$ of all natural numbers $k\ge m,$ for which the premise $p(k)$ is false is not empty, $N\neq\emptyset.$ * Because of the well-ordering principle, $N$ contains a minimum $k_0.$ * But then $p(m)$ was true for all $m < k_0,$ which is a contradiction to the minimality of $k_0.$