Puzzle of the Day

A lattice is a mathematical structure composed of a set S and a relation r. If x, y, and z are elements of S, and r is a relation over those elements, then (S, r) is a lattice if and only if the following conditions are met:

  1. r is reflexive, so for every element x in S, xrx.
  2. r is antisymmetric, so if xry and yrx, then x = y.
  3. r is transitive, so if xry and yrz, then xrz.
  4. Every pair of elements in S has a lower bound. In other words, there is a z in S such that zrx and zry for every pair (x, y).
  5. Every pair of elements in S has an upper bound. In other words, there is a z in S such that xrz and yrz for every pair (x, y).

Does ({ 1, 2, 3, 4, 5 }, <=) form a lattice? How about ({true, false}, and)?


You can also see this document in its native format, in Postscript, in PDF, or in ASCII text.
Send email to cs153@csif.cs.ucdavis.edu.

Department of Computer Science
University of California at Davis
Davis, CA 95616-8562



Page last modified on 12/2/98