1. What a relation is
Let $A$ and $B$ be sets. Their Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ with $a \in A$ and $b \in B$. A relation is, simply, a subset of that product.
A relation from $A$ to $B$ is any subset $R \subseteq A \times B$. We write $a \mathrel{R} b$ as shorthand for $(a, b) \in R$. A relation on $A$ is a subset $R \subseteq A \times A$ — both coordinates come from the same set.
That definition is intentionally lean. A relation is just a collection of pairs. There's no implicit law, no formula, no "rule" lurking behind it. Whether two elements are related is decided one pair at a time: either the pair sits in $R$, or it doesn't.
The power of the definition is that it covers everything. "Less than or equal to" on $\mathbb{R}$ is the set $\{(a, b) \in \mathbb{R}^2 \mid a \leq b\}$. "Is a subset of" on $\mathcal{P}(X)$ is the set $\{(S, T) \mid S \subseteq T\}$. "Has the same birthday as" on a group of people is the set of pairs sharing a date. Each of these is a relation, and the same vocabulary applies to all of them.
Examples
- $=$ on any set $A$ — the pairs $(a, a)$.
- $\leq$ on $\mathbb{R}$ — the half-plane above the diagonal.
- "$n \mid m$" on $\mathbb{N}_{\geq 1}$ — divisibility.
- "$\ell_1 \parallel \ell_2$" on lines in the plane.
- Edges of a graph — a relation on the vertex set.
- $(3, 5) \in {<}$
- $3 \mathrel{<} 5$
- "$3$ is less than $5$"
If $|A| = m$ and $|B| = n$, then $|A \times B| = mn$, and every subset of $A \times B$ is a relation — so there are $2^{mn}$ relations from $A$ to $B$. Most are random-looking; the interesting ones are the few that satisfy nice properties.
Domain, range, inverse
For a relation $R \subseteq A \times B$:
- The domain is $\{a \in A \mid \exists b,\ (a, b) \in R\}$ — the first-coordinates that appear.
- The range (or image) is $\{b \in B \mid \exists a,\ (a, b) \in R\}$ — the second-coordinates that appear.
- The inverse relation $R^{-1} \subseteq B \times A$ is $\{(b, a) \mid (a, b) \in R\}$. Flip every pair.
For "$<$" on $\mathbb{N}$, the inverse is "$>$". For divisibility, the inverse is "is a multiple of." Inverting a relation costs nothing — it's just bookkeeping.
2. Properties of relations on a set
When $R$ relates a set $A$ to itself, four properties are worth naming. Each is a universal statement about every element (or pair, or triple) of $A$.
| Property | Definition | Says, in words |
|---|---|---|
| Reflexive | $\forall a \in A,\ (a, a) \in R$ | Every element is related to itself. |
| Symmetric | $(a, b) \in R \Rightarrow (b, a) \in R$ | Direction doesn't matter. |
| Antisymmetric | $(a, b), (b, a) \in R \Rightarrow a = b$ | Two-way arrows only happen on the diagonal. |
| Transitive | $(a, b), (b, c) \in R \Rightarrow (a, c) \in R$ | Chains close up. |
A relation can have any combination of these. Each gets checked the same way: assume the hypothesis, derive the conclusion (to prove it); or exhibit a counterexample (to refute it).
A quick tour
- $=$ on $\mathbb{R}$ has all four — and is the prototype.
- $\leq$ on $\mathbb{R}$ is reflexive, transitive, antisymmetric, but not symmetric. $3 \leq 5$ doesn't imply $5 \leq 3$.
- $<$ on $\mathbb{R}$ is transitive, but neither reflexive ($3 \not< 3$) nor symmetric. It is antisymmetric, vacuously.
- "Same birthday as" on a set of people is reflexive, symmetric, transitive — but not antisymmetric (two different people can share a birthday).
- "Is a friend of", usual interpretation: symmetric, often not transitive, rarely reflexive. Not a member of any famous family.
Antisymmetric and symmetric are not opposites. The relation $\{(a, a)\}$ on $\{a\}$ is both. A relation can also be neither. Antisymmetric is a positive statement: whenever both $(a, b)$ and $(b, a)$ are present, the two elements are forced to coincide.
3. Equivalence relations and partitions
The most important named combination of properties — and the one that powers a huge amount of higher mathematics.
A relation $\sim$ on $A$ that is reflexive, symmetric, and transitive. The equivalence class of $a \in A$ is
$$ [a] = \{x \in A \mid x \sim a\}, $$the set of everything related to $a$. The collection of all equivalence classes is the quotient set, written $A/{\sim}$.
The point of an equivalence relation is to make precise the act of "regarding two things as the same." Fractions $\tfrac{1}{2}$ and $\tfrac{2}{4}$ aren't literally the same pair of integers, but they represent the same rational number. Two integers can leave the same remainder mod $n$ without being equal. Two geometric shapes can be congruent without being identical. Each of these is an equivalence relation in disguise — and the corresponding rational, residue, or congruence class is what you actually want to talk about.
The partition theorem
A partition of $A$ is a collection of disjoint, nonempty subsets of $A$ whose union is all of $A$. Every element of $A$ sits in exactly one block.
Equivalence relations on $A$ and partitions of $A$ are the same data, viewed two ways.
Given an equivalence relation $\sim$, the equivalence classes $\{[a] \mid a \in A\}$ form a partition. Given a partition $\mathcal{P}$, define $a \sim b$ to mean "$a$ and $b$ are in the same block" — that's an equivalence. The two constructions are mutual inverses.
Why classes don't overlap: suppose $[a] \cap [b] \neq \varnothing$ — pick $c$ in both. Then $c \sim a$ and $c \sim b$, so by symmetry and transitivity $a \sim b$, which means $[a] = [b]$. Two classes are either identical or disjoint. Nothing in between.
Worked example: congruence mod $n$
On the integers, declare $a \sim b$ when $n$ divides $a - b$. This is the relation usually written $a \equiv b \pmod{n}$. Check the three axioms:
- Reflexive. $n \mid (a - a) = 0$, always. ✓
- Symmetric. If $n \mid (a - b)$, then $n \mid (b - a) = -(a - b)$. ✓
- Transitive. If $n \mid (a - b)$ and $n \mid (b - c)$, then $n \mid \bigl((a - b) + (b - c)\bigr) = (a - c)$. ✓
So $\equiv \pmod{n}$ is an equivalence. The classes are $[0], [1], \ldots, [n-1]$, the familiar residue classes. The quotient set $\mathbb{Z}/n\mathbb{Z}$ has $n$ elements. That entire construction — the foundation of modular arithmetic, of finite cyclic groups, of $\mathbb{F}_p$ — is one application of the partition theorem.
$[a]$ is the set of everything equivalent to $a$. It contains $a$, but $[a] \neq a$. When you later define operations on classes — like adding $[3] + [5]$ in $\mathbb{Z}/7\mathbb{Z}$ — you're operating on sets, and you have to check that the answer doesn't depend on which representative you pick. That well-definedness check is non-negotiable.
4. Partial and total orders
Swap symmetry for antisymmetry and you get the other great combination.
A relation $\leq$ on $A$ that is reflexive, antisymmetric, and transitive. The set $A$ together with the order is called a partially ordered set, or poset.
A total (or linear) order adds one more requirement: comparability — for every $a, b \in A$, either $a \leq b$ or $b \leq a$.
The standard $\leq$ on $\mathbb{R}$ is the canonical total order: any two reals can be compared. But many natural orderings are partial: $\subseteq$ on the power set $\mathcal{P}(X)$ is reflexive, antisymmetric, transitive — but $\{1\}$ and $\{2\}$ are incomparable, neither one a subset of the other. Likewise, divisibility on $\mathbb{N}_{\geq 1}$ is a partial order with incomparable pairs ($2$ and $3$, $4$ and $9$).
| Relation | Reflexive | Antisym. | Transitive | Total? |
|---|---|---|---|---|
| $\leq$ on $\mathbb{R}$ | ✓ | ✓ | ✓ | Total |
| $\subseteq$ on $\mathcal{P}(\{1,2,3\})$ | ✓ | ✓ | ✓ | Partial only |
| $\mid$ on $\mathbb{N}_{\geq 1}$ | ✓ | ✓ | ✓ | Partial only |
| $<$ on $\mathbb{R}$ | ✗ | ✓ (vac.) | ✓ | Strict order |
The point of partial orders is exactly that they accept incomparability. You don't have to force a ranking between two subsets of an arbitrary set, or between $2$ and $3$ under divisibility — they just sit beside each other, neither above nor below. Hierarchies, dependency graphs, type systems, subset lattices: all live in the partial-order world.
To draw a finite poset, place each element as a dot and connect $a$ upward to $b$ iff $a < b$ and nothing sits strictly between them. The result is a Hasse diagram — a picture that captures the order without drawing every transitive arrow.
5. Functions as special relations
In algebra and precalculus you met functions as rules: $f(x) = 2x + 3$, "double and add three." That picture works, but it leaves "rule" undefined. Here is the definition that doesn't.
A function $f \colon A \to B$ is a relation $f \subseteq A \times B$ such that:
- Total. For every $a \in A$, there exists $b \in B$ with $(a, b) \in f$.
- Single-valued. If $(a, b) \in f$ and $(a, b') \in f$, then $b = b'$.
Equivalently: each $a \in A$ appears as the first coordinate of exactly one pair in $f$. The unique $b$ that comes with it is written $f(a)$.
That's the entire definition. A function is a relation with two extra constraints — every input shows up, and never more than once. Everything else — the "rule," the formula, the graph — is recovered from this.
The graph of an algebraic function $f \colon \mathbb{R} \to \mathbb{R}$, the curve you'd draw on paper, is literally the set $\{(x, f(x)) \mid x \in \mathbb{R}\}$. So the function and its graph are the same object, just with different names. The vertical line test from precalc — "no vertical line hits the curve twice" — is exactly the single-valued condition translated into pictures.
What the formal view adds
A function carries three pieces of data: a domain $A$, a codomain $B$, and the set of pairs. Change any one and you have a different function — even with the same formula.
- $f \colon \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$ — not surjective, not injective.
- $f \colon \mathbb{R} \to [0, \infty)$, $f(x) = x^2$ — surjective, still not injective.
- $f \colon [0, \infty) \to [0, \infty)$, $f(x) = x^2$ — bijective. Has an inverse, $\sqrt{\cdot}$.
All three have the formula $f(x) = x^2$. They are three different functions, with three different properties. The algebra-class shorthand "let $f(x) = x^2$" hides this — fine when context is clear, dangerous when it isn't.
Once a function is a set, you can prove things about it by manipulating sets. "Composition is associative" becomes a one-line argument about elements of $A \times C$. "A bijection has an inverse" becomes "the inverse relation $f^{-1}$ is already a function." The formal view trades intuition for portability: it works in places — quotient sets, function spaces, category theory — where the "rule" picture has nothing to say.
Non-examples
- $\{(1, 2), (1, 3)\}$ as a relation $\{1\} \to \mathbb{N}$ — input $1$ has two outputs.
- "$y$ is a number whose square is $x$" on $[0, \infty)$ — for $x = 9$, both $y = 3$ and $y = -3$ satisfy. Pick a branch ($\sqrt{x}$) to recover a function.
- $f(x) = 1/x$ on $\mathbb{R}$ — undefined at $0$. Restrict the domain to $\mathbb{R} \setminus \{0\}$ and it becomes a function.
- "The next prime after $n$" on $\mathbb{N}$ is a function; "the previous prime before $n$" on $\mathbb{N}$ is not, because there is none before $2$.
6. Injective, surjective, bijective
Three properties a function can have. Each one is a precise statement about how the function uses its codomain.
A function $f \colon A \to B$ is:
- Injective (one-to-one) when $f(a_1) = f(a_2) \Rightarrow a_1 = a_2$ — different inputs always give different outputs.
- Surjective (onto) when for every $b \in B$ there is some $a \in A$ with $f(a) = b$ — every codomain element is hit.
- Bijective when it is both — a perfect pairing between $A$ and $B$.
Some quick examples on familiar territory:
- $f \colon \mathbb{R} \to \mathbb{R}$, $f(x) = 2x + 3$ — bijective. Solve $y = 2x + 3$ for $x$ to get the inverse $f^{-1}(y) = (y - 3)/2$.
- $f \colon \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$ — neither. $f(-1) = f(1)$ kills injectivity; no negative output kills surjectivity.
- $f \colon \mathbb{N} \to \mathbb{N}$, $f(n) = 2n$ — injective (different $n$ give different doubles), not surjective (no odd number is hit).
- $f \colon \mathbb{Z} \to \mathbb{N}$, $f(n) = |n|$ — surjective, not injective.
The range $f(A)$ is the set of outputs the function actually produces. The codomain $B$ is the set you declared as the target. $f$ is surjective exactly when the two coincide. Changing $B$ — without touching the formula — can flip a function between surjective and not. Pin down the codomain before you make a claim.
7. Composition and inverses
Given $f \colon A \to B$ and $g \colon B \to C$, the composition $g \circ f \colon A \to C$ is
$$ (g \circ f)(a) = g(f(a)). $$Right-to-left: $f$ runs first, then $g$. As sets of pairs:
$$ g \circ f = \{(a, c) \in A \times C \mid \exists b \in B,\ (a, b) \in f \text{ and } (b, c) \in g\}. $$Composition is associative — $h \circ (g \circ f) = (h \circ g) \circ f$ — but generally not commutative. If $f(x) = x + 1$ and $g(x) = 2x$, then $(g \circ f)(x) = 2x + 2$ while $(f \circ g)(x) = 2x + 1$.
The identity function $\mathrm{id}_A \colon A \to A$ sends each $a$ to itself; it's the neutral element for composition: $f \circ \mathrm{id}_A = f$ and $\mathrm{id}_B \circ f = f$.
Inverses
Every relation has an inverse — flip the pairs. The question is whether that inverse is itself a function.
- If $f$ is not injective, two inputs $a_1 \neq a_2$ share an output $b$. In $f^{-1}$ that becomes two pairs with first coordinate $b$ — failing single-valuedness.
- If $f$ is not surjective, some $b \in B$ has no preimage. In $f^{-1}$ that $b$ never appears as a first coordinate — failing totality.
So:
$f^{-1}$ is a function from $B$ to $A$ if and only if $f$ is bijective.
Stated differently: a function has a (two-sided) inverse exactly when it's a bijection. When it does, $f^{-1} \circ f = \mathrm{id}_A$ and $f \circ f^{-1} = \mathrm{id}_B$.
In algebra you "solve $y = f(x)$ for $x$" to find an inverse. That works exactly when the function is bijective on the relevant domains. Restricting the domain to make a function bijective is what creates inverse trig: $\sin$ on all of $\mathbb{R}$ has no inverse; $\sin$ restricted to $[-\pi/2, \pi/2]$ is bijective onto $[-1, 1]$, and that restriction is $\arcsin$.
8. Common pitfalls
The classic trap: from $a \sim b$, symmetry gives $b \sim a$, then transitivity gives $a \sim a$. But this only works if $a$ is related to something. An isolated element with no edges is not reflexively related to itself. Reflexivity must be checked separately. (This is why equivalence relations list all three axioms.)
$[a]$ is the set of everything equivalent to $a$. Writing $[a] = a$ or treating $[a]$ as a single number leads to nonsense — especially in modular arithmetic, where operations are on classes and well-definedness must be checked for each new operation.
Antisymmetric: if both $(a, b)$ and $(b, a)$ are in $R$, then $a = b$ (reflexive pairs are allowed). Asymmetric: $(a, b) \in R$ forces $(b, a) \notin R$ (no reflexive pairs possible). $\leq$ is antisymmetric; $<$ is asymmetric.
$f(x) = x^2$ is a rule. A function needs a domain and codomain as well. The same formula can give a non-injective, non-surjective function on $\mathbb{R} \to \mathbb{R}$ and a bijection on $[0, \infty) \to [0, \infty)$. Don't make claims about injectivity or surjectivity without nailing down the three pieces.
$f^{-1}(T)$ for a set $T \subseteq B$ is the preimage $\{a \in A \mid f(a) \in T\}$ — always defined, even when $f$ has no inverse function. $f^{-1}(b)$ for a single $b \in B$ is ambiguous: either the preimage (a set, possibly empty or large) or the inverse function evaluated at $b$ (a single element, only when $f$ is bijective). Read carefully in context.
$g \circ f$ means "first $f$, then $g$" — right to left, the opposite of how reading goes. $(g \circ f)(x) = g(f(x))$, never $f(g(x))$. Composition is not commutative in general; swap the order and you usually get a different function.
9. Worked examples
Example 1 · Show that "$a \sim b$ iff $a^2 = b^2$" on $\mathbb{R}$ is an equivalence, and describe its classes
Reflexive. $a^2 = a^2$ for all $a$. ✓
Symmetric. If $a^2 = b^2$, then $b^2 = a^2$. ✓
Transitive. If $a^2 = b^2$ and $b^2 = c^2$, then $a^2 = c^2$. ✓
So $\sim$ is an equivalence relation. The class of $a$ is
$$ [a] = \{x \in \mathbb{R} \mid x^2 = a^2\} = \{a, -a\}. $$For $a = 0$ that's the singleton $\{0\}$; for any other $a$ it's a two-element set. The quotient set $\mathbb{R}/{\sim}$ is in bijection with $[0, \infty)$ — each nonnegative real represents one class, namely $\{r, -r\}$.
Example 2 · Is divisibility on $\mathbb{N}_{\geq 1}$ a partial order? A total order?
Define $a \mid b$ to mean "there exists $k \in \mathbb{N}_{\geq 1}$ with $b = ka$."
Reflexive. $a = 1 \cdot a$, so $a \mid a$. ✓
Antisymmetric. If $a \mid b$ and $b \mid a$, write $b = ka$ and $a = \ell b$. Then $a = \ell k a$, so $\ell k = 1$. In positive integers that forces $\ell = k = 1$, hence $a = b$. ✓
Transitive. If $b = ka$ and $c = \ell b$, then $c = (\ell k) a$, so $a \mid c$. ✓
So divisibility is a partial order. Not total: $2 \nmid 3$ and $3 \nmid 2$, so $2$ and $3$ are incomparable.
Example 3 · Show $f \colon \mathbb{R} \to \mathbb{R}$, $f(x) = 3x - 7$ is bijective and find its inverse
Injective. Suppose $f(a_1) = f(a_2)$. Then $3a_1 - 7 = 3a_2 - 7$, so $3a_1 = 3a_2$, so $a_1 = a_2$. ✓
Surjective. Given any $y \in \mathbb{R}$, set $x = (y + 7)/3$. Then $f(x) = 3 \cdot \tfrac{y+7}{3} - 7 = y$. ✓
So $f$ is bijective. The inverse is the function we just constructed in the surjectivity step:
$$ f^{-1}(y) = \frac{y + 7}{3}. $$Check. $f^{-1}(f(x)) = \tfrac{(3x - 7) + 7}{3} = x$, and $f(f^{-1}(y)) = 3 \cdot \tfrac{y+7}{3} - 7 = y$. ✓
Example 4 · Compose $f(x) = x^2 + 1$ and $g(x) = 2x - 3$ both ways, on $\mathbb{R} \to \mathbb{R}$
$g \circ f$: apply $f$ first, then $g$.
$$ (g \circ f)(x) = g(f(x)) = g(x^2 + 1) = 2(x^2 + 1) - 3 = 2x^2 - 1. $$$f \circ g$: apply $g$ first, then $f$.
$$ (f \circ g)(x) = f(g(x)) = f(2x - 3) = (2x - 3)^2 + 1 = 4x^2 - 12x + 10. $$The two compositions are different functions — composition is not commutative.
Example 5 · Count relations and functions on small finite sets
Let $|A| = 3$ and $|B| = 2$. How many relations from $A$ to $B$? How many functions $A \to B$? How many injections? How many surjections?
Relations: $A \times B$ has $3 \cdot 2 = 6$ pairs; each is either in or out. So $2^6 = 64$ relations.
Functions: each of the $3$ elements of $A$ chooses one of the $2$ elements of $B$. So $2^3 = 8$ functions.
Injections: need three distinct outputs from a $2$-element set — impossible. $0$ injections.
Surjections: total functions minus those missing an output. Two functions miss output $b_1$ (the constant $b_2$) — wait, only one, the constant $b_2$ function. Similarly one missing $b_2$. So $8 - 2 = 6$ surjections.
The numbers $64 \gg 8 \gg 6 \gg 0$ show how each constraint (single-valuedness, then surjectivity, then injectivity) carves out a smaller slice of the full set of relations.