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. In particular between algebras, the quotients are the surjective morphisms.

Equations

The L-equation identifying two L-terms X, Y from a given category of L-drafts with variables-preserving morphisms, is the L-equational system (V,Q,b) defined as follows, using the coproduct Z of X and Y in that category:Then for any L-algebra E and any u∈EV, the condition of equality between terms X and Y in E with valuation u (the equality of images of x and y), is equivalent to the existence of an f ∈ MorL(Q,E) extending u (i.e. such that u = f⚬b).

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 and any L-equational system (V, K, b), if ACV holds, then the quotient of any b-module (L-system) E 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.

In particular, for any morphism f ∈ MorL(E,F) between algebras E,F, any algebraic identity which holds in E also holds in the subalgebra Im f of F. For example, the action of any commutative monoid on any set X forms a family of transformations of X among which composition is commutative.

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.

Generating congruences

For any L-system E, the congruence of E generated by a graph R⊂E2, is defined as the intersection G of all congruences of E which include R (it is the "smallest" of them).

This can be expressed as G = 〈R〉L∪{Re,Sy,Tr} = 〈R ∪ 𝛿E〉〉L∪{Sy,Tr} where the algebraic symbols Re,Sy,Tr with arities 0,1 and 2 respectively express reflexivity, symmetry and transitivity, as explained in 3.8.

This generation process may be split into steps of generation by the successive structures (Re,Sy,L,Tr) (or even (Re,L,Sy,Tr) which is a bit harder to prove) according to the following theorem.

If E is serial and 𝛿E ⊂ R ∈ SubL(E2) then the transitive closure T of R is also L-stable.

Sketch of proof. Let S⊂ (E2)2 defined by

((x,y),(z,t)) ∈ S ⇔ ∃(s,u)∈ LE, ∃a∈Vs, u(a)=x ∧ ((s,u),z)∈ E ∧ ((s,(Vs∋i↦(i=a ? y : u(i)))),t)∈ E

The proof then goes by the following steps:
  1. If R is reflexive and L-stable then it is S-stable ;
  2. If R is S-stable and E is serial, then T is S-stable ;
  3. As T is reflexive, transitive and S-stable and all arities in L are finite, we deduce that T is L-stable. ∎
A technical difficulty at this stage is that finiteness was not formally defined yet; a proof may still be written with explicit arities (0,1,2...).

From this result, one may infer that any equality formula implied by a set of equality axioms, is more precisely 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 remarkable general fact was illustrated by the example of the proof of (g⚬f)-1 = f -1⚬g-1 in 2.8.

Minimal congruences

The minimal congruence of E is the one generated by ∅ (i.e. 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 an equivalence relation R is the preimage of ≃E/R by R⃗.

Sums of partial algebras

The category of all partial algebras over a given language has coproducts, also called the sum of a family of partial algebras, given by the condensate of their disjoint union.

It more generally has wide pushouts, which is the dual concept to that of wide pullback (3.10).
Namely, a pushout of f : X → Y and g : X → Z (where Y and Z are disjoint for simplicity), also called their amalgamated sum, is given by the quotient of Y∪Z by the congruence generated by Im(f⊓g).

The wide pushout of a family of quotients qi : X ↠ Yi (dual concept to that of intersections of subobjects) can also be expressed as the quotient of X by the congruence generated by ⋃i∈I ∼qi.

Quotients of algebras by equational systems

Given any L-algebra E, any L-equational system S = (V,K,b) and any tuple u : V → E, the pushout of u and b (in the category of partial algebras, as above) is a quotient of E we shall denote E/u:S.

Proof. Let (p,q) ∈ MorL(E,Q)×MorL(K,Q) a pushout of (u,b).
The subset Im p of the partial algebra Q is algebraic and thus stable.
Im q = q[〈Im b〉L] ⊂ 〈q[Im b]〉L = 〈Im p⚬u〉L ⊂ Im p
Im p = Im p ∪ Im q = Q. ∎

Another proof goes by checking that (for any serial system E),

Im b ⊂ Dom 〈Im(b⊓u)〉L,K×E ∈ SubL K ∴ Dom 〈Im(b⊓u)〉L,K×E = K. ∎

With the same E and S, assuming ACV and denoting M the category of all partial L-algebras which are b-modules, the acting category M(E) has an egg E/S given by the wide pushout of all quotients E ↠ E/u:S where u ranges over EV. (The proof is easy and left as an exercise.)

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.∎

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