Why Does Induction Prove Multiplication is Commutative?

Question

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?

Answer 1

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.

Answer 2

I am not familiar with GA2, but this is how one can prove that multiplication is commutative in PA, and it seems not to use very much.

I assume that multiplication is defined by recursion, so that $x\cdot 0=0$ and $x\cdot(y+1)=x\cdot y+x$. Let me also assume that you already know that addition is associative and commutative.

We prove that multiplication is commutative by proving that every $x$ commutes with every $y$, by induction on $x$. It is not difficult to prove that $0\cdot y=0=y\cdot 0$, and so it is true for $x=0$. Now, suppose that $x$ commutes with all $y$, and consider $x+1$. This commutes with $0$, so assume it commutes with $y$, and observe that

$$(x+1)(y+1)=(x+1)y+(x+1)$$

$$ =y(x+1)+x+1$$ $$ =yx+y+x+1$$ $$ =y+yx+x+1$$ $$ =y+xy+x+1$$ $$ =y+x(y+1)+1$$ $$ =y+(y+1)x+1$$ $$ =(y+1)x+y+1$$ $$ =(y+1)(x+1),$$ as desired. At each step, we either use the definition of multiplication, the induction assumption on $x$ or the induction assumption on $y$, with $x+1$. Altogether, it can be unified as one induction on pairs $(x,y)$ under the lexical order.

Answer 3

This is not an answer to your question but, I hope, an answer to your confusion.

Consider 2 x 2 matrices whose elements are from the set {0,1}. Endowed with the usual addition and multiplication, the set of such matrices forms a non-commutative ring.

Now there are a finite number of elements in this set, 16 in all, so one can define a successor function arbitrarily, by choosing a first element, then a next, and so on, and touching every element in the set. For instance, one can define:

$$\mathrm{S}\begin{bmatrix}0&0\\0&0\end{bmatrix}=\begin{bmatrix}0&1\\0&0\end{bmatrix}$$ $$\mathrm{S}\begin{bmatrix}0&1\\0&0\end{bmatrix}=\begin{bmatrix}0&0\\1&0\end{bmatrix}$$ $$\mathrm{S}\begin{bmatrix}0&0\\1&0\end{bmatrix}=\begin{bmatrix}0&0\\0&1\end{bmatrix}$$ $$\mathrm{S}\begin{bmatrix}0&0\\0&1\end{bmatrix}=\begin{bmatrix}1&0\\0&0\end{bmatrix}$$ $$...$$ $$\mathrm{S}\begin{bmatrix}1&1\\1&1\end{bmatrix}=\begin{bmatrix}0&0\\0&0\end{bmatrix}$$

Now, if one uses this definition of succession, then the axioms of GA will hold, because (1) as we've said this successoring is a function; and (2) because every element has been included in the successoring chain, induction holds. However, the addition (call it ++) which is induced by this successoring is not normal matrix addition (call this +). For instance

$$\begin{bmatrix}0&1\\0&0\end{bmatrix}+\begin{bmatrix}0 &1\\0&0\end{bmatrix}=\begin{bmatrix}0&0\\0&0\end{bmatrix}$$

while

$$\begin{bmatrix}0&1\\0&0\end{bmatrix}++\begin{bmatrix}0&1\\0&0\end{bmatrix}=\begin{bmatrix}0&0\\1&0\end{bmatrix}$$

Similarly the multiplication induced by this successoring is not normal matrix multiplication. You will find that the induced multiplication is in fact commutative, while (of course) matrix multiplication is not.