14
$\begingroup$

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?

  • 1
    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.)2011-04-30
  • 2
    @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 +.2011-04-30
  • 0
    @Chris Eagle: Why is the definition of the Square in the even case not recursive in this sense? (It is quite likely that I overlook something obvious, but I don't see it.)2011-04-30
  • 2
    @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.2011-04-30
  • 2
    @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.2011-04-30
  • 0
    It reminds me of a question in the course I TA'ed last semester. Given the structure $\mathbb N$ with $+$ as a binary operation, define $\le$ and $\times$ as first order formulae. The $\le$ is very easy, the $\times$ was extremely long and hard.2011-04-30
  • 0
    Asaf, wouldn't the ability to define × mean that every Peano formula can be encoded as a Presburger formula? But Presburger arithmetic is complete.2011-04-30
  • 1
    @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).2011-04-30
  • 0
    @Dan: If I recall correctly, user6312's answer below contains one of the possible solutions. The professor whom with I worked said he had written the exercise as a TA back in the '70s.2011-04-30
  • 0
    FWIW, it’s always struck me as cool that multiplication can be, essentially, defined in terms of squaring, in that all you need besides squaring is ‘trivial’ extra operations of addition, subtraction, and halving. Here is the proof: xy = (((x + y)^2 – (x – y)^2)/2)/2.2017-05-13

4 Answers 4

16

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.

  • 3
    What divisibility axioms are needed for the system to be equivalent to PA?2011-04-30
  • 1
    @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.2011-04-30
  • 0
    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?2011-04-30
  • 1
    @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.2011-05-01
7

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.
  • 0
    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?2012-02-21
  • 0
    @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.2012-02-21
  • 0
    I see, thanks. Interesting, I didn't know about self-verifying theories.2012-02-21
0

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

  • 1
    By $\rm lcm(x,y) gcd(x,y)$ do you mean the product of $\rm lcm(x,y)$ and $\rm gcd(x,y)$ ?2011-04-30
  • 0
    aaa: Yes, what Gerry gave is an identity.2011-04-30
  • 3
    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?2011-04-30
  • 2
    I don't feel strongly about leaving or deleting, but I certainly learned something from reading it and the comments.2011-04-30
  • 0
    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.2011-05-01
  • 0
    Please leave this answer. It's a nice reminder that, as they say in chess culture, even a master blunders now and then.2017-05-13
0

Julia Robinson in her paper (1949), define multiplication in terms of the relation of divisibility and the successor operation. You can see this in MathSciNet.