
Re: function arity > 2
Posted:
Jan 16, 2013 6:28 PM


On Jan 16, 5:10 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: > >> 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)". > > 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,
See also Hilbert's 13th problem:
https://en.wikipedia.org/wiki/Hilbert%27s_thirteenth_problem

