DISCRETE MATHEMATICS NOTES
Algebraic Systems, Modulo Systems, Homomorphism &
Isomorphism
Prepared by
Dr. Obwocha Abraham
March 28, 2026
1 1. Introduction to Algebraic Systems
Definition
An algebraic system is a mathematical structure consisting of:
• A non-empty set A
• One or more operations defined on A
It is written as:
(A, ∗)
Explanation: This means we take elements from a set and combine them using a
rule (operation) to produce another element.
2 2. Binary Operations
Definition
A binary operation on a set A is a function:
∗:A×A→A
which assigns each pair (a, b) to a unique element in A.
Key Idea: The result of the operation must always remain inside the set.
1
2.1 Worked Example 1
Worked Example
Let A = {0, 1, 2} and define:
a ∗ b = (a + b) mod 3
Compute:
1 ∗ 2 = (1 + 2) mod 3 = 3 mod 3 = 0
Explanation:
• Add: 1 + 2 = 3
• Divide by 3 → remainder is 0
• Result 0 ∈ A
Therefore, the operation is valid.
3 3. Properties of Binary Operations
3.1 3.1 Closure
Definition
A set A is closed under operation ∗ if:
a ∗ b ∈ A ∀a, b ∈ A
Worked Example
Let A = {0, 1, 2} under addition mod 3
2+2=4 mod 3 = 1
Since 1 ∈ A, closure holds.
3.2 3.2 Associativity
Definition
An operation is associative if:
(a ∗ b) ∗ c = a ∗ (b ∗ c)
2
Worked Example
(2 + 3) + 4 = 5 + 4 = 9
2 + (3 + 4) = 2 + 7 = 9
Since both sides are equal, the operation is associative.
3.3 3.3 Identity Element
Definition
An element e is called identity if:
a∗e=a
Worked Example
For addition:
5+0=5
Thus, identity is 0.
3.4 3.4 Inverse Element
Definition
An element b is the inverse of a if:
a∗b=e
Worked Example
7 + (−7) = 0
Thus, inverse of 7 is −7.
4 4. Cayley Tables
Explanation: A Cayley table shows how elements combine under an operation.
4.1 Example: Addition Mod 3
+3 0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
Observations:
• Closure holds
3
• Identity = 0
• Inverses exist
4
5
4.2 Worked Example: Cayley Table
Worked Example
Problem: Construct a Cayley table for the set
A = {0, 1, 2}
under addition modulo 3.
Step 1: Define the operation
a+b mod 3
Step 2: Compute all combinations:
• 0 + 0 mod 3 = 0
• 0 + 1 mod 3 = 1
• 0 + 2 mod 3 = 2
• 1 + 0 mod 3 = 1
• 1 + 1 mod 3 = 2
• 1 + 2 mod 3 = 0
• 2 + 0 mod 3 = 2
• 2 + 1 mod 3 = 0
• 2 + 2 mod 3 = 1
Step 3: Fill the table
+3 0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
Step 4: Observations
• Closure: All results are in A
• Identity: 0
• Inverses:
0 → 0, 61 → 2, 2→1
• Associativity: Inherited from addition
5 5. Algebraic Structures
5.1 5.1 Semigroup
Definition
A semigroup satisfies:
• Closure
• Associativity
5.2 5.2 Monoid
Definition
A monoid is a semigroup with an identity element.
5.3 Monoid
Definition
A monoid is an algebraic structure (A, ∗) that satisfies:
• Closure: a ∗ b ∈ A
• Associativity: (a ∗ b) ∗ c = a ∗ (b ∗ c)
• Identity element: ∃e ∈ A such that a ∗ e = a
Explanation: A monoid is similar to a semigroup but with an additional property:
it must have an identity element. However, unlike a group, a monoid does not require
inverse elements.
7
5.3.1 Worked Example
Worked Example
Consider the set of natural numbers:
N = {0, 1, 2, 3, . . . }
with addition (+).
Step 1: Closure
2+3=5∈N
Step 2: Associativity
(2 + 3) + 4 = 5 + 4 = 9
2 + (3 + 4) = 2 + 7 = 9
Step 3: Identity
5+0=5
Step 4: Inverse There is no number in N such that:
5+x=0
Conclusion: All required properties are satisfied except inverse, therefore (N, +)
is a monoid but not a group.
5.3.2 Another Example (Multiplication)
Worked Example
Consider (N, ×)
Closure:
2×3=6∈N
Associativity:
(2 × 3) × 4 = 2 × (3 × 4)
Identity:
5×1=5
Conclusion: (N, ×) is also a monoid with identity element 1.
8
5.4 5.3 Group
Definition
A group satisfies:
• Closure
• Associativity
• Identity
• Inverse
5.5 5.4 Abelian Group
Definition
A group is Abelian if:
a∗b=b∗a
6 6. Worked Example: Verifying a Group
Worked Example
Let A = {0, 1, 2} under addition mod 3.
Step 1: Closure All results remain in set.
Step 2: Associativity Inherited from addition.
Step 3: Identity 0 is identity.
Step 4: Inverses
Element Inverse
0 0
1 2
2 1
Conclusion: It is a group.
7 7. Summary
• Algebraic system = Set + Operation
• Binary operation must satisfy closure
• Important properties: Associativity, Identity, Inverse
• Structures include Semigroup, Monoid, Group
9
8 8. Modulo Systems
8.1 8.1 Introduction to Modulo Arithmetic
Definition
Modulo arithmetic is a system of arithmetic for integers where numbers ”wrap
around” after reaching a certain value called the modulus.
a mod n = remainder when a is divided by n
Explanation: Instead of working with large numbers, modulo reduces them into a
fixed range:
0, 1, 2, . . . , n − 1
8.2 8.2 Understanding Modulo (Step-by-Step)
Worked Example
Compute:
17 mod 5
Step 1: Divide
17 ÷ 5 = 3 remainder 2
Step 2: Write result
17 mod 5 = 2
Conclusion: The answer is the remainder after division.
8.3 8.3 Addition Modulo
Definition
Addition modulo n is defined as:
(a + b) mod n
Procedure:
1. Add the numbers normally
2. Divide by n
3. Take the remainder
10
8.3.1 Worked Example 1
Worked Example
(8 + 6) mod 5
Step 1: Add
8 + 6 = 14
Step 2: Divide
14 ÷ 5 = 2 remainder 4
Answer:
(8 + 6) mod 5 = 4
8.3.2 Worked Example 2
Worked Example
(9 + 7) mod 4
Step 1: Add
9 + 7 = 16
Step 2: Divide
16 mod 4 = 0
Answer: 0
8.4 8.4 Addition Modulo Table (Cayley Table)
Example: Addition mod 4
+4 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2
Observations:
• Identity element = 0
• Each element has an inverse:
– 1→3
– 2→2
11
8.5 8.5 Multiplication Modulo
Definition
Multiplication modulo n is defined as:
(a × b) mod n
Procedure:
1. Multiply normally
2. Divide by n
3. Take remainder
8.5.1 Worked Example 1
Worked Example
(7 × 6) mod 5
Step 1: Multiply
7 × 6 = 42
Step 2: Divide
42 ÷ 5 = 8 remainder 2
Answer:
(7 × 6) mod 5 = 2
8.5.2 Worked Example 2
Worked Example
(9 × 4) mod 7
Step 1: Multiply
9 × 4 = 36
Step 2: Divide
36 mod 7 = 1
Answer: 1
8.6 8.6 Multiplication Modulo Table
Example: Multiplication mod 5
12
×5 0 1 2 3 4
0 0 0 0 0 0
1 0 1 2 3 4
2 0 2 4 1 3
3 0 3 1 4 2
4 0 4 3 2 1
Observations:
• Identity = 1
• Not all elements have inverses
• Only numbers coprime with 5 have inverses
8.7 8.7 Important Properties of Modulo Arithmetic
Definition
For any integers a, b, n:
(a + b) mod n = [(a mod n) + (b mod n)] mod n
(a × b) mod n = [(a mod n)(b mod n)] mod n
Worked Example
(17 + 8) mod 5
= (2 + 3) mod 5 = 5 mod 5 = 0
8.8 8.8 Real-Life Interpretation
• Clock arithmetic (12-hour clock)
• Computer science (hashing, encryption)
• Cyclic patterns
9 9. Homomorphism
9.1 9.1 Definition
Definition
A homomorphism is a function between two algebraic systems that preserves the
operation.
f (a ∗ b) = f (a) ◦ f (b)
13
Explanation: This means performing the operation first and then applying the
function gives the same result as applying the function first and then performing the
operation.
9.2 9.2 Step-by-Step Method to Test Homomorphism
To verify if a function f is a homomorphism:
1. Compute f (a ∗ b)
2. Compute f (a) ◦ f (b)
3. Compare both results
If equal ⇒ homomorphism
9.3 9.3 Worked Example 1 (Valid Homomorphism)
Worked Example
Let f (x) = 2x from (Z, +) to (Z, +)
Step 1: Compute LHS
f (a + b) = 2(a + b) = 2a + 2b
Step 2: Compute RHS
f (a) + f (b) = 2a + 2b
Conclusion: LHS = RHS ⇒ Homomorphism
9.4 9.4 Worked Example 2 (Not a Homomorphism)
Worked Example
Let f (x) = x2
Step 1:
f (a + b) = (a + b)2 = a2 + 2ab + b2
Step 2:
f (a) + f (b) = a2 + b2
Comparison:
a2 + 2ab + b2 ̸= a2 + b2
Conclusion: Not a homomorphism
14
9.5 9.5 Homomorphism in Modulo Systems
Worked Example
Let f (x) = x mod 5
Check:
f (a + b) = (a + b) mod 5
f (a) + f (b) = (a mod 5 + b mod 5) mod 5
Both sides are equal due to modulo properties.
Conclusion: f is a homomorphism
10 10. Isomorphism
10.1 10.1 Definition
Definition
An isomorphism is a bijective homomorphism.
It must satisfy:
• Homomorphism (operation preserved)
• One-to-one (injective)
• Onto (surjective)
Key Idea: Two algebraic structures are isomorphic if they have the same structure.
10.2 10.2 Testing for Isomorphism (Step-by-Step)
To verify isomorphism:
1. Check homomorphism property
2. Check injective (no two elements map to same value)
3. Check surjective (covers entire target set)
15
10.3 10.3 Worked Example 1 (Isomorphism)
Worked Example
Let f (x) = x from (Z, +) to (Z, +)
Step 1: Homomorphism
f (a + b) = a + b
f (a) + f (b) = a + b
Equal
Step 2: One-to-one Each element maps uniquely
Step 3: Onto Every integer is mapped
Conclusion: f is an isomorphism
10.4 10.4 Worked Example 2 (Not Isomorphism)
Worked Example
Let f (x) = x2
Check injective:
f (2) = 4, f (−2) = 4
Two different inputs give same output.
Not one-to-one
Conclusion: Not isomorphism
10.5 10.5 Key Differences
Homomorphism Isomorphism
Preserves operation Preserves operation
Not necessarily one-to-one Must be one-to-one
Not necessarily onto Must be onto
11 11. Summary of Concepts
• Homomorphism preserves algebraic structure
• Isomorphism shows two systems are identical in structure
• Modulo arithmetic is widely used in homomorphisms
• Always verify step-by-step using definitions
Exam Questions: Discrete Mathematics
1. Algebraic Systems: Define an algebraic system. Give one example and explain
why it satisfies the properties of closure, associativity, identity, and inverse (if any).
16
2. Monoid: Consider the set N = {0, 1, 2, 3, ...} under multiplication.
(a) Show that this set with multiplication forms a monoid.
(b) Identify the identity element.
(c) Explain why it is not a group.
3. Modulo Systems: Compute the following:
(a) (7 + 9) mod 5
(b) (8 × 6) mod 7
4. Cayley Table: Construct the Cayley table for the set A = {0, 1, 2} under addition
modulo 3. Identify:
(a) The identity element
(b) Inverses of each element
5. Homomorphism: Let f : (Z, +) → (Z, +) be defined by f (x) = 3x.
(a) Verify if f is a homomorphism.
(b) Explain why or why not.
6. Isomorphism: Let f : (Z, +) → (Z, +) be defined by f (x) = x + 1.
(a) Check if f is a homomorphism.
(b) Is f an isomorphism? Justify your answer.
7. True or False: Decide if the following statements are true or false:
(a) (N, +) is a group.
(b) The additive identity modulo n is 0.
(c) Every monoid is a group.
(d) A homomorphism always preserves the identity element.
17