On the (In)Dependence of the Peano Axioms for Natural Numbers

We investigate two notions of independence—(usual) independence and complete independence—applied to the Peano axioms for the sequence of natural numbers. We review the results that, although they are independent, the Peano axioms are not completely independent. The standard proof that the Peano axioms are not completely independent is algebraic, in the sense that it makes essential reference to the relationship between several mathematical structures that satisfy, or do not satisfy, these axioms. We then present an alternative logical proof, which makes no essential references to the relationship between mathematical structures. There is a completely independent set of axioms for the sequence of natural numbers, but it is based on primitives different from those originally adopted by Peano. Therefore, we present a new completely independent set of axioms based on the same set of primitives as the one originally adopted by Peano.