|
|
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 2-place 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 n-element 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.
|
|
