''Introduction to Lattices and Order'' is a

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

textbook on

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

by Brian A. Davey and

Hilary Priestley 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. Hilary Priestley introduced ordered separable topol ...

. It was published by the

Cambridge University Press Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press A university press is an academic publishing hou ...

in their Cambridge Mathematical Textbooks series in 1990, with a second edition in 2002. 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 Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...

. The Basic Library List Committee of the

Mathematical Association of America The Mathematical Association of America (MAA) is a professional society that focuses on mathematics accessible at the undergraduate level. Members include university, college, and high school teachers; graduate and undergraduate students; pure a ...

has suggested its inclusion in undergraduate mathematics libraries.

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 Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premises ...

, topologists, and

lattice Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an ornam ...

theorists. The first chapter concerns

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a Set (mathematics), set. A poset consists of a set toget ...

s, with a fundamental example given by the

partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is de ...

s ordered by the

subset In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...

relation on their

graphs Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

, 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 lattice In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' ...

s, every set) has a

greatest lower bound In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest l ...

and a

least upper bound In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest low ...

. This chapter includes the construction of a lattice from the lower sets of any partial order, and the

Knaster–Tarski theorem In the mathematics, mathematical areas of order theory, order and lattice theory, the Knaster–Tarski theorem, named after Bronisław Knaster and Alfred Tarski, states the following: :''Let'' (''L'', ≤) ''be a complete lattice and let f : L → ...

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 lattice In the branch of mathematics called order theory, a modular lattice is a lattice (order), lattice that satisfies the following self-duality (order theory), dual condition, ;Modular law: implies where are arbitrary elements in the lattice, &nbs ...

distributive lattice 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 uni ...

s, and

Boolean lattice 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 gene ...

s. In the second part of the book, chapter 5 concerns the

theorem In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of th ...

that every finite Boolean lattice is

isomorphic In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...

to the lattice of subsets of a finite set, and (less trivially)

Birkhoff's representation theorem :''This is about lattice theory. For other similarly named results, see Birkhoff's theorem (disambiguation).'' In mathematics, Birkhoff's representation theorem for distributive lattices states that the elements of any finite distributive lattice ...

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 connection In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the funda ...

s on partial orders, and the

Dedekind–MacNeille completion 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 ...

of a partial order into the smallest complete lattice containing it. The next two chapters concern

complete partial order In mathematics, the phrase complete partial order is variously used to refer to at least three similar, but distinct, classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central rol ...

s, their fixed-point theorems, information systems, and their applications to

denotational semantics In computer science, denotational semantics (initially known as mathematical semantics or Scott–Strachey semantics) is an approach of formalizing the meanings of programming languages by constructing mathematical objects (called ''denotations'' ...

. Chapter 10 discusses order-theoretic equivalents of the

axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...

, including extensions of the

representation theorem In mathematics, a representation theorem is a theorem that states that every abstract structure with certain properties is isomorphic to another (abstract or concrete) structure. Examples Algebra * Cayley's theorem states that every group i ...

s from chapter 5 to infinite lattices, and the final chapter discusses the representation of lattices with

topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...

s, including

Stone's representation theorem for Boolean algebras In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a certain field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first hal ...

and the

duality theory for distributive lattices In mathematics, duality theory for distributive lattices provides three different (but closely related) representations of bounded distributive lattices via Priestley spaces, spectral spaces, and pairwise Stone spaces. This duality, which is orig ...

. Two appendices provide background in

topology In mathematics, topology (from the Greek language, Greek words , and ) is concerned with the properties of a mathematical object, geometric object that are preserved under Continuous function, continuous Deformation theory, deformations, such ...

needed for the final chapter, and an annotated bibliography.

Audience and reception

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

discrete mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The term ''a ...

, and

group theory In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups. The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...

. Writing of the first edition, reviewer Josef Niederle calls it "an excellent textbook", "up-to-date and clear". Similarly, Thomas S. Blyth praises the first edition as "a well-written, satisfying, informative, and stimulating account of applications that are of great interest", and in an updated review writes that the second edition is as good as the first. 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". Both Blyth and Cohen note the book's skilled use of

LaTeX Latex is an emulsion (stable dispersion) of polymer microparticles in water. Latexes are found in nature, but synthetic latexes are common as well. In nature, latex is found as a milky fluid found in 10% of all flowering plants (angiosperms ...

to create its diagrams, and its helpful descriptions of how the diagrams were made.

References

{{reflist, refs= {{citation, title=Review of ''Introduction to Lattices and Order'' (1st ed.), journal=

Mathematical Reviews ''Mathematical Reviews'' is a journal published by the American Mathematical Society (AMS) that contains brief synopses, and in some cases evaluations, of many articles in mathematics, statistics, and theoretical computer science. The AMS also pu ...

, first=T. S., last=Blyth, year=1991, mr=1058437 {{citation, title=Review of ''Introduction to Lattices and Order'' (2nd ed.), journal=

, first=T. S., last=Blyth, year=2003, mr=1902334 {{citation , last = Cohen , first = Jonathan , date = March 2007 , doi = 10.1145/1233481.1233488 , issue = 1 , journal =

ACM SIGACT News ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer. Publ ...

, pages = 17–23 , title = Review of ''Introduction to Lattices and Order'' (2nd ed.) , url = http://users.cecs.anu.edu.au/~jon/review.pdf , volume = 38 {{citation , last = Davidow , first = Amy , date = February 1991 , department = Telegraphic Reviews , issue = 2 , journal =

The American Mathematical Monthly ''The American Mathematical Monthly'' is a mathematical journal founded by Benjamin Finkel in 1894. It is published ten times each year by Taylor & Francis for the Mathematical Association of America. The ''American Mathematical Monthly'' is an e ...

, jstor = 2323967 , page = 184 , title = Review of ''Introduction to Lattices and Order'' (1st ed.) , volume = 98 {{citation, title=Review of ''Introduction to Lattices and Order'' (1st ed.), journal=

zbMATH zbMATH Open, formerly Zentralblatt MATH, is a major reviewing service providing reviews and abstracts for articles in pure mathematics, pure and applied mathematics, produced by the Berlin office of FIZ Karlsruhe – Leibniz Institute for Informa ...

, first=Josef, last=Niederle, zbl=0701.06001 {{citation, title=Review of ''Introduction to Lattices and Order'' (2nd ed.), journal=

, first=Václav, last= Slavík, zbl=1002.06001 {{citation, url=https://www.maa.org/press/maa-reviews/introduction-to-lattices-and-order, title=Introduction to Lattices and Order, work=MAA Reviews, publisher=Mathematical Association of America, type=index page only, no review, access-date=2021-07-28 Mathematics textbooks Order theory 1990 non-fiction books 2002 non-fiction books