State Lagrange's Theorem with an example. Also explain Permutation and Symmetric Group.

Introduction

In the field of Discrete Structure, Lagrange's Theorem, Permutation and Symmetric Group are fundamental concepts. They are used to understand the structure and properties of groups, which are sets equipped with an operation that combines any two of its elements to form a third element.

Lagrange's Theorem

Lagrange's Theorem is a statement in group theory that deals with the number of elements in a finite group and its subgroups. The theorem states that the order (number of elements) of every finite subgroup of a group divides the order of the group.

Explanation

Let's denote the order of a group G as |G| and the order of a subgroup H as |H|. According to Lagrange's Theorem, if G is a finite group and H is a subgroup of G, then |H| divides |G|. This can be written mathematically as:

|G| = k * |H|

where k is a non-negative integer.

Example

Consider the group G = {e, a, a^2, a^3} under multiplication, where 'a' is a primitive root of unity and 'e' is the identity element. The order of G is |G| = 4.

Now, consider a subgroup H = {e, a^2}. The order of H is |H| = 2.

According to Lagrange's Theorem, |H| should divide |G|. Indeed, 4 = 2 * 2, so the theorem holds.

Permutation

A permutation of a set is an arrangement of its elements into a sequence or linear order. The number of permutations of a set of n elements is given by n!.

Example

Consider the set S = {1, 2, 3}. The number of permutations of S is 3! = 3 * 2 * 1 = 6. The permutations are:

1. {1, 2, 3}
2. {1, 3, 2}
3. {2, 1, 3}
4. {2, 3, 1}
5. {3, 1, 2}
6. {3, 2, 1}

Symmetric Group

The symmetric group on a set is the group consisting of all permutations of the set. The order of the symmetric group on a set of n elements is n!.

Example

Consider the set S = {1, 2}. The symmetric group on S, denoted by S_2, consists of the permutations:

1. {1, 2}
2. {2, 1}

The order of S_2 is 2! = 2.

Comparison

Conclusion

Understanding Lagrange's Theorem, Permutation and Symmetric Group is crucial in Discrete Structure. These concepts provide insights into the structure and properties of groups, which are fundamental objects in many areas of mathematics.

Summary

Lagrange's Theorem states that the order of every finite subgroup of a group divides the order of the group. Permutation is an arrangement of elements in a set, and the number of permutations of a set of n elements is n!. The symmetric group on a set is the group consisting of all permutations of the set, and its order is n!.

Analogy

Lagrange's Theorem can be compared to dividing a cake into equal-sized pieces. Permutation is like arranging different flavors of ice cream in a cone. The symmetric group is like a group of friends swapping seats at a dinner table.