Can we unify addition and multiplication into one binary operation? To what extent can we find universal binary operations? 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.


*

*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? 

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

*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?

*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.
 A: 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
A: 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.
A: Here is an easy answer to question 1.
Let $\langle x,y\rangle$ be a pairing function with $L(\langle x,y\rangle)=x$ and $R(\langle x,y\rangle)=y$.
Define:
$$\begin{align}
a \star 1 &= 2a\\
a \star 3 &= L(a)\\
a \star 5 &= R(a)\\
a \star 2b &= \langle a+b,ab\rangle
\end{align}$$
and other values of $a\star b$ equal to 1.
Then:
$$a+b = L(a\star2b) = (a\star(b\star1))\star3$$
$$ab = R(a\star2b) = (a\star(b\star1))\star5$$
A: 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$:


*

*$f(x,x) = x+1$.

*$f(x,  x+1) = i(x)$.

*$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$.
A: 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.
A: 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.
A: 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.
A: 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)$.
