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 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 : E → X,

R ⊂ ∼h ⇒ (h ∈ MorL(E,X) ⇔ h/R ∈ MorL(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

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

It implies ∀B⊂F, B ∈ SubLF ⇔ f⋆(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 as 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, ∀CX, equivalently

Mor(F,X) = {g∈XF | 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, 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 : V → K, V is structureless and ACV holds, if E is a b-module then its quotient by any congruence is also a b-module.
Proof. 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; the proof of uniqueness needs F to still be a partial algebra, but when E is serial (as often happens) this assumption 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 ∀i∈I, fi ∈ MorL(E,Fi), P = ∏i∈I Fi and g = ⊓i∈I fi ∈ MorL(E, P). Then

∼g = ⋂i∈I ∼fi.

If all Fi 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, hi = πi|G ∈ MorL(G,Fi). Then fi = hi⚬g. 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 defined as 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) | h ⚬ f = g}
Mor((⤓E, πE),(Y,g)) = {g/πE}

The congruence of E generated by any equivalence relation R (defined as the smallest congruence which includes 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 equals 〈𝛿E〉L, and ⤓E is injective.

Proof:

The formula R = 𝛿E ∪ F⋆(LR) is equivalent to

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

which determines R when E is a draft.
The formula (*) expresses R ⊂ 𝛿E ∪ F⋆(LR), and is equivalent to the conjunction of
  1. ∀(x,y)∈R, x ∉ Dom ψE ⇒ x = y
  2. ∀(x,y)∈Dom ψE, xRy ⇒ (x ∼σ y ∧ Im(lx⊓ly) ⊂ 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.

Other proof that the condensate F of an injective system (E, tGr ψE) is injective.
Let t∈LF, A = {x∈LE | LπE(x) = t} and B = {z∈ Dom ψE | ψE (z) ∈ A}.
Let R = ≃E ∩ {(x,y)∈ E2 | x∈B ⇔ y∈B}.
∀x∼σy ∈ Dom ψE, Im lx⊓ly ⊂ R ⊂ ≃E ⇒ (x ≃E y ∧ (x∈B ⇔ ψE(x) ∈ A ⇔ ψE(y) ∈ A ⇔ y∈B)) ⇒ xRy
R is a congruence, thus equal to ≃E.
Finally, ∀x,y ∈ Dom ψE, (x ≃E y ∧ x∈B) ⇒ y∈B.∎

Remark. For any graph G⊂E2, the transitive closure of 〈G ∪ 𝛿E〉L is L-stable. The proof of this is somewhat subtle, as it makes crucial use of the hypothesis that all symbols in L have finite arity (otherwise a counter-example can be given), thus can only be written once seen the basic properties of finiteness (4.6). As a consequence, the congruence generated by G equals the transitive closure of 〈G ∪ tG ∪ 𝛿E〉L. Actually (more subtly), it is also the transitive closure of 〈G ∪ 𝛿E〉L ∪ 〈tG ∪ 𝛿E〉L.
In the case of drafts, this result means that any equality formula coming as a theorem of a set of equality axioms, is directly deducible from them by means of a chain of equalities where any two successive terms in the chain differ by one or more substitutions of sub-terms directly given by axioms. This may be seen as a remarkable fact illustrated by the example of the proof of (g⚬f)-1 = f -1⚬g-1 in 2.8.

Set theory and foundations of mathematics
1. First foundations of mathematics
2. Set theory
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
4.7. Countability and Completeness
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