Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: William Hughes <>
Date: 20 Sep 2006 19:03:50 -0700
Message-ID: <>

Chris Smith wrote:
> <> 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. Marshall's comments can only apply to this subset [whether the subset should be called the aggregate functions is a different issue].

> 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). But note, it only makes sense to talk about idempotence for g:A^2->A. 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.

>This second attempt does seem to include all interesting
> aggregate 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.
> 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]

                                   -William Hughes

                                            - William Hughes
Received on Thu Sep 21 2006 - 04:03:50 CEST

Original text of this message