Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

May 31, 2011

Möbius Inversion for Categories

Posted by Tom Leinster

Every small category AA has a classifying space BAB A. It’s a topological space, and it can be constructed as the geometric realization of the nerve of AA.

The homotopy type of BAB A depends on every aspect of AA: its underlying directed graph, its composition, and its identities. But the Euler characteristic of BAB A does not: it only depends on the underlying graph. What’s going on?

Last week I gave a talk about this at a conference in Louvain-la-Neuve, Belgium. I’ll also be doing a shorter version at the major annual category theory meeting in Vancouver. So, I’d be grateful for any comments, suggestions or thoughts. The slides are here.

(If the title slides mystify you, what you need to know is that the conference marked the appointment of Ross Street to a visiting chaire.)

As you’ll have surmised from the title, my answer was all about Möbius inversion. Let me explain…

In 1832, August Ferdinand Möbius introduced the number-theoretic Möbius inversion that crops up in elementary (and not so elementary) number theory. In modern language, we might say that the original Möbius inversion takes place in the poset of positive integers, ordered by divisibility.

In the mid-20th century, Möbius inversion was generalized to arbitrary posets. Several people came up with this idea, but it’s usually associated with the name of Gian-Carlo Rota, who demonstrated its importance in enumerative combinatorics.

(I tell a small lie: instead of ‘arbitrary posets’, I should say ‘arbitrary posets satisfying a suitable finiteness condition’. I told a similar lie when speaking of the Euler characteristic of BAB A, since it won’t have a well-defined Euler characteristic unless AA satisfies some finiteness condition.)

The stage was then set for generalizing from posets to (suitably finite) categories. This was done in two distinct ways.

First, there’s what I refer to in the slides as fine Möbius inversion. You can find the definition there. Here I just want to mention a couple of its features. For a category AA to have fine Möbius inversion means that there’s a fine Möbius function, that is, a function

μ:arr(A)k \mu: arr(A) \to k

satisfying certain equations. Here arr(A)arr(A) is the set of arrows of AA and kk is a commutative ring over which we’ve chosen to work. Whether a category has fine Möbius inversion does depend on its composition and identities, as does the fine Möbius function (if it exists).

Second, there’s what I call coarse Möbius inversion. For a category AA to have coarse Möbius inversion means that there’s a coarse Möbius function, that is, a function

μ:ob(A)×ob(A)k \mu: ob(A) \times ob(A) \to k

satisfying certain equations. Here ob(A)ob(A) is the set of objects of AA. Whether a category has coarse Möbius inversion does not depend on its composition and identities, and nor does the coarse Möbius function (if it exists).

All of this is described in more detail in the slides. References are on the final page.

What has this got to do with Euler characteristic? Well, it’s a theorem that if AA has coarse Möbius inversion (and is suitably finite) then

χ(BA)= a,bμ(a,b). \chi(B A) = \sum_{a, b} \mu(a, b).

This result appeared in my first paper on Euler characteristic of categories. Since the right-hand side is independent of the composition and identities in AA, so is the left-hand side.

(I should add that it’s also easy to show directly that χ(BA)\chi(B A) is independent of composition and identities, at least under the usual finiteness assumptions. None of the proofs here are in any way difficult; it’s just a matter of trying to arrange things for maximum insight.)

But also, coarse and fine Möbius inversion are related as follows. If a category has fine Möbius inversion then it also has coarse Möbius inversion. Moreover, the coarse Möbius function is determined by the fine one:

μ(a,b)= f:abμ(f). \mu(a, b) = \sum_{f\colon a \to b} \mu(f).

So for a category with fine Möbius inversion, we also have

χ(BA)= farr(A)μ(f). \chi(B A) = \sum_{f \in arr(A)} \mu(f).

The right-hand side appears to depend on the composition and identities in AA, but, being equal to the left-hand side, does not.

Posted at May 31, 2011 9:03 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2403

105 Comments & 1 Trackback

Re: Möbius Inversion for Categories

What a coincidence! Yesterday I happened to be thinking about Möbius inversion in the context of entropy! It turns out that mutual information can be generalized to interaction information, and this latter concept arises from a Möbius inversion on a poset. Since mutual information is of central importance in many applications of information theory, this might be an interesting example of Möbius inversion.

So let RR be a finite set of random variables. The relevant poset is the power set 2 R2^R. Any subset of variables SRS\subseteq R has a joint entropy H(S)H(S), which is the ordinary entropy of the joint distributions of the variables in SS. For any TSRT\subseteq S\subseteq R, we define the conditional entropy

H(S|T)=H(S)H(T) H(S|T) = H(S) - H(T)

and then H(|)H(\cdot|\cdot) is an element of the incidence algebra of the poset 2 R2^R. If we now consider H*μH\ast \mu and take the first argument to be the empty set, we recover precisely the formula for interaction information:

(H*μ)(,V)= TV(1) |VT|H(T) (H\ast \mu)(\emptyset, V)=\sum_{T\subseteq V}(-1)^{|V\setminus T|}H(T)

Now on to the question: given any commutative diagram in FinProb\Fin\Prob (in terms of a functor CFinProbC\rightarrow\Fin\Prob from some finite category CC), is there a way to talk about the entropy associated to the diagram?

The mutual information H(X)+H(Y)H(XY)H(X)+H(Y)-H(XY) should be a special case of such a construction where the diagram consists of the two morphisms (X,Y)X(X,Y)\rightarrow X and (X,Y)Y(X,Y)\rightarrow Y. Here, (X,Y)(X,Y) is the joint distribution of the random variables XX and YY, and I don’t distinguish between distributions of random variables and probability spaces.

Okay, as John just said there are many possible routes for continuing on the entropy business, so this is just yet another question wanting to be pursued…

Your talk and Wikipedia call the constant function the zeta function. Is there a particular reason for this term?

Posted by: Tobias Fritz on May 31, 2011 11:13 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Thanks for this, Tobias. For now I’ll just answer the bit I can answer easily:

Your talk and Wikipedia call the constant function [with value 1] the zeta function. Is there a particular reason for this term?

Yes. It’s a zeta as in Riemann. It might seem funny to use the same name for the mighty Riemann ζ\zeta and the humble function with constant value 1, but there’s a good reason, as follows.

First — and I know you know this, but I’ll say this for others — any two sequences of integers α,β: + \alpha, \beta: \mathbb{Z}^+ \to \mathbb{Z} have a kind of convolution product α*β\alpha * \beta, defined by (α*β)(n)= m|nα(m)β(n/m). (\alpha * \beta)(n) = \sum_{m | n} \alpha(m) \beta(n/m). This product is associative, with unit δ\delta defined by δ(n)={1 ifn=1 0 otherwise. \delta(n) = \begin{cases} 1 &if n = 1\\ 0 &otherwise. \end{cases} Note in particular that δ\delta does not have constant value 1.

Now we bring in the idea of generating function, memorably described by Herb Wilf:

A generating function is a clothesline on which we hang up a sequence of numbers for display.

There are ordinary generating functions α(n)x n\sum \alpha(n) x^n, and exponential generating functions α(n)x n/n!\sum \alpha(n) x^n/n!, each defined for any sequence α\alpha. But in the same spirit, we can also write down the (formal) Dirichlet series associated to α\alpha, namely n=1 α(n)n s \sum_{n = 1}^\infty \frac{\alpha(n)}{n^s} where ss is a ‘symbol’, or a ‘formal variable’, or whatever you want to call it. And the point is that convolution of sequences corresponds to multiplication of Dirichlet series: (α*β)(n)n s=(α(n)n s)(β(n)n s). \sum \frac{(\alpha * \beta)(n)}{n^s} = \Bigl( \sum \frac{\alpha(n)}{n^s} \Bigr) \Bigl( \sum \frac{\beta(n)}{n^s} \Bigr). Similarly, for the unit, δ(n)n s=1. \sum \frac{\delta(n)}{n^s} = 1. Abusing notation, we might end up using the same letter for a sequence and its corresponding Dirichlet series. Since the Riemann zeta function is ζ(s)= n=1 1n s, \zeta(s) = \sum_{n = 1}^\infty \frac{1}{n^s}, that means using ζ\zeta for the sequence constant at 1.

This also explains one of the formulas in my slides, 1/1n s=μ(n)n s. 1\Bigl/ \sum \frac{1}{n^s} = \sum \frac{\mu(n)}{n^s}. For the defining property of μ\mu is that μ*ζ=δ\mu * \zeta = \delta, so, converting everything into Dirichlet series, (μ(n)n s)(ζ(n)n s)=1, \Bigl( \sum \frac{\mu(n)}{n^s} \Bigr) \Bigl( \sum \frac{\zeta(n)}{n^s} \Bigr) = 1, which is what the formula says.

Posted by: Tom Leinster on May 31, 2011 11:36 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Woohoo, thanks! Suddenly the subject of analytic number theory makes a lot more sense to me.

Posted by: Tobias Fritz on May 31, 2011 12:28 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I only just noticed something about Dirichlet series versus ordinary generating series. The ordinary generating series (or function) of a sequence α\alpha is n=1 α(n)x n. \sum_{n = 1}^\infty \alpha(n) x^n. In the expression for Dirichlet series, it would make no essential difference if we changed ss to s-s. (As far as I know — which isn’t very far — it’s just a matter of convention.) And writing x=sx = -s, the Dirichlet series for α\alpha becomes n=1 α(n)n x. \sum_{n = 1}^\infty \alpha(n) n^x. These two expressions are pleasingly symmetric!

Posted by: Tom Leinster on May 31, 2011 12:39 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Tom wrote:

I only just noticed something about Dirichlet series versus ordinary generating series.

I noticed that too, once. It started out seeming just ‘cute’. But then it revealed some deeper aspects, and James Dolan and I wrote a paper about it, called Zeta functions. I’ll quote the beginning to whet your interest, or maybe at least someone’s interest:

In this paper we begin categorifying the theory of zeta functions. As a precursor, we must understand how to get a Dirichlet series from a species. This is a very nice counterpart to the usual recipe for computing a formal power series from a species, namely its generating function.

Briefly, a species is any type of structure that one can put on finite sets: for example, a coloring, or ordering, or tree structure. Suppose FF is some such structure. If we denote the set of FF-structures on the nn-element set by F(n)F(n), the generating function of FF is the formal power series |F|(x)= n0|F(n)|n!x n. |F|(x) = \sum_{n \ge 0} \frac{|F(n)|}{n!} x^n \, . On the other hand, the Dirichlet series associated to FF is
F¯(s)= n1|F(n)|n!n s. \overline{F}(s) = \sum_{n \ge 1} \frac{|F(n)|}{n!} n^{-s} \, . Far from being ad hoc tricks, the generating function and the Dirichlet series fit into a nice unified theory, which we shall explain here.

Of course calling the exponent ‘s-s’ is just a convention; we could call it ‘xx’ if we wanted. The more important thing is that generating functions get along with the Cauchy product of species, while Dirichlet series get along with the Dirichlet product.

The ‘Cauchy product’ of species is the one you probably knowif you’ve ever heard of species and how to multiply them. It goes sort of like this:

(F CG)(n)= k+k=nF(k)×G(k) (F \cdot_{C} G)(n) = \sum_{k + k' = n} F(k) \times G(k')

The ‘Dirichlet product’ goes sort of like this:

(F DG)(n)= k×k=nF(k)×G(k) (F \cdot_{D} G)(n) = \sum_{k \times k' = n} F(k) \times G(k')

I say ‘sort of like this’ because it’s easy to misinterpret these formulas unless you read our paper. But the point is that the Cauchy product involves the usual ++ operation on finite sets, while the Dirichlet product involves the usual ×\times operation.

And, the Cauchy product gets along with generating functions:

|F CG|=|F||G| |F \cdot_{C} G| = |F| |G|

while the Dirichlet product gets along with the Dirichlet series:

F DG¯=F¯G¯ \overline{F \cdot_{D} G} = \overline{F} \overline{G}

(For know-it-alls: the groupoid of finite sets is a rig category in an obvious way, so it has two monoidal structures, so the category of presheaves on this groupoid gets two monoidal structures, thanks to Day convolution. These presheaves are called ‘species’, and these two monoidal structures on species are called the Cauchy and Dirichlet product.)

Tobias wrote:

Woohoo, thanks! Suddenly the subject of analytic number theory makes a lot more sense to me.

That’s how I felt when Jim figured out how to understand Hasse-Weil zeta function of a scheme using this viewpont. All that stuff about Dirichlet series and L-functions is a lot less ad hoc than it sounds at first. And ‘the Hasse-Weil zeta function of a scheme’ is a lot less scary than it sounds at first: we explain it in our paper.

Posted by: John Baez on June 1, 2011 6:45 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Thanks John; I like the look of your paper with Jim. I was dimly aware of it, but perhaps I’ll get round to reading it one of these days.

Posted by: Tom Leinster on June 1, 2011 10:38 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

If you don’t care much about number theory, the main thing to remember is short and sweet: the rig category structure on the groupoid of finite sets makes species into a rig category thanks to Day convolution. And this, it turns out, is what unites generating functions and Dirichlet series.

We tend to think of generating functions as related to combinatorics, and Dirichlet series as related to number theory. But this is because combinatorists prefer adding finite sets, while number theorists get more excited about multiplying them. (Primes and all that.)

Posted by: John Baez on June 1, 2011 11:15 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

That was actually the main thing I got from your previous message. It stoked my enthusiasm. (The first time I read your message, though, I skipped the paragraph headed “For know-it-alls”, because who wants to be a know-it-all?)

Posted by: Tom Leinster on June 1, 2011 11:19 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Hi Tom,

all this Moebius stuff is very interesting! I look forward to hear more about it.

But here is just some advertisement:

In case anybody is interested, I have on my web page a short introduction to Moebius inversion — very basic stuff, but including a neat conceptual proof of Euler’s product expansion of Riemann’s zeta function. (It’s from a seminar talk last year which I meant to type up. The second part was about Leroux-Menni theory, but that’s not in the note (yet).)

See “Incidence Hopf Algebras” on the page
http://mat.uab.cat/~kock/upcoming.html

Cheers,
Joachim.

Posted by: Joachim Kock on June 3, 2011 12:58 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Hi Joachim. Thanks for the link: I like the look of your notes.

(There’s a typo on page 1, in the Euler formula for the zeta function.)

Here’s a question. Do people ever use a Fourier-transform-type notation for the Dirichlet series associated to an arithmetic function? If we write

f^(s)= n1f(n)n s \hat{f}(s) = \sum_{n \geq 1} \frac{f(n)}{n^s}

then

(f*g)^=f^g^, \widehat{(f \ast g)} = \hat{f} \cdot \hat{g},

as for Fourier transforms. (That formula doesn’t render too well on my browser, but I hope it’s clear what I mean.) This analogy must have been obvious to people for donkeys’ years. Bt I have no idea how far it goes or how useful it is.

Posted by: Tom Leinster on June 3, 2011 10:44 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Tobias wrote:
is there a way to talk about the entropy associated to the diagram?

If consider morphisms as a process of construction of the codomain object , if the domain object alredy exist(as a result of previous construction). Every such morphism result in entropy production. Then the diagram building is a loops product with non nessesary trivial “information curvature” because of loops’ lengths(process time, constructive homotopy time, that produce the measure).
This “information curvature” may be associated to a diagram.

Posted by: Maxim Budaev on May 31, 2011 3:09 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Maxim, I’m not sure you’re answering Tobias’s question. At least, I don’t see an answer in your comment. What Tobias means by a diagram is (as he says) a finite category CC together with a functor D:CFinProbD: C \to FinProb. Can you give a precise definition of the entropy of DD?

Posted by: Tom Leinster on May 31, 2011 3:34 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Yes, of course.
Precise definition here “Entropic Memory, Attractors’ Category”
Rougly, this is the outcome counting measure on set respect to the outcomes generating process.
This is purely constructive approach to the category theory:
object exists if it had been constructed by means some morphism, and pre ergodic considerations.

Posted by: Maxim Budaev on May 31, 2011 4:42 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Maxim, to save us all reading your paper, could you tell us what your definition of the entropy of a diagram gives in the following simple example? Thanks.

Let CC be the category with two objects, 0 and 1, and a single non-identity arrow, u:01u: 0 \to 1. Then a functor D:CFinProbD: C \to FinProb amounts to:

  • a finite set XX equipped with a probability measure pp
  • a finite set YY equipped with a probability measure qq
  • a measure-preserving map f:(X,p)(Y,q)f: (X, p) \to (Y, q).

What, according to your definition, is the entropy of DD?

Posted by: Tom Leinster on June 1, 2011 10:42 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

The entropy of this functor(endomorphism in the Attractors’ Category considered as one object category) is:

H(f)~(log|Y|-H(q))-(log|X|-H(p))

log|set|-H(P(set)) convex functional minimal on equidistribution on the set.

If these distributions are metastable for the outcome counting process.

But it is very simple example.
More interesting to consider process of natural transformations of such functors(n-morphisms).
Or more complex diagrams(commutative diagrams, associativity condition diagram).

Posted by: Maxim Budaev on June 1, 2011 1:06 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

OK, thanks. Let me just make sure I understand correctly: you assign to the measure-preserving function

f:(X,p)(Y,q) f: (X, p) \to (Y, q)

an “entropy”

H(f)=(log|Y|H(q))(log|X|H(p)). H(f) = (log |Y| - H(q)) - (log |X| - H(p)).

Here, presumably, |X||X| is the cardinality of the set XX.

I’m only asking you to confirm this because you used an approximation sign \sim rather than an equality sign.

Assuming I’ve understood correctly, this is different from our “information loss”, which is simply

H(p)H(q). H(p) - H(q).

For example, let X={a,b}X = \{a, b\} be a two-element set and pp the probability measure on XX such that aa has measure 11 and bb has measure 00. Let Y={c}Y = \{c\}, with its unique probability measure. Let f:XYf: X \to Y be the unique measure-preserving function. Then your definition gives

H(f)=(log10)(log20)=log2 H(f) = (log 1 - 0) - (log 2 - 0) = -log 2

whereas our information loss is

00=0. 0 - 0 = 0.

Maxim wrote:

But it is very simple example.

Sure, it’s a very simple example, but very simple examples help us to understand what’s going on. For instance, it already seems to have told us that your quantity and ours are not the same.

Posted by: Tom Leinster on June 1, 2011 1:21 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Excuse me. I forget to define ||.
By |set| I mean cardinality of the measure support
may be better |P(set)|
now no contradictions.

I consider constructive approach.
Then morphism is an algorithm of (re)construction of codomain object.
If the domain object already exists.
This is some kind of measure transformation by means of outcome counting.
This process has the time-number of valuation until codomain (re)construct.
I prefer characterize morphisms by this time(natural or rational).
Then where is simple representation for n-morphisms

If the process(algorithm) depends on current entropy(defined) then appears the Entropic Memory.
Objects are classified by complexity(entropy).
And by the time of construction-familiar is simple(need no more time for reconstruction).

The class of “simple objects”(respect to current entropy) is a “near associative” subcategory.
I name it by the coherent superobject.
This mean that morphisms are “short”(in time sense) and actualy not depends on order of valuations.
But “near” is important part. The Coherent superobject may “condensed” in singular object.
This is “choice” of the class representative or conjugation for entropy functor.
Or sclerosis-rare event-return in the “complexity spectrum”.

These lead to some kind of convergence-filtration by complexity.
The search for greater complexity with the Entropic Memory:
familar-simple-no interest-deserve no attention(time for reconstruction).

Posted by: Maxim Budaev on June 1, 2011 3:32 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Maxim wrote:

Excuse me. I forget to define |||\cdot|. By |set||set| I mean cardinality of the measure support. […] Now no contradictions.

OK, but it’s still not going to be the same as the quantity we’re currently interested in, information loss. For instance, you could take the example I gave but change pp so that it gives nonzero measures to each of aa and bb. Then your H(f)H(f) will be H(p)log2H(p) - \log 2, whereas our information loss will be H(p)H(p).

Posted by: Tom Leinster on June 1, 2011 4:06 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

This is may view on Tobias’ question about diagrams and entropy.
I find this is very interesting in context of the categorification.

Our entropies the same in some cases.
This is one of reasons for ~.
Your choices of exotic distribution (X,P) in my point of view the current metastable attractor(singular, coherent) in the entropy spectrum.
Morphism to (Y,Q)is the actual coherent-singular intermittency chain-diagram in the entropy spectrum. Degeneracy of the permutation symmetry delooping by the entropic memory.

Posted by: Maxim Budaev on June 1, 2011 5:27 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Although Maxim’s definition is indeed not what we have been considering so far, it may possibly still be a natural thing to do. If D(||)D(\cdot||\cdot) stands for the relative entropy (or Kullback-Leibler divergence) between probability measures on XX and u Xu_X is the uniform probability measure on XX, then we have, for any other probability measure pp on XX,

D(p||u X)= ip ilogp i1/|X|=log|X|H(p) D(p||u_X)=\sum_i p_i \log\frac{p_i}{1/|X|}=\log|X|-H(p)

This is the kind of terms that Maxim uses. So instead of considering differences of entropies as we do, he takes differences of relative entropies.

Maxim, which entropy value does your definition assign to a commuting triangle in FinProb\Fin\Prob? If we have probability spaces (X,p)(X,p), (Y,q)(Y,q) and (Z,r)(Z,r) together with measure-preserving functions f:XYf:X\rightarrow Y, g:YZg:Y\rightarrow Z and gf:XZgf:X\rightarrow Z, which value do you get?

And what does it assign to the diagram consisting of two measure-preserving functions h:(Z,r)(X,p)h:(Z,r)\rightarrow (X,p) and k:(Z,r)(Y,q)k:(Z,r)\rightarrow (Y,q)?

Posted by: Tobias Fritz on June 1, 2011 4:45 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

This depends from the history of process.
I assign to diagram the 2-morphism time(rational), what may be estimate as:

tt=t(f)-t(g)~ (L(Z,r)-L(X,p))/(H(X,p)+log(max(p))-(L(Z,r)-L(Y,q))/(H(Y,p)+log(max(q))

L==Lambda(set,P(set))~log|set|-H(P(set)).

This is very rough. In paper you may find more interesting diagrams that illustrate effects induced by the entropic memory. “Dissolving” short loops, for example.

Posted by: Maxim Budaev on June 1, 2011 7:22 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Maxim, I suspect I’m not alone in finding this impossible to understand. I’m afraid I found your paper impossible too.

But let’s see if we can make some progress. You said that you had a precise definition of the entropy of a diagram. Here “diagram” means a finite category CC together with a functor CFinProbC \to FinProb.

You told us what your definition gives in the case that CC is the category consisting of a single arrow. It was a little confusing because of your use of \sim rather than ==: the \sim sign suggests approximation, whereas you’d told us you had a precise definition.

Tobias just asked you two questions:

  1. what, according to your definition, is the entropy of a commutative triangle (X,p) f (Y,q) gf g (Z,r) \begin{matrix} (X, p) &\stackrel{f}{\to} &(Y, q) \\ &g f \searrow &\downarrow g\\ & &(Z, r) \end{matrix} in FinProbFinProb?
  2. what, according to your definition, is the entropy of a diagram (Z,r) h (X,p) k (Y,q) \begin{matrix} (Z, r) &\stackrel{h}{\to} &(X, p)\\ k\downarrow& & \\ (Y, q) & & \end{matrix} in FinProbFinProb?

You don’t say which question you’re answering, but as you mention ff and gg and not hh or kk, I assume it’s (1).

Here are some things that are hard to understand about the answer you just gave:

  • you use the letter tt without saying what it means.
  • you use Lambda without saying what it means.
  • you use “set” without saying what it means. (Which set?)
  • you use “P(set)” — but maybe that’s OK for readers who’ve really been paying attention, because what you wrote here suggests that by that you mean the support of the measure on the set concerned. (It’s not good notation, though.)
  • You use max(p)max(p) and max(q)max(q) without saying what they mean.
  • You use \sim, and say “this is very rough”, when you’d previously claimed to have a precise definition.
  • You write “I assign to diagram the 2-morphism time(rational)”. I’m afraid I can’t begin to understand this. I know very well what a 2-morphism is, but I don’t know what you mean by “2-morphism” here. 2-morphisms live in 2-categories, and you haven’t said which 2-category you’re referring to.

I don’t want to have a general discussion, but I did want to explain why we’re having trouble understanding you.

Posted by: Tom Leinster on June 2, 2011 6:22 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I was sure that format of paper more appropriate than web.
But in any case I am happy for any questions.
Thanks for “The n-Category Cafe”!

…suggests approximation, whereas you’d told us you had a precise definition.
I told:
…This “information curvature” may be associated to a diagram.

Information curvature is the dynamical variable-components of natural transformation.

This is FinProp generating process with complicated evolution.
The definitions of convergence and limits are separate interesting themes.
“Precise definition”-current(actual) state of the process.
We may only to estimate of effects of this process.
In categorical point of view this is some sort of a weak-n category of the constructive order.

…Tobias just asked you two questions:

Yes. In fact I had answered on first. But need some definitions from paper for details.

t-time of morphism
tt-time of 2-morphism
Lambda I name log||-H in paper there is greek font.

I was using “set” for simplicity. Actually I mean finite category with internal structure. P(set) constructive measure on objects now.

Excuse my for my English.

Posted by: Maxim Budaev on June 2, 2011 9:57 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

OK, thanks. I’m afraid I still don’t understand what your definition is, but if you’re happy to finish the conversation here, that’s fine with me.

Posted by: Tom Leinster on June 2, 2011 10:30 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Not that it matters much, but I find it a bad idea to write “BAB A” for the geometric realization of a category AA. I also find it a bad idea to call it the “classifying space” of the category. I know that there is a tradition to do both of this. But there is also a tradition not to do this. I think the latter opens doors, where the former closes them.

I think the geometric realization of a category AA is best denoted |A||A| and best called this: the geometric realization. The nerve operation is something one can entirely suppress notationally without danger. I think for AA a monoid one should write BAB A for the corresponding 1-object category: the delooping of AA.

The tradition of writing “BAB A” for the geometric realization of a category AA and calling it the “classifying space” of the category originates from the dubious move of conflating a group GG with its one-object groupoid that in homotopy theory has been written BGB G since the dawn of time. I know that in 1-category theory texts the BB here tends to be forgotten. But I think it is a bad move that leads to lots of clashes later on and makes a beautiful general theory look unnecessarily obscure.

As I said, not that it matters much here. Maybe I am just saying it in case some young student comes around here and starts to wonder about the notation.

Posted by: Urs Schreiber on May 31, 2011 7:58 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

While I love to say that a group is a one-object category, just to annoy Urs, I agree with him that ‘BB’ should be reserved for various kinds of ‘delooping’ process where nn-morphisms get reinterpreted as (n+1)(n+1)-morphisms… the classic example being where the points of a topological group GG get reinterpreted as loops in its classifying space BGB G. Points are like objects, loops are like morphisms, so BB is reinterpreting objects as morphisms.

For beginners who are still wondering why BB is called ‘delooping’, the point here is that we get a nice homotopy equivalence

GΩBGG \simeq \Omega B G

where Ω\Omega is the based loop space of a pointed space. So, BB undoes the effect of Ω\Omega, which is called ‘looping’.

I also agree with Urs that the geometric realization of the nerve of a category should be called |NA||N A| or just |A||A| if you’re feeling more relaxed.

(And it’s not just Urs and I who think this; these usages are pretty common—though Tom’s use of BAB A for the geometric realization of the nerve of a category AA is also common, I guess. This clash of conventions confused the heck out of me when I was just getting started.)

Posted by: John Baez on June 1, 2011 10:07 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

There seem to be three different customs here.

Some people, like Urs, call |NA||N A| the geometric realization of AA. This amounts to treating NN as a nameless inclusion, or silently regarding a category as a simplicial set.

Some people call |NA||N A| the nerve of AA. This amounts to treating |||\cdot| as a nameless inclusion, or silently regarding a simplicial set as a topological space.

Some people, like me, call |NA||N A| the classifying space of AA. I guess that custom came about through silently regarding a monoid as a one-object category.

People also seem to use BB in all sorts of different ways. To add another to those that have been mentioned so far, the notation BG\mathbf{B} G for the topos of GG-sets is used in Mac Lane and Moerdijk’s topos theory book and in Moerdijk’s book on classifying spaces and classifying toposes.

Urs, this puzzles me:

a group GG with its one-object groupoid that in homotopy theory has been written BGB G since the dawn of time.

I had the impression that in homotopy theory, BGB G had denoted the classifying space of GG (I mean an actual topological space) since the dawn of time?

Posted by: Tom Leinster on June 1, 2011 10:52 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Urs, this puzzles me:

I know. ;-)

I had the impression that in homotopy theory, BGB G had denoted the classifying space of GG (I mean an actual topological space) since the dawn of time?

No, that’s what it means in topology. In homotopy theory it means the object presented by that topological space in the homotopy category Ho(Top)Ho(Grpd)Ho(Top) \simeq Ho(\infty Grpd) (or better in the \infty-category Grpd\infty Grpd of which this is the decategorification). Under the fully faithful inclusion

Ho(Grpd)Ho(Top 1Types)Ho(Top)Ho(Grpd) Ho(Grpd) \simeq Ho(Top_{1Types}) \hookrightarrow Ho(Top) \simeq Ho(\infty Grpd)

it is identified precisely with the one-object groupoid given by GG.

(Here we are regarding GG as a discrete group. We can generalize this discussion to the case where GG is some cohesive group and \infty-groupoids are generalized to cohesive \infty-groupoids, but let’s not do that right now.)

Posted by: Urs Schreiber on June 1, 2011 12:17 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Got you: thanks.

And I forgot to say it before, but thanks also for the feedback. As the next version of this talk will be to an audience of category theorists, I’ll probably stick with the same notation and terminology. I’m fairly confident that most category theorists do use BB and “classifying space” in the way I do, rightly or wrongly, and as it’s only a small part of the talk I don’t want to create a distraction by using conventions that they’ll regard as non-standard. Nevertheless, it’s good for me to understand different viewpoints, and perhaps I’ll say a few words on that in the talk.

Posted by: Tom Leinster on June 1, 2011 12:28 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Actually, Urs, I believe that, even if BG means what you say in “homotopy theory”, most homotopy theorists (at least old-fashioned ones like me!) probably do use BG to denote an honest topological space of the homotopy type of the geometric realization of the nerve of G. Most probably even have a favorite explicit topological construction in mind when they write BG.

Posted by: Kathryn Hess on June 1, 2011 2:35 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Dear Kathryn, you write:

most homotopy theorists (at least old-fashioned ones like me!) probably do use BGB G to denote an honest topological space of the homotopy type of the geometric realization of the nerve of GG. Most probably even have a favorite explicit topological construction in mind when they write BGB G.

Yes, but what I tried to say is: these various explitic topological spaces will not be homeomorphic to each other, generally, but just weakly equivalent. Still they are regarded as explicit constructions of the same abstract object. Therefore they are regarded not in the topologist’s category but in the homotopy theorist’s category. That happens to be canonically equivalent to Ho(Grpd)Ho(\infty Grpd) and all the different explicit models for BGB G correspond to one and the same equivalence class in there: that of the one-object groupoid with GG as its set of morphisms (which one may regard of course itself just as one further explicit model).

And this is really the definition of BGB G. This space is not defined to be any of these models, such as |N{g|gG}||N\{\bullet \stackrel{g}{\to} \bullet | g \in G\}|. It is defined to be the homotopy type such that Ho(Top)(X,BG)GBund(X)Ho(Top)(X, B G) \simeq G Bund(X). This definition does not single out a topological space. But under the equivalence Ho(Top 1Type)Ho(Grpd)Ho(Top_{1Type}) \simeq Ho(Grpd) it does single out a groupoid. So that groupoid should be called BGB G.

I believe what we see here is a basic phenomenon of category theory, really: given a category, it matters little how we think about its objects, and any way we do can be quite misleading. The only thing that counts is what the isomorphisms do. I can build a category whose objects are varieties of green cheese with extra structure. If it is equivalent to Ho(Grpd)Ho(\infty Grpd), then I should think of its objects as being \infty-groupoids, not cheese.

Posted by: Urs Schreiber on June 1, 2011 4:06 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I can build a category whose objects are varieties of green cheese with extra structure. If it is equivalent to Ho(∞Grpd), then I should think of its objects as being ∞-groupoids, not cheese.

Well, you could think of its objects that way. But you could also use that equivalence to think of ∞-groupoids as being cheese. Don’t let’s be prejudiced to read equivalences in one direction only. (-:

So that groupoid should be called BG.

I agree entirely that that groupoid should be called BG. But it is a different thing to say that that groupoid “has been called BG since the dawn of time”. Even though now we know that groupoids should be identified with homotopy 1-types, and that homotopy theory can be regarded as being really about ∞-groupoids, the homotopy theorists back at the dawn of time did not think like that (and some still don’t). So instead of saying “the one-object groupoid that in homotopy theory has been written BG since the dawn of time” I think it would be more correct to say “the one-object groupoid which, with the advantage of modern language and hindsight, we can now see should be identified with the homotopy 1-type presented by the objects that in homotopy theory have been denoted BG since the dawn of time.”

I’m fairly confident that most category theorists do use B and “classifying space” in the way I do, rightly or wrongly, and as it’s only a small part of the talk I don’t want to create a distraction by using conventions that they’ll regard as non-standard.

Can I also make a try to convince you to do otherwise? I can’t really say about what most category theorists do, since I guess I tend to hang out more with nn- and ∞-folks, but the only way that we can change the use of bad terminology is by not using it. If it were really a question of “non-standard” terminology, that would be one thing, but the phrase “geometric realization of the nerve” also consists of completely standard words that have no possible alternative meaning in this context.

And actually, I don’t object as strongly to the phrase “classifying space,” because the geometric realization of a category does classify something related to that category (flat diagrams of sheaves, module concordance). It’s just the notation “B”, and especially the concomitant identification of groups with one-object groupoids, that I find produces needless confusion. (In particular, identifying groups with one-object groupoids, rather than with pointed one-object groupoids, is what leads people to think that there’s some sort of problem with the delooping hypothesis. I feel like a broken record mentioning this again, but the myth never seems to die.)

Posted by: Mike Shulman on June 1, 2011 7:15 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Mike wrote:

Can I also make a try to convince you to do otherwise?

Sure. I’m open to persuasion, just not persuaded.

the only way that we can change the use of bad terminology is by not using it

Absolutely. I think I’ve done my fair share of trying (usually unsuccessfully) to banish what I regard as bad terminology by not using it.

I have no objection to “geometric realization of the nerve” except that it’s a bit long. The same goes for |NA||N A| instead of BAB A.

To my ear, “geometric realization of AA” and “nerve of AA” (for |NA||N A|) both sound wrong, in the sense of not type-checking. You take geometric realizations of simplicial sets (or other presheaves), not categories, and the nerve is a simplicial set, not a topological space. More generally, I think of “realization” as a left adjoint, which what I call BB isn’t.

As I said before, each of these customs amounts to not mentioning one inclusion or another. (I don’t know whether it’s really correct to refer to ||:SSetTop|\cdot|: SSet \to Top as an inclusion, but that’s what I mean.) Of course we all elide inclusions all over the place.

If I understand correctly, you and Urs object to not mentioning the inclusion from monoids into categories. To me, this is the more interesting point, because category theorists do this all the time. What exactly is the problem here? Obviously there are some contexts where it does need mentioning, e.g. if you’re discussing the periodic table. (Ross Street used to, and maybe still does, use the suspension sign Σ\Sigma to denote the process of turning a monoidal nn-category into an (n+1)(n + 1)-category, etc.) But if the meaning’s clear, what’s the problem?

Posted by: Tom Leinster on June 2, 2011 6:52 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

My point is that the functor from (the category of) monoids to (the 2-category of) categories is not an inclusion, so it is more dangerous to omit to mention it. (It is fully faithful on 1-morphisms, but not on 2-morphisms.) This may not be a big deal in some contexts, but the letter “B” is only one keystroke. (I don’t like the use of Σ\Sigma for this operation either, because in topology Σ\Sigma is the left adjoint to the functor Ω:\Omega\colon pointed spaces \to pointed spaces, whereas BB is the inverse of the functor Ω:\Omega\colon pointed spaces A \to A_\infty-spaces.)

Is |NA||N A| really that much longer than BAB A? It’s two more keystrokes, and less than two more characters’ width.

I probably wouldn’t say “nerve of AA” for |NA||N A| in a context where it really matters that |NA||N A| is a topological space rather than a simplicial set. I might say “geometric realization of the nerve” the first time I use it, and “geometric realization” thereafter. On the other hand, in a context where all that matters is the homotopy type of |NA||N A|, I see no reason not to just call it “the nerve”, since homotopy types are modeled just as well by simplicial sets, and |||-| is a no-op on homotopy types. I guess the Euler characteristic is sort of a boundary case—it’s homotopy invariant, so it’s a function on homotopy types, but one of the ways we compute it is with cellular decompositions.

Posted by: Mike Shulman on June 2, 2011 5:31 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

What’s a “no-op”?

Posted by: Tom Leinster on June 2, 2011 5:59 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Posted by: Mike Shulman on June 2, 2011 8:47 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

OK; I remember NOP from my programming days. So what you wrote means “|||-| is the identity on homotopy types”, right?

My point is that the functor from (the category of) monoids to (the 2-category of) categories is not an inclusion, so it is more dangerous to omit to mention it.

That’s a reasonable point, I think.

Do you feel the same way about the functor from the category of posets to the 2-category of categories?

Posted by: Tom Leinster on June 2, 2011 11:00 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

So what you wrote means “|||-| is the identity on homotopy types”, right?

Yes.

Do you feel the same way about the functor from the category of posets to the 2-category of categories?

That’s an interesting question. I don’t think I’ve ever had much reason to consider the 1-category of posets, as opposed to the 2-category (which is, of course, a (1,2)-category) thereof. I’d be interested to hear the opinion of someone who definitely had such a reason (if such a person exists).

In general, I think there’s less danger in conflating a (1,2)-category with its “underlying” 1-category than there is for a general 2-category or a (2,1)-category. Here by “underlying” I mean either to identify isomorphic 1-morphisms and then forget the 2-cells—which in the case of a 2-category this would maybe be better called its “homotopy” 1-category—or, in the case of a strict (1,2)-category whose hom-categories are posets (rather than preorders), to just forget the 2-cells. One of the nice things about (1,2)-categories is that it doesn’t matter which of those things you do, whereas it does for 2-categories: the 1-category Cat is different from the homotopy 1-category of the 2-category Cat, and similarly for its full subcategory on deloopings of monoids. Another nice thing is that conical 2-limits in a (1,2)-category are 1-limits in its homotopy 1-category, which is not true for 2-categories or (2,1)-categories. And so on.

One could also ask the same question about the functor from topological spaces (or locales) to the 2-category of topoi, and I would probably answer it in the same way, with the additional remark that most topological spaces and locales that many of us are used to thinking about are discrete objects (in the categorical sense) in the (1,2)-category thereof.

Posted by: Mike Shulman on June 3, 2011 12:58 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Mike wrote:

which is, of course, a (1, 2)-category

It took me a while to find out what you meant by “(1, 2)-category”, so to save others the time, here’s a link.

Posted by: Tom Leinster on June 3, 2011 10:51 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

You mean you didn’t immediately go to http://ncatlab.org/nlab/show/(1,2)-category? (-: (I think this is a slightly better link than the one you gave, as more specific.)

But yes, I should probably be less lazy about linking terms when they’re first introduced to a particular discussion. Sorry; I think I tend to assume unjustifiably that everyone around here knows about the (n,r) periodic table.

Posted by: Mike Shulman on June 3, 2011 4:42 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories


I’ve never heard of this use of (n,r)-category either. I’m currently finding it extremely confusing although I can see that it does in some sense make sense.

Posted by: Eugenia Cheng on June 3, 2011 5:05 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I assume the idea is that for n,k0n, k \geq 0, an (n+k,n)(n + k, n)-category can be viewed as an nn-category whose top-level hom-“sets” are in fact kk-groupoids. Now extending the idea to k=1k = -1 and using the principle that a 1-1-groupoid is a truth value, an (n1,n)(n - 1, n)-category is an nn-category whose top-level hom-sets have at most one element — it’s locally posetal at the top level.

Posted by: Tom Leinster on June 3, 2011 5:12 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I assume the idea is that …

Yes. A precise way to state it is this, inductively:

An (r,0)(r,0)-category is an \infty-groupoid that is rr-truncated (is an rr-groupoid).

For n1n \geq 1 an (r,n)(r,n)-category is an (,n)(\infty,n)-category CC such that for all objects X,YX, Y we have that C(X,Y)C(X,Y) is an (r1,n1)(r-1, n-1)-category.

Posted by: Urs Schreiber on June 3, 2011 6:00 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

There’s some discussion of (n,n+1)(n,n+1)-categories in the appendix to this paper, although the idea predates that.

Posted by: Mike Shulman on June 3, 2011 6:47 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

No, I didn’t; in fact, I hadn’t seen that page. What I did was to go to the nLab front page and then navigate my way through the contents, starting with higher category theory. And I didn’t see a specific page on (1, 2)-categories.

As it happened, I didn’t google it (I suppose because I was sure the information would be on the nLab). But trying it now, it doesn’t turn up on the first page, for me at least.

(And of course I know what an (n, r)-category is when r \leq n. It’s the case r > n that was new to me.)

Posted by: Tom Leinster on June 3, 2011 4:48 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

What I did was to go to the nLab front page and then navigate my way through the contents, starting with higher category theory. And I didn’t see a specific page on (1, 2)-categories.

The higher category table of contents did have the line

But I have now expanded this to

Posted by: Urs Schreiber on June 3, 2011 5:03 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

In case the implicit question isn’t clear, how could I have known that that page existed (apart from guessing the URL)? When I type “(1, 2)-category” into the search box, it tells me that no pages contain that string. I guess that’s something to do with part of it being a math expression. What do you use to find pages on the nLab?

Posted by: Tom Leinster on June 3, 2011 5:04 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

What do you use to find pages on the nLab?

The best way is to use Google – not the nnLab search function – in this form:

“(1,2)-category” site:http://ncatlab.org/nlab/

(in this case this gives a result where the first 4 hits are pages linking to the entry in question and only the fifth is the entry itself, for some reason).

In general this of course only gives good results if the page in question is linked to properly. For “(1,2)(1,2)-category” this was not quite the case. I always try to add enough cross links back and forth nnLab entries to help find Google its way around, but sometimes I or other nnLab contributors are being lazy.

Posted by: Urs Schreiber on June 3, 2011 5:44 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Thanks; that’s good to know. I can see how “(1, 2)-category” might present particular difficulties to a search algorithm.

Posted by: Tom Leinster on June 3, 2011 5:57 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I think another big part of the problem is that the nLab search box accepts regular expressions. Thus, it interprets parentheses as a grouping command, rather than as part of the string to be searched for. If you search for “(1,2)-category”, you’ll get lots of pages.

I think it would be somewhat preferable if regular expressions were off by default in the search box, with a checkbox to turn them on. IIRC this sort of thing has bitten us before. But probably we can’t do anything about that unless someone wants to hack on instiki.

Posted by: Mike Shulman on June 3, 2011 6:32 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

The “problem” is that the nLab search looks in the source of the page. So when it looks for something like “2-category” then it doesn’t find “$2$-category”. Or, to take another example, searching for nLab I get 2/485 hits (page names versus mere mentions), for _n_-Lab I get 0/2, for $n$Lab I get 0/241 (see below).

But this isn’t a problem, it’s a feature. If the nLab search looked at the rendered output, it would just be emulating what Google and other search engines do. So the rule is: use the internal search to look at the source, and the external search to look at the output.

And so to the regexp. Maybe we should have an FAQ entry on this. There is no need to have a checkbox to turn it off as it can be easily disabled. Regexp works by considering certain characters as special (bit like TeX, really) but any special character can be escaped with a backslash (the opposite of TeX, if you think about it!). So to search for (1,2)-category simply escape the parentheses. When I do that, I get most of the results that Google returns. The ones I don’t are probably due to the (1,2) being typeset as $(1,2)$.

Posted by: Andrew Stacey on June 6, 2011 8:13 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Regexp works by considering certain characters as special (bit like TeX, really) but any special character can be escaped with a backslash (the opposite of TeX, if you think about it!).

No, TeX is exactly like this: $ is special but \$ is escaped, same for %, &, even the space. But TeX also has the reverse feature, where a backslash makes an ordinary character special. (And then there's cases like ^, where both versions are special and you have to really contort yourself to get something ordinary!)

Posted by: Toby Bartels on June 7, 2011 3:13 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Pedant fight!!

No, TeX is exactly like this: $ is special but \$ is escaped, same for %, &, even the space.

No again. \$ is still special. You could say that $ is super special but \$ is just plain ordinarily special. It’s just that the definition of \$ is that it produces a literal $. But the way in which it does that is fairly convoluted. In LaTeX, \$ is:

> \$=macro:
->\x@protect \$\protect \$  .

Hidden in there is a “secret” macro, if we expand that, then we get:

*\expandafter\show\csname $ \endcsname
> \$ =\long macro:
->\ifmmode \mathdollar \else \textdollar \fi .

and finally when we look at \textdollar we get something that inserts a character:

*\show\textdollar
> \textdollar=macro:
->\OT1-cmd \textdollar \OT1\textdollar .

Incidentally, the definition in plain TeX is much simpler:

**\show\$
> \$=\char"24.

But either way, there is no reason at all why \$ has to insert a dollar. The only difference between \$ and \^ is that no-one’s yet thought of an accent that looks a bit like a dollar.

Posted by: Andrew Stacey on June 9, 2011 10:50 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

But this isn’t a problem, it’s a feature.

You can say this maybe for your personal software. But once a software runs out in the public and its behaviour puzzles the generic user, then it’s not a feature, but a problem. It were a feature if it came with an explanation: “click here to search the nnLab source code, notice that for most searches you’d rather want to use Google”.

We had this discussion before, concerning the “TeX”-button on the bottom of each nnLab page. I know that you and Jacques told me that this button just has to have the behaviour that it has, but the fact remains that the generic user will pass by the nnLab, click the button, be puzzled by its behaviour, and conclude that things don’t work.

If Tom Leinster, being sort an insider to the nn-community here, has trouble understanding how to use the nnLab, then that gives a somewhat depressing extrapolation for the rest of the world.

I said this before, and I’ll now say it again: the work that you have done for the nnLab is outright amazing. But it will be all the more appreciated the more it is admitted that there are still problems that need resolution. Declaring bugs to be features is not making a good impression on a public software. I understand that it can be frustrating if after lots and lots of work on a software it turns out that the userers are just too dumb to use it in the right way, but if the software’s purpose is to run a public service, then one just has to face this.

So I’d say in conclusion: no, the search functionality on the nnLab is a problem. It could be cured by adding a tiny bit of explanation on how to use it, and/or by accompanying it with an alternative functionality. At the same time I understand that this needs somebody to do it and I am all fine with nobody finding the energy to actually do it. But I don’t agree that we should say that there is nothing that needs to be done.

Posted by: Urs Schreiber on June 6, 2011 10:53 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I did say that there should probably be an FAQ entry on this, and maybe a better explanation on the search page. The former we can do, the latter needs Jacques (note: not me!).

I had no intention of conveying any frustration on this matter: internal Instiki stuff is not (much) to do with me! I agree that things should “just work”, but would argue that that is indefinable as what “just works” for one person is completely counter-intuitive to another. So the “solution” is almost always better documentation and better ability to find that documentation and almost never changing the functionality.

I also completely agree that the nLab is not perfect (software-wise, I’ll leave the evaluation of the mathematics to the experts). Here is not a great place to discuss this, though. (I don’t check the cafe very often any more.) Fortunately, there is a better place.

Posted by: Andrew Stacey on June 6, 2011 2:37 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I see that the blog software outsmarted me.

If you search for “(1,2)-category”, you’ll get lots of pages.

was originally typed as

if you search for "\(1,2\)-category", you'll get lots of pages

but the escapes got escaped. (-:

As Andrew suggests, let’s continue the discussion here.

Posted by: Mike Shulman on June 6, 2011 6:45 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

What do you use to find pages on the nLab?

The Lab elves have taken some steps to improve on the situation:

if you go again to nLab HomePage you’ll see now an easy new search window that does what you expect it should do, as well as a link to a page with hints about how to do more sophisticated searching.

Posted by: Urs Schreiber on June 8, 2011 7:48 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Excellent.

Posted by: Tom Leinster on June 8, 2011 8:49 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

if the meaning’s clear, what’s the problem?

To reply with an only slightly exaggerated counter-question:

I could define “+” to mean “-” and “0” to mean “1”. If the meaning is clear, what is the problem?

Indeed, for a computer program there is no problem. In C++ we can define “+” to mean “-” and if we stick with it, everything is fine.

But there is a problem for humans and their communication: it hurts to use notation that is well established in a closely related area in a way not consistent with its use there.

Personally, years back I did suffer from the use of the symbol Σ\Sigma instead of BB that you mention, which is inconsistent with the standard use of these symbols, as Mike indicates above. This experience was one of the reasons why I started this discussion here above: I am imagining that one can safe young people following this here from some pain by pointing out the problem.

Posted by: Urs Schreiber on June 2, 2011 6:04 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

the geometric realization of a category does classify something

Yes, every space classifies something . But we should say “classifying space of XYZ” if it classifies XYZs.

The tradition of speaking of the “classifying space of a category” leads to the curious situation that people have to write research articles to figure out what should be obvious by correct terminology, as in

What does the classifying space of a category classify?

(The Baas-Dundas-Rognes article on topological 2-categories used to have the analogous 2-title, but it seems these days the only remnant of this which Google remembers is my blogging about it, so I won’t point to it.)

Posted by: Urs Schreiber on June 1, 2011 8:35 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

the notation BG\mathbf{B}G for the topos of GG-sets is used in Mac Lane and Moerdijk’s topos theory book and in Moerdijk’s book on classifying spaces and classifying toposes.

Yes, and that’s good: this topos is the topos-incarnation of both, the one-object groupoid {g|gG}\{\bullet \stackrel{g}{\to} \bullet | g \in G\} and the topological space |N{g|gG}||N \{\bullet \stackrel{g}{\to} \bullet | g \in G\}|:

BG:=Sh({g|gG}) wheSh(|N{g|gG}|). \mathbf{B}G := Sh(\{\bullet \stackrel{g}{\to} \bullet | g \in G\}) \simeq_{whe} Sh(|N \{\bullet \stackrel{g}{\to} \bullet | g \in G\}|) \,.

So this is not a different use from the one I am advocating above, but in line with it.

Posted by: Urs Schreiber on June 1, 2011 12:43 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Urs and Mike have suggested that I don’t use BAB A for the geometric realization of the nerve of a category AA, and that I don’t call it the “classifying space” of AA. As I said, I’m open to persuasion, but I’d be more likely to be persuaded if I understood better where they were coming from. (Plus, it would be interesting in its own right.) So I’d like to know more about the system of terminology and notation that they do favour.

So here are some questions, which I hope Mike and/or Urs won’t mind answering.

  1. Consider the functors

    MonoidCat *Cat. Monoid \stackrel{\longleftarrow}{\rightarrow} Cat_* \to Cat.

    Here Cat *=1/CatCat_* = 1/Cat is the category of pointed categories, the functor Cat *CatCat_* \to Cat forgets the basepoint (distinguished object), the functor MonoidCat *Monoid \to Cat_* sends a monoid to its corresponding one-object pointed category, and the functor Cat *MonoidCat_* \to Monoid is its right adjoint, sending a pointed category to the monoid of endomorphisms of the basepoint.

    Question: which of these functors, including the composites that I haven’t drawn, do you have names and notation for? What are they?

  2. This is 18 questions in one. First let XX be a category. In your preferred system of notation, does BXB X mean anything? If so, what? Same questions for NXN X, and same questions for |X||X|. (That’s 6 so far.) Now the same 6 questions when XX is a pointed category, and the same 6 again when XX is a monoid.

    (I’m sure I know the answers to some of these, and there’s overlap with the first question. But I’m trying to be systematic here.)

  3. Let MM be a monoid. There’s a topological space that I’d call “BMB M”. If I understand correctly, you would call it |NBM||N B M|, at least if you were giving it its full name. Is that right? If so, which of the following abbreviations do you feel comfortable with?

    NBM,|BM|,|NM|,|M|,NM,BM,M. N B M, |B M|, |N M|, |M|, N M, B M, M.

Thanks!

Posted by: Tom Leinster on June 3, 2011 11:09 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

It should be

Cat *ΩBMonoid. Cat_* \stackrel{\overset{B}{\leftarrow}}{\underset{\Omega}{\to}} Monoid \,.

The forgetful functor Cat *CatCat_* \to Cat can be left implicit or not, depending on taste and context. I think that’s not the issue.

First let XX be a category. In your preferred system of notation, does BXB X mean anything?

Only if XX is equipped with monoidal structure. Then it means the one-object 2-category with (BX)(*,*)X(B X)(\ast,\ast) \simeq X. Analogously for NXN X and |X||X|.

As I said before, I’d be happy with writing |BM||B M| for |NBM||N B M|. We can safely suppress writing the nerve operation.

Posted by: Urs Schreiber on June 3, 2011 12:15 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

OK, thanks. I think this identifies something that I don’t understand about where you’re coming from: in topology, I’m accustomed to the left adjoint of Ω\Omega being called Σ\Sigma (or SS), not BB. I thought that was universal. Why not do so here?

I took care over pointed categories because of what Mike wrote at the end of this comment.

Posted by: Tom Leinster on June 3, 2011 12:29 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

The point is that there are two different functors called Ω\Omega. We call them the same thing, because one of them is the composite of the other with a nameless forgetful functor. But their adjoints are very different. On the one hand, we have an adjunction:

PointedspacesΩΣPointedspaces Pointed spaces \underoverset{\Omega}{\Sigma}{\rightleftarrows} Pointed spaces

and on the other hand, we have an equivalence (of (,1)(\infty,1)-categories):

GrouplikeA spacesΩBPointedconnectedspaces Grouplike A_\infty spaces \underoverset{\Omega}{B}{\rightleftarrows} Pointed connected spaces

The first Ω\Omega is the composite of the second with the nameless forgetful functor from grouplike A A_\infty-spaces to pointed spaces. Therefore, its adjoint Σ\Sigma must be, up to homotopy, the composite of the left adjoint to this forgetful functor with BB. This unnamed left adjoint is a homotopical version of “the free group on a pointed set”, so you can see that there is lots happening in it. This is why Σ\Sigma is very different from BB.

Posted by: Mike Shulman on June 3, 2011 4:43 PM | Permalink | PGP Sig | Reply to this

Re: Möbius Inversion for Categories

I’m accustomed to the left adjoint of Ω\Omega being called Σ\Sigma (or SS), not BB.

That’s for Ω\Omega regarded as Ω:Spaces Spaces \Omega : Spaces_* \to Spaces_*. But above we had (the directed analog of) Ω:SpacesGroups\Omega: Spaces \to \infty Groups: we remember monoidal structure.

Posted by: Urs Schreiber on June 3, 2011 4:43 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I took care over pointed categories because of what Mike wrote at the end of this comment.

Yes, in order to have (Ω,B)(\Omega, B) restrict to an equivalence it is important that we use pointed spaces. But for distinguishing between BB and Σ\Sigma that’s not the issue.

Posted by: Urs Schreiber on June 3, 2011 4:45 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

The main principles I want to adhere to are that BB always denotes an upwards level-shift, aka delooping, and level-shifts are never nameless. I also prefer that operations which turn directed things into undirected things, such as the geometric realization of the nerve of a category, are not nameless. (Whether it’s the “geometric realization” part or the “nerve” part which makes a category undirected depends on whether today we are regarding simplicial sets as directed gadgets or undirected ones.)

  1. MonoidBΩCat *forgetCatMonoid \;\underoverset{B}{\Omega}{\rightleftarrows}\; Cat_\ast \xrightarrow{forget} Cat. As Urs said, the forgetful functor can be nameless.

  2. As Urs said, if XX is only a plain category, then I wouldn’t write BXB X to mean anything, since a plain category cannot be upwards level-shifted or delooped. NXN X means the nerve of XX, which is a simplicial set and makes sense for any category, but if we are thinking up to homotopy and identifying simplicial sets with spaces, then we might also leave geometric realization nameless and write NXN X for |NX||N X|. Plain |X|{|X|} doesn’t “really” have a meaning, since as you say we generally geometrically realize presheaves, not categories, but since there’s a canonical presheaf associated to XX, namely NXN X, I don’t have a problem with writing |X|{|X|} to mean |NX|{|N X|}—though it should probably be explained on first usage.

    The same answers apply when XX is pointed, except that NXN X will be a pointed simplicial set and |X|{|X|} will be a pointed space.

    If XX is a monoid, then I would write BXB X to mean (1) the category with one object whose endomorphisms are XX. If XX is a group, then I would also write BXB X to mean (2) the nerve of that category or (3) the geometric realization of that category. I would, I guess, also grudgingly accept (2) and (3) when XX is a mere monoid, since they are standard usages in algebraic topology, although I’d prefer to separate the level-shifting operation from the making-things-invertible operation notationally.

    For a monoid XX, I might also grudgingly accept NXN X for the nerve of the category BXB X, since at least the level-shift is being notated somehow, and the category BXB X is the only thing canonically associated to XX which has a nerve. Writing |X|{|X|} for the geometric realization of that nerve is stretching it a bit more, but if it were explained on first usage, it might be okay.

  3. For a monoid MM, yes, I would write the geometric realization of the nerve of its associated 1-object category as |NBM||N B M|. By the answer to |X|{|X|} when XX is a category, I might abbreviate this as |BM||B M|. By the answer to NXN X when XX is a category, if thinking of it only as a homotopy type, I might abbreviate it NBMN B M. By answer (3) to BXB X when XX is a monoid, I might also (grudgingly, unless MM is a group) abbreviate it as BMB M. By the answers to NXN X and |X||X| when XX is a monoid, I might (grudgingly) abbreviate it to |NM||N M| or |M||M|. Finally, combining the justifications for NBMN B M and |NM||N M|, I could even accept just NMN M, if thinking of it only as a homotopy type. But I don’t think just plain “MM” would ever be okay, since something is being done to it.

Let me mention two last examples, which really contributed to convincing me to take a hard line that BB should always denote a level-shift. Firstly, if CC is a monoidal category, then |NC||N C| is an A A_\infty-space, and as such it has a delooping B(|NC|)B(|N C|). If |NC||N C| is denoted by BCB C, then B(|NC|)B(|N C|) would be denoted by B(BC)B(B C). I have actually seen this notation used! But notice that it cannot be rewritten as B 2CB^2 C, since the two “BB“s have very different meanings. I find this an unacceptable state of affairs.

Secondly, if we accept that the functor MonoidCatMonoid\to Cat needs some name, since as I argued above, it is not an inclusion, then BB seems like the natural name for it. But this in incompatible with notating the functor “geometric realization of the nerve” by BB, since then in the commutative square Groups B Groupoids B TopologicalGroups B Spaces \array{ Groups & \overset{B}{\to} & Groupoids\\ \downarrow & & \downarrow^B\\ Topological Groups & \underset{B}{\to} & Spaces } all the functors would be denoted by BB, except the left-hand vertical one which is simply an inclusion and usually nameless. Thus we would have BB=BB\circ B = B, also an unacceptable state of affairs.

Posted by: Mike Shulman on June 3, 2011 6:27 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Thanks, Mike. That really sheds a lot of light on the point of view you’ve been putting forward.

If you come to my talk in Vancouver then you’ll see what I’ve decided, but I think you’ve probably persuaded me.

Posted by: Tom Leinster on June 5, 2011 3:39 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Glad to help! I look forward to your talk.

Posted by: Mike Shulman on June 6, 2011 6:55 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Your slides look really good, Tom. I like your use of repetition: for example, how the “coarse Möbius inversion” slide is built by taking the “fine Möbius inversion” slide and changing it piece by piece, how you then have a “Fine and coarse: summary” slide that sets the two ideas side by side, how you then repeat the original “Overview” slide and draw a bridge between “fine” and “coarse”, how later you “Recall” a fact you previously stated about bijective-on-objects functors, and how you then summarize the whole talk.

It’s as if actually wanted the audience to remember what you said!

Usually mathematicians assume that saying something once means it’s completely unnecessary to ever say it again. After all,

(PandP)P, (P \; \and \; P) \iff P,

right?

Posted by: John Baez on June 1, 2011 9:54 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Thanks very much, John. I was acutely aware that my talk fit perfectly into what Eugenia has observed is a classic pattern for really boring talks: “here are two things you’ve never heard of and don’t care about; I’m going to show you how they’re related”. I couldn’t find a way out of that, so I thought that at least I could try to be aware of the fact that most people wouldn’t have heard of, or care about, either kind of Möbius inversion.

Posted by: Tom Leinster on June 1, 2011 10:57 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Maybe I’m overoptimistic, but I guess most mathematicians worthy of the name have at least heard of ‘Möbius inversion’ and are thus vaguely curious about what it means, or at least annoyed at the existence of yet another buzzword they don’t understand. So if you can explain it in a way they remember, they’ll thank you for it.

So in fact I guess the first few slides, review for me, may be extremely useful for people who have never understood any version of ‘Möbius inversion’ or the ‘Möbius function’.

If at the bottom of page 32 (that’s what it’s called, anyway) you say the magic phrase Riemann zeta function, they’ll know this is important stuff. And if you wanted to really pull out all the stops, you could note that the left-hand side of this equation blows up at the famous zeroes of the Riemann zeta function.

(Which, however, occur at points where the sum doesn’t converge.)

Posted by: John Baez on June 2, 2011 7:29 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Yes, I’d assume most people in the audience would have seen the definition of the classical Möbius function at some point, even if they’d forgotten it. The first few slides, reviewing this, were mostly by way of scratching an itch, so that people didn’t sit there thinking “but what was that thing called the Möbius function from my undergraduate days?”

(When I wrote that most people wouldn’t have heard of or care about either kind of Möbius inversion, I was referring to Möbius inversion for categories.)

you could note that the left-hand side of this equation blows up at the famous zeroes of the Riemann zeta function.

Good idea. I could also be more clear than I was in Belgium about the reason for the notation “ζ\zeta” for the function with constant value 11.

Posted by: Tom Leinster on June 2, 2011 8:25 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I have started an nnLab entry: Euler characteristic.

Posted by: Urs Schreiber on June 1, 2011 12:23 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I wrote:

I have started an nLab entry: Euler characteristic.

There is something crucial missing in that entry (among the many other aspects also missing there): a discussion of the relation between the “homological” and the “homotopical” Euler characteristic.

But I don’t really understand this. Can anyone help me?

  1. The ordinary Euler characteristic of a topological space is the alternating sum of the rank of its homology groups .

  2. The other definition (its “\infty-groupoid-cardinality”) is the alternating product of the size of its homotopy groups.

The Leinster-Euler-characteristic of categories somehow interpolates between the two: let GG be a finite group, then

  1. for CC a finite poset presentation of the space BGB G it produces the homological Euler characteristic of BGB G,

  2. but for CC a groupoid presentation of BGB G it produces the homotopical Euler characteristic of BGB G.

What’s going on?

Posted by: Urs Schreiber on June 1, 2011 1:51 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Hmm. I understand what you just wrote, but I don’t have any explanation.

Can you say a bit more about what kind of answer to “What’s going on?” you’re hoping for?

Posted by: Tom Leinster on June 1, 2011 2:25 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

The logarithmic relationship between the first two is not that surprising to me, since for a finite-dimensional vector space over a field with qq elements, its cardinality ss and rank rr are related by s=q rs = q^r. Therefore, an alternating product of cardinalities corresponds to an alternating sum of ranks. If we regard homology groups as a sort of approximation to homotopy groups, then morally it seems clear that the ordinary Euler characteristic is a sort of logarithm of the groupoid cardinality. Of course the Euler characteristic is usually defined using integral or rational homology, and many of the spaces we apply it to have infinite homotopy groups, so it seems like usually “the base of the logarithm is infinity” or some such nonsense.

Is there anything more precise we can say in that direction? And is there some reason why a finite poset presentation is a “logarithm” of a groupoid presentation?

Posted by: Mike Shulman on June 1, 2011 7:25 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

the ordinary Euler characteristic is a sort of logarithm of the groupoid cardinality

Thinking about it further, I realize that that’s probably wrong, since in some cases they are actually equal rather than one being the log of the other. Maybe instead we should think of homology as the free abelian group on homotopy? Argh… I wish I understood what homology was supposed to mean.

Posted by: Mike Shulman on June 3, 2011 4:37 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Mike wrote:

Thinking about it further, I realize that that’s probably wrong, since in some cases they are actually equal rather than one being the log of the other.

Right: the reason I call it a ‘mystery’ is that while the first is defined using addition and the second is defined using multiplication, the Euler characteristic is morally equal to the groupoid cardinality, not its logarithm. There are very few spaces that are both cohomologically finite and homotopically finite in the sense required to make the Euler characteristic and homotopy cardinality converge. But in many more cases, standard tricks for computing divergent sums or products let us compute the one that diverges, and see that it equals the one that converges!

And in any case, they both act like a concept of ‘cardinality’ for topological spaces. In other words, they’re both additive under disjoint union and multiplicative under twisted product (i.e., the formation of a fibration with a given fiber and base). So it’s not like one really ‘wants’ to be the logarithm of the other.

(For some details backing up my remarks above, see my talk.)

Argh… I wish I understood what homology was supposed to mean.

Don’t bother. To understand the Jekyll-and-Hyde duality of Euler characteristic and homotopy cardinality for spaces, it’s better to think of Euler characteristic as defined using rational cohomology groups.

Posted by: John Baez on June 3, 2011 9:03 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

There are very few spaces that are both cohomologically finite and homotopically finite in the sense required to make the Euler characteristic and homotopy cardinality converge.

I’m actually having trouble thinking of any (except for finite discrete spaces). Can someone give some examples?

To understand the Jekyll-and-Hyde duality of Euler characteristic and homotopy cardinality for spaces, it’s better to think of Euler characteristic as defined using rational cohomology groups.

Care to expand on that cryptic remark? (-: I tend to think of Euler characteristics, and more generally fixed point indices, as defined intrinsically in the stable homotopy category, with the fact that we can compute them in terms of homology or cohomology (rational or integral) being a nice consequence of the monoidality of those functors.

(This isn’t just a preference for abstract nonsense, either. I recently learned from Kate that when you want to generalize from fixed point indices to coincidence invariants, which is to say to answer the question “where does f(x)=g(x)f(x)=g(x)?” rather than “where does f(x)=xf(x)=x?”, then at least for maps f,gf,g between manifolds of different dimension, you have to stay in the stable homotopy category and not hit things with (co)homology. This is basically because spheres have higher (stable) homotopy groups, but not higher homology groups.)

Posted by: Mike Shulman on June 3, 2011 6:20 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I wrote:

To understand the Jekyll-and-Hyde duality of Euler characteristic and homotopy cardinality for spaces, it’s better to think of Euler characteristic as defined using rational cohomology groups.

Or integral ones, if you prefer…

Mike wrote:

Care to expand on that cryptic remark? (-:

Euler characteristic is most easily defined on finite CW complexes, while homotopy cardinality is most easily defined on spaces with finite Postnikov towers and all homotopy groups finite.

You should sense the duality here. The first kind of space is nice for mapping out of. The second is nice for mapping into. More precisely, the first kind of space, say XX, has [X,K(,n)][X,K(\mathbb{Z},n)] finite rank, and nonzero for only finitely many XX. The second kind of space, say YY, has [S n,Y][S^n, Y] finite, and nonzero for only finitely many nn.

Only very few spaces are nice in both ways. So, my feeling is that Euler characteristic and homotopy cardinality are two aspects of ‘the same thing’, but defined on domains that barely overlap at all.

That’s what I meant by ‘Jekyll and Hyde’: they’re two faces of the same guy, but you have to be incredibly lucky to catch him in the state of transforming from one to the other.

Those papers I called “really exciting”, by Floyd–Plotnick and Grigorchuk, expand the domain of definition of Euler characteristic so it starts overlapping with the domain of definition of homotopy cardinality. But I don’t think the final shoe has dropped yet.

I tend to think of Euler characteristics, and more generally fixed point indices, as defined intrinsically in the stable homotopy category, with the fact that we can compute them in terms of homology or cohomology (rational or integral) being a nice consequence of the monoidality of those functors.

Maybe someday I’ll understand that—probably not. But my point was really just about ‘maps in’ versus ‘maps out’. When in your discussion of Euler characteristic you said

Argh—I wish I understood what homology was supposed to mean.

I was trying to reassure you that since Euler characteristic is the ‘maps out’ face of this Jekyll-and-Hyde concept, we can think of it in terms of the cohomology groups [X,K( n)][X,K(\mathbb{Z}^n)], which are somehow conceptually clearer than the homology groups.

Speaking of ‘Jekyll meets Hyde’, I wrote:

There are very few spaces that are both cohomologically finite and homotopically finite in the sense required to make the Euler characteristic and homotopy cardinality converge.

and you wrote:

I’m actually having trouble thinking of any (except for finite discrete spaces). Can someone give some examples?

Actually I don’t know any others! You listed all the ones I know: finite unions of weakly contractible spaces, to be annoyingly pedantic. From the viewpoint of homotopy theory these are all weakly equivalent to ‘finite sets’. So we can think of Euler characteristic and homotopy cardinality as two generalizations of the cardinality of finite sets, which happen to be both defined—as far as I know!—only for finite sets.

I would love to see this proved or disproved:

Conjecture: Every connected space that has just finitely many nontrivial integral cohomology groups, all finite rank, and finitely many nontrivial homotopy groups, all finite, is weakly homotopy equivalent to a point.

In 1953 Serre proved that any noncontractible simply-connected finite CW-complex has infinitely many nontrivial homotopy groups. That kills off a lot of possible counterexamples.

Is any space meeting the conditions of the conjecture weakly homotopy equivalent to a finite CW-complex?

In 1998, Carles Casacuberta wrote:

However, we do not know any example of a finite CW-complex with finitely many nonzero homotopy groups which is not a K(G,1)K(G, 1), and the results of this paper suggest that it is unlikely that there exist any.

I’ve decided to ask about this on Mathoverflow.

Posted by: John Baez on June 8, 2011 6:19 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I was trying to reassure you that since Euler characteristic is the ‘maps out’ face of this Jekyll-and-Hyde concept, we can think of it in terms of the cohomology groups … which are somehow conceptually clearer than the homology groups.

Thanks. I feel like I understand cohomology with arbitrary coefficients in the “maps out” sort of way, but cohomology with integral or rational coefficients is still somewhat mysterious to me, and it seems as though it’s that particular sort of cohomology that’s important here.

However, the MO answers point out that considering rational cohomology groups may be the wrong way to go, since there are spaces whose cohomology is infinitely generated but entirely torsion, so their “rational Euler characteristic” is 1 but their homotopy cardinality may be interesting. I would guess that even just considering integral cohomology groups may be misleading, since if one considers the “rank” of an infinitely generated torsion group to be zero, one might come up with the same “Euler characteristic”.

(Neil Strickland’s answer to your MO question is of course interesting, since 12\frac{1}{2} is the homotopy cardinality of P \mathbb{R}P^\infty. I don’t follow what he’s doing to get 12\frac{1}{2}, but I gather that it’s the same sort of “analytic continuation” thing. Is an “adele” something I should learn about?)

The definedness condition for Euler characteristic as a trace in the stable homotopy category is stronger: the suspension spectrum of the space must be dualizable, which I believe is equivalent to saying it is (up to homotopy) a finite cell spectrum. That’s not too far off from saying that the space itself is a finite CW complex (it’s implied by it; I don’t know whether it is equivalent to it.)

Maybe someday I’ll understand that

Let me try to help. Suppose XX is a compact manifold. The first step is to show that the Euler characteristic is equal to the total index of some vector field with isolated zeros. This can be done with Morse theory. Take the vector field to be the gradient of a Morse function; then the indices of its zeros can be identified with the dimensions of the cells being attached in the resulting Morse decomposition.

The next step is to realize that a vector field with isolated zeros is almost the same as a self-map with isolated fixed points which is homotopic to the identity. (The vector field tells you which direction to “push” the map off of the identity; it stays fixed where the vector field is zero.) Now at any isolated fixed point of any self-map, we can define an “index” just as we can for a zero of a vector field, by looking at the degree of the induced map on a sphere surrounding the fixed point. Any map with isolated fixed points thus has a “total fixed point index,” and the Euler characteristic of a manifold is the fixed point index of (something homotopic to) its identity map.

Finally, we need to identify fixed point indices with stable traces. I tried to sketch the argument for that, with lots of pictures and no spectra, on these slides (pages 13–35).

This suggests that we ask: is there an invariant of self-maps of “homotopically finite” spaces which gives the homotopy cardinality when applied to the identity map? If so, then we could try looking for a place in which that invariant is a trace.

Posted by: Mike Shulman on June 8, 2011 5:21 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I tried to sketch the argument for that,

But what’s the canonical reference? Did you and Ponto work this out? Is this classical? Dold?

I see these statements appear as example 3.7 of your article with Ponto, but there, too, it remains unclear if you leave this as an exercise for the reader or are meaning to review something in the literature.

For the moment I have just added this to the nnLab. I’d be grateful if you could provide whatever it takes that we can state this as formal theorems.

Posted by: Urs Schreiber on June 8, 2011 5:50 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Oh my, is that so unclear? Nothing in that overview paper is original to us, except maybe a few of the toy examples (not the contentful ones). I think this is due to Dold, from the references cited in that example.

Posted by: Mike Shulman on June 8, 2011 8:17 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Oh my, is that so unclear?

Well, sorry, it wasn’t clear to me. What can I do? I ask! It seems that annoyed you. You should instead feel honored that by default I assumed this is due to you and you consider it too trivial to spell out the details. Seriously.

But all right, I’ll try to dig through the references then.

Posted by: Urs Schreiber on June 8, 2011 8:28 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Sorry, I wasn’t annoyed at you; I was just surprised (and, maybe, a little annoyed with myself) that we hadn’t written it clearly enough. And in a hurry. Like now. (-:

Posted by: Mike Shulman on June 9, 2011 1:18 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

But what’s the canonical reference?

I have trouble checking the Dold references here from home (and did he really say that in between 1965-72 already?)

But I found the statement of the theorems now in the fourth reference that you give: Greenlees-May, Equivariant stable homotopy theory .

The duality of the suspension spectrum Σ X\Sigma^\infty X of a manifold to the Thom spectrum of its normal bundle – called Atiyah duality there – is theorem 4.18.

The fact that the trace of the identity on Σ X\Sigma^\infty X is the Euler characteristic of XX is presumeably prop. 5.2, though I need to think about how that “transfer map” there is the trace. And maybe it’s stated only for coset spaces? I need to spend more time with this than I have now.

There are no proofs or pointers to proofs given there, it seems.

Posted by: Urs Schreiber on June 8, 2011 9:15 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I have started an entry Spanier-Whitehead duality.

The source for (Σ X) *Th(NX)(\Sigma^\infty X)^* \simeq Th(N X) seems to be: Atiyah, Thom complexes , Proc. London Math. Soc. (3) , no. 11 (1961), 291–310.

Posted by: Urs Schreiber on June 8, 2011 11:28 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I think the formulation of Spanier-Whitehead duality and the fixed point index in terms of duality in the monoidal stable homotopy category (as opposed to with explicit geometric definitions) dates to Dold’s paper around 1980: “Duality, trace, and transfer”. Here’s one link, which is maybe not exactly the paper we cited? But looks pretty similar.

Posted by: Mike Shulman on June 9, 2011 2:25 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Here’s one link

Thanks, that helps! Especially since I am still not on a connection subscribed to any journals.

The Thom spectrum as a monoidal dual is theorem 3.1 there, proven in fair detail. Good, thanks, I have added that to the entry.

I still want to locate the precise reference for the statement about the trace of Id Σ XId_{\Sigma^\infty X} being the Euler characteristic. But I have to concentrate on something else for the moment.

Posted by: Urs Schreiber on June 9, 2011 9:32 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I still want to locate the precise reference for the statement about the trace of Id Σ XId_{\Sigma^\infty X} being the Euler characteristic.

Once you know that traces in the stable homotopy category are fixed point indices, you just need to know that the fixed point index of the identity map is the Euler characteristic. This is a very classical thing that doesn’t require any category theory, e.g. the Morse theory argument I sketched above. It’s in Minor’s “Topology from the Differentiable Viewpoint” for instance. I don’t know the original source.

Posted by: Mike Shulman on June 9, 2011 11:20 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Once you know that traces in the stable homotopy category are fixed point indices,

Okay, and what’s the reference for that?

(Sorry if this is obvious, am posting in a rush.)

Posted by: Urs Schreiber on June 10, 2011 5:25 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Isn’t that what the Dold paper is about?

Posted by: Mike Shulman on June 10, 2011 7:09 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Isn’t that what the Dold paper is about?

I didn’t read far enough, being busy with other things.

Okay, I’d still need more time to state and reference a nice formal theorem at the nnLab entry, but for the moment I have now at least added a pointer to “around corollary 4.6 in Dold-Puppe”. Thanks.

Posted by: Urs Schreiber on June 11, 2011 3:07 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

the ordinary Euler characteristic is a sort of logarithm of the groupoid cardinality

Thinking about it further, I realize that that’s probably wrong,

I am being vaguely reminded of the situation for Goodwillie calculus:

there, too, is a claim that some arithmetic of homotopy groups that looks like it should be thought of as a (Taylor) series, is rather a logarithmic expansion: Arone and Kankaanrinta in The Goodwillie tower of the identity is a logarithm write

It is the point of this paper that the Goodwillie tower is the homotopy theoretic analog of logarithmic expansion, rather than of Taylor series. (p. 6)

and that sums should instead be thought of as products

the Goodwillie tower is an infinite product, rather than an infinite sum, (p. 2)

Where I think the point is that people used to think the opposite, so that maybe both perspectives are valid?

Is there any connection between Euler characteristic/homotopy cardinality and Goodwillie calculus?

Posted by: Urs Schreiber on June 3, 2011 10:35 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

The Euler characteristic (of a category) was mentioned in the context of the Goodwillie calculus in this blog post.

Posted by: David Corfield on June 3, 2011 11:12 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

Urs wrote:

What’s going on?

I think this is a big mystery, which is why I gave a talk on this subject called The Mysteries of Counting: Euler Characteristic versus Homotopy Cardinality. This was before Tom provided a new clue to the puzzle. Unfortunately, Tom’s clue leaves me still mystified about the way cardinality has an ‘additive’ and ‘multiplicative’ face, which like Jekyll and Hyde are secretly the same yet hardly ever seen in the same place at the same time.

His work brings them closer together. But I’d still like to see a nice category of topological spaces (or homotopy types) that includes both the “cohomologically finite” and “homotopically finite” spaces mentioned in my talk, and comes equipped with a notion of cardinality generalizing both Euler characteristic and homotopy cardinality, that is both additive under disjoint union and multiplicative under twisted products.

The page for my talk includes lots of references for anyone interested in Euler cardinality. Some perhaps lesser-known papers that I find really exciting are:

• William J. Floyd and Steven P. Plotnick, Growth functions on Fuchsian groups and the Euler characteristic, Invent. Math. 88 (1987), 1-29.

• R. I. Grigorchuk, Growth functions, rewriting systems and Euler characteristic, Mat. Zametki 58 (1995), 653-668, 798.

Posted by: John Baez on June 2, 2011 7:37 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I think this is a big mystery, […]

Thanks for reminding me of that page of yours. I have now incorporated a little bit of its content and many of its references into the nnLab page.

I think Mike is correctly aiming at getting to the bottom of the nature of Euler char with his emphasis of the fact that Euler characteristic is just the categorical dimension in the correct ambient symmetric monoidal category/\infty-category.

So I agree that his query box-question in the entry looks like the one to concentrate on:

in which ambient symmetric monoidal category/\infty-category is the Euler characteristic of a category/enriched category/higher category nothing but the categorical dimension (trace of the identity morphism)?

Posted by: Urs Schreiber on June 2, 2011 10:38 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

in which ambient symmetric monoidal category/∞-category is the Euler characteristic of a category/enriched category/higher category nothing but the categorical dimension (trace of the identity morphism)?

Here’s a specific question I’d like to know the answer to: the category of Z-categories should be symmetric monoidal, with a smash product analogous to that for spectra. And there should be a “suspension Z-category” functor Σ + \Sigma^\infty_+ from ω-categories to Z-categories. For which ω-categories X is the Z-category Σ + X\Sigma^\infty_+ X dualizable, and what is the resulting Euler characteristic?

Posted by: Mike Shulman on June 2, 2011 8:51 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

the category of Z-categories should be symmetric monoidal

Can we just briefly see if we agree on what this is?

I suppose you are thinking of globular sets, unbounded in both directions, equipped with a composition operation?

More systematically it could be defined to be: the stabilization of (,n)Cat(\infty,n)Cat. Maybe here we want n=1n= 1 or somehow imagine sending nn \to \infty. Maybe better the former.

Or is it? This definition would stabilize with respect to looping whose loops are invertible. Maybe ZCatZ Cat should instead be stabilized with respect to “lax looping” (or “comma looping”, I guess)?

The former version has the advantage that we know in some detail how to make sense of it and we also know that it indeed is a sensible directed analog of spectra. And for comparison with Tom’s 1-categorical Euler characteristic it should be sufficient.

Another question I have: if we want (nn-)categorical Euler characteristic to be a categorical trace, the ambient symmetric monoidal context has to be such that End(1)End(1) “contains rational numbers” in some way. That seems unlikely for any category of (higher) categories. Or is it? We might need to abelianize in some other way, too, maybe.

Posted by: Urs Schreiber on June 2, 2011 10:17 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

There are two things that I would consider calling Z-categories:

  1. globular sets (or some other kind of shapes) unbounded in both directions, with compositions

  2. a sequence {X n} n\{X_n\}_{n\in \mathbb{N}} of basepointed ω-categories with equivalences X nΩ dirX n+1Hom X n+1(*,*) X_n \simeq \Omega_{dir} X_{n+1} \coloneqq Hom_{X_{n+1}}(\ast,\ast)

The second is, I think, what you mean by stabilizing with respect to lax or comma looping. We could also, I guess, consider the usual (,1)(\infty,1)-categorical stabilization of ω-Cat (or, I guess, (,n)(\infty,n)-Cat), but I wouldn’t expect it to be very interesting. In particular, I think if XX is a pointed ω-category, then the homotopy pullback

Ω invX * * X\array{ \Omega_{inv} X & \to & \ast \\ \downarrow && \downarrow \\ \ast &\to&X}

in the (,1)(\infty,1)-category of ω-categories, consists only of automorphisms of *\ast, automorphisms of those, etc.—only invertible things. Even the comma object in the (,2)(\infty,2)-category of ω-categories would only have invertible higher cells. So it seems that there isn’t really any directedness appearing at all in that construction: the spectrification condition will force the objects to just be ordinary ∞-groupoids and the resulting “Z-category” to just be an ordinary undirected spectrum.

Whether (1) and (2) above are equivalent is also an interesting question. My guess would be that the objects (2) are equivalent to the objects of (1) with some additional property like that for every cell xx, there exists an nn such that s nx=t nxs^n x = t^n x is an identity cell.

if we want (n-)categorical Euler characteristic to be a categorical trace, the ambient symmetric monoidal context has to be such that End(1) “contains rational numbers” in some way.

Yes, I guess so. That is also puzzling to me. Is there any known symmetric monoidal category containing a dualizable object whose Euler characteristic is fractional?

Posted by: Mike Shulman on June 3, 2011 4:25 AM | Permalink | Reply to this

Re: Möbius Inversion for Categories

By the way, let me take this opportunity to shamelessly advertise the expository paper Traces in symmetric monoidal categories, which Kate and I have just posted on our websites. It has a lot of toy examples (most of which were in the first version of “Shadows and traces in bicategories”), and some informal discussion about what traces have to do with fixed points, which is something that puzzled me for a long time.

Posted by: Mike Shulman on June 3, 2011 5:00 AM | Permalink | Reply to this

looping and delooping

I have started an nnLab entry looping and delooping.

Not quite done, but I must not further work on this. I must be taking care of something else right now.

Posted by: Urs Schreiber on June 3, 2011 5:33 PM | Permalink | Reply to this

Re: Möbius Inversion for Categories

I’ve just written a paper on this stuff: Notions of Möbius inversion.

Posted by: Tom Leinster on January 4, 2012 6:28 AM | Permalink | Reply to this
Read the post Magnitude of Metric Spaces: A Roundup
Weblog: The n-Category Café
Excerpt: Resources on magnitude of metric spaces.
Tracked: April 7, 2013 9:53 PM

Post a New Comment