7.1-7.2 Binary operations, monoids, and groups

Set theory lets us compare sets by functions, relations, and cardinalities. But many mathematical objects are not interesting merely because of which elements they contain. They are interesting because the set carries extra structure.

For example, from the point of view of bare cardinality, the set {5, dog} and the set $\{0,1\}$ both have two elements. But $\{0,1\}$ also supports familiar operations such as addition and multiplication modulo $2$, while 5 + dog is not meaningful unless extra structure has been specified.

Sets with structure

Many mathematical objects can be read as sets with additional data: natural numbers with addition and multiplication, the plane with vector addition, and permutations with composition.

The common pattern is:

1. start with a set;
2. specify some operation, relation, function, or distinguished element on that set;
3. state axioms that this extra data must satisfy;
4. prove theorems from those axioms.

This is one of the central habits of modern mathematics. Instead of proving the same fact separately for many examples, define a structure once and prove what all examples of that structure must satisfy.

Binary operations

Definition 7.1.1

(Binary operation)

Let $X$ be a set. A binary operation on $X$ is a function

$$*:X\times X\to X.$$

For $a,b\in X$, we usually write $a*b$ instead of $*(a,b)$.

There are two important parts to this definition.

First, the operation takes two inputs from $X$. Second, the output must again belong to $X$. That second requirement is often called closure, although in this course it is already built into the function type $X\times X\to X$.

Common mistake

(A formula is not automatically a binary operation on every set)

Subtraction is a binary operation on $Z$, because $a-b\in Z$ whenever $a,b\in Z$. But subtraction is not a binary operation on $N$ if $N$ is required to stay closed under the operation, because $2-5$ is not a natural number.

Boolean integers

Define

$$B=\{0,1\}.$$

On this set, addition is given by

$$0+0=0,\qquad 0+1=1,\qquad 1+0=1,\qquad 1+1=0,$$

and multiplication is given by

$$0\cdot 0=0,\qquad 0\cdot 1=0,\qquad 1\cdot 0=0,\qquad 1\cdot 1=1.$$

Definition 7.1.2

(Boolean integers)

The Boolean integers are the triple

$$(B,+,\cdot),$$

where $B=\{0,1\}$ and $+$, $\cdot$ are the two binary operations displayed above.

Even a two-element set can carry different operations, whose laws must be examined separately.

Worked example 7.1.3

(Solving $x+y=0$ in $B$)

Every $x\in B$ can be paired with an element whose sum with $x$ is zero:

$$\forall x\in B,\ \exists y\in B\ (x+y=0).$$

Check the two possible values of $x$.

If $x=0$, choose $y=0$, since $0+0=0$.

If $x=1$, choose $y=1$, since $1+1=0$.

Thus every element of $B$ has an additive inverse with respect to this addition rule.

More examples of binary operations

The familiar examples are:

• $+$ and $\times$ are binary operations on $N$;
• $+$ and $\times$ are binary operations on $Z$;
• for any set $X$, composition is a binary operation on the set $X^X$ of all functions $X\to X$.

If $f:X\to X$ and $g:X\to X$, their composition $g\circ f$ again maps $X$ to $X$. Hence composition defines a binary operation

$$\circ:X^X\times X^X\to X^X.$$

Worked example 7.1.4

(Composition as a binary operation)

Let $X=\{a,b\}$ with $a\ne b$. Define $f$ by $f(a)=f(b)=a$, and let $g$ exchange the two elements: $g(a)=b$ and $g(b)=a$. Then

$$(g\circ f)(a)=(g\circ f)(b)=b, \qquad (f\circ g)(a)=(f\circ g)(b)=a.$$

Both composites belong to $X^X$, but they are different functions. Composition is closed on $X^X$ without being commutative. The elements being combined are functions, not elements of $X$.

Monoids

Function composition has two properties independent of the choice of $X$: regrouping a sequence of compositions leaves the result unchanged, and composing with $id_X$ leaves a function unchanged. A monoid abstracts these two laws, so that the same arguments apply to addition, multiplication, and composition.

Definition 7.1.5

(Monoid)

A monoid $(M,*)$ is a set $M$ together with a binary operation

$$*:M\times M\to M$$

such that:

• for all $a,b,c\in M$,

  $$(a*b)*c=a*(b*c)$$

  (associativity);

• there exists $e\in M$ such that for all $a\in M$,

  $$a*e=e*a=a$$

  (existence of an identity element).

Associativity tells us that parentheses do not matter when multiplying three elements in a row. The identity element tells us that there is an element that does nothing when combined on either side.

The standard examples are:

• $(N,+)$ is a monoid with identity $0$;
• $(N,\times)$ is a monoid with identity $1$;
• $(Z,+)$ is a monoid with identity $0$;
• $(Z,\times)$ is a monoid with identity $1$;
• for any set $X$, $X^X$ under composition is a monoid with identity $id_X$;
• $(B,+)$ is a monoid;
• $(B,\cdot)$ is a monoid.

Worked example 7.1.6

(Checking that $(N,+)$ is a monoid)

The operation $+$ is a binary operation on $N$.

Associativity holds:

$$(a+b)+c=a+(b+c)$$

for all natural numbers $a,b,c$.

The identity is $0$, because

$$a+0=0+a=a.$$

Therefore $(N,+)$ is a monoid.

Worked example 7.1.7

(Checking the composition monoid)

Let $X$ be any set. The elements of $X^X$ are functions $X\to X$.

Composition is associative:

$$(h\circ g)\circ f=h\circ(g\circ f).$$

The identity function $id_X$ satisfies

$$f\circ id_X=f,\qquad id_X\circ f=f.$$

Therefore $X^X$ under composition is a monoid.

Non-examples of monoids

Worked example 7.1.8

($(Z^+,+)$ is not a monoid)

If $Z^+$ denotes the positive integers, then addition is closed and associative. But there is no identity element inside $Z^+$.

The additive identity would have to be $0$, because $a+0=a$. But $0\notin Z^+$. So $(Z^+,+)$ is not a monoid.

Worked example 7.1.9

($(Z,-)$ is not a monoid)

Subtraction is a binary operation on $Z$, but it is not associative. For example,

$$(5-3)-1=1,$$

while

$$5-(3-1)=3.$$

Since these are not equal, associativity fails. Therefore $(Z,-)$ is not a monoid.

Common mistake

(Having an identity is not enough)

An operation can have a plausible identity and still fail to be a monoid if it is not associative. Associativity and identity are separate requirements.

The identity element is unique

Theorem 7.1.10

(Uniqueness of identity)

A monoid has exactly one identity element.

Proof

Suppose $e$ and $e'$ are both identity elements. Since $e$ is an identity,

$$e*e'=e'.$$

Since $e'$ is an identity,

$$e*e'=e.$$

Therefore

$$e=e*e'=e',$$

so the identity element is unique.

The proof is short because the identity law works on both sides. Each identity must leave the other one unchanged, forcing them to be equal.

Groups

A monoid allows operations to be composed, but does not require them to be reversible. In the two-element example above, $f(a)=f(b)=a$. No function $h$ can satisfy $h\circ f=id_X$: that equation would require the single value $h(a)$ to equal both $a$ and $b$. By contrast, the exchange $g$ satisfies $g\circ g=id_X$ and undoes itself.

Restricting to bijections $X\to X$ removes this obstruction. A composite of bijections is a bijection, $id_X$ is a bijection, and every bijection has an inverse from $X$ to itself. These reversible operations form the model for a group. Symmetries provide geometric examples: they can be composed, include the identity symmetry, and can be reversed. The group axioms express these laws without requiring the elements to be functions.

Definition 7.1.11

(Group)

A group is a set $G$ equipped with an element $e\in G$ and a binary operation

$$(a,b)\longmapsto a\cdot b$$

such that:

• for all $a\in G$,

  $$e\cdot a=a=a\cdot e;$$

• for all $a,b,c\in G$,

  $$(a\cdot b)\cdot c=a\cdot(b\cdot c);$$

• for every $a\in G$, there exists an inverse element $a^{-1}\in G$ satisfying

  $$a\cdot a^{-1}=e \qquad\text{and}\qquad a^{-1}\cdot a=e.$$

Under this standard reading, every group is a monoid after forgetting the inverse axiom. What makes a group stronger is not a different identity or a different associativity law, but the existence of inverses.

Common mistake

(A group is not just any set with a binary operation)

The operation must be associative, there must be a two-sided identity, and every element must have an inverse. If any one of these fails, the structure is not a group.

Examples of groups

The basic examples are:

• $(Z,+)$;
• $(Q,+)$;
• $(Q^+,\cdot)$, where $Q^+$ denotes the positive rationals.

Worked example 7.1.12

(Why $(Z,+)$ is a group)

The identity element is $0$.

For every integer $a$, the inverse is $-a$, since

$$a+(-a)=0=(-a)+a.$$

Addition is associative, so $(Z,+)$ is a group.

Worked example 7.1.13

(Why $(Q^+,\cdot)$ is a group)

The identity element is $1$.

For every positive rational $q$, the inverse is $1/q$, which is again a positive rational. Then

$$q\cdot \frac1q=1=\frac1q\cdot q.$$

Multiplication is associative, so $(Q^+,\cdot)$ is a group.

Common mistake

($(Z,\times)$ is a monoid but not a group)

The identity for multiplication on $Z$ is $1$, and multiplication is associative. But most integers do not have multiplicative inverses in $Z$. For example, there is no integer $b$ such that $2b=1$.

Uniqueness of inverses

Theorem 7.1.14

(Uniqueness of inverses)

For each $a\in G$, the inverse $a^{-1}$ is unique.

Proof

Suppose $b$ and $c$ are both inverses of $a$. Then

$$a*b=e,\qquad b*a=e,$$

and

$$a*c=e,\qquad c*a=e.$$

Using the identity and associativity,

$$b=b*e=b*(a*c)=(b*a)*c=e*c=c.$$

So $b=c$.

The proof shows why inverse notation is legitimate. If an inverse exists, there is only one such element, so writing $a^{-1}$ is unambiguous.

Socks-shoes property

The inverse-of-a-product rule is often called the socks-shoes property: to undo two operations, undo the second one first.

Theorem 7.1.15

(Socks-shoes property)

For elements $a,b$ in a group,

$$(a*b)^{-1}=b^{-1}*a^{-1}.$$

Proof

Compute:

$$(a*b)*(b^{-1}*a^{-1}) =a*(b*b^{-1})*a^{-1} =a*e*a^{-1} =a*a^{-1} =e.$$

The product in the opposite order is also the identity:

$$(b^{-1}*a^{-1})*(a*b) =b^{-1}*(a^{-1}*a)*b =b^{-1}*e*b =b^{-1}*b =e.$$

Thus $b^{-1}*a^{-1}$ is a two-sided inverse of $a*b$. Uniqueness of inverses proves the formula.

The order reversal is essential. In a non-commutative group, $a^{-1}*b^{-1}$ need not undo $a*b$.

Cancellation laws

Theorem 7.1.16

(Cancellation laws)

In a group:

• if $a*b=a*c$, then $b=c$;
• if $b*a=c*a$, then $b=c$.

Left cancellation

Assume

$$a*b=a*c.$$

Multiply on the left by $a^{-1}$:

$$a^{-1}*(a*b)=a^{-1}*(a*c).$$

By associativity,

$$(a^{-1}*a)*b=(a^{-1}*a)*c.$$

Since $a^{-1}*a=e$, this becomes

$$e*b=e*c,$$

and hence $b=c$.

The proof of right cancellation is analogous, multiplying on the right by $a^{-1}$.

One-sided inverses and noncommutativity

The group axioms require a two-sided inverse. For functions, a left inverse $g\circ f=id$ gives injectivity and a right inverse $f\circ h=id$ gives surjectivity; both are needed for a genuine inverse function. In an arbitrary monoid, one-sided inverses need not automatically coincide, so the side on which an equation is multiplied must be recorded.

Theorem 7.1.17

(Two opposite-sided equations identify the inverse)

If $b*a=e=a*c$ in a monoid, then $b=c$; no separate two-sided-inverse assumption is needed because the displayed equations already provide the needed sides. The proof is $b=b*e=b*(a*c)=(b*a)*c=e*c=c$. In a group every element therefore has one well-defined inverse, and both left and right cancellation follow by multiplying on the corresponding side.

Theorem 7.1.18

(Right inverses everywhere force a group)

Let $M$ be a monoid. If every $a\in M$ has a right inverse, choose $b,c\in M$ with $a*b=e$ and $b*c=e$. Then

$$a=a*(b*c)=(a*b)*c=e*c=c,$$

so $b*a=b*c=e$. Thus each right inverse is also a left inverse, and $M$ is a group. The opposite-sided identity is derived from associativity.

Worked example 7.1.19

(The group $GL(2,R)$ is noncommutative)

$GL(2,R)$ is the set of real $2\times2$ matrices with nonzero determinant, under matrix multiplication. Let

$$A=\begin{pmatrix}1&1\\0&1\end{pmatrix}, \qquad B=\begin{pmatrix}1&0\\1&1\end{pmatrix}.$$

Both determinants equal $1$, so both matrices lie in $GL(2,R)$. But

$$AB=\begin{pmatrix}2&1\\1&1\end{pmatrix}, \qquad BA=\begin{pmatrix}1&1\\1&2\end{pmatrix},$$

which are different. Thus associativity does not imply commutativity. The identity is the identity matrix, and each matrix has its usual inverse, so the group axioms still hold.

Common mistake

(Boolean multiplication is not a group)

The Boolean multiplication monoid has identity $1$, but $0$ has no inverse: $0b=0$ for both possible $b$, never $1$. Therefore $(B,\cdot)$ is not a group.

Homomorphisms and isomorphisms

A bijection compares the sizes of two sets, but can ignore their operations. To compare groups, a map must respect multiplication: multiplying first and then applying the map must give the same result as mapping each factor first and multiplying in the target group. This requirement allows algebraic calculations to pass from one group to another.

Definition 7.1.20

(Group homomorphism)

For groups $(G,*)$ and $(H,\star)$, a function $\varphi:G\to H$ is a homomorphism if

$$\varphi(a*b)=\varphi(a)\star\varphi(b)$$

for all $a,b\in G$. It preserves the operation, but it need not be injective or surjective.

Theorem 7.1.21

(Homomorphisms preserve identity and inverses)

If $\varphi:G\to H$ is a homomorphism, then $\varphi(e_G)=e_H$ and $\varphi(a^{-1})=\varphi(a)^{-1}$.

Proof

Since $\varphi(e_G)=\varphi(e_G*e_G)=\varphi(e_G)\star\varphi(e_G)$, multiply by the inverse of $\varphi(e_G)$ in $H$ to obtain $\varphi(e_G)=e_H$. Also, $\varphi(a)\star\varphi(a^{-1})=\varphi(a*a^{-1})=\varphi(e_G)=e_H$, and the same calculation in the opposite order gives the other side. Uniqueness of inverses in $H$ proves the claim.

If a homomorphism is also bijective, no elements are identified or omitted. It gives a reversible relabelling that preserves every product, so the two groups have the same algebraic structure.

Definition 7.1.22

(Isomorphism)

An isomorphism is a bijective group homomorphism. If one exists, write $G\cong H$; the groups have the same operation structure after relabelling.

Symmetric groups and $S_2\cong Z_2$

For a finite set $X$, the symmetric group $S_X$ consists of the bijections $X\to X$ under composition. These are precisely the reversible self-maps considered above. For $X=\{1,\ldots,n\}$, write $S_n$. Cycle notation $(a_1\ a_2\ \cdots\ a_k)$ sends each displayed element to the next, sends $a_k$ to $a_1$, and fixes the elements not displayed.

The elements of $S_2$ are the identity $id$ and the transposition $\tau=(1\ 2)$, with $\tau\circ\tau=id$. Write $Z_2$ for the group $(B,+)$ with Boolean addition defined above. Its addition table and the composition table of $S_2$ have the same pattern: exchanging $id$ for $0$ and $\tau$ for $1$ preserves the operation.

Worked example 7.1.23

(The composition table for $S_2$)

$$\begin{array}{c|cc} \circ&id&\tau\\\hline id&id&\tau\\ \tau&\tau&id \end{array}$$

Define $\varphi:S_2\to Z_2$ by $\varphi(id)=0$ and $\varphi(\tau)=1$. The table shows $\varphi(\sigma\circ\rho)=\varphi(\sigma)+\varphi(\rho)\pmod2$. It is bijective, hence $S_2\cong Z_2$.

Conjugacy: the same operation after relabelling

For permutations, a change of labels also changes the formula for an operation. If $k$ maps the old labels to the new ones, the operation $h$ is represented in the new labels by $k\circ h\circ k^{-1}$: undo the relabelling, apply $h$, and restore the new labels. This expression makes sense in any group, with its multiplication in place of composition.

For a group $G$ and elements $g,h\in G$, define $g\sim h$ if there exists $k\in G$ such that $g=khk^{-1}$. This is conjugacy. Reflexivity follows from $g=ege^{-1}$. If $g=khk^{-1}$, then $h=k^{-1}gk$, proving symmetry. If also $h=\ell j\ell^{-1}$, then $g=(k\ell)j(k\ell)^{-1}$, proving transitivity. Thus conjugacy is an equivalence relation on $G$. Its equivalence classes, called conjugacy classes, partition the group.

The dihedral group $D_8$

For the group of symmetries of a square, conjugacy permits only changes of labels that are themselves square symmetries. The conjugacy classes distinguish reflections in diagonals from reflections in lines through opposite edge midpoints, even though both reverse the orientation of the square.

Label the square's vertices by $1=(1,1)$, $2=(-1,1)$, $3=(-1,-1)$, and $4=(1,-1)$. Let $r=(1\ 2\ 3\ 4)$ be the quarter-turn and let $s=(2\ 4)$ be reflection in the diagonal $y=x$. We compose permutations rightmost first. The eight symmetries are

$$e, r, r^2, r^3, s, rs, r^2s, r^3s.$$

The action on $(1,2,3,4)$ makes the geometric description explicit:

Here $r^4=e$, $s^2=e$, and the geometric reflection relation is $srs=r^{-1}$. These relations describe every product after moving a power of $r$ to the left and using $sr=r^{-1}s$.

Worked example 7.1.24

(Conjugacy classes in $D_8$)

Conjugating a rotation by $s$ sends $r$ to $r^{-1}$, so $r$ and $r^3$ form one class. The element $r^2$ is fixed by both rotations and reflections, so it forms its own class. Conjugating reflections by powers of $r$ gives two families, according to parity of the exponent:

$$\{e\},\qquad \{r^2\},\qquad \{r,r^3\},\qquad \{s,r^2s\},\qquad \{rs,r^3s\}.$$

For example, $r s r^{-1}=r^2s$ and $r(rs)r^{-1}=r^3s$, while conjugation by $s$ reverses the rotation exponent. Conjugation by each generator $r$ and $s$ preserves each displayed set. Since every group element is a product of these generators, no conjugation can move an element into a different displayed set. The calculations above also connect the two members of each two-element set. Thus these sets are exactly the conjugacy classes.

Two homomorphisms involving $S_2$ and $S_3$

There is an inclusion $f:S_2\to S_3$ obtained by letting a permutation of $\{1,2\}$ fix $3$: $f(id)=id$ and $f((1\ 2))=(1\ 2)$. Composition is unchanged, so $f$ is a homomorphism. It is injective but not surjective: a permutation that moves $3$ is not in its image. Preserving the operation therefore does not require covering the target group.

For the reverse direction, put $c=(1\ 2\ 3)$ and $t=(1\ 2)$ in $S_3$. Direct composition gives $c^3=t^2=e$ and $tct=c^{-1}$. The six distinct permutations are $e,c,c^2,t,ct,c^2t$: the last three are respectively $(1\ 2),(1\ 3),(2\ 3)$. Thus each element has a unique form $c^i t^\varepsilon$ with $i\in\{0,1,2\}$ and $\varepsilon\in\{0,1\}$. From $tc=c^{-1}t$,

$$(c^i t^\varepsilon)(c^j t^\delta) =c^{i+(-1)^\varepsilon j}t^{\varepsilon+\delta},$$

where powers of $c$ are reduced modulo three and powers of $t$ modulo two. Define $g(c^i t^\varepsilon)=\tau^\varepsilon$ in $S_2$. The formula shows that the exponent of $t$ adds modulo two, exactly as the exponent of $\tau$ does. Hence $g(\sigma\rho)=g(\sigma)g(\rho)$. This is the parity homomorphism; the elements mapped to the identity are precisely $e,c,c^2$, often denoted $A_3$. This homomorphism is surjective because $g(e)=id$ and $g(t)=\tau$, but it is not injective because $e,c,c^2$ have the same image. The two examples show separately why neither injectivity nor surjectivity is part of the definition.

Check laws interactively

The checker tests closure, associativity, identity, and inverse laws for small operation tables. Compare Boolean addition with Boolean multiplication to see which axiom distinguishes a group from a monoid.

Figure. Monoids and groups both require associativity and an identity. A group also requires every element to have an inverse.

Quick checks

Quick check

(What must be true for a rule $*$ to be a binary operation on a set $X$?)

State the input and output requirement.

Solution · Answer

It must be a function $*:X\times X\to X$. Thus it takes two elements of $X$ as input and returns an element of $X$.

Quick check

(Why is $(Z,-)$ not a monoid?)

Name the failed axiom and give a concrete calculation.

Solution · Answer

Subtraction is not associative. For instance,

$$(5-3)-1=1$$

but

$$5-(3-1)=3.$$

Since the two results differ, $(Z,-)$ is not a monoid.

Quick check

(Why is $(Z,\times)$ not a group?)

Focus on inverses.

Solution · Answer

Although multiplication on $Z$ is associative and has identity $1$, not every integer has a multiplicative inverse in $Z$. For example, no integer $b$ satisfies $2b=1$.

Quick check

(What is the inverse of $a*b$ in a group?)

Pay attention to the order.

Solution · Answer

The inverse is

$$(a*b)^{-1}=b^{-1}*a^{-1}.$$

The order reverses.

Exercises

Exercise 1

Show directly that $(B,+)$ is a monoid using the Boolean addition rule above.

Solution · Hint

Check associativity and identify the identity.

Solution · Guided solution

The identity is $0$, since $0+0=0$, $0+1=1$, $1+0=1$, and therefore $x+0=0+x=x$ for both $x\in B$.

Associativity can be checked by the finite cases $x,y,z\in\{0,1\}$. Boolean addition is addition modulo $2$, so both $(x+y)+z$ and $x+(y+z)$ record the parity of the number of $1$s among $x,y,z$. Hence they agree.

Exercise 2

A binary operation on $X$ has a left identity $e$ and a right identity $f$. Prove that $e=f$ and that this common element is a two-sided identity. Is associativity needed?

Solution · Hint

Evaluate $e*f$ using each identity property separately.

Solution · Model solution

Because $e$ is a left identity, $e*f=f$. Because $f$ is a right identity, $e*f=e$. Hence $e=f$. The common element inherits both identity properties. Associativity is not used: the argument evaluates one product, without regrouping.

Exercise 3

Let $a$ be an element of a monoid with a left inverse $h$, so $h*a=e$. Prove that $a*b=a*c$ implies $b=c$. Explain why a right inverse is not needed.

Solution · Hint

Multiply both sides on the left by $h$, keeping the order fixed.

Solution · Model solution

From $a*b=a*c$, left multiplication by $h$ and associativity give $(h*a)*b=(h*a)*c$. Since $h*a=e$, this reduces to $e*b=e*c$, hence $b=c$. Only the equation $h*a=e$ is used; no equation for $a*h$ is needed.

Related notes

2.2 Functions and relations supplies composition, inverse functions, and the partition theorem for equivalence classes used in conjugacy. The quantifiers in the algebraic axioms use the language of 1.3 Quantifiers and negation.

3.4 Rationals and well-defined operations gives another example of specifying an operation on mathematical objects and checking that it is well-defined. Order relations provide a different kind of extra structure, illustrated in 6.3 Intervals, Cantor set, density, and well-ordering; those results are a comparison, not a prerequisite for the group proofs here.