Bigeneration in complete lattices and principal separation in ordered sets

By a recent observation of Monjardet and Wille, a finite distributive lattice is generated by its doubly irreducible elements iff the poset of all join-irreducible elements has a distributive MacNeille completion. This fact is generalized in several directions, by dropping the finiteness condition and considering various types of bigeneration via arbitrary meets and certain distinguished joins. This leads to a deeper investigation of so-called L-generators resp. C-subbases, translating well-known notions of topology to order theory. A strong relationship is established between bigeneration by (minimal) L-generators and so-called principal separation, which is defined in order-theoretical terms but may be regarded as a strong topological separation axiom. For suitable L, the complete lattices with a smallest join-dense L-subbasis consisting of L-primes are the L-completions of principally separated posets.     

The order dimension of multinomial lattices

Using the notion of Ferrers dimension of incidence structures, the order dimension of multi-nomial lattices (i.e. lattices of multi-permutations) is determined. In particular, it is shown that the lattice of all permutations on ann-element set has dimensionn–1.     

A horn sentence for involution lattices of quasiorders

The quasiorders of a setA form a lattice Quord(A) with an involution ^–1={x, y: y, x}. Some results in [1] and Chajda and Pinus [2] lead to the problem whether every lattice with involution can be embedded in Quord(A) for some setA. Using the author's approach to the word problem of lattices (cf. [3]), which also applies for involution lattices, it is shown that the answer is negative.Research supported by the Hungarian National Foundation for Scientific Research (OTKA), under grant no. T 7442.     

The generalized Füredi conjecture holds for finite linear lattices

We say that a rank-unimodal poset P has rapidly decreasing rank numbers, or the RDR property, if above (resp. below) the largest ranks of P, the size of each level is at most half of the previous (resp. next) one. We show that a finite rank-unimodal, rank-symmetric, normalized matching, RDR poset of width w has a partition into w chains such that the sizes of the chains are one of two consecutive integers. In particular, there exists a partition of the linear lattices L_n(q) (subspaces of an n-dimensional vector space over a finite field, ordered by inclusion) into chains such that the number of chains is the width of L_n(q) and the sizes of the chains are one of two consecutive integers.     

Priestley duality for order-preserving maps into distributive lattices

The category of bounded distributive lattices with order-preserving maps is shown to be dually equivalent to the category of Priestley spaces with Priestley multirelations. The Priestley dual space of the ideal lattice L of a bounded distributive lattice L is described in terms of the dual space of L. A variant of the Nachbin-Stone-ech compactification is developed for bitopological and ordered spaces. Let X be a poset and Y an ordered space; X ^Y denotes the poset of continuous order-preserving maps from Y to X with the discrete topology. The Priestley dual of L ^P is determined, where P is a poset and L a bounded distributive lattice.     

Join-semidistributive lattices and convex geometries

We introduce the notion of a convex geometry extending the notion of a finite closure system with the anti-exchange property known in combinatorics. This notion becomes essential for the different embedding results in the class of join-semidistributive lattices. In particular, we prove that every finite join-semidistributive lattice can be embedded into a lattice S_P(A) of algebraic subsets of a suitable algebraic lattice A. This latter construction, S_P(A), is a key example of a convex geometry that plays an analogous role in hierarchy of join-semidistributive lattices as a lattice of equivalence relations does in the class of modular lattices. We give numerous examples of convex geometries that emerge in different branches of mathematics from geometry to graph theory. We also discuss the introduced notion of a strong convex geometry that might promise the development of rich structural theory of convex geometries.     

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.     

Cancellative residuated lattices

Cancellative residuated lattices are natural generalizations of lattice-ordered groups ( -groups). Although cancellative monoids are defined by quasi-equations, the class of cancellative residuated lattices is a variety. We prove that there are only two commutative subvarieties of that cover the trivial variety, namely the varieties generated by the integers and the negative integers (with zero). We also construct examples showing that in contrast to -groups, the lattice reducts of cancellative residuated lattices need not be distributive. In fact we prove that every lattice can be embedded in the lattice reduct of a cancellative residuated lattice. Moreover, we show that there exists an order-preserving injection of the lattice of all lattice varieties into the subvariety lattice of .We define generalized MV-algebras and generalized BL-algebras and prove that the cancellative integral members of these varieties are precisely the negative cones of -groups, hence the latter form a variety, denoted by . Furthermore we prove that the map that sends a subvariety of -groups to the corresponding class of negative cones is a lattice isomorphism from the lattice of subvarieties of to the lattice of subvarieties of . Finally, we show how to translate equational bases between corresponding subvarieties, and briefly discuss these results in the context of R. McKenzies characterization of categorically equivalent varieties.     

Counting formulas for glued lattices

A tolerance relation of a lattice L, i.e., a reflexive and symmetric relation of L which is compatible with join and meet, is called glued if covering blocks of have nonempty intersection. For a lattice L with a glued tolerance relation we prove a formula counting the number of elements of L with exactly k lower (upper) covers. Moreover, we prove similar formulas for incidence structures and graphs and we give a new proof of Dilworth's covering theorem.     

Tensorial decomposition of concept lattices

A tensor product for complete lattices is studied via concept lattices. A characterization as a universal solution and an ideal representation of the tensor products are given. In a large class of concept lattices which contains all finite ones, the subdirect decompositions of a tensor product can be determined by the subdirect decompositions of its factors. As a consequence, one obtains that the tensor product of completely subdirectly irreducible concept lattices of this class is again completely subdirectly irreducible. Finally, applications to conceptual measurement are discussed.Dedicated to Ernst-August Behrens on the occasion of his seventieth birthday.     

On context patterns associated with concept lattices

In this paper, we consider the following reconstruction problem: Given two ordered sets (G, ) and (M, ) representing join- and meet-irreducible elements, respectively together with three relationsJ,, onG×M modelling comparability (gm) and maximal noncomparability with respect tog (gm, butgm*) and with respect tom (gm, butgm*). We determine necessary and sufficient conditions for the existence of a finite latticeL and injections :GJ(L) and :MM(L) such that the given order relations and the abstract relations coincide with the one induced by the latticeL.     

Algebraic lattices and Boolean algebras

In this paper we establish several equivalent conditions for an algebraic lattice to be a finite Boolean algebra. This paper is dedicated to Walter Taylor. Received February 11, 2005; accepted in final form October 9, 2005.     

Fast algorithms for Toeplitz and Hankel matrices

The paper gives a self-contained survey of fast algorithms for solving linear systems of equations with Toeplitz or Hankel coefficient matrices. It is written in the style of a textbook. Algorithms of Levinson-type and Schur-type are discussed. Their connections with triangular factorizations, Padè recursions and Lanczos methods are demonstrated. In the case in which the matrices possess additional symmetry properties, split algorithms are designed and their relations to butterfly factorizations are developed.     

On the category Q-Mod

In this paper we consider the category Q-Mod of modules over a given quantale Q. The paper is motivated by constructions and results from the category of modules over a ring. We show that the category Q-Mod is monadic, consider its relation to the category Q-Top of Q-topological spaces and generalize a method of completion of partially ordered sets. Received December 20, 2005; accepted in final form December 4, 2006.     

Nonstandard analysis of ordered sets

We introduce a nonstandard approach to the study of ordered setsX based on a classification of the elements of the ordered set *X into three types, upward, downward, and lateral, which may be thought of dynamically as arising from the possibilities of upward, downward, and lateral motion withinX. Initial applications include the characterization thatX has no infinite diverse subset iff *X has no lateral elements, a result subsequently exploited in work on the interval topology and order-compatibility, where we give a nonstandard proof of Naito's result that ifX has no infinite diverse subset, it has a unique order-compatible topology. We also describe how the completion of a nonempty linearly ordered setX may be obtained as a quotient of *X.     

A solution to a spectral poset problem of Lewis and Ohm

We show that there is a 1-dimensional (countable) non-spectral poset X such that for all x≠y∈X, ↑x∩↑y and ↓x∩↓y are finite subsets. On the other hand, we obtain some sufficient conditions for posets to be spectral.     

On the nonexistence of free complete distributive lattices

We prove that there is no free object over a countable set in the category of complete distributive lattices with homomorphisms preserving binary meets and arbitrary joins.     

Cover-preserving order embeddings into Boolean lattices

It is not known which finite graphs occur as induced subgraphs of a hypercube. This is relevant in the theory of parallel computing. The ordered version of the problem is: Which finite posets P occur as cover-preserving subposets of a Boolean lattice? Our main Theorem gives (for 0,1-posets) a necessary and sufficient condition, which involves the chromatic number of a graph associated to P. It is applied respectively to upper balanced, meet extremal, meet semidistributive, and semidistributive lattices P. More specifically, we consider isometric embeddings of posets into Boolean lattices. In particular, answering a question of Ivan Rival to the positive, a nontrivial invariant for the covering graph of a poset is found.     

Orthmodular lattices whose MacNeille completions are not orthomodular

The only known example of an orthomodular lattice (abbreviated: OML) whose MacNeille completion is not an OML has been noted independently by several authors, see Adams [1], and is based on a theorem of Ameniya and Araki [2]. This theorem states that for an inner product space V, if we consider the ortholattice ?(V,⊥) = {A \( \subseteq \) V: A = A ^⊥⊥} where A ^⊥ is the set of elements orthogonal to A, then ?(V,⊥) is an OML if and only if V is complete. Taking the orthomodular lattice L of finite or confinite dimensional subspaces of an incomplete inner product space V, the ortholattice ?(V,⊥) is a MacNeille completion of L which is not orthomodular. This does not answer the longstanding question Can every OML be embedded into a complete OML? as L can be embedded into the complete OML ?(V,⊥), where V is the completion of the inner product space V. Although the power of the Ameniya-Araki theorem makes the preceding example elegant to present, the ability to picture the situation is lost. In this paper, I present a simpler method to construct OMLs whose Macneille completions are not orthomodular. No use is made of the Ameniya-Araki theorem. Instead, this method is based on a construction introduced by Kalmbach [7] in which the Boolean algebras generated by the chains of a lattice are glued together to form an OML. A simple method to complete these OMLs is also given. The final section of this paper briefly covers some elementary properties of the Kalmbach construction. I have included this section because I feel that this construction may be quite useful for many purposes and virtually no literature has been written on it.