Binary operations

Addition, multiplication, union, and composition are all examples of a common pattern: take two elements of a set and produce a third element of the same set. That pattern is called a binary operation. Studying it abstractly reveals the common structure behind apparently unrelated processes , and previews the algebraic notion of a group, which dominates higher mathematics.

Definition

A binary operation on a set $A$ is a function

$\ast : A \times A \to A.$

We typically write $a \ast b$ instead of $\ast(a, b)$. The key requirement is that $A$ is closed under $\ast$: combining two elements of $A$ must give another element of $A$.

A binary operation $\ast$ on $A$ is

• commutative if $a \ast b = b \ast a$ for all $a, b \in A$;
• associative if $(a \ast b) \ast c = a \ast (b \ast c)$ for all $a, b, c \in A$;
• has an identity element $e \in A$ if $a \ast e = e \ast a = a$ for all $a \in A$;
• $b$ is an inverse of $a$ if $a \ast b = b \ast a = e$.

Identity and inverse: uniqueness

If $\ast$ has an identity, it is unique. Proof: if $e$ and $e'$ are both identities, then $e = e \ast e' = e'$, using each one's identity property in turn.

If $\ast$ is associative and has identity $e$, and $a$ has an inverse, that inverse is unique. Proof: if $b$ and $b'$ are both inverses of $a$, then $b = b \ast e = b \ast (a \ast b') = (b \ast a) \ast b' = e \ast b' = b'$.

Common examples

The last row reveals that composition is a binary operation on the set of bijections of $A$, and that set forms a group , the symmetric group on $A$.

Cayley tables

For a finite set we can record a binary operation as a table, called the Cayley table. For example, $\ast$ on $\{e, a, b\}$:

Here $e$ is the identity, $a^{-1} = b$, $b^{-1} = a$. Reading off properties from a Cayley table is a frequent exercise.

Worked examples

Example 1. Define $\ast$ on $\mathbb{Q}$ by $a \ast b = a + b - ab$. Check commutativity, associativity, identity.

Commutative: $b + a - ba = a + b - ab$. Yes.

Associative: $(a \ast b) \ast c = (a + b - ab) \ast c = (a + b - ab) + c - (a + b - ab)c = a + b + c - ab - ac - bc + abc$. Compute $a \ast (b \ast c) = a \ast (b + c - bc) = a + b + c - bc - a(b + c - bc) = a + b + c - ab - ac - bc + abc$. Equal. Yes.

Identity: solve $a \ast e = a$: $a + e - ae = a \Rightarrow e(1 - a) = 0$. For this to hold for all $a$, we need $e = 0$. Check: $0 \ast b = b$. Yes.

Inverse of $a$: solve $a \ast b = 0$: $a + b - ab = 0 \Rightarrow b(1 - a) = -a \Rightarrow b = a/(a - 1)$, defined for $a \neq 1$. So every $a \neq 1$ has inverse $a/(a - 1)$; $a = 1$ has no inverse.

Example 2. On $\mathbb{N}$ define $a \ast b = \gcd(a, b)$. Show $\ast$ is commutative and associative. Does an identity exist?

Commutative: $\gcd(a, b) = \gcd(b, a)$. Yes.

Associative: $\gcd(\gcd(a, b), c) = \gcd(a, \gcd(b, c))$. Yes (both equal $\gcd(a, b, c)$).

Identity: need $\gcd(a, e) = a$ for all $a$, so $e$ must be a multiple of every $a$. No such natural number exists. (If we allowed $e = 0$, then $\gcd(a, 0) = a$ works, and $0$ is the identity in $\mathbb{Z}_{\ge 0}$.)

Example 3. Let $\ast$ on $\mathbb{Z}$ be $a \ast b = a + b + 1$. Identity? Inverse of $a$?

$a \ast e = a + e + 1 = a \Rightarrow e = -1$. Inverse: $a \ast b = -1 \Rightarrow b = -2 - a$. So every element has inverse.

Example 4. Define $\ast$ on the set $A = \{1, 2, 3, 4, 5\}$ by $a \ast b = \min\{a, b\}$. Is $\ast$ commutative, associative, and does it have an identity?

Commutative: yes. Associative: $\min(\min(a, b), c) = \min(a, b, c) = \min(a, \min(b, c))$. Yes. Identity: need $\min(a, e) = a$, so $e \ge a$ for every $a$. The only candidate is $e = 5$. Check: $\min(a, 5) = a$. Yes.

Inverses: $\min(a, b) = 5$ forces both $a, b \ge 5$, so only $5 \ast 5 = 5$. Hence only $5$ has an inverse (itself), and the structure is a monoid, not a group.

Example 5. Define $\ast$ on $\mathbb{R}^2$ by $(a, b) \ast (c, d) = (a + c, b + d)$. Show this is a binary operation with identity $(0, 0)$ and inverses $(a, b)^{-1} = (-a, -b)$.

Straightforward.

Example 6. On the set of all $2 \times 2$ matrices with real entries, matrix multiplication is a binary operation. Is it commutative? Identity? Always invertible?

Not commutative in general. Identity: the matrix $I_2$. Not every matrix is invertible , only those with nonzero determinant.

Try it yourself

1. On $\mathbb{Z}$, define $a \ast b = a + b - 5$. Find identity and inverse of $a$.
2. On $\mathbb{Q}$, define $a \ast b = (a + b)/2$. Commutative? Associative? Identity?
3. On the set of all subsets of $X$, is symmetric difference $A \triangle B$ associative? Commutative? Identity?
4. Construct a Cayley table for $\ast$ on $\{a, b\}$ with $a \ast a = a, a \ast b = b, b \ast a = b, b \ast b = a$. Identity?
5. On $\mathbb{Z}_5 = \{0, 1, 2, 3, 4\}$, define $\ast$ by $a \ast b = (a + b) \bmod 5$. Identity? Inverse of $3$?
6. Show that for $\ast$ on $\mathbb{Z}$ defined by $a \ast b = a$ (left projection), $\ast$ is associative but has no two-sided identity.
7. On the set $\{1, -1, i, -i\}$ with usual complex multiplication, write the Cayley table. Identity? Inverses?
8. On $\mathbb{R} \setminus \{-1\}$, define $a \ast b = a + b + ab$. Show $\ast$ is commutative and associative, identity is $0$, and $a^{-1} = -a/(a + 1)$.
9. Define $\ast$ on $\mathbb{Z}_+$ by $a \ast b = a^b$. Is it commutative? Associative? (Check carefully.)
10. Show that subtraction is not associative on $\mathbb{Z}$.
11. On $\mathbb{N}$, is $\ast$ defined by $a \ast b = a + 2b$ commutative? Associative?
12. Suppose $\ast$ has identity $e$. Show $e \ast e = e$.
13. Show: if $\ast$ is associative and every element has a left inverse, then every left inverse is also a right inverse, provided an identity exists.
14. Construct a binary operation on $\{1, 2, 3\}$ that has no identity element.

Pitfalls / Tricks

• Always check closure first. If $a \ast b$ can land outside $A$, $\ast$ is not a binary operation on $A$.
• "Identity" is a two-sided requirement: $e \ast a = a \ast e = a$ for all $a$.
• Inverses are defined only when an identity exists. Asking for an inverse of $a$ in a monoid that has no identity is meaningless.
• A binary operation can have a left identity but no right identity, or vice versa. The "left projection" $a \ast b = a$ has every element as a right identity but no left identity.
• A Cayley table is symmetric across the main diagonal exactly when $\ast$ is commutative.

This concludes Chapter 1. The themes , well-defined operations, identities, inverses , return in matrices, determinants, and (under the name group) throughout your future mathematics.