"kernel" of a monoid homomorphism
andy
Take the multiplicative monoids Z_0=Z\{0} and N, and define a mapping f: Z_0 --> N by f(x)=|x|.
It follows that f is a monoid homomorphism from Z_0 onto N.
The pre-image of {1} under f, K={1,-1}, resembles the group-theoretical kernel.
However, since K is not an ideal of Z_0, it is not the monoid kernel, ker(f).
Similar thoughts go for the "cosets" of K, {x,-x}, and the "factor" monoid, Z_0 / K.
Do these constructions have proper names in semigroup theory? Is this homomorphism significant in any way?
The actual example I'm working with is a bit more complicated in that, for example, a "coset" does not appear from the composition of an arbitrary element of Z_0\K and K.
Arturo Magidin
andy <abro...@mitre.org> wrote:
>I've encountered an example of the following type:
>
>Take the multiplicative monoids Z_0=Z\{0} and N, and define a mapping
>f: Z_0 --> N by f(x)=|x|.
>
>It follows that f is a monoid homomorphism from Z_0 onto N.
>
>The pre-image of {1} under f, K={1,-1}, resembles the
>group-theoretical kernel.
Perhaps, but that is not a good analogue in the case of semigroups and
monoids.
>However, since K is not an ideal of Z_0, it is not the monoid kernel, ker(f).
>
>Similar thoughts go for the "cosets" of K, {x,-x}, and the "factor"
>monoid, Z_0 / K.
>
>Do these constructions have proper names in semigroup theory? Is this
>homomorphism significant in any way?
>
The correct analogue of the kernel for monoids and semigroups takes
the form of a congruence. Namely, define an equivalence relation on
Z_0 by:
x~y if and only if f(x)=f(y).
Considering this equivalence relation as a set of pairs, it is a
subset of the monoid K x K. It is easy to verify that it is in fact a
submonoid of K x K, under the obvious operations.
You can then define operations on the set of congruence classes of this
equivalence relation. If we let [x] denote the congruence class of x,
then we define [x]*[y] = [x*y]. This is well defined, as is not too
hard to verify. This monoid is called the quotient of K modulo the
equivalence relation, K/~
We can then define the induced map F: K/~ -> N given by F([x])=f(x),
and this is an isomorphism.
In fact, you can do the exact same thing with groups and rings. The
thing is that if you have an equivalence relation on a group G such
that the graph of the relation is a subgroup of GxG, then it is easy
to see that a~b if and only if ab^{-1} ~ 1; the "normal subgroup" is
in fact the collection of all elements equivalent to 1. For rings, the
ideal is the set of all elements equivalent to 0.
The reason this breaks down for semigroups and monoids is that you do
not have the equivalence a~b if and only if ab^{-1}~1, so the
equivalence class of 1 is not enough to "reconstruct" the entire
equivalence relation.
The semigroup/monoid case is a special case of the Homomorphism and
Isomorphism theorems of Universal Algebra. The magic word, parallel to
"normal subgroup" and "ideal" is "congruence."
--
======================================================================
"It's not denial. I'm just very selective about
what I accept as reality."
--- Calvin ("Calvin and Hobbes" by Bill Watterson)
======================================================================
Arturo Magidin
magidin-at-member-ams-org
hagman
> I've encountered an example of the following type:
>
> Take the multiplicative monoids Z_0=Z\{0} and N, and define a mapping f: Z_0 --> N by f(x)=|x|.
>
> It follows that f is a monoid homomorphism from Z_0 onto N.
>
> The pre-image of {1} under f, K={1,-1}, resembles the group-theoretical kernel.
>
> However, since K is not an ideal of Z_0, it is not the monoid kernel, ker(f).
Did I miss something here?
i:K->A is called kernel of f:A->B if
f o i is the zero morphism (factors over the zero object)
and for any morphism g:X->A such that f o g is the zero morphism,
there exists a unique morphism h:X->K such that g = i o h.
Given a monoid homomorphism f:A->B,
let K be the preimage of the neutral element e in B,
K={a in A | f(a)=e } and i:K->A the inclusion map.
Then K is clearly a monoid and i is a monoid homomorphism.
Also f o i is clearly the zero morphism (i.e. maps everything
to the neutral element).
Let g:X->A be a monoid homomorphism such that f o g is
the zero morphism.
Then g(x) in K for all x in X and thus g can be viewed
as a map (now named h) from X to K. We have g = i o h.
The map h is obviously a monoid homomorphism and uniquely
determined.
Thus (K,i) *is* the kernel of f in the category of monoids.
>
> Similar thoughts go for the "cosets" of K, {x,-x}, and the "factor" monoid, Z_0 / K.
>
> Do these constructions have proper names in semigroup theory?
Now you are talking about semigroups, not monoids.
Not everybody uses these terms synonymously and I guess you don't
mean to either.
> Is this homomorphism significant in any way?
>
> The actual example I'm working with is a bit more complicated in that, for example, a "coset" does not appear from the composition of an arbitrary element of Z_0\K and K.
Yep, your example was probably "too simple" since Z_0 = N x K.
hagman
Bill Dubuque
>
> [...] Universal Algebra. The magic word, parallel to
> "normal subgroup" and "ideal" is "congruence."
And in fact there are general notions of "ideal"
that are studied in universal algebra, e.g. see the
following paper, whose foreward is excerpted below.
ON SUBTRACTIVE VARIETIES IV: DEFINABILITY OF PRINCIPAL IDEALS
http://www.mat.unisi.it/~agliano/fosv4.ps
Paolo Agliano and Aldo Ursini
0. Foreword
We have been asked the following questions:
(a) What are ideals in universal algebra good for?
(b) What are subtractive varieties good for?
(c) Is there a reason to study definability of principal ideals?
Being in the middle of a project in subtractive varieties,
this seems the right place to address them.
To (a). The notion of ideal in general algebra [13], [17], [22] aims
at recapturing some essential properties of the congruence classes of 0,
for some given constant 0. It encompasses: normal subgroups, ideals
in rings or operator groups, filters in Boolean or Heyting algebras,
ideals in Banach algebra, in l-groups and in many more classical
settings. In a sense it is a luxury, if one is satisfied with the
notion of "congruence class of 0". Thus in part this question might
become: Why ideals in rings? Why normal subgroups in groups? Why filters
in Boolean algebras?, and many more. We do not feel like attempting any
answer to those questions. In another sense, question (a) suggests similar
questions: What are subalgebras in universal algebra good for? and many
more. Possibly, the whole enterprise called "universal algebra" is
there to answer such questions?
Having said that, it is clear that the most proper setting for a theory
of ideals is that of ideal determined classes (namely, when mapping a
congruence E to its 0-class 0/E establishes a lattice isomorphism between
the congruence lattice and the ideal lattice). The first paper in this
direction [22] bore that in its title.
It comes out that -- for a variety V -- being ideal determined is the
conjunction of two independent features:
1. V has 0-regular congruences, namely for any congruences E,E'
of any member of V, from 0/E = 0/E' it follows E = E'.
2. V has 0-permutable congruences, namely for any congruences E,E'
of any member of V, if 0 E y E' x, then for some z, 0 E' z E x.
Investigating them separately -- in our case we deal with the latter --
points out at what depends in fact only on 0-permutability and not on
0-regularity.
Our results want to apply first of all to ideal determined varieties,
even if we do not formulate the corollaries explicitly. For instance,
the following is true (as a trivial corollary of Proposition 4.1 below):
An ideal determined variety V is congruence distributive iff for any
algebra A in V, for any a,b in A, the intersection of the principal
ideals (a)_A, (b)_A is equal to their commutator.
Then one may want to apply this fact to varieties of groups or rings ...
Thus the only variety of groups which is congruence distributive is the
trivial variety, and a variety of rings is arithmetical iff the
intersection of any two principal ideals equals their product.
This is well known but we get it as a particular case of a corollary of
an interpretation of Proposition 4.1. We felt that pursuing that course
in each case, namely giving the explicit application of our results to
ideal determined varieties, would be too much for the reader. In fact
the reader may get these results at once when he wishes to.
...
http://www.mat.unisi.it/~agliano/fosv4.ps
--Bill Dubuque
andy
After this (and consulting MacLane/Birkhoff) I feel somewhat enlightened, although it seems to me that there still might be some useful analogies between equivalence classes and cosets, at least in some limited cases, that I havent seen spelled out in texts (for some reason the literature on cosets, even in groups, appears very modest)
I also suffered from misreading Grillet on the concepts of the kernel of a semigroup homomorphism and the kernel of a semigroup, which I initially presumed is the same thing (the second IS an ideal, the first is not).
Arturo, I believe you mean Z_0 x Z_0 and Z_0/~, not K x K and K/~, in your comments.
Andrzej Brodzik
Arturo Magidin
andy <abro...@mitre.org> wrote:
>Thank you all for your comments.
>
>After this (and consulting MacLane/Birkhoff)
Pet peeve: correct spelling is Mac Lane (with a space).
>I feel somewhat enlightened, although it seems to me that there still
>might be some useful analogies between equivalence classes and
>cosets, at least in some limited cases, that I havent seen spelled
>out in texts (for some reason the literature on cosets, even in
>groups, appears very modest)
Not sure what you mean by "useful analogies"; cosets ->are<-
equivalence classes. If you have a group G and a subgroup H, the
equivalence relation a =_H b if and only if ab^{-1} is in H makes the
right cosets into the equivalence classes of the relation; while the
relation a _H= b if and only if b^{-1}a is in H makes the left cosets
into equivalence classes.
>I also suffered from misreading Grillet on the concepts of the kernel
>of a semigroup homomorphism and the kernel of a semigroup, which I
>initially presumed is the same thing (the second IS an ideal, the
>first is not).
>Arturo, I believe you mean Z_0 x Z_0 and Z_0/~, not K x K and K/~, in your comments.
No, I meant what I wrote. In universal algebra, if A is an algebra,
then a "congruence ~ on A" is an equivalence relation that is a
subalgebra of A x A (under pointwise operation). The equivalence
classes under ~ can be made into an algebra by operating on
representatives, and this quotient algebra is denoted by A/~.
See for example the Homomorphism Theorem (Theorem 6.12, p 50) in
Burris-Sankappanavar's "A Course in Universal Algebra", available at
http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html
or the Homomorphism Theorem (Theorem 1, Section 11, Chapter 1, p 57)
in Gratzer's "Universal Algebra", van Nostrand Co., 1969; or the
discussion of congruences in monoids (Section 3.10, pp 60-62) in
George Bergman's "An Invitation to General Algebra and Universal
Constructions", available at:
http://math.berkeley.edu/~gbergman/245/
I highly recommend the last one as an introduction to Universal Algebra.
Arturo Magidin
Arturo Magidin <mag...@math.berkeley.edu> wrote:
>In article <16031308.1187327787...@nitrogen.mathforum.org>,
>andy <abro...@mitre.org> wrote:
[...]
>>Arturo, I believe you mean Z_0 x Z_0 and Z_0/~, not K x K and K/~, in your comments.
Oops, you're right. I misread this on first reading, as if you were
saying the quotient should be denoted AxA/~ instead of A/~. And you
are correct that I used K, what you defined to be the kernel, rather
than your algebra.
Sorry about that. Still, I recommend the books I mentioned, especially
George Bergman's.
andy
I've meant it the other way around: when congruence classes are specified on monoids that are not groups, and they still behave a bit like cosets; in the simple example of f:Z_0-->N, each set {x,-x} can be obtained by the multiplication {x,-x}=x{1,-1}=-x{1,-1}; there are other, less trivial examples when this does not quite work, but almost: an element in a congruence class can be found that generates the entire class by a composition with the pre-image. Perhaps this is not important, but interesting nevertheless (to me, at least).
Thank you for the references; Bergman is, indeed, helpful.
Andrzej
ren...@mitre.org
> In article <fa49sb$29c...@agate.berkeley.edu>,
>
> Arturo Magidin <magi...@math.berkeley.edu> wrote:
> >In article <16031308.1187327787848.JavaMail.jaka...@nitrogen.mathforum.org>,
> >andy <abrod...@mitre.org> wrote:
>
> [...]
>
> >>Arturo, I believe you mean Z_0 x Z_0 and Z_0/~, not K x K and K/~, in your comments.
>
> Oops, you're right. I misread this on first reading, as if you were
> saying the quotient should be denoted AxA/~ instead of A/~. And you
> are correct that I used K, what you defined to be the kernel, rather
> than your algebra.
>
> Sorry about that. Still, I recommend the books I mentioned, especially
> George Bergman's.
>
> --
> ======================================================================
> "It's not denial. I'm just very selective about
> what I accept as reality."
> --- Calvin ("Calvin and Hobbes" by Bill Watterson)
> ======================================================================
>
> Arturo Magidin
> magidin-at-member-ams-org
Arturo and Andy,
Here's the problem: the definition of kernel of a homomorphism
commonly used in semigroup (and monoid) theory does not agree with the
definition used in group theory. This is awkward since all groups are
semigroups and monoids. If we talk about the kernel of a homomorphism
f between groups A and B, readers expect us to be talking about the
pre-image of the identity in B, i.e., the set of all a in A for which
f(a) = 1_B. But A and B are also monoids and semigroups, and the
definition of the kernel of f for monoids and semigroups says that the
kernel of f is the equivalence relation induced by f, which is a very
different thing. The problem is acute for a homomorphism between
monoids, for which a pre-image of the identity exists, but for which
common usage in semigroup (or monoid) theory would seem to prevent us
from calling that pre-image a kernel. I think the semigroup
literature has a problem here. The definition of kernel for a
semigroup homomorphism ought to give us the same kernel of the
homomorphism when the domain and codomain of the homomorphism are
groups. Personally, I think the semigroup literature should
substitute a term such as "congruence of the homomorphism" rather than
"kernel" for the equivalence relation induced by the homomorphism, and
leave the term kernel for the pre-image of the identity.
- Rob Enders