17
$\begingroup$

Does there exist a function $\mathbb R^n \to \mathbb R$

$$f(x_1, x_2, x_3, \dots, x_n)$$

such that it is not possible to write $f$ in terms of a finite number of arbitrary binary operations $\mathbb R^2 \to \mathbb R$?

Let's term a binary operation which takes only real numbers as inputs and outputs a single real number (as opposed to a tuple of real numbers) to be a real-valued binary operation. If all real-valued functions can be written in terms of arbitrary real-valued binary operations, is there a lower-bound to the minimum number of real-valued binary operations needed to write a real-valued function that takes $n$ inputs?

$\endgroup$
  • $\begingroup$ Not a full answer, but in Computational Complexity theory there's the concept of an arithmetic circuit, which essentially is anything you can compute with finite inputs, $+$, $\times$, and finite "depth" of operations. You can do suprisingly a lot with this, but as a theory of computation it isn't turing complete - things that would require loops of unbounded size aren't computible. I'd start looking there. It has some issues though, like $f(x) = \chi_{0}(x)$ isn't computible, but may be via binary operations. $\endgroup$ – Mark Jul 24 '17 at 22:26
  • 1
    $\begingroup$ How is this a set theory question? $\endgroup$ – Asaf Karagila Jul 24 '17 at 22:56
  • 5
    $\begingroup$ @AsafKaragila I think it's roughly a set theory question. The question concerns what are essentially arbitrary functions, so they don't really have properties other than set-theoretic ones. $\endgroup$ – Christopher A. Wong Jul 24 '17 at 23:15
  • $\begingroup$ This calls to mind a ferocious debate among Relational Theory aficionados concerning aggregate operators such as "average." I believe its relevance to your question hinges on the crucial question of whether you mean for this function to accept a variable number of inputs ($n$), or a fixed but arbitrary number of inputs. $\endgroup$ – Wildcard Jul 25 '17 at 3:17
  • $\begingroup$ @Christopher: It's always odd to see an answer to a rhetorical question. $\endgroup$ – Asaf Karagila Jul 25 '17 at 8:23
25
$\begingroup$

Let $X$ be any infinite set and $f:X^n\to X$ be an $n$-ary operation for some $n>2$. Let $g:X\times X\to X$ be any bijection, and let $h:X^{n-1}\to X$ be given by $h(x_1,x_2,\dots,x_{n-1})=f(y_0,y_1,x_2,\dots,x_{n-1})$ where $y_0,y_1\in X$ are the unique elements such that $g(y_0,y_1)=x_1$. We then have $$f(x_0,x_1,\dots,x_{n-1})=h(g(x_0,x_1),x_2,\dots,x_{n-1}).$$ That is, $f$ is a composition of one binary operation and one $(n-1)$-ary operation. By induction on $n$, this shows that any $n$-ary operation on $X$ can be written as a composition of $n-1$ binary operations (and in fact, all but the last of these binary operations can be chosen to be some fixed bijection $X\times X\to X$).

Note that clearly you can't use fewer than $n-1$ binary operations, since in any expression formed by composing $k$ binary operations, you have only $k+1$ different inputs. So if you had fewer than $n-1$ operations, one of the variables would need to not appear as an input at all, and so the $n$-ary operation could not depend on that variable.

If you impose additional restrictions on what kinds of operations you're allowed to use, this question can become much more subtle, and is generally known as (variations on) Hilbert's thirteenth problem. For instance, in the case $X=\mathbb{R}$, if you require all the operations to be continuous, then it is a theorem of Arnold and Kolmogorov that every operation can be written as a composition of binary operations (or in fact, a composition of addition and unary operations). If you require the operations to be smooth instead, then for every $n$ there are $n$-ary operations on $\mathbb{R}$ which are not compositions of operations of lower arity (see https://mathoverflow.net/questions/195380/are-all-smooth-functions-composites-of-0-1-and-2-ary-functions).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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