Stanford Encyclopedia of Philosophy

Supplement to Quantum Logic and Probability Theory

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

missing text, please inform on P. Thus, for all p, q, rP, we have

  1. pmissing text, please informp
  2. pmissing text, please informq and qmissing text, please informp only if p = q.
  3. if pmissing text, please informq and qmissing text, please informr then pmissing text, please informr

If pmissing text, please informq, 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,missing text, please inform) where P is a set and missing text, please inform is a specified ordering on P. It is usual to let P denote both the set and the structure, leaving missing text, please inform 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 missing text, please inform(X) is a poset under set inclusion.

Let P be a poset. The meet, or greatest lower bound, of p, qP, 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 missing text, please inform pq, then rmissing text, please informp and rmissing text, please informq
  2. if pq missing text, please inform r, then pmissing text, please informr and qmissing text, please informr

Note that pp = pp = p for all p in P. Note also that pmissing text, please informq iff pq = p iff pq = q.

Note that if the set P = missing text, please inform(X), ordered by set-inclusion, then pq = pq and pq = pq. 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 = MN, but MN = span(MN).

The concepts of meet and join extend to infinite subsets of a poset P. Thus, if AP, 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 ∧aA a. Similarly, the join of A is denoted by ∨A or by ∨aA a.

2. Lattices

A lattice is a poset (L,missing text, please inform) 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 missing text, please inform(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,missing text, please inform) is distributive iff meets distribute over joins and vice versa:

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

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

The power set lattice missing text, please inform(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 pq = 0 and pq = 1.

In the lattice missing text, please inform(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.

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

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

q = q∧1
  = q ∧ (pr)
  = (qp) ∨ (qr)
  = 0 ∨ (qr)
  = qr

Hence, qmissing text, please informr. Symmetrically, we have rmissing text, please informq; 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 missing text, please inform(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 pmissing text, please informq then qmissing text, please inform p
  2. p′′ = p

When these conditions are satisfied, one calls the mapping pp′ an orthocomplementation on L, and the structure (L,missing text, please inform,′) 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 MM 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 MM.

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 pmissing text, please informq,

(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]:

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 : PQ is order preserving iff for all p,qP, if pmissing text, please informq then f(p)missing text, please informf(q).

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

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

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 missing text, please inform and missing text, please inform are collections of subsets of a set X with missing text, please inform closed under arbitrary unions and missing text, please inform under arbitrary intersections. For any set AX, let

cl(A) = ∩{Cmissing text, please inform | AC}, and

int(A) = ∪{Omissing text, please inform | OA}

Then cl and int are interior operators on missing text, please inform(X), for which the closed and open sets are precisely missing text, please inform and missing text, please inform, respectively. The most familiar example, of course, is that in which missing text, please inform, missing text, please inform are the open and closed subsets, respectively, of a topological space. Another important special case is that in which missing text, please inform is the set of linear subspaces of a vector space V; in this case, the mapping span : missing text, please inform(V) → missing text, please inform(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 pP, qQ

f(p) missing text, please inform q if and only if p missing text, please inform 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:

Let f : LM 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.

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

  1. g missing text, please inform f : LL is a closure operator.
  2. f missing text, please inform g : MM is an interior operator.

Return to Quantum Logic and Quantum Probability