13

I remember reading a while back about arithmetics with only a single operator that did all the work of the familiar $+ - \times /$ operators. If there is such a thing, could someone point me to it?

As background: I have a side project where I'm playing with neural nets and genetic search algorithms. Right now it's the good old kind, with matrix multiplication and addition. I thought it would be interesting to implement a sort of neural network that used a combined or "all in one" operator.

I've googled like heck and can't pick up the trail of where I thought I saw that before.

Is there study in that area, or am I mis-remembering, or worse, just making it up? I'd appreciate any pointers.

Michael Hardy
  • 1
sea-rob
  • 381
  • 1
    I haven't heard of it, but some thoughts: The NAND operator alone can be used to build a computer. It might not qualify as an "arithmetic" operator though. You could design a contrived example like $op(a,b,c,d,e) = a+b-c*d/e$, or even force it to be binary in some contrived way like mapping $\Bbb{R}$ to itself "4 times" and thus "encoding" the operation you want in the first operand. So you might want to introduce some conditions on this operator to force it to be "neat" (and then try to build it, or prove it doesn't exist). – Yoni Rozenshein Mar 22 '13 at 23:52
  • One thought was to just making a big matrix of NAND operands, converting all my real inputs to integers (losing some precision) and then running it through the NAND bank in a matrix-operation-manner, and let the genetic search do the rest. Actually, that's probably what I'll do next. (would be a good excuse to try writing some logic in C with a python binding) – sea-rob Mar 23 '13 at 21:08
  • FYI I was also thinking about playing with "multi_nand" like $\lnot((x \times y) \land y)$ (with bitwise logic on ints) Or, based on @MJD answer, maybe "divi_nand". ;) However, it would be a pure experiment, because reasoning that out is above my pay scale. Good thing no one is paying for this work. – sea-rob Mar 23 '13 at 21:44

3 Answers3

10

[Added: @MJD's answer and mine are really answers to somewhat different questions, and @MJD's answer is the one that probably addresses the intended question. But I'll leave this answer in place as the issue it notes is interesting anyway!]

It depends what logical apparatus is available.

Dedekind/Peano arithmetic in its original form has just the successor $S$ function built in as the one primitive arithmetical operator, but is strong enough to express all the usual arithmetical functions.

How come? Well, other functions can be defined. Thus addition is the one and only function $f$ such that $f(x, 0) = x$ and $f(x, Sy) = Sf(x, y)$. Having defined addition, multiplication is the one and only function $f$ such that $f(x, 0) = 0$ and $f(x, Sy) = Sf(x, y) + x$. (Dedekind famously has a proof that such definitions do indeed uniquely pin down well-defined functions).

But note this sort definition of a function in effect quantifies over functions (NB that "one and only") -- hence it is only available in a second-order framework which allows quantifications over functions (as of course the original Dedekind/Peano axiomatisation did).

In a first-order framework, we can't define functions by quantification in the same way, but have to explicitly postulate at least some additional functions -- canonically, we take addition and multiplication as additional primitive functions (and then show all the other recursive functions can be expressed using these, by Gödel's trick).

Peter Smith
  • 54,743
  • I'm going to need to dig into this and figure it out :) It sounds very powerful. Thank you! – sea-rob Mar 23 '13 at 21:25
  • Thank you for the update. Mea culpa -- I apologize that I didn't ask the original question as clearly as I could have. Thank you for leaving the answer in place -- I want to study up on it and understand it. – sea-rob Mar 24 '13 at 16:02
8

This discussion follows the solutions of problems 1–2 given in A Problem Seminar by Donald J. Newman (Springer, 1982), pp. 45–46.

First, note that all four of $+, -, \times, \div$ can be built just from $-$ and the reciprocal operation $x\mapsto \frac1x$: Addition is easy: $$x+y = x-((x-x)-y).$$

By partial fraction decomposition we have $$ \frac1{x-x^2} = \frac1{1-x} + \frac1x$$

So $$x^2 = x-\left(\frac1{1-x} + \frac1x\right)^{-1}.$$

Now we can calculate $(x,y)\mapsto -2xy$ by using $-2xy = (x-y)^2 - x^2 - y^2$. We can get rid of the $-2$ by using $\frac u{-2} = \left(\left(0-\frac1u\right)-\frac1u\right)^{-1}$. And now that we have multiplication, obviously we get $x\div y = x\cdot \frac 1y$. So we have all of $+,-,\times,\div$ from $-$ and reciprocal.

Second, we need to find a single operation that gives us $-$ and reciprocal. Newman observes that nothing like $x\circ y = x(x+y)$ can work because it can never give us subtraction. So instead, we try something like $$x\circ y = \frac1{x-y}$$ that has subtraction and reciprocal in it already.

Reciprocal is easy: $$x\circ 0 = \frac1{x-0} = \frac1x.$$

And then $$(x\circ y)\circ 0 = \frac1{\frac1{x-y}-0} = x-y.$$

So all four of $+, -, \times, \div$ can be defined in terms of $\circ$.

Looking at this now, I notice that Newman has tacitly assumed that we are allowed to use certain constants: $0$ in the second part, and 1 in the first part. (0 in the first part can be synthesized from $x-x$.) I don't know if these can be avoided, but perhaps you don't care about that detail.

MJD
  • 65,394
  • 39
  • 298
  • 580
  • I'm accepting (edited -- ty!) this as the answer, because it looks just like what I was looking for! (I need to process @Peter Smith's answer about Dedekind/Peano arithmetic -- lots of people liked it. I need to figure out how to express that in C or Python code.) Ultimately, I need an operator that I can apply $x \circ y_1 \circ y_2 \circ \ldots \circ y_n = z$ (with matrix semantics), and let the genetic search find the values of y that produce the best z's. – sea-rob Mar 23 '13 at 21:41
  • 1
    I've finally gotten around to coding this. I found a funny consequence of this approach. I started to render expressions in Reverse Polish Notation, but they looked like this: $\circ \circ y x 0$ ... in other words, expressions using this operator boil down to a sequence of operands! $y x 0$ lol! Well, I thought that was funny. Thanks again -- I'm enjoying playing around with this. – sea-rob Sep 19 '13 at 22:37
  • I'm glad I was able to help. – MJD Sep 20 '13 at 04:28
4

In MO there is a similar question, but only related to addition and multiplication, but the accepted answer, ensure that this is possible whenever we want to do this with a countable collection of binary operations, so we can do it with four.

https://mathoverflow.net/questions/57465/can-we-unify-addition-and-multiplication-into-one-binary-operation-to-what-exten

Community
  • 1
Fenrir
  • 656
  • 5
  • 17