12
$\begingroup$

Is it possible to define multiplication of two positive integers only using addition and squaring? Of course I have $5 \cdot 3 = 5 + 5 + 5$ but I would like something without saying do this $n$-times.

Peano Arithmetic has the following two axioms:

  1. $x \cdot 0 = 0$
  2. $x \cdot y = x \cdot (y-1) + x$

So I could also write $3 \cdot 5 = 3 \cdot (5-1) + 3 = 3^2 + 3 + 3$ but again I don't "know" how often I need to apply the $2$nd axiom.

I tried a few things and noticed that one has:

$$2xy = (x+y)^2-x^2-y^2 \text{ and } 4xy = (x+y)^2-(x-y)^2$$

Close to $xy$ but still not what I am looking for. And actually this uses subtraction...

Edit: As clarified in the comments: I am asking how to define multiplication inside the structure $(\mathbb{N}, +, \cdot^2)$.

$\endgroup$
9
  • 2
    $\begingroup$ 2) must be $x \cdot s(y)=x \cdot y +x$, where $s(x)$ is the successor of $x$. $\endgroup$ Mar 4, 2019 at 15:48
  • 2
    $\begingroup$ In order to define mult with squaring, you have to provide a def of squaring that does not rely of mult... $\endgroup$ Mar 4, 2019 at 15:49
  • 2
    $\begingroup$ Does one need to define squaring? In a simple case one could have a calculator with a squaring button but times button broken, maybe add still works. $\endgroup$
    – coffeemath
    Mar 4, 2019 at 16:06
  • 4
    $\begingroup$ @MauroALLEGRANZA Or just take squaring as primitive - e.g. ask whether multiplication is definable in the structure $(\mathbb{N}; +, \cdot^2)$. That's a perfectly sensible question. (Actually, that specific question is a bit silly - $xy$ is the unique number $\alpha$ satisfying $x^2+y^2+\alpha+\alpha=(x+y)^2$ - so to make the question nontrivial we have to pin down a more limited notion of "define." But my point stands.) $\endgroup$ Mar 4, 2019 at 16:30
  • $\begingroup$ @NoahSchweber Acutally that is my original question. I know that multiplication is definable in the structure (\mathbb{N}, +, \cdot^2) but not how. It is just written this "weird" because I wanted to avoid talking about structures. $\endgroup$
    – Sqyuli
    Mar 4, 2019 at 16:45

1 Answer 1

25
$\begingroup$

Per your comment, the precise question you're asking is:

Is multiplication definable in the structure $(\mathbb{N}; +,\cdot^2)$?

The answer is yes: we have $z=x\cdot y$ iff $z+z+x^2+y^2=(x+y)^2$.


This is a bit unsatisfying; can we do better?

Well, one natural hope would be for a specific term built out of $+$ and $\cdot^2$ which gives multiplication. E.g. raising to the fourth power isn't just definable, it's given by the term $(x^2)^2$. So we now ask:

Is the term $xy$ equivalent (in the obvious sense) to a term in the language $+,\cdot^2$?

The answer to this new question is no. One way to see this is by taking derivatives. Suppose $t(x,y)$ is a term built out of $+$ and $\cdot^2$. Then when we write ${\partial\over\partial x}t(x,y)$ as a fully-cancelled-where-possible sum of monomials, every monomial in which $y$ occurs have even coefficient$^1$. But the monomial $xy$ itself doesn't have this property.$^2$


$^1$This takes proof, but it's a straightforward induction so I'll leave it to the reader.

$^2$OK fine, technically we need to prove that the fully-cancelled-sum-of-monomials form of a polynomial is unique, but meh - I'll leave it to the reader as well. Induction builds character.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .