5 views

Skip to first unread message

Aug 15, 2007, 9:52:46 PM8/15/07

to

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).

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.

Aug 15, 2007, 10:47:20 PM8/15/07

to

In article <25408156.1187229196...@nitrogen.mathforum.org>,

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.

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

Aug 16, 2007, 5:43:44 AM8/16/07

to

On 16 Aug., 03:52, andy <abrod...@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.

>

> However, since K is not an ideal of Z_0, it is not the monoid kernel, ker(f).

> 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

Aug 16, 2007, 7:44:03 AM8/16/07

to

Arturo Magidin <mag...@math.berkeley.edu> wrote:

>

> [...] Universal Algebra. The magic word, parallel to

> "normal subgroup" and "ideal" is "congruence."

>

> [...] 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

Aug 17, 2007, 1:15:57 AM8/17/07

to

Thank you all for your comments.

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

Aug 17, 2007, 10:03:55 AM8/17/07

to

In article <16031308.1187327787...@nitrogen.mathforum.org>,

andy <abro...@mitre.org> wrote:

>Thank you all for your comments.

>

>After this (and consulting MacLane/Birkhoff)

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.

Aug 17, 2007, 10:23:26 AM8/17/07

to

In article <fa49sb$29cl$1...@agate.berkeley.edu>,

Arturo Magidin <mag...@math.berkeley.edu> wrote:

>In article <16031308.1187327787...@nitrogen.mathforum.org>,

>andy <abro...@mitre.org> wrote:

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.

Aug 18, 2007, 12:35:03 AM8/18/07

to

>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'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

Aug 21, 2007, 11:59:29 PM8/21/07

to

On Aug 17, 10:23 am, magi...@math.berkeley.edu (Arturo Magidin) wrote:

> 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

> 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

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu