Take the 2-minute tour ×

Peano Arithmetic has two axioms which use the multiplication symbol: ∀x:x*0=0 and ∀x:∀y:x*Sy=x+x*y. The 2-term relation "x divides y" can be expressed as D(x,y) := ∃z:z*x=y. Multiplication is a function and divisibility is a relation, so in order to compare apples and apples, consider the 3-term relation M(x,y,z) := x*y=z and the axioms ∀x:M(x,0,0) and ∀x:∀y:∃u:∃v:M(x,Sy,u)∧M(x,y,v)∧v+x=u and also the fact that M is a function ∀x:∀y:∀u:∀v:(M(x,y,u)∧M(x,y,v))→u=v. Now D can be defined in terms of M by D(x,y) := ∃z:M(z,x,y). I wonder if it is possible to do the reverse, and define multiplication in terms of divisibility. If the M axioms are replaced by some D axioms (maybe ∀x:D(x,x), ∀x:D(x,0), and others), can M be expressed in terms of D? Prime, GCD, LCM can all be defined in terms of D alone, but I don't know how to define M in terms of D, nor do I know how to axiomatize D without reference to M. If it is possible, what axioms are required for the divisibility relation, and how is the multiplication relation defined? If not, why not?

share|improve this question
But what does this question really mean? How can you tell that the answer of user6312 does not implicitly repeat the standard definition of multiplication by using it for $s^2-1$? (Note that I like the answer by user6312, I just want to point out that it is not at all clear what "define M in terms of D" means since the expressions + and S of the usual definition of "M" are allowed.) –  Phira Apr 30 '11 at 7:44
@user9325: I think the point is that we're working in first-order PA, so the recursive definition of M from + and S doesn't work, but you can define M from D and +. –  Chris Eagle Apr 30 '11 at 9:20
@Chris Eagle: It wasn't recursive to begin with, but I changed it so that it doesn't even look recursive. The issue is: if we have addition and a binary predicate for divisibility, can we build a first-order formula for the predicate $z=xy$? And we can. –  André Nicolas Apr 30 '11 at 10:39
@user9325: There is no "usual definition" of multiplication in first-order arithmetic. The language has a constant symbol $0$, and two binary function symbols $+$ and $\times$. We also have $=$, and the usual logical connectives and quantifiers. Then there is a collection of axioms formulated in this language. No more. –  André Nicolas Apr 30 '11 at 10:56
@Dan: It seems the late hour has struck my memory. The language had a "Reminder(a,b)" operator which returns $a\bmod b$, and $0$ when $b=0$. It did not, however, have addition. That needed to be defined (also not hard if you already have $\le$, as $a+b$ is the smallest number greater than both $a$ and $b$ such that $a+b = a\bmod b$ and $a+b = b\bmod a$ (could be formulated in other ways too). –  Asaf Karagila Apr 30 '11 at 21:40

3 Answers 3

up vote 14 down vote accepted

My answer is couched in informal terms, largely in order to make typing less tedious. I assume that you have enough experience to turn the answer into a formal one. The downside of doing that is that it would make the thing look more complicated than it really is. In producing the definition, I make no attempt at efficiency.

Suppose that we have produced a definition from divisibility of the relation $\text{Square}(s,t)$, where $\text{Square}(s,t)$ means "$t$ is the square of $s$."

Then we can readily produce a definition of of your $\text{M}(x,y,z)$ by using the fact that $(x+y)^2=x^2+ 2xy + y^2$.

Indeed $\text{M}(x,y,z)$ if and only if there exist $u$, $v$, and $w$ such that $\text{Square}(x,u)$ and $\text{Square}(y,v)$ and $\text{Square}(x+y,w)$ and $w=u+z+z+v$.

Now we want to define the relation $\text{Square}(s,t)$ from divisibility. Note that $s$ and $s+1$ are relatively prime, so $s^2+s$ is the LCM of $s$ and $s+1$. Thus $t=s^2$ precisely if there exists $u$ such that $u$ is the LCM of $s$ and $s+1$, and $s+t=u$.

The LCM is easily handled using only divisibility, so that's all there is to it.

share|improve this answer
What divisibility axioms are needed for the system to be equivalent to PA? –  Dan Brumleve Apr 30 '11 at 8:39
@Dan Brumleve: We could cheat by rewriting the usual axioms in terms of the new predicate. But you are asking about natural divisibility axioms. Nice question. I don't have an answer. –  André Nicolas Apr 30 '11 at 10:47
So let's just rewrite the two M axioms in terms of D. But now we have D'(x,y) := ∃z:M(z,x,y). Is it possible to prove that ∀x:∀y:D'(x,y)↔D(x,y)? If not, can we just add that statement as an axiom also? –  Dan Brumleve Apr 30 '11 at 19:43
@Dan Brumleve: Need to say formula $M$ is "functional." You mentioned two $M$ axioms. You forgot the infinitely many instances of the induction scheme, whose relativizations to $M$ would have to be added. I expect that would give so much rigidity that your "$D(x,y)$" assertion would be a theorem. If it sn't, no problem, add it. It would be interesting to see what could be done more naturally. Probably lying in forgotten theses. For adequate power, we cannot avoid an induction scheme. –  André Nicolas May 1 '11 at 12:41

No, not in general. You can define the multiplication relation in terms of the division function, but this only gives you a truth condition M(x,y,z) that tells you if z is the product of x and y. It does not give you a mechanism for generating the z from the x and y: for that you need to be able to prove that the multiplication relation specifies a total function.

And this is not always possible:

  1. There are weak theories of arithmetic for which division is total, but where, although the multiplication relation exists, and specifies the expected triples, the relation cannot prove the multiplication is total (and so admits nonstandard models in which there are multiplication relations but all have "holes" at nonstandard number parameters and so are not functions);
  2. Even worse, there are such weak theories which would be rendered inconsistent by the addition of an axiom asserting that multiplication was a total function. All self-verifying theories are of this sort.
share|improve this answer
In which sense do you mean "specifies the expected triples [but] does not determine a total function"? The expected triples are such that a relation containing exactly them would be total function. Do you mean that the theory can't prove that this is a total function? –  joriki Feb 21 '12 at 8:56
@joriki: Of course the standard model has all the usual theorems of arithmetic. I guess my wording is a little unclear here and should be fixed: I mean that because multiplication is not provably total in such theorems, the theory does not "fix" multiplication to be something total, i.e., there are nonstandard models in which it is not. –  Charles Stewart Feb 21 '12 at 10:58
I see, thanks. Interesting, I didn't know about self-verifying theories. –  joriki Feb 21 '12 at 11:48

$xy={\rm lcm}(x,y)\times\gcd(x,y)$, so if you can define lcm and gcd, can't you define product?

share|improve this answer
By $\rm lcm(x,y) gcd(x,y)$ do you mean the product of $\rm lcm(x,y)$ and $\rm gcd(x,y)$ ? –  aaa Apr 30 '11 at 8:21
aaa: Yes, what Gerry gave is an identity. –  Ｊ. Ｍ. Apr 30 '11 at 8:32
I've edited to clarify. But I've also realized that I'm being silly - the formula shows if you have lcm, gcd, and product, then you can get product, not a very useful observation. Should I delete it? or leave it up as a warning? –  Gerry Myerson Apr 30 '11 at 9:46
I don't feel strongly about leaving or deleting, but I certainly learned something from reading it and the comments. –  Phira Apr 30 '11 at 10:29
Gerry: It is a lot easier to define the multiplication of two co-prime numbers, for example lcm+1 and the gcd, then define the multiplication as the number such that when added the gcd equals that co-prime multiplication. –  Asaf Karagila May 1 '11 at 18:30

Your Answer


