Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By Deveno

Math Help - Quotients of Semi-groups or Monoids?

  1. #1
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,407
    Thanks
    523

    Quotients of Semi-groups or Monoids?

    Let A be the set of all strictly increasing sequences of integers. Define a binary operator +: A\times A \to A by (a_n)_{n\ge 1} + (b_n)_{n\ge 1} = (a_n+b_n-n)_{n\ge 1}. The pair (A,+) is a monoid. Define a sequence of functions for k\ge 1, \varphi_k:A\to A by \varphi\left( (a_n)_{n\ge 1}\right) = (a_{n+k}-a_k)_{n\ge 1}. It is easy enough to check that each function in the sequence is a homomorphism, and for each k, \ker(\varphi_k)\subseteq \ker(\varphi_{k+1}). Let \displaystyle B=\bigcup_{k\ge 1} \ker(\varphi_k). Questions: Is B a sub-monoid of A? Is there a way to "mod-out" by B?

    Edit:

    Some additional info:
    The identity element is the sequence (n)_{n\ge 1}. The sets, \ker(\varphi_k)=\{(a_n)\in A\mid \forall n>k, a_{n+1}=a_n+1\} are all closed under addition. Does the set B=\{(a_n)\in A\mid \exists N\in \mathbb{N} \forall n>N, a_{n+1}=a_n+1\}? If so, it should be closed under addition, as well. I forgot to mention that (A,+) is commutative. So, if "modding out" does make sense in this context, cosets would have the form (a_n)+B. Without inverses, I have no idea how to tell if two sequences are in the same left coset.
    Last edited by SlipEternal; February 16th 2013 at 09:21 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,407
    Thanks
    523

    Re: Quotients of Semi-groups or Monoids?

    From what I can gather, what I am attempting just doesn't make any sense. I am gonna try embedding the monoid into the group of all integer sequences and using relations to find subgroups. Such as (b_n) := (a_n)-n. Now, I am looking for all (b_n) that are eventually constant. Essentially, I am looking for a way to group together sequences based on how uniform they eventually become.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,154
    Thanks
    593

    Re: Quotients of Semi-groups or Monoids?

    quotient monoids are determined by congruences, so we have to show that B induces a congruence on A (our original monoid).

    that is to say we need to show that: ((an) + B) + ((bn) + B) = ((an) + (bn)) + B is well-defined.

    the way you show (an) + B = (a'n) + B is to show there is a k for which:

    φN((an)) = φN((a'n)) for all N ≥ k.

    now if (an) + B = (a'n) + B, and (bn) + B = (b'n) + B), there is a k such that:

    φN((an)) = φN((a'n)) for all N ≥ k, and a k' such that:

    φN((bn)) = φN((b'n)) for all N ≥ k'.

    so choose k" = max(k,k'). then for all N ≥ k":

    φN((a'n) + (b'n)) = φN((a'n)) + φN((b'n)) = φN((an)) + φN((bn))

    = φN((an) + (bn)), so ((an) + (bn)) + B = ((a'n) + (b'n)) + B.

    more formally, what we have done is defined a relation ~ by: (an) ~ (bn) iff there exists k such that φN((an)) = φN((a'n)) for all N ≥ k.

    what is shown above shows that if ~ is an equivalence relation, it IS a congruence, and we can speak of A/~. verification that ~ is an equivalence is tedious, and rather unenlightening (symmetry and reflexiveness are immediate, and we can use the same "max trick" to show transitivity).

    note that doing this only separates increasing sequences in terms of "how far they deviate from (n)", A/~ is still quite large. for example if (an) + B ≠ (a'n) + B, then one is more "increasingly increasing" (eventually).
    Thanks from SlipEternal
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,407
    Thanks
    523

    Re: Quotients of Semi-groups or Monoids?

    Ok, that makes a lot more sense. I was digging through information on universal algebras, and now that I see what you did, I understand what I was reading. And now I think I understand much better what I want. The kernel of the homomorphism is really not terribly useful. I think what I want is to define the relation:
    (a_n) \sim (b_n) if and only if there exists i,j such that \varphi_i (a_n) = \varphi_j (b_n).

    Reflexivity and symmetry are again immediate. Now, suppose (a_n)\sim (b_n) and (b_n) \sim (c_n). That means there exists i,j,i',j' such that \varphi_i((a_n)) = \varphi_j((b_n)) and \varphi_{j'}((b_n)) = \varphi_{i'}((c_n)). So, let j''=\max(j,j'). Then \varphi_{i+j''-j}((a_n)) = \varphi_{j''}((b_n)) = \varphi_{i' + j''-j'} ((c_n)) implies (a_n)\sim (c_n), and transitivity is evident. So, now, what might the equivalence classes of A/\mathopen{\sim} look like? Would it be difficult to classify sequences by which equivalence class they were in?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. semi-metric spaces and qausi-semi developable
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: July 18th 2011, 01:38 AM
  2. Monoids with two elements
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 25th 2009, 09:33 PM
  3. Monoids and Groups
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: September 4th 2009, 10:21 AM
  4. Monoids and Groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 4th 2009, 10:16 AM
  5. Semi-Groups
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 22nd 2006, 02:55 PM

Search Tags


/mathhelpforum @mathhelpforum