Search

H2020 Marie Sklodowska-Curie Actions; DST-NRF Centre of Excellence in Mathematical and Statistical Sciences (CoE-MaSS), South Africa and National Research Foundation of South Africa.

For (finitary) deductive systems, we formulate a signature-independent abstraction of the \emph{weak excluded middle law} (WEML), which strengthens the existing general notion of an inconsistency lemma (IL). Of special interest is the case where a quasivariety $\mathsf{K}$ algebraizes a deductive system $\,\vdash$. We prove that, in this case, if $\,\vdash$ has a WEML (in the general sense) then every relatively subdirectly irreducible member of $\mathsf{K}$ has a greatest proper $\mathsf{K}$-congruence; the converse holds if $\,\vdash$ has an inconsistency lemma. The result extends, in a suitable form, to all protoalgebraic logics. A super-intuitionistic logic possesses a WEML iff it extends $\mathbf{KC}$. We characterize the IL and the WEML for normal modal logics and for relevance logics. A normal extension of $\mathbf{S4}$ has a global consequence relation with a WEML iff it extends $\mathbf{S4.2}$, while every axiomatic extension of $\mathbf{R^t}$ with an IL has a WEML.

It is proved that epimorphisms are surjective in a range of varieties of residuated structures, including all varieties of Heyting or Brouwerian algebras of finite depth, and all varieties consisting of Goedel algebras, relative Stone algebras, Sugihara monoids or positive Sugihara monoids. This establishes the infinite deductive Beth definability property for a corresponding range of substructural logics. On the other hand, it is shown that epimorphisms need not be surjective in a locally finite variety of Heyting or Brouwerian algebras of width 2. It follows that the infinite Beth property is strictly stronger than the so-called finite Beth property, confirming a conjecture of Blok and Hoogland.

A commutative residuated lattice $${\varvec{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 $${\varvec{A}}^-$$ ). It is proved here that epimorphisms are surjective in a variety $${\mathsf {K}}$$ of such algebras $${\varvec{A}}$$ (with or without involution), provided that each finitely subdirectly irreducible algebra $${\varvec{B}}\in {\mathsf {K}}$$ has two properties: (1) $${\varvec{B}}$$ is generated by lower bounds of e, and (2) the poset of prime filters of $${\varvec{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.

The second author was supported in part by the National Research Foundation of South Africa (UID 85407).

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 $$\wedge ,\vee ,\circ $$ 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.

It is proved that the relevance logic $${\mathbf{R}}$$R (without sentential constants) has no structurally complete consistent axiomatic extension, except for classical propositional logic. In fact, no other such extension is even passively structurally complete.

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 noninjective homomorphisms. The homomorphic preimages 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 (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 (C4) [or of (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.

This paper concerns residuated lattice-ordered idempotent commutative monoids that are subdirect products of chains. An algebra of this kind is a generalized Sugihara monoid (GSM) if it is generated by the lower bounds of the monoid identity; it is a Sugihara monoid if it has a compatible involution ¬ \neg . Our main theorem establishes a category equivalence between GSMs and relative Stone algebras with a nucleus (i.e., a closure operator preserving the lattice operations). An analogous result is obtained for Sugihara monoids. Among other applications, it is shown that Sugihara monoids are strongly amalgamable, and that the relevance logic R M t \mathbf {RM}^\mathbf {t} has the projective Beth definability property for deduction.

In this paper, the inconsistency lemmas of intuitionistic and classical propositional logic are formulated abstractly. We prove that, when a (finitary) deductive system is algebraized by a variety , then has an inconsistency lemma—in the abstract sense—iff every algebra in has a dually pseudo-complemented join semilattice of compact congruences. In this case, the following are shown to be equivalent: (1) has a classical inconsistency lemma; (2) has a greatest compact theory and is filtral, i.e., semisimple with EDPC; (3) the compact congruences of any algebra in form a Boolean lattice; (4) the compact congruences of any constitute a Boolean sublattice of the full congruence lattice of . These results extend to quasivarieties and relative congruences. Except for (2), they extend even to protoalgebraic logics, with deductive filters in the role of congruences. A protoalgebraic system with a classical inconsistency lemma always has a deduction-detachment theorem (DDT), while a system with a DDT and a greatest compact theory has an inconsistency lemma. The converses are false.

This paper provides a semantic analysis of admissible rules and associated completeness conditions for arbitrary deductive systems, using the framework of abstract algebraic logic. Algebraizability is not assumed, so the meaning and significance of the principal notions vary with the level of the Leibniz hierarchy at which they are presented. As a case study of the resulting theory, the nonalgebraizable fragments of relevance logic are considered.

An odd Sugihara monoid is a residuated distributive lattice-ordered commutative idempotent monoid with an order-reversing involution that fixes the monoid identity. The main theorem of this paper establishes a category equivalence between odd Sugihara monoids and relative Stone algebras. In combination with known results, it swiftly determines which varieties of odd Sugihara monoids are [strongly] amalgamable and which have the strong [or weak] epimorphism-surjectivity property. In particular, the full variety is shown to have all of these properties. The results extend, with slight modification, to the case where the algebras are bounded. Logical applications include immediate answers to some questions about projective and finite Beth definability and interpolation in the uninorm-based logic IUML, its boundless fragment and all of their extensions.

Equations are the most basic formulas of algebra, and the logical rules for manipulating them are so intuitive that they are seldom formalized. Consequently, non-algebraic deductive systems (or ‘logics’) are very often interpreted in equational languages—although this is not always possible. For the optimal transfer of algebraic techniques, we require invertible interpretations that respect the structure of substitution; they should also induce isomorphism between the extension lattice of a system and that of its algebraic counterpart. The successful resolution of concrete logical problems in the presence of such an isomorphism has inspired (1) a robust general notion of equivalence between deductive systems, (2) a precise account of ‘algebraizable’ logics (pioneered by Blok and Pigozzi) and (3) a stock of ‘bridge theorems’ between logic and algebra. Moreover, an algebraic invariant in the theory of equivalence— called the Leibniz operator—has given rise to (4) a classification of deductive systems, analogous to the Maltsev classification of varieties in universal algebra. The present paper is a selective exposition of these developments.Keywords: Algebra of logic, relation algebra, residuation, substructural logic, modal logic, deductive system, algebraizable logic, Leibniz operator, reduced matrix, Leibniz hierarchy.Quaestiones Mathematicae 34(2011), 275–325.

Logics that do not have a deduction-detachment theorem (briefly, a DDT) may still possess a contextual DDT--a syntactic notion introduced here for arbitrary deductive systems, along with a local variant. Substructural logics without sentential constants are natural witnesses to these phenomena. In the presence of a contextual DDT, we can still upgrade many weak completeness results to strong ones, e.g., the finite model property implies the strong finite model property. It turns out that a finitary system has a contextual DDT iff it is protoalgebraic and gives rise to a dually Brouwerian semilattice of compact deductive filters in every finitely generated algebra of the corresponding type. Any such system is filter distributive, although it may lack the filter extension property. More generally, filter distributivity and modularity are characterized for all finitary systems with a local contextual DDT, and several examples are discussed. For algebraizable logics, the well-known correspondence between the DDT and the equational definability of principal congruences is adapted to the contextual case.

An idempotent residuated po-monoid is semiconic if it is a subdirect product of algebras in which the monoid identity is comparable with all other elements. It is proved that the quasivariety SCIP of all semiconic idempotent commutative residuated po-monoids is locally finite. The lattice-ordered members of this class form avariety SCIL, which is not locally finite, but it is proved that SCIL has the finite embeddability property (FEP). More generally, for every relative subvariety K of SCIP, the lattice-ordered members of K have the FEP. This gives a unified explanation of the strong finite model property for a range of logical systems. It is also proved that SCIL has continuously many semisimple subvarieties, and that the involutive algebras in SCIL are subdirect products of chains.

A translation in an algebraic signature is a finite conjunction of equations in one variable. On a quasivariety K, a translation τ naturally induces a deductive system, called the τ-assertional logic of K. Two quasivarieties are τ-assertionally equivalent if they have the same τ-assertional logic. This paper is a study of assertional equivalence. It characterizes the quasivarieties equivalent to ones with various desirable properties, such as τ-regularity (a general form of point regularity). Special attention is paid to structural properties of quasivarieties that are assertionally equivalent to their varietal closures under an indicated translation.

This paper establishes several algebraic embedding theorems, each of which asserts that a certain kind of residuated structure can be embedded into a richer one. In almost all cases, the original structure has a compatible involution, which must be preserved by the embedding. The results, in conjunction with previous findings, yield separative axiomatizations of the deducibility relations of various substructural formal systems having double negation and contraposition axioms. The separation theorems go somewhat further than earlier ones in the literature, which either treated fewer subsignatures or focussed on the conservation of theorems only. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

It is proved that in the variety of positive Sugihara monoids, every finite subdirectly irreducible algebra is a retract of a free algebra. It follows that every quasivariety of positive Sugihara monoids is a variety, in contrast with the situation in several neighboring varieties. This result shows that when the logic R-mingle is formulated with the Ackermann constant t, then its full negation-free fragment is hereditarily structurally complete.

It is proved that the variety of relevant disjunction lattices has the finite embeddability property. It follows that Avron's relevance logic RMImin has a strong form of the finite model property, so it has a solvable deducibility problem. This strengthens Avron's result that RMImin is decidable. (© 2006 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

Most Gentzen systems arising in logic contain few axiom schemata and many rule schemata. Hilbert systems, on the other hand, usually contain few proper inference rules and possibly many axioms. Because of this, the two notions tend to serve different purposes. It is common for a logic to be specified in the first instance by means of a Gentzen calculus, whereupon a Hilbert-style presentation ‘for’ the logic may be sought—or vice versa. Where this has occurred, the word ‘for’ has taken on several different meanings, partly because the Gentzen separator ⇒ can be interpreted intuitively in a number of ways. Here ⇒ will be denoted less evocatively by ⊲.In this paper we aim to discuss some of the useful ways in which Gentzen and Hilbert systems may correspond to each other. Actually, we shall be concerned with thededucibility relationsof the formal systems, as it is these that are susceptible to transformation in useful ways. To avoid potential confusion, we shall speak of Hilbert and Gentzenrelations. By aHilbert relationwe mean any substitution-invariant consequence relation onformulas—this comes to the same thing as the deducibility relation of a set of Hilbert-style axioms and rules. By aGentzen relationwe mean the fully fledged generalization of this notion in whichsequentstake the place of single formulas. In the literature, Hilbert relations are often referred to assentential logics. Gentzen relations as defined here are their exactsequentialcounterparts.

The logic RM and its basic fragments (always with implication) are considered here as entire consequence relations, rather than as sets of theorems. A new observation made here is that the disjunction of RM is definable in terms of its other positive propositional connectives, unlike that of R. The basic fragments of RM therefore fall naturally into two classes, according to whether disjunction is or is not definable. In the equivalent quasivariety semantics of these fragments, which consist of subreducts of Sugihara algebras, this corresponds to a distinction between strong and weak congruence properties. The distinction is explored here. A result of Avron is used to provide a local deduction-detachment theorem for the fragments without disjunction. Together with results of Sobocinski, Parks and Meyer (which concern theorems only), this leads to axiomatizations of these entire fragments — not merely their theorems. These axiomatizations then form the basis of a proof that all of the basic fragments of RM with implication are finitely axiomatized consequence relations.

Two constructions for adding an involution operator to residuated ordered monoids are investigated. One preserves integrality and the mingle axiom x 2≤x but fails to preserve the contraction property x≤x 2. The other has the opposite preservation properties. Both constructions preserve commutativity as well as existent nonempty meets and joins and self-dual order properties. Used in conjunction with either construction, a result of R.T. Brady can be seen to show that the equational theory of commutative distributive residuated lattices (without involution) is decidable, settling a question implicitly posed by P. Jipsen and C. Tsinakis. The corresponding logical result is the (theorem-) decidability of the negation-free axioms and rules of the logic RW, formulated with fusion and the Ackermann constant t. This completes a result of S. Giambrone whose proof relied on the absence of t.

A full separation theorem for the derivable rules of intuitionistic linear logic without bounds, 0 and exponentials is proved. Several structural consequences of this theorem for subreducts of (commutative) residuated lattices are obtained. The theorem is then extended to the logic LR+ and its proof is extended to obtain the finite embeddability property for the class of square increasing residuated lattices.

A method of constructing residuated lattices is presented. As an application, examples of simple, integral, cancellative, distributive residuated lattices are given that are not linearly ordered. This settles a problem raised in [5] and [2].

Relatively congruence regular quasivarieties and quasivarieties of logic have noticeable similarities. The paper provides a unifying framework for them which extends the Blok-Pigozzi theory of elementarily algebraizable (and protoalgebraic) deductive systems. In this extension there are two parameters: a set of terms and a variable. When the former is empty or consists of theorems, the Blok-Pigozzi theory is recovered, and the variable is redundant. On the other hand, a class of ‘membership logics’ is obtained when the variable is the only element of the set of terms. For these systems the appropriate variant of equivalent algebraic semantics encompasses the relatively congruence regular quasivarieties.

An open problem in algebraic logic asks whether a variety that is the equivalent algebraic semantics of an algebraizable logic must be congruence modular. A negative solution is provided here: it is shown that such ‘varieties of logic’ need satisfy no special congruence lattice identity.

The aim of this paper is to show that the implicational fragment BKof the intuitionistic propositional calculus (IPC) without the rules of exchange and contraction has the finite model property with respect to the quasivariety of left residuation algebras (its equivalent algebraic semantics). It follows that the variety generated by all left residuation algebras is generated by the finite left residuation algebras. We also establish that BKhas the finite model property with respect to a class of structures that constitute a Kripke-style relational semantics for it. The results settle a question of Ono and Komori [OK85].

Prime ringsMaybe classified by the sizes of the sets that ‘insulate’ their elements from annihilation. For a cardinal m > 0, the class [Pbar]r,(m) of all rings that are right prime of ‘bound at most m’ is studied, with particular reference to its closure under constructions such as matrix rings, semigoup rings, orders and extensions. The classes [Pbar]r,(m) are special in the sense of radical theory for each m > 0. The attendant upper radicals υ[Pbar]r,(m) are right (and not left) strong; their compatibility with certain ring constructions is examined. In the lattice of radicals (where they form a strictly descending chain), their positions are described, relative to various familiar radicals.

The equivalence of the following conditions on a chain L is proved: (1) L is algebraic; (2)There is a tight chain domain T (with identity) such that L is isomorphic to the chain of proper two-sided ideals of T and all two-sided ideals of T are idempotent; (3) L is isomorphic to the congruence lattice of a ring (not necessarily with identity).

Let m be a positive cardinal. We denote by Pr(m) (resp. P t(m)) the class of all rings R for which m is the least cardinal such that all nonzero elements of R possess right (resp. left) insulators of cardinality less than m + 1. We also set P r(m) = Un ≤ m Pr(n). The classes Pr(m),> m 0, partition the class of all prime rings. Various descriptions of these classes are obtained. In particular if m is regular then P r(m) contains just those rings R such that t(R) = 0 for all proper torsion preradicals t on Mod -R whose torsion classes are closed under direct products of fewer than m modules. Examples are provided which show that P r(m) is non-empty for all m > 0 and which partially answer the question: for which cardinals m, n is P r(m) ∩ P t(n) nonempty?

It is proved that a quasivariety \( {\sf K} \) of algebras is a variety if the relative congruences of each algebra A in \( \sf K \) form a sublattice of the congruence lattice of A.

A ring R is called strongly prime (DR, CTF, CC) if a(E(R)) = 0 or o(E(R)) = E(R) for all torsion preradicals (idempotent radicals, torsion radicals, cotorsion radicals) σ on Mod-R. (DR and CC rings were introduced recently by Katayama). Examples are provided which distinguish these four conditions one from another and which show each condition to be one-sided. A conjecture of Handelman and Lawrence, to the effect that a ring is CTF if its singular ideal is strongly prime, is disproved, and it is shown that a nonsingular CTF ring is strongly prime iff all of its nonsingular quasi-injective modules are injective. It is also proved that hereditary CTF rings are strongly prime.

Given a non-zero cardinal α, a ring R is said to be SP(α) if a is the first cardinal for which every non-zero element of R has an insulator of cardinality less than α + 1. It is shown that the class of SP(α) rings is a special class (in the sense of Andrunakievic) for each α. A theorem of Groenewald and Heyman (also Desale and Varadarajan) to the effect that the class of all strongly prime rings is a special class is obtained as a corollary. Every SP(α) ring has an SP(α) rational extension ring with identity.