In mathematics, a compact semigroup is a
semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively (just notation, not necessarily th ...
in which the sets of solutions to equations can be described by finite sets of equations. The term "compact" here does not refer to any
topology
Topology (from the Greek language, Greek words , and ) is the branch of mathematics concerned with the properties of a Mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformat ...
on the semigroup.
Let ''S'' be a semigroup and ''X'' a finite set of letters. A system of equations is a subset ''E'' of the
Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is
A\times B = \.
A table c ...
''X''
∗ × ''X''
∗ of the
free monoid
In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ...
(finite strings) over ''X'' with itself. The system ''E'' is satisfiable in ''S'' if there is a map ''f'' from ''X'' to ''S'', which extends to a
semigroup morphism ''f'' from ''X''
+ to ''S'', such that for all (''u'',''v'') in ''E'' we have ''f''(''u'') = ''f''(''v'') in ''S''. Such an ''f'' is a ''solution'', or ''satisfying assignment'', for the system ''E''.
[Lothaire (2011) p. 444]
Two systems of equations are ''equivalent'' if they have the same set of satisfying assignments. A system of equations if ''independent'' if it is not equivalent to a proper subset of itself.
[ A semigroup is ''compact'' if every independent system of equations is finite.][Lothaire (2011) p. 458]
Examples
* A free monoid on a finite alphabet is compact.[Lothaire (2011) p. 447]
* A free monoid on a countable alphabet is compact.[Lothaire (2011) p. 461]
* A finitely generated free group
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''− ...
is compact.[Lothaire (2011) p. 462]
* A trace monoid
In computer science, a trace is an equivalence class of strings, wherein certain letters in the string are allowed to commute, but others are not. Traces generalize the concept of strings by relaxing the requirement for all the letters to have a d ...
on a finite set of generators is compact.[
* The ]bicyclic monoid
A bicyclic molecule () is a molecule that features two joined rings. Bicyclic structures occur widely, for example in many biologically important molecules like α-thujene and camphor. A bicyclic compound can be carbocyclic (all of the ring ...
is not compact.[Lothaire (2011) p. 459]
Properties
* The class of compact semigroups is closed under taking subsemigroups and finite direct products.[Lothaire (2011) p. 460]
* The class of compact semigroups is not closed under taking morphic images or infinite direct products.[
]
Varieties
The class of compact semigroups does not form an equational variety. However, a variety of monoids has the property that all its members are compact if and only if all finitely generated members satisfy the maximal condition on congruences
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively (just notation, not necessarily ...
(any family of congruences, ordered by inclusion, has a maximal element).[Lothaire (2011) p. 466]
References
* {{cite book , last=Lothaire , first=M. , authorlink=M. Lothaire , title=Algebraic combinatorics on words , others=With preface by Jean Berstel and Dominique Perrin , edition=Reprint of the 2002 hardback , series=Encyclopedia of Mathematics and Its Applications , volume=90, publisher=Cambridge University Press , year=2011 , isbn=978-0-521-18071-9 , zbl=1221.68183
Semigroup theory
Formal languages
Combinatorics on words