Semigroup in Discrete Mathematics

---

---

Algebraic Structures play an important role in Group Theory and Discrete Mathematics. Among these structures, one of the useful structures is a semigroup. A semigroup is a set paired with an operation that satisfies a specific property.

In this chapter, we will explain what a semigroup is and why it is important. In addition, we will provide several examples to help you understand the concept better.

What is a Semigroup?

A semigroup is nothing but an algebraic structure. As we know, an algebraic structure is a collection of set and an operation like addition or multiplication that we apply to elements within that set. However, for it to be considered an algebraic structure, the set must satisfy the closure property.

Closure Property

The Closure Property implies that, if we apply the operation to any two elements of the set, the result must also be an element of the set. For example, the set of natural numbers (1, 2, 3, …) is closed under addition. If we add two natural numbers, we will always get another natural number.

Once the closure property is satisfied, we can start talking about semigroups. And a semigroup is an algebraic structure that satisfies two properties −

• Closure Property − The set must be closed under the operation.
• Associative Property − The operation must be associative. This means the way in which elements are grouped during the operation does not affect the result. In other words, (A * B) * C should be the same as A * (B * C).

If a set and operation satisfy both of these properties, then we have a semigroup. The operation could be addition, multiplication, or any binary operation.

Understanding Associative Property

The Associative Property is at the heart of what makes a semigroup. Associativity means that no matter how the group elements are arranged, the result remains the same. For example, with addition −

$$\mathrm{(2 \:+\: 3) \:+\: 5 \:=\: 2 \:+\: (3 \:+\: 5) \:=\: 10}$$

Here, the order in which we add the numbers does not matter. This is why addition is associative. On the other side, not all operations are associative. Subtraction, for example, is not associative −

$$\mathrm{(7 \:-\: 3) \:-\: 2 \:\neq\: 7 \:-\: (3 \:-\: 2)}$$

This difference is key when determining whether something qualifies as a semigroup.

Examples of Semigroups

Let us now understand more about semigroups with the help of a set of examples −

Example 1: Natural Numbers under Addition

The set of natural numbers (1, 2, 3, …) under the operation of addition forms a semigroup. It is because:

• Closure Property − If we add any two natural numbers, the result is also a natural number. For instance, 2 + 5 = 7.
• Associative Property − Addition is associative. No matter how our group the numbered, the sum will be the same. For example, (1 + 2) + 3 equals 1 + (2 + 3), both returning 6.

Since both properties are satisfied, the set of natural numbers under addition forms a semigroup.

Example 2: Integers under Multiplication

Now, let us consider the set of integers (…, -3, -2, -1, 0, 1, 2, 3, …) under multiplication.

• Closure Property − Multiplying any two integers will always give another integer. For example, 5 * (-3) = -15.
• Associative Property − Multiplication is also associative. So, (2 * 3) * 4 is the same as 2 * (3 * 4), and both equal 24.

Thus, the set of integers under multiplication forms a semigroup.

Example 3: Real Numbers under Addition

The set of real numbers, which includes all rational and irrational numbers, under the operation of addition is also a semigroup.

• Closure Property − Adding two real numbers would always result in a real number. For example, 1.5 + 2.3 = 3.8.
• Associative Property − Just like with integers, addition is associative with real values. For example, (1.2 + 3.4) + 5.6 is the same as 1.2 + (3.4 + 5.6), and both equal 10.2.

So that, real numbers under addition satisfy both properties and form a semigroup.

Non-Examples of Semigroups

Not every set and operation combination forms a semigroup. Let us look at some cases where they do not.

Example 1: Natural Numbers under Subtraction

While natural numbers form a semigroup under addition, they do not form a semigroup under subtraction. Because −

• Closure Property − If we subtract two natural numbers, the result is not always a natural number. For example, 5 - 10 = -5, which is not a natural number.
• Associative Property − Subtraction is not associative. For instance, (7 - 3) - 2 is not the same as 7 - (3 - 2). In the first case, we get 2, and in the second, we get 6.

Since both properties are not satisfied, natural numbers under subtraction do not form a semigroup.

Example 2: Integers under Division

Let us consider the set of integers under division.

• Closure Property − Division of two integers does not always give an integer. For example, 5 ÷ 2 = 2.5, which is not an integer.
• Associative Property − Division is not associative. For example, (8 ÷ 4) ÷ 2 is 1, but 8 ÷ (4 ÷ 2) is 4.

Therefore, integers under division does not form a semigroup.

Associativity Example

Let us see another real-world analogy to understand associativity. Imagine we are at a restaurant ordering food. The chef can prepare meals in any sequence, and we will get the same result. Whether the chef prepares the appetizer, then the main course, and then the dessert, or prepares the dessert first, the final meal is still complete.

In this sense, associativity is like the flexibility of a chefs cooking sequence. As long as all the steps are followed, the result will be the same.

Special Case: Semigroups in Modular Arithmetic

The example of a semigroup can be found in modular arithmetic, which is often used in several use cases in computer science. For instance, let us consider the set of integers under addition modulo 5. In this case −

• Closure Property − Adding two numbers modulo 5 always results in a number between 0 and 4. For example, (3 + 4) mod 5 = 2.
• Associative Property − Addition modulo 5 is associative. For example, (1 + 2) mod 5 + 3 mod 5 is the same as 1 mod 5 + (2 + 3) mod 5.

Thus, modular arithmetic with addition forms a semigroup.

Conclusion

A semigroup is an algebraic structure where the set of elements is closed under a binary operation and that operation is associative.

In this chapter, we presented several examples, including natural numbers under addition and integers under multiplication, to understand how the closure and associative properties work. Additionally, we understood non-examples too, like natural numbers under subtraction and integers under division.