Algebraic model theory for languages without equality

Abstract

In our opinion, it is fair to distinguish two separate branches in the origins of model theory. The first one, the model theory of first-order logic, can be traced back to the pioneering work of L. Lowenheim, T. Skolem, K. Gödel, A. Tarski and A.I. MaI 'cev, published before the mid 30's. This branch was put forward during the 40s' and 50s’ by several authors, including A. Tarski, L. Henkin, A. Robinson, J. Los. Their contribution, however, was rather influenced by modern algebra, a discipline whose development was being truly fast at the time. Largely due to this influence, it was a very common usage among these authors lo the equality symbol belonging lo the language. Even when a few years later the algebraic methods started to be supplanted to a large extent by the set-theoretical technique that mark present-day theory, the consideration of the equality a constant in the language still subsisted.

The second branch is the model theory of equational logic. It was born with the seminal work of G. Birkhoff which established the first basic tools and results of what later developed the part of universal algebra known as the theory of varieties and quasivarieties. The algebraic character of this other branch of model theory was clearer and stronger, for it simply emerged as the last stop in the continuous process of abstraction in algebra.

Amid these two branches of model theory, which suffered a rapid growth at the time, there appeared the work done by Mal'cev in the early 1950's and the late 60's, which some influence in the future development of the discipline, in the old Soviet Union. During the period mentioned above, he developed a first-order model theory that retained much of the spirit of the period and diverged openly from the model theory developed in the West. In particular, he put forward the model theory of universal Horn logic with equality along the of Birkhoff's theory of varieties, and showed that such logic forms a right setting for a large part of universal algebra, including the theory of presentations and free structures. The most worth-mentioning peculiarities of Mal'cev's program were the following: first, he kept on dealing with first-order languages with equality; second, he adopted notions of homomorphism and congruence that had little to do with the relational part of the language.

This well-roted tradition of developing model theory in the presence of an equality symbol to express the identity relation, which goes back to its very origin, finally broken when logicians from the PoIish School started program similar to that of Mal'cev for another type of UHL, viz. general sentential logic. Indeed, in spite of the fact that the algebraic character of sentential logic was evident early in its development (chiefly because classical sentential calculus could be completely reduced to the quasi-equational theory of Boolean algebras), the natural models of arbitrary sentential calculus quickly took the form of logical matrices, that is, algebras endowed with a unary relation on their universe. This matrix semantics so became the first attempt of starting a systematic development of a model theory for first-order languages without equality. Beginning with the publication of a paper by Los in 1949, matrix semantics was successfully developed over the next three decades by a number of different authors in Poland, including J. Los himself, R. Suszko, R. Wojcicki and J. Zygmunt.

The present evolution of these issues points towards an effort of encompassing the theory of varieties and quasi-varieties and the model theory of sentential logic, by means of the development of a program similar to Mal’cev’s for UHL without equality. We recognize that this evolution has been fast and notorious in the last decade, thanks mainly to the work done by J. Czelakowski, W. Blok and D. Pigozzi among others. For example, the first author has been developing a model theory of sentential logic inherits a lot of the algebraic character of Mal’cev’s theory of sentential logic originated by Birkhoff. On the other hand, Blok and Pigozzi, in a paper published in 1992, have succeeded in the development of a model theory –based on the Leibniz operator introduced by them– that does comprises for the first time both equational logic and sentential logic, and so strengthens Czelakowsk’s program. What enables such a simultaneous treatment in their approach in the observation that equational logic can be viewed as an example of a 2-dimensional sentential calculus and thus admits a matrix semantics, this time a matrix being an algebra together with a congruence on the algebra.

A characteristic of decisive importance in Blok and Pigozzi's approach in their apparent conviction that only reduced models really possess the algebraic character of the models of quasi-equational theories. We give up such a conviction and the restriction to particular types of languages.

The main purpose of this paper is to outline some basic aspects of the model theory for first-order languages that definitively do not include the equality symbol and which account of both the full and the reduced semantics. The theory is intended to follow as much as possible of the Mal'cev's tradition by pronounced algebraic character and mainly covering topics fairly well studied in universal algebra (that is the reason for giving the term “algebraic” to our model theory). Most of the work, that extends to general languages and fairly clarifies some recent trends in algebraic logic, constitutes the foundations of a model theory of UHL without equality. An important number of the results in the paper run side by side with some well-known results of either classical model theory or universal algebra; so, we make an effort to highlight the concepts and techniques only applied in these contexts although, in some sense, they find a more general setting in ours. The outgrowth of the current interest in the model theory of UHL without equality is the emergence of several applications mainly in algebraic logic and computer science. Therefore we also discuss the way that the developed theory relates to algebraic logic. Actually, we maintain that our approach provides an appropriate context to investigate the availability of nice algebraic semantics, not only for the traditional deductive systems that arise in sentential logic, but also for some other types of deductive systems that are attracting increasing attention at the time. The reason is that all of them admit as interpretation as universal Horn theories without equality.

As we said before, the absence of symbol is the language to mean the identity relation is central to this work. Traditionally, the equality in classical model theory has had a representation is the moral language and has been understood in an absolute sense, i.e., for any interpretation of the language, the interest of model-theorists has been put on the relation according to which two members of the universe are the same or has no other logical relation. We break this tradition by introducing a weak form of equality predicate and not presupposing its formal representation by a symbol of the language. Then the main problem consists, broadly speaking, in the investigation of the relationship between the features of this weaker equality in a given class of structures and the fulfillment of certain properties by this class.

This is not at all recent treatment of the equality; for instance, it underlies the old notion of Lindenbaum-Tarski algebra in the model theory of sentential logic, and more recently contributions to the study of algebraic for semantics logics. Our contribution amounts to no more than providing a broader framework for the investigation of this question in the domain of first-order logic, the universal Horn fragment.

Several points stand out for they govern all our approach. First, the extended use we make of two unlike notions of homomorphism, whose difference relies on the importance each one attaches to relations; this is a distinction that no longer exists in universal algebra but does exist in classical model theory. Secondly, the availability of two distinct adequate semantics easily connected through an algebraic operation, which consists in factorizing the structures in such a way that the Leibniz equality and the usual identity relation coincide. We believe this double semantics is what is mainly responsible for the interest of the model theory for languages without equality as a research topic; in spite of their equivalence from a semantical point of view, they furnish several stimulating problems regarding their comparability from an algebraic perspective. Thirdly, the two extensions that the notion of congruence on an algebra admits when dealing with general structures over languages without equality, namely, as a special sort of binary relation associated to a structure, here called congruence, and as the relational part of a structure, which is embodied in the concept of filter extension. Finally, and not because of this less important, the nice algebraic description that our equality predicate has as the greatest one of the congruence on a structure. This fact allows to replace the fundamental (logical) concept of Leibniz equality by an entirely algebraic notion, and to put the main emphasis on the algebraic methods. Actually, it seems to us that other forms of equality without such a property hardly give rise to model theories that work out so beautifully.

The work is organized in 10 chapters. The first three contain basic material that is essential to overcome the small inadequacies of some approaches to the topic formerly provided by other authors. Chapter 1 reviews some terminology and notation that will appear repeteadly thereafter, and presents some elementary notions and results of classical model theory that remains equal for languages without equality. Chapter 2 states and characterizes algebraically the fundamental concept of equality in the sense of Leibniz which we deal with all over the paper. Finally, in Chapter 3 we discuss the semantical consequences of factorizing a structure by a congruence and show that first-order logic without equality has two complete semantics related by a reduction operator (Theorem 3.2.1). Right here we pose out if the central problem to which most of the subsequent work is devoted, i.e., the investigation of the algebraic properties that the full reduced model classes of an elementary theory exhibit.

Chapter 4 contains the first difficult results in the work. By a rather obvious generalization of proofs known from classical model theory, we obtain Birkhoff-type characterizations of full classes of axiomatized by certain sorts of first-order without equality, and apply these results to derive analogue characterizations for the corresponding reduced classes.

Chapter 5 is a central one; it examines the primary consequences of dealing with the relational part of a structure as the natural extension of congruences when passing from algebraic to general fist-order languages without equality. A key observation in this case is that the sets of structures of an algebraic complete lattice. It is proved that this classes is just the quasinvarieties of structure. The Leibniz operator is defined right here as a primary criterion to distinguish properties of the Leibniz equality in a class of models. Using the operator, a fundamental hierarchy of classes.

Chapter 7 examines how the characterizations of reduced quasinvarieties (relative varieties) obtained in Chapter 4 can be improved when we deal with the special types of classes introduced formerly. Chapters 6, 8 and 9 provide an explicit generalization of well-known results from universal algebra. Concretely, in Chapter 6 we present the main tools of Subdirect Representation Theory for general first-order structures without equality. Chapter 8 deals with the existence of free structures both in full and reduced classes. This Chapter also includes the investigation of a correspondence between (quasi)varieties and some lattice structures associated with the Herbrand structures, correspondence that offers the possibility of turning the logical methods used in the theory of varieties and quasivarieties into purely algebraic ones (Theorems 8.3.3 and 8.3.6). In Chapter 9 we set the problem of finding Mal'cev-type conditions for properties concerning posets of relative congruences or relative filler extensions of members of quasivarieties.

Finally, Chapter 10 discusses briefly the relation between algebraic logic and the approach to model theory outlined in the previous chapters, providing that some vindication to it. Of course, we cannot say whether this work will ultimately have a bearing on the resolution of any of the problem of algebraic logic, but for us, it could at least provide fresh insights in this exciting branch of logic.