
Re: function arity > 2
Posted:
Jan 16, 2013 4:55 AM


On Jan 16, 2:41 am, JohnF <j...@please.see.sig.for.email.com> wrote: > Butch Malahide <fred.gal...@gmail.com> wrote: > > JohnF <j...@please.see.sig.for.email.com> wrote: > >> As in universal algebra, where introductory discussions > >> typically suggest arity>2 not often used. Are there any > >> functions f:N^3>N (domain integers) that can't be > >> decomposed into some g,h:N^2>N, where f(i,j,k)=g(i,h(j,k))? > >> If so (i.e., if arity>2 needed), got an example? If not, > >> got a proof? And, if not for integers, is there any domain D > >> where f:D^3>D can't be decomposed like that (example or > >> proof again appreciated)? > > > Hmm. Your equation "f(i,j,k) = g(i,h(j,k))" seems kind of special, > > and it's not clear to me that it covers all ways of expressing > > a ternary operation in terms of binary operations. > > Oops, you're right, I meant to "cover all ways", but couldn't > see how to say that (i.e., not sure what that intuitive idea > formally means).
Hmm. I guess you'd want to allow all kinds of iterated compositions. Which I think is what "clone theory" is about. Not that I ever knew anything about of that, but I've heard of it, in some bygone century. I see that there is a Wikipedia page on "Clone_(algebra)".
> > Anyway: > > > If D is an infinite domain, assuming the axiom of choice, there is an > > injection h:DxD>D, i.e., a pairing function. Given any function > > f:D^3>D, we can then define g(i,h(j,k)) = f(i,j,k). > > Thanks, D=N=integers is what I'm primarily interested in. > > > If D = {0,1}, the function f:D^3>D such that f(0,j,k) = j, f(1,j,k) > > = k, can not be expressed in your form f(i,j,k) = g(i,h(j,k)). > > Okay, that's pretty obvious  now that you've pointed it out. > Is it an artifact of my failure to "cover all ways" as you > mentioned above, or a fundamental property related to the > cardinality of those function spaces, as you discuss below?
The former, I guess. Ternary operations on {0,1} are just Boolean functions of 3 variables, and I dimly recall from a previous millennium when I dabbled in logic for a while, that all Boolean functions can be expressed in terms of 2place functions (connectives) such as NAND. But I'm sure you know a lot more about that stuff than I do.
> At first blush, I might try to "symmetrize" f(i,j,k)=g(i,h(j,k)) > over i,j,k permutations in some way to avoid your counterexample. > But I suppose that's silly, and a fundamentally better expression > to "cover all ways" is probably what's really called for. > > > If D is an nelement set, 2 < n < infinity, we can generalize the > > example for n = 2, or we can just use a counting argument: the number > > of ternary operations on D is n^(n^3), whereas the number of ordered > > pairs of binary operations is only n^(2n^2). > > Right, this cardinality issue sounds like what I probably really need > to address. Suppose we restrict our function space to continuous > functions wrt some suitable topology (I'm thinking somehow analogous > to Scott's D_\infty construction for a model of the lambda calculus, > and subsequent domain theory stuff). I imagine cardinality problems > could be resolved. Are some additional open set properties required > so that arity>2 functions can always be written as (some suitable > composition of) arity<=2 functions? Or am I totally barking up the > wrong tree, or what?
Damned if I know. I've *heard* of lambda calculus, and that's about it.

