Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: Chris Smith <>
Date: Mon, 18 Sep 2006 20:55:15 -0600
Message-ID: <>

William Hughes <> wrote:
> You are correct.

I happen to be reading both discussions. Perhaps it's better to say that Pamela is right about what she proposed here in the sci.math newsgroup. The real question is more like this. (This is a rough attempt at formalizing the notion of aggregate functions. It may contain errors.)

  1. Let g: A^2 -> A be a binary function with domain A^2 and codomain A.
  2. Let M(A) denote the set of multisets with elements in A.
  3. Let 0 denote the empty multiset.
  4. Let h: A x M(A) -> A be a function defined as follows:

     h(a, P) = h(g(a, b), P - {b})

   As a technical detail, h remains undefined when its value depends    on the choice of b. In practice, g should be chosen so that this    never happens.

5. Let f: M(A) -> A be a function defined as follows. To evaluate f(P),

   choose an arbitrary member a from P.

   f(P) = h(b, P - {a})

   As with h, f is undefined if its value depends on the choice of a,    and g is expected to be chosen so that this cannot occur.

The question, then, is this: are the following two statements equivalent?

I. f(P) is replication insensitive (i.e., it produces the same result

    regardless of the replication of items in P. II. g(a, b) is idempotent.

I think it's clear that the two statements are equivalent.

Chris Smith
Received on Tue Sep 19 2006 - 04:55:15 CEST

Original text of this message