Re: no fundamental theorems please

Re: no fundamental theorems please

[Andrej Bauer]

On Tue, Jun 23, 2009 at 11:27 AM, Miles Gould<miles@assyrian.org.uk> wrote:
> is there another name I can use for the theorem that right
> adjoints preserve limits and left adjoints preserve colimits

My teacher of category theory calls the first of these two theorems
RAPL. Maybe he can explain whether he picked it up from someone.
Somehow, LAPC does not sound so good.

Andrej


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

Re: no fundamental theorems please

[Michael Shulman]

On Wed, Jun 24, 2009 at 8:52 AM, claudio pisani<pisclau@yahoo.it> wrote:
> Of course, the proof that the object x:1->X (of Cat/X) has the slice
>  X/x -> X as a reflection in df/X (and its final object as
> reflecton map) is essentially the same of that of the standard
> Yoneda lemma, and the general case only requires a little more
> effort.

This is indeed a very nice statement of the ordinary Yoneda lemma, but
it doesn't seem capable of capturing all incarnations of the Yoneda
lemma, such as that in enriched category theory.

Mike


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

Re: no fundamental theorems please

[Steve Vickers]

Vaughan Pratt wrote:
> ...  The Yoneda Lemma usually states that J embeds (meaning
> fully) in [J^op,Set], ...

Dear Vaughan,

The usual statement is significantly stronger than that (see e.g. Mac
Lane, Mac Lane and Moerdijk, or Wikipedia). It says that, for
contravariant functors F: C -> Set, the elements of FX are in bijection
with transformations to F from the representable functor for X. Your
statement can be deduced by considering the particular case where F too
is representable.

(To put it another way, the representable presheaf for X is freely
generated - as presheaf - by a single element (the identity morphism) at
X. This then allows you to calculate the left adjoint of the forgetful
functor from presheaves over C to ob(C)-indexed families of sets.)

There can be no doubt that this strong Yoneda Lemma is vitally important
when calculating with presheaves - for example, it shows immediately how
to calculate exponentials and powerobjects. If F and G are two
presheaves, then the exponential G^F is calculated by

   G^F(X) = nt(Y(X), G^F)    (by Yoneda's Lemma)
          = nt(Y(X) x F, G)  (by definition of exponential)

I don't think you can get it and its useful consequences from your
weaker statement, even if you start strengthening yours in the way you
suggest by supplying converses.

Another closely related and important result, though not known as
Yoneda's Lemma as far as I know, is that the presheaf category over C is
a free cocompletion of C, and the Yoneda embedding is the injection of
generators.

(By the way, I agree that category theory doesn't have to have a
Fundamental Theorem. I haven't see any compelling reason to appoint one.)

Regards,

Steve.


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

Re: no fundamental theorems please

[claudio pisani]

Of course, the proof that the object x:1->X (of Cat/X) has the slice  X/x -> X as a reflection in df/X (and its final object as reflecton map) is essentially the same of that of the standard Yoneda lemma, and the general case only requires a little more effort.
My point is that this formulation seems to me more in the "categorical spirit", stating a universal property that relates categories over X and discrete fibrations.
In fact the paradigm "categories, functors and natural transformations" can be in part replaced by "categories, functors and discrete (op)fibrations"; for instance a colimit x of the object p:P -> X of Cat/X is a reflection of p in slices over X, where the reflection map p -> X/x in Cat/X is the colimiting cone, and so on.
Furthermore, there is a clear analogy (which can be made precise with the proper choice of factorization system on posets) with the reflection of the subsets of a poset X in lower or upper sets of X (the principal sieves being a particular case).

Best regards

Claudio



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

Re: no fundamental theorems please

[Vaughan Pratt]

On 6/22/2009 2:07 PM, Paul Taylor wrote:
> Claudio, Vaughan, Ross and others have mentioned various more
> "sophisticated" versions of the Yoneda Lemma.

I don't see how supplying the missing half of an if-and-only-if is "more
sophisticated."  The Yoneda Lemma usually states that J embeds (meaning
fully) in [J^op,Set], but it could just as well state this for any
factor C between J and [J^op,Set].  In such situations it is natural to
ask whether the converse holds; it doesn't, but if one adds to
full-and-faithful the (very natural) requirement of density then it
does: the dense extensions of J are precisely the categories of
presheaves on J, by which I mean the full subcategories of [J^op,Set]
that retain J as a full subcategory (the sense of "on").  I don't call
that sophisticated.

> However, I contend that the more sophisticated the result is,
> the LESS it deserves to be called "the fundamental theorem of
> category theory".

Indeed.  Any branch of mathematics that does so only contributes to the
image of mathematics as a difficult subject.

> I particularly like Euclid's algorithm for the highest common
> factor as a historical and methodological example, Without
> meaning to dictate to number theorists how their subject should
> be organised, let me suggest for the sake of argument that it
> is a pretty good candidate for being called the "fundamental
> theorem of number theory".

That's an algorithm.  The relevant theorem is also called the
fundamental theorem of arithmetic.  One could state the essential idea
in sophisticated language as "Z is a principal ideal domain" but the
more usual statement about uniqueness of factorization of positive
integers makes number theory a more accessible subject.

> As I say, I like Euclid's algorithm because the idea has
> survived many many revolutions in the "official" foundations
> of mathematics.
>
[...] Cantor's "theorem" about a powerset being
> strictly bigger than a set. This belongs entirely to the dogma
> of set theory. When set theory is overturned, this miserable
> and wholely misguided "theorem" will go in the dustbin of
> mathematical history with it.

I like Cantor's theorem because, like Euclid's algorithm, it will
survive the revolution Paul is trying to foment here.

> But Euclid's algorithm will live forever.

As will diagonalization arguments like Cantor's.

> But [Yoneda's Lemma] still shouldn't be called the "fundamental theorem"!

Unlike the Fundamental Theorems of Arithmetic and of Algebra, the Yoneda
Lemma has not yet established itself as *the* fundamental theorem of
category theory.  Nor will it unless a reasonable consensus to that
effect emerges.  I suggest waiting a few years before coming to any
conclusion about whether CT has an FT, and if so what it is.

Vaughan Pratt


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

Re: no fundamental theorems please

[Michael Barr]

Let me second Paul's observation.  Going from the Yoneda lemma to a more
sophisticated version would be analogous to saying that the Fundamental
Theorem of calculus is "really" Stokes's theorem in its most general form
(that the integral of form over the boundary of an n-dimensional compact
region is the integral of the differential of the form over the region).
The point of fundamental theorems is that they are easy to state and
somehow capture something essential about the subject.  The original
Yoneda lemma states that all the properties of an object are present in
its homfunctor.  Thus objects are really captured by the morphisms.  That
it then leads to very sophisticated extensions is the point, but it, not
they, are the basis for it all.

Michael

On Mon, 22 Jun 2009, Paul Taylor wrote:

> I see that Takuo and I have still not overcome the "royalist" forces.
>
> Claudio, Vaughan, Ross and others have mentioned various more
> "sophisticated" versions of the Yoneda Lemma.
>
> However, I contend that the more sophisticated the result is,
> the LESS it deserves to be called "the fundamental theorem of
> category theory".
>

...

> And the Yoneda Lemma will survive as long as Category Theory
> does in a recognisable form.
>
> But it still shouldn't be called the "fundamental theorem"!
>
> Paul
>

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

Re: no fundamental theorems please

[Martin Escardo]

I am sure several other readers of this list will have the same reply
to this specific point of Paul's message:

Paul Taylor wrote:
> For example, there is Cantor's "theorem" about a powerset being
> strictly bigger than a set.  This belongs entirely to the dogma
> of set theory.  When set theory is overturned, this miserable
> and wholely misguided "theorem" will go in the dustbin of
> mathematical history with it.

There is a very nice paper by Lawvere that shows that the essence of
Cantor's theorem is fundamental and beautiful:

   Originally published in: Diagonal arguments and cartesian closed
   categories, Lecture Notes in Mathematics, 92 (1969), 134-145.

   Reprinted in TAC:

   http://www.tac.mta.ca/tac/reprints/articles/15/tr15abs.html

There is also a post by Andrej Bauer in his Mathematics and
Computation blog:

   http://math.andrej.com/2007/04/08/on-a-proof-of-cantors-theorem/

Martin



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

Re: no fundamental theorems please

[Miles Gould]

I expected my term to be slightly controversial, but didn't realise what
depth of feeling existed on the subject!

So, while I thank everyone for the very enlightening discussion of
Yoneda's Lemma, and Paul for his thoughts on Fundamental Theorems, I'd
like to ask: is there another name I can use for the theorem that right
adjoints preserve limits and left adjoints preserve colimits that's (a)
a bit less of a mouthful than that and (b) emphasises the result's
importance and applicability?

Miles


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

no fundamental theorems please

[Paul Taylor]

I see that Takuo and I have still not overcome the "royalist" forces.

Claudio, Vaughan, Ross and others have mentioned various more
"sophisticated" versions of the Yoneda Lemma.

However, I contend that the more sophisticated the result is,
the LESS it deserves to be called "the fundamental theorem of
category theory".

I particularly like Euclid's algorithm for the highest common
factor as a historical and methodological example,   Without
meaning to dictate to number theorists how their subject should
be organised, let me suggest for the sake of argument that it
is a pretty good candidate for being called the "fundamental
theorem of number theory".

Gauss used the same idea to factorise polynomials, and no doubt
number theorists have many more "sophisticated" developments of it.

But the principal idea was Euclid's (or one of his colleagues),
not Gauss's, and definitely not that of any subsequent number
theorist!

Saunders Mac Lane said something about "the right" generality,
as opposed to the greatest generality.

As I say, I like Euclid's algorithm because the idea has
survived many many revolutions in the "official" foundations
of mathematics.

Theorems, like royalty, are rightly the victims of revolutions,
because the way in which we encapsulate a piece of theory as
a "theorem" depends as much on our current cultural prejudices
as it does on the real underlying mathematics.

For example, there is Cantor's "theorem" about a powerset being
strictly bigger than a set.  This belongs entirely to the dogma
of set theory.  When set theory is overturned, this miserable
and wholely misguided "theorem" will go in the dustbin of
mathematical history with it.

But Euclid's algorithm will live forever.

And the Yoneda Lemma will survive as long as Category Theory
does in a recognisable form.

But it still shouldn't be called the "fundamental theorem"!

Paul



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