Variety of finite semigroups

Last updated January 19, 2022

In mathematics, and more precisely in semigroup theory, a variety of finite semigroups is a class of semigroups having some nice algebraic properties. Those classes can be defined in two distinct ways, using either algebraic notions or topological notions. Varieties of finite monoids, varieties of finite ordered semigroups and varieties of finite ordered monoids are defined similarly.

Definition

Two equivalent definitions are now given.

Algebraic definition

A variety V of finite (ordered) semigroups is a class of finite (ordered) semigroups that:

is closed under division.
is closed under taking finite Cartesian products.

The first condition is equivalent to stating that V is closed under taking subsemigroups and under taking quotients. The second property implies that the empty product—that is, the trivial semigroup of one element—belongs to each variety. Hence a variety is necessarily non-empty.

A variety of finite (ordered) monoids is a variety of finite (ordered) semigroups whose elements are monoids. That is, it is a class of (ordered) monoids satisfying the two conditions stated above.

Topological definition

In order to give the topological definition of a variety of finite semigroups, some other definitions related to profinite words are needed.

Let A be an arbitrary finite alphabet. Let A⁺ be its free semigroup. Then let ${\hat {A}}$ be the set of profinite words over A. Given a semigroup morphism $\phi :A^{+}\to S$ , let ${\hat {\phi }}:{\hat {A}}\to S$ be the unique continuous extension of $\phi$ to ${\hat {A}}$ .

A profinite identity is a pair u and v of profinite words. A semigroup S is said to satisfy the profinite identity u = v if, for each semigroup morphism $\phi :A^{+}\to S$ , the equality ${\hat {\phi }}(u)={\hat {\phi }}(v)$ holds.

A variety of finite semigroups is the class of finite semigroups satisfying a set of profinite identities P.

A variety of finite monoids is defined like a variety of finite semigroups, with the difference that one should consider monoid morphisms $\phi :A^{*}\to M$ instead of semigroup morphisms $\phi :A^{+}\to M$ .

A variety of finite ordered semigroups/monoids is also given by a similar definition, with the difference that one should consider morphisms of ordered semigroups/monoids.

Examples

A few examples of classes of semigroups are given. The first examples uses finite identities—that is, profinite identities whose two words are finite words. The next example uses profinite identities. The last one is an example of a class that is not a variety.

More examples are given in the article Special classes of semigroups.

Using finite identities

The most trivial example is the variety S of all finite semigroups. This variety is defined by the empty set of profinite equalities. It is trivial to see that this class of finite semigroups is closed under subsemigroups, finite products, and quotients.
The second most trivial example is the variety 1 containing only the trivial semigroup. This variety is defined by the set of profinite equalities {x = y}. Intuitively, this equality states that all elements of the semigroup are equal. This class is trivially closed under subsemigroups, finite products, and quotients.
The variety Com of commutative finite semigroups is defined by the profinite equality xy = yx. Intuitively, this equality states that each pair of elements of the semigroup commutes.
The variety of idempotent finite semigroups is defined by the profinite equality xx = x.

More generally, given a profinite word u and a letter x, the profinite equality ux = xu states that the set of possible images of u contains only elements of the centralizer. Similarly, ux = x states that the set of possible images of u contains only left identities. Finally ux = u states that the set of possible images of u is composed of left zeros.

Using profinite identities

Examples using profinite words that are not finite are now given.

Given a profinite word, x, let $x^{\omega }$ denote $\lim _{n\to \infty }x^{n!}$ . Hence, given a semigroup morphism $\phi :A^{+}\to S$ , ${\hat {\phi }}(x^{\omega })$ is the only idempotent power of $\phi (x)$ . Thus, in profinite equalities, $x^{\omega }$ represents an arbitrary idempotent.

The class G of finite groups is a variety of finite semigroups. Note that a finite group can be defined as a finite semigroup, with a unique idempotent, which in addition is a left and right identity. Once those two properties are translated in terms of profinite equality, one can see that the variety G is defined by the set of profinite equalities $\{x^{\omega }=y^{\omega }{\text{ and }}x^{\omega }y=yx^{\omega }=y\}.$

Classes that are not varieties

Note that the class of finite monoids is not a variety of finite semigroups. Indeed, this class is not closed under subsemigroups. To see this, take any finite semigroup S that is not a monoid. It is a subsemigroup of the monoid S¹ formed by adjoining an identity element.

Reiterman's theorem

Reiterman's theorem states that the two definitions above are equivalent. A scheme of the proof is now given.

Given a variety V of semigroups as in the algebraic definition, one can choose the set P of profinite identities to be the set of profinite identities satisfied by every semigroup of V.

Reciprocally, given a profinite identity u = v, one can remark that the class of semigroups satisfying this profinite identity is closed under subsemigroups, quotients, and finite products. Thus this class is a variety of finite semigroups. Furthermore, varieties are closed under arbitrary intersection, thus, given an arbitrary set P of profinite identities uⁱ = vⁱ, the class of semigroups satisfying P is the intersection of the class of semigroups satisfying all of those profinite identities. That is, it is an intersection of varieties of finite semigroups, and this a variety of finite semigroups.

Comparison with the notion of variety of universal algebra

The definition of a variety of finite semigroups is inspired by the notion of a variety of universal algebras. We recall the definition of a variety in universal algebra. Such a variety is, equivalently:

a class of structures, closed under homomorphic images, subalgebras and (direct) products.
a class of structures satisfying a set of identities.

The main differences between the two notions of variety are now given. In this section "variety of (arbitrary) semigroups" means "the class of semigroups as a variety of universal algebra over the vocabulary of one binary operator". It follows from the definitions of those two kind of varieties that, for any variety V of (arbitrary) semigroups, the class of finite semigroups of V is a variety of finite semigroups.

We first give an example of a variety of finite semigroups that is not similar to any subvariety of the variety of (arbitrary) semigroups. We then give the difference between the two definition using identities. Finally, we give the difference between the algebraic definitions.

As shown above, the class of finite groups is a variety of finite semigroups. However, the class of groups is not a subvariety of the variety of (arbitrary) semigroups. Indeed, $\langle \mathbb {Z} ,+\rangle$ is a monoid that is an infinite group. However, its submonoid $\langle \mathbb {N} ,+\rangle$ is not a group. Since the class of (arbitrary) groups contains a semigroup and does not contain one of its subsemigroups, it is not a variety. The main difference between the finite case and the infinite case, when groups are considered, is that a submonoid of a finite group is a finite group. While infinite groups are not closed under taking submonoids.

The class of finite groups is a variety of finite semigroups, while it is not a subvariety of the variety of (arbitrary) semigroups. Thus, Reiterman's theorem shows that this class can be defined using profinite identities. And Birkhoff's HSP theorem shows that this class can not be defined using identities (of finite words). This illustrates why the definition of a variety of finite semigroups uses the notion of profinite words and not the notion of identities.

We now consider the algebraic definitions of varieties. Requiring that varieties are closed under arbitrary direct products implies that a variety is either trivial or contains infinite structures. In order to restrict varieties to contain only finite structures, the definition of variety of finite semigroups uses the notion of finite product instead of notion of arbitrary direct product.

Related Research Articles

In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element.

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation.

In mathematics, in particular abstract algebra, a graded ring is a ring such that the underlying additive group is a direct sum of abelian groups $such that . The index set is usually the set of nonnegative integers or the set of integers, but can be any monoid. The direct sum decomposition is usually referred to as gradation or grading .$

Ring theory is the branch of mathematics in which rings are studied: that is, structures supporting both an addition and a multiplication operation. This is a glossary of some terms of the subject.

In mathematics, a Lie algebroid is a vector bundle $together with a Lie bracket on its space of sections and a vector bundle morphism, satisfying a Leibniz rule. A Lie algebroid can thus be thought of as a "many-object generalisation" of a Lie algebra.$

In mathematics, the support of a real-valued function $is the subset of the domain containing the elements which are not mapped to zero. If the domain of is a topological space, the support of is instead defined as the smallest closed set containing all points not mapped to zero. This concept is used very widely in mathematical analysis.$

In mathematics, a join-semilattice is a partially ordered set that has a join for any nonempty finite subset. Dually, a meet-semilattice is a partially ordered set which has a meet for any nonempty finite subset. Every join-semilattice is a meet-semilattice in the inverse order and vice versa.

In universal algebra, a variety of algebras or equational class is the class of all algebraic structures of a given signature satisfying a given set of identities. For example, the groups form a variety of algebras, as do the abelian groups, the rings, the monoids etc. According to Birkhoff's theorem, a class of algebraic structures of the same signature is a variety if and only if it is closed under the taking of homomorphic images, subalgebras and (direct) products. In the context of category theory, a variety of algebras, together with its homomorphisms, forms a category; these are usually called finitary algebraic categories.

In abstract algebra, a branch of mathematics, the algebraic structure group with operators or Ω-group can be viewed as a group with a set Ω that operates on the elements of the group in a special way.

In algebraic geometry, a morphism of schemes generalizes a morphism of algebraic varieties just as a scheme generalizes an algebraic variety. It is, by definition, a morphism in the category of schemes.

In mathematics, a hereditary property is a property of an object that is inherited by all of its subobjects, where the meaning of subobject depends on the context. These properties are particularly considered in topology and graph theory, but also in set theory.

In algebra, a transformation semigroup is a collection of transformations that is closed under function composition. If it includes the identity function, it is a monoid, called a transformationmonoid. This is the semigroup analogue of a permutation group.

In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, considered as unary operator, exhibits certain fundamental properties of the operation of taking the inverse in a group: uniqueness, double application "cancelling itself out", and the same interaction law with the binary operation as in the case of the group inverse. It is thus not a surprise that any group is a semigroup with involution. However, there are significant natural examples of semigroups with involution that are not groups.

In mathematics, a null semigroup is a semigroup with an absorbing element, called zero, in which the product of any two elements is zero. If every element of a semigroup is a left zero then the semigroup is called a left zero semigroup; a right zero semigroup is defined analogously. According to Clifford and Preston, "In spite of their triviality, these semigroups arise naturally in a number of investigations."

In abstract algebra, an epigroup is a semigroup in which every element has a power that belongs to a subgroup. Formally, for all x in a semigroup S, there exists a positive integer n and a subgroup G of S such that xⁿ belongs to G.

In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some morphism to a finite monoid. Recognizable sets are useful in automata theory, formal languages and algebra.

In computer science, more precisely in automata theory, a rational set of a monoid is an element of the minimal class of subsets of this monoid that contains all finite subsets and is closed under union, product and Kleene star. Rational sets are useful in automata theory, formal languages and algebra.

In Category theory and related fields of mathematics, an envelope is a construction that generalizes the operations of "exterior completion", like completion of a locally convex space, or Stone–Čech compactification of a topological space. A dual construction is called refinement.

In mathematics, more precisely in formal language theory, the profinite words are a generalization of the notion of finite words into a complete topological space. This notion allows the use of topology to study languages and finite semigroups. For example, profinite words are used to give an alternative characterization of the algebraic notion of a variety of finite semigroups.

In mathematics, and more precisely in semigroup theory, a nilsemigroup or nilpotent semigroup is a semigroup whose every element is nilpotent.

References

Pin, Jean-Éric (2016-11-30). Mathematical Foundations of Automata Theory (PDF). pp. 141–160.
Pin, Jean-Éric (1986). Varieties of formal language. New York: Plenum Publishing Corp.
Eilenberg, S (1976). Automata, languages, and machines. New york: Harcourt Brace Jovanovich Publishers. pp. chapters "Depth decomposition theorem” and “Complexity of semigroups and morphisms”.
Almeida, J (1994). Finite semigroups and universal algebra. Rivere Edge, NJ: World Scientific Publishing Co. Inc.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.