Friday nights at the Library

On foundations and folklore

Maria Cristina Pedicchio (also ) and Walter Tholen, eds. Categorical foundations. Special topics in order, topology, algebra, and sheaf theory. Cambridge: Cambridge University Press, 2004. (Encyclopedia of Mathematics and its Applications, 97) See also the item “Atlantis” in Tholen’s publication list.

In Scholastic philosophy, a local assumption—that is, a premise that is not the conclusion of some prior argument—is often called a fundamentum, a “foundation”. To be a fundamentum is a rhetorical matter; distinctions treated as fundamenta in one context may be argued for at length elsewhere. A fundamentum functions as a point granted by both sides in a disputatio, because it is obvious, perhaps, or a matter of faith. Of course what is obvious to a well-trained Jesuit may not be obvious to you or me.

Mathematical argument is replete with fundamenta in the Scholastic sense. For example, I may start a proof by saying “let f : A → B be a map and let Im f be the image of f ”. I’m assuming of course that you know how to interpret the symbols; I’m also assuming a lemma of the form “Every map has an image”.

One fundamentum that turned out not to be easily proved is the Jordan Curve Theorem. The Theorem states that every simple closed curve in the plane divides the plane into exactly two pieces separated from one another by the curve. Everyone assumed, most often tacitly, its truth; but even Camille Jordan, after whom it is named, did not succeed in proving it; Oswald Veblen finally proved it in 1905. A rigorous proof (a formal proof, that is, checkable by a computer) was completed only in 2005 after fourteen years of effort. See Yakusa Nakamura, “Culmination of a complete proof of the Jordan Curve Theorem” (Sep 2005); the proof itself is accessible from the “abstract” at the Mizar Home Page.

It is my expectation that either you will have seen a proof of the lemma or that you will grant it for the sake of argument. In every branch of mathematics, as it develops, there is a collection of fundamenta, theorems that everyone takes as proved—the “folklore” of that branch. Some have in fact been proved; but some, taken as obvious, may not be explicitly proved until someone writes an introduction to the subject for outsiders. You won’t, after all, make your mark by proving what everyone “knows”—even if in fact they don’t. Though fundamenta are supposed to be obvious, and (so you’d think) easy to prove, sometimes the obvious and the easy-to-prove part ways. The worst case is when the obvious turns out to be false; but that, I think, is not so common. More often it turns out that what was taken to be obvious is not—that is, it depends on hitherto unstated conditions.

▷▷

“Foundations” took a new turn…

“Foundations” took a new turn with Descartes. The task of the Meditations is to discover absolute foundations—propositions that might serve as premises in any context. Correlative with absolute foundations is an absolute notion of obviousness, the “evident” or “self-evident” propositions Descartes claims to know by the light of nature. The subsequent rejection of innate ideas by Locke did not include a rejection of absolute foundations; but now they were to be found in the simple ideas of sense or in ideas of reflection deriving from ideas of sense.

In mathematics, axioms were often justified on the grounds that they were evident. By the end of the nineteenth century, however, it had become clear that some propositions thought to be evident by intuition were either false or else not at all evident in the sense of being easily proved from other more secure propositions. Naïve evidence, or even the refined versions of it put forward by philosophers, ceased to be relevant to the acceptance of mathematical truths. Mathematics ceased to have foundations in the Cartesian sense.

One result was that the part of philosophy known as the “foundations of mathematics” has, over time, lost its rationale. The axioms of set theory—or even those of logic—are not foundational in the Cartesian sense. They are neither evident nor absolute. They remain “first” (as “first philosophy” was first) to the extent that they are explicitly or implicitly appealed to in many mathematical proofs. That is to say, the mathematician finds herself using propositions from set theory frequently in other parts of mathematics. That set theory serves that purpose is no accident. It was designed in part to be a universal workspace, in which the constructions of all other branches of mathematics could be modelled. If the group theorist wants to define the product of two groups, he starts with the product of their underlying sets. Similarly a quotient object in the category of groups is realized by a quotient in sets. Questions of existence can be referred to set theory, whose axioms assert the existence of the requisite models.

The Foundations in Pedicchio and Tholen’s collection are fundamenta both by virtue of being “obvious” (up to a point) to those well-versed in the discipline and by virtue of being “first” in their respective branches. Everyone “knows”, for example, that an idempotent commutative monoid—which is algebraic object—is equivalent, in a sense only recently made precise, to a semilattice. Everyone has known for much longer that in many cases the collection of subobjects of an algebra is a lattice. Knowing those things is requisite to knowing many other things: knowing how to subtract is requisite to knowing the algorithm for long division.

A mathematician’s expertise includes knowing a great many propositions of the form “every so-and-so is a so-and-so”, and also of the form “not every so-and-so is a so-and-so”. The latter are typically witnessed by counterexamples.

Separation properties. The inclusions are proved from the definitions; the properness of the inclusions is witnessed by counterexamples (Seebach & Steen’s example no. 8, for instance, witnesses the truth of “not every T0 space is T1”). Adapted from Lynn A. Steen & J. Arthur Seebach, Jr., Counterexamples in topology (2nd ed., Springer, 1978; Dover, 1995), p16.

The picture on the right, adapted from Seebach and Steen’s Counterexamples in topology, exhibits the relations among classes of topological spaces; the properties listed (other than “Urysohn”) are defined in terms of the open sets and points of a space. It is likely that only specialists will know all the inclusions pictured here. But most mathematicians will know what “Hausdorff” means, that not all spaces are Hausdorff, and that certain constructions preserve Hausdorffness.

The fundamenta of mathematics as a whole are a kind of quilt composed of the overlapping fundamenta of its various branches, together with a small collection of fundamenta common to all. This would include logic (at least constructive logic), naïve set theory, and—increasingly—the basics of category theory. Pedicchio and Tholen’s collection is a series of “glimpses”, from a categorical point of view, of “key areas” in mathematics (2). Those areas are: the theory of order, topology, commutative algebra, universal algebra (as the theory of “monads”), sheaf theory, and the descent theory of Grothendieck.

In a capsule history, Tholen states the project of the new way of doing “structural mathematics” that emerged in the work of Samuel Eilenberg and Saunders Mac Lane during and just after World War II.

Rather than building objects made up from sets with a structure, like topological spaces and modules over a ring, one imposes additional conditions on a category which make its objects behave like the structured sets one has in mind. Hence, rather than relying on a set-theoretic foundation on which to build the structures at issue, one moves into a “fully equipped building” in which to explore the objects of interest (“Introduction”, 1).

Each branch of mathematics requires a “workspace” that contains the tools and materials for building the objects it studies. Set theory, as I’ve said, is a universal workspace. Many theories—including, for example, elementary theories of objects like groups and rings—do not require so much as set theory provides (unless you are interested in questions of cardinality and the like, where you may need the full machinery of “higher set theory”). Two sorts of questions arise. The first sort concerns the “base category” from which you start. If you want to build groups, you need at least to be able to define operations; and if your theory is to include theorems analogous to those of the classical theory of groups, you need various other constructions too. The second sort concerns global features of the category of the objects constructed. What sort of features must a category have to be a category of groups, of spaces?

The most successful instances…

The most successful instances of providing answers to questions of the second sort are the treatment of algebras (objects equipped with operations) in the theory of monads, which developed out of work by F. W. Lawvere in the 1960s, and the treatment of modules and abelian groups in the theory of abelian categories, which arose in the work of Grothendieck in the 1950s; the first notable results of that work were proofs in the mid-1960s that categories of modules are “abstractly” the same as categories satisfying certain axioms stated in the elementary language of categories. Chapters 5 & 6 of Foundations are an introduction to monads and algebraic theories; Chapter 4 describes abelian categories and categories related to them.

Seen in this light, the theory of sets is not so much a description of the mathematical universe as it is the specification of a workspace—a “convenient category”—in which to build various objects, notably the classical objects ℕ, ℤ, ℚ, ℝ, and ℂ (the natural numbers, the integers, the rationals, the reals, and the complex numbers), together with structures based on them like n-dimensional Euclidean space or the space of all functions from ℝ to ℝ. Philosophers have tended to think of those objects as unique (if they exist at all). There is just one 1, just one 2, and so on, to which the names ‘1’, ‘2’, and so on refer uniquely; and thus too just one set of natural numbers. Mathematics is about the classical objects, so that group theory, topology, and so on just provide ever fancier ways of proving theorems about numbers or sets constructed from numbers. So-called “structuralism” in the philosophy of mathematics has altered that only to the extent of talking about “patterns”; but this, it seems to me, is a rudimentary version of profounder, more fruitful ideas to be found in mathematics itself.

Here’s an example…

Here’s an example in which both sorts of question are answered. The topic is recursion. What sorts of structures support recursion, and in what sorts of category is recursion constructible? The answer, which is due to Lawvere, is that the structure is a “pointed endomorphism” object, and the category is one that has a “natural numbers object” or NNO.

An endomorphism is just a morphism or arrow from an object to itself. The map n ↦ 2n is an endomorphism of the natural numbers; so is the map that sends everything to 0. A pointed endomorphism is an endomorphism together with a map from the terminal object ∗ of the category that the object lives in to that object. (A “terminal object” in a category is an object ∗ such that every object in the category has exactly one arrow to ∗. In the category of sets any one-point set is terminal.) In short,

u:∗ → X, s:X → X

is the structure of a pointed endomorphism. The inspiration for s is the successor function n ↦ n + 1 in the natural numbers as these are defined in set theory; the inspiration for the “point” is 0.

Given u:∗ → X, s:X → X and v:∗ → Y, t:Y → Y, a morphism of pointed endomorphisms is a morphism f :X → Y such that

f (u∗) = v∗ (the image of the “zero” of s is the “zero” of t)

f · s = t · f  (the image of the “successor” is the “successor” of the image)

If we take s to be the successor function for the natural numbers as defined in a set theory, then the second condition becomes f (n + 1) = t(f (n)), which looks more like a recursive definition: f (1) = f · s(0) = t · f (0), f (2) = f · s(1) = t · f (1) = t · f · s(0) = t · t · f (0), and in general f (n) = f (sn0) = tn · f (0).

A natural numbers object in a category is a pointed endomorphism N = zero :∗ → N, s:N → N such that there is a unique morphism from N to every other pointed endomorphism (see Lambek & Scott 46, 68). Notice that this, unlike the definition of ‘pointed endomorphism’, is a condition on the entire category.

Order

Some chapters in Categorical foundations are too technical to be of immediate interest to philosophers. R. J. Wood’s chapter on order, however, concerns a topic that many philosophers will have encountered in logic. Even so, the standpoint taken will probably be unfamiliar. If you have studied logic, you will know the inference rules for disjunction; you will know the truth-table; but you will probably not know that ‘or’ is the join operation for the lattice of truth values or that it is “adjoint to the diagonal morphism”. Those are more general characterizations: they define conjunction even where the lattice of truth values is not Boolean, and they extend readily to infinite disjunction.

An order is…

An order is a special sort of category, so we’ll start with that.

Categories

A category consists in a collection of arrows and a collection of objects. Every arrow has two objects (not necessarily distinct) assigned to it: a source and a target. Every object has one arrow assigned to it: its identity arrow, whose source and target are that same object.

Given two arrows f and g, if the source of g is identical to the target of f, then they are composable. In a category, every pair of composable arrows has a composite.

An identity arrow for an object x is composable with every arrow that has x as either its source or its target. In a category, composable arrows always have a composite. The composite of f and g in the diagram on the right is g · f. If f and g were not composable, the value of g · f would not be defined. Note the reversal: this is owing to the traditional notation g(f(x) for the composite. It’s annoying but one has to get used to it.

Suppose now that g · f and h · g are defined. We have the situation at right.

There are two ways to construct an arrow from A to D, the composite (h · g) · f and the composite h · (g · f). Life would be simpler if these were identical. In particular, a unique arrow would correspond to each path from one object to another, where a path is a sequence of objects and arrows that looks like this: • → • → … → •.

In a category, life is simple:

(h · g) · f = h · (g · f)

(whenever one of the two is defined). This condition is called associativity.

The identity arrows are lazy. They leave everything unchanged. Composing an identity with any arrow yields that same arrow again.

idx · f = f

f · idx = f

whenever these are defined. (Exercise: suppose that every arrow is composable with every arrow. How many objects are there? How many identity arrows?)

Equations for a diagram tell us when two paths (with the same start and the same end) are identical. A diagram is commutative if any two paths with the same start and end are identical. If the square at right is commutative, then g · f = k · h. (The motivation for calling such a square “commutative” is that if h = g and f = k, then the diagram states that f · g = g · f, which is the commutative law in algebra.)

You might find all this very abstract. But it isn’t really. The diagrams you’ve just been looking at are categories—provided that we add to them all the arrows that the axioms require. That means attaching an identity morphism to every vertex, and composing all the composables. The result of doing this to the commutative square above is the “decorated” square at the right. From now on all diagrams will be assumed to be decorated; each of them thus represents a finite category. Diagrams will also be assumed to commute unless this is specifically denied.

Orders

An order (which other authors call a “preorder”) is a category which has at most one arrow from any object to any object. It follows immediately that the only arrow from an object to itself—the only endomorphism—is the identity arrow with which every object is equipped. Suppose we write x ≤ y for “there exists an arrow from x to y”. Then we have, for all x,

x ≤ x

A relation satisfying the condition is reflexive. Orders are thus first of all reflexive relations.

The existence of composites tells us that if there is an arrow from x to y and an arrow from y to z then there is an arrow from x to z—the composite, which will be the unique arrow from x to z.

if x ≤ y and y ≤ z, then x ≤ z

A relation satisfying this condition is transitive. An order is therefore a reflexive and transitive relation. Here is a Gallery of Orders (it is understood that all arrows point up):

Let L and M be orders. A morphism f from L to M (also known as a “monotone map”) assigns to each object of L an object of M in such a way as to “preserve the order”:

if x ≤ y in L then fx ≤ fy in M. This definition does not preclude fx = fy, since after all ≤ is reflexive. Nor does it preclude the existence of elements in M between fx and fy, even if there are none in L between x and y. So for example the map n ↦ 2n preserves order in the natural numbers (just as 5 ≤ 7 so too 5 · 2 ≤ 7 · 2), and so does the map that sends everything to 0.

There is a category that has just one object and just one arrow—the identity arrow it is required to have. That category is an order. Call it ∗. Given an order L, there is a morphism from L to ∗ that consists in assigning to every object in L the unique object of ∗. That is in fact the only morphism from L to ∗. In general, an object which is the target of exactly one morphism from every object in its category is called a terminal object. ∗ is the terminal object in the category of orders. (I haven’t shown that orders and order-morphisms are a category. But this is easy to prove.)

Partial order

Consider the diagram in a preorder. Starting from x the two arrows compose to yield an arrow from x to itself; starting from y they compose to yield an arrow from y to itself. But the axiom for a preorder (“at most one arrow”, etc.) tells us that in each case the arrow must be an identity. If a pair of arrows f, g is such that f · g and g · f are both identity, then f and g are isomorphisms. In any category, two objects x and y are isomorphic (in symbols: x ≅ y) if there is an isomorphism between them.

From the standpoint of the predicates available in the elementary theory of categories, isomorphic objects are indistinguishable. Anything true of one is true of the other. In the category of sets, for example, all one-point sets are isomorphic, and there is no predicate of sets expressible in the elementary theory of the category of sets that distinguishes them.

Isomorphism is an equivalence relation (each object is isomorphic to itself; if x is isomorphic to y then y is isomorphic to x; and since the composite of isomorphisms is an isomorphism, ‘being isomorphic to’ is transitive). In the usual way we could form equivalence classes and construct a new preorder from the old in which the following holds:

If there is an arrow from x to y and from y to x then x = y.

In the usual language of orders, this becomes the axiom of antisymmmetry:

If x ≤ y and y ≤ x, then x = y.

A partial order, then, is a preorder in which isomorphism and identity coincide. In the general case, constructing a partial order from a preorder requires the Axiom of Choice, which is not constructive (Wood in Foundations 16–17). Many of the theorems of the theory of partial orders can be restated as theorems about preorders provided that instead of = one writes ≅ (see for example, Wood, Proposition 3.7). On the whole, the difference between identity and isomorphism doesn't seem to matter much in mathematics; the mathematician doesn’t care whether Shakespeare, or merely someone just like him, wrote Hamlet.

Opposites

If C is a category, then so is Cop, the opposite of C (in the theory of order, opposites are sometimes called “duals”). Cop is defined by “reversing the arrows” of C:

Cop has the same objects and arrows as C

the source of an arrow f in Cop is its target in C

the target of an arrow f in Cop is its source in C

the composite in Cop of composable arrows f and g is their composite g · f, but with source and target interchanged as above

In orders, things are simpler. The opposite Lop of an order L has the same objects as L; x ≤ y in Lop iff y ≤ x in L. Of the orders in the Gallery, the first four are the same as their opposites; the last is not.

One needs to show that opposites, so defined, really are categories or orders. But this is readily verified by looking at diagrams of the axioms. They are “self-dual”—that is, reversing the arrows yields the same diagram.

Adjoints

What might be called the “categorical point of view” is apparent from the prominence in Wood’s exposition of adjunctions. Suppose we have morphisms f: L → M, u: M → L. Then f is (left) adjoint to u iff for all x in L and all y in M,

fx ≤ y iff x ≤ gy.

That condition immediately yields (by applying it to ‘fx ≤ fx’ and to ‘gy ≤ gy’)

x ≤ (g · f)x

(f · g)y ≤ y

Those two conditions, as it happens, suffice to make f and g adjoint (this is a special case of a general fact about adjoints).

Elements and products

Though it is sometimes said that category theory does without elements, it would be accurate to say that it generalizes the set-theoretical relation “is an element of”.

Given two orders E and L, define an element of shape E in L to be a morphism x : E → L. For example, an element of shape • → • in L is just an arrow in L (together with the identity arrows of its source and target). An element of shape ∗ in L is an object of L (together with its identity arrow). Notice that if x : E → L is an element of L, and y : L → M an element in M, then y · x is an element (of shape E) in M. The identity morphism of an order L is an L-shaped element of L. In a general category, a D-shaped object in an category C is a morphism (i.e. a functor) from D to C; when D is a finite category, a D-shaped object is a diagram in the usual sense.

This “shape” talk shouldn’t be taken too literally. In an order, there is an element of shape x in the object y just in case x ≤ y. Here the notion of “shape” is not interesting. On the other hand, in geometry the notion defined does overlap nicely with the commonsense notion. A “line-shaped” object in the plane is a curve of some sort—a continuous image of the unit interval {x | 0 ≤ x ≤ 1}.

Again, given an order E and two orders L and M, define a joint element of shape E in L and M to be a pair of morphisms x : E → L, y : E → M.

We might ask: is there one order P such that elements of P “represent” joint elements of L and M in the sense that for every joint element there is exactly one element of P and vice versa?

An element x of shape E in P would also be a joint element of L and M if there were morphisms p1 : P → L and p2 : P → M, since p1 · x would be an element of L and p2 · x an element of M.

An order P equipped with morphisms p1 : P → L and p2 : P → M would represent joint elements of L and M if for every order E and every joint element x : E → L, y : E → M there is exactly one morphism f from E to P such that x = p1 · f and y = p2 · f. Such a P, if it exists, is called the product of L and M, and denoted L × M, and the representative in L × M of the joint element x : E → L, y : E → M is denoted ‹x, y› (this by analogy with the notation for ordered pairs in set theory).

When orders are defined in the usual way as relations on sets, then the “objects” of an order L are just the elements of its underlying set ob L, and the product of two orders L and M is the set ob L × ob M with the order given by ‹x, y› ≤ ‹w, z› in L × M iff x ≤ w in L and y ≤ w in M.

Let’s suppose that for a given order L, the product L × L exists. The identity id of L is a joint element of L and L; so there is a unique morphism, denoted Δ , from L to L × L. This morphism assigns to an element x : E → L the element ‹x, y› : E → L × L. Δ is called the diagonal morphism (think of the graph of the line x = y on the x-y plane, which is the set of ordered pairs ‹x, x›).

Meet and join

In an order z is a lower bound of x and y if z ≤ x and z ≤ y. The meet of x and y is their greatest lower bound, if that exists.

Notice that the definition of meet, pictured on the right, looks exactly like the definition of product. That suggests that products and meets are instances of the same phenomenon.

In fact they are both adjoints (Wood, Foundations, 19). Let L be an order, and let Δ : L → L × L be defined as before. Suppose that L has a meet for every pair of elements. Consider the meet to be a morphism ⋀ : L × L → L, where to the element ‹x, y› there corresponds the meet of x and y, denoted ⋀xy or x ⋀ y, in L (I haven’t shown that ⋀ is order-preserving, but let’s suppose it is). If Δ is (left) adjoint to ⋀, we must have

Δx = ‹x, x› ≤ ‹y, y´› in L × L iff x ≤ ⋀yy´ in L.

But since ‹x, x› ≤ ‹y, y´› in L × L iff x ≤ y and x ≤ y´ in L, this amounts to saying that ⋀yy´ is a greatest lower bound if it is a lower bound at all; but substituting ⋀yy´ for x in the proposition above shows that it is indeed a lower bound.

The join is defined dually. Reverse the ≤ in the definitions above. An order that has meets need not have joins, and vice versa.

Consider, finally, an adjoint to the unique morphism t:L → ∗, where ∗ is the one-point order. This is a morphism b: ∗ → L such that for all y in L

b∗ ≤ y in L iff ∗ ≤ ty in ∗.

But the right-hand side is always true (since ty = ∗ for all y), and so we have defined an element b∗ which is the least element in L. The least element in an order, if it exists, is denoted by 0 or ⊥. Dually we can define a greatest element in L, denoted 1 or ⊤. It should be clear that having a least element and having a greatest element are independent (if not, look at the last picture in the Gallery, and consider its opposite too).

A 0,1–lattice is usually defined as a partial order with meet and join operations ⋀, ⋁ and least and greatest elements 0, 1. (Such a lattice can be degenerate—it can have 0 coincide with 1—but it cannot be empty.) We have seen that the operations of a lattice (including 0 and 1 considered as “nullary” operations) can be treated as adjoints to “natural” morphisms in the category of orders—the diagonal morphism Δ and the unique morphism to the terminal object ∗.

One lattice of especial importance in topology is the lattice • → • (remember that identity arrows are understood to be present. This lattice, denoted 2, is the lattice of the indiscrete topology defined below.

One moral to draw from Wood’s treatment of lattices (and the treatment of Heyting lattices and Boolean algebras that follows) is that not all axiomatizations of a theory are equal. Some make evident connections with other parts of mathematics; others obscure them.

Russell’s principles of deduction…

In his Introduction to mathematical philosophy, Russell gives five “formal principles of deduction” (1920 ed., pp149–150). In a more modern notation, these are:

• (i) p ⋁ p ⊦ p
• (ii) q ⊦ p ⋁ q
• (iii) p ⋁ q ⊦ q ⋁ p
• (iv) p ⋁ (q ⋁ r) ⊦ q ⋁ (p ⋁ r)
• (v) q ⇒ r ⊦ (p ⋁ q) ⇒ (p ⋁ r)

A little work shows that these axioms make the relation ⊦ an order on the set of well-formed words in the language assumed here by Russell (you need a deduction theorem, I think, to get transitivity from (v); but Russell doesn’t distinguish strongly between the object-language ⇒ and the metalanguage ‘implies’). We can make that order a partial order (i.e. reflexive, transitive, and antisymmetric) by treating as equivalent all terms t, u such that t ⊦ u and u ⊦ t. That partial order is a join-semilattice with respect to ⋁: axiom (i) tells you that ⋁ is idempotent (p ⋁ p = p), (iii) tells you that it is commutative (p ⋁ q = q ⋁ p), and from (iii) and (iv), using substitution, it follows that ⋁ is associative (p ⋁ (q ⋁ r) = (p ⋁ q) ⋁ r). (I am abusing notation by writing ‘p’ for the equivalence class of p and ⋁ for a new operation on equivalence classes derived from the original ⋁. One would also need to show that in the partial order, p ⋁ q really is the greatest lower bound of p and q.)

Idempotence, commutativity, and associativity are “natural” conditions on an operation. Not only are they simple, but they arise automatically in a variety of contexts. The condition corresponding to the “twisted” associative axiom (iv) is not in this sense as natural. Russell claims for (iv) the virtue of increased “deductive” power. But that comes at the expense of another sort of power: the efficiency that comes with proving things once for a great variety of specific instances.

In the present instance we might start with the order given by ⊦. There are of course endlessly many examples of orders. We might then note that ⋀ is the greatest lower bound in that order (which immediately gives you the rules p ⋀ q ⊦ p, p ⋀ q ⊦ p, and also (the solid horizontal lines are the same as ⊦, the dotted line represents ‘if … then …’ in the metalanguage)

r p	r q
r p ⋀ q

Similarly, ⋁ is the least upper bound in the ⊦ - order (the rules are the rules for ⋀ with the turnstile reversed).

The resulting structure is a lattice, which is simultaneously an order and an algebra. In Russell’s logic, the lattice is distributive: p ⋀ (q ⋁ r) is equivalent to (p ⋀ q) ⋁ (p ⋀ r). If we then introduce ⇒ by the rules

p ⋀ q ⊦ r p ⊦ q ⇒ r

p ⊦ q ⇒ r p ⋀ q ⊦ r

we have a new structure, a Heyting algebra. (Arend Heyting was a student of L. E. J. Brouwer, the founder of intuitionism. He was the first to formalize intuitionistic logic). The rules say that q ⇒ r is the greatest among elements p such that p ⋀ r precedes r in the ⊦ - order. A Heyting algebra is automatically a distributive lattice. We can adjoin, if the algebra doesn’t already have them, a least element ⊥ and a greatest element ⊤ with the rules ⊥ ⊦ p and p ⊦ ⊤. (⊤ is the “always true” proposition and ⊥ the “always false”.) Negation can then be defined by

¬p p ⇒ ⊥

p ⇒ ⊥ ¬p

(¬p is the greatest among elements q such that q ⋀ p ⊦ ⊥.)

This is not yet Russell’s logic. To get Russell’s logic we must add one more rule: ¬¬p ⊦ p (the converse is a consquence of the rules we already have). The result is a Boolean algebra, in which ¬p is the complement of p, that is, p ⋀ ¬p ⊦ ⊥ (which already holds in Heyting algebras) and 1 ⊦ p ⋁ ¬p. (From the definitions of ⊥ and ⊤ it follows that these are in fact equivalences (i.e. the ⊦ can be reversed in each of them.)

Note that if we consider ¬ to be an operation, then ¬¬ is just the identity operation, the operation that “leaves everything as it is”. In general an operation φ such that φφ (or φ2) is the identity is called an involution. Involutions are ubiquitous in mathematics: we have –(–x) = x, 1/(1/x) = x (for nonzero x; in geometry, reflection around an axis (“mirroring”) is an involution.

Consider now how the Boolean algebra was arrived at. We started with

an order,

added rules to make it

a (distributive) lattice,

further rules to make it

a Heyting algebra,

and finally one last rule (double negation) to make it

a Boolean algebra.

The only rules that don’t have noteworthy counterparts elsewhere in mathematics are the rules for ⇒; but the definition of ⇒ exhibits it as an instance of a very common phenomenon in category theory: ⇒ is adjoint to ⋀ (see Pedicchio & Tholen 24).

Given two orders A and B, an adjunction from A to B is a pair of order-preserving maps f: A → B and g: B → A such that for all x in A and all y in B,

fx ≤ y in B iff

x ≤ gy in B.

In the case of ⋀ and ⇒, the maps are

f = (— ⋀ q): L → L

and

g = (q ⇒ —): L → L,

where L is the collection of well-formed terms ordered by ⊦.

You might say that ⇒ is what distinguishes “logical” algebras from algebras generally; ⇒ is an “internalization” of ⊦, in the sense that p ⊦ q iff ⊤ ⊦ (p ⇒ q). (This holds because p ⊦ q iff ⊤⋀ p ⊦ q iff ⊤ ⊦ p ⇒ q.) It’s worth noting that ⊥,⊤, ⋀, ⋁ can also be construed as adjoints (P & T 18).

The logician may have good reasons to write as few rules as possible using as few operations as possible. The arguments by induction used to prove soundness and completeness are shorter if you economize on primitives and rules. But connections between logics and similar structures elsewhere in mathematics may well be lost if an axiom system is designed to that end. There is a payoff even for the logician in presenting Boolean algebras (and so also Boolean logics) as a progression of structures (or, equivalently, as inhabiting a succession of categories, each with significant relations to its neighbors).

Significant relations: Within the category of simple inference systems, the subcategory of those which have least upper and greatest lower bounds is an “image” of the category of ⋀,⋁-logics. Within the category of distributive ⋀,⋁-logics, the subcategory of those that have arbitrary joins (infinitary disjunctions) is an “image” of the category of Heyting algebras.

The order is a simple “inference” logic (transitivity is, if memory serves, a rudimentary “cut” rule). The lattice is a negationless logic. Heyting algebras are models for intuitionistic logic, and Boolean algebras of course for classical logic, which is thus situated in a spectrum of logics.

Russell mentions the work of Jean Nicod, who following Sheffer reduced the propositional connectives to a single one (the “Sheffer stroke” p|q meaning “not-p or not-q”) and the axioms of Russell and Whitehead’s Principia to a single axiom

(p|(q|r))|((t|(t|t))|((s|q)|((p|s)|(p|s)))

See Russell Introduction 152; the original source is “A Reduction in the Number of Primitive Propositions of Logic”, Proceedings of the Cambridge Philosophical Society 19 (1917-20): 32-41.

Whatever one may think of this as an instance of economy, mathematically it is opaqueness itself. Nothing could be further from the aim of mathematicians in defining their concepts, which not the economy of minimizing axioms or symbols, but one of naturalness, universality, and richness. Concepts often can be defined in a variety of ways; a theory may have any number of “generating sets” from which its theorems can be demonstrated. The determination of axioms is driven by the interest of the structures picked out by them. In that sense structures are prior to axioms even if knowledge of truths about those structures consists (at least in principle) in proof from axioms.

Locales

The subject of the second and third chapters of Foundations is topology. As always, the point of view is categorical. Chapter II, by Jorge Picado, Aleš Pultr, and Anna Tozzi, is on locales, which are a special sort of lattice.

Topology began as, and still is, a heterogeneous branch of mathematics. Its beginnings lie, on the one hand, in the set theory of Cantor and the limit concepts of analysis, and on the other hand, in the algebraic treatment of figures either themselves discrete, like the polyhedra of Euler’s theorem (which was already known to Descartes) or which have discrete surrogates, like the surfaces of Möbius and Klein, which can be “triangulated” and thus treated as if they were polyhedra too. Topology of the first sort was called “point-set” or “general” topology; topology of the other was called “algebraic”.

Point-set topology was mature by the 1930s. With the exception of paracompactness, almost all the basic concepts had been defined, and a body of theorems based on them supplied the content for introductory courses—the “common knowledge” working mathematicians were supposed to have (see Steen and Seebach Counterexamples for a history of the basic concepts in relation to the metrizability of spaces).

In point-set topology a space is defined in terms of a base set and a collection of its subsets called the opens of that space. (The elements of the base set are called points.) The collection of opens satisfies certain simple conditions: the empty set and the base set are open; a finite intersection of opens is open; any union of opens is open. These conditions and the properties of union and intersection in the category of sets make the collection of opens a lattice (lattices will be defined below). For any base set, the collection consisting only in that set itself and the empty set is satisfies the conditions, and is therefore a topology, known as the indiscrete topology.

At the opposite extreme…

At the opposite extreme from indiscrete spaces are (naturally enough) discrete spaces. The collection of all subsets of the base set also satisfies the conditions for opens. A base set together with its “power set”—the set of all its subsets—is called a discrete space, because it has, intuitively speaking, as many “pieces” as it has points. Discrete spaces are isomorphic as spaces only if they are isomorphic as sets. There is essentially one countable discrete space, and so on. The theory of discrete spaces is just the theory of sets. In the Gallery, the second figure is the lattice of opens of the discrete 2-point space, and the fourth is the lattice of opens of the discrete 3-point space.

In the 50s and 60s it became apparent that in some contexts only the lattice structure matters; the point-structure is irrelevant. All indiscrete spaces, however many points they contain, have the same lattice structure: it is the 2-object lattice 2 defined above. They fail to be “abstractly the same”, that is, isomorphic in the category of spaces, only because they differ in the cardinality of their base sets. This, you might say, is not really a topological but a set-theoretical property, just as absolute size, unlike relative size, is not really a property of Euclid’s circles and triangles.

If we abstract from the point structure of a space, and consider only its opens, ordered by inclusion, the result is a lattice which has finite meets but infinite joins (corressponding to the arbitrary unions mentioned in the conditions on opens)—a “join-complete” lattice. The meet “distributes” over the join: for all opens x and all collections of opens S,

x ⋀ ∨{y | y ∈ S} = ∨{x ⋀ y | y ∈ S}

In short, the opens of a space are a “distributive 0,1,⋀,∨-lattice”. Such lattices are called frames. Every finite distributive lattice is join-complete (but not every finite lattice is distributive: the third figure in the Gallery is an example).

We start with a space defined as a set with structure (the lattice of open subsets). We throw away the set and consider only the lattice, which is of course a frame. Can we then recover the set? Just from considering indiscrete spaces, it is clear that the answer is no. The lattice of open subsets of an indiscrete space, whatever its base set, is just the two element lattice 2. What has gone wrong? If the entire base set is the only nonempty open, we can’t distinguish the points of that set by reference to the lattice of opens. There aren’t enough of them.

At this point I must wave my hands a little. The natural definition of a “morphism of frames” is just the notion inherited from their definition as orders (i.e. as categories of a certain sort) or as lattices. A morphism of frames is an order-morphism. But to make frames look like spaces, you must consider not the category of frames and order-morphisms, but rather the opposite of that category, which has the same objects and arrows, but in which the sources and targets are reversed (see the more precise definition given earlier). This new category is called the category of locales.

Here’s a bit of motivation…

Here’s a bit of motivation. In spaces, the one-point space (whose topology is automatically the indiscrete topology) is the “terminal object”. For every space there is exactly one map to the one-point space. Considered as a frame, the topology of the one-point space is 2 (the first figure in the Gallery). 2 is not the terminal object in the category of frames. That, as we have seen, is the frame ∗ with one object and one arrow. On the other hand, 2 is the initial object in the category of frames. A frame morphism f : 2 → L has to preserve the least element 0 and the greatest element 1, which means that the 0 and 1 of 2 are automatically assigned to the 0 and 1 of L.

If we want to pick out, using a map, a point of a space, we can do so by mapping the one-point space to that point. By analogy, if we want to pick out, using a frame morphism, a “point” of a frame L,

A “point” of the frame 2 × 2 × 2. The right-hand object is the frame 2, the left-hand object is the lattice of subsets of a three-point set, which is the discrete topology on that set.

it would make sense to use a morphism from L to 2. That in fact turns out to be the way to do so—that is, the analogy works. The collection of “points” of a space, when its opens are treated as a frame, is isomorphic as a set (if the space is a well-behaved one in which points can be distinguished by opens) to the base set of that space.

A space whose points can be distinguished by its opens is called sober. Sobriety is a elementary property of spaces. In the category of frames there is likewise an elementary property that distinguishes “spatial” frames. The theorem relating those two properties can be taken to show just when two intuitive conceptions of space, each with a long history, coincide.

The first is the conception of a space as consisting of parts. In Scholastic treatments of quantity, extensio, the property by virtue of which a body “occupies space”—by virtue of which it has measurable dimensions, is divisible, and has modes of the sort we call surfaces, edges, and corners—is defined as “having partes extra partes”, “parts outside parts”, where ‘outside’ at least means “distinct”.

The second intuitive conception is of space as a collection of dimensionless points. It was rejected by Aristotle but implicit, for example, in the point-by-point construction of non-algebraic curves like the quadratrix. Not until the nineteenth century did anyone understood rigorously how to construct lines, surfaces, and volumes from points; but despite the apparent paradoxes arising from this conception it persisted. In the twentieth century it became predominant.

A space S is disconnected iff there exist opens u and v such that u ⋀ v = 0 (the empty set) and u ⋁ v = 1 (the entire space S) in its lattice of opens. In this case the opens u and v are called components.

A space is totally disconnected if every point is a component. The connection with Boolean algebras becomes more evident if you think of v in the situation above as the “negation” ¬u of u. If points are components, then every open u of S has a negation ¬u which satisfies the axioms for negation in classical logic.

To define the Cantor set, consider a line segment. Label its endpoints 0 and 1. Now divide it into thirds. Throw away the middle third, leaving, however, its endpoints 1/3, 2/3. From the two segments that remain remove their middle thirds, again leaving the endpoints. From the four segments that remain, remove their middle thirds. And so forth. What remains is a set of points corresponding to the numbers x1/3 + x2/32 + x3/33 + x4/34 + … where each xi is either 0 or 2. See Mathworld, Wikipedia, and cut-the-knot for more.

Consider the relation between the “points” of a frame (or locale) and its opens. Write “x ⊧ u” for this relation. In spatial locales it can be interpreted as set-membership, but not in general. The relation satisfies in all locales the axioms not of classical, but of constructive logic (with finite conjunctions and arbitrary disjunctions: see Vickers for the details). The logic of spaces is classical (or Boolean) only in spaces where the (set-theoretical) complement of an open is itself open. A theorem of Marshall H. Stone, proved in 1934, states that those spaces are the “totally disconnected” spaces (the Cantor set, with the topology it inherits as a subset of the real line, is an example; see Johnstone for proofs and a history of Stone’s theorem). What is remarkable in Stone’s work, according to Johnstone, is that “nobody had previously had the idea of applying these techniques”—the construction of spaces with specified topological properties—“to the study of spaces constructed from purely algebraic data” (xv). Stone’s theorem is an early instance of a phenomenon pervasive in mathematics: an equivalence of categories.

Questions

All I’ve mentioned here is the preliminaries to the first two chapters of Foundations. But that suffices to raise some philosophical questions.

1. Is the shift from point-set topology, where a space is a “set with structure”, to localic topology, where “having points” is an additional feature possessed by some but not all topologies, a conceptually significant change?

If we consider the lattice of opens to be a category, then the preeminence of the part-whole relation is an instance of the general injunction to consider objects only by way of their morphisms. That, as a number of authors have argued, a significant conceptual change even if categories can be modelled as sets. One indication that the concept has changed is the fact that “pointless”locales exist (see Johnstone, “The point of…” and “The art of…” for details). Locales are more general than spaces; but not just any generalization is fruitful.

2. What is the epistemological role of the concept of space—in either the point-set or the localic formulation? The realization that in certain settings (sheaf theory, for example, which is the topic of chapter VII in Foundations) only the lattice-theoretic properties of a space are relevant was one of the motivations behind the replacement of spaces with locales. That suggests a maxim (in the spirit of Maddy’s “Maximize” for large cardinal theory): “don’t import more structure than you need into your objects”. What is the benefit of following such a maxim? I don’t think questions like this can be answered, any more than in the other sciences, except by reference to practice.

Johnstone, Peter T. “The Art of pointless thinking: a student's guide to the category of locales”. In: Category Theory at Work (Heldermann, 1991):85–107.

Johnstone, Peter T. “The point of pointless topology”. Bull. Amer. Math. Soc. (N.S.) 8(1983):41–53.

Johnstone, Peter T. Stone spaces. Cambridge: Cambridge University Press, 1982. (Cambridge studies in advanced mathematics, 3)

Lambek, J. and P. J. Scott. Introduction to higher order categorical logic. Cambridge: Cambridge University Press, 1986. (Cambridge studies in advanced mathematics, 7)

Picado, Jorge. Weil Entourages in Pointfree Topology. Ph. D. Thesis, Departamento de Matemática, Universidade de Coimbra, 1995. (The introduction is available online.)

Steen, Lynn Arthur, and J. Arthur Seebach, Jr. Counterexamples in topology. Mineola, New York: Dover, 1995 (reprint of the 2nd ed., 1978).

Vickers, Steven. “Topology via constructive logic”. http://www.cs.bham.ac.uk/~sjv/tvcl.ps (postscript). Other formats at Citeseer (or the MIT mirror).

Vickers, Steven. Topology via logic. Cambridge: Cambridge University Press, 1989. (Cambridge tracts in theoretical computer science, 6)