Composition of relations

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 = {(x₀,y₁) | (x,y)∈R×S ∧ x₁=y₀}
∀R⊂E×F, ∀S⊂F×G, R;S = {(x,z)∈E×G | ∃y∈F, xRy ∧ ySz}
= ∐_x∈E S^⋆R⃗(x)

This extends the composition of functions coming as functional relations, with the same identity elements (1_E = 𝛿_E = Gr Id_E).
(This is the only natural way to extend composition, as the other expression of the composite of functions by their graphs, with ∀y∈F, xRy ⇒ ySz, 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 (_⋆): ∀R⊂E×F, ∀S⊂F×G,

∀A⊂E, (S⚬R)^⋆A = S^⋆(R^⋆A)
∀B⊂G, (R;S)_⋆B = R_⋆(S_⋆B)

For this action, each object (set) E has a basis made of its singletons : ({x})_x∈E, 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 E_i is given by their union, with the morphisms 𝛿_{E_i} from each E_i 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: ∀R⊂E×F, ∀A⊂E, ∀B⊂F,

＊×(R^⋆A) = (＊×A);R
(R_⋆B)×＊ = 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×＊) = ∅ ⇔ A ∩ R_⋆(B) = ∅ ⇔ B ∩ R^⋆(A) = ∅
(∁_F⚬R^⋆, ∁_E⚬R_⋆) ∈ Gal(℘(E), ℘(F))
(R^⋆, ∁_E⚬R_⋆⚬∁_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,

R⊂S ⇒ R;T ⊂ S;T
R⊂S ⇒ T;R ⊂ T;S
(R∪S);T = R;T ∪ S;T
T;(R∪S) = T;R ∪ T;S

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

T;⋃_i∈I R_i = ⋃_i∈I T;R_i
T⚬⋃_i∈I R_i = ⋃_i∈I T⚬R_i

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

∀S⊂E×F, S ⊂ R;S
∀S⊂F×E, S ⊂ S;R

The transitivity of R can be written R;R ⊂ R.
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 A⊂E, reflected by the Galois connection (End, Sub)∈ Gal(℘(℘(E)), ℘(E^E)) introduced in 3.4, is equivalent to that of single relations R ⊂ E² (non-functional structures named by a single function symbol) in the Galois connection (Po, Sub)∈ Gal(℘(℘(E)), ℘(E²)) defined as relating any A⊂E to (x,y)∈E² by (x∈A ⇒ y∈A):

A ∈ Sub_R E ⇔ R^⋆A ⊂ A ⇔ (∀(x,y)∈R, x∈A ⇒ y∈A) ⇔ ∁_E A ∈ Sub_^tR E

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

E ∋ z ↦ (z=x ? y : z).

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

∀x,y∈E, (x,y)∈Po(G⃗[K]) ⇔ (∀z∈K, zGx ⇒ zGy) ⇔ 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|x∈A}. Namely, ∈⃗ defines a pre-embedding from (E,Po(S)) to (℘(S),⊂).

The closure Po(Sub_RE) of any R ⊂ E² 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. (∀i∈I, R^⋆A_i ⊂ A_i) ⇒ R^⋆⋃_i∈I A_i = ⋃_i∈I R^⋆A_i ⊂ ⋃_i∈I A_i ∎
Second proof. Use A ∈ Sub_R E ⇔ ∁_E A ∈ Sub_^tR E and the similar property with intersections.∎

Proposition. ∀A⊂E, 〈A〉_R = ⌈R⌉^⋆A.

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

∀y∈E, x⌈R⌉y ⇔ (∀A∈Sub_RE, x∈A ⇒ y∈A) ⇔ y∈〈{x}〉_R

Then, ⌈R⌉^⋆A = ⋃_x∈A 〈{x}〉_R ⊂ 〈A〉_R because A ↦ 〈A〉_R is monotone.
We conclude by ⌈R⌉^⋆A ∈ Sub_R E from the above lemma.∎

From the end of 3.3 we get ∀A⊂E, 〈A〉_R = A ∪ R^⋆〈A〉_R.
By the faithfulness of the action, it can also be written

⌈R⌉ = 𝛿_E ∪ R⚬⌈R⌉

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

Transitive closure

For any R⊂E², the smallest transitive T⊂E² such that R⊂T (which exists as transitivity is preserved by intersections), called the transitive closure of R, is

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

Proof. By hypothesis, R ⊂ T and R⚬T ⊂ T⚬T ⊂ T, thus ⌈R⌉⚬R ⊂ T by the above result (⌈R⌉⚬R is the smallest T such that R ∪ R⚬T ⊂ T).
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 R ⊂ E² is called well-founded if ∀A⊂E, A ⊂ R^⋆A ⇒ A = ∅.
This does not depend on E such that R ⊂ E² for a given graph R, and implies that any S ⊂ R is also well-founded.
Any well-founded relation is irreflexive : ∀x, x ∉ R^⋆{x}.

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

Proof. If R ⊂ E² is well-founded, T = R⚬P and P = 𝛿_E ∪ T (namely, P=⌈R⌉), then T is well-founded:

∀A⊂E, A ⊂ T^⋆A ⇒ P^⋆A = A∪ T^⋆A = R^⋆P^⋆A = ∅ ∎

Note: the well-foundedness of R implies the uniqueness of P such that P = 𝛿_E ∪ R⚬P.
The proof goes by considering A = {x∈E | P⃖(x) ≠ P'⃖(x)} for P and P' with this property ; this is a first example of a definition by well-founded induction, concept which will be developed later.

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⌉ = 𝛿_E ∪ T.∎
(The antisymmetry of a well-founded R can also be deduced by ∀x,y,¬{x,y}⊂R^⋆{x,y})

Well-order

A relation R ⊂ E² is called a strict well-order on E if

∀A⊂E, A = ∅ ∨ ∃!:A\(R^⋆A)

It is easy to see that any strict well-order is a well-founded strict total order; conversely, any well-founded R ⊂ E² whose complement ∁_E² R is antisymmetric, is a strict well-order on E.
Given that the corresponding total order ≤ equals ∁_E² ^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

∀A⊂E, A = ∅ ∨ ∃!x∈A, A ⊂ ≤⃗(x)

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

Greatest and least elements

In any ordered set (E,≤), an x∈E is called a lower bound (resp. upper bound) of a subset A⊂E if A ⊂ ≤⃗(x) (resp. A ⊂ ≤⃖(x)). If moreover x∈A, 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): ∀A⊂E, ∀x∈E,

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