3
$\begingroup$

How do you prove commutativity of multiplication using peano's axioms.I know we have to use induction and I have already proved n*1=1*n.But I cant think of how to prove the inductive step.

$\endgroup$
1
  • 1
    $\begingroup$ I believe the real trick here is to choose your induction variable wisely. You have chosen to fix $n$ and prove that $n\cdot i = i \cdot n$ by induction on $i$. This might not be the easy approach. Two other approaches that stand out are to use induction on $n$ where the induction hypothesis is that $i\cdot j = j \cdot i$ for all $i, j$ with $i + j \leq i$, or alternatively for all $i, j$ with $\max\{i, j\} \leq n$. I would probably go for the diagonal case, together with what you already know (that $n\cdot 1 = 1 \cdot n$). $\endgroup$
    – Arthur
    May 23, 2014 at 15:15

3 Answers 3

5
$\begingroup$

Show that if an operator $\star$ satisfies the defining equations for multiplication, i.e. $0 \star n = 0$ and $(m + 1)\star n = n + m \star n$, then $\star$ is multiplication (this is a straightforward induction).

Then show that the operator defined by $m \star n = n \times m$ satisfies the defining equations for multiplication, and therefore $m \star n = m \times n$, so $n \times m = m \times n$.

That is, show that $n \times 0 = 0$ and $n \times (m + 1) = n + n \times m$, and you're done.

Unfortunately, that's just not easy. $n \times 0 = 0$ is not too bad, you can use induction on $n$, but the only proof I have of the latter statement uses the associativity and commutativity of addition, which both have to be proven by induction as well.

$\endgroup$
2
$\begingroup$

Honestly, proving this using Peano's axioms is not very educational, however logically valid it may be. After pondering this question for too long a while, I finally just sat down and wrote out a proof which I haven't been able to find anywhere. Here it is:

First we need the definition of multiplication for natural numbers (which nearly nobody actually knows). For any two natural numbers $n$ and $m$, $n*m$ $\space$:= $\space$ $\underbrace{n+n+...+n}_m$ , and this definition is crucial to a structured view of mathematics. Now, by removing 1 from each summand and summing all those removals into a new summand, since there are $m$ summands, we obtain $\underbrace{(n-1)+(n-1)+...+(n-1)}_m + m$ , then, repeating the process with the old summands, we obtain $\underbrace{(n-2)+(n-2)+...+(n-2)}_m + m + m$, and we keep repeating the process until we obtain $\underbrace{(n-n)+(n-n)+...+(n-n)}_m + \underbrace{m + m+...+m}_n$ , which will happen because n is finite, and this result is identically $\underbrace{0+0+...+0}_m + \underbrace{m + m+...+m}_n$ $\space$ = $\space$ $0 + \underbrace{m + m+...+m}_n$ $\space$ = $\space$ $\underbrace{m + m+...+m}_n$ $\space$ = $\space$ $m*n$ $\space \implies \space n*m$ = $m*n$ .

That proves multiplicative commutativity for any particular choice of $n$ and $m$. To prove multiplicative commutativity for ALL choices of $n$ and $m$, we must show that $(n+1)*m$ = $m*(n+1)$, $\space$ $n*(m+1)$ = $(m+1)*n$,$\space$ and $(n+1)*(m+1)$ = $(m+1)*(n+1)$ $\space$ (the "for ALL" generality follows by recursion).

I created this account just to answer your question, so I hope you like that response.

$\endgroup$
4
  • $\begingroup$ This isn't responsive to the question, and it is kind of deranged to think that it is useful to answer a question by using a definition that "nearly nobody actually knows" (not sure you really think that, though). You might as well answer a question about how to prove something in geometry using Hilbert's version of Euclid's axioms by giving a response that uses coordinates. $\endgroup$
    – C Monsour
    May 12, 2018 at 5:37
  • $\begingroup$ I realize this doesn't answer the question, I guess I got too excited. However, this is a much more useful response. I do believe that so few people know the definition of natural number multiplication because everybody I've ever asked doesn't know it, including PhD math professors conducting research, and almost everyone responds with ignorant dismissal, claiming the definition is arbitrary. What they're really saying is that they'd rather memorize math than make sense of it. I'm here exclaiming that this definition is very significant because it is useful and insightful. $\endgroup$
    – Joseph Z
    May 12, 2018 at 6:00
  • $\begingroup$ No one who is asking how to prove something from Peano's axioms is preferring memorization to understanding. $\endgroup$
    – C Monsour
    May 12, 2018 at 6:02
  • $\begingroup$ Thanks, Joseph; I enjoyed your answer. Not sure why the other commenter appears to be infuriated at you. Doesn't seem very nice. $\endgroup$
    – Owl
    May 10, 2021 at 23:05
0
$\begingroup$

Using the following Peano-like axioms to define + (addition), · (multiplication) and 1, where x and y are variables of type natural number and S denotes the successor function: (Note: Ax. is an abbreviation for "Axiom".)

Ax. x + 0 = x
Ax. x + S(y) = S(x + y)

Ax. x · 0 = 0
Ax. x · S(y) = x + x · y

Ax. 1 = S(0)

One may then prove that · is commutative by first establishing the following theorems:

Th. (0) S(x) = x + 1 (does not require induction)
Th. (1) + is commutative (i. e. x + y = y + x)
Th. (2) 0 · x = 0
Th. (3) 1 is a left identity of · (i. e. 1 · x = x)
Th. (4) · right-distributes over + (i. e. (x + y) · z = x · z + y · z)

Theorem (1) can be proved easily by induction over y if you first establish the theorems 0 + x = x and S(x) + y = S(x + y). (Which may both be shown by induction) Theorem (4) may be proved by induction over z. (Just saying in case it is not evident.)

And then the proof of multiplication's commutativity by induction over y can go like this: (Hints for the justifications of each successive manipulation are indicated between curly brackets.)

The base case: x · 0 = 0 · x

    x · 0
= { First multiplication axiom }
    0
= { Theorem (2) }
    0 · x

Now, by postulating that the induction hypothesis x · y = y · x is true for some natural number y, we may prove that x · S(y) = S(y) · x is implied:

    x · S(y)
= { Second multiplication axiom }
    x  +  x · y
= { Induction hypothesis }
    x  +  y · x
= { Theorem (3) }
    1 · x  +  y · x
= { Theorem (4) }
    (1 + y) · x
= { Theorems (1) and (0) }
    S(y) · x

And that completes the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.