Dear Dima Pasechnik,

It seems still unclear. If g is a permutation of a set X of
whatever nature, S a subset of X, then S^g is a set, otherwise one
would expect a message like "Error, <set> must be a set in
...OnSets". That is, S^g is uniquely defined. That is , S^g
should be a set, so the appropriate flag of it is 'yes'.

sorry, now I am I bit confused. You were asking about sets in
general and in particular, why 'AddSet' has some problems with sets of
mutable objects and insertion. I think we now all more or less agree
how to solve these kinds of problems. But 'OnSets' does not use
'AddSet', it will apply <g> to all elements of <S> and then sort the
resulting list. Again for the same reasons that 'AddSet' cannot flag
this list as set, if X contains mutable objects, 'OnSets' will not do
it either. Surely, we can do without the 'IsSet' test but again we
decided to play it safe in order to avoid traps for others, even if
this means that GAP will be slower than possible without these tests.
If however your set X contains unchangeable objects like integers,
yes, one could try a bit harder to keep the information that 'OnSets'
returns a set. It is not clear to what amount this will speed up
things, because the test requires only |<S>|-1 comparisons while the
sort needs something like O(|<S>|*log|<S>|) and one has to check if
the image of <s> in <S> under <g> is again unchangeable. In the very
special case of a list/set of integers <S> and permutation <g> one
could do without tests. I will try to do this in the next version but
the speedup - I guess - will not be dramatical, presumably much
smaller than a factor of 2.

I hope we all now understand the problems with sets, but if there are
any further questions, I think we should discuss them in
"gap-trouble". So if anyone wants more information about the internal
structure of sets, simply send a mail to

"gap-trouble@math.rwth-aachen.de"

(there is no need to subscribe to it). If any new insight will come
out of further discussion, we will report this to the gap-forum.

best wishes
Frank Celler