Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The question is the extent to which we can unify addition and multiplication, realizing them as terms in a single underlying binary operation. I have a number of questions.

  1. Is there a binary operation $n\star m$ on the integers $\mathbb{Z}$ such that both addition $+$ and multiplication $\cdot$ can be expressed as specific composition expressions using only $\star$? A more relaxed version of the question would allow constants into the expressions; for example, perhaps we can arrange that $a+b=0\star(a\star b)$ and $ab=1\star(a\star b)$.

    One obvious idea is to try somehow to use a pairing function, so that $a\star b$ codes up both $a$ and $b$ into one number, which then can appear as one argument to $\star$, whose other argument will signal whether or not addition or multiplication is desired. But there is the difficulty of making these two tasks not interfere with one another.

    Note that if we allow a trinary operation, then we can easily do it simply by defining $\star(0,a,b)=a+b$ and $\star(1,a,b)=ab$ and extending this arbitrarily. Can we get rid of the need for parameters here?

  2. Can we prove that there is no associative such binary operation $\star$ on the integers, from which both $+$ and $\cdot$ are expressible by terms?

  3. Does every ring have such a binary operation $\star$ from which both addition $+$ and multiplication $\cdot$ are expressible as $\star$-terms? Does it matter if the ring is finite or infinite?

  4. Can every countable family $F$ of finitary operations on an infinite set $Z$ be unified by a single binary operation $\star$ on $Z$, so that every function in $F$ is the same function as that induced by some $\star$-term?

This question arose from what I found interesting about a recent question on math.SE, asked by someone who was interested in the phenomenon that logical and and or are expressible from nand and also from nor.

share|improve this question
1  
Very interesting question! (By some coincidence I was wondering about a similar thing myself too...) –  efq Mar 5 '11 at 16:09
1  
In the introductory course I was TA'ing last semester we gave an exercise to define $\le$, $+$ and $\cdot$ from $a\mod b$ (when everything is zero when taken mod 0). –  Asaf Karagila Mar 5 '11 at 16:46
1  
Although most probably unrelated to your question, something of this ilk happens in the context of Poisson algebras. In a Poisson algebra there are two operations: a commutative, associative multiplication and a Lie bracket, subject to a compatibility condition. It is possible to unify them into one product whose symmetric part is the commutative multiplication and the antisymmetric part is the Lie bracket. –  José Figueroa-O'Farrill Mar 5 '11 at 18:18
    
There is a notion of universal term. When I get to my copy of ALV, I will look it up. I remember it as an exercise as well as work done by George McNulty. Gerhard "Ask Me About Clone Theory" Paseman, 2011.03.05 –  Gerhard Paseman Mar 5 '11 at 18:43
    
Asaf, indeed, one can easily define the operations by formulas of first order logic as in your exercise. In my question, however, I am seeking a binary operation having mere terms that give rise to the given functions. –  Joel David Hamkins Mar 5 '11 at 18:56
add comment

8 Answers

up vote 14 down vote accepted

The answer to Q4 is yes. Let $X$ be any infinite set. Wlog $X= Z\times\mathbb N$, where there is a bijection $i:X\to Z\times \lbrace0\rbrace $. For $x=(z,n)$ write $x+1$ for $(z,n+1)$. [Typo corrected.]

You are given countably many finitary functions $g_1, g_2, \ldots$. We may assume there is a pairing function $x*y$ among them, so we may as well assume that all of them are binary. (Due to Sierpinski, I think. E.g., $g(x,y,z) = h(x*(y*z)) $ for some unary $h$.)

Now there is a binary function $f$ satisfying the following for all $x,y\in X$:

  1. $f(x,x) = x+1$.
  2. $f(x, x+1) = i(x)$.
  3. $f(i(x)+k,i(y)) = g_k(x,y)$ for $k=1,2,\ldots$.

Clearly $f$ generates the functions $x+1$, $i(x)$, and $g_k$ for all $k$.

share|improve this answer
    
I forgot to mention that for finite sets there is a 1935 paper of Donald L. Webb (Zentralblatt 0012.00103), pointed out to me by Agnes Szendrei, which shows that there is a single binary operation generating all functions, a generalization of the Sheffer stroke: $f(x,x) = x+1$ modulo $n$, and $f(x,y) = 0$ otherwise. –  Goldstern May 12 '11 at 17:25
2  
Great! This seems very clear. (But I think you mean $(z,n+1)$ in the first paragraph.) I am inclined to accept this answer as the most sweeping general solution provided. –  Joel David Hamkins May 13 '11 at 13:27
    
Thanks for the correction. –  Goldstern May 13 '11 at 14:43
1  
Reference: Martin Goldstern, A single binary function is enough. Contributions to general algebra 20, 35–37, Heyn, Klagenfurt, 2012. Abstract: (1) Every countable clone (on any base set) is contained in a 1-generated clone. (2) For a countable base set, the local clone generated by a single function f will be the full clone of all operations (this holds for many operations f). (3) But on an uncountable base set a finitely or countably generated local clone will never contain all operations. See Math Reviews MR2908433. –  Goldstern Dec 3 '12 at 15:45
1  
As I just discovered, Trevor Evans showed this (at least for countable base sets) in 1989 in his paper "Embedding and representation theorems for clones and varieties", Bull. Austral. Math. Soc. 40. MR1012828 (90k:08004) –  Goldstern Feb 11 at 13:00
add comment

With constants, the answer to Q1 is "yes". Let me work on the natural numbers ${\bf N} = \{0,1,2,\ldots,\}$ for notational simplicity. The idea is to identify ${\bf N}$ with the shifted naturals $4 + {\bf N}$ using the shift function $f(n) := n+4$ and its partial inverse $g(n) := \hbox{max}(n-4,0)$, and by using some pairing function $\pi: {\bf N}^2 \to {\bf N}$ that is inverted by coordinate functions $c_1, c_2: {\bf N} \to {\bf N}$ (thus $(n,m) = (c_1(\pi(n,m)), c_2(\pi(n,m))$ for all $n,m$). The point is that the shift creates some "room" in which to store the unary functions. More precisely, define

$$0 \star n := f(n)$$ $$1 \star n := g(n)$$ $$2 \star n := c_1(n)$$ $$3 \star n := c_2(n)$$

for any n, and

$$n \star m := \pi( g(n) + g(m), g(n) * g(m) )$$

for $n,m \geq 4$. Then

$$ n + m = c_1( f(n) \star f(m) )$$ and $$ n * m = c_2( f(n) \star f(m) )$$ and so one can write both multiplication and addition in terms of composition operations.

Clearly one can make the same idea work on the integers after placing them in one-to-one correspondence with the natural numbers (which distorts the addition and multiplication operations, but no actual properties of these operations were needed in the above construction).

I would imagine that some clever ad hoc trick would allow one to simulate constants such as 0,1,2,3, for instance by designing the $\star$ operation so that $n \star n$ is usually 0, though I don't see how to simulate four separate constants without using branching, which presumably is not allowed in this exercise.

UPDATE: OK, I found an ad hoc trick to encode constants, again working on the natural numbers for simplicity. The first observation is that one never wants to have a fixed point $n$ where $n \star n = n$, as then any binary operation formed by composition with $\star$ must always map this fixed point to itself. So we do the next best thing, which is to enforce

$$ n \star n := 0$$ for non-zero n, and $$ 0 \star 0 := 1$$ (say). So $n \star n$ is always going to be either 0 or 1. Furthermore, if $n \star n$ is zero, then $(n \star n) \star (n \star n)$ is one, and if $n \star n$ is one, then $(n \star n) \star (n \star n)$ is zero. Hence if we then enforce $$ 0 \star 1 = 1 \star 0 = 2$$ then we have the identity $$ ((n \star n) \star (n \star n)) \star (n \star n) = 2$$ for all n, which allows us to define the constant 2 as a composition word from an arbitrary input n. If we then enforce $$ 0 \star 2 = 1 \star 2 := 3$$ and $$ 2 \star 0 = 2 \star 1 := 4$$ then we can define the constants 3 and 4 also, since $3 = (n \star n) \star 2$ and $4 = 2 \star (n \star n)$. If we then enforce $$ 2 \star 3 := 5; 2 \star 4 := 6; 3 \star 2 := 7; 3 \star 4 := 8; 4 \star 2 := 9; 4 \star 3 := 10$$ then we have now made all the constants from 5 to 10 definable, with no constraints as yet as to how $\star$ acts on these constants, other than to annihilate the diagonal ($5 \star 5 = 0$, etc.).

Now we need shift operators, say $f(n) := n+11$ and $g(n) := \max(n-11,0)$, to make room for all the constants that have been created. Encoding $g$ is easy, e.g. we can enforce $$ 5 \star n := g(n)$$ for all $n$, as this does not conflict with the existing requirement that $5 \star 5 = 0$. Encoding $f$ is slightly trickier. We can write $f$ as a composition $f = h \circ k$, where $k: {\bf N} \to {\bf N}$ is an injective "Hilbert's hotel" map that maps $6$ to $0$ and avoids $7$ in the range, and $h: {\bf N} \to {\bf N}$ is such that $h(g(n)) = n+11$ for all $n$, and $h(7)=0$. Then we can enforce $$ 6 \star n := k(n)$$ $$ 7 \star n := h(n)$$ and $f(n)$ is then $f(n) = 7 \star ( 6 \star n )$.

Finally, we can encode pairing and coordinate functions as before: $$ 8 \star n := c_1(n)$$ $$ 9 \star n := c_2(n)$$ $$ n \star m := \pi( g(n) + g(m), g(n) * g(m) )$$ for $n,m \geq 11$, where we choose the pairing function $\pi$ to only take values $11$ and greater to avoid collision. Then we can recover addition and multiplication as before.

share|improve this answer
    
Very good. Your new edited version seems like it may provide an attack on questions 3 and 4 as well. –  Joel David Hamkins Mar 5 '11 at 19:38
2  
It seems to me that this answer combined with mine will do the job. Terry showed how to get the constant-free operation that encodes two binary operations, and we only need to encode a single binary operation (the partial application of a PCA). –  Andrej Bauer Mar 6 '11 at 8:57
    
Your definition of $n \star n$ for $n \ge 11$ seems to be inconsistent: you want it to be both $0$ and $\pi(g(n)+g(m),g(n)g(m)) \ge 11$. You can probably get around this by encoding more functions with more constants (such as $n\mapsto 2n$ and $m\mapsto 2m+1$, and redefining $\pi$ accordingly), using the same techniques that you've already demonstrated. –  zeb May 13 '11 at 16:59
add comment

A partial combinatory algebra (PCA) is a set $A$ with a partial binary operation $\bullet$, called application, which is combinatorially complete in the sense that "every polynomial is represented". More precisely, given a term $t(x_1, \ldots, x_n)$ built from the elements of $A$ and variables $x_1, \ldots, x_n$ using the application operation $\bullet$, there exists an element $a \in A$ such that, for all $b_1, \ldots, b_n \in A$, $$a \bullet b_1 \bullet \cdots \bullet b_n \simeq t(b_1, \ldots, b_n),$$ where application associates to the right, $u \bullet v \bullet w = (u \bullet v) \bullet w)$ and $\simeq$ is Kleene's equality: if one side is defined then so is the other and they are equal.

For example, in a combinatory alebra there is always an element $a$ such that $a \bullet b \simeq b \bullet b$ for all $b$.

An example of a combinatory algebra is a model of the untyped $\lambda$-calculus, since the element representing $t(x_1, \ldots, x_n)$ is simply $\lambda x_1 x_2 \ldots x_n . t(x_1, \ldots, x_n)$.

A standard theorem about PCA's states that $(A, {\bullet})$ is combinatorially complete if, and only if, it contains elements $k, s \in A$ such that $k \bullet a \bullet b = a$ and $s \bullet a \bullet b \bullet c \simeq (a \bullet c) \bullet (b \bullet c)$, for all $a, b, c \in A$.

The set of natural numbers $\mathbb{N}$ may be equipped with the structure of a PCA, known as Kleene's first algebra, if we define $n \bullet m = \phi_n(m)$, where $\phi$ is a standard enumeration of partial recursive maps. The representable maps in Kleene's first algebra are precisely the partial recursive ones. Therefore, for any binary partial recursive map $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ there exists a natural number $c$ such that $c \bullet m \bullet n \simeq f(m, n)$ for all $m, n \in \mathbb{N}$.

This answers your question positively and quite a bit more generally, i.e., there is an operation on $\mathbb{N}$ which generates all partial computable maps (of all arities), provided you are willing to consider partially defined operations. If we want to represent a countable family of possibly non-computable maps, then a suitable variation of Kleene's first algebra over an oracle will accomplish that.

If you are willing to consider non-computable maps we can use a cheap trick to make our operation total. Define a new operation $\star$ on $\mathbb{N}$ by $$m \star n = \begin{cases} m \bullet n & \text{if $m \bullet n$ defined}\\\\ 42 & \text{otherwise}\end{cases}$$ which has the following property. Given any total computable map $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ there is a number $c$ such that $c \star m \star n = f(m,n)$ for all $m, n \in \mathbb{N}$. To see this, just take the $c$ which works for $\bullet$. Since $c \bullet m \bullet n$ is always defined we get $c \star m \star n = c \bullet m \bullet n = f(m, n)$. Note however that $\star$ also represents some non-computable maps.

Partial combinatory algebras are important in certain branches of computability and in theory of programming languages. Unfortunately, we know almost nothing about the general structure of PCAs.

share|improve this answer
    
Dang it! :-) I was just setting out to write something about combinatory logic. :-) –  Todd Trimble Mar 5 '11 at 20:01
    
Andrej, Thanks! I like this answer very much. But you still seem to need the constants, so it doesn't answer the strong version of question 1. But perhaps one can omit the constants somehow with a complicated term. Another point is that it appears that we can relativize your idea to have an oracle, and thereby get an answer to question 3 in the case of countable rings (using the ring operations as an oracle). With a view to question 4, is there any reason to expect such operations on uncountable sets? –  Joel David Hamkins Mar 5 '11 at 20:03
    
Every powerset is a (total) combinatory algebra because it is a model of $\lambda$-calculus, so at least for powers of $2$ we get a similar result. Reals numbers are a power of two (in the insane world of classical mathematics with axiom of choice). –  Andrej Bauer Mar 5 '11 at 20:11
2  
Ok, I will edit my answer so that we don't need constants. –  Andrej Bauer Mar 5 '11 at 20:12
2  
This will take a while because I also have to put a six-year old to bed (and six-year olds specialize in not going to bed). –  Andrej Bauer Mar 5 '11 at 20:32
show 2 more comments

The answer to Q2 is also yes, at least if no constants are allowed. Suppose that addition and multiplication can be modeled by some words involving an associative operation $\star$. If we then let $A_k := 1 \star \ldots \star 1$ be the $k$-fold iterated $\star$ of $1$, we thus see that $A_1=1$ and $A_k + A_l = A_{ak + bl}$ and $A_k \cdot A_l = A_{ck+dl}$ for some natural numbers $a,b,c,d$ and all $k,l$ (reflecting the number of times $n,m$ appear in the words for $n+m$ and $n \cdot m$ respectively). Thus addition and multiplication starting from the generator 1 have simultaneously been encoded as additive operations, which can be shown to be impossible by a variety of means (for instance, one can use the sum-product theorem of Erdos and Szemeredi to rule this out, although this is something of a sledgehammer and I am sure that there are much more elementary ways to proceed here).

The situation seems more interesting with constants, though. My guess is that because you did not require the $\star$ operation to be invertible in any way, one could still pull off the shift-encoding trick while respecting associativity, though this would require some more ad hoc contortions.

share|improve this answer
1  
Here's a nice simple way for this case - $A_1\cdot A_1=A_1$, so c+d=1, so we either have nm=n for all n,m, or nm=m for all n,m! –  Harry Altman May 12 '11 at 22:27
add comment

The exercise in Algebras, Lattices, Varieties Volume I by McKenzie, McNulty, and Taylor may be of interest: There is a term t(x,y,z) in three variables in the language of one binary symbol which is universal in the sense, that, given an infinite set A and a ternary operation G(x,y,z) on the set A, there is a binary operation on A such that, when t is constructed out of this binary operation, then G(x,y,z) = t(x,y,z) for all triples x,y,z from A. Note that the term t specified is independent of A or G. I do not know if universality is defined for tuples of terms (I would be expect that serious side conditions need to be present in order for a tuple of terms to represent uniformly a tuple of operations of the same arity, thus making it not so universal).

For the question regarding whether a given countable family of operations can be built from one operation, this is a consequence of asking if the clone generated by the family of operations is generated by one operation. Given that there are uncountable many clones on a 3-element set, I would say that the question is of interest but unlikely to be solvable uniformly or even nicely. By this I mean, if Q(F) is some way of expressing that the family F generated a clone which is finitely generated, I can imagine necessary condtions implied by Q(F) and sufficient conditions which could imply Q(F), but nothing which would be equivalent. (The question of whether F is contained in a finitely generated clone might be easier, but I do not know how much easier.)

You probably have better access to references on clone theory than I; you might try pursuing those first before asking me for a further opinion.

Gerhard "Ask Me About System Design" Paseman, 2011.03.05

share|improve this answer
    
I suspect one can answer Q1 by finding terms without constants by building on the universal term t. For example, if G(a,b,c) returns b+c when a=b and otherwise returns b*c, then addition could be t(a,a,b) and multiplication is close to ( but not quite) t(t(a,a,a),a,b). Perhaps someone quicker than I can find the appropriate arguments in terms of t. Even if I found it though, I can't yet tell you what the binary operation underlying t is. Gerhard "Ask Me About System Design" Paseman, 2011.03.05 –  Gerhard Paseman Mar 5 '11 at 21:37
add comment

How about this alternative approach to answer Q1:

Step 1: Get some room by defining first the diagonal of $*$ (which is mapped to numbers divisible by $5$):

  • $z*z := 5z$ for $z > 0$ and $z*z := 5z-5$ for $z <= 0$.

Now we define the meaning of $x*y$ for $x\ne y$ depending on $x \bmod 5$ and $y \bmod 5$.

Step 2: We recode all integers in different ways (to signal if we want to add or multiply)

  • $z * (z*z) := 5z+1$ (special $x*y$ for $y = 0 \bmod 5$ and $x \ne y$).
  • $(z*z) * (z*(z*z)) := 5z+2$ (special $x*y$ for $x = 0 \bmod 5$ and $y = 1 \bmod 5$).
  • $(z*z) * ((z*z) * (z*(z*z))) := 5z+3$ (special $x*y$ for $x = 0 \bmod 5$ and $y = 2 \bmod 5$).

Step 3: We define the addition and the multiplication

  • $(y*(y*y)) * ((z*z) * (z*(z*z))) := y + z$ (special $x*y$ for $x = 1 \bmod 5$ and $y = 2 \bmod 5$).
  • $(y*(y*y)) * ((z*z) * ((z*z) * (z*(z*z)))) := y \cdot z$ (special $x*y$ for $x = 1 \bmod 5$ and $y = 3 \bmod 5$).

The still undefined values of $x*y$ can be assigned arbitrarily. The last two definitions give the formulas for addition and multiplication.

share|improve this answer
    
There is still room (and you can create new one with repeating step 1 for another prime) for other operations, so I see no reason why this approach couldn't encode countably many binary operations on $\mathbb{Z}$ answering a special case of your Q4. –  Someone May 13 '11 at 16:28
    
There is an affinity of this idea with Goldstern's solution. If you don't work mod $5$, but replace $\mathbb{Z}$ with $\mathbb{Z}\times\mathbb{Z}$, you'll be able to accommodate infinitely many functions. –  Joel David Hamkins May 13 '11 at 16:38
    
@Joel: Or if I run out of space, I just increase the modulus. –  Someone May 13 '11 at 16:41
    
You may have (in principle) solved the ALV exercise I mentioned in my post. Your term bears some resemblance to the universal term they have. Gerhard "Ask Me About System Design" Paseman, 2011.05.13 –  Gerhard Paseman May 13 '11 at 16:49
    
@Gerhard: I guess you are right. –  Someone May 13 '11 at 17:04
add comment

Let $R$ be a ring and suppose $j\colon R \to R$ is an injection such that $j(a) \neq a,a+1$ for all $a \in R$. (Such an injection exists iff $R$ has more than two elements: take $j$ to be a translation $x \mapsto x+c$.)

Define $a \star a:=j(a)$ and $j(a)\star b:=a+b$. Since $j(a) \neq a$, this is well defined and $(a \star a) \star b=a+b$.

Now define $(j(a)+1) \star b :=ab$. Again this is well-defined, and $ab=((a \star a)\star 1)\star b)$.

share|improve this answer
1  
If I carry out your idea in the integers, using $j(a)=a+2$, then I seem to have $2\star 2=j(2)=4$ by your first requirement, but also $2\star 2=j(0)\star 2=0+2$. So your definition is not well-defined. –  Joel David Hamkins Mar 5 '11 at 18:51
    
What if you take (for the integers) $j$ to be $a \mapsto a^4+2$? Then this $j$ has the property that $im j$+1 is disjoint from $im j$, which seems to cause the trouble. –  Guntram Mar 5 '11 at 19:40
    
That alone won't fix the problem, since your definitions will require that $j(a)\star j(a)$ is both $j(j(a))$ and also $a+j(a)$. –  Joel David Hamkins Mar 5 '11 at 19:51
add comment

In a sense, addition is a universal operation. Hilbert's Thirteenth Problem. One answer shows that any operation $g \colon \mathbb R^n \to \mathbb R$ can be written as a finite combination of several unary functions and the binary function addition.

share|improve this answer
    
Thanks Gerald. I am aware of this theorem, which uses the combination of functions to implement a pairing function---some of the unary functions stretch the reals to make $0$s in every other digit, and then adding them combines two reals into one real whose digits are the two interleaved, and another unary function carries out the desired function on these codes. But this method doesn't answer my question unless you can get it all down to one binary function. –  Joel David Hamkins Mar 5 '11 at 18:44
add comment

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.