3.12. Composition of relations

The category of relations

This category extends the category of sets, keeping the same objets (the sets) and defining Mor(E,F) as the set ℘(E×F) of all relations between E and F. Their composition is defined by

grR,S, R;S = {(x0,y1) | (x,y)∈R×Sx1=y0}
RE×F, ∀SF×G, R;S = {(x,z)∈E×G | ∃yF, xRyySz}
= ∐xE SR(x)

This extends the composition of functions coming as functional relations, with the same identity elements (1E = 𝛿E = Gr IdE).
(This is the only natural way to extend composition, as the other expression of the composite of functions by their graphs, with ∀yF, xRyySz, would lose associativity in non-functional cases).
This category faithfully acts by direct images () on the powersets of its objects, and co-acts on them by preimages (): ∀RE×F, ∀SF×G,

AE, (SR)A = S(RA)
BG, (R;S)B = R(SB)

For this action, each object (set) E has a basis made of its singletons : ({x})xE, following the canonical bijection (℘(F))E ⥬ ℘(E×F).
Thus, coproducts in this category are given by the disjoint unions of objects (which operate as products on the powersets acted on). So, a coproduct of pairwise disjoint sets Ei is given by their union, with the morphisms 𝛿Ei from each Ei to it.
By symmetry of duality, this disjoint union also serves as a product.
The eggs of this action are the ({x}, {x}) for any x. A standard choice of singleton is given by the notations * = {•}. Then, direct and inverse images can be re-expressed in terms of composition: ∀RE×F, ∀AE, ∀BF,

*×(RA) = (*×A);R
(RB)×* = R;(B×*)

By these action and co-action, morphisms in this category behave as a third form of expression of Galois connections (after the ordinary and monotone ones). Indeed by associativity of composition,

(*×A);R;(B×*) = ∅ ⇔ AR(B) = ∅ ⇔ BR(A) = ∅
(∁FR, ∁ER) ∈ Gal(℘(E), ℘(F))
(R, ∁ER⚬∁F) ∈ Gal+(℘(E), ℘(F))

Re-expressing properties of relations

Each side (curried form) of the composition of relations, behaves similarly to direct images, which it can be seen as made of: ∀grR,S,T,

(RS);T = R;TS;T
T;(RS) = T;RT;S

and for any family of graphs Ri indexed by I and any graph T,

T;iI Ri = iI T;Ri
TiI Ri = iI TRi

The reflexivity (𝛿ER) of a relation R on a set E, implies


The transitivity of R can be written R;RR.
Thus if R is a preorder then R;R = R but the converse does not always hold.

Generated preorders

The role of sets of transformations of E as defining stability conditions on subsets AE, reflected by the Galois connection (End, Sub)∈ Gal(℘(℘(E)), ℘(EE)) introduced in 3.4, is equivalent to that of single relations RE2 (non-functional structures named by a single function symbol) in the Galois connection (Po, Sub)∈ Gal(℘(℘(E)), ℘(E2)) defined as relating any AE to (x,y)∈E2 by (xAyA):

A ∈ SubR ERAA ⇔ (∀(x,y)∈R, xAyA) ⇔ ∁E A ∈ SubtR E

Indeed any set of transformations can be replaced by the union of their graphs; inversely, any (x,y)∈E2 can be replaced by

Ez ↦ (z=x ? y : z).

The set Im Po of closed elements of ℘(E2) there, is the set of preorders of E. Indeed, for any set K and any GK×E,

x,yE, (x,y)∈Po(G[K]) ⇔ (∀zK, zGxzGy) ⇔ G(x)⊂G(y)

which, according to 2.9, gives all preorders on E (intersections of preimages of the natural order on {0,1}).
Now the inclusion order on any S⊂℘(E) appears that way with {(A,x)∈S×E|xA}. Namely, ∈ defines a pre-embedding from (E,Po(S)) to (℘(S),⊂).

The closure Po(SubRE) of any RE2 is called the preorder on E generated by R; we shall write it ⌈R⌉.

Generated stable subsets

Lemma. Any union of R-stable subsets is R-stable.
(This does not generalize to structures of other arities).

First proof. (∀iI, RAiAi) ⇒ RiI Ai = iI RAiiI Ai
Second proof. Use A ∈ SubR E ⇔ ∁E A ∈ SubtR E and the similar property with intersections.∎

Proposition.AE, 〈AR = ⌈RA.

Proof. First, when A is a singleton {x}, both definitions coincide :

yE, xRy ⇔ (∀A∈SubRE, xAyA) ⇔ y∈〈{x}〉R

Then, ⌈RA = xA 〈{x}〉R ⊂ 〈AR because A ↦ 〈AR is monotone.
We conclude by ⌈RA ∈ SubR E from the above lemma.∎

From the end of 3.3 we get ∀AE, 〈AR = ARAR.
By the faithfulness of the action, it can also be written

R⌉ = 𝛿ER⚬⌈R

An easy consequence of the above is that for any sets K, E and any GK×E and RE2, ⌈R⌉⚬G is the smallest SK×E such that GRSS, and it is a case of equality (GRS = S).

Transitive closure

For any RE2, the smallest transitive TE2 such that RT (which exists as transitivity is preserved by intersections), called the transitive closure of R, is

T = R⚬⌈R⌉ = ⌈R⌉⚬R.

Proof. By hypothesis, RT and RTTTT, thus ⌈R⌉⚬RT by the above result (⌈R⌉⚬R is the smallest T such that RRTT).
Then, ⌈R⌉⚬R fulfills both conditions for which T is smallest : R ⊂ ⌈R⌉⚬R, and transitivity:

R⚬⌈R⌉ ⊂ ⌈R⌉ = ⌈R⌉⚬⌈R⌉ ∴ ⌈R⌉⚬R⚬⌈R⌉⚬R ⊂ ⌈R⌉⚬⌈R⌉⚬R = ⌈R⌉⚬R

Hence T = ⌈R⌉⚬R. By duality, T = R⚬⌈R⌉.∎

Well-founded relations

A relation RE2 is called well-founded if ∀AE, ARAA = ∅.
This does not depend on E, and implies that any SR is also well-founded.
Any well-founded relation is irreflexive : ∀x,¬{x}⊂R{x}.

Proposition. The transitive closure T of a well-founded relation R is well-founded.

Proof. If RE2 is well-founded, T = RP and P = 𝛿ET (namely, P=⌈R⌉), then T is well-founded:

AE, ATAPA = ATA = RPA = ∅ ∎

Note (possible exercise): if R is well-founded then actually !P, P = 𝛿ERP.

Proposition. If R is well-founded then ⌈R⌉ is an order, whose strict order coincides with the transitive closure of R.

Proof. The transitive closure T of R, being both transitive and irreflexive, is a strict order, and ⌈R⌉ = 𝛿ET.∎
(The antisymmetry of a well-founded R can also be deduced by ∀x,y,¬{x,y}⊂R{x,y})


A relation RE2 is called a strict well-order on E if

AE, A = ∅ ∨ ∃!:A\(RA)

It is easy to see that any strict well-order is a well-founded strict total order; conversely, any well-founded RE2 whose complement ∁E2 R is antisymmetric, is a strict well-order on E.
Given that the corresponding total order ≤ equals ∁E2 tR, the condition for a relation ≤ to be a well-order, which means a total order whose strict version is a strict well-order on E, can be written

AE, A = ∅ ∨ ∃!xA, A ⊂ ≤(x)

or equivalently : it is antisymmetric and ∀AE, A = ∅ ∨ ∃xA, A ⊂ ≤(x).

Greatest and least elements

In any ordered set (E,≤), an xE is called a lower bound (resp. upper bound) of a subset AE if A ⊂ ≤(x) (resp. A ⊂ ≤(x)). If moreover xA, it is then called a least element (resp. greatest element) of A, which we shall denote x :min A (resp. x :max A). These concepts only depend on the set A ordered by restriction of ≤, ignoring the rest of E and ≤.
By antisymmetry of ≤, these relations are functional from ℘(E) to E, which is why they are usually denoted as functions min (the least element) and max (the greatest element): ∀AE, ∀xE,

x :min A ⇔ (xAA ⊂ ≤(x)) ⇔ (A∈ Dom min ∧ x = min A)
x :max A ⇔ (xAA ⊂ ≤(x)) ⇔ (A∈ Dom max ∧ x = max A)

The successor function

In any ordered set (E,≤) with strict order <, the successor is the functional relation S on E defined by ∀x,yE,

xSyy :min <(x) ⇔ ≤(y) = <(x)

This last equivalence is easy to check.
If the order is total then S is injective and its definition is symmetric in the sense that

xSyx :max <(y) ⇔ ≤(x) = <(y)

If it is a well-order then ∀xE, x ∉ Dom S ⇔ <(x) = ∅ ⇔ x :max E.
Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
3. Algebra 1
4. Arithmetic and first-order foundations 5. Second-order foundations
6. Foundations of Geometry