Group Theory: Axioms, Lagrange's Theorem, and Subgroups

Welcome to lesson 1.7 of the Discrete Mathematics module. In our previous lesson, we formalized the properties of functions, exploring injectivity, surjectivity, and bijectivity, and saw how to compose functions. You might recall that function composition is an operation that takes two functions and produces a new one. This leads to a natural question: what happens when we study a set of elements (like functions) together with a specific operation (like composition)?

Today, we delve into the world of Algebraic Structures, which are sets equipped with one or more operations that obey certain rules or "axioms." This is a cornerstone of abstract algebra and has profound implications across computer science, from cryptography and coding theory to the study of algorithms. Our specific goal is to master the concepts of groups, subgroups, and cosets, and to apply the powerful Lagrange's theorem to analyze their properties.

1. What is an Algebraic Structure?

At its core, an algebraic structure is a non-empty set $S$ combined with one or more binary operations. A binary operation $*$ on a set $S$ is simply a rule that assigns to each ordered pair of elements $(a, b)$ from $S$ a unique element $a * b$ .

For example, addition + is a binary operation on the set of integers $Z$ , because for any two integers $a$ and $b$ , their sum $a + b$ is also a unique integer.

We can classify algebraic structures based on the properties their operations satisfy. A simple but important structure is the monoid. A set $S$ with a binary operation $*$ , denoted $(S, *)$ , is a monoid if it satisfies two axioms:

Associativity: For all $a, b, c \in S$ , $(a * b) * c = a * (b * c)$ .
Identity Element: There exists an element $e \in S$ such that for every $a \in S$ , $a * e = e * a = a$ .

For example, $(Z, +)$ is a monoid with identity element 0. The set of non-negative integers $(N_{0}, +)$ is also a monoid with identity 0. The set of strings over an alphabet $Σ$ , with the operation of string concatenation, is a monoid where the identity element is the empty string.

2. Groups: The Four Axioms

A group is a monoid with one additional property: the existence of inverses. A group $(G, *)$ is a set $G$ with a binary operation $*$ that satisfies the following four axioms:

G1: Closure. For all $a, b \in G$ , the result of the operation, $a * b$ , is also in $G$ . (This is implicit in the definition of a binary operation on a set, but is always stated for clarity).
G2: Associativity. For all $a, b, c \in G$ , $(a * b) * c = a * (b * c)$ .
G3: Identity Element. There exists an element $e \in G$ such that for every $a \in G$ , $a * e = e * a = a$ . This identity element is unique for the group.
G4: Inverse Element. For each element $a \in G$ , there exists an element $a^{- 1} \in G$ such that $a * a^{- 1} = a^{- 1} * a = e$ . This inverse is unique for each element $a$ .

If a group also satisfies the commutative property ( $a * b = b * a$ for all $a, b \in G$ ), it is called an Abelian group.

Key Examples for GATE:

$(Z, +)$ : The set of integers under addition is an Abelian group. The identity is 0, and the inverse of $a$ is $- a$ .
$(Z_{n}, +_{n})$ : The set of integers modulo $n$ , ${0, 1, ..., n - 1}$ , under addition modulo $n$ . This is a finite Abelian group, crucial for cryptography and hashing. For example, in $(Z_{4}, +_{4})$ , the inverse of 3 is 1, because $(3 + 1) (mod 4) = 0$ .
The Symmetric Group: From our last lesson, the set of all bijective functions (permutations) on a set $S$ , with the operation of function composition, forms a group. This group is generally not Abelian.

3. Subgroups

Often, we find smaller groups living inside larger ones. This gives us the concept of a subgroup.

A subset $H$ of a group $G$ is a subgroup of $G$ if $H$ is also a group under the same operation as $G$ . To verify this, we don't need to check all four axioms again. A simpler test suffices. For a non-empty subset $H$ of $G$ , $H$ is a subgroup if and only if:

$H$ is closed under the operation: for all $a, b \in H$ , $a * b \in H$ .
$H$ is closed under inverses: for all $a \in H$ , $a^{- 1} \in H$ .

This is often combined into a single condition: $H$ is a subgroup if and only if for all $a, b \in H$ , $a * b^{- 1} \in H$ .

Let's watch a video that formalizes these definitions and provides some important foundational theorems.

Group Theory | Subgroup | Subgroup Theorems | Discrete Mathematics

This video by Dr. Gajendra Purohit covers the definition of a subgroup, distinguishes between proper and improper subgroups, and discusses some essential theorems related to them.

Please focus on the following segments: Definition of a Subgroup: Watch from this section to understand the formal definition. It clarifies that a subgroup must be a group with respect to the same operation as the parent group. Proper and Improper Subgroups: The part from this timestamp explains trivial (or improper) subgroups—which are the group G itself and the group containing only the identity element \{e\}—and non-trivial (or proper) subgroups. An Important Remark: Pay close attention to the example discussed from here. It highlights that a subset forming a group under a different operation is not a subgroup. Key Theorems: Finally, watch the explanation of the three theorems starting from this point. The key takeaways are that a subgroup's identity and its elements' inverses are the same as in the parent group.

As the video explained, every group $G$ has at least two subgroups: $G$ itself and the trivial subgroup ${e}$ . Any other subgroup is called a proper subgroup. For example, the set of even integers $(2 Z, +)$ is a proper subgroup of $(Z, +)$ .

4. Lagrange's Theorem, Cosets, and the Size of Subgroups

For finite groups, there is a remarkable relationship between the size (or order) of a group and the order of its subgroups. This relationship is given by Lagrange's Theorem, and its proof relies on the concept of cosets.

A coset is a way of partitioning a group based on one of its subgroups. Let $H$ be a subgroup of $G$ , and let $g$ be an element of $G$ .

The left coset of $H$ with respect to $g$ is the set $g H = {g h ∣ h \in H}$ .
The right coset of $H$ with respect to $g$ is the set $H g = {h g ∣ h \in H}$ .

Crucially, the cosets of a subgroup $H$ partition the entire group $G$ . This means every element of $G$ belongs to exactly one coset of $H$ . Furthermore, all cosets have the same size as $H$ . This insight is the key to proving Lagrange's Theorem.

The following video from Socratica provides one of the clearest explanations available.

Cosets and Lagrange’s Theorem - The Size of Subgroups (Abstract Algebra)

This video brilliantly explains and proves Lagrange's Theorem by building up the concept of cosets. It's a must-watch to develop a deep intuition for this topic.

Please watch these key segments: Statement of the Theorem: Begin by watching from this part, which introduces subgroups and clearly states Lagrange's Theorem: If H is a subgroup of a finite group G, then the order of H divides the order of G. Application and Limitation: The section from here shows how the theorem restricts possible subgroup sizes. Critically, it explains that the converse is not true: just because a number divides the order of a group does not guarantee a subgroup of that size exists. The example of group A_4 is a classic counter-example often cited in exams. Proof via Cosets: The core of the lesson is from this section. Follow the argument carefully: It defines left cosets (gH). It proves that any two left cosets are either identical or completely disjoint (non-overlapping). It proves that all left cosets have the same size as the subgroup H. It concludes that the group G is partitioned into a number of disjoint cosets, each of size |H|. Therefore, |G| must be a multiple of |H|.

Let's formalize the result from the video.

Lagrange's Theorem: Let $G$ be a finite group and $H$ be a subgroup of $G$ . Then the order of $H$ divides the order of $G$ .
$∣ H ∣ divides ∣ G ∣$
The number of distinct left cosets of $H$ in $G$ is called the index of $H$ in $G$ , denoted $[G : H]$ . The theorem can be stated as:
$∣ G ∣ = ∣ H ∣ \times [G : H]$

Applying Lagrange's Theorem (GATE-Style)

This theorem is extremely useful for answering GATE questions quickly.

Example 1: A group $G$ has order 77. What are the possible orders of its subgroups?

The divisors of 77 are 1, 7, 11, and 77.
According to Lagrange's theorem, any subgroup must have an order that divides 77.
Therefore, the only possible orders for subgroups of $G$ are 1, 7, 11, or 77. (These correspond to the trivial subgroup, subgroups of order 7 and 11, and the group itself).

Example 2: Can a group of order 30 have a subgroup of order 7?

No. Because 7 does not divide 30, Lagrange's theorem forbids the existence of a subgroup of order 7.

Remember the crucial warning from the video: the converse is false. A group of order 12 might not have a subgroup of order 6 (the group $A_{4}$ is the proof). However, if the order of a group is a prime number $p$ , then it can only have subgroups of order 1 and $p$ . This means its only subgroups are the trivial one and the group itself.

Conclusion

In this lesson, we formalized the notion of an algebraic structure and focused on the properties of groups. You learned to apply the four group axioms, identify subgroups, and understand the powerful implications of Lagrange's theorem.

Here are the key takeaways:

An algebraic structure is a set with a binary operation satisfying certain axioms.
A group $(G, *)$ satisfies closure, associativity, identity, and inverse properties.
A subgroup is a subset of a group that is also a group under the same operation.
Lagrange's Theorem states that for a finite group, the order of any subgroup must divide the order of the group.
This theorem is proven by showing that the cosets of a subgroup form a partition of the group into equal-sized blocks.
The converse of Lagrange's Theorem is not true, a common pitfall in questions.

We have now covered the essentials of logic, sets, relations, functions, and basic algebraic structures. In our final lesson of this module, we will switch gears to Combinatorics, where we will learn systematic methods for counting arrangements and selections, a skill vital for algorithm analysis and probability.