๐พ Archived View for siiky.srht.site โบ algebra โบ groups.gmi captured on 2024-05-12 at 15:16:04. Gemini links have been rewritten to link to archived content
โฌ ๏ธ Previous capture (2023-03-20)
-=-=-=-=-=-=-
siiky
2020/02/20
2022/07/15
en
This post is about groups (whouldathunkit).
gemini://gemi.dev/cgi-bin/wp.cgi/view/en?Group_(mathematics)
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:
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]โ.
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:
From (R2) and (R3) we can conclude that id always has inverse, itself.
There is one extra optional property:
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.
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โ is the set of natural numbers (w/ zero), and + is the usual addition on natural numbers. Is it a group?
Nโ with + does not satisfy property R3, so it is not a group.
Z is the set of integers, and + is the usual addition on integers. Is it a group?
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).
Some more definitions.
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:
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:
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โปยน)โปโฟ.
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:
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.
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.
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.
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:
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:
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โ:
Zโ = { [0]โ, [1]โ, [2]โ, [3]โ }
[0]โ = 4Z
[1]โ = 4Z + 1
[2]โ = 4Z + 2
[3]โ = 4Z + 3
Once again, things about this group:
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:
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.
Try this one yourself.
Summing up:
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โ.
Groups that are isomorphic to some proper subgroup.