# Thread: Quotients of Semi-groups or Monoids?

1. ## 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:

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.

2. ## 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.

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

4. ## 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?