Back-and-forth for systems of antichains

We consider the distributive lattice of all the antichains over a root-system. The main result shows that the first-order theory of the former is determined by that of the latter. It is also shown that this kind of distributive lattices can be thought of as a generalization of that of atomic Boolean algebras.     

Combinatorial representation and convex dimension of convex geometries

We develop a representation theory for convex geometries and meet distributive lattices in the spirit of Birkhoff's theorem characterizing distributive lattices. The results imply that every convex geometry on a set X has a canonical representation as a poset labelled by elements of X. These results are related to recent work of Korte and Lovász on antimatroids. We also compute the convex dimension of a convex geometry.Supported in part by NSF grant no. DMS-8501948.     

Boolean and distributive ordered sets: Characterization and representation by sets

Boolean ordered sets generalize Boolean lattices, and distributive ordered sets generalize distributive lattices. Ideals, prime ideals, and maximal ideals in ordered sets are defined, and some well-known theorems on Boolean lattices, such as the Glivenko-Stone theorem and the Stone representation theorem, are generalized to Boolean ordered sets. A prime ideal theorem for distributive ordered sets is formulated, and the Birkhoff representation theorem is generalized to distributive ordered sets. Fundamental are the embedding theorems for Boolean ordered sets and for distributive ordered sets.Financial support of the Grant Agency of the Czech Republic under the grant No. 201/93/0950 is gratefully acknowledged.     

Remarks on Priestley duality for distributive lattices

The notion of a Priestley relation between Priestley spaces is introduced, and it is shown that there is a duality between the category of bounded distributive lattices and 0-preserving join-homomorphisms and the category of Priestley spaces and Priestley relations. When restricted to the category of bounded distributive lattices and 0-1-preserving homomorphisms, this duality yields essentially Priestley duality, and when restricted to the subcategory of Boolean algebras and 0-preserving join-homomorphisms, it coincides with the Halmos-Wright duality. It is also established a duality between 0-1-sublattices of a bounded distributive lattice and certain preorder relations on its Priestley space, which are called lattice preorders. This duality is a natural generalization of the Boolean case, and is strongly related to one considered by M. E. Adams. Connections between both kinds of dualities are studied, obtaining dualities for closure operators and quantifiers. Some results on the existence of homomorphisms lying between meet and join homomorphisms are given in the Appendix.     

A non-commutative Priestley duality

We prove that the category of left-handed strongly distributive skew lattices with zero and proper homomorphisms is dually equivalent to a category of sheaves over local Priestley spaces. Our result thus provides a non-commutative version of classical Priestley duality for distributive lattices and generalizes the recent development of Stone duality for skew Boolean algebras.     

MacNeille completions of lattice expansions

There are two natural ways to extend an arbitrary map between (the carriers of) two lattices, to a map between their MacNeille completions. In this paper we investigate which properties of lattice maps are preserved under these constructions, and for which kind of maps the two extensions coincide. Our perspective involves a number of topologies on lattice completions, including the Scott topologies and topologies that are induced by the original lattice. We provide a characterization of the MacNeille completion in terms of these induced topologies. We then turn to expansions of lattices with additional operations, and address the question of which equational properties of such lattice expansions are preserved under various types of MacNeille completions that can be defined for these algebras. For a number of cases, including modal algebras and residuated (ortho)lattice expansions, we provide reasonably sharp sufficient conditions on the syntactic shape of equations that guarantee preservation. Generally, our results show that the more residuation properties the primitive operations satisfy, the more equations are preserved. Received August 21, 2005; accepted in final form October 17, 2006.     

Comparability graphs of lattices

A theorem of N. Terai and T. Hibi for finite distributive lattices and a theorem of Hibi for finite modular lattices (suggested by R.P. Stanley) are equivalent to the following: if a finite distributive or modular lattice of rank d contains a complemented rank 3 interval, then the lattice is (d+1)-connected.In this paper, the following generalization is proved: Let L be a (finite or infinite) semimodular lattice of rank d that is not a chain (d∈N₀). Then the comparability graph of L is (d+1)-connected if and only if L has no simplicial elements, where z∈L is simplicial if the elements comparable to z form a chain.     

Lattice-theoretic properties of algebras of logic

In the theory of lattice-ordered groups, there are interesting examples of properties — such as projectability — that are defined in terms of the overall structure of the lattice-ordered group, but are entirely determined by the underlying lattice structure. In this paper, we explore the extent to which projectability is a lattice-theoretic property for more general classes of algebras of logic. For a class of integral residuated lattices that includes Heyting algebras and semi-linear residuated lattices, we prove that a member of such is projectable iff the order dual of each subinterval [a,1]$[a,1]$ is a Stone lattice. We also show that an integral GMV algebra is projectable iff it can be endowed with a positive Gödel implication. In particular, a ΨMV or an MV algebra is projectable iff it can be endowed with a Gödel implication. Moreover, those projectable involutive residuated lattices that admit a Gödel implication are investigated as a variety in the expanded signature. We establish that this variety is generated by its totally ordered members and is a discriminator variety.     

The center of an effect algebra

An effect algebra is a partial algebra modeled on the standard effect algebra of positive self-adjoint operators dominated by the identity on a Hilbert space. Every effect algebra is partially ordered in a natural way, as suggested by the partial order on the standard effect algebra. An effect algebra is said to be distributive if, as a poset, it forms a distributive lattice. We define and study the center of an effect algebra, relate it to cartesian-product factorizations, determine the center of the standard effect algebra, and characterize all finite distributive effect algebras as products of chains and diamonds.     

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).     

Ordered groups with a conucleus

Our work proposes a new paradigm for the study of various classes of cancellative residuated lattices by viewing these structures as lattice-ordered groups with a suitable operator (a conucleus). One consequence of our approach is the categorical equivalence between the variety of cancellative commutative residuated lattices and the category of abelian lattice-ordered groups endowed with a conucleus whose image generates the underlying group of the lattice-ordered group. In addition, we extend our methods to obtain a categorical equivalence between -algebras and product algebras with a conucleus. Among the other results of the paper, we single out the introduction of a categorical framework for making precise the view that some of the most interesting algebras arising in algebraic logic are related to lattice-ordered groups. More specifically, we show that these algebras are subobjects and quotients of lattice-ordered groups in a “quantale like” category of algebras.     

Approximate unitary equivalence of completely distributive commutative subspace lattices

In this note, we classify completely distributive CSLs up to approximate unitary equivalence. Our proof uses a new characterization of complete distributivity and leads to a generalization of a result of Arveson on ordered group lattices. As consequences of our results, we obtain a similarity theorem for hyperreflexive, completely distributive CSLs and some new perturbation results.Partially supported by an NSERC grantResearch partially supported by NSF grant DMS-9204811.     

Insertion of lattice-valued and hedgehog-valued functions

Problems of inserting lattice-valued functions are investigated. We provide an analogue of the classical insertion theorem of Lane [Proc. Amer. Math. Soc. 49 (1975) 90-94] for L-valued functions where L is a ?-separable completely distributive lattice (i.e. L admits a countable join-dense subset which is free of completely join-irreducible elements). As a corollary we get an L-version of the Katětov-Tong insertion theorem due to Liu and Luo [Topology Appl. 45 (1992) 173-188] (our proof is different and much simpler). We show that ?-separable completely distributive lattices are closed under the formation of countable products. In particular, the Hilbert cube is a ?-separable completely distributive lattice and some join-dense subset is shown to be both order and topologically isomorphic to the hedgehog J(ω) with appropriately defined topology. This done, we deduce an insertion theorem for J(ω)-valued functions which is independent of that of Blair and Swardson [Indian J. Math. 29 (1987) 229-250]. Also, we provide an iff criterion for inserting a pair of semicontinuous function which yields, among others, a characterization of hereditarily normal spaces.     

Generalizations of Boolean products for lattice-ordered algebras

It is shown that the Boolean center of complemented elements in a bounded integral residuated lattice characterizes direct decompositions. Generalizing both Boolean products and poset sums of residuated lattices, the concepts of poset product, Priestley product and Esakia product of algebras are defined and used to prove decomposition theorems for various ordered algebras. In particular, we show that FL_w-algebras decompose as a poset product over any finite set of join irreducible strongly central elements, and that bounded n-potent GBL-algebras are represented as Esakia products of simple n-potent MV-algebras.     

Planar acyclic oriented graphs

A plane Hasse representation of an acyclic oriented graph is a drawing of the graph in the Euclidean plane such that all arcs are straight-line segments directed upwards and such that no two arcs cross. We characterize completely those oriented graphs which have a plane Hasse representation such that all faces are bounded by convex polygons. From this we derive the Hasse representation analogue, due to Kelly and Rival of Fary's theorem on straight-line representations of planar graphs and the Kuratowski type theorem of Platt for acyclic oriented graphs with only one source and one sink. Finally, we describe completely those acyclic oriented graphs which have a vertex dominating all other vertices and which have no plane Hasse representation, a problem posed by Trotter.     

The Loomis–Sikorski Theorem revisited

We prove, constructively, that the Loomis–Sikorski Theorem for σ-complete Boolean algebras follows from a representation theorem for Archimedean vector lattices and a constructive representation of Boolean algebras as spaces of Carathéodory place functions. We also prove a constructive subdirect product representation theorem for arbitrary partially ordered vector spaces. Received August 10, 2006; accepted in final form May 30, 2007.     

A Gentzen system for involutive residuated lattices

We establish a cut-free Gentzen system for involutive residuated lattices and provide an algebraic proof of completeness. As a result we conclude that the equational theory of involutive residuated lattices is decidable. The connection to noncommutative linear logic is outlined. Received July 22, 2004; accepted in final form July 19, 2005.     

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.     

Forbidden configurations for distributive and modular ordered sets

As modular and distributive ordered sets generalize modular and distributive lattices, it is a natural question to ask whether there exist some forbidden configurations for those ordered sets. We present such configurations in the form of strong subsets and LU subsets.     

Reducible classes of finite lattices

In this paper we study a notion of reducibility in finite lattices. An element x of a (finite) lattice L satisfying certain properties is deletable if L-x is a lattice satisfying the same properties. A class of lattices is reducible if each lattice of this class admits (at least) one deletable element (equivalently if one can go from any lattice in this class to the trivial lattice by a sequence of lattices of the class obtained by deleting one element in each step). First we characterize the deletable elements in a pseudocomplemented lattice what allows to prove that the class of pseudocomplemented lattices is reducible. Then we characterize the deletable elements in semimodular, modular and distributive lattices what allows to prove that the classes of semimodular and locally distributive lattices are reducible. In conclusion the notion of reducibility for a class of lattices is compared with some other notions like the notion of order variety.