# Why Does Induction Prove Multiplication is Commutative?

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?

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?

-
I don't understand the "why" of your question. Consider 2 x 2 matrices. What do you propose to define as the successor relationship (from which you then define addition and multiplication)? What is the successor of 0? I imagine a first-order version cannot prove multiplication is commutative. –  abo Feb 17 '13 at 9:02
Question from a bystander. I don't understand your successor axiom. Is it not a consequence of the general axioms of equality? –  Joël Feb 18 '13 at 1:43
If $S$ is meant to be a function symbol in first-order logic, then I agree with Joël that the displayed axiom follows from the axioms for equality. Following the link to Boucher's text, however, it seems that for GA he wants the axiom he calls PA3, which seems to assert that successor is functional (formalized as a binary relation giving the graph). –  Joel David Hamkins Feb 18 '13 at 2:40
Regarding your edit, Russell, isn't it clear that every countable set (whether finite or infinite) admits a successor function for which induction holds? Just pick a $0$, and then define $S(x)$ so that the $n^{th}$ element of the ring is $S^n(0)$. This will satisfy induction for the same reason that $\mathbb{N}$ satisfies induction. But of course, this $S$ will not interact with the ring operations meaningfully, and in the non-commutative case it cannot agree so as to make multiplication agree with the usual recursion, since then the inductive argument would make that operation commutative. –  Joel David Hamkins Feb 18 '13 at 22:23
Matrix addition and multiplication satisfy all of the axioms of Ring Theory (RT). Non-commutative rings are not models of RT+Ind where Ind is first order induction. Abo gives an example of a phi(x) we can prove using induction that is false in matrix arithmetic. –  Russell Easterly Feb 19 '13 at 4:07

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.

-
$\forall x(Sx=x+S0)$ is a theorem of PA and weaker theories. I don't know if it is a theorem of GA2. I am interested in theories of arithmetic where induction fails. It looks like finite non-commutative rings are models of ring theory + Not(Ind) + $\forall x(Sx=x+1)$. –  Russell Easterly Feb 20 '13 at 2:19
It's actually not quite a theorem of GA2 because you don't know that the successor of x exists. But it can be proven, if the successor of x exists, then it equals x + S0. Yes, finite non-commutative rings would be models of that theory. –  abo Feb 20 '13 at 6:22

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.

-

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.

-
I think GA2 is strong enough to prove if x has a successor then $Sx = x+S0$. I know ring theory proves this. Once we call some element 0 and some element 1 we have no choice on how successor is defined. I know nothing about non-commutative rings, but I assume they satisfy GA2's very weak successor axiom using matrix addition. –  Russell Easterly Feb 18 '13 at 5:25
OK, let the zero matrix be 0 and the identity matrix I (1's on the diagonal and 0's elsewhere) be the successor of 0. And define Sx to be x + I. Then S0 = I and SS0 = 0. So the successoring chain starting from 0 only includes two elements, {0,I}, and not the whole ring. You therefore cannot conclude that multiplication is commutative on the whole ring. –  abo Feb 18 '13 at 6:28
This still satisfies the successor axiom. An element doesn't even have to have a successor in GA2. –  Russell Easterly Feb 18 '13 at 9:20
Yes it does satisfy the successor axiom. But the problem is that with this definition of successor all the GA2 axioms do not hold, because induction does not hold. Why doesn't it? Define e.g. the predicate phi to be (n = 0 v n = S0). Then phi(0), and if phi(n), then phi(Sn), by a very simple argument on cases. But it's not true that every element in the ring is 0 or S0. So induction doesn't hold. Because induction doesn't hold for 2x2 matrices over {0,1} with this definition of successor, you can't use the results about GA2 to infer that matrix multiplication is commutative. –  abo Feb 18 '13 at 18:56