Dear Sage developers,
This e-mail is to request some feedback for:
#17160: Finitely generated axiom for (mutiplicative) magmas, semigroups,
monoids, groups
Context
-------
Currently in Sage, any finite semigroup (set with a multiplication) is
automatically assumed to be a finite enumerated set. The enumeration
can be provided explicitly by implementing __iter__. Otherwise, a
default implementation is provided that assumes that a distinguished
set of generators is provided via semigroup_generators.
This was ok so far, but is too restrictive. In particular, with #8678,
Sage often learns indirectly that a given semigroup is actually
finite, and suddenly asks for __iter__ or semigroup_generators to
exist. This is inconvenient, if not just plain impossible to implement
in some extreme cases.
So #17160 is about refining the categories to distinguish the cases
``finite'' and ``finite with generators''. Of course something similar
will need to be done at some point for the other notions of generation
(for additive structures, for additive and multiplicative structures,...).
There has been some discussion on the ticket, which I try to
synthesize here.
Difficulty
----------
There are actually several concepts that we may want to model for a
semigroup M:
(1) The fact that M is finitely generated: we just know that there
exists a finite set of generators for the semigroup. In particular
a finite semigroup is automatically finitely generated.
(2) The fact that M is endowed with a distinguished enumerated set of
generators, provided by a method semigroup_generators. This makes
M into an enumerated set.
(3) The fact that M is endowed with a distinguished finite enumerated
set of generators. This makes M into an enumerated set, but also
allows for defining the Cayley graph, ...
Note that (3) is a subcase of both (1) and (2); however (1) and (2)
together do not imply (3); the distinguished set of generators might
not be one of the finite ones.
Question 1
----------
At this point, implementing all three concepts seems like overkill. I
don't see a practical use case for (1). I'd say (3) is much more
useful than (2), and tend to only implement it for now.
What do you think?
Question 2
----------
(3) is naturally implemented as an axiom to handle that the fact that
a multiplicative structure (M,*) satisfies (3) does not depend on
whether we see `M` as a magma, a semigroup, a monoid, or a
group. There remains to choose a good name for this axiom.
At this point, there are two reasonable candidates; other suggestions
are welcome:
(a) ``with finite set of generators''; variant: ``with finite generating set``
(b) ``finitely generated''
(a) is very explicit; however it's longish and does not read as
nicely, in part because (b) is so much more common in everyday math
discussions:
sage: Semigroups().WithFiniteSetOfGenerators()
Category of semigroups with finite set of generators
sage: Semigroups().FinitelyGenerated()
Category of finitely generated semigroups
On the other hand, with (b), there is a shift between the math concept
and its model in the computer. The latter insists on being
constructive: a finite set of generators must be provided. This may
lead to some of confusion (why isn't a finite semigroup automatically
finitely generated?).
This is not unheard of though. For many other categories there is a
similar distinction between the pure math concept and the more
constructive concept modeled by the category. An object in Semigroups
is not just a set with some product; the product has to be
distinguished and implemented as '__mult__'. Similarly, for an
Euclidean domain, the division method needs to be implemented.
What do you think?
I personally lean toward (b).
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <nthi...@users.sf.net>
http://Nicolas.Thiery.name/
--
You received this message because you are subscribed to the Google Groups
"sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-devel+unsubscr...@googlegroups.com.
To post to this group, send email to sage-devel@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-devel.
For more options, visit https://groups.google.com/d/optout.
