First-order t-norm based fuzzy logics with truth-constants: Distinguished semantics and completeness properties

This paper aims at being a systematic investigation of different completeness properties of first-order predicate logics with truth-constants based on a large class of left-continuous t-norms (mainly continuous and weak nilpotent minimum t-norms). We consider standard semantics over the real unit interval but also we explore alternative semantics based on the rational unit interval and on finite chains. We prove that expansions with truth-constants are conservative and we study their real, rational and finite chain completeness properties. Particularly interesting is the case of considering canonical real and rational semantics provided by the algebras where the truth-constants are interpreted as the numbers they actually name. Finally, we study completeness properties restricted to evaluated formulae of the kind , where φ has no additional truth-constants.     

Canonical extensions for congruential logics with the deduction theorem

We introduce a new and general notion of canonical extension for algebras in the algebraic counterpart of any finitary and congruential logic S. This definition is logic-based rather than purely order-theoretic and is in general different from the definition of canonical extensions for monotone poset expansions, but the two definitions agree whenever the algebras in are based on lattices. As a case study on logics purely based on implication, we prove that the varieties of Hilbert and Tarski algebras are canonical in this new sense.     

Erratum to “State-morphism MV-algebras” [Ann. Pure Appl. Logic 161 (2009) 161-173]

Recently, the first two authors characterized in Di Nola and Dvure?enskij (2009) [1] subdirectly irreducible state-morphism MV-algebras. Unfortunately, the main theorem (Theorem 5.4(ii)) has a gap in the proof of Claim 10, as the example below shows. We now present a correct characterization and its correct proof.     

Algebraic proof theory for substructural logics: Cut-elimination and completions

We carry out a unified investigation of two prominent topics in proof theory and order algebra: cut-elimination and completion, in the setting of substructural logics and residuated lattices.We introduce the substructural hierarchy — a new classification of logical axioms (algebraic equations) over full Lambek calculus FL, and show that a stronger form of cut-elimination for extensions of FL and the MacNeille completion for subvarieties of pointed residuated lattices coincide up to the level N₂ in the hierarchy. Negative results, which indicate limitations of cut-elimination and the MacNeille completion, as well as of the expressive power of structural sequent calculus rules, are also provided.Our arguments interweave proof theory and algebra, leading to an integrated discipline which we call algebraic proof theory.     

Topo-canonical completions of closure algebras and Heyting algebras

We introduce and investigate topo-canonical completions of closure algebras and Heyting algebras. We develop a duality theory that is an alternative to Esakia’s duality, describe duals of topo-canonical completions in terms of the Salbany and Banaschewski compactifications, and characterize topo-canonical varieties of closure algebras and Heyting algebras. Consequently, we show that ideal completions preserve no identities of Heyting algebras. We also characterize definable classes of topological spaces. Received January 20, 2006; accepted in final form September 12, 2006.     

MV-algebras: a variety for magnitudes with archimedean units

Chang’s MV-algebras, on the one hand, are the algebras of the infinite-valued Łukasiewicz calculus and, on the other hand, are categorically equivalent to abelian lattice-ordered groups with a distinguished strong unit, for short, unital ℓ-groups. The latter are a modern mathematization of the time-honored euclidean magnitudes with an archimedean unit. While for magnitudes the unit is no less important than the zero element, its archimedean property is not even definable in first-order logic. This gives added interest to the equivalent representation of unital ℓ-groups via the equational class of MV-algebras. In this paper we survey several applications of this equivalence, and various properties of the variety of MV-algebras.Dedicated to the Memory of Wim BlokReceived August 26, 2003; accepted in final form October 3, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Algorithmic correspondence and canonicity for distributive modal logic

We define the algorithm ALBA for the language of the same distributive modal logic (DML) for which a Sahlqvist theorem was proved by Gehrke, Nagahashi, and Venema. Successful executions of ALBA compute the local first-order correspondents of input DML inequalities, and also guarantee their canonicity. The class of inequalities on which ALBA is successful is strictly larger than the newly introduced class of inductive inequalities, which in its turn properly extends the Sahlqvist inequalities of Gehrke et al. Evidence is given to the effect that, as their name suggests, inductive inequalities are the distributive counterparts of the inductive formulas of Goranko and Vakarelov in the classical setting.     

Subreducts of MV-algebras with product and product residuation

Recently, MV-algebras with product have been investigated from different points of view. In particular, in [EGM01], a variety resulting from the combination of MV-algebras and product algebras (see [H98]) has been introduced. The elements of this variety are called ŁΠ-algebras. In this paper we treat subreducts of ŁΠ-algebras, with emphasis on quasivarieties of subreducts whose basic operations are continuous in the order topology. We give axiomatizations of the most interesting classes of subreducts, and we connect them with other algebraic classes of algebras, like f-rings and Wajsberg hoops, as well as to structures of co-infinitesimals of ŁΠ-algebras. In some cases, connections are given by means of equivalences of categories.Dedicated to the Memory of Wim BlokReceived June 19, 2002; accepted in final form November 29, 2004.This revised version was published online in August 2005 with a corrected cover date.     

The normal subgroup lattice of 2-transitive automorphism groups of linearly ordered sets

Using combinatorial and model-theoretic means, we examine the structure of normal subgroup lattices N(A()) of 2-transitive automorphism groups A() of infinite linearly ordered sets (, ). Certain natural sublattices of N(A()) are shown to be Stone algebras, and several first order properties of their dense and dually dense elements are characterized within the Dedekind-completion of (, ). As a consequence, A() has either precisely 5 or at least 2²¹ (even maximal) normal subgroups, and various other group- and lattice-theoretic results follow.     

Categorical Abstract Algebraic Logic: Partially Ordered Algebraic Systems

An extension of parts of the theory of partially ordered varieties and quasivarieties, as presented by Pałasińska and Pigozzi in the framework of abstract algebraic logic, is developed in the more abstract framework of categorical abstract algebraic logic. Algebraic systems, as introduced in previous work by the author, play in this more abstract framework the role that universal algebras play in the more traditional treatment. The aim here is to build the generalized framework and to formulate and prove abstract versions of the ordered homomorphism theorems in this framework. To Don Pigozzi and Kate Pałasińska.     

A characterization of free generating sets in MV-algebras

MV-algebras are a generalization of Boolean algebras. As is well known, a free generating set for a Boolean algebra is characterized by the following simple algebraic condition: whenever A and B are finite disjoint subsets of X then . Our aim in this note is to give a similar characterization of free generating sets in MV-algebras. Received January 30, 2005; accepted in final form March 13, 2007.     

Projective limits of MV-spaces

An MV-space is a topological space X such that there exists an MV-algebra A whose prime spectrum Spec A is homeomorphic to X. The characterization of the MV-spaces is an important open problem.We shall prove that any projective limit of MV-spaces in the category of spectral spaces is an MV-space. In this way, we obtain new classes of MV-spaces related to some preservation properties of the Belluce functor.     

Locally finite varieties of Heyting algebras

We show that for a variety of Heyting algebras the following conditions are equivalent: (1) is locally finite; (2) the -coproduct of any two finite -algebras is finite; (3) either coincides with the variety of Boolean algebras or finite -copowers of the three element chain are finite. We also show that a variety of Heyting algebras is generated by its finite members if, and only if, is generated by a locally finite -algebra. Finally, to the two existing criteria for varieties of Heyting algebras to be finitely generated we add the following one: is finitely generated if, and only if, is residually finite. Received November 11, 2001; accepted in final form July 25, 2005.     

Aglianò-Montagna type decomposition of linear pseudo hoops and its applications

We decompose every linear pseudo hoop as an Aglianò-Montagna type of ordinal sum of linear Wajsberg pseudo hoops which are either negative cones of linear ?-groups or intervals in linear unital ?-groups with strong unit. We apply the decomposition to present a new proof that every linear pseudo BL-algebra and consequently every representable pseudo BL-algebra is good. Moreover, we show that every maximal filter and every value of a linear pseudo hoop is normal, and every σ-complete linear pseudo hoop is commutative.     

Symmetry in information flow

The article investigates information flow properties of symmetric multi-party protocols. It gives a sound and complete axiomatic system for properties of the functional dependence predicate that are common to all protocols with the same group of symmetries.     

The cardinal characteristic for relative γ-sets

For X a separable metric space define p(X) to be the smallest cardinality of a subset Z of X which is not a relative γ-set in X, i.e., there exists an ω-cover of X with no γ-subcover of Z. We give a characterization of p(ω²) and p(ωω) in terms of definable free filters on ω which is related to the pseudo-intersection number p. We show that for every uncountable standard analytic space X that either p(X)=p(ω²) or p(X)=p(ωω). We show that the following statements are each relatively consistent with ZFC: (a) p=p(ωω)<p(ω²) and (b) p<p(ωω)=p(ω²)     

The complexity of cover graph recognition for some varieties of finite lattices

We address the following decision problem: Instance: an undirected graphG. Problem: IsG a cover graph of a lattice? We prove that this problem is NP-complete. This extends results of Brightwell [5] and Ne?et?il and Rödl [12]. On the other hand, it follows from Alvarez theorem [2] that recognizing cover graphs of modular or distributive lattices is in P. An important tool in the proof of the first result is the following statement which may be of independent interest: Given an integerl, l?3, there exists an algorithm which for a graphG withn vertices yields, in time polynomial inn, a graphH with the number of vertices polynomial inn, and satisfying girth(H)?l and χ(H)=χ(G).     

On extensions of countable filterbases to ultrafilters and ultrafilter compactness

We show in the Zermelo-Fraenkel set theory ZF without the axiom of choice:

1. Given an infinite set X, the Stone space S(X) is ultrafilter compact.

2. For every infinite set X, every countable filterbase of X extends to an ultra-filter i? for every infinite set X, S(X) is countably compact.

3. ω has a free ultrafilter i? every countable, ultrafilter compact space is countably compact.

   We also show the following:

4. There are a permutation model 𝒩 and a set X ∈ 𝒩 such that X has no free ultrafilters and S(X) is not compact but S(X) is countably compact and every countable filterbase of X extends to an ultrafilter.

5. It is relatively consistent with ZF that every countable filterbase of ω extends to an ultrafilter but there exists a countable filterbase of ? which does not extend to an ultrafilter. Hence, it is relatively consistent with ZF that ? has free ultrafilters but there exists a countable filterbase of ? which does not extend to an ultrafilter.