Subject: categories: Limits

From: Tobias Schroeder <[email-masked]>
Date: Wed, 2 May 2001 15:04:00 +0200 (CEST)

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: [email-masked]

---

From: Andrej Bauer <[email-masked]>
Date: 02 May 2001 19:10:56 +0200

>   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.

>   (And, by the way, who has defined it first?)

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

Andrej

---

From: Martin Escardo <[email-masked]>
Date: Thu, 3 May 2001 13:59:08 +0100 (BST)

>   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

---

From: Dusko Pavlovic <[email-masked]>
Date: Thu, 03 May 2001 16:15:02 -0700

> 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