Can multiplication be defined in terms of divisibility?
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?
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.
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:
- 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);
- 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.