Groups

siiky

2020/02/20

2022/07/15

en

This post is about groups (whouldathunkit).

• https://en.wikipedia.org/wiki/Group_(mathematics)

Conventions/Notation

• ∀ v: P means P is true for all possible v
• ∃ v: P means P is true for at least one v
• ∃¹ v: P means P is true for exactly one v
• ∀ v1: ∀ v2: P will be abbreviated as ∀ v1, v2: P

Sets are written as its elements surrounded by brackets. For example, ∅ is the empty set and { a, b, c } is a set with the elements a, b and c. Sets comprehension will be written as { expr : vars, restrictions } and the cardinal of a set will be written as #S.

N is the set of natural numbers (w/o zero), N₀ the set of natural numbers (w/ zero), Z the set of integers, and R the set of real numbers.

The modulo operator will be recurrent throughout this post. A couple of examples:

• 4 mod 5 ≣ 9 mod 5 ≣ 4
• 5 mod 2 ≣ 1

This operator is called % in C, modulo in Scheme and mod in Haskell.

A useful definition: p ≣ q (mod n) ⇔ p mod n ≣ q mod n.

"|" will be used to mean "divides": "a | b" means "a divides b", "b is a multiple of a", or, with modulo, "a | b ⇔ b ≣ 0 (mod a)".

We will be needing the concept of a "Congruential Equivalence Class" later on. They are written as [m]ₙ (∀ n ∈ N, m ∈ Z) and are defined as [m]ₙ = { x ∈ Z : x ≣ m (mod n) }.

Depending on context, + and ∗ will either be the usual addition and multiplication of numbers, or addition and multiplication of classes.

Addition and multiplication of classes are defined as [p]ₙ + [q]ₙ = [p+q]ₙ and [p]ₙ ∗ [q]ₙ = [p∗q]ₙ. Example: 2+2=4, [2]₃ + [1]₃ = [2+1]₃ = [0]₃.

What is a Group?!

In general

A group is just a pair (S, O), where S is a set and O is a binary operation on S (i.e., O : S ∗ S → S) with the following required properties:

• (R1) Associativity: ∀ a, b, c ∈ S: O(a, O(b, c)) = O(O(a, b), c)
• (R2) Identity: ∃¹ id ∈ S: ∀ a ∈ S: O(a, id) = O(id, a) = a
• (R3) Inverse: ∀ a ∈ S: ∃¹ a' ∈ S: O(a, a') = O(a', a) = id

From (R2) and (R3) we can conclude that id always has inverse, itself.

There is one extra optional property:

• (R4) Commutativity: ∀ a, b ∈ S: O(a, b) = O(b, a)

A group with a commutative operation is called a commutative group or an abelian group.

Given G = (G, O) a group, G will be used to refer both to the group itself and its associated set.

A group G is said to be infinite if #G is infinite, and finite if #G is finite.

That is the generic definition. We will focus on groups with integer sets and + or ∗ as the operation, however.

Integers

When the operation is + we call the identity element "null element" and represent it with 0. When the operation is ∗ we call the identity element "unity element" and represent it with 1.

When the operation is + we call the inverse of an element a its symmetric and represent it as -a. When the operation is ∗ we call the inverse of an element a its inverse and represent it as a⁻¹.

(N₀, +)

N₀ is the set of natural numbers (w/ zero), and + is the usual addition on natural numbers. Is it a group?

• ∀ a, b, c ∈ N₀: a + (b + c) = (a + b) + c
• 0 is the identity of the group, because ∀ a ∈ N₀: a + 0 = 0 + a = a
• ∀ a, b ∈ N: a + b ≠ 0 (Note that N = N₀∖{0})

N₀ with + does not satisfy property R3, so it is not a group.

(Z, +)

Z is the set of integers, and + is the usual addition on integers. Is it a group?

• ∀ a, b, c ∈ Z: a + (b + c) = (a + b) + c
• 0 is the identity of the group, because ∀ a ∈ Z: a + 0 = 0 + a = a
• ∀ a ∈ Z: ∃¹ a' ∈ Z: a + a' = 0

Z satisfies all 3 requirements so it is a group. We also know that addition is commutative, so Z is an abelian group (see property R4).

Other examples

• (R, +), where R is the set of real numbers, is a group
• (R∖{0}, ∗) is also a group
• (R, ∗) is not a group, because 0 has no inverse (R3)
• (N, +) is not a group, because there is no identity and no inverse (R2 and R3)
• (N, ∗) is not a group, because there is no inverse (R3)
• (Z∖{0}, ∗) is not a group, because other than 1 and -1, no element has inverse (R3)

What's next?

Some more definitions.

Subgroup

Given a group G, H is called a subgroup of G if H is contained in G and it is also a group, and we write H ≤ G. Examples:

• ∀ (G, +) group: (G, +) ≤ (G, +)
• Trivial Subgroup: ∀ (G, +) group: ({0}, +) ≤ (G, +)
• (2Z, +) ≤ (Z, +)

A subgroup H of a group G that is not G itself (H ≠ G, or H ⊂ G) is called a "Proper Subgroup", and we write H < G. Examples:

• Trivial Subgroup: ∀ (G, +) group: ({0}, +) < (G, +)
• (2Z, +) < (Z, +)

Multiples/Powers of an element

Given an element a of an additive group, a+...+a (n times) can be written as n∗a. Special case: 0∗a = 0.

Given an element a of a multiplicative group, a∗...∗a (n times) can be written as aⁿ. Special case: a⁰ = 1.

For negative n, n∗a = -((-n)∗a) = (-n)∗(-a); and aⁿ = (a⁻ⁿ)⁻¹ = (a⁻¹)⁻ⁿ.

Order of an element

The order of an element a is the minimum number of times it must be operated with itself until it turns into the identity, and is written as o(a). If no matter how many times you operate the element it doesn't turn into the identity, its order is said to be infinite.

A more rigorous definition is:

• a has infinite order if ∀ n ∈ N: n∗a ≠ 0
• a has finite order k, that is, o(a) = k, if: (1) k ∈ N; (2) k∗a = 0; (3) ∀ n ∈ N: n∗a = 0 ⇒ n ≤ k

In particular, the order of the identity is 1, and the identity is the only element with order 1.

Useful fact: ∀ G group: ∀ a ∈ G: o(a) | #G. From this comes that in a finite group no element has infinite order.

Generated Subgroup

Given a ∈ (G, +), 〈a〉 = { n∗a : n ∈ Z } is a subgroup of G and is called the "Subgroup of G generated by a". In particular, if G = 〈a〉, a is said to generate G, or that G is generated by a. Note that #〈a〉 = o(a). An example of this is 〈1〉 = 〈-1〉 = Z.

Zₙ Groups

You can group integers together according to their (mod n), make a set out of them, and define a group with it. These groups are called Zₙ, for some n ∈ N, and are defined as Zₙ = { [m]ₙ : m ∈ { 0, ..., n-1 } }.

These will get repetitive after Z₂, but the reason why they're here will become clear.

(Z₁, +)

According to definition above Z₁ = { [0]₁ }, but you can go further here:

[0]₁

= { def [m]ₙ }

{ x : x ∈ Z, x ≣ 0 (mod 1) }

= { def (mod n) }

{ x : x ∈ Z, x mod 1 = 0 mod 1 }

= { 0 mod 1 = 0 }

{ x : x ∈ Z, x mod 1 = 0 }

= { ∀ x ∈ Z: 1 | x }

{ x : x ∈ Z }

= { def Z }

Z

Z₁ is a trivial group (#Z₁ = 1), so it isn't that interesting, other than Z being its only element.

Some things we can find about it:

• Since it is a trivial group, its only subgroup is itself
• [0]₁ is the identity, so o([0]₁) = 1
• Z₁ = 〈[0]₁〉

(Z₂, +)

When n=2 we get Z₂ = { [0]₂, [1]₂ }.

[0]₂

= { def [m]ₙ }

{ x : x ∈ Z, x = 0 (mod 2) }

= { def (mod n) }

{ x : x ∈ Z, x mod 2 = 0 mod 2 }

= { 0 mod 2 = 0 }

{ x : x ∈ Z, x mod 2 = 0 }

= { x mod 2 = 0 ⇒ ∃ k ∈ Z: x = 2 ∗ k }

{ 2 ∗ x : x ∈ Z }

= { def 2Z }

2Z

So [0]₂ = 2Z is the set of even integers. You can probably guess by now, but:

[1]₂

= { def [m]n }

{ x : x ∈ Z, x = 1 (mod 2) }

= { def (mod n) }

{ x : x ∈ Z, x mod 2 = 1 mod 2 }

= { 1 mod 2 = 1 }

{ x : x ∈ Z, x mod 2 = 1 }

= { x mod 2 = 1 ⇒ ∃ k ∈ Z: x = 2 ∗ k + 1 }

{ 2 ∗ x + 1 : x ∈ Z }

= { def 2Z+1 }

2Z+1

And with that you see that [1]₂ is the set of odd integers.

Some things we can find about it:

• [0]₂ is the identity, so o([0]₂) = 1
• [1]₂ ≠ [0]₂, but [1]₂ + [1]₂ = [1 + 1]₂ = [2]₂ = [0]₂, so o([1]₂) = 2
• 〈[0]₂〉 = { [0]₂ } < Z₂
• 〈[1]₂〉 = Z₂

(Z₃, +)

Z₃ = { [0]₃, [1]₃, [2]₃ }

I'll skip showing how to get to the definition of each of the classes from now. Also, you may have already noticed, but if not, [0]ₙ is the set of multiples of n, nZ.

[0]₃ = 3Z

[1]₃ = 3Z + 1

[2]₃ = 3Z + 2

And now things about Z₃:

• o([0]₃) = 1
• o([1]₃) = 3; you may also have noticed that o([1]n) = n. This has to do with the fact that ∀ n ∈ Z: n ∗ 1 = n. So n ∗ [1]n = [n ∗ 1]n = [n]n = [0]n
• o([2]₃) = 3; [2]₃ ≠ [0]₃, 2 ∗ [2]₃ = [1]₃ ≠ [0]₃, 3 ∗ [2]₃ = [0]₃ This one has to do with the fact that 2 and 3 are coprime, which means lcm(2, 3) = 6, and 6 / 2 = 3
• 〈[0]₃〉 = { [0]₃ } < Z₃
• 〈[1]₃〉 = 〈[2]₃〉 = Z₃

(Z₄, +)

Z₄ = { [0]₄, [1]₄, [2]₄, [3]₄ }

[0]₄ = 4Z

[1]₄ = 4Z + 1

[2]₄ = 4Z + 2

[3]₄ = 4Z + 3

Once again, things about this group:

• o([0]₄) = 1
• o([2]₄) = 2
• o([1]₄) = o([3]₄) = 4
• 〈[2]₄〉 = { [0]₄, [2]₄ } < Z₄
• 〈[1]₄〉 = 〈[3]₄〉 = Z₄

Now something interesting happened here! Remember that ∀ G group: ∀ a ∈ G: o(a) | #G

Because of this we know that the only possible orders are 1, 2 and 4.

This also means that it is possible for a subgroup of cardinal 2 to exist. In this case, the only one is 〈[2]₄〉. Why, though, did this happen with Z₄, but not with Z₁, Z₂ or Z₃? Z₁ is obvious: #Z₁ = 1, so the only possible subgroup is itself. Z₂ is also easy: its only elements are [0]₂ and [1]₂, and we know that:

• ∀ n ∈ N: 〈[0]n〉 = { [0]n }; and that
• ∀ n ∈ N: 〈[1]n〉 = Zₙ

For Z₃ it's not as clear. The hint is, again: ∀ G group: ∀ a ∈ G: o(a) | #G

Both 2 and 3 are prime, which means, their only divisors are 1 and themselves. So it's not possible for a subgroup of Z₃ with cardinal 2 to exist.

(Z₅, +)

Try this one yourself.

(Zₙ, +)

Summing up:

• ∀ n ∈ N: Zₙ has more than one proper subgroup ⇔ n is not prime
• ∀ n ∈ N: Zₙ has exactly one proper subgroup ⇔ n is prime

Proving this is easy: Let n ∈ N.

Suppose that Zₙ has more than one proper subgroup. We want to prove that n is not prime.

There is a proper subgroup H such that #H > 1. Since H is a proper subgroup, then #H < n. From this, and the fact that #H | n, we can conclude n is not prime.

Now the other way: Suppose n is not prime. We want to prove that Zₙ has more than one proper subgroup. Since n is not prime, then ∃ k ∈ N: 1 < k < n ∧ k | n.

Let k be such a number. Then ∃ a ∈ Zₙ: o(a) = k.

Let a be such an element. o(a) = k ⇒ #〈a〉 = k. We know that 〈a〉 ≤ Zₙ and that k < n, so 〈a〉 < Zₙ.

TODO

Groups that are isomorphic to some proper subgroup.