MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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. – Qiaochu Yuan Apr 29 '10 at 5:20
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... – Mariano Suárez-Alvarez Apr 29 '10 at 5:27
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. – Mariano Suárez-Alvarez Apr 29 '10 at 5:38
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. – Theo Johnson-Freyd Apr 29 '10 at 16:16
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! – Peter LeFanu Lumsdaine Apr 30 '10 at 1:10
up vote 9 down vote accepted

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

share|cite|improve this answer
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 ? – user2734 Apr 29 '10 at 6:36
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}$. – Reid Barton Apr 29 '10 at 6:49
Ah, of course. Thank you. – user2734 Apr 29 '10 at 6:50
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. – Dan Petersen Apr 29 '10 at 8:04
I haven't learned about limits and colimits in categories yet. Perhaps that will shed some light on the subject. – Matthew Willis Apr 29 '10 at 11:39

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

share|cite|improve this answer
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). – Qiaochu Yuan Apr 29 '10 at 5:51
Presumably, that example wouldn't be "convergent" in this "topology". – Steve D Apr 29 '10 at 6:02
@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). – Pete L. Clark Apr 29 '10 at 6:04
@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"). – Qfwfq Apr 29 '10 at 6:10
@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. – Matthew Willis Apr 29 '10 at 11:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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