This is a file in the archives of the Stanford Encyclopedia of Philosophy.

Stanford Encyclopedia of Philosophy
Supplement to Quantum Logic and Probability Theory
Citation Information

The Basic Theory of Ordering Relations

What follows is the briefest possible summary of the order-theoretic notions used in the main text. For a good introduction to this material, see Davey & Priestley [1990]. More advanced treatments can be found in Gratzer [1998] and Birkhoff [1967].

1. Ordered Sets

A partial ordering -- henceforth, just an ordering -- on a set P is a reflexive, anti-symmetric, and transitive binary relation on P. Thus, for all p, q, r ∈ P, we have

  1. pp
  2. pq and qp only if p = q.
  3. if pq and qr then pr

If pq, we speak of p as being less than, or below q, and of q as being greater than, or above p, in the ordering.

A partially ordered set, or poset, is a pair (P,) where P is a set and is a specified ordering on P. It is usual to let P denote both the set and the structure, leaving tacit wherever possible. Any collection of subsets of some fixed set X, ordered by set-inclusion, is a poset; in particular, the full power set (X) is a poset under set inclusion.

Let P be a poset. The meet, or greatest lower bound, of p, q ∈ P, denoted by pq, is the greatest element of P -- if there is one -- lying below both p and q. The join, or least upper bound, of p and q, denoted by pq, is the least element of P -- if there is one -- lying above both p and q. Thus, for any elements p, q, r of P, we have

  1. if r pq, then rp and rq
  2. if pq r, then pr and qr

Note that pp = pp = p for all p in P. Note also that pq iff pq = p iff pq = q.

Note that if the set P = (X), ordered by set-inclusion, then pq = p∩q and pq = p∪q. However, if P is an arbitrary collection of subsets of X ordered by inclusion, this need not be true. For instance, consider the collection P of all subsets of X = {1,2,...,n} having even cardinality. Then, for instance, {1,2}{2,3} does not exist in P, since there is no smallest set of 4 elements of X containing {1,2,3}. For a different sort of example, let X be a vector space and let P be the set of subspaces of X. For subspaces M and N, we have

MN = M∩N, but MN = span(M∪N).

The concepts of meet and join extend to infinite subsets of a poset P. Thus, if A⊆P, the meet of A is the largest element (if any) below A, while the join of A is the least element (if any) above A. We denote the meet of A by A or by a∈A a. Similarly, the join of A is denoted by A or by a∈A a.

2. Lattices

A lattice is a poset (L,) in which every pair of elements has both a meet and a join. A complete lattice is one in which every subset of L has a meet and a join. Note that (X) is a complete lattice with respect to set inclusion, as is the set of all subspaces of a vector space. The set of finite subsets of an infinite set X is a lattice, but not a complete lattice. The set of subsets of a finite set having an even number of elements is an example of a poset that is not a lattice.

A lattice (L,) is distributive iff meets distribute over joins and vice versa:

p (qr) = (pq) (pr), and

p (qr) = (pq) (pr).

The power set lattice (X), for instance, is distributive (as is any lattice of sets in which meet and join are given by set-theoretic intersection and union). On the other hand, the lattice of subspaces of a vector space is not distributive, for reasons that will become clear in a moment.

A lattice L is said to be bounded iff it contains a smallest element 0 and a largest element 1. Note that any complete lattice is automatically bounded. For the balance of this appendix, all lattices are assumed to be bounded, absent any indication to the contrary.

A complement for an element p of a (bounded) lattice L is another element q such that p q = 0 and p q = 1.

In the lattice (X), every element has exactly one complement, namely, its usual set-theoretic complement. On the other hand, in the lattice of subspaces of a vector space, an element will typically have infinitely many complements. For instance, if L is the lattice of subspaces of 3-dimensional Euclidean space, then a complement for a given plane through the origin is provided by any line through the origin not lying in that plane.

Proposition:
If L is distributive, an element of L can have at most one complement.

Proof:
Suppose that q and r both serve as complements for p. Then, since L is distributive, we have

q = q1
  = q (pr)
  = (qp) (qr)
  = 0 (qr)
  = qr

Hence, qr. Symmetrically, we have rq; thus, q = r.

Thus, no lattice in which elements have multiple complements is distributive. In particular, the subspace lattice of a vector space (of dimension greater than 1) is not distributive.

If a lattice is distributive, it may be that some of its elements have a complement, while others lack a complement. A distributive lattice in which every element has a complement is called a Boolean lattice or a Boolean algebra. The basic example, of course, is the power set (X) of a set X. More generally, any collection of subsets of X closed under unions, intersections and complements is a Boolean algebra; a theorem of Stone and Birkhoff tells us that, up to isomorphism, every Boolean algebra arises in this way.

3. Ortholattices

In some non-uniquely complemented (hence, non-distributive) lattices, it is possible to pick out, for each element p, a preferred complement p′ in such a way that

  1. if pq then q′ p′
  2. p′′ = p
When these conditions are satisfied, one calls the mapping p→p′ an orthocomplementation on L, and the structure (L,,′) an orthocomplemented lattice, or an ortholattice for short.

Note again that if a distributive lattice can be orthocomplemented at all, it is a Boolean algebra, and hence can be orthocomplemented in only one way. In the case of L(H) the orthocomplementation one has in mind is M → M⊥ where M⊥ is defined as in Section 1 of the main text. More generally, if V is any inner product space (complete or not), let L(V) denote the set of subspaces M of V such that M = M⊥⊥ (such a subspace is said to be algebraically closed). This again is a complete lattice, orthocomplemented by the mapping M → M⊥.

4. Orthomodularity

There is a striking order-theoretic characterization of the lattice of closed subspaces of a Hilbert space among lattices L(V) of closed subspaces of more general inner product spaces. An ortholattice L is said to be orthomodular iff, for any pair p, q in L with pq,

(OMI)       (qp′)p = q.

Note that this is a weakening of the distributive law. Hence, a Boolean lattice is orthomodular. It is not difficult to show that if H is a Hilbert space, then L(H) is orthomodular. The striking converse of this fact is due to Amemiya and Araki [1965]:

Theorem:
Let V be an inner product space (over R, C or the quaternions) such that L(V) is orthomodular. Then V is complete, i.e., a Hilbert space.

5. Closure Operators, Interior Operators and Adjunctions

Let P and Q be posets. A mapping f : P → Q is order preserving iff for all p,q ∈ P, if pq then f(p)f(q).

A closure operator on a poset P is an order-preserving map cl : P → P such that for all p ∈ P,

Dually, an interior operator on P is an order-preserving mapping int : P → P on P such that for all p ∈ P,

Elements in the range of cl are said to be closed; those in the range of int are said to be open. If P is a (complete) lattice, then the set of closed, respectively open, subsets of P under a closure or interior mapping is again a (complete) lattice.

By way of illustration, suppose that and are collections of subsets of a set X with closed under arbitrary unions and under arbitrary intersections. For any set A ⊆ X, let

cl(A) = ∩{C∈ | A ⊆ C}, and

int(A) = ∪{O∈ | O ⊆ A}

Then cl and int are interior operators on (X), for which the closed and open sets are precisely and , respectively. The most familiar example, of course, is that in which , are the open and closed subsets, respectively, of a topological space. Another important special case is that in which is the set of linear subspaces of a vector space V; in this case, the mapping span : (V) → (V) sending each subset of V to its span is a corresponding closure.

An adjunction between two posets P and Q is an ordered pair (f, g) of mappings f : P → Q and g : Q → P connected by the condition that, for all p ∈ P, q ∈ Q

f(p) q if and only if p g(q).

In this case, we call f a left adjoint for g, and call g a right adjoint for f. Two basic facts about adjunctions, both easily proved, are the following:

Proposition:
Let f : L → M be an order-preserving map between complete lattices L and M. Then
  1. f preserves arbitrary joins if and only if it has a right adjoint.
  2. f preserves arbitrary meets if and only if it has a left adjoint.

Proposition:
Let (f, g) be an adjunction between complete lattices L and M. Then

  1. g f : L →L is a closure operator.
  2. f g : M → M is an interior operator.

Return to Quantum Logic and Quantum Probability

Copyright © 2002
Alexander Wilce
wilce@susqu.edu

Supplement to Quantum Logic and Probability Theory
Stanford Encyclopedia of Philosophy