S. D. V. Stephens

notes / Studies in Algebra and Group Theory / chapter 1: Sets and Groups

2 Cardinality, Subgroups and Cyclic Groups

· Denis Auroux

Original Professor Auroux’s handwritten notes (PDF), behind a password for now:

Set theory interlude

Recall that a map of sets is

  • injective if , (or: ). Write .
  • surjective if , such that . Write .
  • a bijection if both hold.

Definition 2.1. Say two sets have the same cardinality if there exists a bijection , and write . If there exists an injection , then write .

This notation is legit thanks to the Schröder–Bernstein theorem:

Theorem 2.2 (Schröder–Bernstein). If there exist injective maps and , then .

(See Halmos, Naive Set Theory, p. 88 for a proof: build a bijection by using on a subset of and on the rest.)

Example 2.3. , , all have the same cardinality; these are called countably infinite.

E.g. construct a bijection by setting For , first understand how to enumerate = pairs of integers.

On the other hand, is uncountable, using Cantor’s diagonal argument: no map can be surjective, because: write the decimal or binary expansions Then let , where we choose for each (going down the diagonal). Looking at the -th digit, for all , so can’t be surjective.

The same argument shows there are arbitrarily large cardinals: given a set , let It is in bijection with , via , with inverse If is finite, , then . What if is infinite?

Theorem 2.4. If is infinite, then .

Proof ((Cantor)). Given , let . Assume for some . Then iff , a contradiction. So , and there is no surjection. ∎

(This is just the diagonal argument again. Do you see how?)

Back to groups

Recall:

Definition 2.5. A group is a set with an operation , , such that

  1. identity: such that , ;
  2. inverse: , such that ;
  3. associativity: , .

We’ve seen various examples last time.

Products

Given two groups , the product group is with composition law .

  • If are finite, of order and , then is a finite group of order .
  • Similarly for a product of groups. Example: , with . (Similarly , , with componentwise addition.)
  • Given infinitely many groups , there are two different notions:
    • the direct product ;
    • the direct sum .

Example 2.6. Consider , and denote by . Then , the formal power series (with addition), and , the polynomials .

Subgroups

Definition 2.7. A subgroup of a group is a non-empty(!) subset which is closed under composition () and inversion (). These conditions imply . So (with the same operation) is also a group.

Say is a proper subgroup if .

Example 2.8.

  • .
  • .
  • , the trivial subgroup.
  • .
  • .

Proposition 2.9. If are two subgroups, then is also a subgroup.

Proof.

  • , so it is nonempty.
  • If , then and , so .
  • Likewise for inverses.

∎

Similarly for more than two subgroups (even infinitely many). (However, is almost never a subgroup. Why?)

Homomorphisms

Definition 2.10. Given two groups , a homomorphism is a map which respects the composition law: , .

(This implies and .)

Remark. A pedantic way to state is by a commutative diagram: “Commutative diagram” means that the two paths from to give the same map: it doesn’t matter if we multiply first or apply first.

  • An isomorphism is a bijective homomorphism (two isomorphic groups are “secretly the same”).
  • An automorphism is an isomorphism .

Example 2.11 (Isomorphisms). All groups of order 2 are isomorphic! , because the multiplication table is always

  • , and .
  • symmetries of (permutations of the vertices).

Example 2.12 (Homomorphisms).

  • , (the remainder of Euclidean division by ).
  • If , similarly (e.g. : last 2 digits last digit).
  • The determinant ().
Notes not reached in this lecture, covered at the start of Lecture 3

Definition 2.13 (Kernel). The kernel of a group homomorphism is

Proposition 2.14.

  • is a subgroup of (check that it contains , products, inverses).
  • is injective iff (using: ).

Definition 2.15 (Image). The image of a group homomorphism is This is a subgroup of . is surjective iff .

Remark. If is injective, then is isomorphic to the subgroup . (The isomorphism is given by the map , .)

Subgroups of

Given , is a subgroup.

Proposition 2.16. All nontrivial subgroups of are of this form.

Proof. This follows from the Euclidean algorithm. Given a nontrivial subgroup , there exists such that . Let be the smallest positive element of . Given any , for some and (the remainder). Since and , . Since , by definition of , must be zero. Hence ; so , and conversely , so . ∎

So every subgroup of is generated by a single element , in the sense we will now explain.

Question 2.17. Given a (nonempty) subset , what is the smallest subgroup of which contains ? This is denoted and called the subgroup generated by .

Answer: look at all subgroups of which contain (there’s at least itself!) and take their intersection:

More useful answer: must contain all products of elements of and their inverses, and these form a subgroup of , so

Definition 2.18. A group is cyclic if it is generated by a single element.

(Examples: , . These are in fact the only cyclic groups up to isomorphism.)

Example 2.19. can be generated by two elements! [Exercise! Fairly hard without a hint.]

Example 2.20. Let be any element in a group . Then the map , is a homomorphism, with image , the cyclic subgroup generated by .

Definition 2.21. The order of is the smallest positive such that , if it exists. Else, say has infinite order.

Note. Do not confuse the order of with the order of (). Though, .

If has infinite order, then the powers of are all distinct, is injective, and is isomorphic to . If has finite order , then , and is isomorphic to . (This completes the classification of cyclic groups, by the way.)

Example 2.22. (observe: has order 6, so it generates).

Similarly, . But : for all , versus .