๐Ÿ’พ 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

View Raw

More Information

โฌ…๏ธ Previous capture (2023-03-20)

-=-=-=-=-=-=-

Groups

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)

Conventions/Notation

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]โ‚ƒ.

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:

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.

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?

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?

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

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:

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:

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:

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:

(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:

(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โ‚ƒ:

(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.

(Zโ‚…, +)

Try this one yourself.

(Zโ‚™, +)

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โ‚™.

TODO

Groups that are isomorphic to some proper subgroup.