Last time in this series on Stone duality, we introduced the concept of lattice and various cousins (e.g., inf-lattice, sup-lattice). We said a lattice is a poset with finite meets and joins, and that inf-lattices and sup-lattices have arbitrary meets and joins (meaning that every subset, not just every finite one, has an inf and sup). Examples include the poset PX of all subsets of a set X, and the poset Sub(V) of all subspaces of a vector space V.

I take it that most readers are already familiar with many of the properties of the poset PX; there is for example the distributive law A \cap (B \cup C) = (A \cap B) \cup (A \cap C), and De Morgan laws, and so on — we’ll be exploring more of that in depth soon. The poset Sub(V), as a lattice, is a much different animal: if we think of meets and joins as modeling the logical operations “and” and “or”, then the logic internal to Sub(V) is a weird one — it’s actually much closer to what is sometimes called “quantum logic”, as developed by von Neumann, Mackey, and many others. Our primary interest in this series will be in the direction of more familiar forms of logic, classical logic if you will (where “classical” here is meant more in a physicist’s sense than a logician’s).

To get a sense of the weirdness of Sub(V), take for example a 2-dimensional vector space V. The bottom element is the zero space \{0\}, the top element is V, and the rest of the elements of Sub(V) are 1-dimensional: lines through the origin. For 1-dimensional spaces x, y, there is no relation x \leq y unless x and y coincide. So we can picture the lattice as having three levels according to dimension, with lines drawn to indicate the partial order:

       V = 1
       / | \
     /   |   \
    x    y    z
     \   |   /
       \ | /
         0

Observe that for distinct elements x, y, z in the middle level, we have for example x \wedge y = 0 = x \wedge z (0 is the largest element contained in both x and y), and also for example y \vee z = 1 (1 is the smallest element containing y and z). It follows that x \wedge (y \vee z) = x \wedge 1 = x, whereas (x \wedge y) \vee (x \wedge z) = 0 \vee 0 = 0. The distributive law fails in Sub(V)!

Definition: A lattice is distributive if x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z) for all x, y, z. That is to say, a lattice X is distributive if the map x \wedge -: X \to X, taking an element y to x \wedge y, is a morphism of join-semilattices.

  1. Exercise: Show that in a meet-semilattice, x \wedge -: X \to X is a poset map. Is it also a morphism of meet-semilattices? If X has a bottom element, show that the map x \wedge - preserves it.
  2. Exercise: Show that in any lattice, we at least have (x \wedge y) \vee (x \wedge z) \leq x \wedge (y \vee z) for all elements x, y, z.

Here is an interesting theorem, which illustrates some of the properties of lattices we’ve developed so far:

Theorem: The notion of distributive lattice is self-dual.

Proof: The notion of lattice is self-dual, so all we have to do is show that the dual of the distributivity axiom, x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z), follows from the distributive lattice axioms.

Expand the right side to ((x \vee y) \wedge x) \vee ((x \vee y) \wedge z), by distributivity. This reduces to x \vee [(x \vee y) \wedge z], by an absorption law. Expand this again, by distributivity, to x \vee (x \wedge z) \vee (y \wedge z). This reduces to x \vee (y \wedge z), by the other absorption law. This completes the proof. \Box

Distributive lattices are important, but perhaps even more important in mathematics are lattices where we have not just finitary, but infinitary distributivity as well:

Definition: A frame is a sup-lattice for which x \wedge -: X \to X is a morphism of sup-lattices, for every x \in X. In other words, for every subset S \subseteq X, we have \sup(\{x \wedge s: s \in S\}) = x \wedge \sup(S), or, as is often written,

\bigvee_{s \in S} x \wedge s = x \wedge \bigvee_{s \in S} s.

Example: A power set PX, as always partially ordered by inclusion, is a frame. In this case, it means that for any subset A and any collection of subsets \{B_i: i \in I\}, we have

A \cap (\bigcup_{i \in I} B_i) = \bigcup_{i \in I} A \cap B_i

This is a well-known fact from naive set theory, but soon we will see an alternative proof, thematically closer to the point of view of these notes.

Example: If X is a set, a topology on X is a subset \mathbf{T} \subseteq PX of the power set, partially ordered by inclusion as PX is, which is closed under finite meets and arbitrary sups. This means the empty sup or bottom element \emptyset and the empty meet or top element X of PX are elements of \mathbf{T}, and also:

  1. If U, V are elements of \mathbf{T}, then so is U \cap V.
  2. If \{U_i: i \in I\} is a collection of elements of \mathbf{T}, then \bigcup_{i \in I} U_i is an element of \mathbf{T}.

A topological space is a set X which is equipped with a topology \mathbf{T}; the elements of the topology are called open subsets of the space. Topologies provide a primary source of examples of frames; because the sups and meets in a topology are constructed the same way as in PX (unions and finite intersections), it is clear that the requisite infinite distributivity law holds in a topology.

The concept of topology was originally rooted in analysis, where it arose by contemplating very generally what one means by a “continuous function”. I imagine many readers who come to a blog titled “Topological Musings” will already have had a course in general topology! but just to be on the safe side I’ll give now one example of a topological space, with a promise of more to come later. Let X be the set \mathbb{R}^n of n-tuples of real numbers. First, define the open ball in \mathbb{R}^n centered at a point x \in \mathbb{R}^n and of radius r > 0 to be the set \{y \in \mathbb{R}: ||x - y|| < r\}. Then, define a subset U \subseteq \mathbb{R}^n to be open if it can be expressed as the union of a collection, finite or infinite, of (possibly overlapping) open balls; the topology is by definition the collection of open sets.

It’s clear from the definition that the collection of open sets is indeed closed under arbitrary unions. To see it is closed under finite intersections, the crucial lemma needed is that the intersection of two overlapping open balls is itself a union of smaller open balls. A precise proof makes essential use of the triangle inequality. (Exercise?)

Topology is a huge field in its own right; much of our interest here will be in its interplay with logic. To that end, I want to bring in, in addition to the connectives “and” and “or” we’ve discussed so far, the implication connective in logic. Most readers probably know that in ordinary logic, the formula p \Rightarrow q (“p implies q“) is equivalent to “either not p or q” — symbolically, we could define p \Rightarrow q as \neg p \vee q. That much is true — in ordinary Boolean logic. But instead of committing ourselves to this reductionistic habit of defining implication in this way, or otherwise relying on Boolean algebra as a crutch, I want to take a fresh look at material implication and what we really ask of it.

The main property we ask of implication is modus ponens: given p and p \Rightarrow q, we may infer q. In symbols, writing the inference or entailment relation as \leq, this is expressed as p \wedge (p \Rightarrow q) \leq q. And, we ask that implication be the weakest possible such assumption, i.e., that material implication p \Rightarrow q be the weakest a whose presence in conjunction with p entails q. In other words, for given p and q, we now define implication p \Rightarrow q by the property

(a \wedge p \leq q) if and only if (a \leq p \Rightarrow q).

As a very easy exercise, show by Yoneda that an implication p \Rightarrow q is uniquely determined when it exists. As the next theorem shows, not all lattices admit an implication operator; in order to have one, it is necessary that distributivity holds:

Theorem:

  • (1) If X is a meet-semilattice which admits an implication operator, then for every element p, the operator p \wedge -: X \to X preserves any sups which happen to exist in X.
  • (2) If X is a frame, then X admits an implication operator.

Proof: (1) Suppose S \subseteq X has a sup in X, here denoted \bigvee_{s \in S} s. We have

(\bigvee_{s \in S} s) \wedge p \leq q if and only if

\bigvee_{s \in S} s \leq p \Rightarrow q if and only if

for all s \in S, (s \leq p \Rightarrow q) if and only if

for all s \in S, (s \wedge p \leq q) if and only if

\bigvee_{s \in S} (s \wedge p) \leq q.

Since this is true for all q, the (dual of the) Yoneda principle tells us that (\bigvee_{s \in S} s) \wedge p = \bigvee_{s \in S} (s \wedge p), as desired. (We don’t need to add the hypothesis that the sup on the right side exists, for the first four lines after “We have” show that (\bigvee_{s \in S} s) \wedge p satisfies the defining property of that sup.)

(2) Suppose p, q are elements of a frame X. Define p \Rightarrow q to be \sup(\{a \in X: a \wedge p \leq q\}). By definition, if a \wedge p \leq q, then a \leq p \Rightarrow q. Conversely, if a \leq p \Rightarrow q, then

a \wedge p \leq \sup\{x: x \wedge p \leq q\} \wedge p = \sup\{x \wedge p: x \wedge p \leq q\},

where the equality holds because of the infinitary distributive law in a frame, and this last sup is clearly bounded above by q (according to the defining property of sups). Hence a \wedge p \leq q, as desired. \Box

Incidentally, part (1) this theorem gives an alternative proof of the infinitary distributive law for Boolean algebras such as PX, so long as we trust that p \Rightarrow q := \neg p \vee q really does what we ask of implication. We’ll come to that point again later.

Part (2) has some interesting consequences vis à vis topologies: we know that topologies provide examples of frames; therefore by part (2) they admit implication operators. It is instructive to work out exactly what these implication operators look like. So, let U, V be open sets in a topology. According to our prescription, we define U \Rightarrow V as the sup (the union) of all open sets W with the property that W \cap U \subseteq V. We can think of this inclusion as living in the power set PX. Then, assuming our formula U^c \cup V for implication in the Boolean algebra PX (where U^c denotes the complement of U), we would have W \subseteq U^c \cup V. And thus, our implication U \Rightarrow V in the topology is the union of all open sets W contained in the (usually non-open) set U^c \cup V. That is to say, U \Rightarrow V is the largest open contained in U^c \cup V, otherwise known as the interior of U^c \cup V. Hence our formula:

U \Rightarrow V = int(U^c \cup V).

Definition: A Heyting algebra is a lattice H which admits an implication p \Rightarrow q for any two elements p, q \in H. A complete Heyting algebra is a complete lattice which admits an implication for any two elements.

Again, our theorem above says that frames are (extensionally) the same thing as complete Heyting algebras. But, as in the case of inf-lattices and sup-lattices, we make intensional distinctions when we consider the appropriate notions of morphism for these concepts. In particular, a morphism of frames is a poset map which preserves finite meets and arbitrary sups. A morphism of Heyting algebras preserves all structure in sight (i.e., all implied in the definition of Heyting algebra — meets, joins, and implication). A morphism of complete Heyting algebras also preserves all structure in sight (sups, infs, and implication).

Heyting algebras are usually not Boolean algebras. For example, it is rare that a topology is a Boolean lattice. We’ll be speaking more about that next time soon, but for now I’ll remark that Heyting algebra is the algebra which underlies intuitionistic propositional calculus.

Exercise: Show that (0 \Rightarrow 0) = 1 in a Heyting algebra.

Exercise: (For those who know some general topology.) In a Heyting algebra, we define the negation \neg x to be x \Rightarrow 0. For the Heyting algebra given by a topology, what can you say about \neg U when U is open and dense?