Re: Codensity and the ultrafilter monad

Re: Codensity and the ultrafilter monad

[Fred E.J. Linton]

Tom Leinster <Tom.Leinster@glasgow.ac.uk> wrote, in part:

> The codensity monad of the inclusion FinSet --> Set is the ultrafilter 
> monad.  This seems a rather basic fact, but I've been unable to find it  in 
> the literature.  I'd be grateful if someone could tell me a reference.

I can't be certain, but I can easily imagine Oswald Wyler or 
Ernie Manes having noticed that fact in the dim, dark, distant past.
Perhaps Ernie will chime in :-) .

HTH. Cheers, -- Fred



[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Codensity and the ultrafilter monad

[Tom Leinster]

Dear all,

Any functor from a small category A to a complete category E induces a 
contravariant adjunction between E and Set^A.  This in turn induces a 
monad on E, the "codensity monad" of the functor.

(The construction of the adjunction is better known in its dual form, 
starting with a functor from a small category to a COcomplete category. 
For example, the usual functor from Delta into Top induces the usual 
adjunction between topological spaces and simplicial sets.)

The codensity monad of the inclusion FinSet --> Set is the ultrafilter 
monad.  This seems a rather basic fact, but I've been unable to find it in 
the literature.  I'd be grateful if someone could tell me a reference.

(I'm aware of the 1987 paper by Reinhard Börger giving a different but 
related characterization of the ultrafilter monad.)

Thanks,
Tom



[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Codensity and the ultrafilter monad

[Michel Hebert]

Hi Tom,

This appears as exercise 3.2.12(e) in Manes' book (Algebraic Theories). The
references there are Lawvere's thesis and Linton's 1966, but I don't know
if this part of the exercise is solved or mentioned explicitly there.
Best regards,
Michel

On Fri, Jun 10, 2011 at 12:25 AM, Tom Leinster
<Tom.Leinster@glasgow.ac.uk>wrote:

> Dear all,
>
> Any functor from a small category A to a complete category E induces a
> contravariant adjunction between E and Set^A.  This in turn induces a monad
> on E, the "codensity monad" of the functor.
>
> (The construction of the adjunction is better known in its dual form,
> starting with a functor from a small category to a COcomplete category. For
> example, the usual functor from Delta into Top induces the usual adjunction
> between topological spaces and simplicial sets.)
>
> The codensity monad of the inclusion FinSet --> Set is the ultrafilter
> monad.  This seems a rather basic fact, but I've been unable to find it in
> the literature.  I'd be grateful if someone could tell me a reference.
>
> (I'm aware of the 1987 paper by Reinhard Börger giving a different but
> related characterization of the ultrafilter monad.)
>
> Thanks,
> Tom

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Codensity and the ultrafilter monad

[Tom Leinster]

A few days ago, I asked where in the literature I could find the fact that 
the codensity monad of the inclusion FinSet --> Set is the ultrafilter 
monad.  Michel Hebert replied:

> This appears as exercise 3.2.12(e) in Manes' book (Algebraic Theories).  The
> references there are Lawvere's thesis and Linton's 1966, but I don't know
> if this part of the exercise is solved or mentioned explicitly there.

Thanks very much, Michel.  The references to Lawvere's thesis (Section 
III, Theorem 2) and Linton's 1966 La Jolla paper (Section 2) seem to be 
general references for the structure-semantics adjunction, which is what 
the earlier parts of the exercise are about.  The word "ultrafilter" does 
not appear in either Lawvere or Linton.

So I currently believe that Manes was the first to publish this fact.  If 
someone knows better (perhaps Bill, Fred, Anders Kock or Myles Tierney), I 
hope they will let me know.

(I suspect that John Isbell would have known it, at some level, when he 
wrote his 1960 paper "Adequate subcategories", even though the language of 
monads wasn't available then.  But I haven't found it mentioned in his 
words; Manes's exercise is the only written reference to this fact that I 
know of.)

Incidentally, I've learned how many names the codensity monad has had 
through history: it has also been called the model-induced monad/triple 
(e.g. by Appelgate and Tierney), the coadequacy monad/triple (e.g. by 
Lawvere), and the algebraic completion (e.g. by Manes).

Thanks to all who replied.

Best wishes,
Tom


> On Fri, Jun 10, 2011 at 12:25 AM, Tom Leinster
> <Tom.Leinster@glasgow.ac.uk>wrote:
>
>> Dear all,
>>
>> Any functor from a small category A to a complete category E induces a
>> contravariant adjunction between E and Set^A.  This in turn induces a monad
>> on E, the "codensity monad" of the functor.
>>
>> (The construction of the adjunction is better known in its dual form,
>> starting with a functor from a small category to a COcomplete category. For
>> example, the usual functor from Delta into Top induces the usual adjunction
>> between topological spaces and simplicial sets.)
>>
>> The codensity monad of the inclusion FinSet --> Set is the ultrafilter
>> monad.  This seems a rather basic fact, but I've been unable to find it in
>> the literature.  I'd be grateful if someone could tell me a reference.
>>
>> (I'm aware of the 1987 paper by Reinhard Börger giving a different but
>> related characterization of the ultrafilter monad.)
>>
>> Thanks,
>> Tom
>

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]