Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

One might define multiplication $\bullet$ on $\mathbb Z$ as follows:

$\bullet: \mathbb Z\times \mathbb N\ni (a,b) \mapsto a+\cdots+a\in \mathbb Z$ where we add $b$ times.

But suppose we are in a universe where we can only multiply. How would one define addtion, or could one even define it?

Silly approach 1: $\log(e^ae^b)=\log(e^{a+b})=a+b$, but this assumes existence of $\log$ and $e$ and is rather unsatisfying.

Approach 2: If we could find a formula for $a+1$ (where $a\in \mathbb N$), then we could successively extend this notion to get an addition function $+:\mathbb N\times\mathbb N\to \mathbb N$. But we can only define $a+1$ through multiplication and the only given parameter is $a$, so $a+1$ is be a product of $a$, hence $a\mid (a+1)$. But this is impossible for $a>1$. So it seems we cannot define an addition function using only multiplication, which is again unsatisfying.

Does anybody have an idea whether this is at all possible? What if we could use a (possibly infinite) product of real numbers to define $a+1$?

share|improve this question
1  
OK... you defined multiplication in terms of addition, but wonder if one can define addition in terms of multiplication? Do you see the problem? –  Pedro Tamaroff Apr 3 '13 at 20:39
    
I know, but I was wondering if I could go the opposite direction, i.e. start off with multiplication in order to get addition. –  Tom Apr 3 '13 at 20:41

2 Answers 2

up vote 11 down vote accepted

The following is a partial answer for $\mathbb{N}$, and the usual notion of (first-order) definability, which is more restrictive than the notion you are implicitly using.

It is an old result of Mostowski that if $S$ is the set of true sentences of number theory that do not use addition, then $S$ is recursive. This is an analogue of the more famous result about the decidability of Presburger arithmetic. There we look at sentences that do not use multiplication.

If addition were definable from multiplication, then the set of true number theoretic sentences would be recursive. But we know that this is not the case.

Thus addition cannot be defined for multiplication in the restricted setting we have described.

Remark: Your definition of multiplication in terms of addition is not first-order. The issue is with the $\dots$, combined with "$b$ times." Replacing this with a more formal recurrence does not make it first-order.

share|improve this answer
    
Might there be a way to prove that addition is not definable by using multiplication without using results from computability and logic that require one to know things like what is computable and what first-order sentences are? –  Michael Hardy Apr 3 '13 at 23:33
    
It's certainly not possible without using results from logic that require notions like "first-order sentences," since it's exactly notions like that which are needed to make your question precise: what do you mean by "definable by using multiplication?" Logic is the language that can make questions like this precise. –  user28111 Apr 3 '13 at 23:52
    
However, as my answer below shows, we don't need computability theory here. –  user28111 Apr 4 '13 at 0:03
    
@user28111: I used computability for the usual sort of reason: to a hammer everything looks like a nail. The automorphism argument is simpler, and proves more. –  André Nicolas Apr 4 '13 at 0:08
1  
@MphLee: It is possible to define the natural numbers, and the addition and multiplication, in terms of set theory, starting with the binary predicate symbol $\in$ (is a member of), and suitable axioms. I take it that's what you mean, and you are right. But the question seems to be about defining addition purely in terms of multiplication. I gave an answer based on a very restricted interpretation of the question (first-order definability). –  André Nicolas May 11 '13 at 17:09

Another, simpler way to show that addition can't be defined from multiplication in "any nice way" (to be defined below): note that the structure $M=(\mathbb{N}, \times)$ has lots of automorphisms. In fact, its automorphism group is $S_\omega$, the group of all permutations of a countably infinite set: automorphisms of $M$ correspond exactly to rearranging the primes.

By contrast, the structure $(\mathbb{N}, +)$ has no automorphisms at all (easy exercise). So addition certainly can't be defined in $(\mathbb{N}, \times)$ by any kind of sentence $\phi$ which doesn't distinguish between isomorphic structures (and this is a basic requirement of every abstract logic I've seen). In particular, first-order sentences certainly have this property, but so do second-order sentences and infinitary sentences, so this isn't a problem with first-order logic: the issue is really that addition contains "more" information than multiplication.


An extension of this argument: consider the case of $\mathbb{R}$ instead of $\mathbb{N}$. Now $(\mathbb{R}, +)$ does have automorphisms (scale by a constant factor), so the above logic doesn't quite work; but there's an easy fix. Consider the map $x\mapsto x^3$; this is an automorphism of $(\mathbb{R}, \times)$, but does not respect addition since in general $$ (x+y)^3\not=x^3+y^3. $$ So again, addition is not definable from multiplication over $\mathbb{R}$ by any kind of isomorphism-respecting sentence. This argument is more robust, and will work in every context I can think of where addition and multiplication make sense.

share|improve this answer
    
This is the general way you show something isn't definable: construct an automorphism which doesn't respect it. Sometimes you need a more powerful method, such as when proving that addition isn't definable from successor by a first-order sentence (in this case, quantifier elimination), but looking for destructive automorphisms is always a good first step. –  user28111 Apr 4 '13 at 0:06
    
What about the 'case in the middle', $\mathbb{Q}$? All of the scaling automorphisms still work on $(\mathbb{Q}, +)$ but $x\mapsto x^3$ isn't an automorphism because it's not surjective. I presume the result still holds, but it's at least a little more nontrivial... –  Steven Stadnicki Apr 4 '13 at 0:10
    
Interesting question! I'm sure it's still true, but it's not obvious to me right now - I'll think about it and see if I can come up with a slick proof. –  user28111 Apr 4 '13 at 1:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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