Re: Limits

Re: Limits

[Peter Freyd]

Tobias Schroeder asks:

- Can the limit of a sequence of real numbers be expressed
  as a categorical limit (of course it can if the sequence is
  monotone, but what if it is not)?

A good question. I have no answer, only a similar (and ancient)
question: is there a setting in which adjoint operators on Hilbert
spaces can be seen to be examples of adjoint functors between
categories?

As for his second question:

- Why have people chosen the term "limit" in category theory?
  (And, by the way, who has defined it first?)

In the beginning, the only diagrams that had limits were "nets", that
is, diagrams based on directed posets. I believe it was Norman
Steenrod in his dissertation who first used the term. Before his
dissertation the Cech cohomology of a space was defined only as the
numberical invarients that arose as a limit of a directed set of such
invariants. It was Steenrod who perceived that Cech cohomology could
be defined as an abelian group. For that he needed to invent the
notion of a limit of a directed diagram of groups.

In the 50s the fact that one didn't need the diagram to be directed
was considered startling.

At least two of us tried to avoid the word "limit" in this more
general setting. Jim Lambek was pushing "inf" and "sup", a suggestion
I wish I had heard. Not having heard it, I was pushing "left root" and
"right root" (one was, after all, supplying a root to a generalized
tree. sort of).

All to no avail. So now we have "finite limits" and "finitely
continuous".

Re: Limits

[jim stasheff]

The category of finite sets and isomorphisms versus the category with
objects
1,2,...,n,... and the symmetric groups \Sigma_n as morphisms

The category of `modules' over one is equivalent to
The category of `modules' over the other

Is this somewhere in the literature or just folk lore?
Maybe for one n at a time??

thanks

jim

Re: Limits

[Paul H Palmquist]

Peter Freyd wrote:

> A good question. I have no answer, only a similar (and ancient)
> question: is there a setting in which adjoint operators on Hilbert
> spaces can be seen to be examples of adjoint functors between
> categories?

I once answered a similar question.
In 1974 or 1975, I published a paper "Adjoint functors induced by adjoint
linear transformations"  in the Proceedings of the AMS.
The idea is that a pair of adjoint linear transformations between two
linear topological vectorspaces, e.g., a special case is Hilbert spaces,
naturally map to an adjoint pair of functors between the categories which
are the lattices of closed subspaces, i.e., a galois connection.

Cheers,
Paul H. Palmquist




Paul Palmquist <Paul_Palmquist@compuserve.com>@compuserve.com> on
05/16/2001 08:35:30 AM

To:   Paul Palmquist <phpalmquist@west.raytheon.com>
cc:

Subject:  categories: Re: Limits




-------------Forwarded Message-----------------

From:     Dusko Pavlovic, INTERNET:dusko@kestrel.edu
To:  [unknown], INTERNET:categories@mta.ca

Date:     5/10/01  4:29 AM

RE:  categories: Re: Limits


Peter Freyd wrote:

> A good question. I have no answer, only a similar (and ancient)
> question: is there a setting in which adjoint operators on Hilbert
> spaces can be seen to be examples of adjoint functors between
> categories?

probably not, but the they seem to be instances of the same general
structure. (it is simple, pretty old, and i am sure many have noticed it,
but since no one mentioned it, here it goes.)

let U :   Cat     ---> CAT be the embedding of small categories in all,
and
let Y: Cat^op ---> CAT map each small category A to the presheaves
Psh(A).

now look at the (pseudo)comma category U/Y. each category A is
represented in it by the yoneda embedding A-->Psh(A). the morphisms
between A-->Psh(A) and B --> Psh(B) are exactly the pairs of adjoint
functors between A and B.

on the other hand, let I: Vec---> Vec be the identity functor,
and let * : Vec^op ---> Vec take a vector space V to its dual V*.

look at the comma category I/*. each hilbert space V is represented in it
by the obvious linear map  V-->V*. the morphisms between V-->V* and
W-->W* are exactly the adjoint pairs of operators between V and W.

playing around a bit, these two comma categories can be thought of as
Chu(CAT,Set) and Chu(Vec,R) respectively. so both sorts of adjunctions
are the instances of the chu morphisms. they are the chu morphisms on the
"representation" objects, in the form X --> R^X, where R is the dualizing
object.

-- dusko

PS infact, one could start from Chu(SET,Set), and define categories as
the profunctors A-->Set^A which form a monoid with respect to the
profunctor composition. you'd get only the object part of the adjoint
functors as the morphisms of this chu, but the arrow part follows from
the adjunction (i think).

now can we characterize hilbert spaces in a similar way within
Chu(Vec,R)? this seems to be a completely different kind of question. in
particular, it is possible to define "profunctors" with respect to R or
C, like we did with respect to Set, and we can compose them, but hilbert
spaces do not seem to be monoids with respect to this composition, at
least the way it occurs to me. if there is no such composition that they
are, then hilbert spaces are like R-enriched graphs, rather than
categories.






----------------------- Internet Header --------------------------------
Sender: cat-dist@mta.ca
Received: from mailserv.mta.ca (mailserv.mta.ca [138.73.101.5])
     by sphmgaae.compuserve.com (8.9.3/8.9.3/SUN-1.9) with ESMTP id
HAA02263
     for <76600.1050@compuserve.com>; Thu, 10 May 2001 07:29:48 -0400 (EDT)
Received: (from Majordom@localhost)
     by mailserv.mta.ca (8.11.1/8.11.1) id f4AAwqm21469
     for categories-list; Thu, 10 May 2001 07:58:52 -0300 (ADT)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to
cat-dist@mta.ca using -f
Message-ID: <3AF9FA78.9968DFEE@kestrel.edu>
Date: Wed, 09 May 2001 19:18:32 -0700
From: Dusko Pavlovic <dusko@kestrel.edu>
X-Mailer: Mozilla 4.72 [en] (X11; U; SunOS 5.5.1 sun4u)
X-Accept-Language: en
MIME-Version: 1.0
To: categories@mta.ca
Subject: categories: Re: Limits
References: <200105032338.f43NcI203820@math-cl-n03.ucr.edu>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk

Re: Limits

[Dusko Pavlovic]

Peter Freyd wrote:

> A good question. I have no answer, only a similar (and ancient)
> question: is there a setting in which adjoint operators on Hilbert
> spaces can be seen to be examples of adjoint functors between
> categories?

probably not, but the they seem to be instances of the same general
structure. (it is simple, pretty old, and i am sure many have noticed it,
but since no one mentioned it, here it goes.)

let U :   Cat     ---> CAT be the embedding of small categories in all,
and
let Y: Cat^op ---> CAT map each small category A to the presheaves
Psh(A).

now look at the (pseudo)comma category U/Y. each category A is
represented in it by the yoneda embedding A-->Psh(A). the morphisms
between A-->Psh(A) and B --> Psh(B) are exactly the pairs of adjoint
functors between A and B.

on the other hand, let I: Vec---> Vec be the identity functor,
and let * : Vec^op ---> Vec take a vector space V to its dual V*.

look at the comma category I/*. each hilbert space V is represented in it
by the obvious linear map  V-->V*. the morphisms between V-->V* and
W-->W* are exactly the adjoint pairs of operators between V and W.

playing around a bit, these two comma categories can be thought of as
Chu(CAT,Set) and Chu(Vec,R) respectively. so both sorts of adjunctions
are the instances of the chu morphisms. they are the chu morphisms on the
"representation" objects, in the form X --> R^X, where R is the dualizing
object.

-- dusko

PS infact, one could start from Chu(SET,Set), and define categories as
the profunctors A-->Set^A which form a monoid with respect to the
profunctor composition. you'd get only the object part of the adjoint
functors as the morphisms of this chu, but the arrow part follows from
the adjunction (i think).

now can we characterize hilbert spaces in a similar way within
Chu(Vec,R)? this seems to be a completely different kind of question. in
particular, it is possible to define "profunctors" with respect to R or
C, like we did with respect to Set, and we can compose them, but hilbert
spaces do not seem to be monoids with respect to this composition, at
least the way it occurs to me. if there is no such composition that they
are, then hilbert spaces are like R-enriched graphs, rather than
categories.

Re: Limits

[Ross Street]

I very much agree with James Dolan's response to the question of 
comparing categorical limits and adjoint functors with their abstract 
counterparts in analysis.

Other words that have been used for "objectification" and 
"categorification" are "laxification" and "identity breaking".

The original questions were a bit like asking: "Is the plus in an 
abelian group a categorical coproduct?"  Lots of abelian groups can 
arise by taking isomorphism classes and using a categorical 
coproduct: but then we lose the beautiful universal property.

Along the same lines, I enjoy bicategories, with coproducts in their 
homcategories (preserved by composition), much more than additive 
categories. Not only is every global coproduct in such a bicategory 
also a global product, but the projections from the global products 
are right adjoint to the coprojections into the coproduct.

Ross

Re: Limits

[jdolan]

i wrote:

|phenomenon of adjoint linear operators is, in yetter's terminology, a
|sort of decategorification of the phenomenon of adjoint functors.

now that i think about i guess it was crane rather than yetter who
started using the term "categorification".

is it correct that lawvere and schanuel use the term "objectification"
(or something like that) to mean pretty much the same thing as what
crane meant by "categorification"?  i think i might actually prefer
"objectification" here but i mostly hang out near sub-communities
where "categorification" has caught on to a certain extent.

Re: Limits

[jdolan]

|A good question. I have no answer, only a similar (and ancient)
|question: is there a setting in which adjoint operators on Hilbert
|spaces can be seen to be examples of adjoint functors between
|categories?

i may as well state the obvious (not necesarily right) answer to this:
no, not quite.  rather, what seems to be going on is that the
phenomenon of adjoint linear operators is, in yetter's terminology, a
sort of decategorification of the phenomenon of adjoint functors.
decategorification is generally a somewhat destructive process,
destroying the morphisms between objects, and since the morphisms are
so intrinsic to the definition of adjoint functor it seems too much to
hope for that the decategorified phenomenon of adjoint linear
operators could actually qualify as a special case of adjoint
functors.  there are suggestive indications, though, that all of the
really interesting special cases of adjoint linear operators in
physics, for example, are decategorifications of interesting pairs of
adjoint functors.  (for example so-called "creation and annihilation
operators on fock space" have categorified analogs that live on a
categorified analog of fock space whose objects/vectors are something
like joyal's "species of structure".)

so roughly: the general phenomenon of adjoint linear operators is
technically probably not quite a genuine special case of adjoint
functors.  the actual interesting special cases of adjoint linear
operators, however, are often seen to be mere shadows of more
interesting cases of adjoint functors.

Re: Limits

[Dusko Pavlovic]

> Tobias Schroeder writes:
>  > - Can the limit of a sequence of real numbers be expressed
>  >   as a categorical limit (of course it can if the sequence is
>  >   monotone, but what if it is not)?
>
> I think I have an answer to this question (without cheating). It may
> be well known or wrong (I haven't carefully checked the details, but I
> believe that they are correct).

the view of (quasi)metric spaces as R+-categories with the hom-objects
d(x,y) goes back to lawvere's "metric spaces, generalized logic and
closed categories" from 1973. the cauchy completeness of a space was
identified with what came to be known as the cauchy completeness of the
corresponding category (see kelly's book on enriched categories, or
francis borceux handbook). and cauchy completeness of a category amounts
to the existence of certain absolute (co)limits: eg over Set, Ab, Cat...
to splitting idempotents (which can be done by taking (co)equalizers with
id).

-- dusko

re: Limits

[Martin Escardo]

Tobias Schroeder writes:
 > - Can the limit of a sequence of real numbers be expressed
 >   as a categorical limit (of course it can if the sequence is
 >   monotone, but what if it is not)?

I think I have an answer to this question (without cheating). It may
be well known or wrong (I haven't carefully checked the details, but I
believe that they are correct).

Given a metric space X with distance function d, construct a category,
also called X, as follows. The objects of the category X are the
points of the space X. An element of the hom-set X(x,y) is a triple
(r,x,y) with r a real number such that d(x,y)<=r. The composite of the
arrows r:x->y and s:y->z is the arrow s+r:x->z. This is well defined
by virtue of the triangle inequality d(x,z)<=d(x,y)+d(y,z). By virtue
of the condition d(x,x)=0, we have identities. Notice that all arrows
are mono.

Of course, because the category X is small and it is not a preordered
set, it doesn't have all limits. But some limits do exist.

CLAIM: Let x_n be a sequence of points of X, and, for each n, let the
arrow r_n:x_{n+1}->x_n be d(x_n,x_{n+1}). If the sum of r_k over k>=0
exists, then this omega^op-diagram has a categorical limit. The source
of the limiting cone is the metric limit l of the sequence. The
projection p_n:l->x_n is the sum of r_k over k>=n. If q_n:m->x_n is
another cone, then the mediating map u:l->m exists (and will be
automatically unique), because, by definition of cone and of our
category, q_n will have to be bigger than r_n, and then u=q_n-r_n does
the job.

Remarks. (1) For any given Cauchy sequence, one can construct an
equivalent Cauchy sequence for which the assumption in the second
sentence of the claim fails. Using classical logic, for any given
Cauchy sequence, one can construct an equivalent Cauchy sequence for
which the assumption holds.  

(2) In (some flavours of) constructive mathematics, the notion of a
Cauchy sequence "with fixed rate of convergence" is taken as
basic. This often is taken to mean that d(x_n,x_n+1)<=c^n for a fixed
c with 0<c<1. For such sequences, the assumption is satisfied. Recall
that a map f:X->Y is called non-expansive if d(fx,fx')<=d(x,x'). If
the natural numbers are metrized by d(m,n)=c^min(m,n) for m/=n, to get
a space N, then such a Cauchy sequence is just a non-expansive map
N->X. It converges if and only if the non-expansive map has a
non-expansive extension to N_{infty}, the metric completion of N
(which, topologically, is the one-point compactification of N). And
non-expansive maps are functors---see (3) below.

(3) Recall that a map f:X->Y is called lipschitz if there is a
constant c for which d(fx,fx')<=c.d(x,x').  A lipschitz map f:X->Y
gives rise to a functor f:X->Y defined by
f(r:x->x')=c.r:f(r)->f(x'). That is, the object part is given by the
map itself, and the arrow part is given by multiplication with the
lipschitz coefficient.

(4) We have taken the arrows r_n to be d(x_n,x_{n+1}). But actually
any choice of arrows does the job, provided the sum of r_k over k>=0
is finite.

(5) Other two conditions for the distance function of a metric space,
which were not used in the definition of the category X, are (i)
d(x,y)=0 implies x=y, and (ii) d(x,y)=d(y,x). By the first, our
category is skeletal. By the second, it is selfdual. Of course, people
have considered generalized metric spaces in which these are not
assumed to hold. See, for example, Lawvere's paper "Metric spaces,
generalized logic, and closed categories", in which he regards a
generalized metric space X as an enriched category with X(x,y)=d(x,y)
(so he has hom-numbers instead of hom-sets). Here we have hom-sets (of
numbers).

MHE

Re: Limits

[Andrej Bauer]

Tobias Schroeder <tschroed@Mathematik.Uni-Marburg.de> writes:
> So I'd be very grateful for answers to one of the following:
> - Can the limit of a sequence of real numbers be expressed
>   as a categorical limit (of course it can if the sequence is
>   monotone, but what if it is not)?

With a little bit of cheating, you can use domain theory to express
the limit as a sequence as a _colimit_ in a partially ordered set.

Let D be the partial order consisting of all the closed intervals,
including singletons [a,a], ordered by reverse inclusion. We can
embed R into D by mapping it to the maximal elements a |---> [a,a],
and under a suitable topology on D (the Scott topology), this is
a topological embedding--purists may want to throw in R as the
smallest element to obtain an honest continuous domain.

Let x_i be a Cauchy sequence of real numbers. To say that x_i is a
Cauchy sequence is to say that there exist numbers d_i such that

(1) For j >= i, the interval [x_i - d_i, x_i + d_i]
    contains [x_j + d_j, x_j + d_j].

(2) The numbers d_i become arbitrarily small: for every k
    there is i such that for all j >= i, d_i < 1/k.

(Exercise for your students: show that this is equivalent to the usual
definition of Cauchy sequence.)

In terms of the partial order D, (1) says that the intervals
[x_i - d_i, x_i + d_i] form an increasing sequence. Every increasing
sequence in D has a supremum, because an intersection of a nested
sequence of closed intervals is a closed interval, so let

    [u,v] = sup_i [x_i - d_i, x_i + d_i]

By (2), we get that u = v, and we have obtained the limit of the
sequence (x_i) as a supremum. Supremums are the _colimits_ in a
partial order. If you prefer limits, you can stand on your head.

I do not see how to get by without using the _evidence_ that (x_i) is
a Cauchy sequence, i.e., the numbers d_i. This is intuitionistic
mathematics creeping in, which is just as well.

> - Why have people chosen the term "limit" in category theory?
>   (And, by the way, who has defined it first?)

I am way too young to know the answer to this.

Andrej

Limits

[Tobias Schroeder]

Hi,
whenever I'm teaching basic category theory, students
ask me if there is a connection between limits in the
categorical sense and limits in the analytical sense,
e.g. the limit of a sequence of real numbers.
I've never found an answer to this question.

So I'd be very grateful for answers to one of the following:
- Can the limit of a sequence of real numbers be expressed
  as a categorical limit (of course it can if the sequence is
  monotone, but what if it is not)?
- Why have people chosen the term "limit" in category theory?
  (And, by the way, who has defined it first?)

Many thanks in advance

Tobias


--------------------------------------------------------------
Tobias Schröder
FB Mathematik und Informatik
Philipps-Universität Marburg
WWW: http://www.mathematik.uni-marburg.de/~tschroed
email: tschroed@mathematik.uni-marburg.de