Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: function arity > 2
Replies: 7   Last Post: Jan 17, 2013 1:37 AM

 Messages: [ Previous | Next ]
 JohnF Posts: 150 Registered: 5/27/08
Re: function arity > 2
Posted: Jan 16, 2013 3:41 AM

Butch Malahide <fred.galvin@gmail.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 )

Date Subject Author
1/16/13 JohnF
1/16/13 Butch Malahide
1/16/13 JohnF
1/16/13 Butch Malahide
1/16/13 JohnF
1/16/13 Butch Malahide
1/17/13 JohnF
1/16/13 Graham Cooper