JohnF
Posts:
180
Registered:
5/27/08


Re: function arity > 2
Posted:
Jan 16, 2013 3:41 AM


Butch Malahide <fred.galvin@gmail.com> wrote: > JohnF <john@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).
> 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? 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? Thanks,  John Forkosh ( mailto: j@f.com where j=john and f=forkosh )

