MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Formalization of n-ary functions

Hi there. I've been doing some thinking lately (oh-no!) about function definitions. Specifically, I'm considering functions with multiple parameters.

Now, I'm familiar with "the usual" definition in which a function from set $S$ to set $T$ has the signature $f : S \to T$, and where $f$ itself is a set of tuples $(s,t)$ such that $s \in S$ and $t \in T$ and we have the property that for all elements $s$ of $S$, and elements $t_1$ and $t_2$ of set $T$, $\left((s,t_1) \in f\right) \wedge \left((s,t_2) \in f\right) \rightarrow t_1 = t_2$ (to distinguish functions from relations).

I've also seen this used in two ways with regards to $n$-ary functions: in curried and uncurried forms. In the uncurried form, we can write an $n$-ary function with the signature $f : A_1 \times A_2 \times \cdots \times A_n \to B$; that is, we simply define $f$ to have a domain which is a Cartesian product of sets. Thus, in this definition, we can still write the signature of $f$ in the form $f : S \to T$ by allowing $S = A_1 \times A_2 \times \cdots \times A_n$.

In the curried form, we instead define $n$-ary functions as higher-order function; specifically, functions which return other function. In this case, the signature of $f$ would be of the form $f : A_1 \to \left[A_2 \to \left[\cdots[A_n \to B\right]\right]$ (I am using the notation $[X\to Y]$ to denote the space of all functions from $X$ to $Y$). By this definition $f$ takes a single parameter from set $A_1$ and returns another function which accepts a single parameter from set $A_2$, and so on, until we finally produce function which accepts a single parameter from set $A_n$ and returns an element of $B$. But this definition could still be written in the form $f : S \to T$ by setting $S = A_1$, and setting $T = \left[A_2 \to \cdots \left[A_n \to B\right]\right]$.

Both the above definitions for $n$-ary functions still boil down to the definition of a unary function. When I see the form $f : A_1 \times \cdots \times A_n$, I still read $f$ as being a unary function, not as an n-ary function. The same goes for the curried form. In no way do I get the feeling of $f$ being an n-ary function.

While I see the appeal to having the simple, yet general definition, I can't help but feel like something is missing by restricting all functions to (in essence) being unary. So does anyone know about, or does anyone have their own ideas of how a "truly n-ary" function could be defined. By "truly n-ary", I specifically mean that the function's signature could not be boiled down to $f : S \to T$, but instead was actually a function with n separate "domains".

-
If you're looking for a context that treats all multi-ary functions on equal grounds, just go ahead and work with the multicategory of Sets and multi-ary functions (either definition above, or any other reasonable definition, will produce equivalent multicategories), rather than the category of Sets and unary functions. The domain of a multi-ary function would indeed be a multi-ary domain distinct from any unary domain, not because of some arcane "How to implement functions as sets of sets of sets..." rules' consequences but simply because you directly set things up the way you wanted them. – Sridhar Ramesh Jul 25 2011 at 7:27
@Sridhar: Why did you not make that an answer? It looks like a great idea! – kenwaynevan Jul 25 2011 at 18:17

Here's a set-theoretic approach that might give you the "feeling" of a genuinely $n$-ary function. Regard an $n$-ary function $f$ as the set of $(n+1)$-tuples $\{(a_1,\dots,a_n,b): b=f(a_1,\dots,a_n)\}$. This might still look like a set of ordered pairs, because some people like to code tuples as pairs. If you want to avoid that, code $(n+1)$-tuples as (unary) functions with domain $\{0,1,\dots,n\}$.

-
 Thanks for the answer. I like the way in which you define tuples. I been born and raised to defined $n+1$-tuples as $(a_1, a_2, \dots, a_{n+1}) = (a_1, (a_2, \dots, a_{n_1}))$, so thinking of treating them differently didn't really enter my head. If tuples are defined as you show, then $f$ doesn't just "feel", $n$-ary, I think it can truly be called $n$-ary. – kenwaynevan Jul 25 2011 at 18:16 Also, if $f$ really is unary, this definition boils down to the usual. Awesome! – kenwaynevan Jul 25 2011 at 18:23

You might consider looking into abstract clones. I don't have a reference handy, but for concrete clones chapter 4 section 4.1 of "Algebras, Lattices, Varieties" by McKenzie, McNulty, and Taylor has a brief introduction.

A concrete clone is a collection of functions of finite arity on the same underlying set, which also contains all the projection functions and is closed under composition, together with (a series of) metaoperations which tell how to make compositions among members of the clone. I think you will get a better appreciation for arity if you consider functions in the context of how they are used to make other functions.

An abstract clone is (to me) a structure which resembles a clone but with no underlying set. I think Agnes Szendrei has abook dealing with abstract and concrete clones, but I have not read it.

 I think the idea of clone is quite interesting. However, using clones pre-supposes a formalization of $n$-ary functions, so I'm not sure how this applies to my question. – kenwaynevan Jul 25 2011 at 18:42 Functions of finite arity are a motivating example for the study, but I mentioned abstract clone because it can be defined and studied independently of the definition of function. My point was that the feeling of arity you desire may come more from how the things interact than from their underlying definition/construction. Gerhard "Ask Me About System Design" Paseman, 2011.07.25 – Gerhard Paseman Jul 26 2011 at 4:21