Groups

Question 1

What is binary operation * in a set S?

Answer 1

A function
∗:S×S→S
(a,b)↦a∗b

Question 2

When is a binary operation ∗ on a set S associative?

Answer 2

When a∗(b∗c) = (a∗b)∗c for all a,b,c∈S.

Question 3

What is an identity element in a set S?

Answer 3

An element e∈S s.t e∗a = a = a∗e for all a∈S.

Question 4

Let ∗ be a binary operation on a non-empty set S. Prove that if there is an identity e∈S, then it is unique.

Answer 4

Let e₁, e₂ be identity elements. Then e₁∗e₂ = e₂ as e₁ an identity and e₁∗e₂ = e₁ as e₂ an identity so e₁ = e₂.

Question 5

Let ∗ be a binary operation on a set S, with identity e. Take a,b∈S, what will make b an inverse of a?

Answer 5

If a∗b = e = b∗a.

Question 6

Let ∗ be an associative binary operation on a set S, with identity e. Take a∈S. Prove that if a has an inverse, then the inverse is unique.

Answer 6

Let b,b′ be inverses of a. Then b′∗(a∗b) = b′∗e = b′and (b′∗a)∗b = e∗b = b, but ∗ is associative so these are equal, so b = b′.

Question 7

Let ∗ be a binary operation on a set S. Let T be a subset of S. We say that T is closed under ∗ if…

Answer 7

∗ : T×T→T is a binary operation on T.

Question 8

A group is a set G together with a binary operation ∗ on G such that… [define the group axioms]

Answer 8

(i) ∗ is associative;
(ii) there is an identity;
(iii) each element of G has an inverse.

Question 9

Let G be a group. Let g, g₁ ,g₂ ,g₃∈G, let m,n∈Z. Then prove:

(i) (g₁g₂)⁻¹ = g₂⁻¹g₁⁻¹;
(ii) (gⁿ)⁻¹ = (g⁻¹)ⁿ;
(iii) gᵐgⁿ = gᵐ⁺ⁿ;
(iv) (gᵐ)ⁿ=gᵐⁿ;
(v) if g₁g₂=g₁g₃, then g₂ = g₃ (‘cancellation on the left’);
(vi) if g₁g₂ = g₃g₂, then g₁ = g₃ (‘cancellation on the right’).

Answer 9

Proof left as an exercise to the flashcarder.

Question 10

What makes a group (G,∗) Abelian?

Answer 10

If g∗g′ = g′∗g for all g,g′∈G — that is, if the binary operation ∗ is commutative.

Question 11

What makes a group cyclic?

Answer 11

If there is some g∈G such that G = {gⁿ : n∈Z}.

Question 12

Why is a cyclic group Abelian?

Answer 12

gⁿgᵐ = gⁿ⁺ᵐ = gᵐ⁺ⁿ = gᵐgⁿ

Question 13

What is the nth cyclic group Cₙ?

Answer 13

{e,g,g²,…,gⁿ⁻¹}, where gⁿ=e, and for 0 ≤ i,j ≤ n−1 gᶦ∗gʲ =
{gᶦ⁺ʲ if i+j < n
{gᶦ⁺ʲ⁻ⁿ if i+j ≥ n

Question 14

Let Pₙ be a regular n-gon in the plane (here n≥3). For n≥3, define the nth dihedral group D₂ₙ to be…

Answer 14

The set of isometries of the plane that send Pₙ to Pₙ. These isometries are called symmetries of Pₙ.

Question 15

Let Pₙ be a regular n-gon in the plane. Write r for rotation anticlockwise by 2π/n about the centre of Pₙ, and s for reflection in an axis of Pₙ. Prove that the symmetries of Pₙ are e, r, r², . . . , rⁿ⁻¹, s, rs, r²s, . . . , rⁿ⁻¹s.

Answer 15

Label the vertices of Pₙ anticlockwise as 1, 2, . . . ,n. Let f be a symmetry of Pₙ, and consider f(Pₙ).
Case 1: The vertices of f(Pₙ) are numbered 1, 2, . . . , n anticlockwise. Say vertex 1 has moved to position k (where 1≤k≤n. Then applying(r⁻¹)ᵏ⁻¹ will return vertex 1 to position 1, and hence all vertices to their starting positions. So (r⁻¹)ᵏ⁻¹f=e, so f=rᵏ⁻¹.
Case 2: The vertices of f(Pₙ) are numbered 1, 2, . . . , n clockwise. Then fs keeps the vertices in anticlockwise order, so as in Case 1 we have fs = rᵏ⁻¹ for some k (1≤k≤n), and then f = fs² = rᵏ⁻¹s. So the symmetries of Pn are contained in the list e, r, r², . . . , rⁿ⁻¹, s, rs, r²s, . . . , rⁿ⁻¹s. Now e, r, r², . . . ,rⁿ⁻¹ each send vertex 1 to a different position, and hence are all distinct. Similarly, s, rs, r²s, . . . , rⁿ⁻¹s are all distinct. The former collection leave the vertices in anticlockwise order, whereas the latter switch them to clockwise, so in fact all 2n symmetries are distinct.

Question 16

Given groups (G,∗𝓰) and (H,∗ₕ), we define their product group (or product) to be…

Answer 16

(G×H,∗) with ∗ defined by (g₁,h₁) ∗ (g₂,h₂) = (g₁ ∗𝓰 g₂, h₁ ∗ₕ h₂).

Question 17

Prove that the operation * defined by (g₁,h₁) ∗ (g₂,h₂) = (g₁ ∗𝓰 g₂, h₁ ∗ₕ h₂) where (G,∗𝓰) and (H,∗ₕ) are groups makes (G×H,∗) into a group.

Answer 17

• closure: since ∗G and ∗H are binary operations on G and H respectively, we have (g₁ ∗𝓰 g₂, h₁ ∗ₕ h₂)∈G×H for all g₁, g₂∈G and h₁, h₂∈H.
• associativity: follows from the associativity of ∗𝓰 and ∗ₕ (exercise).
• identity: the identity element in (G×H, ∗) is e(𝓰 ₓ ₕ) = (e𝓰, eₕ).
• inverses: given (g, h)∈G×H, we have (g, h)⁻¹ = (g⁻¹,h⁻¹)∈G×H.

Question 18

What is the order of a group (G,∗), and when is G a finite group?

Answer 18

The order is the cardinality |G| of the set G. If |G| is finite, then we say that G is a finite group.

Question 19

Let G = {g₁,g₂,…,gₙ} be a finite group. The Cayley table, or group table, of G is…

Answer 19

A square n×n grid in which the entry in row i and column j is gᶦ∗gʲ.

Question 20

Prove that a Cayley table is a Latin square: each element appears exactly once in each row and in each column.

Answer 20

Let G be a finite group, take g∈G. Define f𝓰 : G→G g′↦gg′. This is a bijection (its inverse is g′↦g⁻¹g′).
So the entries in the row corresponding to g are precisely the elements of G in some order, each appearing exactly once.
Similarly for columns.

Question 21

Let (G,∗) be a group. We say that a subset H⊆G is a subgroup (H≤G) if…

Answer 21

The restriction of ∗ to H makes H into a group, that is,
• H is closed under ∗ (if h₁,h₂∈H then h₁h₂∈H);
• H has an identity (e𝓰∈H);
• H contains inverses (if h∈H then h⁻¹∈H).

Question 22

Let G be a group, and take g∈G. We define the order of g, o(g), to be…
When does g have infinite order?

Answer 22

the smallest positive integer k such that gᵏ = e. If no such integer k exists, then we say that g has infinite order.

Question 23

Let (G,∗𝓰) and (H,∗ₕ) be groups. An isomorphism between G and H is…

Answer 23

A bijective map θ : G→H such that θ (g₁ ∗𝓰 g₂) = θ(g₁) ∗ₕ θ(g₂) for all g₁,g₂∈G. If such an isomorphism exists, then we say that G and H are isomorphic, and write G∼=H.

Question 24

What is a permutation of a set S?

Answer 24

A bijection S→S

Question 25

What is the set of permutations of a set S called?

Answer 25

Sym(S)

Question 26

What is shorthand for τ(σ(k))?

Answer 26

kστ

Question 27

Let S be a set. Prove that

(i) Sym(S) is a group under composition, called the symmetry group of S.
(ii) If |S|≥3, then Sym(S) is non-Abelian.
(iii) |Sₙ|=n!.

Answer 27

(i) Exercise. (ii) Let x₁, x₂, x₃ be three distinct elements of S. We seek to find two elements of Sym(S) that don’t commute. Define f: x₁↦x₂ x₂↦x₁ x↦x for other x and g: x₂↦x₃ x₃↦x₂ x↦x for other x. Then f,g∈Sym(S) and x₁gf = x₁f = x₂ while x₁fg = x₂g = x₃ so fg =/= gf.
(iii) To specify f∈Sₙ, we say what f does to each of 1, 2, … , n. There are n possibilities for 1f, and f is injective so there are n−1 possibilities for 2f, and so on.This gives n! possibilities for f.

Question 28

A permutation σ∈Sₙ is a cycle if there are distinct a₁, . . . ,aₖ∈{1,2,…,n} such that…
What is the name for this k-length cycle and how is it wriiten?

Answer 28

aᵢσ = aᵢ₊₁ for 1≤i≤k−1 and aₖσ = a₁ and xσ = x for x ∈/ {a₁,…,aₖ}. We call it a k-cycle, and this has order k. We write it as (a₁ a₂ … aₖ).

Question 29

The cycles (a₁… aₖ) and (b₁… bₗ) are disjoint if…

Answer 29

aᵢ =/= bⱼ for all i, j.

Question 30

Let α = (a₁… aₖ) and β = (b₁… bₗ) be disjoint cycles. Show that α and β commute.

Answer 30

We have
aᵢαβ = aᵢ₊₁β = aᵢ₊₁ for 1≤i≤k−1 and aᵢβα = aᵢα = aᵢ₊₁ for 1≤i≤k−1 and aₖαβ = a₁β = a₁ and aₖβα = aₖα = a₁. Similarly bⱼαβ = bⱼβα for 1≤j≤l, and for x ∈/ {a₁,…,aₖ,b₁,…,bₗ} we have xαβ = x = xβα. So αβ = βα.

Question 31

Show that every permutation in Sₙ can be written as a product of disjoint cycles. And that this product is unique up to cycling elements without cycles and permuting the order of the cycles.

Answer 31

Bottom of page 13.

[Two parts, existence and uniqueness]

Question 32

What is the cycle type for a given permutation σ∈Sₙ?

Answer 32

The list of lengths of the cycles in σ, e.g 
The permutation (1 5 3 9)(2 6)(4 7)∈S₉ has cycle type 4, 2, 2, 1.

Question 33

Let π∈Sₙ be written as π=σ₁σ₂···σₖ as a product of disjoint cycles. For 1≤i≤k, let lᵢ be the length of σᵢ. Then the order of π is lcm(l₁,…,lₖ). “cycle type determines order”. Prove this

Answer 33

Left as an exercise for the flashcarder.

Question 34

We say that two permutations σ,τ∈Sₙ are conjugate if…

Answer 34

There is some ρ∈Sₙ with σ=ρ⁻¹τρ.

Question 35

Let (a₁ a₂ … aₖ)be a cycle in Sₙ, and take σ∈Sₙ. Then σ⁻¹(a₁ a₂ … aₖ)σ= (a₁σ a₂σ … aₖσ). Prove it

Answer 35

Exercise (on Problem Sheet 2).

Question 36

Let σ,τ∈Sₙ. They are conjugate if and only if they have the same cycle type. Prove it

Answer 36

[There was double subscript so instead ᵇk₁ is used.]

(⇒) Assume that σ,τ are conjugate, so there is ρ∈Sₙ such that σ=ρ⁻¹τρ. Say τ=π₁···πᵣ where the πᵢ are disjoint cycles. By Lemma 11, ρ⁻¹πᵢρ is a cycle of the same length as πᵢ. But σ = ρ⁻¹τρ = ρ⁻¹π₁ρρ⁻¹π₂ρ···ρ⁻¹πᵣρ so σ has the same cycle type as τ.
(⇐) Assume that σ and τ have the same cycle type, say σ = (ᵃ1 … ᵃk₁)(ᵃk₁+1 … ᵃk₂)···(ᵃkₘ₋₁+1… ᵃkₘ) and τ = (ᵇ1… ᵇk₁)(ᵇk₁+1… ᵇk₂)···(ᵇkₘ₋₁+1… ᵇkₘ). Define ρ∈Sₙ as follows: define aᵢρ = bᵢ for 1≤i≤kₘ. Then, by Lemma 11, ρ⁻¹(ᵃ1… ᵃk₁)ρ = (ᵇ1… ᵇk₁) and so on, so ρ⁻¹σρ = τ, so σ and τ are conjugate.

{Note this is a proof only for Sₙ, this isn’t necessarily true for other groups}

Question 37

An n×n matrix is a permutation matrix if…

Answer 37

Each row and each column contains exactly one entry that is 1, with all other entries 0.

Question 38

Take σ∈Sₙ. We obtain a corresponding permutation matrix Pσ with i,j entry []

Answer 38

δᵢσ,ⱼ (Kronecker delta at iσ,j)

done by specifying that the nonzero entry in row i is a 1 in column iσ.

Question 39

If σ,τ∈Sₙ, then ᴾστ = ᴾσᴾτ. Prove it

Answer 39

The i,j entry of ᴾσᴾτ is
(ᴾσᴾτ)ᵢ,ⱼ = ⁿ∑ₖ₌₁ (ᴾσ)ᵢ,ₖ(ᴾτ)ₖ,ⱼ
(definition of matrix multiplication)
= ⁿ∑ₖ₌₁ (δᵢσₖ)(δₖτ,ⱼ) = δᵢστ,ⱼ = (ᴾστ)ᵢ,ⱼ.

(δᵢστ,ⱼ is Kronecker delta at iστ,j)

Question 40

If σ∈Sₙ is a transposition, then det(ᴾσ) = −1. Prove it

Answer 40

Say σ = (i j).Then ᴾσ is Iₙ with rows i and j swapped, so det(ᴾσ) = −det(Iₙ) = −1.

Question 41

A permutation is odd (resp.even) if…

Answer 41

It can be written as a product of an odd (resp. even) number of transpositions.

Question 42

Prove that:

(i) Any permutation in Sn can be written as a product of transpositions.
(ii) A permutation cannot be both even and odd.

Answer 42

(i) Any permutation in Sₙ can be written as a product of dis-joint cycles (Theorem 9), so we concentrate on an arbitrary cycle (a₁ a₂ … aₖ). We have (a₁ a₂ … aₖ) = (a₁ a₂)(a₁ a₃)···(a₁ aₖ).
(ii)Say σ = τ₁···τₖ where τ₁, … ,τₖ are transpositions. Then det(ᴾσ) = det(ᴾτ₁···ᴾτₖ) by Lemma 13
= det(ᴾτ₁)···det(ᴾτₖ) as det multiplicative
= (−1)ᵏ by Lemma 14.
So σ cannot be both even and odd.

Question 43

(i) A cycle is odd iff
(ii) A permutation is even iff
(iii) σ is even iff det(ᴾσ) =

Answer 43

(i) The cycle has even length.
(ii) The permutation’s cycle type has an even number of cycles of even length
(iii) det(ᴾσ) = 1

Question 44

Define Aₙ

Answer 44

Aₙ := {σ∈Sₙ : σ is even}, and is called the nth alternating group.

Question 45

Prove that

(i) Aₙ is a subgroup of Sₙ.
(ii) For n≥2, the order of Aₙ is (1/2)n!.
(iii) For n≥4, Aₙ is non-Abelian

Answer 45

(i) –Closure: Take σ,τ∈Aₙ, so σ and τ are even. Then det(ᴾσ) = det(ᴾτ) = 1 by Theorem 15, so det(ᴾστ) = det(ᴾσᴾτ) = det(ᴾσ) det(ᴾτ) = 1 (using Lemma13), so στ is even so στ∈Aₙ.
–Identity: Note that e (the identity permutation) is a product of 0 transpositions and hence even, so e∈Aₙ.
–Inverses: Take σ∈Aₙ. Then det(ᴾσᴾ[σ⁻¹]) = det(ᴾσ)det(ᴾ[σ⁻¹]) = det(ᴾ[σ⁻¹]), but also det(ᴾσᴾ[σ⁻¹]) = det(Iₙ)= 1, so σ⁻¹ is even so σ⁻¹∈Aₙ. So Aₙ≤Sₙ.
(ii) Define f:Aₙ→Sₙ\Aₙ
σ↦(1 2)σ. Note that f is well defined: if σ is even, then (1 2)σ is odd. And f is a bijection: it has inverse σ↦(1 2)σ. So |Aₙ| = |Sₙ\Aₙ| = |Sₙ|−|Aₙ|, so |Aₙ| = (1/2)|Sₙ| = (1/2)n!.
(iii) For n≥4, (1 2 3) and (1 2 4) are elements of Aₙ. Now (1 2 3)(1 2 4) =
while (1 2 4)(1 2 3) = so Aₙ is non-Abelian.
[These products have been left blank for the flashcarder to fill in.]

Question 46

Let G be a group. The subset H⊆G is a subgroup of G iff…
[Subgroup Test]

Also prove it too.

Answer 46

H is non-empty and h₁h₂⁻¹∈H for all h₁,h₂∈H.

Proof.(⇒) Assume that H is a subgroup of G. Then e∈H, so H is non-empty. Also, if h₁,h₂∈H then h₂⁻¹∈H as H contains inverses so h₁h₂⁻¹∈H as H is closed under the group operation.
(⇐) Assume that H is non-empty, say h∈H, and that h₁h₂⁻¹∈H for all h₁,h₂∈H.
•Identity: Have hh⁻¹ = e∈H.
•Inverses: Take h₁∈H. Have eh₁⁻¹ = h₁⁻¹∈H.
•Closure: Take h₁,h₂∈H. Then h₂⁻¹∈H so h₁(h₂⁻¹)⁻¹ = h₁h₂∈H. So H≤G.

Question 47

Let G be a group. Let H,K be subgroups of G. Then prove that H∩K is a subgroup of G.

Also can this be extended?

Answer 47

Left as an exercise for the flashcarder.

Yes, we can extend this to show that for any index set I, if Hᵢ (for i∈I) are subgroups of a group G, then
⋂ Hᵢ is a subgroup of G.
i∈I

Question 48

Let G be a group. Let S be a subset of G. The subgroup generated by S, written [], is…

What are the elements of S called?

Answer 48

Written 〈S〉, is the smallest subgroup of G that contains S, that is,〈S〉=
⋂ H.
S⊆H≤G
The elements of S are called the generators of〈S〉.

Par exemple, For g∈G, we write〈g〉for〈{g}〉.

Question 49

What is the division algorithm?

Answer 49

Let a,b be integers with b >0. Then there are unique integers q and r such that a = qb+r and 0≤r< b

Question 50

Let G be a group. Take g∈G. Prove:

(i) We have〈g〉= {gᵏ : k∈Z}.
(ii) If g has finite order, then〈g〉= {e,g,g²,…,gᵒ⁽ᵍ⁾⁻¹}.

Answer 50

(i) ⊇: Clearly if k∈Z then gᵏ∈〈g〉, so〈g〉⊇ {gᵏ : k∈Z}.
⊆: Claim: H = {gᵏ : k∈Z} is a subgroup of G.
Proof of claim:
– We have e = g⁰∈H so H is non-empty.
–If gᵏ, gˡ∈H, then (gᵏ)(gˡ)⁻¹ = gᵏ⁻ˡ∈H.
So by subgroup test have H≤G, which proves the claim. So〈g〉⊆H. So〈g〉= H.
(ii) Let d = o(g).
⊇: Clearly〈g〉⊇{e,g,…,gᵈ⁻¹}.
⊆: Take gᵏ∈〈g〉. By the division algorithm, we have k = qd+r for some q,r∈Z with 0≤r≤d−1. Then gᵏ = gᵠᵈ⁺ʳ = (gᵈ)ᵠgʳ = gʳ∈{e,g,…,gᵈ⁻¹}. So〈g〉⊆ {e,g,…,gᵈ⁻¹}. So〈g〉= {e,g,…,gᵈ⁻¹}.

Question 51

A group G is cyclic precisely when there is some g∈G such that G = []. In particular, a finite group G is cyclic iff

Answer 51

G =〈g〉

A finite group G is cyclic iff there is some g∈G with o(g) = |G|.

Question 52

Let G be a cyclic group, say G =〈g〉, then prove:

(i) If G is finite, with |G| = n, then G ∼= Cₙ.
(ii) If G is infinite, then G ∼= Z.

Answer 52

(i) We see that g has order n, and G = {e,g,…,gⁿ⁻¹} ∼=Cₙ.

(ii) Define θ : G→Z, gᵏ↦k. This is an isomorphism.

Question 53

Let G be a cyclic group. Let H be a subgroup of G. Then prove that H is cyclic.

Answer 53

Say G =〈g〉. If H = {e}, then H is cyclic and we are done. So suppose not, so gᵏ∈H for some k∈Z{0}. Then we must have gˡ∈H for some l∈Z>0, because if gᵏ∈H then also g⁻ᵏ∈H. Let d = min{m∈(Z>0):gᵐ∈H}. Then certainly〈gᵈ〉⊆H. Take gⁿ∈H. By the division algorithm, there are q,r∈Z with n = qd+r and 0≤r < d. Then gⁿ = gᵠᵈ⁺ʳ, so gʳ
= gⁿ⁻ᵠᵈ = gⁿ(gᵈ)⁻ᵠ∈H. Since 0≤r < d and d is minimal, we must have r = 0. That is, d divides n, and so gⁿ∈ gᵈ. So H =〈gᵈ〉is cyclic.

Question 54

Applying the cyclic subgroup theorem to the cyclic group Z shows that every subgroup of Z is of the form…

Answer 54

〈m〉= mZ for some integer m.

Question 55

Let m,n be integers. Let h,l be positive integers such that〈m,n〉=〈h〉and〈m〉∩〈n〉=〈l〉. Then prove that

(i) h|m and h|n (that is, h is a common factor of m and n);
(ii) There are a,b∈Z such that h = am+bn (Bézout’s lemma);
(iii) If d|m and d|n, then d|h (that is, h is divisible by every common factor of m and n);
(iv) m|l and n|l (that is, l is a common multiple of m and n);
(v) If m|c and n|c, then l|c (that is, any common multiple of m and n is a multiple of l).

Answer 55

(i) We have m∈〈m,n〉=〈h〉, so m = kh for some k∈Z so h|m. Similarly h|n.
(ii) We have h∈ 〈h〉=〈m,n〉so h = am+bn for some a,b∈Z (here we use that Z is Abelian).
(iii) Suppose that d|m and d|n. Then d|(rm+sn) for any r,s∈Z. So from (ii) we have d|h.
(iv) We have l∈〈l〉, so l∈〈m〉and l∈〈n〉so m|l and n|l.
(v) Suppose that m|c and n|c. Then c∈ 〈m〉and c∈ 〈n〉, so c∈〈m〉∩〈n〉=〈l〉. So l|c.

Question 56

Let G be a group, let g∈G be an element with finite order d. Then prove that gᵏ
= e iff d|k.

Answer 56

(⇐) Assume that d|k, say k= ad where a∈Z. Then gᵏ = (gᵈ)ᵃ = e.
(⇒) Assume that gᵏ = e. By the division algorithm, we have k = qd+r for some integers q,r with 0≤q < d. Then gʳ = gᵏ⁻ᵠᵈ = gᵏ(gᵈ)⁻ᵠ = e. Since r < d and d is minimal, we have r = 0. So d|k.

Question 57

(Chinese Remainder Theorem). Let m,n be coprime positive integers (that is, they have hcf 1). Then prove that Cₘ×Cₙ is cyclic, and is isomorphic to Cₘₙ.

Answer 57

Say Cₘ =〈g〉and Cₙ =〈h〉. Claim. (g,h)∈Cₘ×Cₙ has order mn.
Proof of claim We have (g,h)ᵐⁿ = ((gᵐ)ⁿ,(hⁿ)ᵐ)) = (e,e), so the order of (g,h) is at most mn. Also, for any k∈Z>0 if (g,h)ᵏ = (e,e) then gᵏ = e and hᵏ = e. So m|k and n|k, by Lemma 23. Since m and n are coprime, by Bézout there are integers a and b such that am+bn = 1. Then akm+bkn = k, and both terms on the left are divisible by mn, so mn|k, so k≥mn. So the order of (g,h) is mn, which proves the claim. Now |Cₘ×Cₙ| = mn, so Cₘ×Cₙ is a group of order mn containing an element with order mn, so Cₘ×Cₙ is cyclic and Cₘ×Cₙ ∼= Cₘₙ.

Question 58

A (binary) relation on a set S is…

Answer 58

A subset of S×S.

Question 59

For a relation R⊆S×S, we write aRb iff…

Answer 59

(a,b)∈R

Question 60

Let ∼ be a relation on a set S. We say that ∼ is an equivalence relation if…

Answer 60

• ∼ is reflexive (that is, if a∼a for all a∈S);
• ∼ is symmetric (that is, if a∼b then b∼a);
• ∼ is transitive (that is, if a∼b and b∼c, then a∼c).

Question 61

Let n≥2 be an integer. Define a relation ∼ on Z by a∼b iff a−b is a multiple of n. Prove that ∼ is an equivalence relation.

What is the name of this equivalence relation?

Answer 61

Take a,b,c∈Z.
• reflexive: a−a is a multiple of n.
• symmetric: if n divides a−b then n divides b−a.
• transitive: if n divides a−b and b−c, say a−b = kn and b−c = ln where k,l∈Z, then a−c = (a−b) + (b−c) = (k+l)n so n divides a−c.

This is called congruence modulo n.

Question 62

Let G be a group. We say that g₁,g₂∈G are conjugate if…

Answer 62

There is h∈G with g₁ = h⁻¹g₂h.

Question 63

Let G be a group. Prove that conjugacy in G is an equivalence relation.

Answer 63

Write h∼k iff h and k are conjugate in G (that is, iff there is g∈G with h = g⁻¹kg). Take g₁,g₂,g₃∈G.
• reflexive: have g₁ = e⁻¹g₁e so g₁∼g₁.
• symmetric: if g₁∼g₂, then there is h∈G with g₁=h⁻¹g₂h. Then g₂ = hg₁h⁻¹ = (h⁻¹)⁻¹g₁(h⁻¹) so g₂∼g₁.
• transitive: if g₁∼g₂ and g₂∼g₃, then there are h₁,h₂∈G with g₁=h₁⁻¹g₂h₁ and g₂ = h₂⁻¹g₃h₂. Then g₁ = h₁⁻¹(h₂⁻¹g₃h₂)h₁ = (h₂h₁)⁻¹g₃(h₂h₁), so g₁∼g₃.

Question 64

Let ∼ be an equivalence relation on a set S. For a∈S, we define the equivalence class of a, written [a] or a, to be…

Answer 64

The set {b∈S : a∼b}. “all the things related to a.”

Question 65

Let S be a set, let I be an index set. For i∈I, let Sᵢ be a subset of S. We say that the Sᵢ (for i∈I) partition S if…

Answer 65

• Sᵢ =/= ∅ for all i∈I (non-empty);
• ⋃ Sᵢ = S (cover);
. i∈I
• Sᵢ∩Sⱼ = ∅ for i =/= j (pairwise disjoint).

Question 66

Let ∼ be an equivalence relation on a set S. Prove that the equivalence classes of ∼ partition S.

Answer 66

• Non-empty: for any a∈S, we have a∈[a] as ∼ is reflexive, so each equivalence class is non-empty.
• Cover: since a∈[a] for all a∈S, certainly ⋃a∈S[a] =S.
• Pairwise disjoint: take a,b∈S. Suppose c∈[a]∩[b]. Then a∼c and b∼c, so by symmetry c∼b, so by transitivity a∼b. If d∈[b], then b∼d, so by transitivity a∼d, so d∈[a]. So [b]⊆[a]. Similarly, [a]⊆[b]. So either [a]∩[b] = ∅ or [a] = [b].

Question 67

Let P be a partition of a set S. For a∈S, write Pₐ for the unique part in P with a∈Pₐ. Define a relation ∼ on S by a∼b iff b∈Pₐ. Prove that ∼ is an equivalence relation.

Answer 67

Take a,b,c∈S.
• reflexive: we have a∈Pₐ so a∼a.
• symmetric: if a∼b then b∈Pₐ, so b∈Pₐ∩Pᵦ, so Pₐ∩Pᵦ =/= ∅, so Pₐ = Pᵦ, so a∈Pᵦ, so b∼a.
• transitive: if a∼b and b∼c, then b∈Pₐ∩Pᵦ and so Pₐ = Pᵦ, but also c∈Pᵦ, so c∈Pₐ so a∼c.

Question 68

Prove there is a bijection between equivalence relations on a set S and partitions of that same set S.

Answer 68

Theorem 27 gives a map in one direction, and a quick check shows that Theorem 28 gives the inverse.

Question 69

Prove that the binary operations + and × on Zₙ defined by
_ ._ . .___ . . . . _ ._ . .___
a+b = a+b and a×b = a×b are well defined.

Answer 69

.. . . . . . . . . . . _ . ._ . . . . _ . ._
Assume that a = c and b = d. Then a ≡ c(modn) and b ≡ d(modn), so there are k,l∈Z such that a−c = kn and b−d = ln. Then (a+b)−(c+d) = (a−c) + (b−d) = (k+l)n so a+b ≡ c+d(modn), and (a×b)−(c×d) = ab−(a−kn)(b−ln) = (bk+al−kln)n so ab ≡ cd(modn), so
___ . .___ . . . .___ . .___
a+b = c+d and a×b = c×d.

Question 70

Prove that (Zₙ,+) is an Abelian group. Moreover, it is cyclic and isomorphic to Cₙ. Furthermore, × is associative and commutative on Zₙ, and × is distributive over +.

Answer 70

Left as an exercise for the flashcarder. Check that the relevant properties transfer across from Z. Note that
_
1 has order n in Zₙ, so (Zₙ,+) is cyclic generated by
_
1.

Question 71

Prove the following:
. . . . . . _ . . . . . . . . . _
(i) Take x∈Zₙ. Then x has a multiplicative inverse in Zₙ (that is, there exists
_ . . . . . . . _ _
y∈Zₙ with x y = 1) iff hcf(x,n) = 1.
(ii) If p is prime, then Zₚ is a field.
. . . . . . . . . . . _ . . . . ._
(iii) Let Zₙˣ = {x∈Zₙ : x has a multiplicative inverse} be the set of units in Zₙ. Then Zₙˣ is a group under multiplication.

Answer 71

Excerise left for the flashcarder. (On problem sheet 4, so fingers crossed we knew what was going on)

Question 72

Let G be a group, let H be a subgroup of G. A left coset of H in G is…
The set of left cosets of H in G is denoted []
The cardinality of this set is called the…
A right coset of H in G is a…

Answer 72

A left coset of H in G is a set gH := {gh : h∈H} where g∈G.
The set of left cosets of H in G is denoted G/H.
The cardinality of this set is called the index of H in G.
A right coset of H in G is a set Hg := {hg : h∈H} where g∈G.

Question 73

(Coset equality test). Let H be a subgroup of a group G. Take g₁,g₂∈G. Prove that we have g₁H = g₂H iff g₂⁻¹g₁∈H.

Answer 73

(⇒) Assume that g₁H=g₂H. Then g₁ = g₁e∈g₁H so g₁∈g₂ H so there is h∈H with g₁=g₂h. Then g₂⁻¹g₁ = h∈H.
(⇐) Assume that g₂⁻¹g₁∈H, say g₂⁻¹g₁ = h∈H. Take an element of g₁H, say g₁h₁ where h₁∈H. Then g₂⁻¹g₁h₁ = hh₁∈H so g₁h₁ = g₂hh₁∈g₂H So g₁H⊆g₂H. Since g₁⁻¹g₂ = h⁻¹∈H, we similarly obtain g₂H⊆g₁H. So g₁H = g₂H.

Question 74

(Lagrange’s Theorem). Let G be a finite group and let H be a subgroup of G. Prove that |H| | |G|. “the order of a subgroup divides the order of the group”

Answer 74

Claim. The left cosets of H partition G.
Proof of claim:
• Non-empty: we have g∈gH so gH =/= ∅ for all g∈G.
• Cover: since g∈gH for all g∈G, we have
. .⋃ gH = G.
g∈G
• Pairwise disjoint: take g₁,g₂∈G. Suppose g∈g₁H∩g₂H. Then there are h₁,h₂∈H with g = g₁h₁ = g₂h₂, so g₂⁻¹g₁ = h₂h₁⁻¹∈H, so by the coset equality test we have g₁H = g₂H. So g₁H = g₂H or g₁H∩g₂H = ∅. This proves the first claim. Claim. Each left coset of H has the same size as H.
Proof of claim Take g∈G. Define f: H→gH, h↦gh. This is a bijection (it has inverse
~ . . . . ~
g↦g⁻¹g). So |H| = |gH|.This proves the second claim. Then |G| = |G/H|×|H|, so |H| | |G|.

Question 75

Let G be a finite group. Take g∈G. Prove that g has finite order.

Answer 75

Consider g,g²,g³, . . . . These are all in the finite set G, and so there are positive integers r and s with r < s and gʳ=gˢ. Then e = gˢ⁻ʳ, so the order of g is finite (and is at most s−r).

Question 76

Let G be a finite group. Take g∈G. Prove that o(g) | |G|.

“the order of an element divides the order of the group”

Answer 76

Note that〈g〉= {e,g,g²,…,gᵒ⁽ᵍ⁾⁻¹} is a subgroup of G with order o(g). Now apply Lagrange.

Question 77

Let p be prime. Let G be a finite group with order p. Prove that G is cyclic.

Answer 77

Take g∈G{e}. Then o(g) divides p and is not 1, so o(g) = p. So g is a generator of G.

This proof shows that any non-identity element generates G.

Question 78

Let G be a finite group. Take g∈G. Prove that g|ᴳ| = e.

Answer 78

We have gᵒ⁽ᵍ⁾ = e and o(g) | |G|.

Question 79

(Fermat’s Little Theorem). Let p be prime. Let a be an integer coprime to p. Prove that aᵖ⁻¹ ≡ 1 (modp).

Answer 79

(Zₚˣ,×) is a group of order p−1. Apply Corollary 38.

Question 80

(Fermat-Euler Theorem). Let n≥2 be an integer. Let a be an integer coprime to n. Define the Euler totient function φ via φ(n) := |{k∈N : 1≤k≤n, hcf(k,n) =1}|. Prove that aᵠ⁽ⁿ⁾ ≡ 1 (modn).

Answer 80

(Zₙˣ,×) is a group of order φ(n). Apply Corollary 38.