[Math] Why Does Induction Prove Multiplication is Commutative

ac.commutative-algebrainductionpeano-arithmetic

Andrew Boucher's General Arithmetic (GA2) is a weak sub-theory of second order Peano Axioms (PA2). GA has second order induction and a single successor axiom:

$$\forall x \forall y \forall z\bigr((Sx=y \land Sx=z)\to(y=z)\bigl)$$

Boucher proves multiplication is commutative in GA2. Why does induction prove multiplication is commutative? GA2 has many finite models. The rings $\mathbb Z/n\mathbb Z$ are models. If we remove induction from GA2 it is easy to see GA-Ind is sub-theory of Ring Theory (RT). RT has finite non-commutative models. Why aren't these finite non-commutative rings models of GA? Would a first order version of GA also prove multiplication is commutative?

I asked on stack exchange and got no answer. https://math.stackexchange.com/questions/287557

Edit: I am not looking for an inductive proof. This is a standard result and I am sure it can be done. I am more interested in something like abo's explanation. Can we prove induction fails in every non-commutative ring? Is it impossible to define a successor chain that visits every ring element using addition in a non-commutative ring?

Best Answer

This is an answer to the edited questions Russell has added. Joel David Hamkins' reply in comments to the question is completely correct, but I'll take advantage of the greater space here.

Let (R,0,1,+,*) be a ring. Define

Sx = x + 1 and

B = {x | $\forall P(P0 \land \forall y\forall z(Py \land Sy,z \to Pz) \to Px)$}

i.e. B is the set of all x which are part of an S-chain beginning with 0.

Then S is functional and induction holds over B, i.e.

$\forall P(P0 \land \forall y\forall z(Py \land Sy,z \to Pz) \to \forall x (Bx \to Px))$.

One can define ++ and ** (both definitions being on B) from S using the normal recursive definitions, both of which can be proved commutative. By induction over B, one can show that + and ++ define the same function on B; also for * and **. Hence, if B = R, then * is commutative. So if R is a non-commutative ring, then B is properly contained in R.

"Can we prove induction fails in every non-commutative ring?" No. There are definitions of the successor function (see my other answer) so that induction will hold. OTOH, in a non-commutative ring R where the successor is defined as Sx = x + 1, induction will fail, because the set B (as defined above) cannot equal all of R. To see that induction fails, consider the predicate phi(n) to be Bn. Then clearly phi(0) and the inductive step holds, but obviously not phi(n) for all n in R.

"Is it impossible to define a successor chain that visits every ring element using addition in a non-commutative ring?" I'm not sure what you mean by this question. If successoring is defined by Sx = x + 1, then the successor chain isn't defined, it's implied (by the definition). You won't be able to prove that the successor chain is the entire ring, because again that would imply that multiplication is commutative, contrary to assumption.