Introduction to Lattices and Order

Last updated

Introduction to Lattices and Order is a mathematical textbook on order theory by Brian A. Davey and Hilary Priestley. It was published by the Cambridge University Press in their Cambridge Mathematical Textbooks series in 1990, [1] [2] [3] with a second edition in 2002. [4] [5] [6] The second edition is significantly different in its topics and organization, and was revised to incorporate recent developments in the area, especially in its applications to computer science. [4] [6] The Basic Library List Committee of the Mathematical Association of America has suggested its inclusion in undergraduate mathematics libraries. [7]

Contents

Topics

Both editions of the book have 11 chapters; in the second book they are organized with the first four providing a general reference for mathematicians and computer scientists, and the remaining seven focusing on more specialized material for logicians, topologists, and lattice theorists. [4]

The first chapter concerns partially ordered sets, with a fundamental example given by the partial functions ordered by the subset relation on their graphs, and covers fundamental concepts including top and bottom elements and upper and lower sets. These ideas lead to the second chapter, on lattices, in which every two elements (or in complete lattices, every set) has a greatest lower bound and a least upper bound. This chapter includes the construction of a lattice from the lower sets of any partial order, and the Knaster–Tarski theorem constructing a lattice from the fixed points of an order-preserving functions on a complete lattice. Chapter three concerns formal concept analysis, its construction of "concept lattices" from collections of objects and their properties, with each lattice element representing both a set of objects and a set of properties held by those objects, and the universality of this construction in forming complete lattices. The fourth of the introductory chapters concerns special classes of lattices, including modular lattices, distributive lattices, and Boolean lattices. [5]

In the second part of the book, chapter 5 concerns the theorem that every finite Boolean lattice is isomorphic to the lattice of subsets of a finite set, and (less trivially) Birkhoff's representation theorem according to which every finite distributive lattice is isomorphic to the lattice of lower sets of a finite partial order. Chapter 6 covers congruence relations on lattices. The topics in chapter 7 include closure operations and Galois connections on partial orders, and the Dedekind–MacNeille completion of a partial order into the smallest complete lattice containing it. The next two chapters concern complete partial orders, their fixed-point theorems, information systems, and their applications to denotational semantics. Chapter 10 discusses order-theoretic equivalents of the axiom of choice, including extensions of the representation theorems from chapter 5 to infinite lattices, and the final chapter discusses the representation of lattices with topological spaces, including Stone's representation theorem for Boolean algebras and the duality theory for distributive lattices. [5]

Two appendices provide background in topology needed for the final chapter, and an annotated bibliography. [6]

Audience and reception

This book is aimed at beginning graduate students, [2] although it could also be used by advanced undergraduates. [6] Its many exercises make it suitable as a course textbook, [2] [3] and serve both to fill in details from the exposition in the book, and to provide pointers to additional topics. [5] Although some mathematical sophistication is required of its readers, the main prerequisites are discrete mathematics, abstract algebra, and group theory. [2] [5]

Writing of the first edition, reviewer Josef Niederle calls it "an excellent textbook", "up-to-date and clear". [3] Similarly, Thomas S. Blyth praises the first edition as "a well-written, satisfying, informative, and stimulating account of applications that are of great interest", [1] and in an updated review writes that the second edition is as good as the first. [4] Likewise, although Jon Cohen has some quibbles with the ordering and selection of topics (particularly the inclusion of congruences at the expense of a category-theoretic view of the subject), he concludes that the book is "a wonderful and accessible introduction to lattice theory, of equal interest to both computer scientists and mathematicians". [5]

Both Blyth and Cohen note the book's skilled use of LaTeX to create its diagrams, and its helpful descriptions of how the diagrams were made. [1] [5]

Related Research Articles

<span class="mw-page-title-main">Boolean algebra (structure)</span> Algebraic structure modeling logical operations

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra.

In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.

In mathematics, the Boolean prime ideal theorem states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on sets is known as the ultrafilter lemma. Other theorems are obtained by considering different mathematical structures with appropriate notions of ideals, for example, rings and prime ideals, or distributive lattices and maximal ideals. This article focuses on prime ideal theorems from order theory.

Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.

In mathematics, there is an ample supply of categorical dualities between certain categories of topological spaces and categories of partially ordered sets. Today, these dualities are usually collected under the label Stone duality, since they form a natural generalization of Stone's representation theorem for Boolean algebras. These concepts are named in honor of Marshall Stone. Stone-type dualities also provide the foundation for pointless topology and are exploited in theoretical computer science for the study of formal semantics.

In mathematical order theory, an ideal is a special subset of a partially ordered set (poset). Although this term historically was derived from the notion of a ring ideal of abstract algebra, it has subsequently been generalized to a different notion. Ideals are of great importance for many constructions in order and lattice theory.

In the mathematical area of order theory, every partially ordered set P gives rise to a dual partially ordered set which is often denoted by Pop or Pd. This dual order Pop is defined to be the same set, but with the inverse order, i.e. x ≤ y holds in Pop if and only if y ≤ x holds in P. It is easy to see that this construction, which can be depicted by flipping the Hasse diagram for P upside down, will indeed yield a partially ordered set. In a broader sense, two partially ordered sets are also said to be duals if they are dually isomorphic, i.e. if one poset is order isomorphic to the dual of the other.

In the mathematical area of order theory, there are various notions of the common concept of distributivity, applied to the formation of suprema and infima. Most of these apply to partially ordered sets that are at least lattices, but the concept can in fact reasonably be generalized to semilattices as well.

<span class="mw-page-title-main">Antimatroid</span> Mathematical system of orderings or sets

In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included. Antimatroids are commonly axiomatized in two equivalent ways, either as a set system modeling the possible states of such a process, or as a formal language modeling the different sequences in which elements may be included. Dilworth (1940) was the first to study antimatroids, using yet another axiomatization based on lattice theory, and they have been frequently rediscovered in other contexts.

In mathematics, a representation theorem is a theorem that states that every abstract structure with certain properties is isomorphic to another structure.

Boolean algebra is a mathematically rich branch of abstract algebra. Stanford Encyclopaedia of Philosophy defines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.' Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1. Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under some operations satisfying certain equations.

In mathematics, the congruence lattice problem asks whether every algebraic distributive lattice is isomorphic to the congruence lattice of some other lattice. The problem was posed by Robert P. Dilworth, and for many years it was one of the most famous and long-standing open problems in lattice theory; it had a deep impact on the development of lattice theory itself. The conjecture that every distributive lattice is a congruence lattice is true for all distributive lattices with at most ℵ1 compact elements, but F. Wehrung provided a counterexample for distributive lattices with ℵ2 compact elements using a construction based on Kuratowski's free set theorem.

<span class="mw-page-title-main">Dedekind–MacNeille completion</span> Smallest complete lattice containing a partial order

In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and constructed it, and after Richard Dedekind because its construction generalizes the Dedekind cuts used by Dedekind to construct the real numbers from the rational numbers. It is also called the completion by cuts or normal completion.

In the branch of mathematics known as universal algebra, a subdirectly irreducible algebra is an algebra that cannot be factored as a subdirect product of "simpler" algebras. Subdirectly irreducible algebras play a somewhat analogous role in algebra to primes in number theory.

In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice can be represented as finite sets, in such a way that the lattice operations correspond to unions and intersections of sets. The theorem can be interpreted as providing a one-to-one correspondence between distributive lattices and partial orders, between quasi-ordinal knowledge spaces and preorders, or between finite topological spaces and preorders. It is named after Garrett Birkhoff, who published a proof of it in 1937.

In universal algebra and lattice theory, a tolerance relation on an algebraic structure is a reflexive symmetric relation that is compatible with all operations of the structure. Thus a tolerance is like a congruence, except that the assumption of transitivity is dropped. On a set, an algebraic structure with empty family of operations, tolerance relations are simply reflexive symmetric relations. A set that possesses a tolerance relation can be described as a tolerance space. Tolerance relations provide a convenient general tool for studying indiscernibility/indistinguishability phenomena. The importance of those for mathematics had been first recognized by Poincaré.

Hilary Ann Priestley is a British mathematician. She is a professor at the University of Oxford and a Fellow of St Anne's College, Oxford, where she has been Tutor in Mathematics since 1972.

In mathematics, particularly in order theory, a pseudocomplement is one generalization of the notion of complement. In a lattice L with bottom element 0, an element x ∈ L is said to have a pseudocomplement if there exists a greatest element x* ∈ L with the property that x ∧ x* = 0. More formally, x* = max{ y ∈ L | x ∧ y = 0 }. The lattice L itself is called a pseudocomplemented lattice if every element of L is pseudocomplemented. Every pseudocomplemented lattice is necessarily bounded, i.e. it has a 1 as well. Since the pseudocomplement is unique by definition, a pseudocomplemented lattice can be endowed with a unary operation * mapping every element to its pseudocomplement; this structure is sometimes called a p-algebra. However this latter term may have other meanings in other areas of mathematics.

<i>The Banach–Tarski Paradox</i> (book) Book about the mathematical paradox

The Banach–Tarski Paradox is a book in mathematics on the Banach–Tarski paradox, the fact that a unit ball can be partitioned into a finite number of subsets and reassembled to form two unit balls. It was written by Stan Wagon and published in 1985 by the Cambridge University Press as volume 24 of their Encyclopedia of Mathematics and its Applications book series. A second printing in 1986 added two pages as an addendum, and a 1993 paperback printing added a new preface. In 2016 the Cambridge University Press published a second edition, adding Grzegorz Tomkowicz as a co-author, as volume 163 of the same series. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion in undergraduate mathematics libraries.

References

  1. 1 2 3 Blyth, T. S. (1991), "Review of Introduction to Lattices and Order (1st ed.)", Mathematical Reviews , MR   1058437
  2. 1 2 3 4 Davidow, Amy (February 1991), "Review of Introduction to Lattices and Order (1st ed.)", Telegraphic Reviews, The American Mathematical Monthly , 98 (2): 184, JSTOR   2323967
  3. 1 2 3 Niederle, Josef, "Review of Introduction to Lattices and Order (1st ed.)", zbMATH , Zbl   0701.06001
  4. 1 2 3 4 Blyth, T. S. (2003), "Review of Introduction to Lattices and Order (2nd ed.)", Mathematical Reviews , MR   1902334
  5. 1 2 3 4 5 6 7 Cohen, Jonathan (March 2007), "Review of Introduction to Lattices and Order (2nd ed.)" (PDF), ACM SIGACT News , 38 (1): 17–23, doi:10.1145/1233481.1233488, S2CID   15496160
  6. 1 2 3 4 Slavík, Václav, "Review of Introduction to Lattices and Order (2nd ed.)", zbMATH , Zbl   1002.06001
  7. ↑ "Introduction to Lattices and Order", MAA Reviews (index page only, no review), Mathematical Association of America, retrieved 2021-07-28
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.