Papers
C. Wolf, Mehrsortige abelsche Algebren in kongruenzmodularen Varietäten, Diplomarbeit, Fachbereich Mathematik, Technische Hochschule Darmstadt, 1993 |
C. Wolf, Many-sorted algebras in congruence modular varieties, Algebra Universalis 36 (1996), 66-80 |
C. Wolf, Many-sorted Abelian algebras in congruence modular varieties, Algebra and Model Theory (A. G. Pinus and K. N. Ponomaryov, eds.), Novosibirsk State Technical University, 1997, pp. 230-237 |
C. Wolf, Restrictions and companions: Two ways from many-sorted to one-sorted Algebras, Shaker Verlag, Aachen, 1997 |
Many-Sorted Algebras in Congruence Modular Varieties
Abstract
We present several basic results on many-sorted algebras, most of them only valid in congruence modular varieties. We describe a connection between the properties of many-sorted varieties and those of varieties of one sort and give some results on functional completeness, the commutator and Abelian algebras.
Introduction
Many-sorted algebras were introduced by P. J. Higgins as an extension of one-sorted algebras. He examined properties of free algebras and varieties. Since then the theory of many-sorted algebras has been influenced mainly by the requirements of computer science. There definitions like abstract data types and algebraic specifications were placed in the foreground. In contrast to that, this paper concentrates on results which are obtained by methods and motivated by goals which are efficient in the structure theory of one-sorted algebras. For this congruence modular varieties seem to be a good starting point.First we give some basic definitions and results. In the second section we define for a many-sorted algebra the restriction to one sort which plays an important role in the rest of this paper. We show that those properties of many-sorted varieties given by congruence equations can be characterized by those of varieties generated by restriction to the sorts. Then we give conditions for many-sorted algebras to be functionally complete. In the last section we compare the many-sorted to the one-sorted commutator and characterize many-sorted Abelian algebras in congruence modular varieties.
We assume the reader to be familiar with the theory of one-sorted universal algebra.
Restrictions and Companions:
Two Ways from Many-Sorted to One-sorted Algebras
Introduction
Many-sorted algebras are, if we lift the limitation that an algebra is allowed to have only one universe, a natural extention of universal algebras (here called one-sorted algebras). So, many-sorted algebras consist of a family of universes indexed by a set whose elements are called sorts, and of operations. They were introduced by P. J. Higgins, where he called them algebras with a scheme of operators. He defined the basic elements of the theory of many-sorted algebras like homomorphisms, subalgebras, direct products, congruences, equations, varieties and free algebras, and examined their fundamental properties.Since then, the theory of many-sorted algebras has been influenced mainly by the requirements of computer science. There, definitions like abstract data types, algebraic specifications or initial semantics, and questions about correctness, specifiability or implementations were placed in the foreground. Also order-sorted algebras, which are many-sorted algebras with a partial order on the sort set and additional conditions on the operation symbols and fundamental operations were examined extensively.
In contrast to that, this paper concentrates on results which are obtained by methods which are efficient in the mathematical theory of one-sorted algebras. These will be a mixture of older results (functional completeness, Abelian algebras) and newer results (decidability, categorical equivalence). We will prove these results in a special way: We construct a one-sorted algebra from a many-sorted algebra in a manner that we can transfer properties of many-sorted algebras to the corresponding one-sorted properties. Then we apply known one-sorted results and show that this leads to the many-sorted result. To achieve this for various questions, two kinds of constructions are given, the restriction to a sort and the one-sorted companion. Both of them have their advantages and disadvantages which we will discuss in the corresponding chapters.
Before we present the content of this thesis, we will make some remarks on sorts with empty universe: Some authors permit empty universes while others do not permit them. Here, regardless of the problems which arise, for example concerning the validity of equations (see Section 2), empty universes are allowed. In Chapter II they are even necessary to obtain a suitable transfer of many-sorted results to one-sorted results, and vice versa, while in Chapter III they sometimes cause problems.
Chapter I recalls the basics of many-sorted algebras.
In the first section, we start with the definitions of
many-sorted signatures and algebras. We look at
many-sorted modules over ringoids, which
will play an important role in some of the following sections.
Then we define many-sorted subalgebras, congruence relations,
homomorphisms, and direct products.
The second section deals with material concerning terms,
equations and varieties like term functions and
polynomial functions, the operators H, S and P, or
free algebras.
In Chapter II we examine the first kind of construction that we are
interested in, namely the restriction to a sort.
In Section 3 we introduce restrictions which give a
one-sorted algebra for every sort. Hence, the information about the
relationship between the sorts is lost.
We examine the action of the operators H, S, and P
which leads to the following nice result: the one-sorted variety
generated by the restriction of a many-sorted algebra
to one of the sorts is equal to the
restriction of the many-sorted variety, generated by this algebra,
to the same sort.
We apply what we have shown in this section in the next two sections, where
we exemplarily point out how useful the restrictions are, in order to translate
one-sorted results to many-sorted results.
In Section 4 we give two results on functional
completeness for many-sorted algebras. The first one uses the many-sorted
version of discriminators, the second one is the translation of H. Werner's
characterization of functionally complete algebras in congruence permutable
varieties. As an interesting application we show that the trivial clone on a
two-element set is functionally complete.
In Section 5 we determine the structure of
many-sorted Abelian algebras in congruence modular varieties. Here,
many-sorted modules are strongly involved.
Chapter III, the largest chapter in this thesis, is about the
more powerful construction, namely the one-sorted companion. This gives a
one-sorted algebra which has the direct product of the sorts as
universe, so that we also respect operations between different sorts, leading
to a more complicated theory as in the case of restrictions.
But the companion construction only works
properly for finitely-sorted algebras (i.e. many-sorted algebras
with a finite set of sorts).
In Section 6 we give the basic definitions concerning
companions, and, in analogy to Section 3,
we study the behavior of companions
with respect to the formation of direct products, subalgebras, and homomorphic
images. Here again, the companion of a finitely-sorted variety is (nearly)
a variety. We close this section with some remarks about the
companion of a many-sorted variety with infinitely many sorts.
Section 7 gives
an axiomatization for one-sorted algebras to be companions of
finitely-sorted algebras.
In Section 8 we translate terms, equations and, finally,
first-order logic from finitely-sorted algebras to their companions, and
vice versa.
Section 9 is a short note on the structure of the subvariety
lattice of a companion variety. This lattice is shown to be a homomorphic
image of the subvariety lattice of the original variety.
Section 10 gives some applications of the theory developed so
far. Examplarily, we show many-sorted results on
minimal varieties, Abelian varieties, discriminator
varieties, decidability and categorical equivalence.
Finally, in Section 11, we discuss an extension of the
definition of companion algebras. This extension yields many-sorted
algebras which are not one-sorted but have less sorts than the original
many-sorted algebra.
In view of the companion construction and the results in Chapter III, one might be in favour to claim that finitely-sorted algebras are not particular interestion since many properties can be translated to the companion, forth and back. In my opinion, this is not true since companion algebras are very special one-sorted algebras and, in many cases, we can understand the structure of many-sorted algebras much better than the structure of the companion.
Although we give a short introduction to the basics of many-sorted algebras, we assume the reader to be familiar with the theory of one-sorted universal algebra.