Re: Idempotence and "Replication Insensitivity" are equivalent ?

Chris Smith wrote:
> William Hughes <wpihughes_at_hotmail.com> wrote:
> > You are correct.
> >
>
> I happen to be reading both discussions.

I am only looking at sci.math

> Perhaps it's better to say
> that Pamela is right about what she proposed here in the sci.math
> newsgroup.

O.K.

> 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, 0) = a
> - For any other value of the second argument P, choose an arbitrary
> member b from P, then
>
> 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.
>

Quite a "technical detail". It is very clear that not all functions  A x M(A) -> A can be characterized as above. How does one find g? (note if g exists it is unique).

> 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})
>

I think you mean f(P) = h(a, 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.
>

g(a,b) idempotent => f(P) replication insensitive is clear

f(P) replication insensitive => g(a,b) idempotent is not obvious to me. I think it's true, but I can't see a clean proof.

Lets call g the generator of f. We have the result (I think)

      If f has a generator g, then f is replication insensitive
      iff g is idempotent.

Note that the function CountUnique can be M(A)->A but does not have a generator g and is replication insensitive. So the set of all functions with generators does not include all interesting functions that are replication insensitive.

• William Hughes