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 : EF such that Lf[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 ∈ MorL(E, F).

For any equivalence relation R on E, the quotient set E/R receives the L-structure E/R defined as LR[E], making (R) a quotient from E to E/R.
Then for any h : EX,

R ⊂ ∼h ⇒ (h ∈ MorL(E,X) ⇔ h/R ∈ MorL(E/R,X)).

Now if L is an algebraic language, the condition for an f : EF between L-systems to be a quotient, is written

{(Lf(x),f(y)) | (x,y) ∈ E} = F.

It implies ∀BF, B ∈ SubLFf *(B) ∈ SubLE.
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 : EF such that, ∀CX, equivalently

Mor(F,X) = {gXF | gf ∈ Mor(E,X)}
Mor(F,X) = {h/f | h ∈ Mor(E,X) ∧ ∼f ⊂ ∼h}
{h ∈ Mor(E,X) | ∼f ⊂ ∼h} = {gf | g∈Mor(F,X)}

Any retraction is a quotient.


Given an algebraic language L, a congruence on an L-system E is an equivalence relation R on E such that, equivalently, Proof of equivalence. 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 : VK and ACV holds, if E is a b-module (where V is structureless) then its quotient by any congruence is also a b-module.
Proof. 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 ACV 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 ∀iI, fi ∈ MorL(E,Fi), P = ∏iI Fi and g = ⊓iI fi ∈ MorL(E, P). Then

g = ⋂iIfi.

If all Fi are partial algebras then P is also a partial algebra, which explains that ∼g is a congruence.
Let G = Im gP. 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 ∀iI, hi = πi|G ∈ MorL(G,Fi). Then fi = hig. As with any composite of morphisms, if fi is a quotient then hi 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 ∈ MorL(E,X), and

Mor((X,f),(Y,g)) = {h ∈ MorL(X,Y) | hf = g}
Mor((⤓E, πE),(Y,g)) = {gE}

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, tGr ψE), its minimal congruence ≃E is 〈𝛿EL, and ⤓E is injective.


The formula R = 𝛿EF*(LR) is equivalent to

R ∈ MorL(E,℘(E)) ∧ ∀xE\Dom ψE, R(x) = {x}
where φ℘(E)(s,u) = {xOD | σ(x)=slx∈∏u}

which determines R when E is a draft.
The formula (*) expresses R ⊂ 𝛿EF*(LR), and is equivalent to the conjunction of
  1. ∀(x,y)∈R, x ∉ Dom ψEx = y
  2. ∀(x,y)∈Dom ψE, xRy ⇒ (xσ y ∧ Im(lxly) ⊂ 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
4.1. Algebraic terms
4.2. Quotient systems
4.3. Term algebras
4.4. Integers and recursion
4.5. Presburger Arithmetic
4.6. Finiteness and countability
4.7. The Completeness Theorem
4.8. More recursion tools
4.9. Non-standard models of Arithmetic
4.10. Developing theories : definitions
4.11. Constructions
4.A. The Berry paradox
5. Second-order foundations
6. Foundations of Geometry