Connected components in a distributive category

Previously we claimed that if you want to check whether a category “behaves like a category of spaces,” you can try checking whether it’s distributive. The goal of today’s post is to justify the assertion that objects in distributive categories behave like spaces by showing that they have a notion of “connected components.”

For starters, let be a distributive category with terminal object , and let be the coproduct of two copies of . For an object , what does look like? If and is a sufficiently well-behaved topological space, morphisms correspond to subsets of the connected components of , and naturally has have the structure of a Boolean algebra or Boolean ring whose elements can be interpreted as subsets of the connected components of .

It turns out that naturally has the structure of a Boolean algebra or Boolean ring (more invariantly, the structure of a model of the Lawvere theory of Boolean functions) in any distributive category. Hence any distributive category naturally admits a contravariant functor into Boolean rings, or, via Stone duality, a covariant functor into profinite sets / Stone spaces. This is our “connected components” functor. When the object this functor outputs is known as the Pierce spectrum.

This construction can be thought of as trying to do for what the étale fundamental group does for .

Read Full Post »

The Lawvere theory of Boolean functions

Let be a set with two elements. The category of Boolean functions is the category whose objects are the finite powers of and whose morphisms are all functions between these sets. For a computer scientist, the morphisms of this category have the interpretation of functions which input and output finite sequences of bits.

Since this category has finite products and is freely generated under finite products by a single object, namely , it is a Lawvere theory.

Question: What are models of this Lawvere theory?

Read Full Post »

How to invent intuitionistic logic

(This is an old post I never got around to finishing. It was originally going to have a second half about pointless topology; the interested reader can consult Vickers’ Topology via Logic on this theme.)

Standard presentations of propositional logic treat the Boolean operators “and,” “or,” and “not” as fundamental (e.g. these are the operators axiomatized by Boolean algebras). But from the point of view of category theory, arguably the most fundamental Boolean operator is “implies,” because it gives a collection of propositions the structure of a category, or more precisely a poset. We can endow the set of propositions with a morphism whenever , and no morphisms otherwise. Then the identity morphisms simply reflect the fact that a proposition always implies itself, while composition of morphisms

is a familiar inference rule (hypothetical syllogism). Since it is possible to define “and,” “or,” and “not” in terms of “implies” in the Boolean setting, we might want to see what happens when we start from the perspective that propositional logic ought to be about certain posets and figure out how to recover the familiar operations from propositional logic by thinking about what their universal properties should be.

It turns out that when we do this, we don’t get ordinary propositional logic back in the sense that the posets we end up identifying are not just the Boolean algebras: instead we’ll get Heyting algebras, and the corresponding notion of logic we’ll get is intuitionistic logic.

Read Full Post »

Cartesian closed categories and the Lawvere fixed point theorem

Previously we saw that Cantor’s theorem, the halting problem, and Russell’s paradox all employ the same diagonalization argument, which takes the following form. Let be a set and let

be a function. Then we can write down a function such that . If we curry to obtain a function

it now follows that there cannot exist such that , since .

Currying is a fundamental notion. In mathematics, it is constantly implicitly used to talk about function spaces. In computer science, it is how some programming languages like Haskell describe functions which take multiple arguments: such a function is modeled as taking one argument and returning a function which takes further arguments. In type theory, it reproduces function types. In logic, it reproduces material implication.

Today we will discuss the appropriate categorical setting for understanding currying, namely that of cartesian closed categories. As an application of the formalism, we will prove the Lawvere fixed point theorem, which generalizes the argument behind Cantor’s theorem to cartesian closed categories.

Read Full Post »

Cantor’s theorem, the prisoner’s dilemma, and the halting problem

Cantor’s theorem is somewhat infamous as a mathematical result that many non-mathematicians have a hard time believing. Trying to disprove Cantor’s theorem is a popular hobby among students and cranks; even Eliezer Yudkowsky₁₉₉₃ fell into this trap once. I think part of the reason is that the standard proof is not very transparent, and consequently is hard to absorb on a gut level.

The goal of this post is to present a rephrasing of the statement and proof of Cantor’s theorem so that it is no longer about sets, but about a particular kind of game related to the prisoner’s dilemma. Rather than showing that there are no surjections , we will show that a particular kind of player in this game can’t exist. This rephrasing may make the proof more transparent and easier to absorb, although it will take some background material about the prisoner’s dilemma to motivate. As a bonus, we will almost by accident run into a proof of the undecidability of the halting problem.

Read Full Post »

Ultrafilters in Ramsey theory

We continue our exploration of ultrafilters. Today we’ll discuss the infinite Ramsey theorem, which is the following classical result:

Theorem: Suppose the complete graph on countably many vertices has its edges colored in one of colors. Then there is a monochromatic (i.e. an infinite subgraph all of whose edges are the same color).

The finite Ramsey theorem implies that there is a monochromatic for every positive integer , but this is a strictly stronger result; it implies not only the finite Ramsey theorem but the “strengthened” finite Ramsey theorem, and by the Paris-Harrington theorem this is independent of Peano arithmetic (although Peano arithmetic can prove the finite Ramsey theorem). Indeed, while the standard proof of the finite Ramsey theorem uses the finite pigeonhole principle, the standard proof of the infinite Ramsey theorem uses the infinite pigeonhole principle, which is stronger; this is part of the subject of a post by Terence Tao which is quite enlightening.

Given a non-principal ultrafilter on , any partition of into finitely many disjoint subsets (that is, any coloring) has the property that exactly one of the subsets is in (that is, has “full measure”), and this subset must be infinite. This subset can, in turn, be colored (partitioned), and exactly one of the blocks of the partition is in , and it must again be infinite, and so forth. It follows that a non-principal ultrafilter lets us use the infinite pigeonhole principle repeatedly (in fact this is in some sense what a non-principal ultrafilter is), and since this is exactly what is needed to prove the infinite Ramsey theorem we might expect that we could use a non-principal ultrafilter to prove the infinite Ramsey theorem. Today we’ll describe this proof, and then describe how the infinite Ramsey theorem implies the finite Ramsey theorem, which involves a different use of a non-principal ultrafilter on .

Read Full Post »

Ultrafilters in topology

Remark: To forestall empty set difficulties, whenever I talk about arbitrary sets in this post they will be non-empty.

We continue our exploration of ultrafilters from the previous post. Recall that a (proper) filter on a poset is a non-empty subset such that

1. For every , there is some such that .
2. For every , if then .
3. is not the whole set .

If has finite infima (meets), then the first condition, given the second, can be replaced with the condition that if then . (This holds in particular if is the poset structure on a Boolean ring, in which case .) A filter is an ultrafilter if in addition it is maximal under inclusion among (proper) filters. For Boolean rings, an equivalent condition is that for every either or , but not both. Recall that this condition tells us that ultrafilters are precisely complements of maximal ideals, and can be identified with morphisms in . If for some set , then we will sometimes call an ultrafilter on an ultrafilter on (for example, this is what people usually mean by “an ultrafilter on “).

Today we will meander towards an ultrafilter point of view on topology. This point of view provides, among other things, a short, elegant proof of Tychonoff’s theorem.

Read Full Post »

Boolean rings, ultrafilters, and Stone’s representation theorem

Recently, I have begun to appreciate the use of ultrafilters to clean up proofs in certain areas of mathematics. I’d like to talk a little about how this works, but first I’d like to give a hefty amount of motivation for the definition of an ultrafilter.

Terence Tao has already written a great introduction to ultrafilters with an eye towards nonstandard analysis. I’d like to introduce them from a different perspective. Some of the topics below are also covered in these posts by Todd Trimble.

Read Full Post »