Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: William Hughes <wpihughes_at_hotmail.com>
Date: 20 Sep 2006 20:05:22 -0700
Message-ID: <1158807921.994201.210760@e3g2000cwe.googlegroups.com>

Marshall wrote:
> William Hughes wrote:
> > Chris Smith wrote:
> > > <pamelafluente_at_libero.it> wrote:
> > > > What confuses me a little is that I thought that math is a (kind of)
> > > > exact science. But here everything (proofs and definitions) seems that
> > > > can be subject to opinion and I do not see resolutive statements !
> > >
> > > Then I've failed in being clear. Certainly, math is more or less exact.
> > > The ambiguous bit here is how we define what we're talking about.
> > >
> > > Basically, the story so far is that I tried to provide a more precise
> > > definition for what Marshall meant when he said that your "replication
> > > insensitive" functions were equivalent to the set of aggregate functions
> > > that are defined by idempotent binary functions.
> >
> > And as pointed out, only a subclass of functions on M(A)
> > (henceforth turquoise functions) can be definied by binary
> > functions.

> Sure. Of course, my formulation of aggregates is not limited
> just to binary functions.

> Recall:

> Type 1:
> f : (A, B -> B)
> e: B
> creates an aggregate of type
> {A} -> B

> (A, B not necessarily distinct.)

> Type 1b:
> f: (A, A -> A)
> creates an aggregate of type
> {A} -> A

> Type 2:
> an arbitrary expression that may include terms of type 1.

> (Alternatively you could think of type 1 being simply the case
> of type 2 where the arbitrary expression is the identity function.)

>
>


> > Marshall's comments can only apply to this

> > subset [whether the subset should be called the aggregate
> > functions is a different issue].

> Well, at this point I've lost track of which comments you're
> referring to. The conversation is getting long.

>
>


> > > First, I came up with a way fo defining aggregate functions from binary

> > > functions that I thought was sufficient.  For the functions I defined,

> > > it *is* true that replication sensitivity is equivalent to idempotence

> > > of a binary generating function.  However, it turns out that the

> > > functions I initially defined don't include everything that's commonly

> > > called an aggregate function.

> > >

> >

> > And more importantly does not include commonly used

> > turqoise functions (i.e. median)

> >

> > > So I then made a second attempt to define aggregate functions.  Marshall

> > > also made an attempt, which I believe is equivalent to my second

> > > attempt.

> >

> > Well, it is less than clear that this second attempt does include

> > functions such as the median,you need to be much more

> > careful with your definition of the range and domain of g.
> > (g: A^2 -> A doesn't work).

> A, A -> A is indeed too restrictive. A, B -> B is the most
> general form. But you also need the final function, if you
> want to address even such relatively simple aggregates
> as avg().

>
>

> > But note, it only makes sense
> > to talk about idempotence for g:A^2->A.

> Agreed.

>
>


> > So you can either

> > restrict g  and thus the class of turquoise functions that

> > you are dealing with, and retain the notion of idempotence,

> > or you can use a more general g, and abandon idempotence.

> > You cannot apply the concept of idempotence to a larger
> > class of turquoise functions by changing the definition of g.

> I don't see why not. If you have a type A, B -> B, you can
> still talk about idempotence. It just implies that A = B.
>

This is silly. I have a function f:A,A->A, but this is too restrictive so I will change this to a function f:A,B->B, but now I want to talk about idempotence so I will let A=B, so I have a function f:A,A->A but this is too restrictive so ...

                                   -William Hughes




>

> > >This second attempt does seem to include all interesting
> > > aggregate functions,

> In fact, I think it includes all computable functions.

>
>


> > >  but I believe that one of the possible definitions

> > > of your NOR function is a counter-example to the equivalence of binary

> > > idempotence and replication insensitivity.  Specifically, that

> > > equivalence is only true when x_0 (which Marshall calls e) is an
> > > identity for the binary function.

> Ah! Rereading this, I think I get it. For example:

> f = OR
> e = T

> f is idempotent, but the resulting aggregate will be
> duplication-insensitive,
> because it is in fact the constant function T. So in the form of the
> fold where you supply a starting value, the starting value has to
> be an identity for f. (Which it is in the common cases, but it isn't
> a requirement.)

>
>


> > > We have been talking about (and even proving) statements about both of

> > > these two mathematical structures.  The only ambiguity relates to which

> > > best captures the very imprecise discussion that was going on before.

> > > For example, early in this thread, Marshall wrote "If the binary form of

> > > the aggregate function is idempotent, the aggregate will return the same

> > > value even if values are repeated arbitrarily." -- and that initially

> > > raised the question of what is meant by the binary form of an aggregate

> > > function.  Unfortunately, mathematics has no answer to the question of

> > > what Marshall meant when he wrote "the binary form of the aggregate

> > > function", so that's why the conversation isn't so cut and dry.

> > >

> >

> > No, but I see no chance of a definition that will allow all

> > interesting turquoise functions to be generated by binary forms

> > without torturing the term "binary form" beyond endurance.

> > [E.g. you could define a binary form to be a function

> > g: M(A) x A -> M(A), but in this case g takes an arbitrary

> > number of elements of A, so calling it a binary form
> > is stretching things]

> I also wouldn't call your g above a binary function. However
> you *can* have this:

> f: A, {A} -> {A}
> f(a, S) = {a} union S

>

Have I got this straight.

S can contain an arbitrary number of elements of A, so f(a,S) takes an arbitrary number of elements of A, but f is despite this a binary form?

                         -William Hughes

Received on Wed Sep 20 2006 - 22:05:22 CDT