Barbour, Graham.
Abstract:
We present and consider a number of logics that arise naturally from universal algebraic considerations, but which are ‘inherently unalgebraizable’ in the sense of [BP89a], essentially because they have no theo- rems. Of particular interest is the membership logic of a quasivariety, which is determined by its theorems, which are the relative congruence classes of the term algebra together with the empty-set in the case that the quasivariety is non-trivial. The membership logic arises by a more general technique developed in this text, for inducing deductive systems from closed systems on the free algebras of quasivarieties. In order to formalize this technique, we develop a theory of logics over constructs, where constructs are concrete categories. With this theory in place, we are able to view a closed system over an algebra as a logic, and in particular a structural logic, structural with respect to a suitable construct, typically the construct con- sisting of all algebras in a quasivariety and all algebra homomorphisms between these algebras. Of course, in such a case, none of these logics are generally sentential (i.e., structural and finitary deductive systems in the sense of [BP89a]), since the formulae of sentential logics arise from the terms of the absolutely free term algebra, which is generally not a member of the quasivariety under interest. In such cases, where the term algebra is not a member of a quasivariety, the free algebra of the quasivariety on denumerably countable free generators takes on the role played by the term algebra in sentential logics. Many of the logics that we encounter in this text arise most naturally as finitary logics on this free algebra of the quasivariety and generally are structural with respect to the quasivariety. We call such logics canons, and show how such structural canons induce sentential calculi, which we call the induced ideal ; the filters of the ideal on the free algebra are precisely the theories of the canon. The membership logic is the ideal of the cannon whose theories are the relative congruence classes on the free algebra. The primary aim of this thesis is to provide a unifying framework for logics of this type which extends the Blok-Pigozzi theory of elementarily algebraizable (and protoalgebraic) deductive systems. In this extension there are two parameters: a set of formulae and a variable. When the former is empty or consists of theorems, the Blok-Pigozzi theory is recovered, and the variable is redundant. For the membership logic, the appropriate variant of equivalent algebraic semantics encompasses the relatively congruence regular quasivarieties. These results have appeared in [BR03]. The secondary aim of this thesis is to analyse our theory of parameterized algebraization from a non- parameterized perspective. To this end, we develop a theory of protoalgebraic logics over constructs and equivalence between logics from different constructs, which we then use to explain the results we obtained in our parameterized theories of protoalgebraicity, algebraic semantics and equivalent algebraic semantics. We relate this theory to the theory of deductively equivalent -institutions [Vou03], and as a consequence obtain a number of improved and new results in the field of categorical abstract algebraic logic. We also use our theory of protoalgebraic logics over constructs to obtain a new and simpler characterization of structural finitary n-deductive systems, which we then use to close the program begun in [BR99], by extending those results for 1-deductive systems to n-deductive systems, and in particular characterizing the protoalgebraicity of the sentential n-deductive system Sn(K,N), which is the natural extension of the 1-deductive system S(K, ) introduce in [BR99], in terms of the quasivariety K having hK,Ni-coherent N-classes (we cannot see how to obtain this result from the standard characterization of protoalgebraic n- deductive systems of [Pal03], which is very complex). With respect to this program of completing [BR99], we also show that a quasivariety K is an equivalent algebraic semantics for a n-deductive system with defining equations N iff K is hK,Ni-regular; a notion of regularity that we introduce and characterize by a quasi-Mal’cev condition. The third aim of this text is to unify as many disparate arguments and notions in algebraic logic under the banner of continuous translations between closed systems, where our use of the term continuous is in the topological sense rather than in the order-theoretic sense, and, where possible, to give elementary, i.e. first order, definitions and proofs. To this end, we show that closed systems, closure operators and conse- quence relations can all be characterized elementarily over orders, and put into one-to-one correspondence that reflects exactly, the standard correspondences between the well-known concrete notions with the same name. We show that when the order is the complete power order over a set, then these elementary structures coincide with their well-known counterparts with the same name. We also introduce two other elementary structures over orders, namely the closed equivalence relation and something we term the proto-Leibniz relation; these elementary structures are also in one-to-one correspondence with the earlier mentioned structures; we have not seen concrete versions of these structures. We then characterize the structure homomorphisms between these structures, as well as considering galois relations between them; galois relations are pairs of order-preserving function in opposite directions; we call these translations, and they are elementary notions. We demonstrate how notions as disparate as structurality, semantics, algebraic semantics, the filter correspondence property, filters, models, semantic consequence, protoalge- braicity and even the logic S(K, ) of [BR99] and our logic Sn(K,N), all fall within this framework, as does much of our parameterized theory and much of the theory of -institutions. A brief summary of the standard theory of deductive systems and their algebraization is provided for the reader unfamiliar with algebraic logics, as well as the necessary background material, including construct and category theory, the theory of structures and algebras, and the model theory of structures with and without equality.