
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
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 Z5 = {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 Z5 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.