Entrance to semigroups半群はんぐん, monoidsモノイド, and groups群ぐん

If the definition of a group is memorized all at once, from having a binary operation (which includes closure) through having inverses, it is hard to see why those conditions are needed. Instead, add conditions one by one to a binary operation二項演算にこうえんざん.

Viewed in this order順序じゅんじょ, a group群ぐん is a structure in which operations can be repeated, there is an operation that does nothing, and operations can be undone.

1Semigroups

A semigroup半群はんぐん is a pair consisting of a set $$S$$S and a binary operation $$\text{[PARSE ERROR: Undefined("Command("ast")")]}$$\ast satisfying the associative law for every $$a,b,c\in S$$a,b,c\in S.

A semigroup does not require an identity element単位元たんいげん or inverse elements. It does not require commutativity either, so $$a\text{[PARSE ERROR: Undefined("Command("ast")")]}b$$a\ast b and $$b\text{[PARSE ERROR: Undefined("Command("ast")")]}a$$b\ast a may differ.

Because associativity holds, parentheses can be omitted in a long product such as

This means that every placement of parentheses, with the order of the elements unchanged, gives the same value. The case of three elements is exactly the associative law. For the general case, use induction on the number of elements. Any parenthesization splits at some $$k$$k into a product of the first $$k$$k elements and the remaining elements. Inductively put each part into left-associated form, then repeatedly use associativity to obtain the same left-associated form for the whole product.

2Monoids

A monoidモノイド is a semigroup with an identity element単位元たんいげん. That is, there exists an element $$e$$e such that for every $$a$$a,

Here we use $$\mathbb{N}=\{0,1,2,\dots \}$$\mathbb N=\{0,1,2,\ldots\}. The natural numbers $$\mathbb{N}$$\mathbb N then form a monoid under addition with identity element 0. However, within the natural numbers, not every element has an additive inverse, so this is not a group.

3Groups

A group群ぐん is a monoid in which every element has an inverse. For every $$a$$a, there exists an element $$a^{-1}$$a^{-1} such that

In a group, an operation that moves forward can be undone by an inverse. This property of being able to return is what makes groups the mathematics of symmetries and transformations.

As proved in the preceding lecture, under associativity the identity element and the inverse of each element are unique whenever they exist. Thus the notation $$a^{-1}$$a^{-1} denotes one determined element.

4Cancellation in a group

In a group $$G$$G, for all $$a,b,c\in G$$a,b,c\in G,

This is the left cancellation law. Indeed, operating on the left of both sides by $$a^{-1}$$a^{-1} gives

and associativity together with the inverse and identity laws yields $$b=c$$b=c. Operating on the right by an inverse similarly gives the right cancellation law, $$b\text{[PARSE ERROR: Undefined("Command("ast")")]}a=c\text{[PARSE ERROR: Undefined("Command("ast")")]}a\Rightarrow b=c$$b\ast a=c\ast a\Rightarrow b=c.

5Concrete examples: natural numbers, integers, and rational numbers

With addition,

is a monoid. The identity element単位元たんいげん is 0, but there is no natural number that brings 3 back to 0 by addition.

is a group群ぐん. The inverse of an integer $$a$$a is $$-a$$-a.

With multiplication,

is a group群ぐん. The reason for excluding 0 is that 0 has no multiplicative inverse.

6A noncommutative example: composition of bijections

A map $$f:X\to X$$f:X\to X is a bijection if, for every $$y\in X$$y\in X, there is exactly one $$x\in X$$x\in X such that $$f\left(x\right)=y$$f(x)=y. Reversing this correspondence defines the inverse map $$f^{-1}$$f^{-1}. Let $$\mathrm{Sym}\left(X\right)$$\operatorname{Sym}(X) be the set of all such bijections.

Define composition, the operation of applying two maps in succession, by $$(f\circ g)\left(x\right)=f\left(g\right(x\left)\right)$$(f\circ g)(x)=f(g(x)). A composition of bijections is again a bijection, so closure holds. Moreover, for every $$x\in X$$x\in X,

so composition is associative. The identity map $${\mathrm{id}}_X\left(x\right)=x$$\operatorname{id}_X(x)=x is the identity element, and the inverse map $$f^{-1}$$f^{-1} is the inverse of each bijection $$f$$f. Therefore

is a group.

Let $$X=\{1,2,3\}$$X=\{1,2,3\}, let $$f$$f interchange 1 and 2, and let $$g$$g interchange 2 and 3. Then $$(f\circ g)\left(1\right)=2$$(f\circ g)(1)=2, whereas $$(g\circ f)\left(1\right)=3$$(g\circ f)(1)=3. Thus $$f\circ g\ne g\circ f$$f\circ g\ne g\circ f: commutativity is not part of the definition of a group.

7What changes and what is preserved

Moving from semigroups to monoids makes the "do nothing" operation available. Moving from monoids to groups makes the "undo" operation available. In all cases, closure閉包性へいほうせい of the operation inside the same set and the associative law結合法則けつごうほうそく are preserved.

8Counterexample supplement: the hierarchy of semigroups半群はんぐん, monoidsモノイド, and groups群ぐん is strict

Semigroups, monoids, and groups form a hierarchy obtained by adding conditions one at a time. However, the stronger notions do not collapse to the weaker ones.

$$(Z_{>0},+)$$(\mathbb Z_{>0},+) is a semigroup半群はんぐん because addition is associative. It is not a monoidモノイド, because the identity element 0 is not in $$Z_{>0}$$\mathbb Z_{>0}.

$$(Z_{\text{[PARSE ERROR: Undefined("Command("ge")")]}0},+)$$(\mathbb Z_{\ge0},+) is a monoidモノイド because it has 0 as its identity element単位元たんいげん. It is not a group群ぐん, because the additive inverse $$-1$$-1 of 1 is not in $$Z_{\text{[PARSE ERROR: Undefined("Command("ge")")]}0}$$\mathbb Z_{\ge0}.

$$(\mathbb{Z},+)$$(\mathbb Z,+) is a group群ぐん because it has 0 and all additive inverses. Thus each newly required condition has real content.

9Exercise link

Solve Problems 2, 3, and 4 in sequence to check every condition that makes one operation a group.

10Bridge to the next lectures

The next two lectures use equivalence relations and congruences to collect integers with the same remainder into single elements. With that concrete example in hand, the sequence returns to group foundations and studies $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+) as a group.

11Summary

A semigroup半群はんぐん is a set equipped with an associative binary operation, a monoidモノイド is a semigroup with an identity element単位元たんいげん, and a group群ぐん is a monoid in which every element has an inverse. Understanding this staircase reveals the role played by each group axiom.