Questions tagged [monoid]
A monoid is an algebraic structure with a single associative binary operation and an identity element.
830
questions
1
vote
1
answer
54
views
Generating(ish) a free monoid
Let $G=\langle a,b\rangle$ be a free monoid generated by $a,b$. In other words, all possible words made up of $a,b$. Say S is a set of pairs of elements of $G$, say $S=\{(aa,bb),(a,ab)\}$, now we can ...
1
vote
0
answers
26
views
Characterization of monoid-realizable symmetric monoidal categories
Given any symmetric monoidal category $\mathbf{C}$, $\mathrm{Mon}(\mathbf{C})$ (the category of monoids, not necessarily commutative, in $\mathbf{C}$) is also a symmetric monoidal category.
Now, is ...
0
votes
1
answer
53
views
Finite monoids are groups
Are all finite monoids groups?
If I have a monoid $M$ such that $|M|=c$ for an integer $c$, then for all $x\in M$, we should have $x^k=e$ for some minimal $k$. Then, we have $x^{-1}=x^{k-1}$.
I don't ...
0
votes
2
answers
74
views
Show that $\sigma$ is a bijection if and only $u$ is a unit.
The full exercise asks
If $M$ is a monoid and $u \in M$, let $\sigma: M \to M$ be defined by $\sigma(a) = ua$ for all $a \in M$. Show that $\sigma$ is a bijection if and only $u$ is a unit.
The ...
0
votes
1
answer
41
views
Viewing monoid rings as rings with identity in GAP
I look at monoid algebra of finite monoids with GAP and want to force GAP to view them as algebras with one. But it seems it does not work:
...
0
votes
0
answers
14
views
All submonoids of $(\mathbb{Z}_2^n, *)$ that induce an equivalence relation?
I am looking for all the sub-monoids of $(\mathbb Z_2^n, *)$, i.e., binary vectors over bitwise multiplication that induce an equivalence relation as described in Characterize kernels of monoid ...
0
votes
1
answer
32
views
Notational clarification needed about definition and a lemma concerning functor and free monoid
The following question is taken from Arrows, Structures and Functors the categorical imperative by Arbib and Manes.
$\color{Green}{Background:}$
$\textbf{(1)}$ $\textbf{(Definition 1:)}$ The $\textbf{...
2
votes
1
answer
59
views
Term for $eSe$ where $S$ is a semigroup and $e \in S$ is an idempotent
For a (possibly non-unital) ring $R$ and an idempotent $e \in R$, $eRe$ is a unital ring with identity $e$ and is known as a corner ring.
Now, given any semigroup $S$ and any idempotent $e \in S$, $...
1
vote
0
answers
21
views
When is the Frobenius number of a numerical semigroup larger than the maximum of the minimal generating set
Let $S$ be a numerical semigroup (https://en.m.wikipedia.org/wiki/Numerical_semigroup). Let $A$ be the minimal generating set for $S$. As standard, let $e(S)$, $m(S)$ and $F(S)$ stand respectively ...
0
votes
1
answer
34
views
Word reduction and multiplication rules for forming product and coproduct of monoids and free monoids
The following question is taken from Arrows, Structures and Functors the categorical imperative by Arbib and Manes.
$\color{Green}{Background:}$
$\textbf{(1)}$Rules for word reduction for Monoids
$\...
-1
votes
1
answer
51
views
Difference between coproduct of monoids and coproduct/product of free monoids.
I posted about monoid coproduct to try to understand the correct way for constructing them. In the process and from the answer I got, I am further confused whether the product and coproduct of plain ...
1
vote
1
answer
50
views
Binary coproduct for abelian monoid and monoid.
The following is taken from the text $\textit{Algebraic approaches to program semantics}$ by: Arbib and Manes, and "Categories for Types" by Roy L.Crole.
$\color{Green}{Background:}$
$\...
1
vote
1
answer
125
views
Correct Construction of coproduct in category of monoid, and possible misprint?
The following question is taken from Arrows, Structures and Functors the categorical imperative by Arbib and Manes.
$\color{Green}{Background:}$
$\textbf{(1)}$ $\textbf{(Definition 1)}$ A $\textbf{...
0
votes
0
answers
34
views
basis of monoid of integral vectors
Suppose that $M\in\mathbb{Z}^{n\times k}$ is a matrix of rank $k<n$. How can I obtain a set of vectors $b_1,\ldots,b_k\in\mathbb{Z}^k$ (if exists) such that each row of $M$ is a non-negative ...
0
votes
0
answers
31
views
Rank of commutative free monoid and Krull dimension of Monoid ring
We just introduced the notion of the Krull dimension of a ring in class and I was thinking about the following:
Let A be a commutative, noetherian ring with unit and let $n=\text{dim}(A)$ be the Krull ...
0
votes
0
answers
51
views
Correct way for coproduct construction in $\textbf{Abm},$ the category of Abelian monoid?
The following question is taken from Arrows, Structures and Functors the categorical imperative by Arbib and Manes.
$\color{Green}{Background:}$
$\textbf{(1)}$ $\textbf{Definition 1:}$ A $\textbf{...
0
votes
0
answers
21
views
Help with identification of a semiring with an "almost-inverse".
I'm working with an idempotent semiring which have families $C^v, \hat{C^v}$ of elements with the following properties:
$$ {C}^v_i \hat{C_i^v} = 1 $$
$$ \sum_i \hat{C_i^v} {C}^v_i = 1 $$
$$ {C}^v_i \...
0
votes
1
answer
51
views
On writing every integer from $(a-1)(b-1)$ onwards as a sum of two non-zero integers from the semigroup generated by $a,b$
Let $\mathbb N$ be the semigroup (even a monoid) of non-negative integers. Let $a<b$ be relatively prime integers such that $2< a$. Let $S :=\mathbb N a +\mathbb N b$ be the semigroup generated ...
1
vote
1
answer
114
views
When exactly is the preimage of the group of units the group of units?
Let $M$ and $N$ be monoids. Denote by $M^\times$ and $N^\times$ the respective groups of units. Let $f:M\to N$ is a homomorphism of monoids.
Is there a necessary and sufficient condition for the ...
0
votes
0
answers
32
views
Is there a name for this condition on a monoid?
Suppose we have a commutative monoid ${\mathcal M}=\langle M,\otimes\rangle$ such that the usual divisibility relation $\leq_\otimes$ given by $a\leq_\otimes b\Leftrightarrow \exists c(a\otimes c=b)$ ...
1
vote
1
answer
35
views
What is the monoid ring $K[(\Bbb{N}, \text{lcm})]$ isomorphic to?
$(d\mid \cdot)(c\mid \cdot) = (\text{lcm}(d,c) \mid \cdot)$ where $(n\mid x) \in \{0,1\}$ is whether (1) or not (0) $n$ divides $x \in \Bbb{Z}$.
Thus, we can linearly extend all formall $K$-linear ...
1
vote
1
answer
42
views
What does $D(D(f))=D(f)=C(D(f))$ it mean in the category of generalized monoid.
The following question is taken from Arrows, Structures and Functors the categorical imperative by Arbib and Manes
In chapter 7 of Arbib and Manes about Functors. The authors introduce the category ...
1
vote
0
answers
47
views
Is the first-order theory of the class of free monoids finitely axiomatizable? [closed]
I asked long ago whether the class $C$ of free monoids is a first-order axiomatizable class. The answer was no. However, the class $C$ does have an associated first-order theory $Th(C)$. Is that ...
1
vote
1
answer
56
views
Recalling a theorem from vague memory: A monoid, in some sense, cannot "describe" the language (over one letter?) of words of prime length.
It has been over a decade (already!) since I studied a module on formal languages & automata during my undergraduate Mathematics degree. In considering a few things in combinatorial group theory (...
3
votes
1
answer
82
views
Show that $A\star B=\{a*b:(a,b)\in A\times B\}$ in $\mathcal P(X)$ is associative or commutative iff $*$ in $X$ is it.
If $*$ is a binary operation on a set $X$ then it is costum to define
$$
\tag{1}\label{1}A\star B:=\{x\in X:x=a*b\text{ with } (a,b)\in A\times B\}
$$
for any $A,B\in\mathcal P(X)$. So it seemed to me ...
4
votes
1
answer
75
views
Non-cancellative commutative monoids in which no element absorbs another
A commutative monoid $M$ is cancellative if $a + c = b + c$ implies $a = b$ for all $a,b,c \in M$. Let's call $M$ positive if $a + b = a$ implies $b = 0$ for all $a,b \in M$ (i.e. no element absorbs ...
6
votes
0
answers
64
views
Multiplicative Subsets of the Natural Numbers and Unique Factorization
Elementary number theory books often give as an example of non-unique factorization the set $S = \{4k+1: k \in \mathbb{N}\}$. $S$ doesn't have unique factorization because $(3 \cdot{7})(11 \cdot {19}) ...
2
votes
1
answer
41
views
Something similar to Kronecker basis theorem for semigroup
I know for abelian group, there is a Kronecker decomposition theorem. It said any finite abelian group can be factored as direct sum of cyclic group of prime power order.
I want to know is there ...
0
votes
1
answer
77
views
A monoid $M$ is $\omega$-presentable in the category $M$-$\mathbf{Set}$
I feel that this is true but I'm unable to prove it formally: a monoid $M$ is $\omega$-presentable in the category $M$-$\mathbf{Set}$. This is the category of $(X,\rho)$ where $\rho:M\times X\to X$ ...
2
votes
1
answer
87
views
Grothendieck group of a monoid with zero
I am currently studying the Grothendieck group and its construction from a commutative monoid $M$. I am troubled by the following question that came to my mind in recent days. Please help me.
My ...
0
votes
0
answers
30
views
Generalization of free magmas for nested structures
Consider a nonempty set $X$. What is the name / concept that gives rise to (the set of) all $X$ labeled planar trees e.g.
...
0
votes
1
answer
56
views
Clarifications needed in an exercise about semilattice and abelian monoids in Arbib and Manes' text
The following question is taken from Arrows, Structures and Functors the categorical imperative by Arbib and Manes
Exercise: A $\textbf{semilattice}$ is a poset in which every finite subset has a ...
4
votes
0
answers
96
views
For an even multivector $A$, if the map $X\mapsto AX\tilde A$ preserves grade, must $A$ be a product of vectors?
We're working in a Clifford algebra over a non-degenerate $n$-dimensional vector space $V$, and considering various properties a multivector $A$ could have:
(0) $A$ is invertible.
(1) $\tilde AA$ is a ...
0
votes
0
answers
33
views
Failure of the Rees structure theorem for $0$-simple compact semigroups
A compact semigroup is a compact Hausdorff space $S$ with a continuous semigroup multiplication $S×S→S$. An ideal in a semigroup $S$ is a subset $A$ such that $AS ⊆ A$ and $SA ⊆ A$. A semigroup is ...
1
vote
0
answers
52
views
Why do symmetric monoidal structures have such a confusing name? [closed]
I've been reading Spivak and Fong's "An invitation to applied category theory" and I read that a monoid is a function $*$, called monoid multiplication for which:
There is a specific ...
1
vote
0
answers
29
views
Monoid with torsion elements
I am currently studying construction of the Grothendieck group of a commutative monoid $M$. I was looking for an example of a monoid that is torsion, namely, I have the following query.
Does there ...
0
votes
0
answers
38
views
The free semiring on the Boolean monoid
Recall the following definitions:
The Boolean monoid is the monoid $\mathbb{B}=(\{0,1\},\max,0)$;
The free semiring on a commutative monoid $A$ is the semiring $\mathrm{Free}(A)$ consisting of
The ...
2
votes
1
answer
59
views
If $N$ is a subset of a monoid $(M,\bot ,e)$ with identity element $\epsilon$ with respect $\bot$ then does the equality $\epsilon=e$ holds?
If $(M,\bot,e)$ is a monoid then it is usually to say that $N$ in $\mathcal P(M)$ is a submonoid of $(M,\bot, e)$ if it is closed under $\bot$ and it contains $e$. So by this definition I suspect that ...
5
votes
1
answer
42
views
Show that a semi-group (E,T) (I.e., with T associative) satisfying a certain property is a monoid (i.e., possesses a neutral element)
Let $E$ be a set with an internal operation $T$ associative such that there exist $a \in E$ such that :
$(∀y\in E) (\exists x\in E) \ y=aTxTa$
Prove that $(E;T)$ has an identity element.
What I have ...
1
vote
1
answer
56
views
Grothendieck group.
I am studying Grothendieck group, and I have the following in my mind.
Let $M$ be a monoid and $N$ be a submonoid of $M$. If $\Gamma(M)$ is the Grothendieck group $M$ and $\Gamma(N)$ is the ...
-1
votes
1
answer
26
views
A monoid structure $*$ on all of $\Bbb{Z}$ isomorphic to $A \Bbb{Z} + 1$ for some $A \neq 0,1$ is such that $\Bbb{Z}*\Bbb{Z}$ has infinite complement.
Let $\Bbb{Z}_*$ be the monoid structure $x * y := Axy + x + y$ for some fixed $A \in\Bbb{N}$, $A \gt 1$.
Then $\Bbb{Z}_* \approx A\Bbb{Z} + 1$ is easy for me to prove on one line (see added Lemma 0 ...
0
votes
1
answer
28
views
If $f$ is a epimorphism from the monoid $(X,⊕,x_0)$ to the monoid $(Y,⊗, y_1)$ then $f(x_0)=y_1$ and $f(x^{-1})=f(x)^{-1}$ provided $x^{-1}$ exists.
Well, I know that if $f$ is a homomorphism from the group $(X,\oplus, x_0)$ to the group $(Y,\otimes, y_1)$ then $f(x_0)$ is $y_1$ and moreover the image of an invertible element of $X$ is an ...
2
votes
0
answers
55
views
If $(G, \cdot)$ is a monoid, then $(\mathcal{P}(G), \cup, \cdot)$is a ring
Let $(G, \cdot)$ be a monoid. On $\mathcal{P}(G)=\{ X \mid X \subseteq G \}$ we define an operation deduced from $\cdot$, namely, if $A, B \in \mathcal{P}(G), AB=\{ab \mid a \in A \land b \in B\} \;$(...
5
votes
2
answers
88
views
algebraic structure of modular multiplication
Consider the set ${\mathbb Z}_N = \{0, \ldots, N-1\}$ under multiplication modulo $N$. When $N=pq$ with $p, q$ relatively prime, ${\mathbb Z}_N$ and ${\mathbb Z}_p \times {\mathbb Z}_q$ are isomorphic ...
0
votes
2
answers
98
views
Solve $x^n=1$ in a monoid.
Let $(X, *)$ a monoid with identity $e$. So can the equality
$$
x^n=e
$$
hold for some $n\ge 1$ when $x$ is not equal to $e$? If this can be true what is an example? If this is not true how prove it?
3
votes
1
answer
91
views
When does this construction always yield a congruence?
Suppose $\mathcal{M}$ is a commutative monoid and $E$ is any equivalence relation on $\mathcal{M}$. Define $\widehat{E}$ to be the "shift-invariant" part of $E$, that is, $$a\widehat{E}b\...
0
votes
0
answers
33
views
basis of a module under monoid actions
Let $(M,\tau,+,\cdot,0,1)$ be a topological commutative ring. And let $(M, \circ, id)$ be a monoid such that $\circ $ on the right distributes over $+$ and $(x\cdot y ) \circ z = x\cdot (y\circ z)$. (...
0
votes
0
answers
43
views
Set of all the subgroups of $G$. [duplicate]
The set of all the subgroups of a group $G$ is a commutative monoid under set intersection, with $G$ as identity. Say $\mathcal G$ this monoid. We get:
$G$ is the only invertible element of $\mathcal ...
0
votes
1
answer
25
views
Construction of Free modules in a monoidal category
Let $(C,\otimes , 1^C , \alpha , \lambda , \rho)$ be a monoidal category and let $\mathsf{Mon}_C$ be the category of monoids in $C$. And let $A \in \mathsf{Mon}_C$. Denote the category of $A$-modules ...
9
votes
1
answer
278
views
When does a semigroup homomorphism preserve identities on monoids?
Let $X,Y$ be monoids, with identities $e_X,e_Y$, respectively. Let $f:X\to Y$ be a semigroup homomorphism. That is, any function which satisfies
$$f(xy)=f(x)f(y)\quad\forall x,y \in X\tag{1}$$
I know ...