Abstract For any $n<\omega $ we construct an infinite $(n+1)$ -generated Heyting algebra whose n -generated subalgebras are of cardinality $\leq m_n$ for some positive integer $m_n$ . From this we conclude that for every $n<\omega $ there exists a variety of Heyting algebras which contains an infinite $(n+1)$ -generated algebra, but which contains only finite n -generated algebras. For the case $n=2$ this provides a negative answer to a question posed by G. Bezhanishvili and R. Grigolia in [4].

Abstract We introduce prime products as a generalization of ultraproducts for positive logic. Prime products are shown to satisfy a version of Łoś’s Theorem restricted to positive formulas, as well as the following variant of the Keisler Isomorphism Theorem: under the generalized continuum hypothesis, two models have the same positive theory if and only if they have isomorphic prime powers of ultrapowers.

We develop a duality for (modal) lattices that need not be distributive, and use it to study positive (modal) logic beyond distributivity, which we call weak positive (modal) logic. This duality builds on the Hofmann, Mislove and Stralka duality for meet-semilattices. We introduce the notion of Π1-persistence and show that every weak positive modal logic is Π1-persistent. This approach leads to a new relational semantics for weak positive modal logic, for which we prove an analogue of Sahlqvist correspondence result.1

A bi-Heyting algebra validates the Gödel-Dummett axiom (p→q)∨(q→p) iff the poset of its prime filters is a disjoint union of co-trees (i.e., order duals of trees). Bi-Heyting algebras of this kind are called bi-Gödel algebras and form a variety that algebraizes the extension bi-GD of bi-intuitionistic logic axiomatized by the Gödel-Dummett axiom. In this paper we initiate the study of the lattice Λ(bi-GD) of extensions of bi-GD. We develop the methods of Jankov-style formulas for bi-Gödel algebras and use them to prove that there are exactly continuum many extensions of bi-GD. We also show that all these extensions can be uniformly axiomatized by canonical formulas. Our main result is a characterization of the locally tabular extensions of bi-GD. We introduce a sequence of co-trees, called the finite combs, and show that a logic in Λ(bi-GD) is locally tabular iff it contains at least one of the Jankov formulas associated with the finite combs. It follows that there exists the greatest nonlocally tabular extension of bi-GD and consequently, a unique pre-locally tabular extension of bi-GD. These results contrast with the case of the intermediate logic axiomatized by the Gödel-Dummett axiom, which is known to have only countably many extensions, all of which are locally tabular.

Abstract A Leibniz class is a class of logics closed under the formation of term-equivalent logics, compatible expansions, and non-indexed products of sets of logics. We study the complete lattice of all Leibniz classes, called the Leibniz hierarchy. In particular, it is proved that the classes of truth-equational and assertional logics are meet-prime in the Leibniz hierarchy, while the classes of protoalgebraic and equivalential logics are meet-reducible. However, the last two classes are shown to be determined by Leibniz conditions consisting of meet-prime logics only.

Abstract A logic is said to admit an equational completeness theorem when it can be interpreted into the equational consequence relative to some class of algebras. We characterize logics admitting an equational completeness theorem that are either locally tabular or have some tautology. In particular, it is shown that a protoalgebraic logic admits an equational completeness theorem precisely when it has two distinct logically equivalent formulas. While the problem of determining whether a logic admits an equational completeness theorem is shown to be decidable both for logics presented by a finite set of finite matrices and for locally tabular logics presented by a finite Hilbert calculus, it becomes undecidable for arbitrary logics presented by finite Hilbert calculi.

Abstract A notion of interpretation between arbitrary logics is introduced, and the poset $\mathsf {Log}$ of all logics ordered under interpretability is studied. It is shown that in $\mathsf {Log}$ infima of arbitrarily large sets exist, but binary suprema in general do not. On the other hand, the existence of suprema of sets of equivalential logics is established. The relations between $\mathsf {Log}$ and the lattice of interpretability types of varieties are investigated.

Abstract We present a logical and algebraic description of right adjoint functors between generalized quasi-varieties, inspired by the work of McKenzie on category equivalence. This result is achieved by developing a correspondence between the concept of adjunction and a new notion of translation between relative equational consequences.

A constraint satisfaction problem (CSP) is a computational problem where the input consists of a finite set of variables and a finite set of constraints, and where the task is to decide whether there exists a satisfying assignment of values to the variables. Depending on the type of constraints that we allow in the input, a CSP might be tractable, or computationally hard. In recent years, general criteria have been discovered that imply that a CSP is polynomial-time tractable, or that it is NP-hard. Finite-domain CSPs have become a major common research focus of graph theory, artificial intelligence, and finite model theory. It turned out that the key questions for complexity classification of CSPs are closely linked to central questions in universal algebra. This thesis studies CSPs where the variables can take values from an infinite domain. This generalization enhances dramatically the range of computational problems that can be modeled as a CSP. Many problems from areas that have so far seen no interaction with constraint satisfaction theory can be formulated using infinite domains, e.g. problems from temporal and spatial reasoning, phylogenetic reconstruction, and operations research. It turns out that the universal-algebraic approach can also be applied to study large classes of infinite-domain CSPs, yielding elegant complexity classification results. A new tool in this thesis that becomes relevant particularly for infinite domains is Ramsey theory. We demonstrate the feasibility of our approach with two complete complexity classification results: one on CSPs in temporal reasoning, the other on a generalization of Schaefer's theorem for propositional logic to logic over graphs. We also study the limits of complexity classification, and present classes of computational problems provably do not exhibit a complexity dichotomy into hard and easy problems.