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:

start with a set;
specify some operation, relation, function, or distinguished element on that set;
state axioms that this extra data must satisfy;
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

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

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

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

Proof

Left cancellation

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

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.

A law table comparing monoids and groups

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

Read and try

Check monoid and group laws

The checker compares binary operations by the exact laws needed for monoids and groups.

This is a group.

Associative

Yes

(a+b)+c = a+(b+c).

Identity

Yes

0 is the identity.

Inverse

Yes

The inverse of a is -a.

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

Quick check

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

Name the failed axiom and give a concrete calculation.

Solution

Answer

Quick check

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

Focus on inverses.

Solution

Answer

Quick check

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

Pay attention to the order.

Solution

Answer

Exercises

Quick check

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

Check associativity and identify the identity.

Solution

Guided solution

Quick check

Prove that the identity element in a monoid is unique.

Use two possible identities e and e'.

Solution

Guided solution

Quick check

Prove left cancellation in a group: if $ab=ac$ , then $b=c$ .

Use the inverse of a.

Solution

Guided solution

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.

7.1-7.2 Binary operations, monoids, and groups

MATH1090: Set theory

Sets with structure

Binary operations

Binary operation

A formula is not automatically a binary operation on every set

Boolean integers

Boolean integers

Solving x+y=0x+y=0x+y=0 in BBB

More examples of binary operations

Composition as a binary operation

Monoids

Monoid

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

Checking the composition monoid

Non-examples of monoids

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

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

Having an identity is not enough

The identity element is unique

Uniqueness of identity

Proof

Groups

Group

A group is not just any set with a binary operation

Examples of groups

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

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

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

Uniqueness of inverses

Uniqueness of inverses

Proof

Socks-shoes property

Socks-shoes property

Proof

Cancellation laws

Cancellation laws

Left cancellation

Check laws interactively

Check monoid and group laws

Quick checks

What must be true for a rule ∗*∗ to be a binary operation on a set XXX?

Answer

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

Answer

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

Answer

What is the inverse of a∗ba*ba∗b in a group?

Answer

Exercises

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

Guided solution

Prove that the identity element in a monoid is unique.

Guided solution

Prove left cancellation in a group: if a∗b=a∗ca*b=a*ca∗b=a∗c, then b=cb=cb=c.

Guided solution

Related notes

Prerequisites

Key terms in this unit

More notes in this series

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

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

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

$(Z,-)$ is not a monoid

Why $(Z,+)$ is a group

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

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

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

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

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

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

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

Prove left cancellation in a group: if $ab=ac$ , then $b=c$ .