[FrontPage] [TitleIndex] [WordIndex

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

../HW9/Solutions are available.

1. Maximization

  1. Let A be the semigroup (N, max), where max(a,b) = a if a > b or b otherwise. Prove that every subset of N yields a subsemigroup of A.

  2. Now let M be the monoid (N, max, 0) obtained by extending A with the identity 0. Determine which subsets of N yield submonoids of M.

2. Egalitarian semigroups

Define an egalitarian semigroup to be a semigroup in which wx=yz for any elements w, x, y, and z.

  1. Prove or disprove: If A and B are egalitarian semigroups, then any function f:A->B is a homomorphism.

  2. Give a formal definition of a free egalitarian semigroup F(S) over a set S, by defining both its set of elements and the effect of its semigroup operation. Prove that the structure you defined satisfies the definition of a free algebra given in AlgebraicStructures: specifically, that F(S) is an egalitarian semigroup that contains all the elements of S, and for any function f from S to the carrier of some egalitarian semigroup G, there is a unique homomorphism f*:F(S)->G such that f*(x)=f(x) for all x in S.

3. Quotients

Let A be the free monoid over {a,b} and B be the free monoid over {b}. Define a function f:A->B where for each sequence x, f(x) is the sequence obtained by removing all occurrences of a from x: for example, f(ababab) = f(bbab) = bbb and f(aaa) = <>.

  1. Show that f is a homomorphism. (Hint: Use the fact that A is a free algebra.)
  2. Let ~ be the kernel of f. Show that A/~ is isomorphic to (N,+,0).

4. Back to the center

Let G be a group, and let C = { a∈G | ax = xa for all x in G }. Show that C is an abelian subgroup of G.

2014-06-17 11:57