Group theory

Welcome to Group Theory: The Mathematics of Symmetry and Structure

Welcome to Group Theory! While it might sound abstract at first, group theory is simply the mathematical study of symmetry, operations, and patterns. Whenever you flip a mattress, rotate a Rubik's cube, or look at a clock where \(11 + 2 = 1\), you are already using group theory in everyday life!

In this chapter from A2 2 Section D (Discrete and Decision Mathematics), we will explore the fundamental building blocks of groups: the four foundational axioms, Cayley tables, orders of elements, subgroups, Lagrange's Theorem, and isomorphisms. Don't worry if this seems tricky at first — we will break down every concept step by step!

Did you know? Group theory was developed in the 19th century by the brilliant young mathematician Évariste Galois to solve a centuries-old puzzle: why there is no general formula to solve polynomial equations of degree 5 or higher!

1. What is a Group? The Four Golden Axioms

A group is a mathematical structure consisting of a set \(S\) combined with a rule or operation (denoted by \(*\)), written as \((S, *)\). For a system \((S, *)\) to qualify as a group, it must strictly satisfy four core axioms.

Memory Aid (Mnemonic): Remember the word CAII (or "Cool Animals In Ice"):
• Closure
• Associativity
• Identity
• Inverse

1. Closure

If you take any two elements in the set and combine them using the operation, the result must also be an element in the same set.
Formal definition: For all \(a, b \in S\), \(a * b \in S\).
Analogy: Imagine a closed room of dancers. If two dancers interact, the resulting person must still be inside the room, not suddenly outside!

2. Associativity

When combining three elements in order, the grouping (where you put the brackets) does not change the final outcome.
Formal definition: For all \(a, b, c \in S\), \((a * b) * c = a * (b * c)\).
Example: Normal addition is associative because \((2 + 3) + 4 = 5 + 4 = 9\) and \(2 + (3 + 4) = 2 + 7 = 9\). Note: Normal subtraction is not associative because \((8 - 3) - 2 = 3\), but \(8 - (3 - 2) = 7\).

3. Identity Element

There must be one special "neutral" element in the set (usually called \(e\)) that leaves every other element completely unchanged when combined with it.
Formal definition: There exists an element \(e \in S\) such that for all \(a \in S\), \(a * e = e * a = a\).
Example: Under addition, \(0\) is the identity because \(a + 0 = 0 + a = a\). Under multiplication, \(1\) is the identity because \(a \times 1 = 1 \times a = a\).

4. Inverses

Every single element in the set must have a corresponding "undo" partner in the set. Combining an element with its inverse brings you right back to the identity element.
Formal definition: For every \(a \in S\), there exists an element \(a^{-1} \in S\) such that \(a * a^{-1} = a^{-1} * a = e\).
Example: Under addition with identity \(0\), the inverse of \(5\) is \(-5\) because \(5 + (-5) = 0\).

Self-Inverse Elements: An element \(a\) is called self-inverse if \(a * a = e\), which means \(a = a^{-1}\). Notice that the identity element \(e\) is always self-inverse because \(e * e = e\).

2. Abelian (Commutative) Groups

In general groups, the order of operation matters: \(a * b\) does not always equal \(b * a\). However, if the order never matters, the group is given a special name.

A group \((G, *)\) is called Abelian (or commutative) if for all elements \(a, b \in G\):
\(a * b = b * a\)

Key Takeaway: All groups have closure, associativity, identity, and inverses. If they also have commutativity, they are Abelian!

3. Cayley Tables (Group Tables)

For finite groups (groups with a countable number of elements), we can display all possible combinations using a grid called a Cayley Table (or group table).

How to Read and Construct a Cayley Table

• The row header represents the first element \(a\), and the column header represents the second element \(b\).
• The entry at row \(a\) and column \(b\) is the result \(a * b\).

Crucial Features to Look for in a Cayley Table:

• The Identity Element: Look for the row and column that look identical to the main header row and column. The element heading that row/column is the identity \(e\).
• Finding Inverses: To find the inverse of an element \(x\), scan across row \(x\) until you find the identity \(e\). The element at the top of that column is \(x^{-1}\).
• Checking for Abelian Groups: If a Cayley table is completely symmetrical across the leading diagonal (from top-left to bottom-right), the group is Abelian.
• The Latin Square Property (Sudoku Rule): In every valid group table, each element of the group must appear exactly once in every row and exactly once in every column. No duplicates, no omissions!

4. The Order of a Group and Order of an Element

The word order has two distinct meanings in group theory. Make sure not to confuse them!

1. Order of a Group, \(|G|\) or \(o(G)\)

The order of a group is simply the total number of elements in the set \(G\).
Example: If \(G = \{e, a, b, c\}\), then the order of the group is \(|G| = 4\).

2. Order of an Element, \(o(a)\)

The order of an element \(a \in G\) is the smallest positive integer \(n\) such that combining \(a\) with itself \(n\) times gives the identity element \(e\):
\(a^n = \underbrace{a * a * \dots * a}_{n \text{ times}} = e\)

Important Points about Element Orders:
• The identity element \(e\) is the only element with an order of \(1\) because \(e^1 = e\).
• Any self-inverse element (where \(a \neq e\) and \(a^2 = e\)) has an order of \(2\).
• In additive notation (like modular arithmetic addition), \(a^n\) means adding \(a\) to itself \(n\) times: \(n \times a = 0 \pmod m\).

Step-by-Step Example: Find the order of each element in the group \((\{0, 1, 2, 3\}, +_4)\) (addition modulo 4).
• The identity element is \(0\).
• Order of \(0\): \(0^1 = 0 \implies o(0) = 1\).
• Order of \(1\): \(1 \neq 0\); \(1 + 1 = 2 \neq 0\); \(1 + 1 + 1 = 3 \neq 0\); \(1 + 1 + 1 + 1 = 4 \equiv 0 \pmod 4\). So, \(o(1) = 4\).
• Order of \(2\): \(2 \neq 0\); \(2 + 2 = 4 \equiv 0 \pmod 4\). So, \(o(2) = 2\).
• Order of \(3\): \(3 \neq 0\); \(3 + 3 = 6 \equiv 2\); \(3 + 3 + 3 = 9 \equiv 1\); \(3 + 3 + 3 + 3 = 12 \equiv 0 \pmod 4\). So, \(o(3) = 4\).

5. Cyclic Groups and Generators

A group \(G\) is called cyclic if every single element in the group can be generated by repeatedly combining one single element (called a generator, \(g\)) with itself.

We write this as \(G = \langle g \rangle = \{g^1, g^2, g^3, \dots, g^n = e\}\).
• A finite group of order \(n\) is cyclic if and only if it contains at least one element of order \(n\).
• Every cyclic group is automatically Abelian!

Example: In the group \((\{0, 1, 2, 3\}, +_4)\), the element \(1\) has order \(4\). Since the order of \(1\) equals the order of the group (\(4\)), the group is cyclic, and \(1\) is a generator. (Notice that \(3\) also has order \(4\), so \(3\) is another generator!)

6. Subgroups and Lagrange's Theorem

What is a Subgroup?

A subgroup \(H\) is a subset of a group \(G\) (written \(H \le G\)) that is itself a group under the exact same operation.

Every group \(G\) with order \(|G| > 1\) has at least two trivial/standard subgroups:
• The group itself: \(G\)
• The identity subgroup: \(\{e\}\)
Any subgroup other than \(G\) itself is called a proper subgroup.

Lagrange's Theorem (A Cornerstone of Group Theory!)

Statement: If \(G\) is a finite group and \(H\) is a subgroup of \(G\), then the order of \(H\) must divide exactly into the order of \(G\).
In symbols: \(\frac{|G|}{|H|}\) is an integer.

Why is Lagrange's Theorem So Useful?

1. Finding Possible Subgroup Sizes:
If a group has order \(12\), the only possible orders for its subgroups are the factors of \(12\): namely \(1, 2, 3, 4, 6\), and \(12\). A group of order \(12\) can never have a subgroup of order \(5\) or \(7\)!

2. Element Orders Must Divide the Group Order:
Since the elements generated by \(a\) form a cyclic subgroup \(\langle a \rangle\) of size \(o(a)\), Lagrange's theorem guarantees that:
The order of every element in a finite group must divide the order of the group!
\(o(a) \text{ divides } |G|\)

3. Groups of Prime Order:
If the order of a group \(|G| = p\) where \(p\) is a prime number (e.g., \(2, 3, 5, 7, 11\)):
• Its only divisors are \(1\) and \(p\).
• Every non-identity element must have order \(p\).
• Therefore, every group of prime order is cyclic and Abelian!

Common Mistake to Avoid: The converse of Lagrange's Theorem is not always true! Just because a number \(k\) divides \(|G|\) does not automatically guarantee that a subgroup of order \(k\) must exist.

7. Isomorphism: When Are Two Groups "The Same"?

Sometimes two groups look completely different on the surface (one might use letters and geometric rotations, while another uses numbers under multiplication), but mathematically they have the exact same underlying structure. These groups are called isomorphic (written \(G \cong H\)).

Conditions for Two Groups to Be Isomorphic

For two groups \(G\) and \(H\) to be isomorphic, there must be a one-to-one correspondence (bijection) between their elements that preserves the group operation: \(\phi(a * b) = \phi(a) \circ \phi(b)\).

How to Prove Two Groups are NOT Isomorphic (Exam Strategy):

To show two groups are not isomorphic, simply find one structural property that they do not share. Check these in order:
1. Different Orders: Do they have the same number of elements? If \(|G| \neq |H|\), they cannot be isomorphic.
2. Abelian vs Non-Abelian: Is one group commutative while the other is not?
3. Cyclic vs Non-Cyclic: Is one group cyclic and the other non-cyclic?
4. Matching Orders of Elements: Count the orders of all elements in both groups. For example, if group \(G\) has three elements of order \(2\), but group \(H\) only has one element of order \(2\), they cannot be isomorphic!

Classic Example: Groups of Order 4
There are only two distinct group structures of order 4:
• The Cyclic Group \(C_4\) (e.g., \((\{0, 1, 2, 3\}, +_4)\)): Has one element of order 1, one element of order 2, and two elements of order 4.
• The Klein 4-Group \(V_4\) (e.g., symmetries of a non-square rectangle): Has one element of order 1, and three elements of order 2 (every non-identity element is self-inverse!).
Because their element orders do not match, \(C_4\) and \(V_4\) are not isomorphic!

Quick Review Summary

• Group Definition (CAII): A set and operation satisfying Closure, Associativity, Identity (\(e\)), and Inverses (\(a^{-1}\)).
• Abelian: Commutative group where \(a * b = b * a\) (symmetrical Cayley table).
• Cayley Table: Sudoku-like grid showing all combinations; each element appears once per row and column.
• Order of Element: Smallest integer \(n \ge 1\) such that \(a^n = e\).
• Cyclic Group: Generated by a single element; contains an element whose order equals the group order.
• Lagrange's Theorem: Subgroup order \(|H|\) and element orders \(o(a)\) must divide group order \(|G|\).
• Isomorphism (\(\cong\)): Structural identicalness between two groups with identical patterns of element orders.