JohnF
Posts:
97
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 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? Thanks,
--
John Forkosh ( mailto: j@f.com where j=john and f=forkosh )
|
|
