Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In this question, all sets are finite. A semigroup is a set equipped with an associative binary operation, which I will call $\circ$. The tranformation semigroup on a set $X$ is the semigroup of maps $X\to X$ with function composition as the semigroup operation. The degree of a semigroup $S$ is the smallest integer $n$ such that $S$ is a subsemigroup (a subset closed under the semigroup operation) of the transformation semigroup on a set of order $n$.

The question is whether there exists $n$ such that for all semigroups of order at least $n$, the degree of $S$ is at most $|S|$.

Every semigroup $S$ can be extended to a semigroup with identity (also called a monoid) $M_S=S\cup\{1\}$, where the semigroup operation $\circ$ is extended by setting $1\circ s=s\circ 1=s$ for all $s\in S$. A semigroup $M$ with identity has degree at most $|M|$, because it is isomorphic to its "regular representation", the semigroup of functions $f_m\colon M\to M$ where $f_m(m')=m\circ m'$. See http://en.wikipedia.org/wiki/Transformation_semigroup#Cayley_representation

Restricting to $S$, this shows that the degree of $S$ is at most $|S|+1$. This cannot be improved to $|S|$. Let $S=\{a,b\}$ and $s\circ s'=a$ for all $s,s'\in S$. Suppose that $S$ was a subsemigroup of the four functions $\{0,1\}\to \{0,1\}$ under composition. Since $S$ does not have an identity elements, we can rule out using the identity function or the swapping function $t\mapsto 1-t$. That leaves only the constant maps. But the constant maps give a different semigroup operation, $s\circ s'=s$.

Clearly a counterexample cannot have an identity element. It is known that there are groups $G$ (and therefore semigroups) of degree $|G|$, for example cyclic groups of order $p^n$ where $p$ prime. (More is known.)

share|improve this question
1  
Have you also tried $n=3$? –  Berci Oct 19 '12 at 18:23
    
It seems that the "$s\circ s'=a$" counterexample generalises to $S=\{a,b,c\}$, by checking cases. A function $f\colon\{0,1,2\}\to\{0,1,2\}$ representing $b$ must satisfy $f\neq f^2=f^3$, and the only options are $0\mapsto 1\mapsto 2\mapsto 2$ and conjugate functions. Then there are no functions left that can represent $c$. –  Colin McQuillan Oct 19 '12 at 19:36

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.