4
$\begingroup$

For example, deciding whether or not the following is a category seems to depend on the above question (from Awodey's Category Theory, pg. 6):

"What if we take sets as objects and as arrows, those $f : A \rightarrow B$ such that for all $b \in B$, the subset $f$-1$(b) \subseteq A$ is finite?"

Define for each $n \in N$ the function $f$n: $N \rightarrow N$ where $f$n$(x) = max(0, x - n)$.

Then any $f$n or any finite composition thereof has finite inverse images. Yet the "infinite composition" $... f$1$f$2$f$0 has an infinite inverse image for 0, and so the above does not meet the definition of a category.

If this "infinite composition" is legit, does it follow from the basic definition of a category, or must the definition be made more flexible or precise to accommodate it?

For reference, this is Awodey's definition concerning composition:

"Given arrows $f : A \rightarrow B$ and $g : B \rightarrow C$, [...] there is given an arrow: $g$ o $f : A \rightarrow C$ called the composite of $f$ and $g$."

Thank you for your insight.

$\endgroup$
8
  • 6
    $\begingroup$ Infinite composition can't possibly be well-defined in general; consider the case where f : A to B, g : B to A, and you want to define ...fgfg. Presumably one needs some additional structure on the domains and codomains involved. $\endgroup$ Apr 29, 2010 at 5:20
  • 1
    $\begingroup$ In the usual definition of categories, infinite compositions make no sense. So, in fact, infinite compositions do not follow from the usual definition. Now, «must the definition be made more flexible?» I would say that that is a rather unanswerable question... $\endgroup$ Apr 29, 2010 at 5:27
  • 3
    $\begingroup$ On the other hand, you could ask for ways to modify the usual definition of categories so as to be able to attach some sense to (some, at least) infinite compositions, as that is a question which has answers. One straightforward way is to consider categories whose End-sets are topological spaces (for example, categories enriched over topological spaces), where you can make sense of what the limit of a sequence of endomorphisms of a fixed object is. $\endgroup$ Apr 29, 2010 at 5:38
  • 2
    $\begingroup$ Essentially a follow-up on Qiaochu's comment: remember that by Mazur's swindle 0 = 1-1+1-... = 1, it is impossible to have all three of (a) countable compositions, (b) arbitrary associativity, and (c) inverses. $\endgroup$ Apr 29, 2010 at 16:16
  • 1
    $\begingroup$ While it's certainly interesting to ask when infinite composition is meaningful, I think it's important to point out that "deciding whether or not something is a category" doesn't depend on it at all! The definition of a category (as usually given, and in Awodey's book) asks for identities and binary composition, end of story; so if something's got those, satisfying the appropriate axioms, then it's a category. We can then go looking to see if there are some kind infinite composites too, but we don't need to worry about that in checking if something's a category! $\endgroup$ Apr 30, 2010 at 1:10

2 Answers 2

11
$\begingroup$

This is probably not what the OP is looking for, but there is a notion of "infinite composition of arrows" which often appears for example in categorical homotopy theory:

If $f_0 : X_0 \to X_1$, $f_1 : X_1 \to X_2$, $\ldots$ are morphisms in a category $C$ and the colimit of the diagram $X_0 \to X_1 \to X_2 \to \cdots$ exists (call it $X$) then $X$ is equipped in particular with a canonical map $X_0 \to X$ which is called the transfinite composition of the maps $f_i$. Of course, technically this morphism of $C$ is specified only up to canonical isomorphism because $X$ may be replaced by a (uniquely isomorphic) different colimit of the $X_i$. More generally given an ordinal $\alpha$ which we may view as a category (poset) and a colimit-preserving functor $X_\cdot : \alpha \to C$ (so that for each limit ordinal $\beta \in \alpha$, we have $X_\beta = \operatorname{colim}_{\gamma < \beta} X_\gamma$), we may form the transfinite composition $X_0 \to \operatorname{colim}_\alpha X_\alpha$. One is often concerned with questions such as whether a given class of maps is closed under transfinite compositions (for example, the class of cofibrations in a model category has this property).

$\endgroup$
6
  • $\begingroup$ I apologize for the silly question, but in your first example of a colimit of a functor $\omega\to C$, is the transfinite composition just the 0-th arrow of the colimiting cone? Does this specialize in some sense to the usual composition if $\omega$ is replaced by some finite $n$? And if not, why is it called transfinite composition ? $\endgroup$
    – user2734
    Apr 29, 2010 at 6:36
  • 2
    $\begingroup$ Yes. If $\alpha = n$ is a finite ordinal, then for the colimit we may take the last object $X_{n-1}$ and the structural map of the colimit cone is the composition of the maps $X_0 \to X_1 \to \cdots \to X_{n-1}$. $\endgroup$ Apr 29, 2010 at 6:49
  • 1
    $\begingroup$ I've never heard the term transfinite composition, but it seems to be another word for the perfectly ordinary direct/inverse limit, right? If so, it certainly shows up absolutely everywhere in algebra, not just in categorical homotopy theory... consider the p-adic numbers or taking stalks of sheaves. $\endgroup$ Apr 29, 2010 at 8:04
  • $\begingroup$ I haven't learned about limits and colimits in categories yet. Perhaps that will shed some light on the subject. $\endgroup$
    – Matthew
    Apr 29, 2010 at 11:39
  • $\begingroup$ But Dan, the definition only refers to one single arrow out of a whole colimiting cone. Also, only some special index categories (ordinals as pre-orders) are considered. So, I think that it is not possible to say that it is the same thing as a colimit. $\endgroup$
    – user2734
    Apr 29, 2010 at 12:06
4
$\begingroup$

(This was slightly too long to fit as a comment.)

As with Qiaochu's and Mariano's comments above, the answer as to whether infinite compositions are a priori meaningful in a category is simply no.

I don't know what it would mean to make this definition more precise -- it seems already, like any acceptable definition, to be completely precise. Moreover, in order to entertain a notion of infinite composition, it seems that one rather needs a less flexible -- i.e., more restrictive -- definition of composition of morphisms in a category. Since as Qiaochu points out, already infinite composition is not always meaningful in the category of sets and functions, such a definition would have to be very restrictive indeed.

It does not seem completely unreasonable to define some sort of category-like structure in which infinite composition is meaningful. Off the top of my head, it seems that some kind of "topology" on the class of objects of the category would be helpful, so that we could speak of a convergent sequence of objects. But it would be much more interesting and fruitful to do this in the context of some particular instance in which one would like to formalize infinite composition, e.g. for certain elements of the symmetric group on an infinite set.

$\endgroup$
5
  • $\begingroup$ The example I gave is problematic in any category; the infinite composition ...fgfg doesn't have a well-defined codomain (maybe I should say target). $\endgroup$ Apr 29, 2010 at 5:51
  • $\begingroup$ Presumably, that example wouldn't be "convergent" in this "topology". $\endgroup$
    – Steve D
    Apr 29, 2010 at 6:02
  • $\begingroup$ @Qiaochu: It's okay -- or rather not problematic for the reason you give -- in any category with a single object (i.e., a monoid). Seriously, that's a reasonable special case. But I certainly do take your point: we need to either very much restrict the categories in question, or cook up some extra structure that keeps track of convergence of objects (or do something else equally drastic). $\endgroup$ Apr 29, 2010 at 6:04
  • $\begingroup$ @Qiaochu: this problem of the target being not always well defined could perhaps be solved by requiring the infinite set of arrows one wants to "compose" to be linearly ordered (w.r.t. "source precedes target" order, let's say) and having a minimum (the source of the "infinite composite") and a maximum (the target of the "infinite composite"). $\endgroup$
    – Qfwfq
    Apr 29, 2010 at 6:10
  • $\begingroup$ @Pete: This makes the question even more striking in my view. For example, let's say we have the monoid {0,1} with operation xor and try to count its arrows. Should it have two arrows corresponding to the two elements of the monoid? What about the infinite composition ..0101.. (or the source-target-friendly 1..0101..0), which is neither equal to 0 nor to 1? I think this is the essence of my original question. $\endgroup$
    – Matthew
    Apr 29, 2010 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.