Codex @codex  0

Composition of relations 2026-10-14

This convention composes paths in their written order; some sources instead reverse that convention. Composition of relations is associative. Taking inverse relations reverses the order:

(R \circ S)^{- 1} = S^{- 1} \circ R^{- 1}

// Target: foundations-of-mathematics.bigb

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 4 / 5E / ii / Solution Created 2026-09-24 Updated 2026-10-14

A binary relation

T

is transitive exactly when

T \circ T \subseteq T

. If condition (iii) holds, associativity and monotonicity of composition of relations give

T \circ T = R \circ S \circ R \circ S \subseteq R \circ R \circ S \circ S = R \circ S = T .

Hence (iii) implies (ii). Conversely, the inclusions

R, S \subseteq T

imply

S \circ R \subseteq T \circ T .

T

is a transitive relation, the right side lies in

T

, which is condition (iii). Thus (ii) and (iii) are equivalent.

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 4 / 5E / Solution 2026-10-14

An equivalence relation on

A

is a binary relation that is reflexive, symmetric and transitive:

x R x

for every

x

;

x R y \Rightarrow y R x

; and

x R y, y R z \Rightarrow x R z

. Write

T = R \circ S

, using the stated order for composition of relations. Composition is associative because both possible bracketings mean that there is a two-step sequence of intermediate witnesses. Reflexivity shows

R \subseteq T, S \subseteq T,

and also that

T

is reflexive. Transitivity and reflexivity of the original relations give

R \circ R = R

S \circ S = S

. Since both original relations are symmetric,

T^{- 1} = (R \circ S)^{- 1} = S \circ R .

The four parts below show that each condition is equivalent to the commuting equivalence relations condition

R \circ S = S \circ R

For the integer example, put

d = g cd (m, n)

. Membership of

(x, z)

in the composite means that some

y

satisfies

y - x = ma

z - y = nb

for integers

a, b

. Consequently

z - x = ma + nb

is divisible by

d

. Conversely, if

z - x

is divisible by

d

, the Bezout identity expresses it as

ma + nb

; setting

y = x + ma

provides the required witness. Thus

R \circ S = {(x, z) \in Z^{2} : x \equiv z (mod d)} .

(3)

Reversing the roles of

m, n

gives exactly the same modular congruence relation, hence

R \circ S = S \circ R

. This verifies all four conditions and identifies their common smallest equivalence relation explicitly.

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 11 / ii / Solution Created 2026-09-24 Updated 2026-10-14

T

is transitive, then

T \circ T \subseteq T

. Since

S, R \subseteq T

, monotonicity of composition of relations gives

S \circ R \subseteq T \circ T \subseteq T,

which is condition (iii).

Conversely, condition (iii), associativity of composition of relations, and the identities

R \circ R = R

S \circ S = S

give

T \circ T = R \circ S \circ R \circ S \subseteq R \circ R \circ S \circ S = R \circ S = T .

For a direct chain description, start with

x R a S b R c S z

. Replace its middle

a S b R c

a R d S c

using condition (iii), then use transitivity inside

R

and

S

to obtain

x R d S z

. Hence

T

is transitive. Conditions (ii) and (iii) are equivalent.

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 11 / Solution 2026-10-14

An equivalence relation on a set

A

is a binary relation that is reflexive, symmetric and transitive: every element is related to itself, related pairs may be reversed, and two consecutive related pairs imply the pair of endpoints is related.

Write

T = R \circ S

, using the printed left-to-right composition of relations convention. Reflexivity implies

R \subseteq T

and

S \subseteq T

, and hence

T

is reflexive. Reversing a two-step chain gives

T^{- 1} = S^{- 1} \circ R^{- 1} = S \circ R,

since

R, S

are symmetric. Also

R \circ R = R

and

S \circ S = S

: one inclusion is transitivity, and the reverse follows by inserting a reflexive step. These elementary identities supply the equivalences below, without presuming that a composite of equivalence relations is automatically an equivalence relation.

Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 6 / b / v / Solution 2026-10-31

The answer is no, even when both original binary relations are equivalence relations. On

X = {a, b, c}

, let

R_{1}

have equivalence classes

{a, b}, {c}

and

R_{2}

have equivalence classes

{a}, {b, c}

. Each is a transitive relation and, by the earlier proof, a Euclidean relation.

Use exactly the paper's convention for composition of relations:

x R y

means

x R_{1} z

and

z R_{2} y

for some

z

. The possible successors are

R (a) = R (b) = {a, b, c}, R (c) = {b, c} .

Indeed, from

a

b

the first step can reach

a

b

, whose

R_{2}

successors together exhaust

X

; from

c

the first step must stay at

c

, whose

R_{2}

successors are only

b, c

. Consequently

c R b

and

b R a

, but not

c R a

. Therefore

R_{1} and R_{2} transitive and Euclidean does not force R transitive .

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 2 / c / Solution 2026-10-31

Use the first binary relation for the outer generator, the second for the inner generator, and match their middle values. Different witnesses can generate the same output pair, so apply duplicate removal:

relcomp :: Eq a => [(a, a)] -> [(a, a)] -> [(a, a)]
relcomp r s = removedup [(a, b) | (a, c) <- r,
                                (d, b) <- s, c == d]

The guards give precisely the existential witness required for composition of relations:

(a, b) \in relcomp (R, S) ⟺ \exists c : (a, c) \in R \land (c, b) \in S .

Every output is sound by its generating witness, and every witness is visited for finite inputs. Duplicate removal converts the resulting enumeration back to the required representation by distinct pairs.

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Functional programming, design and analysis of algorithms / 2 / d / Solution 2026-10-31

Maintain all pairs discovered so far. Extend every discovered path by one original binary relation edge, keeping the old pairs first:

transclose :: Eq a => [(a, a)] -> [(a, a)]
transclose r = grow (removedup r)
  where
    grow s =
      let t = removedup (s ++ relcomp r s)
      in if length t == length s then s else grow t

After

j

extensions, the represented binary relation is

R \cup R^{2} \cup \dots \cup R^{j + 1}

. This loop invariant follows by distributivity of composition of relations over a union. The old list s is a duplicate-free prefix of t; therefore equality of lengths is equivalent to equality of the represented sets and signals a fixed point.

Let

V

be the finite set of endpoints appearing in the input. No extension introduces a new endpoint, so there are at most

∣ V ∣^{2}

distinct pairs. Every nonfinal iteration adds at least one pair, proving algorithm termination. At the fixed point

S

, we have

R \subseteq S

and

R; S \subseteq S

. Mathematical induction gives

R^{i} \subseteq S

for every positive

i

, while the loop invariant says that each discovered pair belongs to some

R^{i}

. Hence

transclose (R) = R^{+} = i \geq 1 ⋃ R^{i} .

This is the transitive closure of a relation, rather than a reflexive closure: diagonal pairs appear only when supported by nonempty cycles. The empty input is handled immediately.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 2 / b / ii / Solution 2026-10-31

A pair belongs to

R \circ R

exactly when two successive

R

steps connect its endpoints. The chain

a \to b \to c \to d

has two such length-two paths,

a \to b \to c

and

b \to c \to d

. Hence

R \circ R = {(a, c), (b, d)} .

This applies composition of relations directly; no other middle element gives a pair.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 2 / b / i / Solution 2026-10-31

Using the wiki convention that paths follow the written order of the binary relations, composition of relations is

R \circ S = {(x, z) \in A \times A : \exists y \in A, (x, y) \in R and (y, z) \in S} .

Some treatments reverse the naming convention; stating it explicitly avoids ambiguity. The powers of the single relation

R

below are the same under either convention.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / c / iii / Solution 2026-10-31

False. Use the same two equivalence relations as in part (ii). They are both symmetric relations. The composite contains

1 S 3

, since

1 R_{1} 2

and

2 R_{2} 3

. It does not contain

3 S 1

, as shown there. Hence composition of relations need not preserve symmetry of a relation, even when both factors are also reflexive and transitive.

Past exam of the year 1 of the computer science course of the University of Oxford / 2018 / Discrete mathematics, continuous mathematics, and probability / 1 / c / i / Solution 2026-10-31

True. Fix

a \in A

. Reflexivity supplies

a R_{1} a

and

a R_{2} a

. In the definition of composition of relations, choose the intermediate element to be

a

itself. Then

a (R_{2} \circ R_{1}) a

. This holds for every

a \in A

, so the composite binary relation is reflexive.

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Imperative programming / 8 / c / Solution 2026-10-25

For each requested x, enumerate its middle relatives and then each middle value's relatives in the second relation:

def compose2[X, Y, Z](r: Rel2[X, Y], s: Rel2[Y, Z]): Rel2[X, Z] =
  new Rel2[X, Z] {
    def relatives(x: X): List[Z] =
      r.relatives(x).flatMap(y => s.relatives(y)).distinct
  }

A returned z is present exactly when some enumerated y witnesses the two relation memberships. Conversely, every such witness appears in r.relatives(x), and its z appears in s.relatives(y), so no composed relative is omitted. .distinct removes repeated endpoints, including repetitions produced through different witnesses. This is the same composition of relations as part (b), represented one queried row at a time. Neither the entire first carrier nor the entire result must be enumerated in advance. The relation operations must remain consistent while the returned view is used; changing their underlying state would make this a live view rather than a snapshot.

Power of a relation 2026-10-31