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 universally quantified (reflexivity directly requires every diagonal pair) (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.

These four properties are a useful starting vocabulary. Total orders additionally require comparability; strict orders use irreflexivity. State the complete definition rather than assuming every relation type is a combination of only four yes/no flags.

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: if b=ak and c=bj for integers k,j, then c=a(kj), so divisibility is transitive. For illustration, $(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$. Positive-length 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 provides an independent finite checking method for this lab.

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 positive-length 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 to the module project

Use this concept to state, justify or challenge one claim in the workflow project. Name the mathematical model and the execution assumptions separately; software behavior is not established by an analogy alone.

Read This Only If Stuck

Use the bounded reading guide to locate this lesson's topic in MCS or Rosen. These links open book indexes. Find the named topic in your edition, read one relevant explanation, then reconstruct the argument with the book closed.

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.

Closure and the role of the carrier

Write R+ for pairs connected by at least one step, and R* for pairs connected by zero or more steps. Thus R* includes every carrier self-pair. On {0,1}, R={(0,1)} has R+=R and R*={(0,0),(0,1),(1,1)}. Positive paths can still produce self-pairs when cycles exist; “positive” does not mean “no diagonal.”

For a finite relation, repeatedly adding pairs from the current composition computes positive closure; add all self-pairs initially to obtain R*. Prove both fixed-point transitivity and minimality among suitable supersets. Merely stopping at a transitive relation does not establish it is the least one.

The four familiar properties are not every possible relation constraint: totality/comparability and irreflexivity are additional definitions. Transfer attempt: explain the empty-carrier results and complete the typed composition in P10 before constructing the project closure.

Use Practice Solutions and Feedback after your attempt, and Proof and Model Contracts to audit assumptions.