Binary Operations and Cayley Tables

Abstract algebra studies operations themselves. You already know many: adding integers, multiplying matrices, adding and multiplying mod n, composing functions. This course asks what all of them have in common, so that one proof can cover every example at once. The first step is to say exactly what an operation is.

Definition. A binary operation on a set $S$ is a function $\ast: S \times S \to S$. It takes an ordered pair $(a, b)$ of elements of $S$ (an element of the Cartesian product $S \times S$) and returns one element $a \ast b$ that is again in $S$. That last requirement is called closure: subtraction is a binary operation on $\mathbb{Z}$, but not on $\mathbb{N} = \{0, 1, 2, \dots\}$, because $1 - 2 \notin \mathbb{N}$.

For a small set we can list every answer in a Cayley table: the entry in row $a$ and column $b$ is $a \ast b$. The order matters, since $a \ast b$ and $b \ast a$ may differ.

Addition mod 5 as a Cayley table. Each cell is tinted by its value, so you can see that every row and every column contains each element exactly once.

Properties you can read off (or not)

Commutative: $a \ast b = b \ast a$ for all $a, b$. In the table this means symmetry across the main diagonal.
Identity: an element $e$ with $e \ast a = a = a \ast e$ for all $a$. Its row and its column copy the headings.
Associative: $(a \ast b) \ast c = a \ast (b \ast c)$ for all $a, b, c$. This one is not visible in the table: for a set with $n$ elements there are $n^{3}$ triples to check.

Why it works

Why care about associativity? It is what lets us drop parentheses and write $a \ast b \ast c \ast d$: every way of grouping gives the same answer. Without it, even $a \ast a \ast a$ is ambiguous. Every operation we build groups from will be associative, and the reason is usually that it comes from something already associative: addition and multiplication of numbers, multiplication of matrices, or composition of functions, where $(f \circ g) \circ h$ and $f \circ (g \circ h)$ both send $x$ to $f(g(h(x)))$.

Worked example: Reading a table, both ways

On $S = \{a, b, c\}$ the table gives $a \ast b = c$ (row $a$, column $b$) and $b \ast a = a$ (row $b$, column $a$). Is $\ast$ commutative?

Commutativity needs $x \ast y = y \ast x$ for every pair.
Here $a \ast b = c$ but $b \ast a = a$.
One failing pair is enough.

Answer: No: $a \ast b \ne b \ast a$.

Worked example: Testing associativity with a formula

On $\mathbb{Z}$ define $a \ast b = a + b + ab$. Is it associative?

Notice $1 + (a \ast b) = 1 + a + b + ab = (1 + a)(1 + b)$.
So $1 + ((a \ast b) \ast c) = (1 + a)(1 + b)(1 + c)$, and the same for $1 + (a \ast (b \ast c))$.
Both groupings give the same number, because multiplication of integers is associative.

Answer: Yes, it is associative (and commutative).

Worked example: A commutative operation that is not associative

On $\mathbb{Z}$ define $a \ast b = |a - b|$. Check commutativity and associativity.

$|a - b| = |b - a|$, so it is commutative.
Try $1, 2, 3$: $(1 \ast 2) \ast 3 = 1 \ast 3 = 2$, but $1 \ast (2 \ast 3) = 1 \ast 1 = 0$.

Answer: Commutative but not associative.

Common mistake

Reading $b \ast a$ when you want $a \ast b$. The row is the left factor and the column is the right factor. A second trap: a symmetric table proves commutativity, not associativity. The example $|a - b|$ has a perfectly symmetric table and still fails associativity, so test triples, or find a reason like the $(1 + a)(1 + b)$ trick above.

Key idea

A binary operation on $S$ sends each ordered pair of elements of $S$ to an element of $S$. A Cayley table lists all the answers (row $a$, column $b$ gives $a \ast b$); commutativity and identities show up in the table, but associativity has to be checked on triples or proved.

Binary Operations and Cayley Tables

Properties you can read off (or not)

Practice

Builds on

Leads to

Sources and further reading