4.2. Quotient systems
Quotients of relational systems
Given a relational language L and two L-systems
E and F, a quotient from E to F is a surjective morphism f
: E↠F such that ^{L}f[E] =
F. We also say that the system F is a quotient of E by ∼_{f}.
This condition defines F from E and f,
as the smallest L-structure on F such that
f ∈ Mor_{L}(E, F).
For any equivalence relation R on E, the quotient set
E/R receives the L-structure E/R defined as
^{L}R⃗[E], making (R⃗)
a quotient from E to E/R.
Then for any h : E → X,
R ⊂ ∼_{h} ⇒ (h ∈ Mor_{L}(E,X) ⇔
h/R ∈ Mor_{L}(E/R,X)).
Now if L is an algebraic language, the condition for an f : E↠F
between L-systems to be a quotient, is written
{(^{L}f(x),f(y)) | (x,y) ∈ E}
= F.
It implies ∀B⊂F, B ∈ Sub_{L}F ⇔ f *(B) ∈ Sub_{L}E.
Any morphism from a serial system to a partial algebra is a quotient to its image, which is
a stable algebra.
Quotients in concrete categories
The concept of quotient has an equivalent definition expressible for any concrete category C,
similar to the concept of embedding
with sides reversed. This can be explained by being the same concept as embedding in the opposite category, once the
concreteness of the category is re-expressed as a link with the category of sets, independently of
the details of the category of sets, which can thus be replaced by any other category,
namely the opposite category to the category of sets.
So, a quotient from E to F in C is a surjective
morphism f : E↠F such that, ∀_{C}X, equivalently
Mor(F,X) =
{g∈X^{F} | g⚬f ∈ Mor(E,X)}
Mor(F,X) =
{h/f | h ∈ Mor(E,X) ∧ ∼_{f} ⊂ ∼_{h}}
{h ∈ Mor(E,X) |
∼_{f} ⊂ ∼_{h}} = {g⚬f | g∈Mor(F,X)}
Any retraction is a quotient.
Congruences
Given an algebraic language L, a congruence on an
L-system E is an equivalence relation R on E such that, equivalently,
- R ∈ Sub_{L}(E^{2})
- The quotient system E/R is a partial algebra.
- There exists a morphism f : E → F where F is a partial algebra
and ∼_{f} = R.
Proof of equivalence. Let f
: E → F such that ∼_{f} = R, and K = {(^{L}f(x),f(y)) |
(x,y) ∈ E}.
R ∈ Sub_{L}(E^{2}) ⇔
(∀s∈L, ∀(x,y),(x',y')∈s_{E},
Im(x⊓x') ⊂ R ⇒ (y,y') ∈ R)
⇔ (∀(x,y),(x',y') ∈ E, ^{L}f(x) =
^{L}f(x') ⇒ f(y) = f(y')) ⇔
K is functional.
If K = F, this means F is a partial algebra. Otherwise,
f ∈ Mor_{L}(E,F) ⇔ K ⊂ F ⇒
(F is a partial algebra ⇒ K is functional).∎
Thus, the quotient of any algebra or other serial system by a congruence, is an algebra.
In this case, a congruence can be essentially described as a binary relation
satisfying the axioms of equality.
Quotients of modules
Not all quotients of modules are modules. But for any algebraic
language L, any L-system E, and any L-equational system
(K, b), where b : V→K and AC_{V}
holds, if E is a b-module (where V is structureless) then its quotient by any
congruence is also a b-module.
Proof. Let f : E ↠ F a quotient to a partial algebra F.
∀u∈F^{V}, ∃v∈E^{V}, f⚬v = u ∧
∃g∈Mor_{L}(K,E), g⚬b = v
∴ f⚬g⚬b = u.
Uniqueness was seen before.∎
While this proof only needs f to be a surjective morphism, not precisely a quotient,
in practice this will only be used with quotients. Indeed, f is a quotient for the smallest
structure of F which makes f a morphism; greater structures preserve
existence; to ensure uniqueness we need F to still be a partial algebra, but when
E is left serial this implies that f is a quotient anyway.
Actually the AC_{V} hypothesis is not needed, as infinite equational
systems will be seen equivalent to sets of finite ones, where finite choice applies.
Intersections of congruences
On any L-system E, any intersection of equivalence relations is an equivalence relation ;
and any intersection of congruences is a congruence.
This can be seen as a case of intersection of
stable subsets, as equivalence
relations are the stable relations by some structure, and the same for congruences. But
here is another viewpoint on this:Let ∀i∈I,
f_{i} ∈ Mor_{L}(E,F_{i}), P =
∏_{i∈I} F_{i} and g = ⊓_{i∈I}
f_{i} ∈ Mor_{L}(E, P). Then
∼_{g} = ⋂_{i∈I}
∼_{fi}.
If all F_{i} are partial algebras then P
is also a partial algebra, which explains that ∼_{g} is a congruence.
Let G = Im g ⊂ P. Like any morphism, g will be a
quotient to its image G if E is serial and P is a partial algebra, but not
necessarily otherwise.
Let ∀i∈I, h_{i} = π_{i|G}
∈ Mor_{L}(G,F_{i}).
Then f_{i} = h_{i}⚬g. As with any composite of
morphisms, if f_{i} is a quotient then h_{i} is also a quotient.
Minimal congruences
The minimal congruence of any L-system E is the intersection of all its
congruences. Let us write it ≃_{E}, or simply ≃ when E is given by context.
It is equality if and only if E is a partial algebra.
Let us call condensate of E its quotient by its minimal congruence, and π_{E} the natural surjection to it:
⤓E = E/≃
π_{E} = ≃⃗_{E} : E ↠ ⤓E
(⤓E, π_{E}) is initial in the category of (X,f) where X is
a partial L-algebra, f ∈ Mor_{L}(E,X),
and Mor((X,f),(Y,g)) = {h ∈ Mor_{L}(X,Y) |
h ⚬ f = g}
Mor((⤓E, π_{E}),(Y,g)) = {g/π_{E}}
The congruence of E generated by any equivalence relation R is the preimage of
≃_{E/R} by R⃗.
In the category of partial algebras, the coproduct
is given by the condensate of the disjoint union.
Condensates of injective systems
For any injective L-system (E, ^{t}Gr ψ_{E}),
its minimal congruence ≃_{E} is 〈𝛿_{E}〉_{L},
and ⤓E is injective.
Proof:
ψ_{E} = σ ⊓ l
F = E^{2}
∴ F = {((σ(x), l_{x}⊓l_{y}), (x,y)) |
x ∼_{σ} y}
R = 〈𝛿_{E}〉_{L} =
𝛿_{E} ∪ F_{*}(^{L}R) ⊂ F
(*) ∀(x,y)∈R, (x = y ∉ Dom ψ_{E}) ∨
(x ∼_{σ} y ∧ Im(l_{x}⊓l_{y}) ⊂ R).
S = {(x,y)∈F | ∀z∈R⃖(y), zRx}
∀(x ∼_{σ} y),
∀z∈R⃖(y), z ∼_{σ} y ∧
Im(l_{z}⊓l_{y}) ⊂ R
∴
(Im(l_{x}⊓l_{y}) ⊂ S ⇒
Im(l_{z}⊓l_{x}) ⊂ R ⇒ zRx)
𝛿_{E} ⊂ S ∈ Sub_{L} F ∴ R ⊂ S
R being reflexive and left Euclidean
is an equivalence relation. So it is ≃_{E}.
Hence by (*) the injectivity of ⤓E.∎
The formula R = 𝛿_{E} ∪ F_{*}(^{L}R)
is equivalent to
R⃗ ∈ Mor_{L}(E,℘(E)) ∧ ∀x∈E\Dom ψ_{E},
R⃗(x) = {x}
where φ_{℘(E)}(s,u) =
{x∈O_{D} | σ(x)=s ∧ l_{x}∈∏u}
which determines R when E is a draft.
The formula (*) expresses R
⊂ 𝛿_{E} ∪ F_{*}(^{L}R), and is equivalent
to the conjunction of
- ∀(x,y)∈R, x ∉ Dom ψ_{E} ⇒ x = y
- ∀(x,y)∈Dom ψ_{E}, xRy ⇒
(x ∼_{σ} y ∧ Im(l_{x}⊓l_{y}) ⊂ R).
If R is an equivalence relation, 2. says the structure of E/R is injective, while 1.
means it has the same variables as E. Thus in a draft, the equivalence relations
which fit (*) are those of variables-preserving morphisms to some other draft.
Therefore, the minimal congruence
of a draft is its only congruence by which the quotient is a (functional) draft with the same variables ;
it is the preimage of = by any variables-preserving morphism to a functional draft.
Set theory and foundations
of mathematics
1. First foundations of mathematics
2. Set theory (continued)
3. Algebra 1
4. Arithmetic and first-order foundations
5. Second-order foundations
6. Foundations of Geometry