Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: William Hughes <>
Date: 21 Sep 2006 05:44:10 -0700
Message-ID: <>

Marshall wrote:
> William Hughes wrote:
> > Marshall wrote:
> >
> > The question posed by the title of this thread "are idempotence
> > and replication insensitivity equivalent?". Since idempotence
> > only applies to functions of the type A,A->A we get that
> > idempotence only applies to a restricted set of functions
> > on M(A). Since this restricted set does not include all
> > the functions we would like to apply the term "replication
> > insensitive" to, I would conclude that the terms
> > "idempotent" and "replication insensitive" are not equivalent.
> Well, they were never proposed to be *equivalent*, at least
> not by me. The two kinds of functions have different types,
> for one thing. They certainly look *related* though.

Then we agree completely.
(See e.g. the last line of my first post in this thread "The two concepts while related are not the same.")

 [For what its worth, I never
disagreed with you. My entire contribution to this thread was my initial response to the OP and subsequent discussions triggered by Chris Smith's claim that the OP had misrepresented the argument. ]

> The proposal is that an aggregate function defined
> by a fold of a function f will be "duplicate insensitive"
> iff f is idempotent. Chris has pointed out the additional
> requirement that the starting value for the fold has to
> be an identity of f.
> Has there been a counterexample? I went back over the
> thread and I couldn't find one; however my eyes started
> glazing over after rereading about 30 posts. There have
> been quite a few posts proposing counterexamples, but
> none of them have held up, again assuming I didn't miss
> something critical.
> Anyway, do you have a counterexample? Please bear
> in mind that:
> 1) I agree that "idempotence" only applies to functions of
> type A, A -> A
> 2) I agree that an arbitrary function of type {|A|} -> B
> might be duplicate insensitive but not have an associated
> idempotent binary function. (For example, the function:
> f:{|A|} -> nat
> f(x) = 7
> )

I do not have a counterexample and indeed believe that, if not this, something very close to this will hold.

                           -William Hughes
Received on Thu Sep 21 2006 - 14:44:10 CEST

Original text of this message