Terminology for “Eightfold Way” of Associative, Commutative, and Idempotent Algebraic Objects

abstract-algebracombinatoricsdiscrete mathematicsgraph theoryuniversal-algebra

Idea

There are associative, commutative, and idempotent algebraic structures. This gives eight categories, an "eight-fold way". What is the ideal terminology for such a categorization as it relates to discrete mathematics, graph theory, and theoretical computer science? More formally:

Introduction To Question

Definition of $\mathtt{ACI}$ algebras $\mathcal{A}_{ijk}$ for ${i,j,k} \in \{0,1\}$.

An $\mathcal{A}_{ijk}$-algebra is an algebra $\langle M, \circ\rangle$ with one binary operation in which the following identities hold:

  • the associative identity $(x \circ y) \circ z = x \circ (y \circ z)$ if $i = 1$,
  • the commutative identity $x \circ y = y \circ x$ if $j = 1$,
  • and the idempotent identity $x \circ x = x$ if $k = 1$.

This defines $2^3 = 8$ sorts of algebras, so that (for example) a $\mathcal{A}_{110}$ is a commutative semigroup, a $\mathcal{A}_{010}$ a commutative magma, and $\mathcal{A}_{000}$ is simply a magma i.e. a set decorated with a binary operation.

Let $\mathsf{W}_{ijk}(M)$ be the free $\mathcal{A}_{ijk}$-algebra over the finite set $M$.

Question:
What is the appropriate terminology in this situation? There are three issues at hand. First, names for the $\mathcal{A}_{ijk}$, names for the $\mathsf{W}_{ijk}(M)$, and names for the elements $x \in \mathsf{W}_{ijk}(M)$. Many of these "gadgets" have common names, many do not. Some perhaps don't deserve well-known names. But it is unclear which do and which do not presently have them.

For example, one could adopt the follow definitions:

  1. $\mathcal{FullBinaryTreesOver}(M)$ = $\mathsf{W}_{000}(M)$

  2. $\mathcal{Z}(M)$ = $\mathsf{W}_{001}(M)$

  3. $\mathcal{Y}(M)$ = $\mathsf{W}_{010}(M)$

  4. $\mathcal{X}(M)$ = $\mathsf{W}_{011}(M)$

  5. $\mathcal{Sequences}(M)$ = $\mathsf{W}_{100}(M)$

  6. $\mathcal{NonRepeatingSequences}(M)$ = $\mathsf{W}_{101}(M)$ [Edit: misleading, see Andreas Blass' comment below]

  7. $\mathcal{MultisetsOn}(M)$ = $\mathsf{W}_{110}(M)$

  8. $\mathcal{SubsetsOf}(M)$ = $\mathsf{W}_{111}(M)$

and speak of these algebraic objects and their elements similarly. However, the ideal terminology seems unclear. In the first four cases, the language of graph theory appears to be more appropriate. In the last four cases, the language of set theory seems to work better. Is there a coherent way to approach this seemingly simple question?

In pure mathematics, this question of terminology appears to be relevant to the subareas of discrete math, universal algebra, category theory, combinatorial species, and combinatorics. I think(?) the $\mathsf{W}_{ijk}(M)$ each suggest associated combinatorial species [https://en.wikipedia.org/wiki/Combinatorial_species].

In computer science, to the areas of type theory and abstract data types. And in software engineering where there is a bewildering array of overlapping but inconsistent labels such "arrays", "tuples", "lists", "sorted lists", "ordered sets", "(unordered) sets", "bags", and "trees" of various kinds. These terms are applied in different fashions to different programming languages such as C#, Java, Python, and JavaScript. It shouldn't be "that hard" to formulate a coherent terminology for "all this".

Edit

  • In particular, I am not aware of a common name for $\mathsf{W}_{000}(\{\bullet\})$. I think $\mathbb{B}$ (for 'binary') would work, in analogy with $\mathbb{N}$. Also, if anything deserves a pithy name, certainly elements $x \in \mathsf{W}_{000}(\{\bullet\})$ do. "Full unlabelled binary trees"? But that evokes graph theory rather than algebra.

  • I am not conversant with Universal Algebra but I couldn't find I way to frame the question without it. Universal algebra appears to be a good language for framing the question, but I feel that the terminology issues here reach further than the topic of universal algebra and could be accessible to those who know little about it.

  • I mirrored the style of definition the $\mathtt{ACI}$ algebras $\mathcal{A}_{ijk}$ after the style of A Course In Universal Algebra by Burris and Sankappanavar (2012 Update)

  • I tried to avoid subscripts as much as possible. Good terminology would make avoiding them easier. The subscripts of the $\mathcal{A}_{ijk}$ are ordered by a convention that intuitively match how often associative, commutative, and idempotent binary operation occur in common practice.

  • Clearly the present naming convention for item 6 is misleading given the comment by Andreas Blass below.

  • I am a software engineer by trade, and a 'loose' form of this question has been lingering on my mind for quite some time.

  • Even phrasing this question in a substantive and correct way took a great deal of work, even with my background in mathematics. It's "been a while" but it was fun.

Best Answer

I would not encourage you to introduce a new terminology, for two reasons. First, it would increase the confusion between existing terminologies (see below). Secondly, it could make it difficult to find relevant information.

There is a large litterature on Semigroups. The free semigroup on a set $A$ is denoted by $A^+$.

Idempotent semigroups have been studied for a long time and bands is another well established terminology for them. In particular, it is known that every finitely generated free idempotent semigroup is finite (a nontrivial fact, as emphasized by Andreas Blass' example, see [3] for an efficient algorithm). Moreover, a complete classification of the varieties of idempotent semigroups is available [1].

Commutative semigroups are also well studied, [2] is an excellent reference. Idempotent and commutative semigroups are also known as semilattices. The free commutative semigroup on a set $X$ is denoted by $F_X$ in [2], but this is a context-depending notation: $F_X$ or $F(X)$ could be used for the free object on $X$ for any algebra.

Magmas are sometimes called groupoids. See your own question for a notation of the corresponding free algebra. Idempotent magma is a very natural name: it is used for instance in two answers to this question. Commutative magmas have their own wikipedia entry (rock, paper, scissors being the emblematic example). Commutative and idempotent magmas are used in this thesis.

[1] J. A. Gerhard, (1970), The lattice of equational classes of idempotent semigroups", Journal of Algebra, 15 (2): 195–224

[2] P. A. Grillet, (2001), Commutative Semigroups, Springer Verlag, ISBN 978-0-7923-7067-3

[3] J. Radoszewski, W. Rytter, Efficient Testing of Equivalence of Words in a Free Idempotent Semigroup. SOFSEM 2010: Theory and Practice of Computer Science. SOFSEM LNCS 5901, Springer (2010) 663-671.

Related Question