JohnF
Posts:
175
Registered:
5/27/08


Re: function arity > 2
Posted:
Jan 16, 2013 6:10 AM


Butch Malahide <fred.gal...@gmail.com> wrote: > JohnF <john@please.see.sig.for.email.com> wrote: >> Butch Malahide <fred.gal...@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). > > 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)".
Thank, looks interesting. And I'm not seeing any mention of clones in the book (A Course in Universal Algebra, Burris and Sankappanavar, Springer 1981) I'm beginning to read.
>> > 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.
Nope, next to nothing (and that's approaching zero from the negative side). But you've coincidentally hit the nail pretty much on the head: if you godel number propositions/predicates/whatever, I want to be sure all rules of inference, particularly for some substructural logics, can be represented as (or reduced to) 2place functions NxN>N.
>> 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.
Yet another interesting subject. Relevant above, I think, as follows: it's a theory (and syntax) describing functions as rules rather than graphs. So, as usual, functions can take other functions as arguments, whereby the space of functions is isomorphic to its own function space. That's impossible, cardinalitywise, so it was thought no settheoretic model of the collection of such lambdaexpressions is possible. Scott solved that little conundrum, and the cardinality issues you raise above seemed to me maybe amenable to a similar treatment. Anyway, see, e.g., wikipedia.org/wiki/Domain_theory for more info if interested. Thanks a lot for your help above,  John Forkosh ( mailto: j@f.com where j=john and f=forkosh )

