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.

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.