The Yoneda lemma I

For two categories let denote the functor category, whose objects are functors and whose morphisms are natural transformations. For a locally small category, the Yoneda embedding is the functor sending an object to the contravariant functor and sending a morphism to the natural transformation given by composition. The goal of the next few posts is to discuss some standard properties of this embedding and try to gain some intuition about it.

Below, whenever we talk about the Yoneda lemma we implicitly restrict our attention to locally small categories.

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 »

The adjoint functor theorem for posets

Recently in Measure Theory we needed the following lemma.

Lemma: Let be non-constant, right-continuous and non-decreasing, and let . Define by . Then is left-continuous and non-decreasing. Moreover, for and ,

.

If you’re categorically minded, this last condition should remind you of the definition of a pair of adjoint functors. In fact it is possible to interpret the above lemma this way; it is a special case of the adjoint functor theorem for posets. Today I’d like to briefly explain this. (And who said category theory isn’t useful in analysis?)

The usual caveats regarding someone who’s never studied category talking about it apply. I welcome any corrections.

Read Full Post »

Lattice paths and the quadratic coefficient of Kazhdan-Lusztig polynomials

SPUR is finally over! Instead of continuing my series of blog posts, I thought I’d just link to my paper, Lattice paths and the quadratic coefficient of Kazhdan-Lusztig polynomials, and the first few blog posts should more or less provide enough background to read it.

My project ended up changing direction. The formula I was working with for the quadratic coefficient was so unwieldy that I ended up spending the whole time trying to simplify it, and instead of saying anything about non-negativity I ended up saying something about combinatorial invariance. The combinatorial invariance conjecture, which goes back to Lusztig and, independently, Dyer, says that the Kazhdan-Lusztig polynomial depends only on the poset structure of . In the special case that this was proven in 2006 by Brenti, Caselli, and Marietti. However, the conjecture is still open in general.

In particular, explicit nonrecursive formulas in which each term only depends on poset-theoretic data are not known in general. They are known in the case that the length of the interval is less than or equal to , and there is also such a formula for the coefficient of of where is the identity. The main result of the paper is a formula for the coefficient of of in which all but three of the terms depend only on poset data, which is a simplification of a general formula due to Brenti for in terms of lattice paths. It reduces to

• a formula for the coefficient of of in which all but one of the terms depends only on poset data,
• a formula for the coefficient of of where in which all but one of the terms (but a different term) depends only on poset data (not in the paper), and
• a formula for the coefficient of of where in which every term depends only on poset data.

I believe these formulas are known in some form, but the method of proof is likely to be novel. In any case, the troublesome terms in the above are all essentially coefficients of R-polynomials. If I revisit this project in the future, I will be focusing my attention on these coefficients, and my goal will be to find a poset-theoretic formula for in the length case, the smallest-length case where (to my knowledge) combinatorial invariance is open.

Read Full Post »

Chevalley-Bruhat order

Before we define Bruhat order, I’d like to say a few things by way of motivation. Warning: I know nothing about algebraic groups, so take everything I say with a grain of salt.

A (maximal) flag in a vector space of dimension is a chain of subspaces such that . The flag variety of is, for our purposes, the “space” of all maximal flags. acts on the flag variety in the obvious way, and the stabilizer of any particular flag is a Borel subgroup . If denotes a choice of ordered basis, one can define the standard flag , whose stabilizer is the space of upper triangular matrices of determinant with respect to the basis . This is the standard Borel, and all other Borel subgroups are conjugate to it. Indeed, it’s not hard to see that acts transitively on the flag variety, so the flag variety can be identified with the homogeneous space .

Read Full Post »

Kraft’s inequality for prefix codes

Kraft’s inequality: Let be a prefix code on an alphabet of size , and let denote the number of codewords of length . Then .

In lieu of reposting my old blog posts I thought I’d revisit some of their topics instead. In an old post of mine I set this inequality as a practice problem. I had an easy but uninspired proof in mind, but recently I learned that this problem is an exercise in the first chapter of The probabilistic method by Alon and Spencer. The probabilistic proof is quite elegant, so I thought it was worth presenting.

Read Full Post »

The “correct” definition of a homomorphism

(Warning: I’m trying to talk about things I don’t really understand in this post, so feel free to correct me if you see a statement that’s obviously wrong.)

Why are continuous functions the “correct” notion of homomorphism between topological spaces?

The “obvious” way to define homomorphisms for a large class of objects involves thinking of them as “sets with extra structure,” and then homomorphisms are functions that preserve that extra structure. In category theory this is formalized by the notion of a concrete category, i.e. a category with a good notion of forgetful functor. For topological spaces this is the functor which gives the set of points.

However, a naive interpretation of “preserving additional structure” suggests that homomorphisms between topological spaces should be open maps, and this isn’t the case. So what gives?

I’m not sure. But rather than take the concrete perspective I’d like to talk about another general principle for defining a good notion of homomorphism.

Little insight: If you can realize a structure as a small category, homomorphisms should be functors.

Read Full Post »