Monotone clones and the varieties they determine

A finite, nontrivial algebra is order-primal if its term functions are precisely the monotone functions for some order on the underlying set. We show that the prevariety generated by an order-primal algebra P is relatively congruence-distributive and that the variety generated by P is congruence-distributive if and only if it contains at most two non-ismorphic subdirectly irreducible algebras. We also prove that if the prevarieties generated by order-primal algebras P and Q are equivalent as categories, then the corresponding orders or their duals generate the same order variety. A large class of order-primal algebras is described each member of which generates a variety equivalent as a category to the variety determined by the six-element, bounded ordered set which is not a lattice. These results are proved by considering topological dualities with particular emphasis on the case where there is a monotone near-unanimity function.This research was carried out while the third author held a research fellowship at La Trobe University supported by ARGS grant B85154851. The second author was supported by a grant from the NSERC.     

Finite modular congruence lattices

We consider the variety of modular lattices generated by all finite lattices obtained by gluing together some M₃’s. We prove that every finite lattice in this variety is the congruence lattice of a suitable finite algebra (in fact, of an operator group). Received February 26, 2004; accepted in final form December 16, 2004.     

The automorphism group of a function lattice: A problem of Jónsson and McKenzie

It is shown that Aut(L ^Q ) is naturally isomorphic to Aut(L) × Aut(Q) whenL is a directly and exponentially indecomposable lattice,Q a non-empty connected poset, and one of the following holds:Q is arbitrary butL is ajm-lattice,Q is finitely factorable and L is complete with a join-dense subset of completely join-irreducible elements, orL is arbitrary butQ is finite. A problem of Jónsson and McKenzie is thereby solved. Sharp conditions are found guaranteeing the injectivity of the natural mapv _P,Q from Aut(P) × Aut(Q) to Aut(P ^Q )P andQ posets), correcting misstatements made by previous authors. It is proven that, for a bounded posetP and arbitraryQ, the Dedekind-MacNeille completion ofP ^Q ,DM(P ^Q ), is isomorphic toDM(P)^Q. This isomorphism is used to prove that the natural mapv _P,Q is an isomorphism ifv _DM(P),Q is, reducing a poset problem to a more tractable lattice problem.Presented by B. Jonsson.The author would like to thank his supervisor, Dr. H. A. Priestley, for her direction and advice as well as his undergraduate supervisor, Prof. Garrett Birkhoff, and Dr. P. M. Neumann for comments regarding the paper. This material is based upon work supported under a (U.S.) National Science Foundation Graduate Research Fellowship and a Marshall Aid Commemoration Commission Scholarship.     

Every finite lattice in $$ \mathcal{V} (M_3) $$

We prove that every finite lattice in the variety generated by M₃ is isomorphic to the congruence lattice of a finite algebra.     

On profinite completions and canonical extensions

We show that if a variety V of monotone lattice expansions is finitely generated, then profinite completions agree with canonical extensions on V. The converse holds for varieties of finite type. This paper is dedicated to Walter Taylor. Received May 14, 2005; accepted in final form September 8, 2005.     

On algebraic properties of monotone clones

Let R ₈ denote the 8-element bounded tower. G. Tardos has shown that C(R ₈), the clone of all monotone functions on R ₈, is not finitely generated. In this paper we show that the clone of all nonsurjective functions is finitely generated.     

Varieties of lattice ordered groups that contain no non-abelian o-groups are solvable

It is shown that the variety _n of lattice ordered groups defined by the identity x ⁿ y ⁿ =y ⁿ x ⁿ , where n is the product of k (not necessarily distinct primes) is contained in the (k+1)st power A ^k+1 of the variety A of all Abelian lattice ordered groups. This implies, in particular, that _n is solvable class k + 1. It is further established that any variety V of lattice ordered groups which contains no non-Abelian totally ordered groups is necessarily contained in _n , for some positive integer n.This work was supported in part, by NSERC Grant A4044.     

Monotone clones and congruence modularity

We investigate the relationship between the local shape of an ordered set P=(P; ) and the congruence-modularity of the variety V generated by an algebra A=(P; F) each of whose operations is order-preserving with respect to P. For example, if V is k-permutable (k2) then P is an antichain; if P is both up and down directed and V is congruence-modular, then V is congruence-distributive; if A is a dual discriminator algebra, then either P is an antichain or a two-element chain. We also give a useful necessary condition on P for V to be congruence-modular. Finally a class of ordered sets called braids is introduced and it is shown that if P is a braid of length 1, in particular if P is a crown, then the variety V is not congruence-modular.     

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.     

Free lattice algorithms

In the late 1930s Phillip Whitman gave an algorithm for deciding for lattice terms v and u if vu in the free lattice on the variables in v and u. He also showed that each element of the free lattice has a shortest term representing it and this term is unique up to commutivity and associativity. He gave an algorithm for finding this term. Almost all the work on free lattices uses these algorithms. Building on the work of Ralph McKenzie, J. B. Nation and the author have developed very efficient algorithms for deciding if a lattice term v has a lower cover (i.e., if there is a w with w covered by v, which is denoted by w) and for finding them if it does. This paper studies the efficiency of both Whitman's algorithm and the algorithms of Freese and Nation. It is shown that although it is often quite fast, the straightforward implementation of Whitman's algorithm for testing vu is exponential in time in the worst case. A modification of Whitman's algorithm is given which is polynomial and has constant minimum time. The algorithms of Freese and Nation are then shown to be polynomial.     

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.     

Simultaneous congruence representations: a special case

We study the problem of representing a pair of algebraic lattices, L₁ and L₀, as Con(A₁) and Con(A₀), respectively, with A₁ an algebra and A₀ a subalgebra of A₁, and we provide such a representation in a special case. Received September 11, 2004; accepted in final form January 7, 2005.     

The word problem in free normal valued lattice-ordered groups: a solution and practical shortcuts

In any lattice-ordered group (l-group) generated by a setX, every element can be written (not uniquely) in the form w(x)=⋁ _i ⋀ _j w _ij (x), where eachw _ij (x) is a group word in the elements ofX. An algorithm will be given for deciding whetherw(x) is the identitye in the free normal valuedl-group onX, or equivalently, whether the statement “∀x,w(x)=e” holds in all normal valuedl-groups. The algorithm is quite different from the one given recently by Holland and McCleary for the freel-group, and indeed the solvability of the word problem was established first for the normal valued case. The present algorithm makes crucial use of the fact (due to Glass, Holland, and McCleary) that the variety of normal valuedl-groups is generated by the finite wreath powersZ Wr Z Wr...Wr Z of the integersZ. In general, use of the algorithm requires a fairly large amount of work, but in several important special cases shortcuts are obtained which make the algorithm very quick. This is an expanded version of material developed while the author was on leave at Bowling Green State University in Bowling Green, Ohio, and presented in 1978 at the Conference on Ordered Groups at Boise State University in Boise, Idaho [9]. Presented by L. Fuchs.     

The saga of the High School Identities

This paper surveys and updates results and open problems related to the variety defined by the High School Identities as well as the variety generated by the positive numbers with exponentiation.In Celebration of the Sixtieth Birthday of Ralph N. McKenzieReceived August 24, 2002; accepted in final form September 13, 2004.     

The free \mathfrak{m} -lattice on the poset H

Let H={a ₀, a ₁, a ₂, b ₀, b ₁, b ₂} be the poset defined by a ₀<a ₂<a ₁, b ₀<b ₂<b ₁, a ₀<b ₁, and b ₀<a ₁. For an infinite regular cardinal , we describe the free -lattice on H. This continues the work of I. Rival and R. Wille who accomplished the same for =. In subsequent papers, we show how to apply this result to describe the free -lattice on a poset for a large class of posets, called slender posets.     

Scheduling tasks with communication delays on parallel processors

LetP={v ₁,...,v _n } be a set ofn jobs to be executed on a set ofm identical machines. In many instances of scheduling problems, if a jobv _i has to be executed before the jobv _j and both jobs are to be executed on different machines, some sort of information exchange has to take place between the machines executing them. The time it takes for this exchange of information is called a communication delay.In this paper we give anO(n) algorithm to find an optimal scheduling with communication delays when the number of machines is not limited and the precedence constraints on the jobs form a tree.     

Free generating sets of lattice-ordered abelian groups

We prove that the generators g₁,…,g_n of a lattice-ordered abelian group G form a free generating set iff each ?-ideal generated by any n−1 linear combinations of the g_i is strictly contained in some maximal ?-ideal of G.     

Finitely generated varieties of distributive double <Emphasis Type="Italic">p</Emphasis>-algebras universal modulo a group

For any monoid M, any universal variety contains arbitrarily large algebras whose endomorphism monoid is isomorphic to M. A variety universal modulo a group G contains arbitrarily large algebras whose endomorphism monoid is isomorphic to the direct product M x G. One of the results of this paper structurally characterizes all finitely generated varieties of distributive double p-algebras universal modulo a group, and shows that any unavoidable direct factor G is a Boolean group with at most eight elements.     

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.     

A characterization of k-normal varieties

Let v be a valuation of terms of type , assigning to each term t of type a value v(t) 0. Let k 1 be a natural number. An identity of type is called k-normal if either s = t or both s and t have value k, and otherwise is called non-k-normal. A variety V of type is said to be k-normal if all its identities are k-normal, and non-k-normal otherwise. In the latter case, there is a unique smallest k-normal variety to contain V , called the k-normalization of V. Inthe case k = 1, for the usual depth valuation of terms, these notions coincide with the well-known concepts of normal identity, normal variety, and normalization of a variety. I. Chajda has characterized the normalization of a variety by means of choice algebras. In this paper we generalize his results to a characterization of the k-normalization of a variety, using k-choice algebras. We also introduce the concept of a k-inflation algebra, and for the case that v is the usual depth valuation of terms, we prove that a variety V is k-normal iff it is closed under the formation of k-inflations, and that the k-normalization of V consists precisely of all homomorphic images of k-inflations of algebras in V .