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.     

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.     

Weakly linear quantum MV-algebras

Quantum MV-algebras (QMV-algebras) are a non lattice-theoretic generalization of MV-algebras (multi-valued algebras) and a non-idempotent generalization of orthomodular lattices. In this paper we construct a finite basis for the variety generated by the class of all weakly linear quantum MV-algebras.Dedicated to the memory of Wim BlokReceived October 12, 2000; accepted in final form October 3, 2004.This revised version was published online in August 2005 with a corrected cover date.     

State-morphism MV-algebras

We present a stronger variation of state MV-algebras, recently presented by T. Flaminio and F. Montagna, which we call state-morphism MV-algebras. Such structures are MV-algebras with an internal notion, a state-morphism operator. We describe the categorical equivalences of such (state-morphism) state MV-algebras with the category of unital Abelian ?-groups with a fixed state operator and present their basic properties. In addition, in contrast to state MV-algebras, we are able to describe all subdirectly irreducible state-morphism MV-algebras.     

Sublattices of complete lattices with continuity conditions

Various embedding problems of lattices into complete lattices are solved. We prove that for any join-semilattice S with the minimal join-cover refinement property, the ideal lattice Id S of S is both algebraic and dually algebraic. Furthermore, if there are no infinite D-sequences in J(S), then Id S can be embedded into a direct product of finite lower bounded lattices. We also find a system of infinitary identities that characterize sublattices of complete, lower continuous, and join-semidistributive lattices. These conditions are satisfied by any (not necessarily finitely generated) lower bounded lattice and by any locally finite, join-semidistributive lattice. Furthermore, they imply M. Erné’s dual staircase distributivity.On the other hand, we prove that the subspace lattice of any infinite-dimensional vector space cannot be embedded into any ℵ₀-complete, ℵ₀-upper continuous, and ℵ₀-lower continuous lattice. A similar result holds for the lattice of all order-convex subsets of any infinite chain.Dedicated to the memory of Ivan RivalReceived April 4, 2003; accepted in final form June 16, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Representation theory of MV-algebras

In this paper we develop a general representation theory for MV-algebras. We furnish the appropriate categorical background to study this problem. Our guide line is the theory of classifying topoi of coherent extensions of universal algebra theories. Our main result corresponds, in the case of MV-algebras and MV-chains, to the representation of commutative rings with unit as rings of global sections of sheaves of local rings. We prove that any MV-algebra is isomorphic to the MV-algebra of all global sections of a sheaf of MV-chains on a compact topological space. This result is intimately related to McNaughton’s theorem, and we explain why our representation theorem can be viewed as a vast generalization of McNaughton’s theorem. In spite of the language used in this abstract, we have written this paper in the hope that it can be read by experts in MV-algebras but not in sheaf theory, and conversely.     

Canonical extensions of double quasioperator algebras: An algebraic perspective on duality for certain algebras with binary operations

The context for this paper is a class of distributive lattice expansions, called double quasioperator algebras (DQAs). The distinctive feature of these algebras is that their operations preserve or reverse both join and meet in each coordinate. Algebras of this type provide algebraic semantics for certain non-classical propositional logics. In particular, MV-algebras, which model the ?ukasiewicz infinite-valued logic, are DQAs.Varieties of DQAs are here studied through their canonical extensions. A variety of this type having additional operations of arity at least 2 may fail to be canonical; it is already known, for example, that the variety of MV-algebras is not. Non-canonicity occurs when basic operations have two distinct canonical extensions and both are necessary to capture the structure of the original algebra. This obstruction to canonicity is different in nature from that customarily found in other settings. A generalized notion of canonicity is introduced which is shown to circumvent the problem. In addition, generalized canonicity allows one to capture on the canonical extensions of DQAs the algebraic operations in such a way that the laws that these obey may be translated into first-order conditions on suitable frames. This correspondence may be seen as the algebraic component of duality, in a way which is made precise.In many cases of interest, binary residuated operations are present. An operation h which, coordinatewise, preserves ∨ and 0 lifts to an operation which is residuated, even when h is not. If h also preserves binary meet then the upper adjoints behave in a functional way on the frames.     

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.     

Bernoulli automorphisms of finitely generated free MV-algebras

MV-algebras can be viewed either as the Lindenbaum algebras of ?ukasiewicz infinite-valued logic, or as unit intervals [0,u] of lattice-ordered abelian groups in which a strong order unit u>0 has been fixed. They form an equational class, and the free n-generated free MV-algebra is representable as an algebra of piecewise-linear continuous functions with integer coefficients over the unit n-dimensional cube. In this paper we show that the automorphism group of such a free algebra contains elements having strongly chaotic behaviour, in the sense that their duals are measure-theoretically isomorphic to a Bernoulli shift. This fact is noteworthy from the viewpoint of algebraic logic, since it gives a distinguished status to Lebesgue measure as an averaging measure on the space of valuations. As an ergodic theory fact, it provides explicit examples of volume-preserving homeomorphisms of the unit cube which are piecewise-linear with integer coefficients, preserve the denominators of rational points, and enjoy the Bernoulli property.     

Infinite independent sets in distributive lattices

We show that a poset P contains a subset isomorphic to if and only if the poset J(P) consisting of ideals of P contains a subset isomorphic to the power set of κ. If P is a join-semilattice this amounts to the fact that P contains an independent set of size κ. We show that if κ := ω and P is a distributive lattice, then this amounts to the fact that P contains either or as sublattices, where Γ and Δ are two special meet-semilattices already considered by J. D. Lawson, M. Mislove and H. A. Priestley.Dedicated to the memory of Ivan RivalReceived April 22, 2003; accepted in final form July 11, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Non-Trivial t-Intersection in the Function Lattice

The function lattice, or generalized Boolean algebra, is the set of ℓ-tuples with the ith coordinate an integer between 0 and a bound n_i. Two ℓ-tuples t-intersect if they have at least t common nonzero coordinates. We prove a Hilton–Milner type theorem for systems of t-intersecting ℓ-tuples.Received September 29, 2004     

Free products of unital ℓ-groups and free products of generalized MV-algebras

We generalize Komori’s characterization of the proper subvarieties of MV-algebras. Namely, within the variety of generalized MV-algebras (GMV-algebras) such that every maximal ideal is normal, we characterize the proper top varieties. In addition, we present equational bases for these top varieties. We show that there are only countably many different proper top varieties and each of them has uncountably many subvarieties. Finally, we study coproducts and we show that the amalgamation property fails for the class of n-perfect GMV-algebras, i.e., GMV-algebras that can be split into n + 1 comparable slices. This paper has been supported by the Center of Excellence SAS -Physics of Information-I/2/2005, the grant VEGA No. 2/6088/26 SAV, by Science and Technology Assistance Agency under the contracts No. APVT-51-032002, APVV-0071-06, Bratislava.     

Which posets have a scattered MacNeille completion?

A poset is order-scattered if it does not embed the chain η of the rational numbers. We prove that there are eleven posets such that N(P), the MacNeille completion of P, is order-scattered if and only if P embeds none of these posets. Moreover these posets are pairwise non-embeddable in each other. This result completes a previous characterisation due to Duffus, Pouzet, Rival [4]. The proof is based on the “bracket relation”: a famous result of F. Galvin.Dedicated to the memory of Ivan Rival.Received June 16, 2004; accepted in final form October 3, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Local algebras in the representation of MV-algebras

In this paper we present several results about local MV-algebras, extending existing results given for MV-chains. The role of local MV-algebras in sheaf representation and weak boolean product is stressed and the relationship of local MV-algebras with varieties of MV-algebras is analyzed. Presented by S. Pulmannova. Received November 11, 2005; accepted in final form December 20, 2005.     

Entropy numbers in sequence spaces with an application to weighted function spaces

We determine the exact asymptotic behaviour of entropy numbers of diagonal operators from ℓ_p to ℓ_q, 0<q<p∞, under mild regularity conditions on the generating diagonal sequence. On one hand, this is a quantitative version of Pitt's theorem for diagonal operators, and on the other hand it is a limiting case of results by Carl. An application to embeddings of weighted Besov and Triebel–Lizorkin spaces is also given.     

State morphism MV-algebras

We present a complete characterization of subdirectly irreducible MV-algebras with internal states (SMV-algebras). This allows us to classify subdirectly irreducible state morphism MV-algebras (SMMV-algebras) and describe single generators of the variety of SMMV-algebras, and show that we have a continuum of varieties of SMMV-algebras.     

Freely adjoining a relative complement to a lattice

Let K be a lattice, and let a < b < c be elements of K. We adjoin freely a relative complement u of b in [a, c] to K to form the lattice L. For two polynomials A and B over K ∪ {u}, we find a very simple set of conditions under which A and B represent the same element in L, so that in L all pairs of relative complements in [a, c] can be described. Our major result easily follows: Let [a, c] be an interval of a lattice K; let us assume that every element in [a, c] has at most one relative complement. Then K has an extension L such that [a, c] in L, as a lattice, is uniquely complemented.As an immediate consequence, we get the classical result of R. P. Dilworth: Every lattice can be embedded into a uniquely complemented lattice. We also get the stronger form due to C. C. Chen and G. Grätzer: Every at most uniquely complemented bounded lattice has a {0, 1}-embedding into a uniquely complemented lattice. Some stronger forms of these results are also presented.A polynomial A over K ∪ {u} naturally represents an element 〈A 〉 of L. Let us call a polynomial A minimal, if it is of minimal length representing x. We characterize minimal polynomials.Dedicated to the memory of Ivan RivalReceived February 12, 2003; accepted in final form June 18, 2004.This revised version was published online in August 2005 with a corrected cover date.     

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.     

All-norm approximation algorithms

A major drawback in optimization problems and in particular in scheduling problems is that for every measure there may be a different optimal solution. In many cases the various measures are different ℓ_p norms. We address this problem by introducing the concept of an all-norm ρ-approximation algorithm, which supplies one solution that guarantees ρ-approximation to all ℓ_p norms simultaneously. Specifically, we consider the problem of scheduling in the restricted assignment model, where there are m machines and n jobs, each job is associated with a subset of the machines and should be assigned to one of them. Previous work considered approximation algorithms for each norm separately. Lenstra et al. [Math. Program. 46 (1990) 259–271] showed a 2-approximation algorithm for the problem with respect to the ℓ_∞ norm. For any fixed ℓ_p norm the previously known approximation algorithm has a performance of θ(p). We provide an all-norm 2-approximation polynomial algorithm for the restricted assignment problem. On the other hand, we show that for any given ℓ_p norm (p>1) there is no PTAS unless P=NP by showing an APX-hardness result. We also show for any given ℓ_p norm a FPTAS for any fixed number of machines.