This is either going to be the first installment of a long running series or something I will never do again. (We'll see, don't know yet.)
Like the name suggests each iteration will showcase a theorem with its proof, all in one picture. I will provide preliminaries and definitions, as well as some execises so you can test your understanding. (Answers will be provided below the break.)
The goal is to ease people with some basic knowledge in mathematics into set theory, and its categorical approach specifically. While many of the theorems in this series will apply to topos theory in general, our main interest will be the topos Set. I will assume you are aware of the notations of commutative diagrams and some terminology. You will find each post to be very information dense, don't feel discouraged if you need some time on each diagram. When you have internalized everything mentioned in this post you have completed weeks worth of study from a variety of undergrad and grad courses. Try to work through the proof arrow by arrow, try out specific examples and it will become clear in retrospect.
Please feel free to submit your solutions and ask questions, I will try to clear up missunderstandings and it will help me designing further illustrations. (Of course you can just cheat, but where's the fun in that. Noone's here to judge you!)
Preliminaries and Definitions:
B^A is the exponential object, which contains all morphisms A→B. I comes equipped with the morphism eval. : A×(B^A)→B which can be thought of as evaluating an input-morphism pair (a,f)↦f(a).
The natural isomorphism curry sends a morphism X×A→B to the morphism X→B^A that partially evaluates it. (1×A≃A)
φ is just some morphism A→B^A.
Δ is the diagonal, which maps a↦(a,a).
1 is the terminal object, you can think of it as a single-point set.
We will start out with some introductory theorem, which many of you may already be familiar with. Here it is again, so you don't have to scroll all the way up:
Exercises:
What is the statement of the theorem?
Work through the proof, follow the arrows in the diagram, understand how it is composed.
What is the more popular name for this technique?
What are some applications of it? Work through those corollaries in the diagram.
Can the theorem be modified for epimorphisms? Why or why not?
For the advanced: What is the precise requirement on the category, such that we can perform this proof?
For the advanced: Can you alter the proof to lessen this requirement?
Bonus question: Can you see the Sicko face? Can you unsee it now?
Expand to see the solutions:
Solutions:
This is Lawvere's Fixed-Point Theorem. It states that, if there is a point-surjective morphism φ:A→B^A, then every endomorphism on B has a fixed point.
Good job! Nothing else to say here.
This is most commonly known as diagonalization, though many corollaries carry their own name. Usually it is stated in its contraposition: Given a fixed-point-less endomorphism on B there is no surjective morphism A→B^A.
Most famous is certainly Cantor's Diagonalization, which introduced the technique and founded the field of set theory. For this we work in the category of sets where morphisms are functions. Let A=ℕ and B=2={0,1}. Now the function 2→2, 0↦1, 1↦0 witnesses that there can not be a surjection ℕ→2^ℕ, and thus there is more than one infinite cardinal. Similarly it is also the prototypiacal proof of incompletness arguments, such as Gödels Incompleteness Theorem when applied to a Gödel-numbering, the Halting Problem when we enumerate all programs (more generally Rice's Theorem), Russells Paradox, the Liar Paradox and Tarski's Non-Defineability of Truth when we enumerate definable formulas or Curry's Paradox which shows lambda calculus is incompatible with the implication symbol (minimal logic) as well as many many more. As in the proof for Curry's Paradox it can be used to construct a fixed-point combinator. It also is the basis for forcing but this will be discussed in detail at a later date.
If we were to replace point-surjective with epimorphism the theorem would no longer hold for general categories. (Of course in Set the epimorphisms are exactly the surjective functions.) The standard counterexample is somewhat technical and uses an epimorphism ℕ→S^ℕ in the category of compactly generated Hausdorff spaces. This either made it very obvious to you or not at all. Either way, don't linger on this for too long. (Maybe in future installments we will talk about Polish spaces, then you may want to look at this again.) If you really want to you can read more in the nLab page mentioned below.
This proof requires our category to be cartesian closed. This means that it has all finite products and gives us some "meta knowledge", called closed monoidal structure, to work with exponentials.
Yanofsky's theorem is a slight generalization. It combines our proof steps where we use the closed monoidal structure such that we only use finite products by pre-evaluating everything. But this in turn requires us to introduce a corresponding technicallity to the statement of the theorem which makes working with it much more cumbersome. So it is worth keeping in the back of your mind that it exists, but usually you want to be working with Lawvere's version.
Yes you can. No, you will never be able to look at this diagram the same way again.
We see that Lawvere's Theorem forms the foundation of foundational mathematics and logic, appears everywhere and is (imo) its most important theorem. Hence why I thought it a good pick to kick of this series.
If you want to read more, the nLab page expands on some of the only tangentially mentioned topics, but in my opinion this suprisingly beginner friendly paper by Yanofsky is the best way to read about the topic.
Following F. William Lawvere, we show that many self-referential paradoxes, incompleteness theorems and fixed point theorems fall out of the
Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.
✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality
Anya is LIVE right now
FREE
Free to watch • No registration required • HD streaming
There is a contravariant* equivalence between the category of Boolean algebras and Boolean homomorphisms and the category of Stone spaces and continuous maps. There is a contravariant equivalence between the category of complete Boolean algebras and complete Boolean homomorphisms and the category of Stonean spaces and open continuous maps.
*One category is equivalent to the opposite of the other.
I recommend reading my blog post Hausdorff Spaces for the prerequisites relating to topology. If you're already familiar with topology, you don't need to read it.
If you want to know what an equivalence of categories is, I recommend searching it up on the internet or reading the relevant chapters in my blog-posts Monad and T-Algebra. The relevant chapters of Monad are Category, Functor, Natural Transformation. The relevant chapter of T-Algebra is Equivalent Categories.
Boolean Algebra
A pre-order is a set P along with a binary relation ≤ on P satisfying:
Reflexivity a ≤ a;
Transitivity If a ≤ b and b ≤ c, then a ≤ c.
A partial order is a pre-order further satisfying:
3. Antisymmetry If a ≤ b and b ≤ a then a = b.
Elements a,b of a pre-order are equivalent, denoted a ≡ b, iff a ≤ b and b ≤ a. For a pre-order P, P/≡ is a partial order and P is uniquely determined by the ordering on P/≡ and the sizes of equivalence classes.
An example of a partial order is the powerset P(X) of a set X with the inclusion order a ≤ b iff a ⊂ b.
We write a < b iff a ≤ b and not b ≤ a. We say a and b are comparable, denoted a||b, iff a ≤ b or b ≤ a.
Let P be a pre-order. For a set A ⊂ P and an element x ∈ P, we say x is a
upper-bound of A, denoted A ≤ x, iff ∀a ∈ A. a ≤ x;
lower-bound of A, denoted x ≤ A, iff ∀a ∈ A. x ≤ a;
greatest element of A iff x ∈ A and A ≤ x;
least element of A iff x ∈ A and x ≤ A;
supremum/join of A iff x is a least upper-bound;
infimum/meet of A iff x is a greatest lower-bound.
Suprema and infima are unique up to equivalence, therefore unique in partial orders. Not all sets have a supremum or infimum. If a set A in a partial order has a join, we write it as ⋁A, and if it has a meet, we write it as ⋀A. We write a ∨ b for ⋁{a,b}, a ∧ b for ⋀{a,b}, ⊥ for ⋁{} and ⊤ for ⋀{}. The element ⊥, if it exists, is the least element of P and is called the bottom element. Conversely, ⊤ is called the top element.
For example, the meet of two elements in P(X) is their intersection and their join is their union.
A partial order is a:
lattice iff it has binary meets and joins;
bounded lattice iff it has finite (nullary and binary) meets and joins;
complete lattice iff it has all meets and joins.
P(X) is an example of a complete lattice, the set of finite and cofinite (complement of finite) subsets of ℕ is a bounded lattice and the set of infinite subsets of ℕ is a lattice. The set of partial functions ℕ -> ℕ ordered under function extension is not a lattice.
An ordering having all meets implies it has all joins, and vice-versa. This is because, if P has all meets, then the join of a set A is the meet of the set of its upper-bounds.
Elements a and b of a bounded lattice are complements iff a ∧ b = ⊥ and a ∨ b = ⊤. A complemented lattice is a bounded lattice where every element has a complement.
An example of a complement lattice is the diamond lattice, with five elements {⊥, a, b, c, ⊤}. We have ⊥ < a,b,c < ⊤, and any three elements of {a,b,c} is incomparable with any other. In this lattice, ⊥ and ⊤ are complements of eachother and every element of {a,b,c} is a complement to every other element of {a,b,c} (not itself).
A lattice is a distributive lattice iff one of the following equivalent statements holds:
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c);
a ∨ (b ∧ c) = (a ∨ c) ∧ (a ∨ c).
A Boolean algebra is a complemented distributive lattice. A complete Boolean algebra is a complemented complete distributive lattice. Complements in a Boolean algebra are unique and we write ¬a for the complement of an element a.
A Boolean algebra (B,≤) has an algebraic structure (B,∧,∨,¬,⊤,⊥). This structure satisfies:
Associativity (a ∧ b) ∧ c = a ∧ (b ∧ c) and (a ∨ b) ∨ c = a ∨ (b ∨ c);
Commutativity a ∧ b = b ∧ a and a ∨ b = b ∨ a;
Identity a ∧ ⊤ = a and b ∨ ⊥ = b;
Distributivity a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) and a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c);
Absorption a ∧ (a ∨ b) = a ∨ b and a ∨ (a ∧ b) = a ∧ b;
Complements a ∧ ¬a = ⊥ and a ∨ ¬a = ⊤.
Conversely, such a structure (B,∧,∨,¬,⊤,⊥) satisfying the above induces an ordering where a ≤ b iff one of the following equivalent statements holds:
a ∧ b = a;
a ∨ b = b.
With this ordering, (B,≤) is a Boolean algebra. These operations (turning the ordering into the algebraic structure and turning the algebraic structure into an ordering) are inverses of eachother, so we could also have defined a Boolean algebra as an algebraic structure (B,∧,∨,¬,⊤,⊥) satisfying the above six axioms. I'll refer to the first definition of a Boolean algebra as the order-theoretic definition, and the second as the algebraic definition.
We define the following operations on a Boolean algebra:
implication a -> b := b ∨ ¬a;
biimplication a ↔ b := (a -> b) ∧ (b -> a);
difference a - b := a ∧ ¬b;
symmetric difference a ⊕ b := (a - b) ∨ (b - a) = (a ∨ b) - (a ∧ b).
Stone Space
A topology is a set X along with a family τ of subsets of X satisfying:
τ is closed under finite (nullary and binary) intersections;
τ is closed under all unions.
The nullary intersection is taken to be the entire set X itself. Elements of τ are called open sets of the topology. Some examples are:
discrete topology every subset of X is open;
indiscrete topology the only open sets are ∅ and X;
usual topology on the reals the open subsets of ℝ are the unions of open intervals (a..b).
A cover of a set A is a family of sets F for which A ⊂ ⋃F. An open cover of a set A ⊂ X in a topology X is a family of open sets F that is also a cover of A. A subcover of a cover F of A is a subset G ⊂ F that is a cover of A.
A topology X is compact iff every open cover of X has a finite subcover. Equivalently, for every family F of closed sets, if every finite subfamily of F has a non-empty intersection, then F has a non-empty intersection.
A topology X is totally disconnected iff, for any two elements x,y in X, there is a clopen set C containing x but not y. Equivalently, there are disjoint open sets U and V for which x is in U, y is in V and U ∪ V = X. Conversely, X is connected iff it has exactly two clopen subsets (those must be ∅ and X).
Every totally disconnected space is Hausdorff (Hd), though the converse is not true. The usual topology on the reals is a counterexample.
A topology X is extremally disconnected iff the closure of any open set is open. Equivalently, the Heyting algebra of opens satisfies the weak law of excluded middle (wlem) ¬p ∨ ¬¬p. Every Hd extremally disconnected space is totally disconnected. The converse is not true, the one-point compactification of the natural number line ℕ̅ is a counter-example.
A Stone space is a compact and totally disconnected space. A Stonean space is an extremally disconnected Stone space, equivalently, an extremally disconnected compact Hausdorff space.
The Cantor space is an example of a Stone space. My blog post Cantor space and Baire space explains what the Cantor space is. In short, it is the product of a countable number of copies of {0,1} with the discrete topology. This results in a topology whose points are infinite binary sequences, and where the basic open sets are U_s = {x | x extends s} where s is a finite list of bits. Its sibling the Baire space is not a Stone space as it fails to be compact.
CLOP and RO
We fix a topology (X,τ).
A set is clopen iff it is both open and closed. Equivalently, it is open with an open complement. We write CLOP(X) for the set of clopen subsets of X.
The regular closure of a set A is the interior of its closure Reg(A) := int(cl(A)). A set is regular open iff it is equal to its regular closure. Equivalently, it is the interior of a closed set. We write RO(X) for the set of regular open subsets of X.
An example of an open set that is not regular open is (-1..0) ∪ (0..1) in the usual topology of the reals.
We have a chain of inclusions
CLOP(X) ⊂ RO(X) ⊂ O(X)
where O(X) = τ is the set of open subsets of X.
We have the following theorems:
Theorem. (CLOP(X),⊂) is a Boolean algebra.
Theorem. (RO(X),⊂) is a complete Boolean algebra.
I trust the reader can prove the first theorem on their own. As for the second theorem, here is a list of things you need to prove:
Show that RO(X) has a top and bottom element.
As the union of regular opens (-1..0) ∪ (0..1) is not itself regular open, binary join in RO(X) cannot be unions. For open U, show that Reg(U) is the smallest regular open set containing U. This implies that a ∨ b = Reg(a ∪ b) in RO(X).
The meet of two elements is included in both elements. Therefore, we must have a ∧ b ⊂ a ∩ b. However, by the point above, we already know that a ∩ b ⊂ Reg(a ∩ b). Therefore, you must show that Reg(a ∩ b) = a ∩ b for regular open a and b.
The exterior of a set A, denoted ext(A), is the interior of its complement, equivalently, the complement of its closure. Show that ext is a negation for RO(X). I.e. show that A ∩ ext(A) = ∅ and Reg(A ∪ ext(A)) = X for any set A (strictly speaking, you only need to prove this for regular open A, however, these equations are true for any set A), and show that ext(U) is regular open for any open U.
For open U and V, show that Reg(U ∩ V) = Reg(U) ∩ Reg(V). Use this to prove that RO(X) satisfies distributivity.
The join of a family F of regular open sets is very clearly just ⋁F = Reg(⋃F). However, just like with binary meets, we want that the meet of a family of regular opens is contained in every member of the family. Therefore, you need to prove that int(⋂F) is regular open for every family of regular opens F.
If you have followed all these steps, you have proven that RO(X) is a complete Boolean algebra. Well done!
The following is also useful:
X is extremally disconnected iff RO(X) = CLOP(X).
Boolean Homomorphisms and Ultrafilters
Let A and B be Boolean algebras. A Boolean homomorphism (morphism) from A to B is a function f: A -> B satisfying:
f(a ∧ b) = f(a) ∧ f(b);
f(a ∨ b) = f(a) ∨ f(b);
f(⊤) = ⊤;
f(⊥) = ⊥;
f(¬a) = ¬f(a).
Note: point 5 follows from 1-4.
A complete Boolean homomorphism is a Boolean homomorphism f: A -> B between complete Boolean algebras satisfying:
f(⋀X) = ⋀ f[X];
f(⋁X) = ⋁ f[X].
Here, f[X] = {f(x) | x ∈ X} denotes the image of X under f.
The category of Boolean algebras and Boolean homomorphisms is denoted Ba. The category of complete Boolean algebra and complete Boolean homomorphisms is denoted cBa. Note: cBa is not a full subcategory of Ba, i.e. there are homomorphisms of complete Boolean algebras that are not complete homomorphisms.
A filter on a Boolean algebra B is a set of Booleans F ⊂ B satisfying:
⊤ ∈ F;
upwards closed If a ≤ b and a ∈ F then b ∈ F;
downwards directed If a,b ∈ F then a ∧ b ∈ F.
A proper filter also satisfies ⊥ ∉ F. An ideal on a Boolean algebra B is a set of Booleans I ⊂ B satisfying:
⊥ ∈ I;
downwards closed If a ≤ b and b ∈ I then a ∈ I;
upwards directed If a,b ∈ I then a ∨ b ∈ I.
A proper ideal also satisfies ⊤ ∉ I. The set of complements of Booleans in a filter F is called its dual ideal and the set of complements of Booleans in an ideal I is called its dual filter. These operations are inverses of eachother.
Given a Boolean algebra B and an ideal I ⊂ B, we define a Boolean algebra B/I where Booleans are equivalence classes of Booleans in B under the equivalence relation a ~ b iff a ⊕ b ∈ I. We have a Boolean homomorphism q: B -> B/I that maps every Boolean in B to its equivalence class in B/I. This Boolean homomorphism is surjective and, conversely, every surjective Boolean homomorphism f: A -> B has a kernel ker(f) = {a ∈ A | f(a) = ⊥}. This kernel is an ideal in A for which A/ker(f) and B are isomorphic. Conversely, the kernel of the quotient map q: B -> B/I is the ideal I. Therefore, ideals in B correspond to surjective Boolean homomorphisms out of B.
Using the same idea, we can define a Boolean algebra B/F for every Boolean algebra B and filter F on B.
An ultrafilter on a Boolean algebra B is a proper filter u on B satisfying one of the following equivalent statements:
For every Boolean a, we have a ∈ u or (¬a) ∈ u;
B/u is a two-element Boolean algebra;
If a ∨ b ∈ u then a ∈ u or b ∈ u.
It is left to the reader to prove these three statements are equivalent. The dual to an ultrafilter is called a prime ideal or maximal ideal.
St
Let B be a Boolean algebra. The Stone space St(B) of B is a topology. Points of St(B) are ultrafilters on B. Further, for every Boolean a in B, there is a basic open set
U_a = {u ∈ St(B) | a ∈ u}
The open sets are the unions of basic open sets.
The name suggests that the Stone space of a Boolean algebra is a Stone space, i.e. is compact and totally disconnected. We leave proving St(B) is totally disconnected to the reader. What might help is proving that the basic open sets are clopen. I give a proof that St(B) is compact below.
Lemma. Let B be a Boolean algebra and let F be a proper filter on B. Then, there is an ultrafilter u on B extending F (i.e. for which F ⊂ u). Further, F is the intersection of all ultrafilters that extend it.
Proof. We use Zorn's lemma. Let P be the set of proper filters on B ordered under inclusion. Let C ⊂ P be a chain in P, i.e. a set of pairwise comparable proper filters. Then, the union ⋃C of all filters in C is easily seen to also be a proper filter on B. This union is an upper-bound for C, so this shows that P is an inductive poset. Zorn's lemma states that every element of an inductive poset has an extension to a maximal element. Therefore, we can extend the filter F to an ultrafilter u, proving the first half of the lemma.
Let a be a Boolean not in F. We want to show that there is an ultrafilter u extending F that does not contain a. We define the filter G as follows:
G = {c ∈ B | ∃b ∈ F. b - a ≤ c}
Clearly, ⊤ ∈ G. Further, G is upwards closed by transitivity of ≤. If c,d ∈ G, then we can find b,b' ∈ F for which b - a ≤ c and b' - a ≤ d. Then, as b ∧ b' ∈ F and (b ∧ b') - a ≤ c ∧ d, we have that c ∧ d ∈ G. If ⊥ were to be in G, then there is some b in F for which b - a ≤ ⊥. This can only happen if b ≤ a, implying a ∈ F, a contradiction. So, ⊥ is not in G. Therefore, G is a proper filter. Further, we have ⊤ - a ≤ ¬a and therefore (¬a) ∈ G. By the first half of this lemma, there is an ultrafilter u extending G. The Boolean a cannot be in u as otherwise a ∧ (¬a) = ⊥ ∈ u as well. Therefore, u is an ultrafilter extending F not containing a, as desired. ∎
The lemma above is called the ultrafilter lemma, and we'll use it in proving St(B) is compact.
Let Σ be a family of closed subsets of St(B) so that any finite subset of Σ has a non-empty intersection.
Define a filter F as follows:
F = {a ∈ B | ∃C₁,...,Cₙ ∈ Σ. C₁ ∩ ... ∩ Cₙ ⊂ U_a}
We have that a ≤ b implies U_a ⊂ U_b and therefore F is upwards closed. Further, for a,b ∈ F, there are some C₁,...,Cₙ,D₁,...,Dₘ ∈ Σ for which C₁ ∩ ... ∩ Cₙ ⊂ U_a and D₁ ∩ ... ∩ Dₘ ⊂ U_b and therefore C₁ ∩ ... ∩ Cₙ ∩ D₁ ∩ ... ∩ Dₘ ⊂ U_(a ∧ b). So, F is downwards directed. Further, U_⊥ = ∅ and, by assumption, any finite subset of Σ has a non-empty intersection, so F is a proper filter.
By the ultrafilter lemma, F has an extension to an ultrafilter u. For every C in Σ, we have that C is the intersection of basic open sets U_a. By construction of F, we have that a ∈ F ⊂ u for every such basic open set U_a and therefore u ∈ C for every C in Σ, as desired. Therefore, St(B) is compact.
CLOP(St(B)) and St(CLOP(X))
We saw that, for a Boolean algebra B, St(B) is a Stone space, and for a space X, CLOP(X) is a Boolean algebra. In this chapter, we'll show that these actions (St and CLOP) are essentially inverses of eachother. For a space X, we'll construct a homeomorphism (topological isomorphism)
u_X: X -> St(CLOP(X))
and for a Boolean algebra B, we'll construct a Boolean isomorphism
β_B: B -> CLOP(St(B))
The notations u_X and β_B are not standard, but I need something to represent these transformations.
Before we define either transformation, I want to explain why Stone spaces are defined as they are. We want to construct a homeomorphism u_X: X -> St(CLOP(X)). However, to do this, we want CLOP(X) to have enough information to reconstruct the space. This is why we require Stone spaces to be totally disconnected space: in a totally disconnected space, points can be identified by the clopens they are contained in. Further, we also want that the Boolean algebra CLOP(X) doesn't suggest X has points that it actually does not have. For example, in the space of rational numbers (with the subspace topology of the reals), which forms a totally disconnected space, it seems like there should be a point at √2 when only looking at the clopens, as we can define a family of clopens that, in theory, are the clopens containing √2 (in particular, the family {C ⊂ ℚ clopen | ∃ε > 0. (√2-ε..√2+ε) ∩ ℚ ⊂ C}). However, √2 is not rational, so we are mislead by this family of clopens. So, we want a Stone space to have enough points so that any family of clopens that looks like it should contain a point in its intersection does contain a point in its intersection, i.e. a Stone space should be compact (which ℚ is not).
Let's begin with defining the transformation
u_X: X -> St(CLOP(X))
For a point x in X, we want u_X (x) to be an ultrafilter on the algebra of clopens of X. You might be able to guess this yourself, but the following works:
u_X (x) := {C ∈ CLOP(X) | x ∈ C}
I.e. u_X (x) is the filter of clopens that contain x. Verifying this is an ultrafilter is left as an exercise to the reader. You can follow the following steps to prove it is a homeomorphism:
Show that u_X is an injection. I.e. show that, if u_X (x) = u_X (y), then x = y;
Show that u_X is a surjection. I.e. show that, for all ultrafilters u on CLOP(X), there is a point x in X for which u_X (x) = u;
Show that u_X is continuous. I.e. show that, for all open U ⊂ St(CLOP(X)), the preimage (u_X)⁻¹[U] ⊂ X is open.
Show that u_X is open. I.e. show that, for all open U ⊂ X, the image u_X [U] ⊂ St(CLOP(X)) is open.
Which steps require the space X to be totally disconnected, and which require the space X to be compact?
We want to define a Boolean isomorphism
β_B: B -> CLOP(St(B))
For a Boolean a in B, β_B (a) is a clopen set in the Stone space of B. There is a clear choice for β_B (a) that we can find in the definition of St(B):
β_B (a) := U_a = {u ∈ St(B) | a ∈ u}
The basic open set works. Proving this is a Boolean isomorphism is left as an exercise to the reader. In particular, why is this function surjective?
Functor
In the beginning of the blog post, I said that there is a contravariant equivalence between the categories Ba and Stone (and the categories cBa and Stonean). However, we have only looked at the actions of the functors CLOP: Ba -> Stone and St: Stone -> Ba on objects so far. So, how do we extend these functions on objects to actual functors?
Let A and B be Boolean algebras and let f: A -> B be a Boolean homomorphism. We want to find a continuous map
St(f): St(B) -> St(A)
in the category of Stone spaces going in the other direction. For brevity, I will write f* for St(f). For an ultrafilter u on B, what should the ultrafilter f*(u) be?
Recall from Boolean Homomorphisms and Ultrafilters that an ultrafilter on B is equivalent to a Boolean homomorphism
u: B -> 2
to the two-element Boolean algebra. We can compose homomorphisms to get another homomorphism, so we can define f*(u) as the composition
f*(u) = u ∘ f: A -> 2
I.e. f*(u)(a) = u(f(a)). Thinking of u as a subset of B (rather than a Boolean homomorphism), this definition says that f*(u) is the set of Booleans a in A for which f(a) is in the ultrafilter u. We want to verify f* is continuous.
An open set in St(A) is a union of basic open sets U_a. The preimage of a union is a union of preimages, and as unions of open sets are open, it is sufficient to show that preimages of basic open sets under f* are open. So, let a ∈ A be a Boolean, aiming to show that (f*)⁻¹[U_a] is open in St(B). We have
which is open. If you did the exercises in the previous chapter, you probably used similar arguments to solve them.
For St to be a functor, we want that it satisfies funtoriality. I.e. we want that
(f ∘ g)* = g* ∘ f*
(id_A)* = id_St(A)
Doing this is just some basic algebraic manipulation, so I won't prove it here.
As for the other direction, for a continuous map f: X -> Y between Stone spaces, we want to find a Boolean homomorphism
CLOP(f): CLOP(Y) -> CLOP(X)
in the other direction. Again, I will abbreviate CLOP(f) to f*. For a clopen subset C of Y, how do we find a clopen subset f*(C) of X?
We find our answer if we look at the definition of continuity. The function f: X -> Y is continuous iff the preimage of any open set is open. As complements of preimages are preimages of complements, this also implies that preimages of closed sets are closed, and preimages of clopen sets are clopen. We can thus set
f*(C) := f⁻¹[C] = {x ∈ X | f(x) ∈ C}
to be the preimage of C under f. We still need to verify f* is a Boolean homomorphism, but that is not too difficult. Every axiom of a Boolean homomorphism maps to a basic fact of preimages:
f* sends ⊤ to ⊤ as the preimage of the codomain is the domain;
f* sends ⊥ to ⊥ as the preimage of the empty set is empty;
f* preserves meets as the preimage of an intersection is an intersection of preimages;
f* preserves joins as the preimage of a union is a union of preimages;
f* preserves complements as the preimage of a complement is the complement of a preimage.
We cannot use the same argument to show that f* is a complete Boolean homomorphism as, in the argument above, we rely on the fact that clopen sets are closed under finite unions, finite intersections and complements. They are generally not closed under infinite unions and intersections.
We are now almost done with proving (CLOP, St, u, β) is an equivalence between Stone and Ba. There is one thing left to do, and that is proving the transformations u and β are natural. Let's start with proving u is natural.
Let X and Y be Stone spaces and let f: X -> Y be a continuous map. We want to show that
St(CLOP(f)) ∘ u_X = u_Y ∘ f
We abbreviate St(CLOP(f)) to f**. Let x ∈ X be a point. We have
To prove β is natural, one must show that, for any two Boolean algebras A and B and any Boolean homomorphism f: A -> B, we have
CLOP(St(f)) ∘ β_A = β_B ∘ f
The proof is similar to the symbol manipulation we did before. I'll leave it as an exercise, as proving this yourself might help you understand the proof that u is natural better.
WLEM
Recall a topology X is extremally disconnected iff it satisfies the weak law of excluded middle (wlem): all negative propositions are decidable. Or, RO(X) = CLOP(X), where the regular open subsets of X correspond to negative propositions and clopen subsets correspond to decidable propositions.
So far, we have looked at Stone duality between the category of Boolean algebras and Boolean homomorphisms and the category of Stone spaces and continuous maps. In the beginning of the blog post, I mentioned that there also is a contravariant equivalence between the category of complete Boolean algebras and complete Boolean homomorphisms and the category of Stonean spaces and open continuous maps. We'll prove the second equivalence in this chapter.
Proposition. A Boolean algebra B is complete iff St(B) is extremally disconnected.
Proof. We have that CLOP(St(B)) is isomorphic to B. If St(B) is extremally disconnected, then CLOP(St(B)) = RO(St(B)). We know the regular open algebra of a topology is complete, so B is complete.
For the other direction, suppose B is complete. Let R ⊂ St(B) be regular open. Then, R is a union of basic open sets U_a. Let S ⊂ B be so that R = ⋃{a ∈ S} U_a. As B is complete, ⋁S exists. I claim that R = U_⋁S and that R is therefore clopen. It suffices to show that cl(R) = U_⋁S, as then R = int(cl(R)) = int(U_⋁S) = U_⋁S. Let u ∈ U_⋁S, aiming to show that u ∈ cl(R). Let U_a be a basic open neighbourhood of u, aiming to show that U_a ∩ R ≠ ∅. We have ⋁S ∈ u and a ∈ u and therefore a ∧ ⋁S ∈ u. Further, as ⊥ ∉ u, we have a ∧ ⋁S ≠ ⊥. If, for all b ∈ S, we have a ∧ b = ⊥, then a ∧ ⋁S = ⋁{b ∈ S} a ∧ b = ⋁{⊥} = ⊥, a contradiction. Therefore, there is some b ∈ S for which a ∧ b ≠ ⊥. By the ultrafilter lemma, there is an ultrafilter extending the principal ultrafilter ↑(a ∧ b) = {c ∈ B | a ∧ b ≤ c}, which lies in the intersection U_a ∩ R. Therefore, the intersection U_a ∩ R is non-empty. As U_a was arbitrary, we have u ∈ cl(R), and as u was arbitrary, we have U_⋁S ⊂ cl(R). Therefore, R = U_⋁S is clopen. ∎
Therefore, for a complete Boolean algebra B, we have that St(B) is a Stonean space and CLOP(St(B)) gives back the cBa B (up to isomorphism). As for the other direction, if X is Stonean, then CLOP(X) = RO(X) is complete (as the regular open algebra is complete), and St(CLOP(X)) gives back the topology X. The rest of the equivalence between cBa and Stonean is the same as that between Ba and Stone.
RO gives us a way to complete any Boolean algebra. For a Boolean algebra B, RO(St(B)) is called the completion of B. For example, the completion of the finite-cofinite algebra (the Boolean algebra of finite and cofinite (complements of finite) subsets of ℕ ordered under inclusion) is RO(St(fin ∪ cofin)) = RO(ℕ̅) = P(ℕ), the power algebra on ℕ.
Edit: I just realized I forgot to prove the duality between complete Boolean homomorphisms and open continuous maps (i.e. that f* is open for complete f: A -> B, and f* is complete for open f: X → Y, where A and B are cBa's and X and Y are Stonean). I don't really want to work on this blog post longer so... exercise to the reader I guess ¯\(˙˘˙)/¯
Last Chapter
Meoww thanks for reading. I'm eepy now, good night.
I was planning to write some more, a chapter explaining a more categorical approach to proving Stone duality, but I'm not confident enough in my understanding of the topics I wanted to write about. Maybe I'll talk about profinite sets in a future blog post.
The Stone topology of a Boolean algebra is a special case of the Zariski topology of a ring. A friend has been teaching me algebraic geometry. Maybe I'll make a blog post on the topic, where I'll explain what the Zariski topology is and maybe how the properties of St(B) generalize to it.
Anyone know of interesting upcoming conferences within the Schengen zone (or more generally just in Europe) in algebraic geometry or algebraic topology or category theory? Thinking of trying to make a trip to one...
Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.
✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality
Anya is LIVE right now
FREE
Free to watch • No registration required • HD streaming
what if the m2 money supply was a single solitary dollar and you had to wait for it to worm its way thru the economy to you before you could use it to buy a can of pop or some such
There is a single dollar, but whenever it interacts with a person i can get reflected in spacetime and potentially travel backwards in time (giving the illusion of debt, which gets annahilated when it comes into contact with money) and the illusion of multiple dollars (multiple instances exist at the same simultinaety of an observer)
You have to have friends who think your life's passion ain't shit. You have to hang out with people who simply do notttt give a crap about the thing that you find all consuming. Because if you don't, then when you're really stressed about that thing, your friends are also gonna be stressed about it, and you're just gonna end up in a stress feedback loop with no outside input.
But if you have friends who could not possibly give fewer fucks about your calling, then when you're really fucking stressed because it feels like it's your entire world, they can say, "...You know representation theory like... doesn't matter, right? Do you want to get takeout and play a video game? Let's get takeout and play a video game." And then you will get takeout and play a video game and feel a bit better.
When people inquire into my early specialization as an undergraduate student, I find no difficulty in producing a response. Often, I feel verbal descriptions fail to adequately convey the warmth I feel looking across the dinner table of smiling mathematicians.
The algebraic combinatorics community has always welcomed students and colleagues with open arms. Mentorship is baked deep into our culture, and boisterous tidbits of history weave their way through every lecture and talk.
I recall walking by my future mentor's side as a starry-eyed forlorn freshman, listening to him share tidbits from his well-regarded books and short tales from past conferences. I ate my first conference dinner surrounded by his students and their friends -- being an undergrad mattered little, save for the initial moment of surprise.
Years later, I run up to the same mathematicians with an eager wave at conferences. We catch up on our research, discuss problems the other might take a stab at, and eventually scurry off the next talk. Gatherings that once felt novel and foreboding melt into friendly reunions. Often, the only alarm is that my mentor continued taking students... one that I often laughingly share in -- he is known by all in the field for his kindness and generosity.
As I grew older, my mentor's students offered countless foundational lessons in our field. I stumbled my way through ideas in Coxeter combinatorics, cluster algebras, topological combinatorics, and recent work on vertex models. They dusted me off when I fell flat on my face during countless presentations, pushing me forward with kind yet intentional words of encouragement.
At times, I questioned if others only talked to me because of my mentor, but age and practice gradually aided my emerging voice in the area. My conjectures became more interesting, and I felt no fear sharing opinions among the group. I had friends I could talk math with at length -- my whole world became beautifully entangled with their community.
Specialization came without question -- I finally had a community that supported both my mathematical and personal success. Ideas from areas of math can be picked up over a lifetime, but a found-family is far more rare.
As I prepare for my final undergraduate summer, surrounded by the mathematicians I've now known for years, I cannot help but bask in the history of my field. I adore reading how kindness runs deep through previous senior mathematicians, how a young field tapped into so many different areas in the large expanse of mathematics.
I only hope I can go on to make their efforts and kindness worthwhile. For now, I write.
(I also recognize this post might make me recognizable to those who know me in real life... although I doubt any of them are here, if they are... hi lol)
I tend to feel this way, but I am eager for counterexamples.
I do think these debates of definition are very useful though in serving as a sort of conceptual engineering that builds a framework for understanding the world through.
This was one of the main observations by Wittgenstein actually, so we are in good company. His statements have been interpreted and oft requoted in the form "there are no philosophical problems".
Philosophical problems... are, of course, not empirical problems; but they are solved through an insight into the workings of our language, and that in such a way that these workings are recognized.
Personally, I have yet to see a philosophical problem (or debate) which was not resolved by merely clarifying our definitions, and I have searched somewhat thoroughly. To be honest, nothing even really comes close for me.
Could it be that this debate, about whether there are philosophical problems, is itself exactly that kind of issue? A problem which is resolved by our defining what "philosophical problem" even means? And if we do define it, would its applicants not cease to be philosophy?
A philosophical problem has the form: “I don’t know my way about.”
Knowing that a certain problem is attributable entirely to confusion about language does, at least for me, tend to instantly resolve the problem. The problems most commonly cited as "unsolved philosophy problems" have always felt trivial to me, in exactly this way. If I understand it then the problem is solved as far as I'm concerned. I don't need others to agree to my definitions or vice versa, I'm content to amicably navigate around theirs while keeping my own. What remains is then tantamount to empiricism.
Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.
✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality
Anya is LIVE right now
FREE
Free to watch • No registration required • HD streaming
I'm attending an "elementary geometry" lecture taught by a category theorist this semester and I've never felt so much like I was living through the chinese room hypothetical in real life
This is a stand-alone version of a post that was split in two reblog chains under a different mostly unrelated post.
There are non-concretizable categories, aka categories which can not be thought of as sets and functions.
A concrete category is a category with a faithful (= injective on each hom-set, but not necessarily on objects) functor to the category of sets.
An classical example of a non-concretizable category is Ho(Top), the homptopy category of Topological spaces.
But why is this relevant?
Like with any size issue you can trick your way into ignoring it when you have large enough cardinals with respect to the category you are working with and are willing to step up in the size hierarchy. Similarily there are trivial counterexamples (if you allow categories with proper hom-classes).
Whenever we have a category K and a universe of set theory V in which this category is set-sized we have an easy concreatization F: K→V which maps objects X to ∪{K(A,X) | A∈K} and morphisms f∈K(X,Y) to -○f.
And if a category has a proper class sized hom-class there cannot be a concretization.
However there is the relevant case of proper class sized categories with set-sized hom-sets. For example the category of topologigal spaces. If we care about "all" topological spaces the trick of taking an universe of set theory with larger cardinals is no longer viable, since this would mean we can also have more topological spaces. Morally similar to how circumventions of various other size issues don't fundamentally invalidate those size issues.
But topological spaces are still concretizable, by simply forgetting the topological structure. The interesting insight is that this can not be done for all categories. Not all categories with set sized hom-sets can be thought of as sets with additional structure and morphisms which are particular functions, hence my original claim.
Ho(Top) has set sized hom-sets, since those are surjected on from the hom-sets of Top. Yet it can not be thought of as sets and functions.
In some way you can reinterpret the fact that not all locally small categories are concretizable as "the hom-sets being small does not imply that the objects can be represented via small sets".
How to prove this?
Theorem (Isbell, Freyd). A category which has all finite limits is concretizable if and only if it is well-powered when restricted to regular subobjects.
In fact this theorem holds for a weakening of the finite limits condition, but that basically just adds notational overhead.
Here an object being well-powered means that it has a partially ordered set of subobjects (= monomorphisms to the object). (This corresponds to the intuition "the powerset of the object exists. Ofc monomorphisms to an object are always partially ordered up to isomorphisms by monomorphisms between their domains, the important part here is that it is only set-sized. Also you can only take the domains of those monomorphisms as the subobjects, which also works.)
A monomorphism (or subobject) is regular if it is the equalizer of two morphisms in the category. (So intuetively if it can be defined as "the part of the domain of two morphisms on which they agree". This has little to do with the notion of regularity in set theory.)
The "⇒" of the theorem is due to Isbell and is quite easy to prove by
just applying the definitions to get that faithful functors are injective on equivalence classes of regular subobjects,
and the fact that sets have power-sets.
Try it yourself! (The "⇐" direction is due to Freyd and more complicated.)
Freyd discovered that we can now use this argument by Isbell to prove that Ho(Top) is not concretizable.
Anya is live and ready to show you everything. Watch her strip, dance, and perform exclusive shows just for you. Interact in real-time and make your fantasies come true.
✓ Live Streaming✓ Interactive Chat✓ Private Shows✓ HD Quality
Anya is LIVE right now
FREE
Free to watch • No registration required • HD streaming
This is a stand-alone version of a post that was split in two reblog chains under a different mostly unrelated post.
There are non-concretizable categories, aka categories which can not be thought of as sets and functions.
A concrete category is a category with a faithful (= injective on each hom-set, but not necessarily on objects) functor to the category of sets.
An classical example of a non-concretizable category is Ho(Top), the homptopy category of Topological spaces.
But why is this relevant?
Like with any size issue you can trick your way into ignoring it when you have large enough cardinals with respect to the category you are working with and are willing to step up in the size hierarchy. Similarily there are trivial counterexamples (if you allow categories with proper hom-classes).
Whenever we have a category K and a universe of set theory V in which this category is set-sized we have an easy concreatization F: K→V which maps objects X to ∪{K(A,X) | A∈K} and morphisms f∈K(X,Y) to -○f.
And if a category has a proper class sized hom-class there cannot be a concretization.
However there is the relevant case of proper class sized categories with set-sized hom-sets. For example the category of topologigal spaces. If we care about "all" topological spaces the trick of taking an universe of set theory with larger cardinals is no longer viable, since this would mean we can also have more topological spaces. Morally similar to how circumventions of various other size issues don't fundamentally invalidate those size issues.
But topological spaces are still concretizable, by simply forgetting the topological structure. The interesting insight is that this can not be done for all categories. Not all categories with set sized hom-sets can be thought of as sets with additional structure and morphisms which are particular functions, hence my original claim.
Ho(Top) has set sized hom-sets, since those are surjected on from the hom-sets of Top. Yet it can not be thought of as sets and functions.
In some way you can reinterpret the fact that not all locally small categories are concretizable as "the hom-sets being small does not imply that the objects can be represented via small sets".
How to prove this?
Theorem (Isbell, Freyd). A category which has all finite limits is concretizable if and only if it is well-powered when restricted to regular subobjects.
In fact this theorem holds for a weakening of the finite limits condition, but that basically just adds notational overhead.
Here an object being well-powered means that it has a partially ordered set of subobjects (= monomorphisms to the object). (This corresponds to the intuition "the powerset of the object exists. Ofc monomorphisms to an object are always partially ordered up to isomorphisms by monomorphisms between their domains, the important part here is that it is only set-sized. Also you can only take the domains of those monomorphisms as the subobjects, which also works.)
A monomorphism (or subobject) is regular if it is the equalizer of two morphisms in the category. (So intuetively if it can be defined as "the part of the domain of two morphisms on which they agree". This has little to do with the notion of regularity in set theory.)
The "⇒" of the theorem is due to Isbell and is quite easy to prove by
just applying the definitions to get that faithful functors are injective on equivalence classes of regular subobjects,
and the fact that sets have power-sets.
Try it yourself! (The "⇐" direction is due to Freyd and more complicated.)
Freyd discovered that we can now use this argument by Isbell to prove that Ho(Top) is not concretizable.
It's getting worse every year. In my department the amount of BSc students who go above and beyond in absolutely insane ways outnumber the departments total number of Phd positions. True effort-inflation; its definitely getting more insane every year.
Working hard to make magic mundane @m---a---x - Tumblr Blog | Tumlook
