Term-Rewriting Systems and Descent in Some Categories

Dali Zangurashvili

A. Razmadze Mathematical Institute, 1, Alexidze Str., Tbilisi, 0193, Georgia

The  Argument

This presentation deals with an issue from A. Grothedieck descent theory, which I will specify a bellow. First I would like to point out that this issue has two-fold touch with computer science. On the one hand, this issue is important for some fields of computer science, for example the theory of multi-agent systems, which has been studied by Professor T. Porter from University of Wales Bangor (see [P1], [P2]).  On the other hand, the issue itself can be solved by means of computer programming, as we show in our work, since we reduce it to an issue from the theory of term-rewriting systems. Applying computer programming methods to the issues from descent theory has not, to the best of my knowledge, been attempted yet by anyone. 

Let us now specify what subject we deal with here. First let us note that descent theory goes back to the problem of A. Weil to study rational points of algebraic varieties, and was developed by A. Grothendieck in the middle of the 20th century [G1], [G2]. Descent theory is closely related to Galois theory. Descent theory provides ways of gluing local information together to obtain global information and is a powerful tool for describing so-called locally trivial objects in various areas of algebra and topology. The main notions of descent theory are those of a descent morphism and of an effective descent morphism. Since we are going to deal with (effective) descent morphisms in categories being dual to varieties of universal algebras (we call them (effective) codescent morphisms in the initial categories, i.e. varieties themselves), let us recall  the relevant definitions directly in the dual form.  A morphism 𝓅: ℬ->ℰ of  a category ℂ is called a codescent (resp. effective codescent) morphism if the change-of-cobase functor 

(Subscript[𝓅, ⋆]) : ℬ/ℂ→ℰ/ℂ

is pre-co-monadic (resp. co-monadic), i.e. the comparison functor 

𝔉𝓅: ℬ/ℂ→ℂ𝕠𝕕𝕖𝕤(𝓅),

where ℂ𝕠𝕕𝕖𝕤(𝓅) is the Eilenberg-Moore category of the co-monad induced by the adjunction

(Subscript[𝓅, ⋆])⊣(𝓅^(!))

is full and faithful (resp. an equivalence of categories). Recall that objects of ℂ𝕠𝕕𝕖𝕤(𝓅) (called codescent data with respect to 𝓅) are triples (𝒞,γ,ξ) with 𝒞 being an object of  ℂ and γ, ξ being morphisms ℰ->𝒞 and 𝒞->𝒞(Subscript[⊔, ℬ])ℰ, respectively, such that the following equalities are valid (see left and right figures below):

ξγ=(Subscript[𝒾, 2]),
((Subscript[1, 𝒞]),γ)ξ=(Subscript[1, 𝒞]),
((Subscript[𝒾, 1(Subscript[⊔, ℬ])])(Subscript[1, ℰ]))ξ=((Subscript[ξ, (Subscript[⊔, ℬ])])(Subscript[1, ℰ]))ξ.






Also recall that the functor 𝔉𝓅 maps every 𝒻: ℬ->𝒟 to

(𝒟(Subscript[⊔, ℬ])ℰ, (Subscript[𝒾, 2]^(')), (Subscript[(Subscript[𝒾, 1]^(')), (Subscript[⊔, ℬ])])(Subscript[1, ℰ])),

where (Subscript[𝒾, 1]^(')) and  (Subscript[𝒾, 2]^(')) are the pushouts of 𝓅 and 𝒻, respectively, along each other.

Effective descent morphisms were described in many important categories from geometry (see, for example, [JT], [JoTi], [Mo], [V], [JS], [JT], [P] [RT], [ST]). In contrast to the case of categories of the geometrical character, only few results are known on the following problem: which morphisms are (effective) descent morpisms in categories being dual to varieties of algebras.  Non-trivial known cases where such morphisms were described  include commutative rings with units (Joyal-Tierney (unpublished); Mesablishvili [M];  Janelidze-Tholen [JT1]), Boolean algebras (Makkai (unpublished)) and groups (Zangurashvili [Z1]). 

 Recently we have  noticed that this issue is simplified if a given variety of universal algebras satisfies the amalgamation property (among varieties satisfying this property are varieties of Abelian groups, groups, quasi-groups, Lie-algebras and so on. Recall that a variety is said to satisfy the amalgamation property if for any monomorphisms ν: 𝒞->𝒟 and μ: 𝒞->𝒞', there exist a commutative square


with monomorphic  μ' and ν'). In particular, we found the necessary and sufficient condition for a morphism in the category being dual to such a variety to be a descent morphism. Namely, we proved the following

Theorem 1 (Zangurashvili [Z1]).
 A monorphism  𝓅: ℬ->ℰ of a variety satisfying the amalgamation property  is a descent morphism if and only if ℛ'⋂(ℬ×ℬ)=ℛ for any congruence ℛ on ℬ and its closure ℛ' in ℰ .

In the case of finite ℬ and ℰ, we can verify this condition by means of computer programming. Knowing this theorem, the issue whether all descent morphism are effective turns out to be important for the description of effective descent morphisms in categories being dual to varieties of universal algebras with the amalgamation property. Recently we found  the following sufficient condition for this:

Theorem 2 (Zangurashvili [Z3]).

This theorem turned out to play the key role in our further investigation of the issue. To give the main result of this work, let us restrict our consideration to only Mal’tsev varieties. The example of Mal'tsev variety is given by any one of algebras equipped by a group structure. Recall that a variety of universal algebras is called Mal’tsev if there exists a ternary term 𝓆(𝓍, 𝓎, 𝓏) such that the following identities (called Mal'tsev identities) are satisfied:

𝓆(𝓍, 𝓍, 𝓎)=𝓎
𝓆(𝓍, 𝓎, 𝓎)=𝓍.

Note that each Mal’tsev variety has a presentation (𝒯, Σ)  such that 
(i)  one of the parts (say , the right one) of any identity from Σ is either a variable involved in the left part or a nullary operation symbol, and the length of the left part of the identity is greater than 1;
(ii) the set of identities contain both Mal'tsev identities;
(iii) for any identity
𝓉=t'
from Σ and each subterm t'' of 𝓉 not being neither a variable nor a nullary operation symbol, the set of variables of 𝓉 is equal to the set of variables of t''.

From now on we will assume that a variety is given by the presentation satisfying conditions (i)-(iii).  Below under  “reduction” and   “irreducible term” we mean, respectively,  a reduction and an irreducible term, with respect to the term-rewriting system related to (𝒯, Σ).

Theorem 3.  
Let the following condition be satisfied

(**)  for any identity
𝓉=t'
from Σ, performing any sequence of reductions over the term 𝓉, we arrive either at a reducible term or at the term 𝓉'.

Then every codescent morphism is effective.

The condition (i) guarantees that the number of reduction sequences mentioned in (**)  is finite. Actually, the number of all reductions mentioned in this condition is limited to the number identities from Σ multiplied by the number of occurrences of operations in the term 𝓉. This implies that we can verify the condition (**) in a finite (reasonable) number of steps, and hence to realize it in a computer. In the particular cases of Abelian groups, quasi-groups, and loops, the verification process was conducted by hand; in the general case, such verification would prove time-consuming and laborious in the extreme.  Hence the need for (and definite advantages of) a Mathematica-based algorithmic approach.

References
[G1] A. Grothendiek, Technique de descente et théoremes d’existence en géometrie algébraique, I. Géneralités. Descente par morphismes fidélement plats, Séminaire Bourbaki 190 (1959).
[G2] A. Grothendiek, Categoeries fibrees et descente, Expose VI, in: Revetements Etales et Groupe Fondamental (SGA1), Lecture Notes in Mathematics, 224 (Springer, Berlin 1971), 145-194
 [JS] G. Janelidze and M. Sobral, Finite preorders and topological descent, I, J. Pure Appl. Algebra, 175 (1-3) (2002), 187-205.
[JT] G. Janelidze and W. Tholen, Facets of descent, I, Appl. Categ Structures 2 (1994), 245-281.
[JT1] G. Janelidze and W. Tholen, Facets of descent, III: Monadic descent for rings and algebras, Appl. Categ. Str. 12, 5-6, 2004, 461-477. 
[JoTi] A. Joyal and M. Tierney, An extension of the Galois theory of Grothendieck, Mem. Amer. Math. Soc., 51, No. 309 (1984).
 [M] B. Mesablishvili, Pure morphisms of commutative rings are effective descent morphisms for modules—a new proof, Theory Appl. Categ., 7 (2000), No. 3, 38-42.
[Mo] I. Moerdijk, Descent theory for toposes, Bull. Soc. Math. Belgique, 41 (1989), 373-391.
 [P1] T. Porter, Geometric Aspects of Multiagent Systems, Electronic Notes in Theoretical Computer Science, 81 (2003) URL: http://www1.elsevier.com/gej-ng/31/29/23/139/23/show/Products/notes/index.htt .
[P2] T. Porter, Interpreted systems and Kripke models for multiagent systems from a categorical perspective, Theoretical Computer Science, 323 (2004) pp. 235-266.
[P] T. Plewe, Localic triquotient maps are effective descent morphisms, Math. Proc. Cambridge Phil. Soc., 122 (1997), 17-43.
[RT] J. Reiterman and W. Tholen, Effective descent maps of topological spaces, Topology Appl., 57 (1994), 53-69.
[ST] M. Sobral and W. Tholen, Effective descent morphisms and effective equivalence relations, Canadian Mathematical Society Conference Proceedings, vol. 13 (AMS, Providence 1992), 421-43.
[V] J. J. C. Vermeulen, Proper maps of locales, J. Pure Appl. Algebra, 92 (1994), 79-107.
[Z1] D. Zangurashvili, The strong amalgamation property and (effective) codescent morphisms, Theory Appl. Categ., 11, 20 (2003), 438-449
[Z2] D. Zangurashvili, Effective codescent morphisms, amalgamations and factorization systems, J. Pure Appl. Algebra, 209, 1 (2007), 255-267.
[Z3] D. Zangurashvili, Effective codescent morphisms in some varieties of universal algebras, arXiv: math.CT/0610643.

Section head

Lorem ipsum dolor sit amet, consectetuer adipiscing elit. Pellentesque enim dolor, euismod sit amet, rutrum nec, fermentum id, risus.

Plot3D[Sin[x y],{x,0,4},{y,0,4}]

Mauris auctor nunc ac nisl. Nunc non turpis a dolor porta tristique. Nam accumsan massa scelerisque sapien.