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