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.

April 6, 2015

Five Quickies

Posted by Tom Leinster

I’m leaving tomorrow for an “investigative workshop” on Information and Entropy in Biological Systems, co-organized by our own John Baez, in Knoxville, Tennessee. I’m excited! And I’m hoping to learn a lot.

A quick linkdump before I go:

  • Reflexive completion   Tom Avery and I are writing a paper on Isbell conjugacy and reflexive completion (also called Isbell or MacNeille completion). I gave a talk on it last week at the British Mathematical Colloquium in Cambridge, which is somewhat similar to the Joint Meetings in the US.

    The concepts of Isbell conjugacy and reflexive completion are at the same very basic, primitive categorical level as the Yoneda lemma. They rely on nothing more than the notions of category, functor and natural transformation. But they’re immeasurably less well-known than the Yoneda lemma.

    As for Tom, you may remember him from the Kan Extension Seminar. He’s doing a PhD with me here in Edinburgh.

  • Mathematicians accepting and resisting overtures from GCHQ   The British Mathematical Colloquium was part-sponsored by the UK surveillance agency GCHQ, which I’ve written about many times before. They paid for one of the plenary talks and some of the costs of student attendance. (They didn’t pay for me.)

    I began my talk by expressing both my thanks to the organizers and my disappointment in them for allowing an extremist organization like GCHQ to buy itself a presence at the conference. As I understand it, the deal was that in return for the money it paid, GCHQ got a recruiting platform for the Heilbronn Institute (their academic brand). For instance, the conference hosted a Heilbronn recruitment session, advertised in the blurb that every delegate received.

    And I said that although one might think it irregular for me to be taking a few moments of my seminar to talk about this, consider the fact that GCHQ bought itself three whole days in which to create the impression that working for an agency of mass surveillance is a normal, decent thing for a mathematician to do.

    There were several encouraging signs, though:

    • An important person within the organizational structure of the British Mathematical Colloquium (an annual event) exhibited clear awareness that GCHQ involvement in the BMC was controversial. This is a start, though it requires people to keep pointing out that committees, as well as individuals, are making a political choice when they cooperate with the intelligence agencies.
    • The conference website advertised that GCHQ would have a stand/booth at the conference, but in the end they didn’t — perhaps knowing that they’d have been asking for trouble.
    • I heard that a certain prominent British mathematician had refused requests to review from both GCHQ and the NSA.
    • And as usual, just about every mathematician I spoke to was opposed to GCHQ mass surveillance.
  • The Euler characteristic of an algebra   I recently gave a couple of talks entitled “The Euler characteristic of an algebra”: one for category theorists and one for algebraists. This represents joint work with Joe Chuang and Alastair King, which I hope we’ll have written up soon. I wrote a couple of posts warming up to this result, though I never got round to the result itself.

  • Review of Nick Gurski’s higher categories book   I wrote a review of Nick Gurski’s book Coherence in Three-Dimensional Category Theory. The review will appear in the Bulletin of the London Mathematical Society.

  • Are lectures the best way to teach?   Nick also has an opinion piece in The Guardian (joint with his colleague Sam Marsh), answering the question: are lectures the best way to teach students?

Posted at April 6, 2015 3:09 PM UTC

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

56 Comments & 0 Trackbacks

Re: Five Quickies

Just a reply to your first and last point.

I look forward to talking to you and Tom about reflexive completions. I’m in Honolulu talking to Dusko Pavlovic about related things.

As for your last point, I was involved in the project with Nick and Sam. Just before I came over to Hawaii, we were down in London at the Guardian University Awards, where we were runners up in the Teaching Excellence category. You don’t see Nick or me with a tie on very often, but here’s a picture of us at the awards ceremony.

Guardian Awards picture

Sam and Nick are on the left. The chap in the middle is Sheffield MP Paul Bloomfield who got the Most Inspiring Leader in Higher Education award. The chap on the right is Tony Ryan, our Pro-Vice Chancellor for Science (the equivalent of a Dean).

Posted by: Simon Willerton on April 10, 2015 7:01 AM | Permalink | Reply to this

Re: Five Quickies

Congratulations!

Something about the upwards angle of the photo makes you look like a bunch of gangsters:

Kray twins

Posted by: Tom Leinster on April 15, 2015 6:47 PM | Permalink | Reply to this

Re: Five Quickies

In Tom’s slides, he mentions that it’s not known whether the reflexive completion of a small category is small or whether the reflexive completion of a finite category is finite.

Here’s a more basic question: is the reflexive completion of a finite category known to be small?

More generally, is there any pair of comparable universes 𝒰𝒱\mathcal{U} \preceq \mathcal{V}\,\, for which the reflexive completion of a 𝒰\mathcal{U}-small category with respect to the universe 𝒱\mathcal{V}\,\, is known to be 𝒱\mathcal{V}-small?

There are also questions to be asked about the size of reflexive completions of locally small categories, but I suppose it’s a good idea to start with the basics.

Posted by: Tim Campion on April 21, 2015 9:46 PM | Permalink | Reply to this

Re: Five Quickies

Also, does the notion of reflexive completion depend on the ambient universe? If we reflexively complete AA inside [A,Set U 1][A,Set_{U_1}] and also inside [A,Set U 2][A,Set_{U_2}], do we get the same thing?

Posted by: Mike Shulman on April 21, 2015 10:42 PM | Permalink | Reply to this

Re: Five Quickies

Tim asked:

is the reflexive completion of a finite category known to be small?

Good question. I don’t know!

It’s perhaps worth noting that this is all very set-based. If we’re enriching over AbAb then the reflexive completion of a field kk, viewed as a one-object AbAb-category, is the AbAb-category of finite-dimensional kk-vector spaces. This is, of course, not finite, though it is essentially small.

I’ve never got into the formalism of universes, so I certainly don’t know the answer to the second question. Can you phrase your question categorically?

Posted by: Tom Leinster on April 21, 2015 11:02 PM | Permalink | Reply to this

Re: Five Quickies

All I mean by “the reflexive completion (A)\mathcal{R}(A) of AA with respect to 𝒰\mathcal{U}\,\,” is the construction which takes the reflexive elements of [A op,Set 𝒰][A^\mathrm{op},\mathsf{Set}_{\mathcal{U}}]. So for example, when 𝒰\mathcal{U} is the universe of finite sets, the “reflexive completion fin(A)\mathcal{R}_{fin}(A) of AA with respect to finite sets” is the category of presheaves which take values in the category of finite sets, as opposed to (A)\mathcal{R}(A), which consists of reflexive presheaves that may take values in infinite sets.

How does this play out when we characterize the reflexive completion in ways other than this construction? One characterization in your slides is that for small AA, A(A)A \to\mathcal{R}(A) is essentially terminal among dense-codense functors ABA \to B. I take it that BB is meant to range over all locally small categories here. If we change universes to finite sets, we get the statement that if AA is finite, then A fin(A)A \to \mathcal{R}_{fin}(A) is terminal among dense-codense functors ABA \to B where BB is required to have finite homsets. So (A)\mathcal{R}(A) and fin(A)\mathcal{R}_{fin}(A) satisfy different universal properties. And similarly 𝒰(A)\mathcal{R}_{\mathcal{U}}(A) will have a different universal property for each universe 𝒰\mathcal{U}.

This is no different, really, from other “completions” like the completion under 𝒰\mathcal{U}-small colimits. The only reason to believe things will be any different here is the vague idea that a “self-duality” condition is usually a kind of “smallness” condition.

Posted by: Tim Campion on April 22, 2015 10:12 PM | Permalink | Reply to this

Re: Five Quickies

By the way, if the theorem that reflexive completions are Cauchy-complete is still true for enriched categories, then there will be finite enriched categories whose reflexive completion is not even essentially small. E.g. no small suplattice-enriched category is Cauchy-complete. I would guess that in this case the reflexive completion is also universe-dependent. So, as Tom said, the open questions are all very set-based.

Posted by: Mike Shulman on April 23, 2015 9:15 PM | Permalink | Reply to this

Re: Five Quickies

The notion of conjugation is universe-independent, though of course there is the usual size issue if you start with a non-small category. Thus, the notion of reflexivity is also universe-independent.

So Mike’s question reduces to this, without talking about universes:

Given a (uncountable strongly) inaccessible cardinal κ\kappa, if 𝒜\mathcal{A} is κ\kappa-small and XX is a reflexive presheaf on 𝒜\mathcal{A}, then is XX a κ\kappa-small presheaf?

Here, you can interpret “κ\kappa-small” in the obvious way as “fewer than κ\kappa elements”, or you can take it to mean “κ\kappa-presentable” in the sense of locally presentable categories.

A question in a similar vein is this:

Is the reflexive completion of a preorder also a preorder?

The answer is yes-by-definition if you think of preorders as 𝟚\mathbb{2}-enriched categories. But you can also think of preorders as Set\mathbf{Set}-enriched categories, and the answer doesn’t change: the conjugate of any presheaf is guaranteed to be a subterminal object, so reflexive presheaves must be subterminal, hence comprise a preorder.

Posted by: Zhen Lin on April 22, 2015 8:58 AM | Permalink | Reply to this

Re: Five Quickies

Here’s an observation which surprises me.

Let’s generalize the reflexive completion to locally small categories by taking C\mathcal{R}C to be the fixed points of the adjunction induced as in the small case between the free cocompletion 𝒫C\mathcal{P}C and the free completion 𝒫 C\mathcal{P}^\dagger C.

Now, if CC is cocomplete, then the Yoneda embedding y:C𝒫Cy: C \to \mathcal{P}C has a left adjoint L:𝒫CCL: \mathcal{P}C \to C, which sends a presheaf XX to the XX-weighted colimit of the identity functor. Then X^=λa.Hom(X,ya)λa.Hom(LX,a)=y LX\hat X =\lambda a. \mathrm{Hom}(X,ya) \cong \lambda a. \mathrm{Hom}(LX,a) = y^\dagger LX where y :C𝒫 Cy^\dagger : C \to \mathcal{P}^\dagger C is the coYoneda embedding. That is, for every XX, X^\hat X is representable. So X^ˇ\check{\hat X} is also representable. It follows that CCC \simeq \mathcal{R}C. Dually, CCC \simeq \mathcal{R}C if CC is complete, too.

I was expecting to need to require that CC be both complete and cocomplete in order to get CCC \simeq \mathcal{R}C!

Posted by: Tim Campion on April 23, 2015 1:05 AM | Permalink | Reply to this

Re: Five Quickies

You’re right, it is true that any complete category is reflexively complete (where for the present purposes, “category” means “locally small category”). As you say, it’s interesting that completeness or cocompleteness implies reflexive completeness — you don’t need both.

You haven’t fallen into the trap that some people do, guessing that complete \iff reflexive complete. As pointed out on slide 17 of my talk, \iff holds for posets but only \implies holds for categories more generally.

However, I don’t think your argument’s quite right. Unless CC is small, conjugacy does not define an adjunction between the free small-cocompletion 𝒫C\mathcal{P}C and the free small-completion 𝒫 C\mathcal{P}^\dagger C. It’s not the adjointness that fails, it’s simply that the conjugate of a small presheaf needn’t be small. You can still make the basic definitions, as on slide 10, but a little more care is needed.

Posted by: Tom Leinster on April 23, 2015 1:17 AM | Permalink | Reply to this

Re: Five Quickies

Ah, thanks for setting me straight!

So in the slides you define a reflexive presheaf on a locally small category to be a small one whose conjugate is small, and which is canonically isomorphic to its double conjugate.

Does this definition recover the universal snug embedding property? Is it idempotent?

And what happens when we bring this back to posets (and shrink the universe)? Is there a “little Dedekind-MacNeille completion”, defined analogously, which is to finite meets and joins as the usual Dedekind-MacNeille completion is to arbitrary meets and joins?

Posted by: Tim Campion on April 23, 2015 2:40 AM | Permalink | Reply to this

Re: Five Quickies

What goes wrong with his argument?

Posted by: Mike Shulman on April 23, 2015 7:15 AM | Permalink | Reply to this

Re: Five Quickies

Well, the way Tim defined C\mathcal{R}C is invalid, because it refers to an adjunction that doesn’t exist. Suppose, for instance, that CC is a large discrete category. The empty functor C opSetC^{op} \to Set is small, but its conjugate is the terminal functor CSetC \to Set, which is not small. So conjugation doesn’t define a functor 𝒫C𝒫 C\mathcal{P}C \to \mathcal{P}^\dagger C.

So the issue is that the conjugate of a small presheaf needn’t be small (and the conjugate of a non-small presheaf needn’t even be defined). It therefore seems to be necessary to define reflexivity as follows: a presheaf XX is reflexive if XX is small, Xˇ\check{X} is small, and the unit map XXˇ^X \to \hat{\check{X}} is iso.

The argument for “complete \implies reflexively complete” in our paper (not yet finished) runs as follows. On any category, any small presheaf is a small colimit of representables, so the conjugate of any small presheaf is a small limit of representables. Hence on a complete category, the conjugate of any small presheaf is representable — and in particular, any reflexive presheaf is representable.

Posted by: Tom Leinster on April 23, 2015 11:42 AM | Permalink | Reply to this

Re: Five Quickies

What I meant was, it seems to me like the argument in Tim’s third paragraph still works for the correct definition of C\mathcal{R}C. It looks quite similar to yours, in fact.

Posted by: Mike Shulman on April 23, 2015 2:23 PM | Permalink | Reply to this

Re: Five Quickies

Oh I see. Right, agreed — and it is indeed the same argument.

Posted by: Tom Leinster on April 23, 2015 3:14 PM | Permalink | Reply to this

Re: Five Quickies

One of the things you ask for on your slides is an “explicit construction” of the reflexive completion. Can you say any more about what you would consider “explicit”? For instance, any construction of the reflexive completion will specialize to a construction of the Dedekind-MacNeille real numbers; is there some other known construction of those that you would consider “more explicit” than the usual one?

Posted by: Mike Shulman on April 23, 2015 7:41 AM | Permalink | Reply to this

Re: Five Quickies

That’s an interesting point about the Dedekind-MacNeille construction of the reals; I hadn’t thought of that.

“Explicit” is of course a vague term. I had in mind the fact that the Cauchy-completion of a (Set-enriched) category AA can be described explicitly as the category where:

  • the objects are the idempotents (a,e:aa)(a, e: a \to a) in AA
  • a map (a,e)(a,e)(a, e) \to (a', e') is a map f:aaf: a \to a' such that efe=fe' f e = f (or equivalently ef=f=fee' f = f = f e)
  • the identity on (a,e)(a, e) is ee
  • composition is as in AA.

That description makes it instantly clear that the Cauchy completion of a small (respectively, finite) category is small (respectively, finite). If we had anything similar for the reflexive completion then we could immediately answer “yes” to the questions about the reflexive completion of a small/finite category, and maybe also answer some of these questions about universes too.

Posted by: Tom Leinster on April 23, 2015 11:51 AM | Permalink | Reply to this

Re: Five Quickies

I’m curious about your proof that reflexively-complete categories have JJ-limits iff JJ is either empty or absolute. In particular, what becomes of it constructively? Does the condition become “JJ is absolute if it is inhabited”?

Posted by: Mike Shulman on April 23, 2015 9:17 PM | Permalink | Reply to this

Re: Five Quickies

I don’t know. It’s a funny result, not what I would have guessed, but it seems to be correct.

(Well, let me fine-tune your statement slightly: the theorem is actually about limits in reflexive completions of small categories, which is a narrower class than all reflexively complete categories. E.g. any large discrete category is reflexively complete, but it doesn’t have a terminal object.)

Here’s the shape of the current proof. Let JJ be a small category. From JJ, construct a certain other small category AA and a certain functor D:J(A)D: J \to \mathcal{R}(A). Let’s view (A)\mathcal{R}(A) as a subcategory of A^\widehat{A}. Supposing that JJ is nonempty and JJ-limits are not absolute, we prove that the limit of DD in A^\widehat{A} is not reflexive. Since the inclusion (A)A^\mathcal{R}(A) \hookrightarrow \widehat{A} preserves limits, DD has no limit in (A)\mathcal{R}(A).

It would be nice to rephrase this proof more constructively, and generally smarten it up; that’s on the “to do” list.

Posted by: Tom Leinster on April 24, 2015 12:37 AM | Permalink | Reply to this

Re: Five Quickies

any large discrete category is reflexively complete, but it doesn’t have a terminal object

Hmm, that makes me somewhat suspicious of the whole business of defining reflexive completion of non-small categories using small presheaves.

Supposing that JJ is nonempty and JJ-limits are not absolute, we prove that the limit of DD in A^\widehat{A} is not reflexive.

That would, of course, be the obvious part of the proof to un-contrapositive-ize to make it constructive, i.e. assume that the limit of DD in A^\widehat{A} is reflexive and see what you can prove. I look forward to hearing what you come up with!

Posted by: Mike Shulman on April 24, 2015 4:06 AM | Permalink | Reply to this

Re: Five Quickies

Hmm, that makes me somewhat suspicious of the whole business of defining reflexive completion of non-small categories using small presheaves.

If you have other ideas for how to do it, I’d be very interested to hear them.

We were more or less following Isbell in defining it that way. (I say “more or less” because he used a size condition on presheaves which, as far as we know, is not quite the same as smallness.)

But it’s a more intuitive idea than it seemed to me at first. Maybe that’s just because I’ve got used to it, or maybe it’s because of the following analogy with Fourier transforms.

Let’s consider functions (measurable, say) f: n.f: \mathbb{R}^n \to \mathbb{C}. Not every such function has a Fourier transform. In order to define the Fourier transform f^\hat{f} of ff, we need to ask for ff to be integrable. Even so, f^: n\hat{f}: \mathbb{R}^n \to \mathbb{C} needn’t be integrable. But if f^\hat{f} is integrable, we can define the dual Fourier transform f^ˇ: n.\check{\hat{f}}: \mathbb{R}^n \to \mathbb{C}. (By “dual Fourier transform” I mean the usual formula for Fourier transform but with a change of sign in the exponential; it’s sometimes called the inverse Fourier transform, even though it doesn’t always give an inverse.)

This leads us to consider those functions ff on n\mathbb{R}^n such that ff is integrable, f^\hat{f} is integrable, and f=f^ˇf = \check{\hat{f}}. And that’s like the definition of the reflexive completion of CC: it consists of those Set-valued functors FF on CC such that FF is small, F^\hat{F} is small, and the unit FF^ˇF \to \check{\hat{F}} is an isomorphism.

Now one can argue that this framework for Fourier transforms is unsatisfactory, what with continually having to worry about the space of functions we’re working with. But it does at least mean that the framework for reflexive completion has some respectable precedent.

Posted by: Tom Leinster on April 24, 2015 10:50 AM | Permalink | Reply to this

Re: Five Quickies

Here’s one. An arbitrary presheaf F:CSetF:C\to Set has a conjugate F^:C opSET\hat{F}:C^{op}\to SET that takes values in a larger universe. Thus, we could define a SetSet-valued presheaf FF to be reflexive if F^\hat{F} is also SetSet-valued and FF^ˇF \to \check{\hat{F}} is iso. One could think of this as also like the Fourier example, with the SETSET-valued presheaves playing the role of the “distributions” — every function has a distributional Fourier transform, and we can then just restrict attention to those functions whose distributional Fourier transform happens to be another function.

Posted by: Mike Shulman on April 24, 2015 6:50 PM | Permalink | Reply to this

Re: Five Quickies

I don’t doubt that you’re right, but as I said in a previous comment, I’ve never got into the formalism of universes. When you say “a larger universe”, this seems to assume a certain foundational framework. Larger than what?

In the work I’ve been doing, I haven’t committed to any particular foundation. If pushed, I guess I’d say that SetSet is any category satisfying ETCS. But really I’d prefer to work independently of any particular foundational commitment.

I tried the nLab for enlightenment, but the page on Grothendieck universes was very ZFC-y (transitive sets and so on). The page on universes in a topos talks about subcategories of an ETCS category, which in the notation I’m using means a subcategory of SetSet, whereas you’re passing to a larger category, called SETSET. So, I’m not getting it.

Posted by: Tom Leinster on April 24, 2015 7:06 PM | Permalink | Reply to this

Re: Five Quickies

The page on universes in a topos talks about subcategories of an ETCS category, which in the notation I’m using means a subcategory of Set, whereas you’re passing to a larger category, called SET.

Just change the notation: SET is an ETCS category and Set is a subcategory of it.

Posted by: Mike Shulman on April 24, 2015 8:02 PM | Permalink | Reply to this

Re: Five Quickies

OK. But I’d rather stick with the notation in my slides, so that I don’t get confused. If I understand you correctly, what you call SETSET is what I call SetSet, and what you call SetSet is some subcategory setset of my SetSet. Right?

Let’s stick with the notation in my slides. Then your last comment says: any F:CsetF: C \to set has a conjugate F^:C opSet\hat{F}: C^{op} \to Set.

In Isbell’s paper and in my slides, a slightly different statement is made: any small F:CSetF: C \to Set has a conjugate F^:C opSet\hat{F}: C^{op} \to Set.

We can compare and contrast. For a functor F:CSetF: C \to Set, is it true that if FF is small then FF takes values in setset? Or conversely? I guess it must depend on exactly what setset is.

Posted by: Tom Leinster on April 24, 2015 8:56 PM | Permalink | Reply to this

Re: Five Quickies

Let’s stick with the notation in my slides.

Okay, but then we have to change all the definitions:

  • A locally small category is one where ob(C)Setob(C)\in Set and where each hom C(a,b)sethom_C(a,b)\in set
  • A small category is a locally small one where ob(C)setob(C)\in set
  • A small presheaf is one that is a colimit of representables indexed by a small category (in the above sense).

If setset is closed under colimits of its own size (as surely ought to be assumed), then a small presheaf on a locally small category is automatically setset-valued, and the converse will admit the usual sort of counterexamples (e.g. the terminal presheaf on a non-small discrete category).

Posted by: Mike Shulman on April 25, 2015 7:04 AM | Permalink | Reply to this

Re: Five Quickies

we have to change all the definitions

Why?

By a locally small category, I meant (as is of course standard) a category enriched in SetSet, not in some subcategory of SetSet. And I want to consider functors from locally small categories into SetSet. More generally, we’re interested in suitable monoidal categories 𝒱\mathcal{V}, and 𝒱\mathcal{V}-functors from 𝒱\mathcal{V}-categories into 𝒱\mathcal{V}.

All that seems to me to be absolutely standard. But the universe approach that you’re describing doesn’t seem to square with this. So I’m puzzled.

Posted by: Tom Leinster on April 25, 2015 12:45 PM | Permalink | Reply to this

Re: Five Quickies

The reason it doesn’t square with it is because you insisted on also having “SetSet” be the larger category of sets. The way universes work is that you have a subcategory of “small sets” inside the category of all sets, and whenever the word “small” appears it refers to the small sets. So if you want to say that “locally small” means “enriched in SetSet”, then you have to call the subcategory SetSet and use something else like SETSET for the supercategory, whereas if you want to call the supercategory SetSet then you have to call the subcategory something else like setset and say that “locally small” means “enriched in setset”. You can’t have it both ways.

Posted by: Mike Shulman on April 25, 2015 4:23 PM | Permalink | Reply to this

Re: Five Quickies

The reason it doesn’t square with it is because you insisted on also having “SetSet” be the larger category of sets.

I don’t think that’s accurate. I was just trying to understand you; I didn’t suggest having two different categories of sets at all. As my last comment said, all I want to do is work with functors from a 𝒱\mathcal{V}-category into 𝒱\mathcal{V}, in particular in the case 𝒱=Set\mathcal{V} = Set. That’s my only requirement.

Specifically, I was trying to understand your proposal here, which invokes two different categories of sets. I noted here that in the nLab page on universes, the larger category is an ETCS category, and I said that in the context of my slides, the only ETCS category in sight was the one in which the presheaves take values. I understood your comment here to mean that this is the larger of the two categories. So I thought you were telling me that if I wanted to consider functors into a category denoted by SetSet (as is standard), then SetSet was to be the larger category. There was no “insisting”.

Now I think that’s not what you meant. I have no doubt whatsoever that you know what you’re talking about; I was just having trouble understanding you.

Posted by: Tom Leinster on April 25, 2015 4:57 PM | Permalink | Reply to this

Re: Five Quickies

Oh, no, sorry. I just meant that SETSET was to be the ETCS category referred to by the nLab, not the ETCS category into which you were considering functors. The ETCS category into which you consider functors should be the subcategory, which we can denote SetSet.

Posted by: Mike Shulman on April 25, 2015 5:30 PM | Permalink | Reply to this

Re: Five Quickies

It’s been bothering me that so far for all Set\mathsf{Set}-enriched examples other than posets, the reflexive completion seems to be just the idempotent completion with initial and terminal objects adjoined (although sometimes, as when the category is complete or cocomplete, the new intial/terminal object is not freely adjoined – it agrees with the existing one. I’ll have to think about why that is).

Here’s an example where that’s not the case. Take A=BA = \mathbf{B} \mathbb{Z} to be the walking automorphism. Then, if I’m not mistaken, A\mathcal{R}A consists of the free \mathbb{Z}-sets. This is the free coproduct completion of the original category.

Posted by: Tim Campion on April 25, 2015 12:07 AM | Permalink | Reply to this

Re: Five Quickies

Sorry, that can’t be right. It contradicts Tom & Tom’s result about the reflexive completion of a group – it simply has initial and terminal objects adjoined.

Posted by: Tim Campion on April 25, 2015 12:11 AM | Permalink | Reply to this

Re: Five Quickies

It’s very generous of you to assume that because your result and ours disagree, it must be yours that’s wrong! In any case, I appreciate the opportunity to kick the tyres on our arguments.

So, let’s do what you suggest and consider A=BA = \mathbf{B}\mathbb{Z} and its reflexive completion. It’s not too hard to see that for any GG, the conjugate of any GG-set is free; so in particular, any reflexive GG-set is free. The question is: which free GG-sets are reflexive? And anyway, that’s the question you raise for G=G = \mathbb{Z}.

The group \mathbb{Z} is abelian, so a left \mathbb{Z}-set is the same as a right \mathbb{Z}-set. Also, the two types of conjugation (^\hat{} and ˇ\check{}) are the same. So, we can speak of just “the conjugate of a \mathbb{Z}-set”.

Let XX be the free \mathbb{Z}-set on a set SS. Then XX is the copower S×S \times \mathbb{Z}. By adjointness, conjugacy converts colimits into limits. Hence the conjugate of XX is the power S\mathbb{Z}^S.

What does S\mathbb{Z}^S look like as a \mathbb{Z}-set? If SS is empty then so is XX, and the empty \mathbb{Z}-set is indeed reflexive. Assume now that SS is not empty, and choose tSt \in S. The action of \mathbb{Z} on S\mathbb{Z}^S is free, and each orbit contains exactly one element of the set

{z S:z t=0} S. \{ z \in \mathbb{Z}^S : z_t = 0 \} \subseteq \mathbb{Z}^S.

Hence the orbits are in bijection with this set, which of course is in bijection with S1\mathbb{Z}^{S - 1}, where S1S - 1 denotes SS with one element removed. Hence the conjugate of XX is the free GG-set on the set S *= S1S^\ast = \mathbb{Z}^{S - 1}.

Repeating the argument, the double conjugate of XX is the free GG-set on S **S^{\ast\ast}.

If XX is reflexive then the orbit-sets of XX and its double conjugate are in bijection, so SS **S \cong S^{\ast\ast}. We do have SS **S \cong S^{\ast\ast} if SS is a one-element set. But otherwise, a little cardinal arithmetic shows that SS is not isomorphic to S **S^{\ast\ast}, so XX is not reflexive.

The same argument works for an arbitrary group (now paying attention to left vs. right GG-sets, but that’s no trouble).

It also brings to light the exceptional case: when GG is the two-element group, the reflexive completion consists not only of the initial GG-set, the terminal GG-set, and the free GG-set G̲\underline{G} on one element, but also the free GG-set on two elements. This is closely related to the fact that

G̲+G̲G̲×G̲ \underline{G} + \underline{G} \cong \underline{G} \times \underline{G}

in the category of GG-sets — or more crudely, the fact that

2+2=2×2. 2 + 2 = 2 \times 2.

It also provides an example of what you’re looking for: a non-posetal category AA whose reflexive completion is not just the Cauchy completion of AA with initial and terminal objects somehow adjoined.

Posted by: Tom Leinster on April 25, 2015 1:24 AM | Permalink | Reply to this

Re: Five Quickies

Very nice! My not-very-interesting error was to mix up sums and products. This definitely leaves me with the feeling that reflexive presheaves are “sporadic” objects.

Here’s another attempt at an observation: If A=⨿ i=1 nA iA = \amalg_{i=1}^n A_i with n>1n \gt 1 (it might be infinite), then (⨿ iA i)\mathcal{R}(\amalg_i A_i) can be obtained from ⨿ i(A i)\amalg_i \mathcal{R}(A_i) by freely adjoining initial and terminal objects, and then identifying the new initial object with the initial object of (A i)\mathcal{R}(A_i) if that initial object corresponds to the empty presheaf on A iA_i (and dually identifying the terminal objects which correspond to empty copresheaves).

For X^= a⨿ iA i[Xa,⨿ iA i(a,)]= i aA i[Xa,A i(a,)]\hat X = \int_{a \in \amalg_i A_i} [Xa,\amalg_i A_i (a,-)] = \prod_i \int_{a \in A_i} [Xa,A_i(a,-)] so X^\hat X is null unless XX is supported on at most one of the A iA_i, in which case X^\hat X is supported on the same A iA_i, and is calculated as it would be on A iA_i alone. If XX is null, then X^\hat{X} is constantly 1. These facts and their duals show that (⨿ iA i)\mathcal{R}(\amalg_i A_i) consists of the reflexive presheaves on the A iA_i (set to be empty on the other components), along with the empty and terminal presheaves. The new empty presheaf is identified with the initial presheaf on an A iA_i if that presheaf is actually empty.

Posted by: Tim Campion on April 25, 2015 5:10 AM | Permalink | Reply to this

Re: Five Quickies

Tom has shown that the codensity monad of FinSetSetFinSet \to Set is the ultrafilter monad.

Question: is the codensity monad of CtbleSetSetCtbleSet \to Set (where CtbleSetCtbleSet is the category of at-most-countable sets) the monad of countably complete ultrafilters?

I suspect this is maybe not the case, since the inclusion of {0,1,2}Set\{0,1,2\} \to Set is not the ultrafilter monad - 2 is “too small”; similarly \mathbb{N} might be “too small”.

But if the answer is affirmative, then CtbleSetCtbleSet is codense in SetSet if there are no measurable cardinals. In this case, CtbleSetSetCtbleSet \to Set is a snug embedding (it is always dense, since CtbleSetCtbleSet contains 1), and I suspect it might be the reflexive completion.

More broadly: what are some interesting examples of snug embeddings? Those are the places to look for interesting examples of reflexive completions.

Posted by: Tim Campion on April 29, 2015 6:19 PM | Permalink | Reply to this

Re: Five Quickies

Interesting questions, and again, I don’t know the answer.

All I can say is that Isbell’s paper — where the stories of density and reflexive completion began — contains some results of interest here. Theorem 2.5 states that a countable (infinite) set is codense as a subcategory of SetSet iff no measurable cardinals exist, and there’s discussion of related issues. That’s almost the same as the result you just stated; I don’t know whether you knew it by reading Isbell or just figured it out for yourself.

Tom has shown that the codensity monad of FinSetSetFinSet \to Set is the ultrafilter monad.

Although that is proved in my paper on codensity and ultrafilters, it was originally proved in 1971 by Kennison and Gildenhuys.

Posted by: Tom Leinster on April 29, 2015 9:08 PM | Permalink | Reply to this

Re: Five Quickies

Theorem A.5 of Adamek–Rosicky Locally presentable and accessible categories proves essentially that a small codense subcategory of SetSet is the same as an upper bound on the size of all measurable cardinals.

Posted by: Mike Shulman on April 29, 2015 9:22 PM | Permalink | Reply to this

Re: Five Quickies

Wow! That’s really cool! I hadn’t read this part of Isbell’s paper and I honestly thought that was too good to hope for!

Similarly, the category of sets of cardinality 3\leq 3 (or just BSet(3,3)\mathbf{B}Set(3,3) is snug in FinSetFinSet, (after all, its codensity monad is the ultrafilter monad, which is the identity on finite sets) and assuming this is the reflexive completion, this gives an example of a finite category whose reflexive completion is not finite (although it is essentially small).

Posted by: Tim Campion on April 29, 2015 11:02 PM | Permalink | Reply to this

Re: Five Quickies

Aha, I hadn’t tried to put this together before.

Let me get this straight. Assume that SetSet contains no measurable cardinals. Write N\mathbf{N} for the full subcategory of SetSet consisting of a single countably infinite set. Then Isbell’s result states that N\mathbf{N} is codense in SetSet.

If I’m not mistaken, any full subcategory of SetSet containing at least one nonempty set is dense. In particular, N\mathbf{N} is dense in SetSet.

Since N\mathbf{N} is small, the inclusion NSet\mathbf{N} \hookrightarrow Set is small-dense and small-codense. So in the terminology of my slides, it’s a “snug embedding”: a full, faithful, small-dense and small-codense functor.

The theorem on page 13 of my slides characterizes the reflexive completion (N)\mathcal{R}(\mathbf{N}) as the largest category into which N\mathbf{N} embeds snugly. Since N\mathbf{N} embeds snugly into SetSet, SetSet embeds snugly into (N)\mathcal{R}(\mathbf{N}). In particular, there is a full and faithful functor Set(N)Set \to \mathcal{R}(\mathbf{N}). Since SetSet is not essentially small, neither is (N)\mathcal{R}(\mathbf{N}).

If I haven’t messed up, we’ve now shown: under the assumption that SetSet contains no measurable cardinals, there is some small category whose reflexive completion is not essentially small.

Right?

I’ll come to the finite case in another comment, but just for now, what do you mean by BSet\mathbf{B}Set?

Posted by: Tom Leinster on April 30, 2015 12:03 AM | Permalink | Reply to this

Re: Five Quickies

Oh, that’s B(Set(3,3))\mathbf{B}(Set(3,3)) – the endomorphism monoid of the set with 3 elements, regarded as a category. That’s me being a little too cute – although it’s interesting to see that a monoid can have a pretty big reflexive completion, given that you’ve shown a group can’t.

I wasn’t sure from your slides, but I guess you’re saying that when ACA \to C is a snug embedding, the canonical functor C(A)C \to \mathcal{R}(A) is itself an embedding (by which I mean fully faithful), right? Assuming that, the argument looks good to me!

Posted by: Tim Campion on April 30, 2015 2:12 AM | Permalink | Reply to this

Re: Five Quickies

Thanks for the clarification.

I don’t think the point about monoids is too cute! As you say, it’s interesting that reflexively completing a group barely enlarges it, but reflexively completing a certain 27-element monoid turns it into something infinite.

The slides don’t say it, but our paper (in draft) will: when G:ACG: A \to C is a snug embedding, there’s a unique snug embedding C(A)C \to \mathcal{R}(A) making the evident triangle commute.

If you view (A)\mathcal{R}(A) as a subcategory of A^\hat{A}, this embedding C(A)C \to \mathcal{R}(A) is nothing more than the nerve-type functor CA^C \to \hat{A} induced by GG. Since GG is dense, the functor C(A)C \to \mathcal{R}(A) is full and faithful. The “nice property” on slide 12 then implies that it’s snug.

Posted by: Tom Leinster on April 30, 2015 2:19 AM | Permalink | Reply to this

Re: Five Quickies

One might even want to state this (putative) result in the following way. Let μ\mu be the smallest measurable cardinal, if it exists, and let Set μSet_\mu denote the sets smaller than μ\mu, or else all of SetSet (ZFC implies measurable cardinals are inaccessible, but not ZF, so I’m not sure if I doing anything suspicious here). Then do the enriched version of your results using Set μSet_\mu. It should be the case that there is a ‘small’ category (i.e. an internal category in Set μSet_\mu when that category is a topos) such that its reflexive completion is not ‘essentially small’ (i.e. it is not the externalisation of an internal category in Set μSet_\mu).

What the terms in scare quotes mean (or should mean) when Set μSet_\mu is not a topos I don’t know. It probably would be handled by fibred categories or similar. Note that in ZF with the axiom of determinacy ω 1\omega_1, the first uncountable ordinal (denoted 1\aleph_1 when Choice is present), is measurable. So Set μ=Set ω 1Set_\mu = Set_{\omega_1} is the category of countable sets. The content of the (putative) result is then, morally, that there is a countable category whose reflexive completion is not equivalent to a countable category. This is a quasi-sensible-sounding statement, but as it requires the axiom of determinacy to prove ω 1\omega_1 measurable, it has to be a bit trickier than that (and apparently the consistency strength of AD is very high).

Posted by: David Roberts on April 30, 2015 4:18 AM | Permalink | Reply to this

Re: Five Quickies

Interesting!

I had some related but different thoughts.

All I want to assume about SetSet is that it satisfies the ETCS axioms. Now, we know that given an ETCS category, it’s possible to build another ETCS category \mathcal{E} that fails the axiom of choice. If the axiom of choice fails badly enough then the full subcategory of \mathcal{E} consisting of the single object 3=1+1+13 = 1 + 1 + 1 should be codense. It should also be dense. In that case, we’ve got a finite SetSet-enriched category whose reflexive completion isn’t even small.

There may be a much easier way of implementing this basic idea, without thinking about ETCS at all. Maybe there’s some easily-constructed large topos \mathcal{E} such that the full subcategory consisting of the single object 1+1+11 + 1 + 1 is finite, dense and codense. That would then be an example of a finite category whose reflexive completion isn’t even small.

Away from set theory, I believe I know an example of a small category whose reflexive completion isn’t small. If I understand correctly, Isbell’s Theorem 2.6 states that the one-object full subcategory [0,1] 2[0, 1]^2 of (compact Hausdorff spaces) is codense, as well as dense. So by the usual argument, the reflexive completion of this small subcategory is not essentially small.

Posted by: Tom Leinster on April 30, 2015 12:05 PM | Permalink | Reply to this

Re: Five Quickies

Is [0,1] 2[0,1]^2 really dense in compact Hausdorff spaces? It doesn’t admit many maps to, say, the Cantor set…

Actually, I’m pretty sure that compact Hausdorff spaces don’t admit a small dense generator, because that would almost make them locally presentable. But the opposite category is locally presentable, and a category and its opposite can never both be locally presentable. In fact there’s a result of Adamek, Rosicky, and Trnkova saying that under Vopenka’s principle, any cocomplete category with a small dense generator is locally presentable. So if compact Hausdorff spaces have a small dense generator, Vopenka’s principle must fail.

Posted by: Tim Campion on April 30, 2015 2:32 PM | Permalink | Reply to this

Re: Five Quickies

Oops, you’re right. Thanks.

Posted by: Tom Leinster on April 30, 2015 3:29 PM | Permalink | Reply to this

Re: Five Quickies

How about this: the category of Hilbert spaces is countably acceessible and self-dual, via an object-fixing duality. So the reflexive completion of the small category of countably accessible Hilbert spaces (or just of the 1-object category 𝔹(End Hilb( 2())\mathbb{B}(End_{Hilb}(\ell_2(\mathbb{Z}))) is the large category of Hilbert spaces.

Posted by: Tim Campion on April 30, 2015 6:26 PM | Permalink | Reply to this

Re: Five Quickies

Or at least, it contains HilbHilb as a full subcategory. But they are probably the same.

Posted by: Tim Campion on April 30, 2015 6:40 PM | Permalink | Reply to this

Re: Five Quickies

(Or at least, HilbHilb is a full subcategory of the reflexive completion of the countable-dimensional Hilbert spaces.)

In fact, any self-dual category with a small dense generator also has a small codense cogenerator, given by the duals of the generator, and so has a small snug subcategory (given by the union of the dense generator and the codense cogenerator).

In particular, any self-dual accessible category has a small snug subcategory, and so the reflexive completion of that small snug subcategory is large. I wonder if the reflexive completion always agrees with the original accessible category?

Another example, given by Makkai and Pare is the category of sets and partial bijections. In this case the category is finitely presentable, with the finitely presentable objects being the finite sets, I believe, and the duality fixes them. Actually, Makkai and Pare show that the category of partial bijections is equivalent to a subcategory of the category of semigroups determined by a finite number of equations, where the carrier set of the semigroup corresponding to a set XX is X+1X+1. This should mean that there is a finite subcategory of partial bijections which is snug in the whole large category. I’m not quite sure, because one of the “equations” has an “or” clause in it…

But this might give an example of a finite category with a large reflexive completion!

Posted by: Tim Campion on April 30, 2015 6:41 PM | Permalink | Reply to this

Re: Five Quickies

Actually, Makkai and Paré cite a paper of Isbell for this example, and in that paper, Isbell explicitly presents it as an example of a finite category (monoid, in fact) snugly (“adequately”, in his terminology) embedded in a large category. As he points out, a dense-codense object in the category of partial injections (I think that’s a preferable name to Makkai and Paré’s “partial bijections”) is given by 2, which has 7 endomorphisms in this category: the identity, transposition, either of these restricted to either element, and the empty partial injection.

Isbell’s paper also proves that SetSet admits a small snug subcategory iff there are only a set of measurable cardinals (or rather, a plainly equivalent set-theoretic hypothesis). He also asserts that the consistency of unboundedly many measurables is “gravely in doubt”. I’ve never heard (in very limited experience!) of doubt being voiced about the consistency of unboundedly many large cardinals of any type – is Isbell being fair here? Does it make a difference that he’s writing in 1968?

The paper also contains the result that if a small category AA embeds snugly into a “strongly” complete (meaning: complete and cocomplete, with intersections of large families of extremal subobjects / cointersections of large families extremal quotients) category CC, then any “strong” completion of AA extends uniquely to CC. This gives a “mapping out” property of some reflexive completions, as opposed to the “mapping in” property in Tom’s slides. Does the Dedekind-MacNeille completion for posets similarly have both “mapping out” and “mapping in” universal properties?

The (different) Isbell paper that Tom linked to also shows (Thm 2.1) that if AA is a full subcategory of an algebraic category BB, then the inclusion ABA \to B factors through the reflexive completion of AA. This establishes that several examples we’ve been talking about, including the {3}FinSet\{3\} \to FinSet, {k 2}FinVect k\{k^2\} \to FinVect_k, {2}\{2\} \to Partial injections, and {}Set\{\mathbb{N}\} \to Set (absent measurables) examples are the actual reflexive completions, and the reasoning may extend to other examples (I haven’t really read the proof, but Isbell asserts that similar reasoning applies to full subcategories of TopTop).

Rosicky has some more results on small codense subcategories. For example, an algebraic category can have one only if there are boundedly many measurables (in line with the case of SetSet – I wonder if this can be improved to locally presentable categories?); this amounts to improving the earlier observation that a small codense subcategory of a locally presentable category contradicts Vopenka’s principle.

Posted by: Tim Campion on May 1, 2015 6:28 AM | Permalink | Reply to this

Re: Five Quickies

I claimed that Isbell’s result on reflexive completions of full subcategories of algebraic categories established that {2}\{2\} \to Partial injections is the reflexive completion, but that’s not correct: the category of partial injections is not algebraic; it’s only itself a full subcategory of an algebraic category. So it’s still open what the reflexive completion of this curious monoid is, although it contains the category of partial injections as a full subcategory.

Posted by: Tim Campion on May 1, 2015 4:05 PM | Permalink | Reply to this

Re: Five Quickies

As he points out, a dense-codense object in the category of partial injections […] is given by 2

Excellent! Thanks very much for pointing that out. I see that that paper was already saved on my computer, but I’d entirely forgotten about its existence.

I was trying a very similar example yesterday morning: the object 2 of the category RelRel of all sets and relations. This contains Isbell’s category. At the point when I ran out of time and had to do other things, I’d just begun to suspect that 2 probably wasn’t (co)dense in Rel. It’s very unlikely I would have thought of restricting to those relations where each element is related to at most one other, which is what Isbell did.

Posted by: Tom Leinster on May 1, 2015 9:15 AM | Permalink | Reply to this

Re: Five Quickies

Interesting - if A is a (non-full - or is this true for full subcategories as well?) subcategory of B, then (A)\mathcal{R}(A) need not be a subcategory of (B)\mathcal{R}(B). Is the reflexive completion functorial? Is the Dedekind-MacNeille completion functorial?

Posted by: Tim Campion on May 1, 2015 4:09 PM | Permalink | Reply to this

Re: Five Quickies

Is the reflexive completion functorial?

Peter Johnstone asked this after the talk, and the answer is no — at least, not in the fullest sense of defining a functor \mathcal{R} from CatCat to CATCAT.

Here’s the proof I gave him. The two-element group C 2C_2 is a section of C 2×C 2C_2 \times C_2. If \mathcal{R} was functorial then (C 2)\mathcal{R}(C_2) would be a section of (C 2×C 2)\mathcal{R}(C_2 \times C_2). But (C 2)\mathcal{R}(C_2) has four iso classes of objects, whereas (C 2×C 2)\mathcal{R}(C_2 \times C_2) has only three, a contradiction.

Posted by: Tom Leinster on May 1, 2015 4:28 PM | Permalink | Reply to this

Re: Five Quickies

Now for the finite case. Let B\mathbf{B} be a finite full subcategory of FinSetFinSet containing at least one set with at least three elements. Then B\mathbf{B} is codense in FinSetFinSet.

Why? Well, Tim notes that the codensity monad TT of BSet\mathbf{B} \hookrightarrow Set is the ultrafilter monad, which restricts to the identity monad on FinSetFinSet. Now TT is given by the formula T(A)= B[[A,B],B] T(A) = \int_B [[A, B], B] (ASetA \in Set), and if AA is finite then this end is the same whether it’s calculated in FinSetFinSet or in SetSet. (The inclusion FinSetSetFinSet \hookrightarrow Set preserves finite limits.) So B\mathbf{B} is codense in FinSetFinSet.

The inclusion BFinSet\mathbf{B} \hookrightarrow FinSet is not only codense, but also dense, full and faithful. Hence it’s a snug embedding. But (B)\mathcal{R}(\mathbf{B}) is the largest category into which B\mathbf{B} embeds snugly, so FinSetFinSet embeds snugly into (B)\mathcal{R}(\mathbf{B}). In particular, (B)\mathcal{R}(\mathbf{B}) is not equivalent to a finite category, even though B\mathbf{B} is finite.

I agree with Tim’s guess that FinSetFinSet is the reflexive completion of B\mathbf{B}. I’ll try to check it out.

Posted by: Tom Leinster on April 30, 2015 1:49 AM | Permalink | Reply to this

Re: Five Quickies

Here’s another example with a similar feel.

The category FinVect kFinVect_k of finite-dimensional vector spaces over a field kk is equivalent to its opposite via an object-fixing duality. Since k 2k^2 (or any vector space of dimension 2\geq 2) is dense in FinVect kFinVect_k, it is also codense. So if B\mathbf{B} is the inclusion of a subcategory of FinVect kFinVect_k containing an object of dimension at least 2, then the inclusion BFinVect k\mathbf{B} \to FinVect_k is snug, and again is probably the reflexive completion.

It’s interesting that by bumping up the dimension, we can recover the same reflexive completion as in the enriched case. I wonder what the SetSet-enriched reflexive completion of B(End k(k))\mathbf{B}(End_k(k)) is?

We can try to play a similar game with finite (or finitely-generated) abelian groups. Using the classification theorem, it’s clear that the cyclic (or even: cyclic and indecomposable) groups form a cogenerator among the finite/finitely generated ones. But I suspect this cogenerator may not be codense.

Posted by: Tim Campion on April 30, 2015 2:41 PM | Permalink | Reply to this

Re: Five Quickies

Re the vector space example, FinVect kFinVect_k is of course essentially small, so it doesn’t help us get an example of a small category whose reflexive completion is large.

However, if we take kk to be a finite field and choose a finite full subcategory B\mathbf{B} of FinVect kFinVect_k containing at least one space of dimension at least 22, then as you say, the embedding BFinVect k\mathbf{B} \hookrightarrow FinVect_k is snug. Hence the reflexive completion of the finite category B\mathbf{B} (as an ordinary category) is infinite.

Posted by: Tom Leinster on April 30, 2015 3:34 PM | Permalink | Reply to this

Post a New Comment