Re: Idempotence and "Replication Insensitivity" are equivalent ?

Chris Smith <cdsmith_at_twu.net> wrote:
> (This is a rough attempt at formalizing the notion of aggregate
> functions. It may contain errors.)

I'm now doubting my definition. Here's an alternate, simpler definition. I've left the original definition in the quoted section for comparison. Any comments on which is superior?

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

OR:

1. Let g: A^2 -> A be a binary function with domain A^2 and codomain A, which is both associative and commutative, and has a unique identity e (i.e., for all a in A, g(a,e) = g(e,a) = 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})

   Because g is associative and commutative, it is guaranteed that    h(a,P) is well-defined. I won't give the proof, but trust me, it's    an easy exercise in induction. ;)

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

   f(P) = h(e,P) [recall that e is the identity of g]

This latter definition is less general, but I don't think you lose anything useful. In particular, the aggregate function was defined in the first definition for choices of g that don't have unique identities (perhaps that don't have identities at all), and allowed something other than f(0) = e even when e was an identity of g.

(The stuff about g being associative and commutative is just a cleaner way of specifying when h and f have well-defined values, so it's not a real change.)

-- 
Chris Smith