Relations

Why do we need a new word for "this is related to that"? Because that single idea covers an enormous range of structures: numerical orderings ($<$, $\leq$), arithmetic links ($\mid$, $\equiv \pmod{n}$), social connections (friend-of, sibling-of), database keys (foreign-key links), and graph edges. The mathematical concept that captures all of them — with no extra restrictions — is the relation. It is the most general "connection" structure you can build, and once you have it, you can ask precise questions: Is the connection symmetric? Reflexive? Transitive? Does it chain? Does it partition? Sections 4.3-4.5 climb that ladder. This section sets the bottom rung.

The definition

A relation from a set $A$ to a set $B$ is any subset $R \subseteq A \times B$. When $(a, b) \in R$, we write $aRb$ and read it "$a$ is $R$-related to $b$." If $A = B$ we call $R$ a relation on $A$. There are no rules — $R$ can be tiny (empty), enormous (all of $A \times B$), or anything in between.

Domain, range, inverse

The domain of $R$ is the set of first components: $\text{Dom}(R) = {a \in A \mid \exists b \in B,, aRb}$. The range is the set of second components: $\text{Ran}(R) = {b \in B \mid \exists a \in A,, aRb}$. The inverse $R^{-1}$ swaps every pair: $R^{-1} = {(b, a) \mid (a, b) \in R}$. Always: $\text{Dom}(R^{-1}) = \text{Ran}(R)$ and $\text{Ran}(R^{-1}) = \text{Dom}(R)$.

Familiar relations

The most important examples to keep in mind:

• Less-than on $\mathbb{R}$: $R = {(a, b) \mid a < b}$. Strict, no element relates to itself.
• Equality on $A$: $R = {(a, a) \mid a \in A}$, the diagonal. Every element relates only to itself.
• Divides on $\mathbb{Z}^+$: $a \mid b$ means $b = ka$ for some positive integer $k$.
• Congruence mod $n$ on $\mathbb{Z}$: $a \equiv b \pmod n$ iff $n \mid (a - b)$.

Pause and think: Why is the empty set $\emptyset$ a perfectly legitimate relation from $A$ to $B$, no matter what $A$ and $B$ are? (Hint: a relation is just a subset of a Cartesian product, and $\emptyset \subseteq X$ for every set $X$.)

Try it

• List the relation $R = {(a, b) \in {1,2,3,4}^2 \mid a \mid b}$. Predict the size before listing.
• For $R = {(1, a), (2, b), (2, c), (3, a)}$, name $\text{Dom}(R)$, $\text{Ran}(R)$, and $R^{-1}$.
• Sketch the "less-than-or-equal" relation on ${1, 2, 3}$ as an arrow diagram in the widget. How many arrows?
• True or false: every function is a relation. Every relation is a function. Justify each.
• Find a relation $R$ on ${1, 2, 3}$ such that $R = R^{-1}$ but $R$ has more than 3 pairs.

A trap to watch for

Relations are more general than functions. A relation $R$ from $A$ to $B$ can pair a single $a$ with many different $b$’s, or with none at all. Students who have only seen functions sometimes assume "each input has exactly one output" is part of the definition of relation. It is not. That extra rule is what makes a relation into a function — we will see this in §5.1.

What you now know

You can write any relation as a set of ordered pairs, identify its domain and range, take its inverse, and recognise the relation behind everyday connection-style data — social graphs, database joins, divisibility, congruence. Section 4.3 asks the next obvious question: which properties can a relation have, and what changes when it does?

References

• Velleman, D. J. (2019). How to Prove It (3rd ed.). Cambridge University Press, §4.2.
• Halmos, P. R. (1960). Naive Set Theory. Springer, §7.
• Hammack, R. (2018). Book of Proof, ch. 11.
• Date, C. J. (2003). An Introduction to Database Systems (8th ed.). Addison-Wesley, ch. 3.
• Bloch, E. D. (2011). Proofs and Fundamentals (2nd ed.). Springer, ch. 5.