Skip to main content

Relation Properties and Composition

What This Concept Is​

A binary relation on a set $A$ is a subset $R \subseteq A \times A$. The elements of $R$ are ordered pairs, and we write $a,R,b$ as shorthand for $(a, b) \in R$. A relation is a data structure in the mathematical sense: it records which pairs of elements stand in a stated connection -- "divides," "less than or equal," "has the same colour as," "depends on" -- and nothing else.

Four structural properties determine almost everything you will say about a relation:

  • Reflexive. $\forall a \in A,\ a,R,a$. Every element is related to itself.
  • Symmetric. $\forall a, b \in A,\ a,R,b \rightarrow b,R,a$. If the pair goes one way, it goes both ways.
  • Antisymmetric. $\forall a, b \in A,\ (a,R,b \land b,R,a) \rightarrow a = b$. Two elements related in both directions must be the same element.
  • Transitive. $\forall a, b, c \in A,\ (a,R,b \land b,R,c) \rightarrow a,R,c$. Chains collapse to direct links.

Each property is a universally quantified implication (see concept 3), so each is proved by the template "let $a, b \in A$; assume the hypothesis; derive the conclusion," and each is disproved by a single concrete counterexample (see concept 8).

Composition of relations generalises composition of functions. Given $R \subseteq A \times B$ and $S \subseteq B \times C$:

$$S \circ R \ =\ {(a, c) \in A \times C \ :\ \exists b \in B,\ (a, b) \in R \land (b, c) \in S}.$$

Reading this: "there is a middleman $b$ linking $a$ to $c$." Transitivity of a single relation $R \subseteq A \times A$ is exactly the inclusion $R \circ R \subseteq R$.

A crisp mental model: think of a relation as a directed graph on $A$.

  • Reflexive means every vertex has a self-loop.
  • Symmetric means every edge is doubled (or equivalently, draw undirected).
  • Antisymmetric means no two vertices are joined by both $u \to v$ and $v \to u$ (except trivially at self-loops).
  • Transitive means every two-step path $u \to v \to w$ has the shortcut $u \to w$.

Composition $S \circ R$ is "take one step in $R$, then one step in $S$." Most theorems on relations have a one-line graph picture that makes them obvious, which is why drawing tiny diagrams pays off before writing symbolic proofs.

Why It Matters Here​

Relations are the structural substrate for the rest of Cluster 4 and for much of Semester 2. Equivalence relations (concept 14) are relations that are reflexive, symmetric, and transitive. Partial orders (concept 15) are relations that are reflexive, antisymmetric, and transitive. Trees, DAGs, and dependency graphs later are relations equipped with extra constraints. If the properties above are fuzzy, every downstream definition inherits the fuzz.

Beyond the module, relations are the mathematical shape of database tables (columns are the coordinates of the underlying Cartesian product), of type hierarchies (is-a is a partial order), of scheduler precedence graphs, and of state-transition systems in concurrency. Engineers who read $R \subseteq A \times A$ fluently recognise each of those situations as "the same thing, dressed differently."

Composition specifically is the algebra behind reachability analysis ($R^*$ is the reflexive-transitive closure), behind JOIN operations in SQL, and behind matrix multiplication when relations are stored as boolean matrices. Cluster 4 gives you the vocabulary; later semesters keep reusing it.

One more reason to invest here: the four properties listed above are the only independent axes you need to reason about. Any named kind of relation you will meet in this course or the next -- equivalence, partial order, total order, strict order, preorder, tolerance -- is a conjunction of some of these four plus the rejection of others. Knowing the four fluently means you parse every later definition by pattern-matching on a short cheat-sheet instead of memorising a new term each time.

Concrete Example​

Let $A = {1, 2, 3, 4}$ and define "$a \mid b$" ($a$ divides $b$) as our relation $R$:

$$R = {(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)}.$$

Audit each property:

  • Reflexive? Yes. $(1,1),(2,2),(3,3),(4,4) \in R$; every element divides itself.
  • Symmetric? No. $(1, 2) \in R$ but $(2, 1) \notin R$.
  • Antisymmetric? Yes. Check all pairs in $R$ whose reverse is also in $R$: only the diagonal $(a,a)$ pairs, and those trivially have $a = a$.
  • Transitive? Yes. Spot-check: $(1,2) \in R$ and $(2, 4) \in R$ force $(1, 4) \in R$; it is.

So divisibility on ${1,2,3,4}$ is a partial order -- reflexive, antisymmetric, transitive -- and it is the running example you will see in concept 15.

Now compose $R$ with itself. By the definition, $(a, c) \in R \circ R$ iff there exists $b$ with $a \mid b$ and $b \mid c$. Because divisibility is transitive, $R \circ R \subseteq R$. In fact equality holds here because reflexivity lets us pick $b = a$ or $b = c$. Composing a transitive reflexive relation with itself reproduces it: the relation is idempotent under composition.

Contrast with a non-transitive example. Let $S$ on ${1,2,3}$ be $S = {(1,2),(2,3)}$. Then $S \circ S = {(1, 3)}$, which is not contained in $S$. Transitive closure $S^* = S \cup (S \circ S) \cup \ldots = {(1,2),(2,3),(1,3)}$ adds exactly the chain-implied pair.

Boolean-matrix view. Represent $R$ on ${1,2,3,4}$ as a matrix $M$ where $M_{ij} = 1$ iff $(i, j) \in R$. Then composition corresponds to boolean matrix multiplication: $(M^2){ij} = \bigvee_k M{ik} \land M_{kj}$, which is $1$ iff some intermediate $k$ witnesses the composition. Transitivity of $R$ becomes the matrix inclusion $M^2 \le M$ (entrywise); transitive closure is the least fixed point of $M \mapsto M \lor M^2$. Every property in this concept has a matrix analogue -- which is how database engines actually compute composition for small relations.

Worked proof of transitivity. Claim: the relation $R$ on $\mathbb{Z}$ defined by $a,R,b \iff 3 \mid (a - b)$ is transitive.

Proof (direct). Let $a, b, c \in \mathbb{Z}$ and assume $a,R,b$ and $b,R,c$. By definition $3 \mid (a - b)$ and $3 \mid (b - c)$, so there exist integers $j, k$ with $a - b = 3j$ and $b - c = 3k$. Adding, $a - c = (a - b) + (b - c) = 3j + 3k = 3(j + k)$. Since $j + k \in \mathbb{Z}$, this shows $3 \mid (a - c)$, i.e., $a,R,c$. $\blacksquare$

Three moves appeared: unpack the definition, combine the hypotheses algebraically, repack into the target form. That template will reappear in every transitivity proof you write.

Common Confusion / Misconception​

  1. Symmetry confused with antisymmetry. Symmetry requires both directions; antisymmetry forbids both directions except on the diagonal. Many relations are neither: divisibility on ${1,2,3,4}$ is antisymmetric but not symmetric; the "sibling of" relation is symmetric but not antisymmetric. A relation can even be both simultaneously -- any relation contained in the diagonal ${(a,a)}$ satisfies both trivially.
  2. "Not symmetric" confused with "antisymmetric." A relation can fail both. Take $T = {(1,2),(2,1),(1,3)}$ on ${1,2,3}$. It is not symmetric (missing $(3,1)$) and not antisymmetric (we have $(1,2)$ and $(2,1)$ but $1 \ne 2$). "Not symmetric" merely says "some pair has no reverse"; antisymmetry is a separate claim.
  3. Reflexivity for free. Some beginners assume every relation on a set is automatically reflexive. It is not. The strict less-than $<$ on $\mathbb{Z}$ is not reflexive: $3 \not< 3$. The empty relation is also not reflexive (unless $A = \emptyset$). Always check.
  4. Transitive closure vs transitivity. A relation being transitive is a property it may or may not have. The transitive closure $R^*$ is the smallest transitive relation containing $R$; it is something you construct when $R$ is not already transitive. Mixing the two terms is a classical source of bugs when writing reachability code.
  5. "Reflexive over $A$" confused with "reflexive on the pairs present." Reflexivity demands the diagonal of the whole set $A$, not merely the diagonal on elements that appear in some other pair. If $A = {1, 2, 3}$ and $R = {(1,1),(2,2),(1,2)}$, $R$ is not reflexive because $(3,3) \notin R$, even though $3$ never appears in a non-diagonal pair.

How To Use It​

Checklist for auditing a relation $R$ on $A$:

  1. Write $R$ as a set of ordered pairs or as a predicate. Do not skip this; "the divisibility relation" is ambiguous without the underlying set.
  2. Reflexive? Quantify: is $(a, a) \in R$ for every $a \in A$? One missing diagonal element disproves it.
  3. Symmetric? For every $(a, b) \in R$ with $a \ne b$, check $(b, a) \in R$. One missing reverse disproves it.
  4. Antisymmetric? For every $(a, b) \in R$ with $(b, a)$ also in $R$, verify $a = b$. One witness with $a \ne b$ disproves it.
  5. Transitive? For every pair of composable pairs $(a, b), (b, c) \in R$, verify $(a, c) \in R$. One missing triangle disproves it.
  6. Composition. To compute $S \circ R$, pair each $(a, b) \in R$ with every $(b, c) \in S$ and collect $(a, c)$. Check matching middle element $b$ carefully.
  7. Transitive closure. Iterate $R, R^2, R^3, \ldots$ and union until the result stabilises -- or cite Warshall's algorithm for a systematic method.
  8. Represent in the right form for the task. Set-of-pairs for small hand-drawn examples; directed-graph picture for intuition about reachability; boolean matrix for programmatic or compositional manipulation. Switching representations mid-problem is normal and expected.

Check Yourself​

  1. Give a relation on ${1,2,3}$ that is symmetric but not transitive. What is its transitive closure?
  2. Is the empty relation reflexive? Antisymmetric? Transitive? Justify each answer precisely.
  3. Why does transitivity say exactly "$R \circ R \subseteq R$"? Sketch the translation in both directions.
  4. Construct a relation that is reflexive and transitive but not antisymmetric. What structural object does this resemble?
  5. If $R$ is symmetric and transitive, is it necessarily reflexive? Find the subtle counterexample and explain.
  6. What does the identity $M^2 \le M$ say on the boolean-matrix representation, and why is it equivalent to transitivity?

Mini Drill or Application​

Let $R$ on ${1, 2, 3, 4}$ be ${(1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(1,3),(3,4),(2,4),(1,4)}$.

  1. Verify each of the four properties (reflexive, symmetric, antisymmetric, transitive). For any property that fails, exhibit a concrete counterexample pair.
  2. Compute $R \circ R$ and compare with $R$. What does the comparison tell you about transitivity?
  3. Build a second relation $S$ on the same set that is symmetric but not transitive, and compute its transitive closure $S^*$ explicitly.
  4. Represent $R$ as a $4 \times 4$ boolean matrix and compute $R^2$ via boolean matrix multiplication. Verify the result matches step 2.

Writing these out disciplines the habit of translating between three representations: set of pairs, graph diagram, and boolean matrix. Every representation will reappear later; the conversions are worth rehearsing once.

As a second drill, classify each of the following relations on $\mathbb{Z}$ (name which of the four properties hold) without looking up any definitions:

  1. $a,R_1,b$ iff $a = b$ (equality).
  2. $a,R_2,b$ iff $a \le b$ (standard order).
  3. $a,R_3,b$ iff $a < b$ (strict order).
  4. $a,R_4,b$ iff $a$ and $b$ have the same parity.
  5. $a,R_5,b$ iff $|a - b| \le 1$ ("approximately equal within 1").

Compare your classifications with a classmate; the disagreements usually land on $R_5$ (reflexive and symmetric but not transitive -- a tolerance relation) and on $R_3$ (transitive but neither reflexive nor symmetric -- a strict partial order).

Transfer / Where This Shows Up Later​

  • Semester 2 (algorithms). Warshall's algorithm computes $R^*$ in $O(n^3)$; it is relational composition applied in a triple loop. Graph reachability, shortest-path "closure," and dependency resolution all compute transitive closures.
  • Semester 5 (concurrency). The happens-before relation is a strict partial order on events; reasoning about data races is reasoning about incomparable pairs in that order.
  • Semester 6 (databases). A JOIN between relations $R \subseteq A \times B$ and $S \subseteq B \times C$ on the common coordinate $B$ is exactly relational composition $S \circ R$. SQL optimisers rely on composition identities (associativity, distributivity over union).
  • Semester 7 (architecture / DDD). Dependency graphs between bounded contexts are relations; cycles (failures of antisymmetry on the reachability closure) signal architectural smell.
  • Semester 9+ (advanced / PL theory). Subtyping relations are preorders (reflexive, transitive, usually not antisymmetric); type-equivalence is then derived as "$S <: T$ and $T <: S$." The four properties let you read those definitions on sight rather than re-derive each one.

Read This Only If Stuck​

Closing Note​

The four properties of a relation are a compact vocabulary that the rest of this module (and much of later discrete math) keeps reusing. Invest an hour now learning to classify a novel relation fluently against the four axes and against composition; the payoff is that concepts 14, 15, and every graph-theoretic definition you meet later read as "relation with these properties, plus this extra condition" instead of "a new thing to memorise." The graph picture, the boolean matrix, and the set-of-pairs form are three dialects of the same object -- switching between them quickly is the skill that separates students who memorise the four properties from students who use them.