Feeds:
Posts

## 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 $p \to q$ whenever $p \Rightarrow q$, and no morphisms otherwise. Then the identity morphisms $\text{id}_p : p \to p$ simply reflect the fact that a proposition always implies itself, while composition of morphisms

$\displaystyle (p \Rightarrow q) \wedge (q \Rightarrow r) \to (p \Rightarrow r)$

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.

## 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 $P$ is a non-empty subset $F$ such that

1. For every $x, y \in F$, there is some $z \in F$ such that $z \le x, z \le y$.
2. For every $x \in F$, if $x \le y$ then $y \in F$.
3. $P$ is not the whole set $F$.

If $P$ has finite infima (meets), then the first condition, given the second, can be replaced with the condition that if $x, y \in F$ then $x \wedge y \in F$. (This holds in particular if $P$ is the poset structure on a Boolean ring, in which case $x \wedge y = xy$.) 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 $x \in B$ either $x \in F$ or $1 - x \in F$, but not both. Recall that this condition tells us that ultrafilters are precisely complements of maximal ideals, and can be identified with morphisms in $\text{Hom}_{\text{BRing}}(B, \mathbb{F}_2)$. If $B = \text{Hom}(S, \mathbb{F}_2)$ for some set $S$, then we will sometimes call an ultrafilter on $B$ an ultrafilter on $S$ (for example, this is what people usually mean by “an ultrafilter on $\mathbb{N}$“).

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.

## 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.

## Functoriality

I wanted to talk about the geometric interpretation of localization, but before I do so I should talk more generally about the relationship between ring homomorphisms on the one hand and continuous functions between spectra on the other. This relationship is of utmost importance, for example if we want to have any notion of when two varieties are isomorphic, and so it’s worth describing carefully.

The geometric picture is perhaps clearest in the case where $X$ is a compact Hausdorff space and $C(X) = \text{Hom}_{\text{Top}}(X, \mathbb{R})$ is its ring of functions. From this definition it follows that $C$ is a contravariant functor from the category $\text{CHaus}$ of compact Hausdorff spaces to the category $\mathbb{R}\text{-Alg}$ of $\mathbb{R}$-algebras (which we are assuming have identities). Explicitly, a continuous function

$f : X \to Y$

between compact Hausdorff spaces is sent to an $\mathbb{R}$-algebra homomorphism

$C(f) : C(Y) \to C(X)$

in the obvious way: a continuous function $Y \to \mathbb{R}$ is sent to a continuous function $X \xrightarrow{f} Y \to \mathbb{R}$. The contravariance may look weird if you’re not used to it, but it’s perfectly natural in the case that $f$ is an embedding because then one may identify $C(X)$ with the restriction of $C(Y)$ to the image of $f$. This restriction takes the form of a homomorphism $C(Y) \to C(X)$ whose kernel is the set of functions which are zero on $f(X)$, so it exhibits $C(X)$ as a quotient of $C(Y)$.

Question: Does every $\mathbb{R}$-algebra homomorphism $C(Y) \to C(X)$ come from a continuous function $X \to Y$?

## Irreducible components

If it wasn’t clear, in this discussion all rings are assumed commutative.

Given a variety like $xy = 0$ we’d like to know if there’s a natural way to decompose it into its “components” $x = 0, y = 0$. These aren’t its connected components in the topological sense, but in any reasonable sense the two parts are unrelated except possibly where they intersect. It turns out that the Noetherian condition is a natural way to answer this question. In fact, we will see that the Noetherian condition allows us to write $\text{MaxSpec } R$ uniquely as a union of a finite number of “components” which have a natural property that is stronger than connectedness.

## The Noetherian condition as compactness

Let’s think more about what an abstract theory of unique factorization of primes has to look like. One fundamental property it has to satisfy is that factorizations should be finite. Another way of saying this is that the process of writing elements as products of other elements (up to units) should end in a finite set of irreducible elements at some point. This condition is clearly not satisfied by sufficiently “large” commutative rings such as $\mathbb{C}[x, x^{ \frac{1}{2} }, x^{ \frac{1}{3} }, ... ]$, the ring of fractional polynomials.

Since we know we should think about ideals instead of numbers, let’s recast the problem in a different way: because we can write $x^{r} = x^{ \frac{r}{2} } x^{ \frac{r}{2} }$ for any $r$, the ascending chain of ideals $(x) \subset (x^{ \frac{1}{2} }) \subset (x^{ \frac{1}{4} }) \subset ...$ never terminates. In any reasonable theory of factorization writing $f = f_1 g_1$ and then comparing the ideals $(f) \subset (f_1)$, then repeating this process to obtain a chain of ideals $(f) \subset (f_1) \subset (f_2) \subset ...$, should eventually stabilize at a prime. This leads to the following definition.

Definition: A commutative ring $R$ is Noetherian if every ascending chain of ideals stabilizes.

Akhil’s posts at Delta Epsilons here and here describe the basic properties of Noetherian rings well, including the proof of the following.

Hilbert’s Basis Theorem: If $R$ is a Noetherian ring, so is $R[x]$.

Today we’ll discuss what the Noetherian condition means in terms of the topology of $\text{MaxSpec}$. The answer turns out to be quite nice.

An analyst thinks of the ring $\mathbb{C}[ t]$ of polynomials as a useful tool because, on intervals, it is dense in the continuous functions $\mathbb{R} \to \mathbb{C}$ in the uniform topology. If we want to understand the relationship between $\mathbb{Z}$ and polynomial rings in a more general context, it might pay off to expand our scope from polynomial rings to more general types of well-behaved rings.
The rings we’ll be considering today are the commutative rings $C( X) = \text{Hom}_{\text{Top}}(X, \mathbb{R})$ of real-valued continuous functions $X \to \mathbb{R}$ on a topological space $X$ with pointwise addition and multiplication. It turns out that one can fruitfully interpret ring-theoretic properties of this ring in terms of topological properties of $X$, and in certain particularly nice cases one can completely recover the space $X$. Although the relevance of these rings to number theory seems questionable, the goal here is to build geometric intuition. You can consider this post an extended solution to Exercise 26 in Chapter 1 of Atiyah-Macdonald.