4.2. Quotient systems

This page is under construction. old French text

Condensed drafts

A draft D is condensed if, equivalently,
  1. D is functional, i.e. ΨD is injective;
  2. D has an injective interpretation in some algebra;
  3. For any two distinct elements of D there is an algebra interpreting them differently.
1.⇒2. if D≠∅ (otherwise replace D by a singleton), ∃φ∈DLD, φ০ΨD = IdOD, i.e. IdD interprets D in (D,φ).
2.⇒3.
3.⇒1. ∀x,yOD, if ΨD(x) = ΨD(y) then x,y have the same interpretation in every algebra.

Any draft D can be reduced to a condensed draft as follows.

Give ℘(D) the L-algebra structure (s,u) ↦ {xOD | σ(x)=slx∈∏u}.
Then the interpretation of D in ℘(D) which sends any variable x to {x}, is the curried form of the only equivalence relation on D which quotients it into a condensed draft.
Let us call condensation of D this projection of D to a condensed draft. This is the (not typographically convenient) way to confuse the repeated sub-terms of a given term (or draft), which will have the same meaning in all algebras.
This equivalence relation is included in that of any interpretation of D in any algebra, thus quotienting interpretations of D.

We can also compare separately given terms by reducing them to this case as any disjoint union of drafts (only keeping variables in common) is a draft.

If L only has symbols with arity 0 or 1 then every L-term is condensed.

Equational systems and equality of terms


The condition defined by an equational system is equivalent to : for any equality between terms found true in K where the list of free variables is B (or whose interpretation is a bijection with B), M also satisfies this equality written under universal quantifiers.
Indeed, the morphism f is defined by mapping any element of K, value of any term with variables in B, into the element of M defined by the same term; for this to be coherent, 2 terms with the same value in K should also have the same value in M.
Conversely, any formula made of universal quantifiers over an equality of terms t=t', is equivalent to the satisfaction of some (K,B), that is the quotient of the algebra of all terms with the same variables, by the relation of being obtainable from each other by replacements of occurrences of t and t' as subterms.

If the family (Ki,Bi)iI encompasses all arities (at least those present in L), then we may as well forget L and reinterpret the L-algebras in this variety, as (⋃iI Ki)-algebras. However, two questions remain:

These questions will be positively answered below.

Some stability properties of varieties

Theorem. For any L-algebra A and any variety V of L-algebras, the category of all (M,f) where M is an L-algebra in V and f ∈MorL(A,M), has an initial object (A',φ), called the quotient of A by the family of conditions defining the variety.

Proof.

Let H be the set of all equivalence relations h on A such that A/h is an L-algebra in V, with the canonical projection ph∈MorL(A,A/h).
Let φ =∏hH ph and A' = Im φ ⊂ P =∏hH A/h.
A' satisfies all (Ki,Bi)iI because it is a subalgebra of a product P of L-algebras that do.
To verify that (A',φ) is an initial object in this category, let (M,f) be another object. We need to show that there is a unique morphism g from (A',φ) to (M,f), i.e. g∈MorL(A',M) such that gφ=f.
In the work on quotients (2.9) we saw the existence of a unique g such that gφ=f, written g=f/φ with domain Im φ = A', provided that ~φ ⊂~f . The condition of uniqueness here is Im φ = A'. The existence is obtained as g=j০πh, where h = ~f ,  πh ∈MorL(A',A/h) is the restriction of the canonical projection of P on its factor A/h, and j = (f/h) ∈ MorL(A/h,M). Indeed,
g
φ = j০πhφ = jph = f.    ∎
Now we can answer the previous questions.
First, to replace (Ki,Bi) by some (K'i,B'i) where K'i satisfies all (Kj,Bj) : we just need to take as K'i the quotient of Ki by this family of conditions.
If the restriction of this quotient φ to Bi was not injective, then only trivial algebras (empty or singletons) would satisfy all conditions. Indeed:
If there is an L-algebra M with elements xx' and satisfying all conditions then for all bb' in B, ∃uMBi , u(b)=xu(b')=x' and ∃f∈MorL(Ki,M), f|B=u thus ∃g∈MorL(K'i,M), gφ=f, and φ(b)φ(b') because f(b)≠f(b').
Now assuming it injective, the arity is preserved; the verification of equivalence of the conditions (Ki,Bi) and (K'i,B'i) as predicates on the class of algebras satisfying all (Kj,Bj) for ji , is straightforward and left to the reader.

Now for fusing several conditions (K,B) and (K',B') with the same arity into one: just take the quotient (K",B") of (K,B) by the condition (K',B'). For the same reason as the previous question, any algebra satisfying both will satisfy (K",B").
Any M satisfying (K",B") will satisfy (K,B); let us verify (K',B'), still assuming that we have a bijection v from B" to B' :∀uMB', since M satisfies (K",B"), the map uvMB" is extensible as a morphism f ∈ MorL(K",M). Since (K",B") satisfies (K',B'), the map v-1 from B' to B" is extensible as g∈MorL(K',K"). Thus fg∈MorL(K',M) is an extension of u.∎
In fact, when B and B' are in bijection, the quotient of (K,B) by both conditions (K,B) and (K',B') (plus any list of other conditions), is isomorphic to the quotient of (K',B') by the same conditions.

In any concrete category,

Section ⇒ Embedding ⇒ Injective morphism
Retraction ⇒ Quotient ⇒ Surjective morphism


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