You are currently browsing the monthly archive for June 2008.
I’ll continue then with this brief subseries on category theory. Today I want to talk more about universal properties, and about the notion of natural transformation. Maybe not today, but soon at any rate, I want to tie all this in with the central concept of representability, which leads directly and naturally to the powerful and fundamental idea of adjoint functors. This goes straight to the very heart of category theory.
The term “natural”, often bandied about by mathematicians, is perhaps an overloaded term (see the comments here for a recent disagreement about certain senses of the word). I don’t know the exact history of the word as used by mathematicians, but by the 1930s and 40s the description of something as “natural” was part of the working parlance of many mathematicians (in particular, algebraic topologists), and it is to the great credit of Eilenberg and Mac Lane that they sought to give the word a precise mathematical sense. A motivating problem in their case was to prove a universal coefficient theorem for Cech cohomology, for which they needed certain comparison maps (transformations) which cohered by making certain diagrams commute (which was the naturality condition). In trying to precisely define this concept of naturality, they were led to the concept of a “functor” and then, to define the concept of functor, they were led back to the notion of category! And the rest, as they say, is history.
More on naturality in a moment. Let me first give a few more examples of universal constructions. Last time we discussed the general concept of a cartesian product — obviously in honor of Descartes, for his tremendous idea of the method of coordinates and analytic geometry.
But of course products are only part of the story: he was also interested in the representation of equations by geometric figures: for instance, representing an equation as a subset of the plane. In the language of category theory, the variable denotes the second coordinate or second projection map , and denotes the composite of the first projection map followed by some given map :
The locus of the equation is the subset of where the two morphisms and are equal, and we want to describe the locus in a categorical way (i.e., in a way which will port over to other categories).
Definition: Given a pair of morphisms
their equalizer consists of an object and a map , such that , and satisfying the following universal property: for any map such that , there exists a unique map such that (any map that equalizes and factors in a unique way through the equalizer ).
Another way of saying it is that there is a bijection between -equalizing maps and maps ,
effected by composing such maps with the universal -equalizing map .
Exercise: Apply a universality argument to show that any two equalizers of a given pair of maps are isomorphic.
It is not immediately apparent from the definition that an equalizer describes a “subthing” (e.g., a subset) of , but then we haven’t even discussed subobjects. The categorical idea of subobject probably takes some getting used to anyway, so I’ll be brief. First, there is the idea of a monomorphism (or a “mono” for short), which generalizes the idea of an injective or one-to-one function. A morphism is monic if for all , implies . Monos with codomain are preordered by a relation , where
if there exists such that . (Such a is unique since is monic, so it doesn’t need to be specified particularly; also this is easily seen to be monic [exercise].) Then we say that two monics mapping into name the same subobject of if and ; in that case the mediator is an isomorphism. Writing to denote this condition, it is standard that is an equivalence relation.
Thus, a subobject of is an equivalence class of monos into . So when we say an equalizer of maps defines a subobject of , all we really mean is that is monic. Proof: Suppose for maps . Since , we have for instance. By definition of equalizer, this means there exists a unique map for which . Uniqueness then implies are equal to this self-same , so and we are done.
Let me turn to another example of a universal construction, which has been used in one form or another for centuries: that of “function space”. For example, in the calculus of variations, one may be interested in the “space” of all (continuous) paths in a physical space , and in paths which minimize “action” (principle of least action).
If is a topological space, then one is faced with a variety of choices for topologizing the path space (denoted ). How to choose? As in our discussion last time of topologizing products, our view here is that the “right” topology will be the unique one which ensures that an appropriate universal property is satisfied.
To get started on this: the points of the path space are of course paths , and paths in the path space, , sending each to a path , should correspond to homotopies between paths, that is continuous maps ; the idea is that . Now, just knowing what paths in a space look like (homotopies between paths) may not be enough to pin down the topology on , but: suppose we now generalize. Suppose we decree that for any space , the continuous maps should correspond exactly to continuous maps , also called homotopies. Then that is enough to pin down the topology on . (We could put it this way: we use general spaces to probe the topology of .)
This principle applies not just to topology, but is extremely general: it applies to any category! I’ll state it very informally for now, and more precisely later:
Yoneda principle: to determine any object up to isomorphism, it suffices to understand what general maps mapping into it look like.
For instance, a product is determined up to isomorphism by knowing what maps into it look like [they look like pairs of maps ]. In the first lecture in the Stone duality, we stated the Yoneda principle just for posets; now we are generalizing it to arbitrary categories.
In the case at hand, we would like to express the bijection between continuous maps
as a working universal property for the function space . There is a standard “Yoneda trick” for doing this: probe the thing we seek a universal characterization of with the identity map, here . Passing to the other side of the bijection, the identity map corresponds to a map
and this is the “universal map” we need. (I called it because in this case it is the evaluation map, which maps a pair (path , point ) to , i.e., evaluates at .)
Here then is the universal characterization of the path space: a space equipped with a continuous map , satisfying the following universal property: given any continuous map , there exists a unique continuous map such that is retrieved as the composite
(for the first arrow in the composite, cf. the exercise stated at the end of the last lecture).
Exercise: Formulate a universality argument that this universal property determines up to isomorphism.
Remark: Incidentally, for any space , such a path space exists; its topology turns out to be the topology of “uniform convergence”. We can pose a similar universal definition of any function space (replacing by , mutatis mutandis); a somewhat non-trivial result is that such a function space exists for all if and only if is locally compact; the topology on is then the so-called “compact-open” topology.
But why stop there? A general notion of “exponential” object is available for any category with cartesian products: for objects of , an exponential is an object equipped with a map , such that for any , there exists a unique such that is retrieved as the composite
Example: If the category is a meet-semilattice, then (assuming exists) there is a bijection or equivalence which takes the form
iff
But wait, we’ve seen this before: is what we earlier called the implication . So implication is really a function space object!
Okay, let me turn now to the notion of natural transformation. I described the original discovery (or invention) of categories as a kind of reverse engineering (functors were invented to talk about natural transformations, and categories were invented to talk about functors). Moving now in the forward direction, the rough idea can be stated as a progression:
- The notion of functor is appropriately defined as a morphism between categories,
- The notion of natural transformation is appropriately defined as a morphism between functors.
That seems pretty bare-bones: how do we decide what the appropriate notion of morphism between functors should be? One answer is by pursuing an analogy:
- As a space of continuous functions is to the category of topological spaces, so a category of functors should be to the category of categories.
That is, we already “know” (or in a moment we’ll explain) that the objects of this alleged exponential category are functors . Since is defined by a universal property, it is uniquely determined up to isomorphism. This in turn will uniquely determine what the “right” notion of morphism between functors should be: morphisms in the exponential ! Then, to discover the nature of these morphisms, we employ an appropriate “probe”.
To carry this out, I’ll need two special categories. First, the category denotes a (chosen) category with exactly one object and exactly one morphism (necessarily the identity morphism). It satisfies the universal property that for any category , there exists a unique functor . It is called a terminal category (for that reason). It can also be considered as an empty product of categories.
Proposition: For any category , there is an isomorphism .
Proof: Left to the reader. It can be proven either directly, or by applying universal properties.
The category can also be considered an “object probe”, in the sense that a functor is essentially the same thing as an object of (just look where the object of goes to in ).
For example, to probe the objects of the exponential category , we investigate functors . By the universal property of exponentials , these are in bijection with functors . By the proposition above, these are in bijection with functors . So objects of are necessarily tantamount to functors (and so we might as well define them as such).
Now we want to probe the morphisms of . For this, we use the special category given by the poset . For if is any category and is a morphism of , we can define a corresponding functor such that , , and sends the morphism to . Thus, such functors are in bijection with morphisms of . Speaking loosely, we could call the category the “generic morphism”.
Thus, to probe the morphisms in the category , we look at functors . In particular, if are functors , let us consider functors such that and . By the universal property of , these are in bijection with functors such that the composite
equals , and the composite
equals . Put more simply, this says and for objects of , and and for morphisms of .
The remaining morphisms of have the form . Introduce the following abbreviations:
- for objects of ;
- for morphisms of .
Since is a functor, it preserves morphism composition. We find in particular that since
we have
or, using the abbreviations,
In particular, the data is redundant: it may be defined either as either side of the equation
.
Exercise: Just on the basis of this last equation (for arbitrary morphisms and objects of ), prove that functoriality of follows.
This leads us at last to the definition of natural transformation:
Definition: Let be categories and let be functors from to . A natural transformation is an assignment of morphisms in to objects of , such that for every morphism , the following equation holds: .
Usually this equation is expressed in the form of a commutative diagram:
F(f) F(c) ---> F(d) | | phi_c | | phi_d V G(f) V G(c) ---> G(d)
which asserts the equality of the composites formed by following the paths from beginning (here ) to end (here ). (Despite the inconvenience in typesetting them, commutative diagrams as 2-dimensional arrays are usually easier to read and comprehend than line-by-line equations.) The commutative diagram says that the components of the transformation are coherent or compatible with all morphisms of the domain category.
Remarks: Now that I’ve written this post, I’m a little worried that any first-timers to category theory reading this will find this approach to natural transformations a little hardcore or intimidating. In that case I should say that my intent was to make this notion seem as inevitable as possible: by taking seriously the analogy
function space: category of spaces :: functor category: category of categories
we are inexorably led to the “right” (the “natural”) notion of natural transformation as morphism between functors. But if this approach is for some a pedagogical flop, then I urge those readers just to forget it, or come back to it later. Just remember the definition of natural transformation we finally arrived at, and you should be fine. Grasping the inner meaning of fundamental concepts like this takes time anyway, and isn’t merely a matter of pure deduction.
I should also say that the approach involved a kind of leap of faith that these functor categories (the exponentials ) “exist”. To be sure, the analysis above shows clearly what they must look like if they do exist (objects are functors ; morphisms are natural transformations as we’ve defined them), but actually there’s some more work to do: one must show they satisfy the universal property with respect to not just the two probing categories and that we used, but any category .
A somewhat serious concern here is that our talk of exponential categories played pretty fast and loose at the level of mathematical foundations. There’s that worrying phrase “category of categories”, for starters. That particular phraseology can be avoided, but nevertheless, it must be said that in the case where is a large category (i.e., involving a proper class of morphisms), the collection of all functors from to is not a well-formed construction within the confines of Gödel-Bernays-von Neumann set theory (it is not provably a class in general; in some approaches it could be called a “super-class”).
My own attitude toward these “problems” tends to be somewhat blasé, almost dismissive: these are mere technicalities, sez I. The main concepts are right and robust and very fruitful, and there are various solutions to the technical “problem of size” which have been developed over the decades (although how satisfactory they are is still a matter of debate) to address the apparent difficulties. Anyway, I try not to worry about it much. But, for those fine upstanding citizens who do worry about these things, I’ll just state one set-theoretically respectable theorem to convey that at least conceptually, all is right with the world.
Definition: A category with finite products is cartesian closed if for any two objects , there exists an exponential object .
Theorem: The category of small categories is cartesian closed.
This week’s problem is offered more in the spirit of a light and pleasant diversion — I don’t think you’ll need any deep insight to solve it. (A little persistence may come in handy though!)
Define a triomino to be a figure congruent to the union of three of the four unit squares in a square. For which pairs of positive integers is an rectangle tileable by triominoes?
Please submit solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, July 3, 11:59 pm (UTC); do not submit solutions in Comments. Everyone with a correct solution will be inducted into our Hall of Fame! We look forward to your response. Enjoy!
We got some very good response to our last week’s problem from several of our “regular” problem-solvers as well as several others who are “new”. There were solutions that were more “algebraic” than others, some that had a more “trigonometric” flavor to them and some that had a combination of both. All the solutions we received this time were correct and they all deserve to be published, but for the sake of brevity I will post just one.
Solution to POW-5: (due to Animesh Datta, Univ of New Mexico)
Note that the given integral may be written as
.
Now, we use the substitution , which transforms the integral into
.
Finally, we use one last (trigonometric) substitution , which transforms the integral into , which evaluates to , which equals . And this is our final answer!
Watch out for the next POW that will be posted by Todd!
Source: I had mentioned earlier that Carl Lira had brought this integral to our attention, and he in turn had found it in the MIT Integration Bee archives. This one was from the year 1994.
Trivia: Four out of the six people who sent correct solutions are either Indians or of Indian origin! Coincidence? :)
After a long hiatus (sorry about that!), I would like to resume the series on Stone duality. You may recall I started this series by saying that my own point of view on mathematics is strongly informed by category theory, followed by a little rant about the emotional reactions that category theory seems to excite in many people, and that I wouldn’t be “blathering” about categories unless a strong organic need was felt for it. Well, it’s come to that point: to continue talking sensibly about Stone duality, I really feel some basic concepts of category theory are now in order. So: before we pick up the main thread again, I’ll be talking about categories up to the point of the central concept of adjoint pairs, generalizing what we’ve discussed before in the context of truth-valued matrix algebra.
I’ll start by firmly denouncing a common belief: that category theory is some arcane, super-abstract subject. I just don’t believe that’s a healthy way of looking at it. To me, categories are no more and no less abstract than groups, rings, fields, etc. — they are just algebraic structures of a certain type (and a not too complicated type at that). That said, they are particularly ubiquitous and useful structures, which can be studied either as small structures (for example, posets provide examples of categories, and so do groups), or to organize the study of general types of structure in the large (for example, the class of posets and poset morphisms forms a category). Just think of them that way: they are certain sorts of algebraic structures which crop up just about everywhere, and it is very useful to learn something about them.
Usually, the first examples one is shown are large categories, typically of the following sort. One considers the class of mathematical structures of a given type: it could be the class of groups, or of posets, or of Boolean algebras, etc. The elements of a general such class are given the neutral name “objects”. Then, we are also interested in how the objects are related to each other, typically through transformations which “preserve” the given type of structure. In the case of sets, transformations are just functions; in the case of groups, the transformations are group homomorphisms (which preserve group multiplication, inversion, and identities); in the case of vector spaces, they are linear transformations (preserving vector addition and scalar multiplication); in the case of topological spaces, they are continuous maps (preserving a suitable notion of convergence). In general, the transformations are given the neutral name “homomorphisms”, or more often just “morphisms” or “maps”.
In all of these cases, two morphisms , compose to give a new morphism (for example the composite of two group homomorphisms is a group homomorphism), and do so in an associative way (), and also there is an identity morphism for each object which behaves as identities should ( for any morphism ). A collection of objects, morphisms between them, together with an associative law of composition and identities, is called a category.
A key insight of category theory is that in general, important structural properties of objects can be described purely in terms of general patterns or diagrams of morphisms and their composites. By means of such general patterns, the same concept (like the concept of a product of two objects, or of a quotient object, or of a dual) takes on the same form in many different kinds of category, for many different kinds of structure (whether algebraic, or topological, or analytic, or some mixture thereof) — and this in large part gives category theory the power to unify and simplify the study of general mathematical structure. It came as quite a revelation to me personally that (to take one example) the general idea of a “quotient object” (quotient group, quotient space, etc.) is not based merely on vague family resemblances between different kinds of structure, but can be made absolutely precise and across the board, in a simple way. That sort of explanatory power and conceptual unification is what got me hooked!
In a nutshell, then, category theory is the study of commonly arising structures via general patterns or diagrams of morphisms, and the general application of such study to help simplify and organize large portions of mathematics. Let’s get down to brass tacks.
Definition: A category consists of the following data:
- A class of objects;
- A class of morphisms;
- A function which assigns to each morphism its domain, and a function which assigns to each morphism its codomain. If , we write to indicate that and .
- A function , taking an object to a morphism , called the identity on .
Finally, let denote the class of composable pairs of morphisms, i.e., pairs such that . The final datum:
- A function , taking a composable pair to a morphism , called the composite of and .
These data satisfy a number of axioms, some of which have already been given implicitly (e.g., and ). The ones which haven’t are
- Associativity: for each composable triple .
- Identity axiom: Given , .
Sometimes we write for the class of objects, for the class of morphisms, and for , for the class of composable -tuples of morphisms.
Nothing in this definition says that objects of a category are “sets with extra structure” (or that morphisms preserve such structure); we are just thinking of objects as general “things” and depict them as nodes, and morphisms as arrows or directed edges between nodes, with a given law for composing them. The idea then is all about formal patterns of arrows and their compositions (cf. “commutative diagrams”). Vishal’s post on the notion of category had some picture displays of the categorical axioms, like associativity, which underline this point of view.
In the same vein, categories are used to talk about not just large classes of structures; in a number of important cases, the structures themselves can be viewed as categories. For example:
- A preorder can be defined as a category for which there is at most one morphism for any two objects . Given there is at most one morphism from one object to another, there is no particular need to give it a name like ; normally we just write to say there is a morphism from to . Morphism composition then boils down to the transitivity law, and the data of identity morphisms expresses the reflexivity law. In particular, posets (preorders which satisfy the antisymmetry law) are examples of categories.
- A monoid is usually defined as a set equipped with an associative binary operation and with a (two-sided) identity element for that operation. Alternatively, a monoid can be construed as a category with exactly one object. Here’s how it works: given a monoid , define a category where the class consists of a single object (which I’ll give a neutral name like ; it doesn’t have to be any “thing” in particular; it’s just a “something”, it doesn’t matter what), and where the class of morphisms is defined to be the set . Since there is only one object, we are forced to define and for all . In that case all pairs of morphisms are composable, and composition is defined to be the operation in : . The identity morphism on is defined to be . We can turn the process around: given a category with exactly one object, the class of morphisms can be construed as a monoid in the usual sense.
- A groupoid is a category in which every morphism is an isomorphism (by definition, an isomorphism is an invertible morphism, that is, a morphism for which there exists a morphism such that and ). For example, the category of finite sets and bijections between them is a groupoid. The category of topological spaces and homeomorphisms between them is a groupoid. A group is a monoid in which every element is invertible; hence a group is essentially the same thing as a groupoid with exactly one object.
Remark: The notion of isomorphism is important in category theory: we think of an isomorphism as a way in which objects are the “same”. For example, if two spaces are homeomorphic, then they are indistinguishable as far as topology is concerned (any topological property satisfied by one is shared by the other). In general there may be many ways or isomorphisms to exhibit such “sameness”, but typically in category theory, if two objects satisfy the same structural property (called a universal property; see below), then there is just one isomorphism between them which respects that property. Those are sometimes called “canonical” or “god-given” isomorphisms; they are 100% natural, no artificial ingredients!
Earlier I said that category theory studies mathematical structure in terms of general patterns or diagrams of morphisms. Let me give a simple example: the general notion of “cartesian product”. Suppose are two objects in a category. A cartesian product of and is an object together with two morphisms , (called the projection maps), satisfying the following universal property: given any object equipped with a map for , there exists a unique map such that for . (Readers not familiar with this categorical notion should verify the universal property for the cartesian product of two sets, in the category of sets and functions.)
I said “a” cartesian product, but any two cartesian products are the same in the sense of being isomorphic. For suppose both and are cartesian products of . By the universal property of the first product, there exists a unique morphism such that for . By the universal property of the second product, there exists a unique morphism such that . These maps and are inverse to one another. Why? By the universal property, there is a unique map (namely, ) such that for . But also satisfies these equations: (using associativity). So by the uniqueness clause of the universal property; similarly, . Hence is an isomorphism.
This sort of argument using a universal property is called a universality argument. It is closely related to what we dubbed the “Yoneda principle” when we studied posets.
So: between any two products of and , there is a unique isomorphism respecting the product structure; we say that any two products are canonically isomorphic. Very often one also has chosen products (a specific choice of product for each ordered pair ), as in set theory when we construe the product of two sets as a set of ordered pairs . We use to denote (the object part of) a chosen cartesian product of .
Exercise: Use universality to exhibit a canonical isomorphism . This is called a symmetry isomorphism for the cartesian product.
Many category theorists (including myself) are fond of the following notation for expressing the universal property of products:
where the dividing line indicates a bijection between pairs of maps and single maps into the product, effected by composing with the pair of projection maps. We have actually seen this before: when the category is a poset, the cartesian product is called the meet:
In fact, a lot of arguments we developed for dealing with meets in posets extend to more general cartesian products in categories, with little change (except that instead of equalities, there will typically be canonical isomorphisms). For example, we can speak of a cartesian product of any indexed collection of objects : an object equipped with projection maps , satisfying the universal property that for every -tuple of maps , there exists a unique map such that . Here we have a bijection between -tuples of maps and single maps:
By universality, such products are unique up to unique isomorphism. In particular, is a choice of product of the collection , as seen by contemplating the bijection between triples of maps and single maps
and similarly is another choice of product. Therefore, by universality, there is a canonical associativity isomorphism
Remark: It might be thought that in all practical cases, the notion of cartesian product (in terms of good old-fashioned sets of tuples) is clear enough; why complicate matters with categories? One answer is that it isn’t always clear from purely set-theoretic considerations what the right product structure is, and in such cases the categorical description gives a clear guide to what we really need. For example, when I was first learning topology, the box topology on the set-theoretic product seemed to me to be a perfectly natural choice of topology; I didn’t understand the general preference for what is called the “product topology”. (The open sets in the box topology are unions of products of open sets in the factors . The open sets in the product topology are unions of such products where for all but finitely many .)
In retrospect, the answer is obvious: the product topology on is the smallest topology making all the projection maps continuous. This means that a function is continuous if and only if each is continuous: precisely the universal property we need. Similarly, in seeking to understand products or other constructions of more abstruse mathematical structures (schemes for instance), the categorical description is de rigeur in making sure we get it right.
For just about any mathematical structure we can consider a category of such structures, and this applies to the notion of category itself. That is, we can consider a category of categories! (Sounds almost religious to me: category of categories, holy of holies, light of lights…)
- Remark: Like “set of sets”, the idea of category of categories taken to a naive extreme leads to paradoxes or other foundational difficulties, but there are techniques for dealing with these issues, which I don’t particularly want to discuss right now. If anyone is uncomfortable around these issues, a stopgap measure is to consider rather the category of small categories (a category has a class of objects and morphisms; a small category is where these classes are sets), within some suitable framework like the set theory of Gödel-Bernays-von Neumann.
If categories are objects, the morphisms between them may be taken to be structure-preserving maps between categories, called “functors”.
Definition: If and are categories, a functor consists of a function (between objects) and a function (between morphisms), such that
- and , for each morphism (i.e., preserves domains and codomains of morphisms);
- for each object , and for each composable pair (i.e., preserves identity morphisms and composition of morphisms).
Normally we are not so fussy in writing or ; we write and for morphisms and objects alike. Sometimes we drop the parentheses as well.
If are groups or monoids regarded as one-object categories, then a functor between them amounts to a group or monoid homomorphism. If are posets regarded as categories, then a functor between them amounts to a poset map. So no new surprises in these cases.
Exercise: Define a product of two categories , and verify that the definition satisfies the universal property of products in the “category of categories”.
Exercise: If a category has chosen products, show how a functor may be defined which takes a pair of objects to its product . (You need to define the morphism part of this functor; this will involve the universal property of products.)
Time for our next problem in the POW series! Earlier, Todd and I deliberated for a bit on whether we should pose a “hard” Ramanujan identity (involving an integral and Gamma function) as the next POW, but decided against doing it. Perhaps, we may do so some time in the future.
Okay, the following integral was brought to our attention by Carl Lira, and for the time being I won’t reveal the actual source of the problem.
Compute .
It is “hard” or “easy” depending on how you look at it!
Please send your solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, June 26, 11:59pm (UTC); do not submit solutions in Comments. Everyone with a correct solution gets entered in our Hall of Fame! We look forward to your response.
Don’t forget to download Firefox 3.0 today!
The solutions are in! I thought last week’s problem might have been a little more challenging than problems of previous weeks — the identity is just gorgeous, but not at all obvious (I don’t think!) without some correspondingly gorgeous combinatorial insight. Luckily, some of our readers came up with the goods, and their solutions provide a forum for discussing a beautiful circle of ideas, involving the inter-related combinatorics of trees and endofunctions.
I can’t decide which of the solutions we received I like best. They all bear a certain familial resemblance, but each has its own distinct personality. I’ll give two representative examples, and append some comments at the end. Both proofs are conceptual “bijective” proofs, in which the two sides of the identity represent two different ways of counting essentially the same combinatorial objects. And both rely on a famous theorem of Cayley, on the number of tree structures or spanning trees on distinct labeled nodes (maybe this would be sufficient hint, if you still want to think about it some more by yourself!). Here, I’ll add a little spoiler space:
1. (Solution by David Eppstein) As is well known (see, e.g., http://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence), the number of different spanning trees on a set of n labeled nodes is . Equivalently, the number of ways of choosing a spanning tree together with a specification of a single vertex is , and the number of ways of choosing a spanning tree together with a specification of two vertices and (possibly equal to each other) is . So that’s the right hand side of the identity.
Now suppose you are given a tree , and two nodes and . If and are different, let be the first edge on the path in from to ; cutting at that edge produces two disjoint subtrees, one containing one marked node and the other containing two (possibly equal) marked nodes, namely and the first node on the path after . Conversely, from this information (two trees, one containing a marked node and the other containing two marks on nodes and ) we can put together simply by connecting the two trees by an edge . If is the number of nodes in the tree containing , the number of ways we can choose two disjoint marked subtrees in this way is
almost the same as the left hand side of the identity, but missing the final term in the sum.
The final term comes from the case when the marked nodes and of tree T coincide. The number of ways this can happen is the same as the number of ways we can pick a single marked node of a tree, that is, , which is the same as the final term in the left hand sum.
Thus, the left side counts (partitions of n vertices into two disjoint subtrees, one subtree having one marked node and one subtree having two possibly-equal marks) + (-vertex trees with one marked node); the right side counts (-vertex trees with two possibly-equal marks), and we have demonstrated a combinatorial equivalence between these two sets.
2. (Solution by Sune Jakobsen) Consider all -tuples , where each term is from the set Since each of the terms can take values, there are such tuples.
Given a -tuple, , construct a graph as follows. Begin with a vertex labeled . Then, for each vertex labeled in the graph, if , add a new vertex labeled , and connect and by an edge. This graph must be a tree since each only takes one value and doesn’t exist.
Using this graph, I will count the number of -tuples in another way. Let be the number of vertices in such a tree graph. The vertices may be chosen in ways, since the vertex labeled is already one of them. Given the vertices, the tree can be formed in ways, by Cayley’s theorem (see http://www.research.att.com/~njas/sequences/A000272). Given the tree graph, the values of the ‘s, for each vertex labeled in the graph, can be chosen in one and only one way (namely, is the label of the first vertex after along the unique path from vertex to vertex ). The remaining components of the tuple are not among the vertex labels in the graph, so each takes on one of possible values, giving possibilities for the remaining components. Therefore the number of -tuples must be:
Remarks:
1. I found this curious identity in HAKMEM, item 118. For those who don’t know, HAKMEM is a kind of archive of cool mathematical observations made by some of the original MIT computer “hackers” from the 60′s and 70′s, including Bill Gosper and Rick Schroeppel. This particular item is credited to Schroeppel, but the accompanying text is a bit cryptic in my view:
Differentiate to get . One observes the curious identity
()
and thus.
Maybe it was just their style to record a lot of their observations in such terse, compact form, but it annoys me that these guys hide their light under a bushel in this way. No motivation whatsoever, even though (I’d be willing to bet) these guys knew about the connection to trees — they’re computer scientists, after all!
Personally, I find it easier to get from to by other means than through their intermediate identity. I feel sure that just about anyone who has played around with enumerative combinatorics, and with the combinatorics of trees in particular, could figure this one out.
For, as David pointed out in his solution, is the number of spanning trees on the set [] equipped with a distinguished vertex; I’ll call that vertex the root, and such structures rooted trees. (Incidentally, a spanning tree is by definition an acyclic subgraph of the complete graph on the set [], such that any two elements of the set are connected or spanned by a path in the subgraph. The theorem of Cayley mentioned above is that there are such spanning trees.) Thus,
Somehow I find this explanation much easier to understand than the machinations hinted at in HAKMEM 118.
2. David’s proof was actually the one I myself had in mind. I can’t say what inspired David, but I myself was inspired by an earlier reading of a beautiful (and in many respects revolutionary-for-its-time) article, on a systematic functorial approach to enumerative combinatorics:
- André Joyal, Une théorie combinatoire des séries formelles, Adv. Math. 42 (1981), 1-82.
In particular, I am very fond of the proof Joyal gives for Cayley’s theorem (which he credits to Gilbert Labelle), and this proof is in a line of thought which also leads to David’s solution. I’d like to present that proof now.
Labelle’s proof of Cayley’s theorem:
The expression probably makes most people think of the number of functions : [] [] from an -element set to itself. The art of combinatorics lies in drawing appropriate pictures, so draw a picture (a graph) of such a function by drawing a directed edge from to whenever (cf. Sune’s solution). Starting from any vertex and iterating enough times, you always eventually land in a cycle where points get revisited periodically, infinitely often. Let’s call those points periodic points; the function acts as a permutation on periodic points. Now, for each periodic point , consider the union of directed paths which end at without hitting any other periodic points. This union forms a subgraph which is a tree, rooted at (again, cf. Sune’s solution). The entire set [] is thereby partitioned into (equivalence) classes (the underlying vertex sets of the trees ), and the structure of a function [] [] thus determines the following data:
- An equivalence relation on [];
- A rooted tree structure on each equivalence class;
- A permutation structure on the set of equivalence classes (each tagged by the periodic point at the root).
Conversely, these three data determine a function, and the correspondence is bijective.
- Remark: It’s not necessary to the proof, but let me add that by basic principles of generatingfunctionology, if is the egf for permutations [namely, ], and if is the egf for rooted trees, then is the egf for structures given by such triplets of data. Thus, by the bijective correspondence, we have
On the other hand, consider a tree structure on points, and suppose we also specify an ordered pair of such points , possibly equal. There is a unique path from to in , which I’ll call the spine (of the “bipointed tree”); call the points along that path, including and , vertebrae. Now, for each point , there is a unique shortest path from to the spine, terminating at a vertebra . The union of all such paths which terminate at a vertebra again forms a subtree rooted at . Again, the set of points is partitioned by the (underlying vertex sets of) , and the structure of a bipointed tree on an -element set [] is thus encoded [in bijective fashion] by
- An equivalence relation on [];
- A rooted tree structure on each equivalence class;
- A spine structure (that is, a linear ordering) on the roots which tag the equivalence classes.
However, the number of linear orderings on an -element set, , is the same as the number of permutations on that set. We conclude that the number of bipointed tree structures on an -element set is the same as the number of endofunctions, . And, voilà! the number of tree structures on the -element set must therefore be .
Note: regular solver Philipp Lampe, who submitted a solution similar to David’s, pointed out that there are no fewer than four proofs of Cayley’s theorem given in Aigner and Ziegler’s Proofs from The Book, which I referred to in an earlier post. At this point, I really wish I had that book! I’d be delighted if someone were to post one of those nice proofs in comments…
3. I’m not quite sure, but Sune’s solution just might be my current favorite, just because it makes obvious contact with the circle of ideas which embrace endofunctions, trees, and rooted trees (I think of the tuples there as endofunctions, or actually, partial endofunctions on -element sets). In any event, my sincere thanks go to David, Philipp, and Sune for their insightful responses.
Encouraged and emboldened (embiggened?) by the ingenuity displayed by some of our readers, I’d like to see what sort of response we get to this Problem of the Week:
Establish the following identity: for all natural numbers .
(Here we make the convention .) I find this problem tantalizing because it looks as if there should be some sort of conceptual proof — can you find one?
Please send your solutions to topological[dot]musings[At]gmail[dot]com by Wednesday, June 11, 11:59pm (UTC); do not submit solutions in Comments. Everyone with a correct solution gets entered in our Hall of Fame! We look forward to your response.
The last Problem of the Week elicited some diverse and creative responses; many thanks to all those who submitted a solution!
Three basic approaches emerged from the solutions we received, each shedding different light on the problem, so Vishal and I thought it appropriate to give a representative example of each. (This is consonant with established practice in other fora, notably the Problems and Solutions section of the American Mathematical Monthly, which we look to as our model.) Here they are:
1. (Method based on Gamma and Beta functions; composite solution due to Philipp Lampe [U. Bonn], Jöel Duet, and Rod Carvalho) For integers , it is well-known that the Beta function
admits an integral representation
(See for instance Andrews, Askey, and Roy, Special Functions, pp. 4-5.) From the first equation we have Now let ; then we have
Interchanging summation and integration, we get
There is a slight difficulty with uniform convergence of the series (which would justify such interchange), at least in the case . There are various ways of handling this; for example, we may establish the result directly as follows: by change of variables , we have
and the partial sum telescopes to
Since for , the last integral is bounded above by
which tends to zero as . Putting all this together, it follows that
as claimed.
2. (Method of repeated integration, due to Gantumur Tsogtgerel, UC San Diego): Put , and let . We have ; thus for , the series defining converges for , and the series defining converges for < . Observe that
for .
We have for We also have
which gives for . By continuity, we get . Further, for we have and
Therefore
where we have used the Cauchy formula for repeated integration. After a short integration by parts, this last expression evaluates to . This yields for .
3. (Method of telescoping series, due to Nilay Vaish)
First, note that
.
Therefore,
.
Remarks:
Method 1 was the most popular; it has the advantage that provided one is already familiar with the Beta function, the calculation is essentially a triviality [modulo the slight technical bump in the road noted above]. For those unfamiliar with this function, I can strongly recommend the beautiful text by Andrews, Askey, and Roy, mentioned above, where the Beta function occupies a central place.
Method 2 was essentially how I accidentally discovered the calculation of the series to begin with: by considering iterated antiderivatives of . This however was some years ago, and I am grateful to Gantumur for his elegant solution, which saved me the trouble of recalling the details! Incidentally, the Wikipedia article on the Cauchy formula (linked above) sketches a proof which implicitly invokes differentiation under the integral sign (a favorite technique of Feynman), but we can also think of it this way: the -dimensional volume of the simplex is , since there are possible linear orderings of coordinates of points in the -cube [] [], and each ordering gives a simplex congruent to all the others. Then the result follows by an application of the Fubini theorem.
Method 3 is in some sense the most elementary solution [e.g., it avoids integration], if one is fortunate enough to see the trick of writing the summands as differences, so that the series telescopes. From one point of view this trick may seem awfully slick, like a magician pulling a rabbit out of a hat. But, it can be made to look utterly natural in the context of discrete calculus (dealing with sequences instead of continuous functions , and with the difference operator instead of the derivative).
Discrete calculus may be built up in analogy with continuous calculus; here are some basic terms of the analogy:
- A basic identity of discrete calculus is the polynomial identity which restates the recursive identity that generates Pascal’s triangle: This is analogous to the identity of continuous calculus,
- The preceding observation suggests that the falling power is the discrete analogue of the ordinary power of continuous calculus. It satisfies the identity The discrete analogue of the identity is the identity
- The last identity may be used to motivate the definition of when is negative: from one quickly derives The identity holds for all integers
- The analogue of continuous integration is finite summation. Formally, introduce the following symbolism for discrete integration: if and is integral, The fundamental theorem of discrete calculus is that if This simply restates the method of telescoping sums.
Using discrete calculus, the solution could be expressed compactly as follows:
Letting , our answer is:
Update: Look for the ‘sexism’ video at the end of this post that essentially strengthens my argument about the media treatment meted out to a woman, who was/is as capable as any other candidate, running for a very high office in America, the world’s oldest democracy and whose founding fathers, as we learn from history, were the children of The Enlightenment!
———————————
With the Democratic primary race practically over now and knowing, as we all do, who the nominee is going to be, I just couldn’t resist writing a post on this one, having avoided writing anything about politics all this while.
Well, it was quite appalling to see/hear all these months that when it came to Hillary the discussions/commentaries in the so-called “mainstream” media were similar to ones that are generally heard in men’s locker rooms, while Obama has been treated almost like a God-like figure. And while Hillary’s “racist” remarks were dissected/analyzed with great relish, no one, it seemed to me, paid any particular attention to the disgusting misogynist remarks directed at her throughout the primary campaign season, with the result that the Democratic party has managed, or so it seems, to lose its grip over white women voters now. I have a feeling that this is going to cost the Democrats another general election. (Of course, I could be wrong; I am not a political “pundit”, after all!)
So much has my mother been miffed/angry at the blatant sexist remarks openly made in the media against Hillary that she has vowed now to vote for McCain this Fall. To her, the contest has “demonstrated” yet again that women still haven’t been able to break the glass ceiling in this male-dominated world. Is anyone listening to women voters like her?
A video sample:
In mathematical parlance, this is the only instance in which Left = Right, if you know what I mean.
Recent Comments