Monoid in Discrete Mathematics

---

---

We consider different types of groups while working with groups in algebraic structures inside discrete mathematics. One of the key structures in this context is the monoid that builds upon the ideas of both algebraic structures and semigroups but includes an additional feature that sets it apart: the identity element.

In this chapter, we will see what a monoid is, look at the properties it must satisfy, and go through several examples to understand it properly.

What is a Monoid?

To understand monoids, let us first recap the concept of semigroups. A semigroup is nothing but a set of elements that satisfies two main properties:

• Closure − If we apply a binary operation (such as addition or multiplication) on any two elements of the set, the result must still belong to the set.
• Associativity − The way in which we group the elements when applying the operation does not matter. For example, (a * b) * c should give the same result as a * (b * c).

A monoid builds on the concept of a semi-group but adds an extra condition: the identity element.

Identity Element

An identity element is a special element in the set that, when combined with any other element of the set using the binary operation, leaves the other element unchanged.

If the operation is addition, the identity element is 0 because adding 0 to any number leaves it the same.

For multiplication, the identity element is 1 because multiplying any number by 1 results in the same number.

Formally we can say, for a set S with a binary operation (∗*∗), if there exists an element e ∈ S such that for all a ∈ S,

$$\mathrm{a * e \:=\: e * a \:=\: a}$$

Then e is the identity element, and S is a monoid.

Monoid Properties

A Monoid must satisfy the following three properties −

• Closure − The set must be closed under the operation. This means applying the operation to any two elements of the set results in another element from the set.
• Associativity − The operation must be associative, meaning grouping the elements in different ways does not affect the outcome of the operation.
• Identity Element − There must exist an identity element that, when combined with any other element using the operation, leaves that element unchanged.

If a set and operation satisfy all three of these properties, then we have a monoid.

Examples of Monoids

Go through the following examples understand how monoids work in practice −

Example 1: Integers under Addition

Let us consider with the set of integers Z and the operation of addition.

• Closure − If we add any two integers, the result is always another integer. For example, 5 + 3 = 8.
• Associativity − Addition is associative. That is, (5 + 3) + 2 is the same as 5 + (3 + 2), and both give 10.
• Identity Element − The identity element for addition is 0, because adding 0 to any number leaves the number unchanged. For example, 5 + 0 = 5.

Since integers under addition satisfy closure, associativity, and have an identity element (0), they form a monoid.

Example 2: Natural Numbers under Multiplication

Now consider the set of natural numbers N = {1, 2, 3, 4, … } under multiplication.

• Closure − Multiplying any two natural numbers results in another natural number. For example, 3 * 4 = 12.
• Associativity − Multiplication is associative, meaning (2 * 3) * 4 = 2 * (3 * 4) = 24
• Identity Element − The identity element for multiplication is 1, because multiplying any number by 1 leaves the number unchanged. For example, 5 * 1 = 5.

Thus, the natural numbers under multiplication form a monoid with the identity element is being 1.

Example 3: Real Numbers under Multiplication

Consider the set of real numbers R under multiplication. However, in this case, we exclude 0 because multiplying by 0 does not preserve the elements.

• Closure − Multiplying any two real numbers results in another real number. For example, 5 * 3 = 7.5.
• Associativity − Multiplication is associative, so (2 * 3) * 4 = 2 * (3 * 4).
• Identity Element − The identity element for multiplication is 1, because multiplying any real number by 1 leaves the number unchanged.

So that, the set of non-zero real numbers under multiplication forms a monoid.

Examples of Non-Monoids

Let us see some examples where the groups are not monoids.

Example 1: Integers under Subtraction

If we take the set of integers under the operation of subtraction, does it form a monoid?

• Closure − Subtracting two integers gives another integer, so it satisfies the closure property.
• Associativity − Subtraction is not associative. For example, (7 - 3) - 2 ≠ 7 - (3 - 2).
• Identity Element − Subtraction also does not have an identity element that leaves all other elements unchanged. There is no number that, when subtracted from any integer, leaves the integer the same.

So that, the set of integers under subtraction does not form a monoid.

Example 2: Natural Numbers under Division

Consider the set of natural numbers under the division.

• Closure − Division of natural numbers does not always result in another natural number. For example, 4 ÷ 2 = 2, but 5 ÷ 2 = 2.5, which is not a natural number.
• Associativity − Division is also not associative. For example, (8 ÷ 4) ÷ 2 = 1, but 8 ÷ (4 ÷ 2) = 4.
• Identity Element − There is no identity element for division in natural numbers, as dividing by 1 does not leave all elements unchanged.

Therefore, natural numbers under division do not form a monoid.

Monoid in Modular Arithmetic

Another great application of monoids is found in modular arithmetic. They are especially in computer science we use such techniques.

Consider a set Z₅ = {0, 1, 2, 3, 4} under addition modulo 5.

• Closure − Adding any two elements and taking the result modulo 5 results in another element in the set. For example, (3 + 4) mod 5 = 2.
• Associativity − Addition modulo 5 is associative. So, (1 + 2) mod 5 + 3 mod 5 gives the same result as 1 mod 5 + (2 + 3) mod 5.
• Identity Element − The identity element here is 0, as (n + 0) mod 5 = n.

Thus, the set Z₅ under addition modulo 5 is a monoid.

Conclusion

Monoids build upon the concept of semigroups by introducing an identity element. In this chapter, we explained the three main properties of a Monoid: closure, associativity, and the existence of an identity element.

We presented several examples, including integers under addition, natural numbers under multiplication, and modular arithmetic, to illustrate how Monoids work in practice. Additionally, we understood the cases like integers under subtraction and natural numbers under division that are not monoids because they fail to satisfy one or more of these properties.