Chapter 23 — Operations and Relations
Table of Contents
23.1 Binary Operations
Definition. A binary operation takes two elements and produces a result. Familiar binary operations include $+$, $-$, $\times$, $/$. But on competitions, you often see invented operations with symbols like $\oplus$, $\star$, $#$, $@$, etc.
Example 23-1. If $a \star b = 3a + b - ab$, find $2 \star 5$.
\(2 \star 5 = 3(2) + 5 - (2)(5) = 6 + 5 - 10 = 1.\)
Example 23-2. If $a \star b = 3a + b - ab$, find $4 \star (2 \star 5)$.
We already know $2 \star 5 = 1$, so:
\(4 \star 1 = 3(4) + 1 - (4)(1) = 12 + 1 - 4 = 9.\)
Exercise 23-1. Using $a \star b = 3a + b - ab$, find $3 \star (4 \star 2)$ and $(3 \star 4) \star 2$.
Exercise 23-2. Using $a \star b = 3a + b - ab$, find $x$ if $3 \star x = 12$.
23.2 Properties of Operations
Operations can have various structural properties, which tell us how flexibly we can rearrange expressions.
Commutativity
An operation $\star$ is commutative if:
\[a \star b = b \star a \quad \text{for all } a, b.\]Example: Addition and multiplication are commutative. Subtraction and division are not $(5 - 3 \neq 3 - 5)$.
Exercise 23-3. Is $a \star b = 3a + b - ab$ commutative? Prove or give a counterexample.
Associativity
An operation $\star$ is associative if:
\[(a \star b) \star c = a \star (b \star c) \quad \text{for all } a, b, c.\]Example: Addition is associative: $(2 + 3) + 4 = 2 + (3 + 4) = 9$. Subtraction is not: $(5 - 3) - 1 = 1 \neq 5 - (3 - 1) = 3$.
Without associativity, expressions like $a \star b \star c$ are ambiguous — the result depends on grouping.
Exercise 23-4. Prove/disprove that $a \star b = 3a + b - ab$ is associative.
Distributivity
An operation $\star$ distributes over another operation $\Diamond$ if:
\[a \star (b \;\Diamond\; c) = (a \star b) \;\Diamond\; (a \star c).\]Example: Multiplication distributes over addition: $a \cdot (b + c) = ab + ac$. Addition does not distribute over multiplication: $a + (b \cdot c) \neq (a + b)(a + c)$.
Exercise 23-5. Does $a \star b = 3a + b - ab$ distribute over addition?
Identity Element
An identity element $e$ for operation $\star$ satisfies:
\[a \star e = e \star a = a \quad \text{for all } a.\]Examples: $0$ is the identity for $+$, and $1$ is the identity for $\times$.
Uniqueness of the Identity. If both $e$ and $f$ are identity elements for $\star$, then $e = e \star f = f$. So the identity element, if it exists, is unique.
Exercise 23-6. Find the identity element for $a \star b = 3a + b - ab$, or show that none exists.
Inverse
An inverse of $a$ under operation $\star$ (with identity $e$) is an element $a^{-1}$ such that:
\[a \star a^{-1} = a^{-1} \star a = e.\]Example: Under $+$, the inverse of $a$ is $-a$. Under $\times$, the inverse of $a \neq 0$ is $1/a$.
Uniqueness of Inverses (if $\star$ is associative). If $b$ and $c$ are both inverses of $a$:
\[b = b \star e = b \star (a \star c) = (b \star a) \star c = e \star c = c.\]So inverses are unique whenever the operation is associative.
The Big Picture — Abstract Algebra.
When an operation has all nice properties (closure, associativity, identity, inverses), the structure is called a group. If commutativity also holds, it’s an abelian group.
The integers under addition form a group. The nonzero rationals under multiplication form a group. Abstract algebra studies these structures in full generality.
23.3 Relations
A relation is a rule that tells us whether a given pair of objects is “related.” We write $a \sim b$ (or use other symbols) to say $a$ is related to $b$.
A relation on a set is formally a subset of all ordered pairs from that set.
Properties of Relations
A relation $\sim$ on a set $S$ is:
| Property | Meaning | Example | |—|—|—| | Reflexive | $a \sim a$ for all $a \in S$ | $=, \leq, \geq$ | | Symmetric | $a \sim b \Rightarrow b \sim a$ | $=$ | | Transitive | $a \sim b$ and $b \sim c \Rightarrow a \sim c$ | $=, <, \leq$ |
Examples.
- $=$ is reflexive, symmetric, and transitive.
- $<$ is not reflexive ($a \not< a$), not symmetric, but is transitive.
- $\leq$ is reflexive and transitive but not symmetric (since $3 \leq 5$ but $5 \not\leq 3$).
- $\neq$ is symmetric, not reflexive, and not transitive ($1 \neq 2$ and $2 \neq 1$, but $1 = 1$).
Equivalence Relations
A relation that is reflexive, symmetric, and transitive is called an equivalence relation. It partitions the set into “equivalence classes” — groups of mutually related elements.
Example. “Has the same remainder when divided by 3” is an equivalence relation on the integers:
- Reflexive: $a$ has the same remainder as $a$.
- Symmetric: if $a$ and $b$ have the same remainder, $b$ and $a$ do too.
- Transitive: if $a, b$ share a remainder and $b, c$ share a remainder, so do $a, c$.
The equivalence classes are ${…, -3, 0, 3, 6, …}$, ${…, -2, 1, 4, 7, …}$, ${…, -1, 2, 5, 8, …}$.
Exercise 23-7. Define a relation on the integers by $a \sim b$ iff $a - b$ is even. Is this an equivalence relation? What are the equivalence classes?
Exercise 23-8. “Is a factor of” is a relation on positive integers. Which properties (reflexive, symmetric, transitive) does it satisfy?
Problems to Solve for Chapter 23
Problem 429. Given the operation $x \otimes y = xy - 3(x+y) + 9$, show that $x \otimes y = (x-3)(y-3)$.
Problem 430. (Continued) Find the identity of $\otimes$ and find the $\otimes$-inverse of $x$ (if it exists).
Problem 431. If $a # b = a + b + ab$, determine commutativity and associativity:
(a) Is $#$ commutative?
(b) Is $#$ associative?
(c) Find the identity.
(d) Given $a$, find $a^{-1}$ under $#$.
Problem 432. The operation $\circledast$ is defined by $a \circledast b = a^b$. Determine commutativity and associativity.
Problem 433. Show that if $\sim$ is a relation on a set such that $a \sim b$ and $b \sim a$ for all $a, b$, then reflexivity follows from symmetry and transitivity. Under what conditions does this argument fail?