Search All of the Math Forum:

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

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

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

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

Butch Malahide <fred.gal...@gmail.com> wrote:
>> Butch Malahide <fred.gal...@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).

>
> 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.

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 2-place 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) 2-place 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 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.

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, cardinality-wise, so it was thought no set-theoretic
model of the collection of such lambda-expressions is possible.
Scott solved that little conundrum, and the cardinality issues you
raise above seemed to me maybe amenable to a similar treatment.
if interested. Thanks a lot for your help above,
--
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