3.12. Composition of relations
The category of relations
The category of relations is defined as an extension of the category of sets: keeping the same
objets (the sets) and defining
Mor(E,F) as the set ℘(E×F) of all relations between them.
The composition of relations is defined by
∀grR,S, R;S = {(x0,y1) |
(x,y)∈R×S ∧ x1=y0}
∀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 represented by functional relations, with the
same identity elements (1E = 𝛿E = Gr IdE),
and keeps associativity (while the other expression of the composite of functions by their graphs,
with ∀y∈F, xRy ⇒ ySz, loses associativity in non-functional cases).
This category faithfully acts by direct images (⋆)
on the powersets of its objects, and symmetrically also 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 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, 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 associativity of composition, they form a third kind of Galois connection:
(*×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 Ri indexed by I and any graph T,
T;⋃i∈I Ri =
⋃i∈I T;Ri
T⚬⋃i∈I Ri =
⋃i∈I T⚬Ri
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 to define stability conditions on subsets A⊂E,
reflected by the Galois connection (End, Sub)∈ Gal(℘(℘(E)), ℘(EE)) introduced in 3.4,
is equivalent to that of single relations R ⊂ E2 (non-functional structures named
by a single function symbol) in the Galois connection
(Po, Sub)∈ Gal(℘(℘(E)), ℘(E2)) defined as relating any A⊂E to
(x,y)∈E2 by (x∈A ⇒ y∈A):
A ∈ SubR E ⇔ R⋆A
⊂ A ⇔ (∀(x,y)∈R, x∈A ⇒ y∈A) ⇔
∁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
E ∋ z ↦ (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 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 all S⊂℘(E) appear that way with
{(A,x)∈S×E|x∈A}.
Namely, ∈⃗ defines a pre-embedding from (E,Po(S)) to (℘(S),⊂).
The closure Po(SubRE) of any R ⊂ E2 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 would not work with structures of other arities).
First proof. (∀i∈I, R⋆Ai
⊂ Ai) ⇒ R⋆⋃i∈I Ai =
⋃i∈I R⋆Ai ⊂ ⋃i∈I Ai ∎
Second proof. Use A ∈ SubR E ⇔ ∁E A ∈ SubtR 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∈SubRE, 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 ∈ SubR E from the above lemma.∎
We have ∀A⊂E, 〈A〉R =
A ∪ R⋆〈A〉R (adapted from the end of 3.3).
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⊂E2, ⌈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⊂E2, the smallest transitive T⊂E2
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.
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 symmetry of the problem, T = R⚬⌈R⌉.∎
Well-founded relations
A relation R ⊂ E2 is called well-founded if ∀A⊂E, A ⊂
R⋆A ⇒ A = ∅.
It does not depend on E, 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 a well-founded relation R is well-founded.
Proof. If R ⊂ E2 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 (possible exercise): if R is well-founded then actually
!P, P = 𝛿E ∪ R⚬P.
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 ⊂ E2 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 ⊂ E2 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
∀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)
The successor function
In any ordered set (E,≤) with strict order <, the successor is the functional relation
S on E defined by ∀x,y∈E,
xSy ⇔ y :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
xSy ⇔ x :max <⃖(y) ⇔ ≤⃖(x) = <⃖(y)
If it is a well-order then ∀x∈E,
x ∉ Dom S ⇔ <⃗(x) = ∅ ⇔ x :maxE.
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