Characterizing FinSet up to equivalence
Rosebrugh and Wood [Proc AMS 122(2), 409-413, 1994] characterized Set up to equivalence as the only category with a string of four adjoints to the left of its Yoneda embedding. A slew of questions about infinite sets being up for grabs, such as the number of infinite cardinals less than 2^N, it is clear that any such on-the-nose characterization must smuggle in much if not all of what it sets out to characterize. Finite sets do not raise these sorts of questions, removing the above argument for the inevitability of smuggling set-theoretic knowledge into a characterization of FinSet. Now some logicians such as Sol Feferman, and one imagines at least a few category theorists, view category theory as built on set theory. An alternative viewpoint is that the basic notions of category theory exist independently of the category of sets. Where one sits in this spectrum is presumably correlated with how strongly one feels that set theory has been smuggled into the following. For ignorance of the correct name I'll call an object b "strongly indecomposable" when Hom(b,-) preserves binary sums. "Successor object" seems like a reasonable name for an object of the form b+1 (1 the final object). Write FinC for the full subcategory of C whose objects have finitely many elements (morphisms from 1). Claim. Let C be a category with finite sums and final object 1. If 1 is a strongly indecomposable generator and every object is either initial or a successor, then FinC is equivalent to FinSet. (Set, FinSet, and Stone all meet these conditions on C, which could be weakened without changing the conclusion by replacing "finite sums" by "sums with 1" and "strongly indecomposable" (SI) by the requirement that b+1 have exactly one element not an element of b. Or, the dichotomy condition could be strengthened to "For all a,b there exists c such that either a ~ b+c or b ~ a+c.") Proof: Given b in FinC, use dichotomy to shed its n elements sequentially yielding b = 0+1+...+1. SI prevents loss or repetition of any element. For any c (in FinC or not), |0=>c| = 1 since 0 is initial, and by induction on n, |b=>c| >= |c|^n. But 1 generates so |b=>c| <= |c|^n. Pointers to previous appearances of this would be appreciated. Do other familiar categories besides finite sets have a similarly short and elementary characterization, e.g. finite Boolean algebras, finite Abelian groups, finite posets, finite monoids, etc? Finite Boolean algebras are easily characterized as dual finite sets. Specifically, for any category C with finite products and initial object 2, if 2 is a strongly coindecomposable cogenerator and every object is either final or of the form 2xb, then FinC is equivalent to FinBool. Bool, FinBool, and CABA all satisfy these conditions on C. ("2 strongly coindecomposable" means of course that Hom(-,2) sends finite products to finite sums; equivalently, every predicate q:axb->2 on axb factors through exactly one of the projections p1:axb->a, p2:axb->b, i.e. it acts as a predicate on one of a or b and is constant on the other.) Have we smuggled Boolean algebra into this argument? Is category theory based on set theory to any greater extent than on Boolean algebra? And is there any essential difference between this argument and its mate for FinSet? Sets and Boolean algebras would seem to deserve equal credit for their foundational role in both. My own view, first articulated in LICS'95, 444-454, is that mathematics is a catenary, the "Stone Gamut," held up at each end by the twin categories Set and CABA. The catenary is created from their interaction. Any suggestions for characterizing finite Abelian groups? Vaughan Pratt
Vaughan Pratt writes:
Now some logicians such as Sol Feferman, and one imagines at least a few category theorists, view category theory as built on set theory. ... Where one sits in this spectrum is presumably correlated with how strongly one feels that set theory has been smuggled into the following.
...
Claim. Let C be a category with finite sums and final object 1. If 1 is a strongly indecomposable generator and every object is either initial or a successor, ...
(Set, FinSet, and Stone all meet these conditions on C, ...
Set theory has been smuggled into the whole argument in an all-pervading way, and moreover in a specifically classical form. This causes problems when you start exploring more adventurously the nature of sethood. The argument about finiteness is then much less help than it might have appeared at first. As a particular example that category theory helps us to explore, we know there are benefits to be had from thinking of sheaves as sets (continuously parametrized by points of spaces, but the trick is to keep the parameter under wraps). They are benefits that do not depend on having recourse to some fixed classical notion of "actual" sets, unparametrized. There are important notions of finiteness for sheaves that require investigation. For instance, "Kuratowski finiteness" underlies the logically important notion of finitely bounded universal quantification. But the categories of sheaves do not in general get off the ground with Vaughan's results, since we do not have that every sheaf is either initial or a successor. Hence the results make little contribution to understanding finiteness for sheaves. Let me present another concrete set theory that, to my mind, provides foundations just as good as those of classical set theory. Buy a lorry load of ready-mixed concrete. Spread it evenly over your front drive. Wade into the middle of it and wait for it to set. Now if you want to explore beyond the margins of your front drive you will be safe, because you have a good solid bit of concrete to support you. Harsh? To bring the sheaves into classical set theory requires quite cumbersome machinery. We do better to find out what really makes the sheaves work rather than insistently reducing them to a notion of set that we know to be ill-matched. Only then can we, as the psalm puts it, "return with songs of joy, carrying sheaves with us". Steve Vickers.
Vaughan Pratt writes:
For ignorance of the correct name I'll call an object b "strongly indecomposable" when Hom(b,-) preserves binary sums.
I've heard this called "connected", which seems very nice, since that's what it amounts to in Top.
"Successor object" seems like a reasonable name for an object of the form b+1 (1 the final object). Write FinC for the full subcategory of C whose objects have finitely many elements (morphisms from 1).
Claim. Let C be a category with finite sums and final object 1. If 1 is a strongly indecomposable generator and every object is either initial or a successor, then FinC is equivalent to FinSet.
Since the concept of "finite set" is sitting right in the definition of FinC, we have to know all about finite sets to use this characterization of FinSet... but I wouldn't be surprised if that annoying circularity is inevitable. I wonder if anyone knows a reference to this characterization, which is simpler and perhaps more blatantly circular: Claim: FinSet is the free category with finite sums on one object. This is supposed to be a short way of saying that if C is a category with finite sums containing an object x, there is a finite-sum-preserving functor F: FinSet -> C, unique up to natural isomorphism, such that F(1) = x. It's a categorification of the fact that the natural numbers are the free commutative monoid on one generators. I think it's even true. I think this is also true: Claim: FinSet is the free biCartesian category on nothing. This is supposed to be a short way of saying that if C is a category with finite sums and finite products, the latter distributing over the former, then there is is a finite-sum-and- product-preserving functor F: FinSet -> C, unique up to natural isomorphism. It's a categorification of the fact that the natural numbers are the free commutative rig on no generators. Personally I find this sort of characterization a bit more illuminating than Vaughan's. Throughout math, as soon as you define some nice sort of gadget, you instantly focus on the free gadgets of this sort - which are probably the ones you knew about before you even made the definition! It's a circular business, but that's life. Best, John Baez
In response to John Baez and Steve Vickers, let me put my question more directly. What categories of "finite" (in any sense of finite you like) objects can be characterized up to equivalence as the finite objects (again feel free to define this notion yourself) common to all categories of some elementary class? I showed that finite sets and finite Boolean algebras could be so characterized. What about finite Abelian groups, or finitely presented (by generators and relators) Abelian groups, or finite dimensional vector spaces over some field? Once an appropriate notion of finiteness is settled on, these become straightforward yes-no questions. A related question is, what categories can be characterized up to equivalence by purely elementary means? I hope it's clear why I asked what I did and not this. (Loewenheim-Skolem and all that.) Like John Baez, I like free algebras and cofree coalgebras as methods of characterization. (Why else would Dusko Pavlovic and I bother to characterize the continuum as a cofree coalgebra?) I would immediately withdraw whatever I said that conveyed the opposite if I knew what it was. In asking about definability in a given framework (here first order logic plus cardinality restrictions) I had not intended to imply even endorsement of that framework, let alone rejection of other frameworks. In defense of sets, I very much like them as a foundational concept, in considerable part because one can reach a larger audience by starting from sets than from sheaves. I was impressed that anyone would dislike sets so much as to compare starting from them to standing in wet concrete until it sets (or were you just making a pun about sets, Steve?). Sheaves as a starting point is fine for category theorists, who are equipped to benefit from its greater generality, but they are singularly inappropriate for most other mathematical audiences, for most of whom experience with adding up the restaurant bill has made natural numbers much more familiar than sheaves. I'm not objecting to crash courses on sheaves here, just to talks for a general mathematical audience that start out "Ladies and gentlemen, let S be a sheaf." Mentioning categories on Steve Simpson's FOM mailing list typically brings on a diatribe from someone railing against categories. It would be nice if one could mention sets on this mailing list without the analogous response. John Baez makes exactly the right connection between sets and the free monoid on one generator (Peter Selinger made a related remark to me privately about the free cocomplete category on one generator satisfying FinC ~ FinSet). The categorification of the semiring of natural numbers yielding the distributive category of sets is natural, simple, beautiful, and easily understood. However I disagree that the assumption of finiteness constitutes smuggling in FinSet. A tiny part of it, fine, but that's a long way from smuggling in the whole notion of function. The notion of linear order with endpoints can be characterized elementarily up to isomorphism if one restricts attention to countable linear orders, but how much of the notion of linear order does countability smuggle in here? Cardinality restrictions as an axiomatization strategy convey no substantial structural information, and are one of the mildest possible excursions outside first order logic when such is unavoidable. They have a long and distinguished history in logic. Vaughan Pratt
Vaughan Pratt wrote in part:
However I disagree that the assumption of finiteness constitutes smuggling in FinSet. A tiny part of it, fine, but that's a long way from smuggling in the whole notion of function.
Indeed, so long as category theory begins with <Let Ob(C) be a set.>, then some set theory can't help but be smuggled in. If you say <FinSet is the free finitely complete category on 1 object.>, then you're asking Mor(D) to be a finite set (where D is the diagram in a limit being considered), but you already have to ask Mor(D) to be a set, so this doesn't smuggle in any more set theory than was already there. -- Toby Bartels toby@math.ucr.edu
baez@math.ucr.edu wrote:
Claim: FinSet is the free category with finite sums on one object.
I wonder what happens in the case of more than one generator. For instance, the free category with finite sums on two objects is FinSet x FinSet. In the case where the set of generators is discrete, it does not make a difference if one also adds coequalizers, e.g. FinSet is the free category with finite colimits on one object. What about the case where one has morphisms on the generators? From [Mac Lane], we know: If D is any diagram (small category), then its free co-completion is the Yoneda category Set^{D^op}. Is this still true when inserting the word "finite"? If D is any diagram, then its free completion under finite colimits is FinSet^{D^op}? And what happens if one drops the coequalizers? Does the free completion of a diagram D under coproducts have a Yoneda-like characterization? -- Peter
Peter, These are pretty wild questions!!! :-) I am presuming you know that FSet^Dop is not the finite cocompletion as in general D does not embedd in this!! If D is a finite category you are home and dry of course. But this is just the same thing as assuming that the universe is finite sets. The free completion with respect to coproducts is the "Fam" construction. I took a look at this in my "Introduction to distributive categories" MSCS 1991 (see towards the end): Steve Schanuel has recently been revisiting this (at the Union meeting). -robin On 24 Nov, Peter Selinger wrote:
baez@math.ucr.edu wrote:
Claim: FinSet is the free category with finite sums on one object.
I wonder what happens in the case of more than one generator. For instance, the free category with finite sums on two objects is FinSet x FinSet. In the case where the set of generators is discrete, it does not make a difference if one also adds coequalizers, e.g.
FinSet is the free category with finite colimits on one object.
What about the case where one has morphisms on the generators? From [Mac Lane], we know:
If D is any diagram (small category), then its free co-completion is the Yoneda category Set^{D^op}.
Is this still true when inserting the word "finite"?
If D is any diagram, then its free completion under finite colimits is FinSet^{D^op}?
And what happens if one drops the coequalizers? Does the free completion of a diagram D under coproducts have a Yoneda-like characterization?
-- Peter
John Baez wrote in part:
Claim: FinSet is the free biCartesian category on nothing.
What is the justification for including in the term "biCartesian" that the products distribute over the coproducts? If you add that the Cartesian product is closed (which it is in FinSet), *then* you get this, of course. So FinSet is either the free biCartesian category where products distribute over coproducts on nothing, or else the free Cartesian closed coCartesian category on nothing. It would be nice to have a single term like "biCartesian" for either of these concepts, but I don't see the justification, especially since the concept isn't very symmetric. -- Toby toby@math.ucr.edu
In defense of sets, I very much like them as a foundational concept, in considerable part because one can reach a larger audience by starting from sets than from sheaves. I was impressed that anyone would dislike sets so much as to compare starting from them to standing in wet concrete until it sets (or were you just making a pun about sets, Steve?).
No, I was in earnest. Having over quite a few years now seen for myself the possibilities of using constructive reasoning to _simplify_ mathematics, so that it now seems very obvious, I get overquickly distressed when other people still haven't seen it. However, I should explain that I was not criticizing sets as pedagogic foundations, where you start from when you're explaining to a large audience, nor as (if I may use Paul Taylor's phrase) practical foundations, since the naive concepts of sets (albeit non-classical ones) underly the way one reasons in toposes. The parable about concrete concerned philosophical foundations, trying to fix on classical set theory as the deep unifying account of what mathematics depends on. Maybe in any case Vaughan wasn't thinking so much about such philosophical diversions. There is a pragmatic message. There are a number of different characterizations of finiteness. Classically they are all equivalent, but it has been known to topos theorists for quite a while now that if you start considering non-classical sets (such as sheaves) or computational structures you find they are inequivalent. My belief is that the explanations of the differences can be understood in naive set theoretic terms, though to see why they are genuine differences and not just presentational you need to know a bit more about sheaves and such. A particular message (really arising out of geometric logic) is that finiteness is _structure_ on a set, and not just a property: How do you know a set is finite? There is something there in its structure that tells you. I've tried to bring this out in my paper "Strongly algebraic = SFP (topically)", soon to appear in Math. Structures in Computer Science, and also available through my web page http://mcs.open.ac.uk/sjv22. In particular you see there discussed Kuratowski finiteness (you can list of all the elements but can't necessarily remove duplicates), finite decidable (in addition you can detect inequality between elements and so can remove duplicates) and finite ordinals (there is a canonical list that thereby puts an ordering on the elements). Consequently, when giving (as Vaughan did) a categorical characterization of finiteness, it's worth pausing to consider which kind of finiteness you are characterizing. Some will be more fruitful than others in terms of how successfully they can generalize to the non-classical sets - with some you will be stuck in your concrete, with others you can explore further afield. The particular one Vaughan described was closely tied to the classical set theory, but that is a limitation that is not inherent in the broad questions he was asking. That's a bit more subtle than saying "finite sets" are now characterized, and treating "finite sheaves" as an interesting topic of further study along with "finite Abelian groups" and so on. There is virtue in finding answers for "finite sets" that also apply to "finite sheaves".
Mentioning categories on Steve Simpson's FOM mailing list typically brings on a diatribe from someone railing against categories. It would be nice if one could mention sets on this mailing list without the analogous response.
Sorry if I railed. The categories list has the big advantage that its readership is very well informed about both sets and categories, and fully in a position to base their opinions on the mathematics and not the railing. All the best, Steve Vickers.
Hello, what kind of characterization do you want? If you accept ZFC as "outside world", then there is no elementary characterization of FinSet (in the sense of finitary first-order logic) because every ultrapower of FinSet satisfies the same (finitary) first-order sentences. Greetings Reinhard
participants (8)
-
baez＠math.ucr.edu -
Boerger -
Peter Selinger -
Robin Cockett -
S Vickers -
S.J.Vickers＠open.ac.uk
-
Toby Bartels -
Vaughan Pratt