Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

440 ALGEBRAIC SYSTEMS [APP. B

MAP(A), PERM(A), and AUT(A)

LetAbe a nonempty set. The collection MAP(A) of all functions (mappings)f:A→Ais a semigroup
under composition of functions; it is not a group since some functions may have no inverses. However, the
subsemigroup PERM(A) of all one-to-one correspondences ofAwith itself (calledpermutationsof A) is a group
under composition of functions.
Furthermore, supposeAcontains some type of geometric or algebraic structure; for example,Amay be the
set of vertices of a graph, orAmay be an ordered set or a semigroup. Then the set AUT(A) of all isomorphisms
ofAwith itself (calledautomorphismsof A) is also a group under compositions of functions.

B.5Subgroups, Normal Subgroups, and Homomorphisms

LetHbe a subset of a groupG. ThenHis called asubgroupofGifHitself is a group under the operation

ofG. Simple criteria to determine subgroups follow.

Proposition B.5:A subsetHof a groupGis a subgroup ofGif:

(i) The identity elemente∈H.

(ii) His closed under the operation ofG, i.e. ifa,b∈H, thenab∈H.

(iii) His closed under inverses, that is, ifa∈H, thena−^1 ∈H.

Every groupGhas the subgroups {e} andGitself. Any other subgroup ofGis called anontrivial subgroup.

Cosets

SupposeHis a subgroup ofGanda∈G. Then the set

Ha={ha|h∈H}

is called aright cosetofH. (Analogously,aHis called aleft cosetofH.) We have the following important
results (proved in Problems B.13 and B.15).

Theorem B.6: LetHbe a subgroup of a groupG. Then the right cosetsHaform a partition ofG.

Theorem B.7 (Lagrange): LetHbe a subgroup of a finite groupG. Then the order ofHdivides the order ofG.

The number of right cosets ofHinG, called the index ofHinG, is equal to the number of left cosets ofH

inG; and both numbers are equal to|G|divided by|H|.

Normal Subgroups
The following definition applies.
Definition B.2:A subgroupHofGis anormalsubgroup ifa−^1 Ha⊆H, for everya∈G, or, equivalently,
ifaH=Ha, i.e., if the right and left cosets coincide.

Note that every subgroup of an abelian group is normal.

The importance of normal subgroups comes from the following result (proved in Problem B.17).

Theorem B.8: LetHbe a normal subgroup of a groupG. Then the cosets ofHform a group under coset
multiplication:
(aH)(bH)=abH

This group is called thequotient groupand is denoted by G/H.

Suppose the operation inGis addition or, in other words,Gis written additively. Then the cosets of a
subgroupHofGare of the forma+H. Moreover, ifHis a normal subgroup ofG, then the cosets form a group
under coset addition, that is,
(a+H)+(b+H)=(a+b)+H