Submonoid

In the vast landscape of abstract algebra, structures like groups and rings often take center stage. Yet, nestled within these familiar concepts lies a more general and equally fundamental idea: the monoid. A monoid is a set equipped with an associative operation and an identity element—a simple framework that captures everything from integer addition to the concatenation of words. This article delves deeper, exploring the concept of the ​​submonoid​​: a self-contained world existing within a larger monoid. We will uncover the simple rules that govern these structures and see how they provide a powerful lens for understanding complex systems.

The article is divided into two main parts. First, in "Principles and Mechanisms," we will define a submonoid through its two essential properties—closure and identity—and explore related concepts like the group of units and the fascinating role of idempotent elements as local identities. Following this, "Applications and Interdisciplinary Connections" will demonstrate how this abstract concept is not merely a mathematical curiosity but a foundational blueprint appearing in computer science, number theory, and even the study of geometric space, revealing the hidden algebraic skeleton of the world around us.

Imagine you're exploring a vast, bustling city—the world of mathematics. This city has its own set of laws, its own ways of combining things. A ​​monoid​​ is like a district in this city with a specific kind of traffic rule: you can always combine any two things (like adding numbers, or multiplying matrices, or concatenating words), this combination is associative (it doesn't matter how you group them, $(a \cdot b) \cdot c$ is the same as $a \cdot (b \cdot c)$), and there's a special "do-nothing" element, the ​​identity​​. Multiplying by 1, adding 0, or attaching an empty word are all examples of this identity action.

Now, a ​​submonoid​​ is like finding a special club or neighborhood within this district that follows the same rules but is a smaller, self-contained world. What does it take to be a proper, self-contained club? It turns out there are just two golden rules.

To form a submonoid, a subset must be a universe unto itself. It cannot rely on outsiders. This translates into two simple but powerful conditions.

First, the club must be ​​closed​​. If you take any two members and apply the district's operation, the result must also be a member of the club. You can't combine two insiders and end up with an outsider. This property is called ​​closure​​.

Consider the set of all $n \times n$ matrices with integer entries, a monoid under matrix multiplication. Let's look at the subset of ​​upper triangular matrices​​, where all entries below the main diagonal are zero. If you multiply two such matrices, you will find that the result is always another upper triangular matrix. It’s a closed club! The identity matrix, with ones on the diagonal and zeros everywhere else, is also upper triangular. Since it's closed and contains the identity, the set of upper triangular integer matrices is a bona fide submonoid.

But closure isn't everything. Let's look at the set of palindromes—words that read the same forwards and backwards, like "level" or "racecar". Let's say our alphabet has the letters 'a' and 'b'. The single-letter words "a" and "b" are both palindromes. But if we concatenate them, we get "ab". Is "ab" a palindrome? Its reverse is "ba", so, no. The set of palindromes is not closed under concatenation! It fails the first rule, so it cannot be a submonoid (unless our alphabet is so restrictive that this problem can't happen, for instance, if it only has one letter!).

The second rule is that the club must contain the leader of the whole district. The ​​identity element​​ of the parent monoid must be an element of the subset.

Let's think about the integers under multiplication. The identity element is 1. Now consider the subset of all even integers. Is this club closed? Let's see: an even number times an even number is always an even number. For instance, $2 \times 6 = 12$. So, it’s closed. A structure that is closed but might be missing the identity is called a ​​subsemigroup​​. But is it a submonoid? Does it contain the multiplicative identity, 1? No, 1 is an odd number. The club of even integers is closed, but it doesn't contain the overall leader. Therefore, it's a subsemigroup, but not a submonoid. The same thing happens with the set of matrices whose determinant is 0. The product of two such matrices also has a determinant of 0, so the set is closed. But the identity matrix has a determinant of 1, so it's not in the set. Again, a subsemigroup, not a submonoid.

So, to check for a submonoid, you just ask two questions: Are you closed? And do you have the identity? If the answer is yes to both, welcome to the club.

One of the most profound ideas in modern algebra is that abstract structures can be represented by concrete ones. The famous Cayley's theorem states that every group, no matter how exotic, can be viewed as just a group of permutations—a set of functions that shuffle elements around.

There's a beautiful analogue for monoids. Every monoid can be thought of as a collection of functions acting on itself. For any element $m$ in our monoid $M$, we can define a function $\lambda_m$ that simply multiplies every element of the monoid by $m$ on the left: $\lambda_m(x) = m \cdot x$. This simple idea provides a "looking glass" through which we can see the true nature of the monoid's elements.

What happens when we look through this glass? If an element $m$ has an inverse, say $m^{-1}$, then the function $\lambda_m$ is a permutation. It just shuffles the elements of $M$ around, and its action can be perfectly undone by the function $\lambda_{m^{-1}}$. The structure is rigid and reversible.

But what if $m$ does not have an inverse? Then the function $\lambda_m$ is not a permutation. It's a "collapsing" function. It might map several different elements to the same destination, and its action cannot be perfectly reversed.

Let's take the monoid of integers from 0 to 9 under multiplication modulo 10. The element 3 has an inverse, 7 (since $3 \times 7 = 21 \equiv 1 \pmod{10}$). If you apply the function $\lambda_3$ (multiplying by 3) to all ten numbers, you'll see it permutes them. But consider the element 2, which has no inverse. The function $\lambda_2$ maps the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ to the set $\{0, 2, 4, 6, 8, 0, 2, 4, 6, 8\}$. The image is smaller; information is lost. For example, both 1 and 6 are mapped to 2. You can't look at the result "2" and know for sure where it came from. The lack of an inverse for the element $2$ in the abstract monoid manifests as the non-invertibility of the function $\lambda_2$.

This is the beauty of Cayley's idea for monoids: the abstract property of invertibility within the monoid is perfectly mirrored by the concrete property of bijectivity (being a permutation) in its function representation. A monoid is not just a group with some "broken" elements; it's a richer structure that includes both permutations and these irreversible, collapsing transformations.

Within any monoid, some elements are more "special" than others. These are the elements that do have a two-sided inverse—the invertible ones. They are the VIPs of the monoid. It turns out that if you gather all these invertible elements together, they form their own exclusive club, and it's not just any club—it's a ​​group​​. This is called the ​​group of units​​ of the monoid.

Think of the monoid of all $n \times n$ matrices under multiplication. The group of units is the set of all invertible matrices, known as the general linear group, $GL_n(\mathbb{R})$. Within this already exclusive club, we can find an even more select group: the matrices with determinant 1. The product of two such matrices also has determinant 1, the identity matrix has determinant 1, and the inverse of a matrix with determinant 1 also has determinant 1. This forms a subgroup called the special linear group, $SL_n(\mathbb{R})$, a submonoid of a submonoid!.

This reveals a wonderful hierarchy. A group is simply a monoid where every element is a unit. A monoid, in general, is a world containing a well-behaved, invertible core (its group of units) surrounded by a "husk" of non-invertible, collapsing elements.

We've assumed so far that any submonoid must contain the one, true identity element of the larger world. But algebra is full of surprises. Can a subset form a perfectly good monoid with its own identity element, one that is not the identity of the parent monoid?

The answer is a resounding yes, and it leads to the fascinating idea of ​​idempotents​​. An idempotent is an element $e$ that, when applied to itself, does nothing: $e \cdot e = e$. The main identity element is always an idempotent, but there can be others.

Think of a projector. It takes a 3D object and creates a 2D image on a screen. If you take that 2D image and "project" it again, it doesn't change. The projection operation is idempotent. In the world of matrices, a projection matrix $P$ satisfies $P^2=P$. For example, $P = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix}$ projects any vector in the plane onto the x-axis. Applying it twice is the same as applying it once.

An idempotent $e$ that isn't the main identity acts as a ​​local identity​​ for a sub-universe. It carves out a piece of the larger monoid and governs it. Consider the set of all functions mapping a set $X$ to itself. This is a huge monoid called the full transformation monoid, $T_X$. An idempotent function $e$ here is one where $e \circ e = e$. Such a function maps the entire space $X$ into a smaller subspace, its image $Y = \text{Im}(e)$, and then acts like the identity on that subspace.

Now, consider the set of all functions $f$ that "live" entirely within this subspace, in the sense that they are completely controlled by $e$ (formally, $e \circ f = f$ and $f \circ e = f$). This collection of functions forms a submonoid. Its identity element is not the original identity function on all of $X$, but the idempotent function $e$! And what's more, this submonoid is a perfect copy (isomorphic to) the entire transformation monoid of the smaller set, $T_Y$.

This is a stunning revelation. Hidden within a large monoid, there can be smaller, self-contained universes, each with its own local "laws of physics" dictated by its own local identity element. It's like finding that a neighborhood in our city not only has its own exclusive club, but the club's leader isn't the mayor—it's a local figurehead who rules only over that neighborhood, yet within those boundaries, their power is absolute. Exploring submonoids is not just about finding subsets that follow the rules; it's about uncovering these hidden worlds and the elegant principles that govern their existence.

We have spent some time getting acquainted with the formal machinery of monoids and their intimate sub-structures, submonoids. You might be tempted to think this is a rather abstract game, a mathematician's sandbox filled with symbols and axioms. And you would be partly right. But it is a game that Nature, and the human mind, seem to delight in playing. Once you learn the rules, you begin to see its patterns etched into the world around us, from the secret logic of our computers to the very structure of numbers and the shape of space. This chapter is our journey into the wild, to witness how this abstract concept of a set closed under an operation provides a surprisingly powerful lens for understanding the world.

Let’s begin with something we interact with daily: computation. At its heart, a computer is a machine that follows a sequence of instructions to transform data. This process is not random; it is governed by a deep and elegant logic, a logic that often has the structure of a submonoid.

Consider the task of a machine scanning a string of data, like ababba..., to determine if it possesses a certain property. The machine transitions between internal states with each symbol it reads. The set of all possible sequences of transitions forms a monoid under composition. A language is "recognized" if the final state, after processing the entire string, belongs to a special set of "accepting" states.

Now, imagine we are interested in properties like, "The number of 'a's is even, and the number of 'b's is a multiple of three." The journey through the machine's states can be mapped to a journey within an algebraic structure, such as the group $\mathbb{Z}_2 \times \mathbb{Z}_3$. Each input symbol corresponds to an element in this group, and processing a string corresponds to combining these elements using the group operation. A string is accepted if and only if the resulting element lies within a specific subgroup of accepting states—in this case, the subgroup containing only the identity element, $(0,0)$. The closure property of the subgroup ensures that if two strings lead to an accepting state, their concatenation also leads to an accepting state, so the set of recognized strings forms a submonoid.

What happens if we change the condition to "The number of 'a's is even, or the number of 'b's is a multiple of three"? Suddenly, this neat algebraic picture can shatter. The set of "successful" journeys no longer forms a subgroup. We can have two successful journeys that, when combined with other operations valid within a group structure, lead to a journey that should be unsuccessful. This demonstrates a profound principle: the algebraic structure of the set of recognized strings is intimately tied to the logic of the property being checked. Properties built on 'and' often preserve the submonoid or subgroup structure, while 'or' conditions can break it.

This idea extends beyond simple recognition to the very nature of computational processes. We can model a system as a "state machine" where inputs trigger transformations of the system's state. The set of all possible transformations generated by sequences of inputs forms a submonoid within the monoid of all possible self-maps of the state space. A fascinating question arises: under what conditions is this system "reversible"? That is, when does this submonoid of transformations have the elegant, symmetrical structure of a group, where every action has an inverse? The answer, beautifully, lies in the properties of the fundamental, individual transformations. The entire system is reversible if, and only if, its most basic building-block operations are themselves reversible (bijections). This is a powerful lesson: the global properties of a complex system are often dictated by the algebraic nature of its elementary parts.

The influence of submonoids extends far beyond the digital realm, providing a combinatorial skeleton for some of the most profound structures in mathematics. They act as a bridge, connecting simple, countable sets to the sprawling, continuous worlds of algebra and geometry.

One of the most elegant examples of this is the numerical semigroup algebra. Let's start with a simple submonoid of the natural numbers, for instance, the set $S$ of all numbers you can make by adding $4$, $6$, and $9$ in any combination ($S = \{0, 4, 6, 8, 9, 10, 12, \dots\}$). We can build an entire algebraic universe, a ring, from this humble set. This ring, denoted $k[S]$, consists of polynomials where the powers of the variable must belong to our submonoid $S$. It's a strange world where $t^1, t^2, t^3, t^5, \dots$ simply do not exist.

The astonishing discovery is that the deepest properties of this algebraic ring are a direct mirror of the combinatorial properties of the submonoid $S$. For example, one of the most cherished properties in algebra is unique factorization, the fact that any number can be factored into primes in exactly one way. When does our ring $k[S]$ have this property? The answer is as stark as it is beautiful: $k[S]$ is a unique factorization domain if and only if the underlying submonoid $S$ has no gaps at all—that is, $S$ must be the entire set of non-negative integers $\mathbb{N}_0$. The existence of a single "gap," a single number that cannot be formed by the generators, introduces an ambiguity into the algebraic world that destroys unique factorization.

Furthermore, simple operations in the algebra become puzzles in the submonoid. Calculating the product of ideals, a fundamental algebraic construction, boils down to studying which new numbers can be formed by adding elements of the submonoid to each other. Even more strangely, if we choose a submonoid that is not finitely generated, like the set of non-negative rational numbers whose denominators are powers of two, we can create a ring with pathological properties, such as an infinite, strictly ascending chain of ideals that never stabilizes. The properties of the submonoid—its gaps, its generators, its very finiteness—serve as the blueprint for the resulting algebra.

This unifying perspective reaches a magnificent peak in number theory. The study of numbers is filled with "arithmetic functions" that tell us about the properties of integers, and these functions can be combined using a mysterious operation called Dirichlet convolution. It turns out this entire rich and complex theory is, in disguise, the theory of a monoid algebra. The monoid is simply the set of positive integers under multiplication, $(\mathbb{N}_{\ge 1}, \times)$. The Fundamental Theorem of Arithmetic, which guarantees unique prime factorization, provides a Rosetta Stone, allowing us to see that this monoid is structurally identical (isomorphic) to a much simpler "free" monoid built from the prime numbers. This translation converts the arcane Dirichlet convolution into simple polynomial multiplication, revealing a breathtaking unity between number theory and algebra, all expressed in the language of monoids.

The organizing power of submonoids doesn't stop at the abstract. It shapes the outcomes of random processes and describes the very notion of symmetry in geometric spaces.

Imagine a particle hopping randomly on a numbered dial with $N$ positions. At each step, its position $k$ might be mapped to $2k \pmod N$ or $3k \pmod N$. Will the particle eventually be able to visit every position? Or will it become trapped in a smaller subset? The long-term behavior of this random walk is entirely governed by the submonoid generated by the multipliers $\{2, 3\}$ within the group of numbers coprime to $N$. The structure of this submonoid partitions the entire state space into "communicating classes"—inescapable zones between which no travel is possible. The algebraic properties of a few numbers dictate the fate of the particle, carving up the space of possibilities into separate, sealed-off worlds.

Perhaps the most surprising appearance of this structure is in topology, the study of shape and space. Imagine a helix endlessly winding above a circle. This is an example of a "covering space." We can ask: which continuous transformations of the helix onto itself "descend" to a well-defined transformation of the circle below? For a map to descend, it must respect the fundamental symmetry of the covering—for instance, shifting a point on the helix up by one full turn lands it directly above where it started. These symmetries themselves form a group, the deck transformation group $G$.

The set of all continuous maps of the helix to itself forms a giant monoid under function composition. The stunning result is that the condition for a map $\alpha$ to descend is a purely algebraic one: $\alpha$ must belong to the normalizer of the deck group $G$ within this larger monoid of maps. A map normalizes $G$ if, when composed with a symmetry operation, the result is the same as composing it with some (possibly different) symmetry operation after the map. A deeply geometric property—compatibility with the projection down to the circle—is perfectly equivalent to a subtle algebraic relationship between the map, the group of symmetries, and the monoid they live in.

From the logic of a finite automaton to the symmetries of topological space, from the factorization of polynomials to the fundamental theorem of arithmetic, the simple concept of a submonoid appears again and again as a unifying thread. It reminds us that abstraction in science is not an escape from reality, but a tool to see its hidden skeleton. The humble rule of closure, when we chase its consequences with persistence and imagination, reveals the profound and beautiful interconnectedness of the mathematical universe.