Matchings and radon transforms in lattices. I. Consistent lattices

An element in a lattice is join-irreducible if x=ab implies x=a or x=b. A meet-irreducible is a join-irreducible in the order dual. A lattice is consistent if for every element x and every join-irreducible j, the element xj is a join-irreducible in the upper interval [x, î]. We prove that in a finite consistent lattice, the incidence matrix of meet-irreducibles versus join-irreducibles has rank the number of join-irreducibles. Since modular lattices and their order duals are consistent, this settles a conjecture of Rival on matchings in modular lattices.     

Finite Intervals in the Lattice of Topologies

We discuss the question whether every finite interval in the lattice of all topologies on some set is isomorphic to an interval in the lattice of all topologies on a finite set – or, equivalently, whether the finite intervals in lattices of topologies are, up to isomorphism, exactly the duals of finite intervals in lattices of quasiorders. The answer to this question is in the affirmative at least for finite atomistic lattices. Applying recent results about intervals in lattices of quasiorders, we see that, for example, the five-element modular but non-distributive lattice cannot be an interval in the lattice of topologies. We show that a finite lattice whose greatest element is the join of two atoms is an interval of T ₀-topologies iff it is the four-element Boolean lattice or the five-element non-modular lattice. But only the first of these two selfdual lattices is an interval of orders because order intervals are known to be dually locally distributive.     

Quasiorder lattices of varieties

The set \({{\mathrm{Quo}}}(\mathbf {A})\) of compatible quasiorders (reflexive and transitive relations) of an algebra \(\mathbf {A}\) forms a lattice under inclusion, and the lattice \({{\mathrm{Con}}}(\mathbf {A})\) of congruences of \(\mathbf {A}\) is a sublattice of \({{\mathrm{Quo}}}(\mathbf {A})\). We study how the shape of congruence lattices of algebras in a variety determine the shape of quasiorder lattices in the variety. In particular, we prove that a locally finite variety is congruence distributive [modular] if and only if it is quasiorder distributive [modular]. We show that the same property does not hold for meet semi-distributivity. From tame congruence theory we know that locally finite congruence meet semi-distributive varieties are characterized by having no sublattice of congruence lattices isomorphic to the lattice \(\mathbf {M}_3\). We prove that the same holds for quasiorder lattices of finite algebras in arbitrary congruence meet semi-distributive varieties, but does not hold for quasiorder lattices of infinite algebras even in the variety of semilattices.     

Primes,irreducibles and extremal lattices

This paper studies certain types of join and meet-irreducibles called coprimes and primes. These elements can be used to characterize certain types of lattices. For example, a lattice is distributive if and only if every join-irreducible is coprime. Similarly, a lattice is meet-pseudocomplemented if and only if each atom is coprime. Furthermore, these elements naturally decompose lattices into sublattices so that often properties of the original lattice can be deduced from properties of the sublattice. Not every lattice has primes and coprimes. This paper shows that lattices which are long enough must have primes and coprimes and that these elements and the resulting decompositions can be used to study such lattices.The length of every finite lattice is bounded above by the minimum of the number of meet-irreducibles (meet-rank) and the number of join-irreducibles (join-rank) that it has. This paper studies lattices for which length=join-rank or length=meet-rank. These are called p-extremal lattices and they have interesting decompositions and properties. For example, ranked, p-extremal lattices are either lower locally distributive (join-rank=length), upper locally distributive (meet-rank=length) or distributive (join-rank=meet-rank=length). In the absence of the Jordan-Dedekind chain condition, p-extremal lattices still have many interesting properties. Of special interest are the lattices that satisfy both equalities. Such lattices are called extremal; this class includes distributive lattices and the associativity lattices of Tamari. Even though they have interesting decompositions, extremal lattices cannot be characterized algebraically since any finite lattice can be embedded as a subinterval into an extremal lattice. This paper shows how prime and coprime elements, and the poset of irreducibles can be used to analyze p-extremal and other types of lattices.The results presented in this paper are used to deduce many key properties of the Tamari lattices. These lattices behave much like distributive lattices even though they violate the Jordan-Dedekind chain condition very strongly having maximal chains that vary in length from N-1 to N(N-1)/2 where N is a parameter used in the construction of these lattices.     

On isotone functions with the Substitution Property in distributive lattices

A universal algebra isaffine complete if all functions satisfying the Substitution Property are polynomials (composed of the basic operations and the elements of the algebra). In 1962, the first author proved that a bounded distributive lattice is affine complete if and only if it does not contain a proper Boolean interval. Recently, M. Ploica generalized this result to arbitrary distributive lattices.In this paper, we introduce a class of functions on a latticeL, we call themID-polynomials, that derive from polynomials on the ideal lattice (resp., dual ideal lattice) ofL; they are isotone functions and satisfy the Substitution Property. We prove that for a distributive latticeL, all unary functions with the Substitution Property are ID-polynomials if and only ifL contains no proper Boolean interval.The research of the first author was supported by the NSERC of Canada. The research of the second author was supported by the Hungarian National Foundation for Scientific Research, under Grant No. 1903.     

The lattice of quasiorder lattices of algebras on a finite set

The quasiorders of an algebra (A, F) constitute a common generalization of its congruences and compatible partial orders. The quasiorder lattices of all algebras defined on a fixed set A ordered by inclusion form a complete lattice \({\mathcal{L}}\). The paper is devoted to the study of this lattice \({\mathcal{L}}\). We describe its join-irreducible elements and its coatoms. Each meet-irreducible element of \({\mathcal{L}}\) being determined by a single unary mapping on A, we characterize completely those which are determined by a permutation or by an acyclic mapping on the set A. Using these characterizations, we deduce several properties of the lattice \({\mathcal{L}}\); in particular, we prove that \({\mathcal{L}}\) is always tolerance-simple.     

A construction of semimodular lattices

In this paper we prove that if is a finite lattice, and r is an integral valued function on satisfying some very natural conditions, then there exists a finite geometric (that is, semimodular and atomistic) lattice I containing as a sublattice such that r is the height function of restricted to . Moreover, we show that if, for all intervals [e, f] of , semimodular lattices I, of length at most r(f)-r(e) are given, then I can be chosen to contain I in its interval [e, f] as a cover preserving {0}-sublattice. As applications, we obtain results of R. P. Dilworth and D. T. Finkbeiner.     

Complemented quasiorder lattices of monounary algebras

We characterize monounary algebras whose lattices of quasiorders are complemented. As a consequence, monounary algebras with Boolean quasiorder lattices are described.     

Transversally bounded lattices

A problem stemming from a boundedness question for torsion modules and its translation into ideal lattices is explored in the setting of abstract lattices. Call a complete lattice L transversally bounded (resp., uniformly transversally bounded) if for all families (X _i)_iIof nonempty subsets of L with the property that {x _iiI}<1 for all choices of x _iX _i, almost all of the sets X _ihave join smaller than 1 (resp., _jJ X _jhas join smaller than 1 for some cofinite subset J of I). It is shown that the lattices which are transversally bounded, but not uniformly so, correspond to certain ultrafilters with peculiar boundedness properties similar to those studied by Ramsey. The prototypical candidates of the two types of lattices which one is led to construct from ultrafilters (in particular the lattices arising from what will be called Ramsey systems) appear to be of interest beyond the questions at stake.     

Comparison of Boolean algebras

In this work, some results related to superatomic Boolean interval algebras are presented, and proved in a topological way. Let x be an uncountable cardinal. To each I x, we can associate a superatomic interval Boolean algebra B _I of cardinality x in such a way that the following properties are equivalent: (i) I I x, (ii) B _I is a quotient algebra of B _J, and (iii) there is an homomorphism f from B _J into B _I such that for every atom b of B _I, there is an atom a of B _J satisfying f(a)=b. As a corollary, there are 2 ^x isomorphism types of superatomic interval Boolean algebras of cardinality x. This case is quite different from the countable one.     

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.     

Lattice subordinations and Priestley duality

There is a well-known correspondence between Heyting algebras and S4-algebras. Our aim is to extend this correspondence to distributive lattices by defining analogues of S4-algebras for them. For this purpose, we introduce binary relations on Boolean algebras that resemble de Vries proximities. We term such binary relations lattice subordinations. We show that the correspondence between Heyting algebras and S4-algebras extends naturally to distributive lattices and Boolean algebras with a lattice subordination. We also introduce Heyting lattice subordinations and prove that the category of Boolean algebras with a Heyting lattice subordination is isomorphic to the category of S4-algebras, thus obtaining the correspondence between Heyting algebras and S4-algebras as a particular case of our approach. In addition, we provide a uniform approach to dualities for these classes of algebras. Namely, we generalize Priestley spaces to quasi-ordered Priestley spaces and show that lattice subordinations on a Boolean algebra B correspond to Priestley quasiorders on the Stone space of B. This results in a duality between the category of Boolean algebras with a lattice subordination and the category of quasi-ordered Priestley spaces that restricts to Priestley duality for distributive lattices. We also prove that Heyting lattice subordinations on B correspond to Esakia quasi-orders on the Stone space of B. This yields Esakia duality for S4-algebras, which restricts to Esakia duality for Heyting algebras.     

On Flat Semimodules over Semirings

The following analog of the characterization of flat modules has been obtained for the variety of semimodules over a semiring R: A semimodule _RA is flat (i.e., the tensor product functor – A preserves all finite limits) iff A is L-flat (i.e., A is a filtered colimit of finitely generated free semimodules). We also give new (homological) characterizations of Boolean algebras and complete Boolean algebras within the classes of distributive lattices and Boolean algebras, respectively, which solve two problems left open in [14]. It is also shown that, in contrast with the case of modules over rings, in general for semimodules over semirings the notions of flatness and mono-.atness (i.e., the tensor product functor – A preserves monomorphisms) are different.     

On the number of join-irreducibles in a congruence representation of a finite distributive lattice

For a finite lattice L, let $ \trianglelefteq_L $ denote the reflexive and transitive closure of the join-dependency relation on L, defined on the set J(L) of all join-irreducible elements of L. We characterize the relations of the form $ \trianglelefteq_L $, as follows: Theorem. Let $ \trianglelefteq $ be a quasi-ordering on a finite set P. Then the following conditions are equivalent:(i) There exists a finite lattice L such that $ \langle J(L), \trianglelefteq_L $ is isomorphic to the quasi-ordered set $ \langle P, \trianglelefteq \rangle $.(ii) $ |\{x\in P|p \trianglelefteq x\}| \neq 2 $, for any $ p \in P $.For a finite lattice L, let $ \mathrm{je}(L) = |J(L)|-|J(\mathrm{Con} L)| $ where Con L is the congruence lattice of L. It is well-known that the inequality $ \mathrm{je}(L) \geq 0 $ holds. For a finite distributive lattice D, let us define the join- excess function:$ \mathrm{JE}(D) =\mathrm{min(je} (L) | \mathrm{Con} L \cong D). $We provide a formula for computing the join-excess function of a finite distributive lattice D. This formula implies that $ \mathrm{JE}(D) \leq (2/3)| \mathrm{J}(D)|$ , for any finite distributive lattice D; the constant 2/3 is best possible.A special case of this formula gives a characterization of congruence lattices of finite lower bounded lattices.Dedicated to the memory of Gian-Carlo Rota     

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.     

Uniform binary geometries

In a geometric lattice every interval can be mapped isomorphically into an upper interval (containing 1) by a strong map. A natural question thus arises as to what extent certain assumptions on the upper interval structure determine the whole lattice. We consider conditions of the following sort: that above a certain levelm any two upper intervals of the same length be isomorphic. This property, called uniformity, is studied for binary geometries. The geometries satisfying the strongest uniformity condition (m = 1) are determined (except for one open case). As is to be expected the corresponding problem for lower intervals is easier and is solved completely.     

Strictly locally order affine complete lattices

We call a latticeL strictly locally order-affine complete if, given a finite subsemilatticeS ofL ⁿ, every functionf: S L which preserves congruences and order, is a polynomial function. The main results are the following: (1) all relatively complemented lattices are strictly locally order-affine complete; (2) a finite modular lattice is strictly locally order-affine complete if and only if it is relatively complemented. These results extend and generalize the earlier results of D. Dorninger [2] and R. Wille [9, 10].     

Identities of cofinal sublattices

If V is a variety of lattices and L a free lattice in V on uncountably many generators, then any cofinal sublattice of L generates all of V. On the other hand, any modular lattice without chains of order-type +1 has a cofinal distributive sublattice. More generally, if a modular lattice L has a distributive sublattice which is cofinal modulo intervals with ACC, this may be enlarged to a cofinal distributive sublattice. Examples are given showing that these existence results are sharp in several ways. Some similar results and questions on existence of cofinal sublattices with DCC are noted.This work was done while the first author was partly supported by NSF contract MCS 82-02632, and the second author by an NSF Graduate Fellowship.     

Proof of a conjecture on partitions of a Boolean lattice

Let n and c be positive integers. We show that if n is sufficiently large given c then the Boolean lattice consisting of all subsets of an n-element set can be partitioned into chains of size c except for at most c — 1 elements which also form a chain. This settles a conjecture of Griggs.     

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.