Search

In this paper we consider, from a computational point of view, the problem of classifying logics within the Leibniz and Frege hierarchies typical of abstract algebraic logic. The main result states that, for logics presented syntactically, this problem is in general undecidable. More precisely, we show that there is no algorithm that classifies the logic of a finite consistent Hilbert calculus in the Leibniz and in the Frege hierarchies.

We prove that the problem of determining whether a finite logical matrix determines an algebraizable logic is complete for EXPTIME. The same result holds for the classes of order algebraizable, weakly algebraizable, equivalential and protoalgebraic logics. Finally, the same problem for the class of truth-equational logic is shown to be hard for EXPTIME.

A commutative residuated lattice A is said to be subidempotent if the lower bounds of its neutral element e are idempotent (in which case they naturally constitute a Brouwerian algebra A*). It is proved here that epimorphisms are surjective in a variety K of such algebras A (with or without involution), provided that each finitely subdirectly irreducible algebra B in K has two properties: (1) B is generated by lower bounds of e, and (2) the poset of prime filters of B* has finite depth. Neither (1) nor (2) may be dropped. The proof adapts to the presence of bounds. The result generalizes some recent findings of G. Bezhanishvili and the first two authors concerning epimorphisms in varieties of Brouwerian algebras, Heyting algebras and Sugihara monoids, but its scope also encompasses a range of interesting varieties of De Morgan monoids.

It is proved that every prevariety of algebras is categorically equivalent to a "prevariety of logic", i.e., to the equivalent algebraic semantics of some sentential deductive system. This allows us to show that no nontrivial equation in the language "meet, join, and relational product" holds in the congruence lattices of all members of every variety of logic, and that being a (pre)variety of logic is not a categorical property.

A quasivariety K of algebras has the joint embedding property (JEP) iff it is generated by a single algebra A. It is structurally complete iff the free countably generated algebra in K can serve as A. A consequence of this demand, called "passive structural completeness" (PSC), is that the nontrivial members of K all satisfy the same existential positive sentences. We prove that if K is PSC then it still has the JEP, and if it has the JEP and its nontrivial members lack trivial subalgebras, then its relatively simple members all belong to the universal class generated by one of them. Under these conditions, if K is relatively semisimple then it is generated by one K-simple algebra. It is a minimal quasivariety if, moreover, it is PSC but fails to unify some finite set of equations. We also prove that a quasivariety of finite type, with a finite nontrivial member, is PSC iff its nontrivial members have a common retract. The theory is then applied to the variety of De Morgan monoids, where we isolate the sub(quasi)varieties that are PSC and those that have the JEP, while throwing fresh light on those that are structurally complete. The results illuminate the extension lattices of intuitionistic and relevance logics.

The simplicial volume is a homotopy invariant of manifolds introduced by Gromov in 1982. In order to study its main properties, Gromov himself initiated the dual theory of bounded cohomology, that developed into an active and independent research field. Gromov's theory of bounded cohomology was based on the use of multicomplexes, which are simplicial structures that generalize simplicial complexes without allowing all the degeneracies appearing in simplicial sets. In the first part of this paper we lay the foundation of the theory of multicomplexes. We construct the singular multicomplex K(X) associated to a topological space X, and we prove that K(X) is homotopy equivalent to $X$ for every CW complex X. Following Gromov, we introduce the notion of completeness, which translates into the context of multicomplexes the Kan condition for simplicial sets. We then develop the homotopy theory of complete multicomplexes. In the second part we apply the theory of multicomplexes to the study of the bounded cohomology of topological spaces. We provide complete proofs of Gromov's Mapping Theorem (which implies that the bounded cohomology of a space only depends on its fundamental group) and of Gromov's Vanishing Theorem, which ensures the vanishing of the simplicial volume of closed manifolds admitting an amenable cover of small multiplicity. The third part is devoted to the study of locally finite chains on non-compact spaces. We expand some ideas of Gromov to provide complete proofs of a criterion for the vanishing and a criterion for the finiteness of the simplicial volume of open manifolds. As a by-product of these results, we prove a criterion for the l^1-invisibility of closed manifolds in terms of amenable covers. As an application, we give the first complete proof of the vanishing of the simplicial volume of the product of three open manifolds., Comment: Revised version after the referee's comments. Some changes in the discussion of the relationship between our paper and the existing literature, and minor improvements regarding the hypotheses of some theorems. To appear in Mem. Amer. Math. Soc

The paper aims at studying, in full generality, logics defined by imposing a variable inclusion condition on a given logic $\vdash$. It turns out that the algebraic counterpart of the variable inclusion companion of a given logic $\vdash$ is obtained by constructing the Plonka sum of the matrix models of $\vdash$. This association allows to obtain a Hilbert-style axiomatization of the logics of variable inclusion and to describe the structure of their reduced models., Comment: to appear in Archive for Mathematical Logic

We define the ideal simplicial volume for compact manifolds with boundary. Roughly speaking, the ideal simplicial volume of a manifold $M$ measures the minimal size of possibly ideal triangulations of $M$ "with real coefficients", thus providing a variation of the ordinary simplicial volume defined by Gromov in 1982, the main difference being that ideal simplices are now allowed to appear in representatives of the fundamental class. We show that the ideal simplicial volume is bounded above by the ordinary simplicial volume, and that it vanishes if and only if the ordinary simplicial volume does. We show that, for manifolds with amenable boundary, the ideal simplicial volume coincides with the classical one, whereas for hyperbolic manifolds with geodesic boundary it can be strictly smaller. We compute the ideal simplicial volume of an infinite family of hyperbolic $3$-manifolds with geodesic boundary, for which the exact value of the classical simplicial volume is not known, and we exhibit examples where the ideal simplicial volume provides shaper bounds on mapping degrees than the classical simplicial volume., Comment: 40 pages, 2 figures, some minor changes, to appear in International Mathematics Research Notices (IMRN)

It is proved that every finitely subdirectly irreducible De Morgan monoid A (with neutral element e) is either (i) a Sugihara chain in which e covers not(e) or (ii) the union of an interval subalgebra [not(a), a] and two chains of idempotents, (not(a)] and [a), where a = (not(e))^2. In the latter case, the variety generated by [not(a), a] has no nontrivial idempotent member, and A/[not(a)) is a Sugihara chain in which not(e) = e. It is also proved that there are just four minimal varieties of De Morgan monoids. This theorem is then used to simplify the proof of a description (due to K. Swirydowicz) of the lower part of the subvariety lattice of relevant algebras. The results throw light on the models and the axiomatic extensions of fundamental relevance logics.

Generalizing a theorem of Campercholi, we characterize, in syntactic terms, the ranges of epimorphisms in an arbitrary class of similar first-order structures (as opposed to an elementary class). This allows us to strengthen a result of Isbell, as follows: in any prevariety having at most s non-logical symbols and an axiomatization requiring at most m variables, if the epimorphisms into structures with at most m + s + aleph0 elements are surjective, then so are all of the epimorphisms. Using these facts, we formulate and prove manageable "bridge theorems", matching the surjectivity of all epimorphisms in the algebraic counterpart of a logic L with suitable infinitary definability properties of L, while not making the standard but awkward assumption that L comes furnished with a proper class of variables.

The variety DMM of De Morgan monoids has just four minimal subvarieties. The join-irreducible covers of these atoms in the subvariety lattice of DMM are investigated. One of the two atoms consisting of idempotent algebras has no such cover; the other has just one. The remaining two atoms lack nontrivial idempotent members. They are generated, respectively, by 4-element De Morgan monoids C4 and D4, where C4 is the only nontrivial 0-generated algebra onto which finitely subdirectly irreducible De Morgan monoids may be mapped by non-injective homomorphisms. The homomorphic pre-images of C4 within DMM (together with the trivial De Morgan monoids) constitute a proper quasivariety, which is shown to have a largest subvariety U. The covers of the variety V(C4) within U are revealed here. There are just ten of them (all finitely generated). In exactly six of these ten varieties, all nontrivial members have C4 as a retract. In the varietal join of those six classes, every subquasivariety is a variety-in fact, every finite subdirectly irreducible algebra is projective. Beyond U, all covers of V(C4) [or of V(D4)] within DMM are discriminator varieties. Of these, we identify infinitely many that are finitely generated, and some that are not. We also prove that there are just 68 minimal quasivarieties of De Morgan monoids.

Hyperideal tetrahedra are the fundamental building blocks of hyperbolic 3-manifolds with geodesic boundary. The study of their geometric properties (in particular, of their volume) has applications also in other areas of low-dimensional topology, like the computation of quantum invariants of 3-manifolds and the use of variational methods in the study of circle packings on surfaces. The Schl\"afli formula neatly describes the behaviour of the volume of hyperideal tetrahedra with respect to dihedral angles, while the dependence of volume on edge lengths is worse understood. In this paper we prove that, for every $\ell<\ell_0$, where $\ell_0$ is an explicit constant, regular hyperideal tetrahedra of edge length $\ell$ maximize the volume among hyperideal tetrahedra whose edge lengths are all not smaller than $\ell$. This result provides a fundamental step in the computation of the ideal simplicial volume of an infinite family of hyperbolic 3-manifolds with geodesic boundary., Comment: 20 pages, 2 figures, Some minor changes, To appear in Periodica Mathematica Hungarica

We generalise the Blok-J\'onsson account of structural consequence relations, later developed by Galatos, Tsinakis and other authors, in such a way as to naturally accommodate multiset consequence. While Blok and J\'onsson admit, in place of sheer formulas, a wider range of syntactic units to be manipulated in deductions (including sequents or equations), these objects are invariably aggregated via set-theoretical union. Our approach is more general in that non-idempotent forms of premiss and conclusion aggregation, including multiset sum and fuzzy set union, are considered. In their abstract form, thus, deductive relations are defined as additional compatible preorderings over certain partially ordered monoids. We investigate these relations using categorical methods, and provide analogues of the main results obtained in the general theory of consequence relations. Then we focus on the driving example of multiset deductive relations, providing variations of the methods of matrix semantics and Hilbert systems in Abstract Algebraic Logic.

We study the behavior of the abstract sectional category in the Quillen, the Strom and the Mixed proper model structures on topological spaces and prove that, under certain reasonable conditions, all of them coincide with the classical notion. As a result, the same conclusions hold for the abstract Lusternik-Schnirelmann category and the abstract topological complexity of a space.