Composition of Relations

Definition

Let $R$ be a relation from set $A$ to set $B$, and let $S$ be a relation from set $B$ to set $C$. The composition of relations $S \circ R$ is the relation from $A$ to $C$ defined by

$$S \circ R = \{(a,c) \mid \text{there exists } b \in B \text{ such that } (a,b) \in R \text{ and } (b,c) \in S\}$$

In words, $(a,c)$ belongs to the composition $S \circ R$ if and only if there is at least one intermediate element $b$ such that $a$ is related to $b$ by $R$, and $b$ is related to $c$ by $S$.

The order of composition is important:

• $S \circ R$ means first apply $R$, then apply $S$.
• In relation notation, the right relation is applied first.

Main Content

1. Basic Idea of Composition of Relations

• Composition describes a two-step connection: the first relation takes you from one set to an intermediate set, and the second relation takes you from that intermediate set to another set.
• It is similar to following a path through a network: if one node is connected to a second node, and the second node is connected to a third, then composition tells us whether the first node is indirectly connected to the third.

Suppose:

• $A = \{1,2,3\}$
• $B = \{x,y,z\}$
• $C = \{p,q\}$

Let $$R = \{(1,x), (1,y), (2,y), (3,z)\}$$ and $$S = \{(x,p), (y,p), (y,q), (z,q)\}$$

Then:

• From $1$, via $x$, we can reach $p$
• From $1$, via $y$, we can reach $p$ and $q$
• From $2$, via $y$, we can reach $p$ and $q$
• From $3$, via $z$, we can reach $q$

So, $$S \circ R = \{(1,p), (1,q), (2,p), (2,q), (3,q)\}$$

This shows that composition collects all possible results of chaining relations.

2. Ordered-Pair Rule and Notation

• Composition is defined using ordered pairs, so both the starting element and ending element matter.
• If $(a,b) \in R$ and $(b,c) \in S$, then $(a,c)$ is in $S \circ R$. This is the exact rule used to determine the composed relation.
• The notation $S \circ R$ is read as “$S$ composed with $R$” or “$S$ after $R$.”

A very common mistake is reversing the order. For relations: $$S \circ R \neq R \circ S$$ in general.

Example: Let $$R = \{(1,2)\}, \quad S = \{(2,3)\}$$ Then $$S \circ R = \{(1,3)\}$$ but $$R \circ S$$ is empty, because there is no pair in $S$ starting from $1$ and no pair in $R$ ending at the correct intermediate value.

This shows that the order of composition is crucial.

3. Properties and Uses in Relation Analysis

• Composition helps in studying how relations behave over multiple steps, especially in recursive structures, transitive closure, and reachability.
• It is closely related to transitivity: a relation $R$ is transitive if whenever $(a,b) \in R$ and $(b,c) \in R$, then $(a,c) \in R$. This is exactly the idea of composing a relation with itself and seeing whether the result stays inside the same relation.
• Composition is associative, meaning: $$(T \circ S) \circ R = T \circ (S \circ R)$$ when the relations are appropriately defined. This allows long chains of relations to be grouped without changing the result.

Important examples of use:

• In directed graphs, composition helps determine whether there is a path of length 2, 3, or more between vertices.
• In database queries, composition can represent joining tables through common attributes.
• In function theory, composition is the same structure used for composing functions, making it a bridge between relations and functions.

Working / Process

1. Identify the two relations and their domains/codomains
   Determine the first relation $R$ and the second relation $S$. Make sure the output set of $R$ matches the input set of $S$, because composition is only possible when the middle set is compatible.

2. Match intermediate elements
   Look for elements $b$ such that $(a,b) \in R$ and $(b,c) \in S$. Each valid middle element produces a possible pair $(a,c)$.

3. Form the composed relation
   Collect all pairs $(a,c)$ obtained through the intermediate matches. Remove duplicates if the same pair appears more than once, because relations are sets of ordered pairs.

Example:

Let $$R = \{(1,2), (2,3), (3,4)\}$$ and $$S = \{(2,a), (3,b), (4,c)\}$$

Step 1: Check compatibility

• $R$ goes from numbers to numbers.
• $S$ goes from numbers to letters.
• Composition is valid because the second component of $R$ matches the first component of $S$.

Step 2: Find chains

• $1 \to 2$ in $R$, and $2 \to a$ in $S$, so $(1,a)$
• $2 \to 3$ in $R$, and $3 \to b$ in $S$, so $(2,b)$
• $3 \to 4$ in $R$, and $4 \to c$ in $S$, so $(3,c)$

Step 3: Write the result
$$S \circ R = \{(1,a), (2,b), (3,c)\}$$

Advantages / Applications

• It simplifies the study of multi-step relationships by reducing them to a single relation.
• It is essential in graph theory for finding indirect connections and paths between vertices.
• It is useful in computer science for database joins, automata transitions, program semantics, and dependency analysis.

Summary

• Composition of relations combines two relations into one by linking them through a common intermediate element.
• The order matters: $S \circ R$ means apply $R$ first, then $S$.
• It helps in finding indirect connections and is widely used in mathematics and computing.
• Important terms to remember: relation, ordered pair, domain, codomain, composition, transitivity, associative property