Unit 3: Groups
Discrete Structures & Optimization notes · PTU syllabus (PGCA1917)
On this page
Unit summary
Groups capture symmetry and are used in coding theory and cryptography. This unit covers groups, semigroups and monoids, cyclic semigroups and submonoids, subgroups and cosets, congruence relations on semigroups, morphisms, normal subgroups and dihedral groups.
After this unit you can
- Distinguish semigroups, monoids and groups
- Identify cyclic semigroups, submonoids and subgroups
- Find cosets and apply Lagrange's theorem
- Explain congruence relations, morphisms, normal subgroups and dihedral groups
PTU syllabus topics
- Groups
- semigroups and monoids
- cyclic semigroups and submonoids
- subgroups and cosets
- congruence relations on semigroups
- morphisms
- normal subgroups
- dihedral groups
- Abelian group
Group + commutative
- Group
Monoid + every element has an inverse
- Monoid
Semigroup + identity element
- Semigroup
Closed and associative
Topic 1
Semigroups and monoids
- Abelian group
Group with commutative operation
- Group
Monoid in which every element has an inverse
- Monoid
Semigroup with an identity element
- Semigroup
Set with an associative binary operation
- Groupoid
Set closed under a binary operation
Example
(N, +) is a semigroup; (N ∪ {0}, +) is a monoid with identity 0; (Z, +) is a group; (Z, ×) is a monoid but not a group; strings under concatenation form a monoid with the empty string as identity.
Topic 2
Cyclic semigroups and submonoids
- A semigroup is cyclic if it is generated by one element a: {a, a², a³, …}. A subsemigroup is a subset closed under the operation; a submonoid also contains the identity.
Example
Even non-negative integers under + form a submonoid of (N ∪ {0}, +); powers of 2 under multiplication {1, 2, 4, 8, …} form a cyclic monoid generated by 2.
Topic 3
Groups
- A group (G, ) satisfies closure, associativity, identity* and inverse. If a * b = b * a for all elements it is abelian. The order of G is its number of elements; the order of an element a is the least n with aⁿ = e.
- (Z, +)
- Infinite abelian group
- (Zn, + mod n)
- Finite cyclic group of order n
- (non-zero elements of Zp, × mod p)
- Multiplicative group for prime p
- Non-singular n × n matrices under multiplication
- Non-abelian group
- Symmetric group Sn
- All permutations of n objects; order n!
- Properties: the identity and each inverse are unique; (ab)⁻¹ = b⁻¹a⁻¹; cancellation laws hold.
Topic 4
Subgroups and cosets
- Subgroup test: a non-empty subset H of G is a subgroup if a, b ∈ H implies ab⁻¹ ∈ H.
- Cosets: for a in G, the left coset aH = {ah : h ∈ H}; cosets partition G and all have |H| elements.
- Lagrange's theorem: the order of a subgroup divides the order of a finite group; hence the order of every element divides |G|.
Example
In (Z6, +), H = {0, 3} is a subgroup; cosets are {0, 3}, {1, 4}, {2, 5}; 3 cosets × 2 = 6. A group of order 7 has no proper subgroups other than {e}, so it is cyclic.
Topic 5
Congruence relations on semigroups
- An equivalence relation R on a semigroup (S, ) is a congruence* if a R b and c R d imply (a * c) R (b * d). The equivalence classes then form a quotient semigroup S/R with [a] * [b] = [a * b].
Example
Congruence modulo n on (Z, +): if a ≡ b and c ≡ d (mod n) then a + c ≡ b + d, giving the quotient group Zn.
Topic 6
Morphisms
- A homomorphism f: (G, ) → (H, ∘) satisfies f(a b) = f(a) ∘ f(b). It is a monomorphism if one-to-one, an epimorphism if onto, and an isomorphism if both; an isomorphism from G to itself is an automorphism.
Example
f(x) = 2ˣ maps (Z, +) to (positive rationals, ×) as a homomorphism, since 2^(a + b) = 2ᵃ × 2ᵇ. f(x) = x mod n maps Z onto Zn; its kernel is nZ.
- Kernel ker f = {a : f(a) = e} is a normal subgroup; fundamental theorem: G / ker f is isomorphic to f(G).
Topic 7
Normal subgroups
- A subgroup N of G is normal if gN = Ng for every g in G (equivalently gng⁻¹ ∈ N). Then the cosets form the quotient (factor) group G/N.
- Every subgroup of an abelian group is normal; a subgroup of index 2 is always normal.
Topic 8
Dihedral groups
- The dihedral group Dn is the group of symmetries of a regular n-sided polygon: n rotations and n reflections, so |Dn| = 2n. It is generated by a rotation r (rⁿ = e) and a reflection s (s² = e) with srs = r⁻¹; it is non-abelian for n ≥ 3.
Example
D3 (symmetries of an equilateral triangle) has 6 elements: e, r, r², s, rs, r²s — isomorphic to S3, the smallest non-abelian group. D4 (square) has 8 elements.
Key terms
- Semigroup
- Set with an associative binary operation
- Monoid
- Semigroup with an identity element
- Coset
- Set aH formed by combining an element with a subgroup
- Normal subgroup
- Subgroup invariant under conjugation
- Dihedral group
- Symmetry group of a regular polygon
Quick revision
- Groupoid → semigroup → monoid → group → abelian group.
- Cyclic semigroups; submonoids; subgroup test.
- Cosets partition G; Lagrange's theorem.
- Congruences and quotient semigroups; homomorphism, isomorphism, kernel.
- Normal subgroups and quotient groups; Dn has 2n elements.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Distinguish a semigroup and a monoid.
- Q2.Is (Z, ×) a group? Why?
- Q3.State Lagrange's theorem.
- Q4.List the cosets of {0, 2, 4} in Z6.
- Q5.When is a subgroup normal?
- Q6.What is the order of D5?
Long-answer questions
- Q1.Explain semigroups, monoids and groups with examples.
- Q2.Explain subgroups, cosets and Lagrange's theorem.
- Q3.Explain congruence relations and homomorphisms.
- Q4.Explain normal subgroups and dihedral groups.
Stuck on this unit?
Message SBS on WhatsApp for help with Discrete Structures & Optimization, or to ask about studying M.Sc IT at Synetic.