[sci.math] Posets and Lattices

afzal@cui.unige.ch (Afzal Ballim) (11/14/89)

Hi there,
    I have a problem relating to lattices. I am currently reading "Lattice
Theory" by T. Donnellan. On page 53 of this book, there is a theorem that a
finite lattice has a zero (or least) element, and a unity (or greatest)
element. The theorem itself is simple, based on properties of meet and join.
However, on page 55, at the end of the theorem there is the following
paragraph:

"This theorem indicates how we may form a lattice of n elements from a
partially ordered set of n-2 elements by adding a zero element o and a unity
element u;" [Donnellan, pp.  55].

My problem is this: surely he could not be saying what he seems to be
saying, i.e., that any partial order of n-2 elements can be made into a
lattice of n elements by adding a zero and a unity element. This is
blatantly false. The simplest poset that contradicts this is the abstract
poset of 4 elements:
                   H = {a,b,c,d}
with the following partial ordering:
	  {c <= a, c <= b, d <= a, d <= b} 
The addition of a zero and a unity element to H does not yield a lattice,
because the meet of a and b (a v b) is undefined (the lower bounds of a and
b have no greatest element) and the join of c and d (c ^ d) is also
undefined (their upper bounds have no least element).

So, am I missing something? Is the statement in Donnellan wrong? Or, is
there something missing? For example, must it be the case that the partial
ordering on the set must allow one to define an algebraic operation over the
set for the conclusion (above) to apply?

Any help on this would be appreciated.

-Afzal Ballim
 afzal@divsun.unige.ch
 Institut Dalle Molle pour les Etudes Semantiques et Cognitives
 University of Geneva, Switzerland



References:

Donnellan, T. (1968) "Lattice Theory."  Pergamon Press: Oxford.

moss@takahe.cs.umass.edu (Eliot &) (11/15/89)

I will admit to not being an expert in this area, though I have studied
lattices and posets a bit for understanding how they are used in some styles
of defining the semantics of programming languages. The point is that the two
added elements (conventionally called "bottom" and "top" and drawn as an
upside down T and a regular T in the papers with which I am familiar) are
*defined* to be the meet/join of elements that do not otherwise have a meet or
join. That is what makes the thing a lattice. The Hasse diagram for the poset
you gave is this:

	a   b
        |\ /|
        | X |
        |/ \|
        c   d

The Hasse diagram for the lattice adding 0 and 1 as bottom and top
respectively is this:

	   1
	  / \
	 a   b
	 |\ /|
	 | X |
	 |/ \|
	 c   d
	  \ /
	   0

This is, I believe, a perfectly good lattice. I suppose you did not take into
account that in adding the two new elements to the poset, one also adds <=
relationships as well. In particular, for all elements x, 0 <= x <= 1. I hope
this solves your difficulties ....
--

		J. Eliot B. Moss, Assistant Professor
		Department of Computer and Information Science
		Lederle Graduate Research Center
		University of Massachusetts
		Amherst, MA  01003
		(413) 545-4206; Moss@cs.umass.edu