Questions tagged [semigroups-and-monoids]

A semigroup is a set $S$ together with a binary operation that is associative. Examples of semigroups are the set of finite strings over a fixed alphabet (under concatenation) and the positive integers (under addition, maximum, or minimum). A monoid is a semigroup with a neutral element. Of course, any group is also a monoid/semigroup.

Filter by
Sorted by
Tagged with
78 votes
12 answers
12k views

Why aren't representations of monoids studied so much?

It seems to me like every book on representation theory leaps into groups right away, even though the underlying ideas, such as representations, convolution algebras, etc. don't really make explicit ...
Mikola's user avatar
  • 2,342
49 votes
3 answers
2k views

Is each squared finite group trivial?

A semigroup $S$ is defined to be squared if there exists a subset $A\subseteq S$ such that the function $A\times A\to S$, $(x,y)\mapsto xy$, is bijective. Problem: Is each squared finite group ...
Taras Banakh's user avatar
  • 40.7k
41 votes
4 answers
2k views

What is the probability two random maps on n symbols commute?

It is well known that two randomly chosen permutations of $n$ symbols commute with probability $p_n/n!$ where $p_n$ is the number of partitions of $n$. This is a special case of the fact that in a ...
Benjamin Steinberg's user avatar
39 votes
5 answers
4k views

What are the main structure theorems on finitely generated commutative monoids?

I should read J. C. Rosales and P. A. García-Sánchez's book Finitely Generated Commutative Monoids and L. Redei's book The Theory of Finitely Generated Commutative Semigroups. I haven't. But here's ...
John Baez's user avatar
  • 21.3k
33 votes
0 answers
2k views

Is there a (discrete) monoid M injecting into its group completion G for which BM is not homotopy equivalent to BG?

For a (discrete) monoid $M$, the classifying space $BM$ is the geometric realization of the nerve of the one object category whose hom-set is $M$. (This definition gives the usual classfiying space ...
Omar Antolín-Camarena's user avatar
31 votes
5 answers
8k views

How many binary operations are associative?

Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each be ...
Joseph O'Rourke's user avatar
28 votes
1 answer
1k views

Is the Golomb countable connected space topologically rigid?

The Golomb space $\mathbb G$ is the set of positive integers endowed with the topology generated by the base consisting of the arithmetic progressions $a+b\mathbb N_0$ with relatively prime $a,b$ and $...
Taras Banakh's user avatar
  • 40.7k
27 votes
13 answers
4k views

Homological algebra for commutative monoids?

Homological algebra for abelian groups is a standard tool in many fields of mathematics. How much carries over to the setting of commutative monoids (with unit)? It seems like there is a notion of ...
Chris Schommer-Pries's user avatar
25 votes
3 answers
1k views

What spaces $X$ do have $\text{End}(X) \cong \text{End}(\mathbb{R})$?

This is a follow-up on the following question. Let $\text{End}(X)$ denote the endomorphism monoid of a topological space $X$ (that is, the collection of all continuous maps $f:X\to X$ with composition)...
Dominic van der Zypen's user avatar
25 votes
2 answers
1k views

The number of polynomials on a finite group

A function $f:X\to X$ on a group $X$ is called a polynomial if there exist $n\in\mathbb N=\{1,2,3,\dots\}$ and elements $a_0,a_1,\dots,a_n\in X$ such that $f(x)=a_0xa_1x\cdots xa_n$ for all $x\in X$. ...
Taras Banakh's user avatar
  • 40.7k
24 votes
3 answers
2k views

Non-abelian Grothendieck group

By general nonsense the forgetful functor from groups to monoids has a left adjoint. It maps a monoid $(X,\cdot,1)$ to the free group on $\{\underline{x} : x \in X\}$ modulo the relations $\underline{...
Martin Brandenburg's user avatar
22 votes
2 answers
938 views

Mapping from a finite index subgroup onto the whole group

Dear All, here is the question: Does there exist a finitely generated group $G$ with a proper subgroup $H$ of finite index, and an (onto) homomorphism $\phi:G\to G$ such that $\phi(H)=G$? My guess ...
Victor's user avatar
  • 1,427
22 votes
5 answers
2k views

Lie groups vs Lie monoids

Does there exist a well developed theory of a class of objects which might rightfully be called Lie monoids? By this I mean with axioms similar to those of Lie groups, but with the axiomatic existence ...
Benjamin's user avatar
  • 2,069
22 votes
2 answers
1k views

Toposes (topoi) as classifying toposes of groupoids

A famous theorem of Joyal and Tierney says that each Grothendieck topos is equivalent to the classifying topos of a localic groupoid. I believe that Butz and Moerdijk have shown that if the topos has ...
Benjamin Steinberg's user avatar
21 votes
2 answers
3k views

Integer matrices with no integer eigenvalues

Let $$A = \begin{pmatrix} 3&1 \\ 0&1 \end{pmatrix}$$ and $$B = \begin{pmatrix} 1&0\\ 1&2 \end{pmatrix}$$ I want to show that the only elements of the semigroup generated by $A$ and $B$...
Hej's user avatar
  • 1,045
21 votes
1 answer
743 views

Extending $\Bbb N$ to a semiring with isomorphic additive and multiplicative structure

Seen $(\Bbb N,+,\cdot)$ as a semiring, is it possible to extend it to a semiring $(R,+,\cdot)$ so that the additive and multiplicative monoids become isomorphic? This means there is some monoid-...
M. Winter's user avatar
  • 12.5k
21 votes
1 answer
601 views

Grothendieck group of the Fibonacci monoid

Let's denote the Fibonacci numbers by $F_0=0,F_1=1,F_{n+2}=F_{n+1}+F_n \; \forall n \ge 0$. According to Zeckendorf's theorem, every positive integer can be represented uniquely as the sum of some (at ...
Zerox's user avatar
  • 1,111
18 votes
2 answers
1k views

Monoids of endomorphisms of nonisomorphic groups

Can monoids of endomorphisms of nonisomorphic groups be isomorphic ?
Arshak Aivazian's user avatar
18 votes
1 answer
729 views

Are there any "simple" monoids with intermediate growth?

The discovery of the Grigorchuk group which has intermediate growth caused a number of other such groups to be found, but they are all fairly complicated, and as far as I know none of them are ...
saolof's user avatar
  • 1,823
17 votes
12 answers
4k views

Why semigroups could be important?

There is known a lot about the use of groups -- they just really appear a lot, and appear naturally. Is there any known nice use of semigroups in Maths to sort of prove they are indeed important in ...
Victor's user avatar
  • 1,427
17 votes
1 answer
2k views

Do these conditions on a semigroup define a group?

As is well known, if $S$ is a semigroup in which the equations $a=bx$ and $a=yb$ have solutions for all $a$ and $b$, then $S$ is a group. This question arose when someone misunderstood the conditions ...
Arturo Magidin's user avatar
17 votes
0 answers
530 views

Question about combinatorics on words

Let $\{a_1,a_2,...,a_n\}$ be an alphabet and let $\{u_1,...,u_n\}$ be words in this alphabet, and $a_i\mapsto u_i$ be a substitution $\phi$. Question: Is there an algorithm to check if for some $m,k$...
user avatar
16 votes
2 answers
1k views

The symmetric monoidal category of finite sets

It is well-known that the (augmented) simplex category is the universal monoidal category with a monoid object. What about a commutative analogue? Consider the category $\mathsf{FinSet}$ of finite ...
Martin Brandenburg's user avatar
16 votes
1 answer
522 views

Does every commutative variety of algebras have a cogenerator?

By a commutative variety $\mathcal{V}$ I mean a classical variety of algebras for some $(\Sigma,E)$, such that each pair of operations in $\Sigma$ commutes. Equivalently (i) every interpretation of ...
Rob Myers's user avatar
  • 1,261
16 votes
0 answers
1k views

Is the category of smooth manifolds equivalent to the opposite category of the category of commutative monoids of some additive symmetric monoidal category?

This is a followup to my previous question, which asked whether the category of commutative or noncommutative C*-algebras or von Neumann algebras is equivalent to the category of commutative or ...
Dmitri Pavlov's user avatar
15 votes
7 answers
951 views

Statements about groups proved using semigroups

Question. Has a statement about groups ever been proved using the theory of semigroups? By "a proof using the theory of semigroups" I do not mean that some steps in the proof are in fact statements ...
15 votes
2 answers
1k views

Exact sequence of monoids

What is the right definition of an exact sequence of monoid homomorphisms? I can't seem to find a consistent in my searches; indeed Balmer (Remark 2.6, http://www.math.ucla.edu/~balmer/Pubfile/...
John Voight's user avatar
  • 2,929
15 votes
2 answers
648 views

Indecomposable contracting maps on the integers

$\def\ZZ{\mathbb{Z}}$Call a function $f : \ZZ \to \ZZ$ "contracting" if $$|f(j) - f(i)| \leq |j-i|$$ for all $i$, $j \in \ZZ$. The contracting functions form a monoid under composition; call ...
David E Speyer's user avatar
15 votes
5 answers
1k views

Monoids with infinite products

Say a monoid $M$ has infinite products if, for any (possibly infinite) sequence $(m_1,m_2,\ldots)$ of elements of $M$, there exists an element $m_1m_2\cdots\in M$, satisfying some good properties. ...
David Spivak's user avatar
  • 8,549
15 votes
1 answer
2k views

Automorphisms of $P(\Bbb N)$

I believe I've proved that the power semigroup of non-negative integers with addition has a trivial automorphism group. The proof is a bit long, completely elementary and rather unremarkable (as the ...
Michał Masny's user avatar
14 votes
4 answers
730 views

Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$

Prove or disprove: $R^{n+1} \supseteq R \cap R^2 \cap \cdots \cap R^n$ for every binary relation $R$ on a set of size $n$. I have verified the statement for $n \leq 4$ with a Mathematica code. I have ...
Geoffrey Critzer's user avatar
14 votes
2 answers
973 views

Recovering a monoidal category from its category of monoids

What kind of additional properties and/or structures one needs to impose on the category of (commutative or noncommutative) monoids of some monoidal category so that one can recover the original ...
Dmitri Pavlov's user avatar
14 votes
1 answer
753 views

Associativity may fail by little?

It is a well-known result on group theory that if a group has many pairs of commuting elements then it is abelian. This motivated the following pseudo-conjecture. If a (possibly infinite) set $S$ ...
Luis Ferroni's user avatar
  • 1,879
14 votes
1 answer
1k views

When are epimorphisms of algebraic objects surjective?

Let $C$ be the category of $\tau$-algebras for some type $\tau$. Consider the statements: Every monomorphism is regular. Every epimorphism in $C$ is surjective. It is easy to see that 1. implies 2. ...
Martin Brandenburg's user avatar
13 votes
3 answers
966 views

Model Structure/Homotopy Pushouts in topological monoids?

Let $\mathsf C$ be the category of topological monoids, that is, the category of monoids in $(\textsf{Top}, \times)$. Can the model category structure on $\textsf{Top}$ (Serre fibrations, ...
Joey Hirsh's user avatar
  • 1,023
13 votes
3 answers
7k views

$fgf = f$, $gfg = g$, $fg$ not necessarily identity, what is this called?

A very simple question, I just totally forgot how it was called, and Google is not helping. There's a pair of functions $f:X\to Y$, $g:Y\to X$. $fgf = f$, $gfg = g$, but $fg$ and $gf$ don't need to ...
user14613's user avatar
  • 241
13 votes
2 answers
1k views

Economical hard word problem

Can anyone give me an example of a very simple word problem, where by "simple" I mean that it has very few generators and relations, that is nevertheless insoluble. To make the question easier, I am ...
gowers's user avatar
  • 28.7k
13 votes
2 answers
310 views

Semigroup of differentiable functions on real line

Let $D(\mathbb R) $ be the set of all differentiable functions $f: \mathbb R \to \mathbb R$. Then obviously $D(\mathbb R)$ forms a semigroup under usual function composition. Can we characterize (up ...
user102248's user avatar
13 votes
1 answer
1k views

For what sets $X$ do there exist a pair of functions from $X$ to $X$ with the identity being the only function that commutes with both?

It is not too difficult to show that if $X$ is an infinite set, then there exists a two-element subset of the group $\operatorname{Sym}(X)$ with trivial centralizer iff $\lvert X\rvert \leq \lvert\...
cha21's user avatar
  • 328
13 votes
2 answers
688 views

How do you compute the space of lifts of an E-infinity map?

Let X, Y and B be $E_\infty$ spaces, and let $p: X \rightarrow Y$ and $f: B \rightarrow Y$ be $E_\infty$ maps. We can ask for the space of lifts of f across p, that is the space of $E_\infty$ maps $g:...
cdouglas's user avatar
  • 3,083
13 votes
1 answer
541 views

Ultracategories with one object

Historically, the theory of ultracategories was invented by Makkai to prove a strong conceptual completeness theorem for first-order logic, roughly: if $T$ and $S$ are two first-order theories such ...
user480841's user avatar
13 votes
1 answer
1k views

Category without identities?

Just as a monoid is a category with a single object, a semigroup may be seen as a non-unital category, still with associative composition. Then an $S$-set for $S$ a semi-group can be seen as a functor ...
Arrow's user avatar
  • 10.3k
13 votes
1 answer
2k views

Coin problem with permutations

Let $a,b,c$ be positive integers with gcd$(a,b,c)=1$, and let $\mathbb{N}$ denote the set of nonnegative integers. It is well known that $\mathbb{N} \setminus (a \mathbb{N}+b \mathbb{N} + c \mathbb{N}...
Peter Dukes's user avatar
  • 1,071
13 votes
0 answers
239 views

Is every simply connected finite complex the classifying space of a finite monoid

On page 323 of Fiedorowicz, "Classifying Spaces of Topological Monoids and Categories" it was stated that "it seems likely that any finite simply connected complex should [have the same weak homotopy ...
user46652's user avatar
  • 655
12 votes
4 answers
1k views

Why is a monoid with closed symmetric monoidal module category commutative?

Given a symmetric monoidal category and a monoid object A in it, one can form the category of modules over this monoid object, i.e. objects are $A \otimes M \rightarrow M$ satisfying the natural ...
Peter Arndt's user avatar
12 votes
2 answers
727 views

Is the Petersen graph a "Cayley graph" of some more general group-like structure?

The Petersen graph is the smallest vertex-transitive graph which is not a Cayley graph. Is it the "Cayley graph" of some slightly more general group-like structure?
saolof's user avatar
  • 1,823
12 votes
1 answer
581 views

Stone–Čech compactification as a semigroup

Let $G$ be a topological group (we can assume that $G$ is countable and discrete) and let $\beta(G)$ be the Stone–Čech compactification of $G$. It is known that $\beta(G)$ can be turned into a left ...
Serge the Toaster's user avatar
12 votes
1 answer
723 views

Is the following construction of the 0-Hecke monoid (well) known?

Let W be a Coxeter group with Coxeter generators S. The corresponding 0-Hecke monoid H(W) has generating set S, the braid relations of W and the relations that each element of S is an idempotent. If ...
Benjamin Steinberg's user avatar
12 votes
0 answers
310 views

Combinatorial proof of invertibility of a symmetric matrix associated to the ring of matrices over a finite field

Let $F$ be a finite field of $q$ elements with characteristic $p$. Let $M_n(F)$ be the ring of $n\times n$ matrices over $F$. We define a $q^{n^2}\times q^{n^2}$ symmetric matrix $L$ over the ...
Benjamin Steinberg's user avatar
11 votes
6 answers
1k views

Computing the structure of the group completion of an abelian monoid, how hard can it be?

Cherry Kearton, Bayer-Fluckiger and others have results that say the monoid of isotopy classes of smooth oriented embeddings of $S^n$ in $S^{n+2}$ is not a free commutative monoid provided $n \geq 3$. ...
Ryan Budney's user avatar
  • 42.8k

1
2 3 4 5
12