Zero divisors and the Peano Axioms

85 Views Asked by At

Using the Peano axioms, how can it be proven that the only zero divisor of the natural numbers is $0$ (or there is no zero divisor depending on your definition).

Can it even be done? Do new axioms need to be introduced?

Namely, how can the Peano axioms be using to prove that $ab = 0 \implies a = 0 \lor b = 0$, where $a$ and $b$ are natural numbers?

1

There are 1 best solutions below

1
On BEST ANSWER

This is one of the few cases where we can (almost!) prove an interesting general fact in Peano Arithmetic without using induction.

The recursion equations that define $+$ and $\times$ immediately unfold to $$ \forall x,y: S(x)\times S(y) = S(S(x)\times y + x)$$ and since another axiom says that $0$ is not a successor this gives $$ \forall x,y: S(x) \times S(y) \ne 0 $$

To get from here to $m\times n = 0 \to m=0 \lor n=0$ you just need the fact that everything is either zero or a successor. That final fact does require induction. (But this induction is literally the first application of the induction axiom in every development of Peano arithmetic I remember reading.)