Limit of finite sets

Limit of finite sets

[Tom Leinster]

I've recently come across the following curious little result.  I know
how to prove it and have a use for it, but my question is: can anyone
supply a wider context or explanation?

The result is that the limit in Set of any diagram

   ... ---> S_3 ---> S_2 ---> S_1

of finite nonempty sets is nonempty.  Note that finiteness cannot be
dropped: for instance, take each S_n to be the natural numbers and
each map to be addition of 1.

Thanks,
Tom

Re: Limit of finite sets

[Prof. Peter Johnstone]

On Fri, 30 Jul 2004, Tom Leinster wrote:

> I've recently come across the following curious little result.  I know
> how to prove it and have a use for it, but my question is: can anyone
> supply a wider context or explanation?
>
> The result is that the limit in Set of any diagram
>
>    ... ---> S_3 ---> S_2 ---> S_1
>
> of finite nonempty sets is nonempty.  Note that finiteness cannot be
> dropped: for instance, take each S_n to be the natural numbers and
> each map to be addition of 1.
>
I'm not sure whether this counts as an explanation, but it's certainly a
wider context: the result is a special case of the fact that a
(cofiltered) inverse limit of locales and proper maps maps properly to
each of the vertices of the diagram. See C3.2.11 in the Elephant, and
also C1.1.12. (And note that the result fails for spaces: thus a key part
of the argument in the finite case is that the inverse limit in Loc is
a spatial locale.)

Peter Johnstone

Re: Limit of finite sets

[Michael Barr]

It is purely a property of compactness.  Take the product of compact
spaces.  The condition of an element of the product being in the limit is
the conjunction of infinitely many conditions each of which says that two
coordinates agree and if it is a chain (or, in fact, an inverse filtered
diagram) of non-empty compact sets, each of those finitely many conditions
defines a closed non-empty subset with the finite intersection property.

So the general context is that an inverse filtered limit of non-empty
compact Hausdorff spaces is non-empty.  Although I don't seem to have used
Hausdorffness, it is required to show those sets are closed.  And without
it, you could get the example Tom described using the trivial topology,
which is certainly compact.  I guess you could use the finite complement
topology to get a T1 counterexample.

Michael

On Fri, 30 Jul 2004, Tom Leinster wrote:

> I've recently come across the following curious little result.  I know
> how to prove it and have a use for it, but my question is: can anyone
> supply a wider context or explanation?
>
> The result is that the limit in Set of any diagram
>
>    ... ---> S_3 ---> S_2 ---> S_1
>
> of finite nonempty sets is nonempty.  Note that finiteness cannot be
> dropped: for instance, take each S_n to be the natural numbers and
> each map to be addition of 1.
>
> Thanks,
> Tom
>
>
>
>
>

Re: Limit of finite sets

[Peter Selinger]

This seems to me to be equivalent to Koenig's lemma: every infinite,
finitely branching tree has an infinite branch. The set of vertices is
the disjoint union of all the S_n, and there is an edge from (a,i) to
(b,i+1) if f_i(b)=a. Conversely, let S_n be the set of vertices at
depth n. -- Peter

Tom Leinster wrote:
>
> I've recently come across the following curious little result.  I know
> how to prove it and have a use for it, but my question is: can anyone
> supply a wider context or explanation?
>
> The result is that the limit in Set of any diagram
>
>    ... ---> S_3 ---> S_2 ---> S_1
>
> of finite nonempty sets is nonempty.  Note that finiteness cannot be
> dropped: for instance, take each S_n to be the natural numbers and
> each map to be addition of 1.
>
> Thanks,
> Tom
>
>
>
>
>
*mbx*
42cf5a8f00000000

Re: Limit of finite sets

[Michael Mislove]

Tom,
   The classical context I know is that in the category of compact
Hausdorff spaces and continuous maps, limits exist, and are non-empty
if each component space is non-empty. This uses the Axiom of Choice
(and the Tychonoff Theorem) to show that the product of the component
spaces $S_i$ is non-empty and compact. The generalization just embeds
Set in Top by regarding sets as discrete spaces, so all sets are
locally compact, and the compact sets are exactly the finite ones.
   The limit can be defined as the family
   $ L = \{ (s_i) \mid p_ji(s_j) = s_i, for i \leq j \in I\}. $
This limit is then the filtered intersection of the sets
   $T_F = \prod_{i \not\in F} S_i \times \{(s_i)_{i \in F} \mid
p_{ji}(s_j) = s_i, i \leq j \in F\},$
where $F\subseteq I$ is finite. The Axiom of Choice implies $F,
\prod_{i \not\in F} S_i$ is non-empty, and it's easy to show that
$\{(s_i)_{i \in F} \mid p_{ji}(s_j) = s_i, i \leq j \in F\}$ is
non-empty since $F$ is finite, so $T_F$ is non-empty. Since the bonding
maps $p_{ji} \colon S_j \to S_i$ are continuous, the set $T_F$ is
closed, so it's a non-empty closed subset of the compact Hausdorff
space $\prod_i S_i$. Since the family is filtered, its intersection is
non-empty.
   This generalization also suggests why the sets have to be finite -
limits of non-empty locally compact spaces and continuous maps can be
empty, because the limit object may be empty. Indeed, the same
construction as given above defines the limit object L, but L may be
empty because the filtered intersection of a family of closed,
non-empty subsets of a locally compact space may be empty.
   Best regards,
   Mike

On Jul 29, 2004, at 7:37 PM, Tom Leinster wrote:

> I've recently come across the following curious little result.  I know
> how to prove it and have a use for it, but my question is: can anyone
> supply a wider context or explanation?
>
> The result is that the limit in Set of any diagram
>
>    ... ---> S_3 ---> S_2 ---> S_1
>
> of finite nonempty sets is nonempty.  Note that finiteness cannot be
> dropped: for instance, take each S_n to be the natural numbers and
> each map to be addition of 1.
>
> Thanks,
> Tom
>
>