Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
up vote 1 down vote accepted

The answer is negative. Let $\mathcal{T}_n$ be the transformation semigroup on $n$ elements and let $S_n = \{s, s^2, \ldots, s^n\}$ be the semigroup defined by $s^{n+1} = s^n$. I will use the following consequence of Green's lemma:

Lemma 1. Let $S$ be a finite semigroup and let $s$ and $t$ be two $\mathcal{J}$-equivalent elements of $S$. If $ts = t$, then $s$ is idempotent.

Proposition. The semigroup $S_n$ is not a subsemigroup of $\mathcal{T}_n$.

Proof. Suppose by contradiction there is an element $s \in \mathcal{T}_n$ such that $s^{n+1} = s^n$ but $s^i \not= s^j$ for $1 \leqslant i < j \leqslant n$. I claim that $s^n <_\mathcal{J} s^{n-1} <_\mathcal{J} \cdots <_\mathcal{J} s$. It is clear that $s^{i+1} \leqslant_\mathcal{J} s^i$ for $1 \leqslant i \leqslant n-1$. Moreover, if $s^{i+1} \mathrel{\mathcal{J}} s^i$, then by Lemma 1 applied to $t = s^i$, $s$ is idempotent, a contradiction. However, $\mathcal{T}_n$ has exactly $n$ $\mathcal{J}$-classes: $J_1 <_\mathcal{J} J_2 <_\mathcal{J} \cdots <_\mathcal{J} J_n$, where each $J_k$ is the set of elements of rank $k$. Thus $s$ necessarily belongs to $J_n$, the group of units of $\mathcal{T}_n$. It follows that $s^n = 1$ and $s^{n+1} = s$, a contradiction.

share|cite|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.