Relation composition, equivalence classes and closures

Objectives and prerequisites

Starting from the earlier relation-property tests, compute composition of arbitrary relations, prove the equivalence-relation/partition correspondence, and construct minimal reflexive, symmetric and transitive extensions. We use finite sets for computation. This lesson does not repeat basic set operations or function classification. A relation need not be a function: an input may have zero, one or many outputs.

1. Composition joins compatible pairs

For R⊆A×B and S⊆B×C, define S∘R={(a,c): some b∈B satisfies (a,b)∈R and (b,c)∈S}. Apply R first, then S. Some texts reverse the written convention; here the displayed definition governs every example. Multiple witnesses b still produce only one ordered pair.

Let A={1,2}, B={u,v}, C={x,y}; R={(1,u),(1,v),(2,v)}, S={(u,x),(v,x),(v,y)}. From 1, the u-route reaches x and the v-route reaches x,y, giving (1,x),(1,y). From 2, only v is possible, giving (2,x),(2,y). Thus S∘R=A×C, with four pairs, not five paths. R∘S is not a compatible typed composition here.

Even on one common carrier composition need not commute. On {1,2,3}, let R={(1,2)} and S={(2,3)}. Then S∘R={(1,3)}, while R∘S=∅. Composition is associative: both T∘(S∘R) and (T∘S)∘R require witnesses b,c with aRb, bSc, cTd. Associativity changes grouping, not order.

For R on A, R²=R∘R and R³=R∘R². Transitivity is exactly R²⊆R, not R²=R. For R={(1,2)} on {1,2}, R²=∅: R is transitive even though equality fails.

2. Equivalence classes really are partition blocks

For an equivalence relation ~ on A, define [a]={x∈A:a~x}. Reflexivity puts a inside [a], so classes are nonempty and cover A. If [a] and [b] share x, then a~x and b~x imply a~b by symmetry and transitivity. Any y∈[a] then satisfies b~a~y, hence y∈[b]; reversing roles proves equality. Thus two classes are either identical or disjoint.

A partition is a family of nonempty, pairwise-disjoint blocks whose union is A. Conversely, any partition defines x~y iff x,y belong to the same block. Every element shares a block with itself; “same block” is symmetric; and if x,y share one block and y,z another, disjointness forces those blocks to coincide. Thus the relation is transitive. These constructions undo each other. The quotient A/~ is the set of distinct classes, not a choice of one special representative.

Example: on A={0,1,2,3,4,5,6,7}, let x~y iff x−y is divisible by 3. The classes are {0,3,6}, {1,4,7}, {2,5}. Here [0]=[3]=[6], so listing all three separately overcounts blocks. The relation has 3²+3²+2²=22 pairs: each block contributes its Cartesian square. More generally, block sizes n₁,…,nₖ give Σnᵢ² pairs, including all loops.

3. A closure is the smallest required extension

A closure contains every original pair, satisfies the specified property, and is contained in every other extension with that property. Deleting offending pairs is not a closure. Fix the underlying A throughout. Let I_A={(a,a):a∈A} and R⁻¹={(b,a):(a,b)∈R}.

• Reflexive closure: R∪I_A. Every reflexive extension must add the missing loops.
• Symmetric closure: R∪R⁻¹. Every symmetric extension must include each reverse pair.
• Transitive closure: R⁺=R∪R²∪R³∪⋯. A pair belongs exactly when a positive-length directed walk connects its endpoints.
• Reflexive-transitive closure: R*=I_A∪R⁺, allowing a length-zero walk.

Why is R⁺ minimal? Concatenating two positive walks gives another positive walk, so R⁺ is transitive. In any transitive extension, induction on walk length forces the endpoint pair of every R-walk. Therefore that extension contains R⁺. A cycle may force diagonal pairs even though reflexivity was not requested. Isolated elements do not acquire loops in R⁺.

4. A closure trace with a cycle and an isolated element

On A={1,2,3,4}, take R={(1,2),(2,1),(2,3)}. R²={(1,1),(1,3),(2,2)}. Adding these to R gives six pairs: (1,1),(1,2),(1,3),(2,1),(2,2),(2,3). All longer walks have endpoints already listed, so this is R⁺. Neither 3 nor 4 has an outgoing original edge; (3,3),(4,4) are absent. R* adds exactly those two loops, for eight pairs.

The symmetric closure of this R adds only (3,2); it does not automatically add (1,3) or any missing loop. For the smallest equivalence relation containing R, first add reverse edges and loops, then take transitive closure. The resulting blocks are {1,2,3} and {4}; all ordered pairs inside each block give 9+1=10 pairs. Taking closures independently and merely unioning the three results can fail to supply paths created by newly reversed edges.

5. Matrix computation without ordinary arithmetic

With M[i,j]=1 iff iRj, composition uses Boolean matrix multiplication: (M_R M_S)[i,k]=∨ⱼ(M_R[i,j]∧M_S[j,k]), representing S∘R with row-source convention. Arithmetic multiplication counts witnesses, whereas Boolean multiplication records existence.

For transitive closure initialize W=M. For k=1,…,n, update W[i,j]←W[i,j]∨(W[i,k]∧W[k,j]) for every i,j. After stage k, W records positive-length walks whose internal vertices come from {1,…,k}. A new walk either avoids k or splits at k into two allowed pieces. This invariant explains the update and gives O(n³) time. Standard in-place updates are valid. Initialize diagonal entries to 1 only when reflexive-transitive closure is wanted; otherwise let genuine cycles create loops.

Pitfalls and a checking routine

State the carrier and composition convention; enumerate intermediate witnesses and remove duplicate endpoint pairs. For classes, merge equal blocks rather than overlapping them. For closure, check inclusion of R, the requested property and minimality. Do not silently replace R⁺ by R*, assume a single shortcut pass is always enough, or infer a missing reverse edge from transitivity alone.

Original practice: six single-correct MCQs

These are original questions, not previous-year questions. Choose exactly one option.

RC01. R={(1,2),(1,3)} and S={(2,4),(3,4)} are relations on {1,2,3,4}. With R applied first, what is S∘R?

A. {(1,4)} B. {(1,2),(1,3)} C. ∅ D. Two distinct copies of (1,4)

Answer: A

A: Both intermediate witnesses give the same endpoint pair, counted once.

B: These are R’s pairs; S must still be applied.

C: There are compatible chains through both 2 and 3.

D: A relation is a set, so duplicate pairs are not distinct.

RC02. An equivalence relation on six elements has blocks of sizes 1,2,3. How many ordered pairs does it contain?

A. 6 B. 11 C. 14 D. 36

Answer: C

A: This counts elements, not pairs within blocks.

B: This omits some pairs; each block contributes its size squared.

C: 1²+2²+3²=14, including loops.

D: 36 would relate every element to every other, giving one block.

RC03. On {a,b,c}, R={(a,b),(b,a)}. Which pair is in R⁺ but not in R?

A. (c,c) B. (a,c) C. (c,a) D. (a,a)

Answer: D

A: No positive-length walk starts at isolated c.

B: No walk reaches c from a.

C: No walk starts at c.

D: The two-edge walk a→b→a forces this loop.

RC04. Which construction is always the smallest symmetric relation containing R on A?

A. R∩R⁻¹ B. R∪R⁻¹ C. R∪I_A D. R²

Answer: B

A: Intersection may delete original pairs, so it need not contain R.

B: Add exactly the missing reverses; symmetry needs no other pairs.

C: Adding loops makes reflexivity, not necessarily symmetry.

D: Two-step endpoints do not generally supply reverses or even contain R.

RC05. For a relation R on A, which condition is equivalent to transitivity under the stated composition convention?

A. R²=R always B. R⊆R² C. R²⊆R D. R=R⁻¹

Answer: C

A: Equality is stronger; a lone edge is transitive but has empty square.

B: This asks every edge to have a two-step factorization, a different property.

C: Every existing two-step chain must have its shortcut in R.

D: This is symmetry.

RC06. On {1,2,3,4}, R={(1,2),(3,2)}. How many pairs are in the smallest equivalence relation containing R?

A. 10 B. 6 C. 8 D. 16

Answer: A

A: Reverses and transitivity unite {1,2,3}; {4} is separate, giving 3²+1²=10.

B: This does not include all pairs among 1,2,3 plus the isolated loop.

C: Adding only loops and reverses gives 8 but misses (1,3),(3,1).

D: This also merges 4 unnecessarily and is not minimal.

Source and scope

This bounded extension develops relations, lattices or groups under Section 1 of the GATE 2026 CS syllabus. It does not claim complete Discrete Mathematics coverage. Definitions, worked examples, proofs and practice are original.

Official GATE 2026 CS syllabus, Section 1

Source checked: 2026-10-14.