The complete Brandt semigroup of trivial charts:
Let $PS_n$ be the symmetric inverse semigroup on $n$ elements. Then the semigroup with zero of the complete thin groupoid $K_n + 0$ is a Brandt semigroup consisting of all trivial charts on $n$ elements. Chart representation makes $K_n + 0$ a subsemigroup of $PS_n$.| $\emptyset$ | (0,0) | (1,1) | (0,1) | (1,0) | |
|---|---|---|---|---|---|
| $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ | $\emptyset$ |
| (0,0) | $\emptyset$ | (0,0) | $\emptyset$ | (0,1) | $\emptyset$ |
| (1,1) | $\emptyset$ | $\emptyset$ | (1,1) | $\emptyset$ | (1,0) |
| (0,1) | $\emptyset$ | $\emptyset$ | (0,1) | $\emptyset$ | (0,0) |
| (1,0) | $\emptyset$ | (1,0) | $\emptyset$ | (0,0) | $\emptyset$ |
Definition. a semigroup of trivial charts is a subsemigroup of $K_n + 0$.
Theorem 1. subsemigroups of $K_n + 0$ are either trivial or they contain zero.
Proof. (1) in the trivial case we have the empty semigroup and the semigroups formed by any of the idempotents of $K_n + 0$. (2) if $S$ contains nilpotent charts then it must contain zero, so suppose that $S$ has no nilpotent charts and at least two non-zero elements. Then those non-trivial elements must be idempotents, but any two idempotents in $K_n + 0$ combine to produce zero, so a non-trivial subsemigroup must contain zero. $\square$
Theorem 2. let $S$ be a semigroupoid, then subsemigroupoids $Sub(S)$ are equivalent to zero-preserving subsemigroups of $Sub(S + 0)$.
Proof. (1) let $T$ be a subsemigroupoid of $S$. Then for all $a,b \in T$ either $ab \in T$ or $ab = 0$, it follows that $ab \in T + 0$. Suppose $X$ is a zero preserving subsemigroup of $S + 0$. Then $ab \in X-0$ or $ab = 0$. Let $T = X - 0$, then $T \subseteq S$ and forall $a,b$ either $ab \in T$ or $ab = 0$, so $ab$ is a subsemigroupoid of $S$. $\square$
Theorem 3. every non-empty semigroup of trivial charts is isomorphic to the semigroup with zero of a thin semigroupoid.
By theorem 1 a non-empty semigroup of trivial charts is equal to the trivial monoid with a single element. This is simply the semigroup with zero of the empty category. Then in the case that $S$ is non-trivial, by theorem one it is a zero-preserving subsemigroup of $K_n + 0$, which by theorem 2 is the semigroup with zero of a thin semigroupoid. $\square$
This allows us to create a direct correspondonce between a concept in semigroup theory and a concept in semigroupoid theory, so that thin semigroupoids can be studied by semigroups of trivial charts. Thin categories are simply a special case, and so they produce a special class of semigroups.
Proposition. a non-empty semigroup of trivial charts is the semigroup with zero of a thin category provided that every nilpotent chart absorbs two idempotents.
Proof. by theorem 3 every non-empty semigroup of trivial charts comes from a thin semigroupoid. There are two elements in a thin semigroupoid: nilpotents and idempotents corresponding to non-endofunctions and endofunctions respectively. In a thin category there are no non-identity idempotents to preserve, so all that is required is that each nilpotent morphism preserves two idempotents which are necessarily identities.
If $(a,b)$ is a morphism in a thin category, then the idempotents preserved by it are precisely the identities that it absorbs: $(a,a) \circ (a,b) = (a,b)$ and $(a,b) \circ (b,b) = (a,b)$ of which there can only be two. So if a nilpotent charts absorbs two different idempotents it preserves identities. $\square$
This is a purely semigroup theoretic characterization of thin categories. These are a very restricted class of semigroups, because concepts of semigroup theory most readily translates to semigroupoid theory rather then category theory. This correspondence forms the basis of the subject at hand.
We now need to characterize the Green's relations in the semigroup with zero of the complete thin groupoid $K_n + 0$ and prove that it is indeed in a Brandt semigroup. We have mentioned that $K_n + 0$ is a Brandt semigroup, and we can see this in the case of five elements by simple inspection, but we have not proved this result in general.
Lemma 1. let $K_n$ be a complete thin groupoid. Then the $L$ preorder on $K_n + 0$ has any ordered pair $(a,b)$ less then $0$ and any pair of ordered pairs are related if they have the same right elements. Dually, the right preorder $R$ has everything less then zero and it preserves left elements.
Proof. let $(a,b)$ be an ordered pair, then by left action $0(a,b) = 0$ so that $(a,b) \subseteq 0$. Then by left action with another ordered pair $(c,a)(a,b) = (c,b)$ two elements are left action related provided they have the same right elements. In other direction, $(a,b)0 = 0$ by right action and $(a,b)(b,c) = (a,c)$ so that ordered pairs are right action related provided they preserve the same left elements.
It follows that $K_n + 0$ has two $J$ classes: zero and all ordered pairs. It follows that $K_n + 0$ is a 0-simple semigroup. In the minimal $D$ class, $L$ and $R$ permute with one another (as is necessary in any $D$ class) and furthermore they form direct products of one another in the lattice of partitions (which is the quotient lattice of the topos of sets). Their direct product is the set of all ordered pairs. $\square$
Theorem 4. $K_n + 0$ is an H-trivial Brandt semigroup.
Proof. (1) let $a$, $b$ be idempotents in $K_n + 0$ then $a$ and $b$ can be represented as charts $(a,a)$ or $(b,b)$ so that $(a,a)(b,b) = 0$ which implies that $ab = 0$. Alternatively, $a = 0$ or $b = 0$ implies that $ab = 0$. As any two idempotents compose to zero, they commute. So that $K_n + 0$ is idempotent commutative.
(2) let $a$ be any element in $K_n = 0$. Then suppose that $a$ is equal to zero, then $a$ is idempotent which implies that it is a regular element. Suppose that $a$ is non-zero, then it is an ordered pair $(a,b)$ so it has an inverse $(b,a)$ then $(a,b)(b,a)(a,b) = (a,b)$ so that $a$ is a regular element.
(3) by lemma 1, $K_n + 0$ is 0-simple. Every trivial chart is periodic, so that every element in $K_n + 0$ is group bound. It follows that $K_n + 0$ is completely 0-simple. Every idempotent commutative regular semigroup is inverse, so by parts (1) and (2) it follows that $K_n + 0$ is an inverse semigroup. As it is a completely 0-simple inverse semigroup, it is a Brandt-semigroup. By lemma 1, the intersection of its L and R relations is trivial, so it is H-trivial. $\square$.
Proposition. $K_n + 0$ is a two-sided inverse subsemigroup ideal of the symetric inverse semigroup $PS(n)$.
Proof. $K_n + 0$ is closed under inverses, with $(a,b)^{-1} = (b,a)$ so it is an inverse subsemigroup of $PS(n)$. It is also a two-sided semigroup ideal because with respect to function composition for any $fg$ then $|fg| \leq |f|,|g|$, so function composition can only reduce the cardinality of partial transformations. It follows that composition can only make trivial charts smaller to become empty, which is included as a trivial chart. So that $K_n+0$ is a two sided semigroup ideal. $\square$
This demonstrates that the semigroup with zero of a thin category is a subsemigroup of an inverse semigroup, so among other things it is idempotent commutative. In general, every thin category embdes in a groupoid whose semigroup with zero is an inverse semigroup.
Zero divisor digraphs:
The zero divisor digraph $Z(S)$ is an important component in a number of constructions related to semigroups of trivial charts including the commuting graph $Com(S)$ and the construction of the underlying thin semigroupoid or category of the semigroup.Definition. let $S$ be a semigroup, then the zero divisor digraph $Z(S)$ is the fiber of $0$. Then $(a,b) \in Z(S) \Leftrightarrow ab = 0$.
The zero divisor graph $Z(S)$ for a semigroup of trivial charts, can be described by the composition of trivial charts.
Proposition. let $S$ be a semigroup of trivial charts then $a,b \in S$ and $(a,b) \in Z(S)$ provided that $a = 0$, $b = 0$, or $a,b \not = 0$ and $a = (a_1,a_2), b = (b_1,b_2)$ with $a_2 \not= b_1$.
With this, we can show that the commuting graph of a semigroup of trivial charts is a subgraph of the zero divisor graph. As it is symmetric, it is naturally embedded in the symmetric component of the zero divisor graph. In fact it is equal to it, as we are about to show.
Theorem 5. let $S$ be a semigroup of trivial charts, then $Com(S) \subseteq Z(S)$.
Proof. the composition any elements with zero is zero, therefore in order for two elements to not be zero divisors of one another they must both be non-zero. Let $a,b$ be non-zero then by trivial chart representation they are $(a_1,a_2)$ and $(b_1,b_2)$ then if $(a_1,a_2)(b_1,b_2) = (a_1,b_2) = (b_1,a_2) = (b_1,b_2)(a_1,a_2)$ we have that $a_1 = a_2$ and $b_1 = b_2$ which implies that $(a_1,a_2) = (b_1,b_2)$. It follows that $a = b$ so the only non-zero elements that commute are equal. $\square$
We define a semigroupoid such as a category from a semigroup of trivial charts, not from the zero divisor graph but rather from its complement: the non-zero divisor graph. The domain of a semigroup is a complete binary relation, but the domain of a semigroupoid or a category is a non-zero divisor graph of a semigroup with zero.
Definition. let $S$ be the composition function of a non-empty semigroup of trivial charts. Then the underlying thin semigroupoid of $S$ is the subobject (in the topos of functions) of $S$ is the partial semigroup with domain equal to the non-zero divisor graph of $S$.
Corollary. the partial semigroup of a thin semigroupoid is anticommutative.
We have primarily studied thin semigroupoids in terms of their semigroups of trivial charts, which naturally emerge from their completions. But in the case of thin semigroupoids they are also anticommutative, which produces a special relationship with rectangular bands.
Theorem 6. let $\circ : R \to M$ with $R \subseteq M^2$ be a thin semigroupoid with object set $O$. Then $\circ$ is a subobject in the topos of functions of the composition function of a rectangular band.
Proof. the composition function of a thin semigoupoid has $(a,b)(c,d) = (a,d)$ when $b = c$. The composition function in a rectangular band has $(a,b)(c,d) = (a,d)$ no matter what. Let $O^2$ be the rectangular band of ordered pairs on $O$, this leads to a function $\cdot : (O^2)^2 \to O^2$. Then we can embed $\circ$ in $\cdot$ by an ordered pair of inclusion monomorphisms $(R \hookrightarrow (O^2)^2, M \hookrightarrow M)$. $\square$
This is of course a different kind of embedding of the composition function of a semigroup or category into a semigroup then we are used to, but this demonstrates a special relationship that exists between rectangular bands and thin categories. This is a consequence of the fact that thin categories are anticommutative.
Theorem 7. let $S$ be a semigroup of trivial charts and $a,b \in S$. If $ab \not= 0$ and $ba \not= 0$ then $a$ and $b$ are non-zero nilpotents and inverses of one another.
Proof. suppose that $a$ or $b$ are idempotent. Then $ab = 0$ and $ba = 0$ because idempotents always compose to zero. So that means $a$ and $b$ must both be non-idempotents and therefore non-zero nilpotent. Let $(a,b)$ and $(c,d)$ be their values then if they are composable then $b = c$ and $a = d$ which means that $(c,d) = (b,a)$ so that they are equal to $(a,b)$ and $(b,a)$ which are inverses of one another. $\square$
With this, we can get an important property of the zero divisors graphs of thin skeletal categories and semigroupoids arising from posets and strict orders.
Theorem 8. let $S$ be an antisymemtric thin semigroupoid. Then the zero divisor digraph of $S$ is total.
Proof. by theorem 7 in order for two elements to not compose to zero with one another they must be inverses of one another. An antisymmetric thin semigroupoid is inverse-free, so that for each $a,b \in S$ we have $ab = 0$ or $ba = 0$ which implies that the zero divisor digraph is total.
In particular, the semigroups with zero of thin categories always have at least one pair of elements compose to zero. Then same is true for the semigroups of trivial charts of strict orders.
Theorem 9. let $S$ be a commutative semigroup of trivial charts. Then $S$ is a maximum chain length two partially ordered commutative J-trivial semigroup, and all such commutative semigroups emerge in this way.
Proof. by the fact that the commuting graph of a semigroup of trivial charts is the symmetric component of the zero divisor graph, if $S$ is commutative this means that $ab = 0$ and $ba = 0$ for all $a,b$ with $a \not= b$. It follows that $S$ is a maximum chain length two J-trivial semigroup, with maximum chains equal to elements together with zero. In the other direction, every height two J-trivial commutative semigroup is classified by its set of idempontents and nilpotents. Idempotents can be represented by permutation charts and nilpotents by nilpotent charts, to get a trivial chart representation of the commutative semigroup. $\square$
Let $S$ be a semigroup with automorphism group $Aut(S)$ and suppose that $p \in Aut(S)$. Then if $ab = ba$ we have $p(ab) = p(ba)$ which implies that $p(a)p(b) = p(b)p(a)$ so that if $(a,b) \in Com(G)$ then $(p(a),p(b)) \in Com(G))$ so that automorphisms of a semigroup are automorphisms of its commuting graph.
Lemma. let $K_n + 0$ be a complete Brandt semigroup of trivial charts. Then let $f \in S_n$ be a permutation on the underlying set $n$. Then define $f' : K_n + 0 \to K_n + 0$ with $f'(0) = 0$ and $f'((a,b) = (f(a),f(b))$ then $f'$ is an automorphism.
Proof. let $ab \in K_n + 0$. Then suppose that $a = 0$ then $ab = 0$ and $f'(ab) = 0f'(b) = f'(0) = 0$ or if $b = 0$ then $f'(ab) = f'(a)0 = f'(0) = 0$. Suppose that $a \not = 0$ and $b \not= 0$ then \[ f'((a_1,a_2)(b_1,b_2)) = f'((a_1,b_2)) = (f(a_1),f(b_2)) \] \[ f'(a_1,a_2)f'(b_1,b_2)) = (f(a_1),f(a_2))(f(b_1),f(b_2)) = (f(a_1),f(b_2)) \] Then $f'((a_1,a_2)(b_1,b_2)) = (f(a_1),f(b_2)) = f'((a_1,a_2))f'((b_1,b_2))$. In the special case in which $a_2 \not = b_1$ then this implies that $f(a_2) \not= f(b_1)$ because $f$ reflects equality since its a permutation. So $f'$ preserves zeros. It follows that $f'$ is a semigroup automorphism.
Corollary. the Brand semigroup $K_n + 0$ has an automorphism group with there orbits: zero, non-zero idempotents, and non-zero nilpotents
We can use this result as an organizing principle in the theory of the centralizers of $K_n + 0$. By this result, we know that the centralizers belong into three classes. In the following theorem we will characterize all of them.
Theorem 10. let $K_n + 0$ be the complete semigroup of trivial charts, then the centralizers of $K_n + 0$ come in three forms:
- The entire semigroup $K_n + 0$
- $K_{n-1} + 0$ plus a side idempotent which has $(n-1)^2 + 1$ elements
- A special case which has $(n-1)^2$ elements and a side nilpotent.
(2) let $a$ be an idempotent non-zero element. Then it is equal to an element $(a,a)$ and so its centralizer is all elements disjoint from $(a,a)$ so besides $(a,a)$ it consits of the $D$ class of all $(x_1,x_2)$ with $x_1 \not = a$ and $x_2 \not = a$. The commuting graph is a subgraph of the zero divisor graph, so $ac = 0$ for any $c \in C(a)$ which implies that $a$ is a side idempotent.
(3) let $a$ be a non-zero nilpotent, then as before for any $c \in C(a)$ we have $ac = 0$ and $ca = 0$ so that $a$ is a side nilpotent element. Then let $(x_1,x_2)$ be the chart of $a$. Any idempotent element has the form $(y_1,y_2)$ with $x_2 \not= y_1$ and $x_1 \not= y_2$. These come in three forms $x_1 = y_1$, $x_2 = y_2$ and $x_1 \not= y_1$ and $x_2 \not= y_2$.
Those with $x_1 \not= y_1$ and $x_2 \not= y_2$ form a single D class with $L$ and $R$ classified by their components. Then those with $x_1 = y_1$ form a R-total D class and those with $x_2 = y_2$ form an L-total D class. Together, these constitute a complement set of J classes of $K_n + 0$. This results in a subsemigroup whose J class ordering has the form $[\{[1,\{1,1\}],1\},1]$. $\square$
The commuting graph of the Brandt semigroup on five elements is the cricket graph. In general, by theorem 10 we have that any commuting graph of a complete Brandt semigroup of trivial charts is a nearly-regular graph (in the sense that degrees can only differ by at most one) with a zero element adjoined.
Special cases:
We have defined semigroups of trivial charts by their embeddings in the partial inverse semigroup $PS(n)$ and its intermediary ideal $K_n + 0$, but we have not created a theory of recognising which semigroups of trivial charts without embeddings. We will now do that.Theorem 11. let $S$ be a non-empty subsemigroup of $K_n+0$. Then $S$ has the following properties
- $S$ is idempotent commutative, with a max height two semilattice of idempotents, and the idempotent action poset is 0-trivial, in the sense that non-zero elements form an antichain.
- $S$ is group-free
- $S$ is a semigroup with zero
- The commuting graph of $S$ is a subgraph of its zero divisor graph
- $S$ is max order two aperiodic.
- Only elements that are inverses of one another are non-zero dividing as pairs
(2) By theorem 4 $K_n + 0$ is H-trivial which by Green's theorem means it is group-free. So its subsemigroups are group-free as well.
(3) By theorem 1, $S$ is a semigroup with zero.
(4) By theorem 5, $Com(S) \subseteq Z(S)$ so that the only elements that commute are ones that both compose to zero.
(5) The charts in $K_n+0$ take two forms: they are idempotent or they are non-zero nilpotent. A non-zero nilpotent $(a,b)$ composed with itself is zero, so every non-zero nilpotent has index two. So $S$ is max index two as an aperiodic semigroup.
(6) By theorem 7, only inverses can be non-zero dividing as pairs. $\square$
The morphism preordering of a thin category $C$ is antisymmetric. This is translated into semigroup theoretic terms by the statement that $C+0$ is a J-trivial semigroup. This is encoded in the following theorem.
Theorem 12. a non-empty semigroup of trivial charts is J-trivial iff it comes from an antisymmetric thin semigroupoid.
Proof. (1) if $S$ is a thin semigroupoid with symmetric pair $(a,b)$ and $(b,a)$ then $(b,a)(a,a)(a,b) = (b,b)$ and $(a,b)(b,b)(b,a) = (a,a)$ so that $a$ and $b$ are in the same $J$ class. So if its semigroup $S + 0$ is J-trivial it must be antisymmetric.
(2) if it is antisymmetric then for $(a,b) \subseteq (c,d)$ then $c \subseteq a$ and $b \subseteq d$ and $(c,d) \subseteq (a,b)$ means $a \subseteq c$ and $d \subseteq b$. By antisymmetry if $a \subseteq b$ and $b \subseteq a$ then $a = b$ and if $c \subseteq d$ and $d \subseteq c$ then $c = d$ so that $(a,b) = (c,d)$ which implies that $S + 0$ is J-trivial. $\square$
Theorem 13. $S$ is a nilpotent semigroup iff it comes from a strict order.
Proof. every non-zero idempotent is of the form $(a,a)$. It follows that if $S$ is nilpotent, it must avoid every element of the form $(a,a)$ which means it is irreflexive. If $(a,b)$ and $(b,a)$ are in $S$ then $(a,b)(b,a) = (a,a)$ and $(b,a)(a,b) = (b,b)$ so that $(a,a)$ and $(b,b)$ are in $S$ it follows that irreflexive transitive are antisymmetric, in which case they are called strict orders. So only strict orders have nilpotent semigroups, and strict orders are nilpotent because they are irreflexive. $\square$
In theorem 9, we characterized from a semigroup perspective the commutative semigroups of charts. In the other direction, we can characterize the thin semigroupoids with commutative semigroup completions.
Theorem 14. let $S$ be a thin semigroupoid, then $S+0$ is commutative iff $S$ is a loop isolated maximum chain length two antisymmetric thin semigroupoid.
Proof. there are cases whereby two morphisms can be composable (1) if we have a loop and a non-loop edge $(a,a)(a,b)$ or $(a,b)(b,b)$ so to forbid this $S$ must be loop isolated (2) if we have two edges in a symmetric pair $(a,b)(b,a)$ which must be forbidden so that $S$ is antisymmetric (3) we have a chain of length three $(a,b)(b,c)$ which means that $S$ must be maximum chain length two. $\square$
Corollary. let $S$ be a thin semigroupoid, then $S+0$ is a null semigroup iff $S$ is a maximum chain length two strict order.
Proof. (1) by theorem 9 $S$ must have maximum chain length to be commutative and by theorem 13 it must be nilpotent, so to be a commutative nilpotent semigroup like a null semigroup it must be a maximu mchain length two strict order (2) by theorem 14 the fact that $S+0$ is commutative implies that $S$ is a maximum chain length two antisymmetric thin semigroupoid, and by theorem 13 we know it is irreflexive. So by combining the two $S$ is a maximum chain length two strict order. $\square$
Semilattices are an important special case in semigroup theory. By theorem 9, we know that every such semilattice is a maximum chain length two semilattice. So every semilattice associated to a thin category is isomorphic, it follows that in order to classify the thin semigroupoids associated with semilattices we need a class of semigroupoids classified by their cardinalities. These are precisely the discrete categories.
Theorem 15. let $S$ be a thin semigroupoid, then $S+0$ is a semilattice if $S$ is a discrete category.
Proof. if $S+0$ is a semilattice then every element of $S$ is an idempotent, which means it is a loop. It follows that $S$ is coreflexive, so that every element is a loop. The only thin semigroupoids that are coreflexive are the discrete categories, so $S$ is a discrete category. Then if $S+0$ is a semilattice, then every element of $S$ must still be idempotent, so that it must be a discrete category. $\square$
We started this discussion by considering the symmetric inverse semigroup $PS_n$ whose elements consist of charts on at most $n$ elements. These charts all have permutation and nilpotent parts, and they can be represented as sets of ordered pairs. If they have at most one ordered pair, they are trivial. So inverse semigroups have played an important role in this entire theory.
We return to the question of inverse semigroups. It remains to characterize which semigroups of trivial charts are indeed inverse semigroups. These are then inverse subsemigroups of the symmetric inverse semigroup $PS_n$. This is a fundamental relationship between groupoids and inverse semigroups.
Theorem 16. let $G$ be a thin groupoid, then $G+0$ is an inverse semigroup. Every inverse semigroup with zero of trivial charts emerges in this way.
Proof. let $(x,y)$ be an element of the thin groupoid, then $(y,x) \in G$ so that $(x,y)(y,x)(x,y) = (x,y)$. It follows that $G+0$ is a regular semigroup, and by theorem 11 it is idempotent commutative so it is an inverse semigroup. Then let $S+0$ be a semigroup with zero then every element $(x,y)$ has an inverse $(y,x)$ so that the underlying semigroupoid $S$ is a groupoid. $\square$
The semigroups of trivial charts are part of the basic relationship between category theory and semigroup theory, because the semigroup completion of any thin category is a semigroup of trivial charts. Further, if we generalize to the semigroup completion of any arbitrary category $C$, then hom class equivalence forms a congruence on $C+0$ whose quotient is a semigroup of trivial charts.
It follows that the theory of semigroups of trivial charts, like those dealt with in this post are part of the basic semigroup theory of categories. Properties of the semigroup completions of categories can be inferred from their quotient semigroups of trivial charts. This suggests a new direction to take the semigroup theory of categories in.
No comments:
Post a Comment