7.1-7.2 Binary operations, monoids, and groups

Chapter 7 begins with a change in viewpoint.

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.

The point of this chapter is to make that extra structure explicit.

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

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

Boolean integers

The Boolean integers are the triple

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

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

The main point is not the name. The point is that a small set can carry nontrivial structure once operations are specified.

Worked example

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

A useful exercise is to prove

$$\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$.

The last example is worth reading carefully. If $f:X\to X$ and $g:X\to X$, then

$$g\circ f:X\to X.$$

So composition combines two elements of $X^X$ and returns another element of $X^X$.

Worked example

Composition as a binary operation

Let $X=\{a,b\}$. An element of $X^X$ is a function from $X$ to itself.

If $f,g\in X^X$, then $g\circ f$ is again a function from $X$ to itself. Hence composition defines

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

The elements being combined are functions, not elements of $X$.

Monoids

The first structure studied in Chapter 7 is a monoid.

Definition

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

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

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

It is just as important to see operations that fail the definition.

Worked example

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

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

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

Monoids are useful but weak. A group adds the requirement that every element can be undone.

Definition

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

Groups are a natural way to formalize symmetry. A symmetry operation should be composable, have a do-nothing operation, and be reversible.

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

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

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

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

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

By uniqueness of inverses, the inverse of $a*b$ must be $b^\{-1\}*a^\{-1\}$.

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

Cancellation laws

Theorem

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, but in a finite-dimensional setting one-sided identities can be decisive. 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

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

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

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

Definition

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

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.

Definition

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$, $S_X$ is the group of bijections $X\to X$ under composition. Let $S_2$ act on $\{1,2\}$. Its elements are the identity $id$ and the transposition $\tau=(1\ 2)$, with $\tau\circ\tau=id$.

Worked example

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

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

The dihedral group $D_8$

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

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.

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

Check laws interactively

The checker below is a support tool for the definitions: use it to test closure, associativity, identity, and inverse behavior for small operation tables. The mathematics remains the axioms above.

Figure. The distinction between monoid and group is not a naming convention: it is controlled by identity and inverse laws in addition to associativity.

Quick checks

Checkpoint

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

Checkpoint

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.

Checkpoint

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

Checkpoint

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

Read this after 2.2 Functions and relations and 6.4-6.7 Intervals, Cantor set, density, and well-ordering. It also uses proof habits from 1.2 Quantifiers and negation and 3.4 Rationals and well-defined operations.