Re: Idempotence and "Replication Insensitivity" are equivalent ?

<pamelafluente_at_libero.it> wrote:
> for an idempotent / assoc / comm function we have
>
> f( 4 3 3 3 3) = f( 4 f(3 3 3 3) ) = f(4 3)
>
> but adding another 4 and using the above result
>
> f( 4 4 3 3 3 3) = f( 4 f( 4 3 3 3 3) ) = f ( 4 f(4 3) )
>
> In general, f(4 3) and f ( 4 f(4 3) ) can be different.
>
> For a duplication insensitive function this cannot happen.
>
> Therefore I meant
>
> f( 4 3 3 3 3) = f( 4 4 3 3 3 3) holds for duplication insensitive
> f( 4 3 3 3 3) = f( 4 4 3 3 3 3) may not hold for idempotence
>
> Therefore
>
> duplication insensitivity does not imply idempotent (n>3)
>
> Make sense?

No. There is an additional requirement that the aggregate function be well-defined. We are not considering binary functions that do not yield well-defined aggregate functions. If f(4 f(4 3)) is not equal to f(4 3), then the aggregate function is not well-defined.

(It turns out that, for your definition, being associative and commutative *is* a necessary and sufficient condition for the aggregate function being well-defined. So the fact that f(4 f(4 3)) must be equal to f(4 3) for the aggregate function to be well defined manifests itself in that if the function is associative and commutative *and* idempotent, then f(4 f(4 3)) = f(f(4 4) 3) [associative property] = f(4 3) [due to idempotence].)

See elsethread for the proofs. If I have time, I'll write them for a consistent notation and set of definitions.

-- 
Chris Smith