You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Julius Hamilton (Mar 29 2024 at 22:41):If U is a Grothendieck universe such that Set is the category of all U-small sets, then you can define
Cat to be the 2-category of all U′-small categories, where U′ is some Grothendieck universe containing
U. That way, you have Set∈Cat without contradiction. By the axiom of choice, the two definitions of Cat as a 2-category are equivalent.
A Grothendieck universe is a transitive set with power sets and the union of the image of any function (Is this the axiom of replacement? Why do we need it, in general?)
If U is a Grothendieck universe, then it is easy to show that U is itself a model of ZFC (minus the axiom of infinity unless you modify (3) to rule out countable universes). (1) Therefore, one cannot prove in ZFC the existence of a Grothendieck universe containing ℕ, and so we need extra set-theoretic axioms to ensure that uncountable universes exist. Grothendieck’s original proposal was to add the following axiom of universes to the usual axioms of set theory: For every set s, there exists a universe U that contains s, i.e., s ∈ U.
Why (1)? You can prove U is a model of ZFC minus infinity. Does that mean Grothendieck universes would always be finite until you added the axiom of universes?
I wanted to know if the category of all small categories is countable. I think it would be really cool to assign a numerical index to all categories, to be able to say, “the category of lattices is category 12,367”. If Cat is not countable, why?
Julius Hamilton (Mar 29 2024 at 22:47):I was reading how people initially suggested the existence of only one additional “super-container”, the “class” of all sets (to avoid Russell’s paradox). Then people considered hierarchies of such “super-containers” (under various names). Grothendieck was able to abstract this where in fact the container of a given collection of sets is still a set, yet, you can express this idea that there is always a “higher container” with the axiom of universes.
It seems like a solution. But, does it have the exact same problem? In general, it seems that there can never be any largest set. But if you define a new concept which is conceptually “one level up”, then don’t we have to ask ourselves about “the universe of all universes”? Or is there some reason why the axioms escape that question?
Brendan Murphy (Mar 29 2024 at 23:23):(1) isn't about finite universes but the universe of all (hereditarily) finite sets. That is, the collection of all sets which are finite, whose elements are themselves finite, whose elements' elements are finite and so on forms a set and is a Grothendieck universe (furthermore it is countable).
The category of all small categories relative to this universe will be countable. Up to equivalence we can think of it as the category of all finite categories. But Cat itself won't be countable for any other universe (any universe containing ω). This is because Set (meaning the category of sets in that universe) embeds into it: any small set defines a "discrete" category with only identity morphisms. And if N is small then so are all of its subsets, so Set (and thus Cat) has to have cardinality at least 2^|N|.
There is no universe of all universes, but for each universe there is a larger one containing it. I would say grothendieck universes do have the same problem as ZFC, in that we can't collect all universes into a universe simultaneously, the problem just occurs "higher up the chain". This isn't a contradiction, it's simply that there is no such universe (like how there's no largest set). What we can do is bound any set of universes by another universe (eg any countably family of them) and this is good enough most of the time
Brendan Murphy (Mar 29 2024 at 23:23):Also, I don't know where the quotes you posted are from so I'm worried I'm missing some context
Julius Hamilton (Mar 29 2024 at 23:29):Here you go https://ncatlab.org/nlab/show/Grothendieck+universe
Julius Hamilton (Mar 29 2024 at 23:43):Brendan Murphy said:
(1) isn't about finite universes but the universe of all (hereditarily) finite sets. That is, the collection of all sets which are finite, whose elements are themselves finite, whose elements' elements are finite and so on forms a set and is a Grothendieck universe (furthermore it is countable).
The category of all small categories relative to this universe will be countable. Up to equivalence we can think of it as the category of all finite categories. But Cat itself won't be countable for any other universe (any universe containing ω). This is because Set (meaning the category of sets in that universe) embeds into it: any small set defines a "discrete" category with only identity morphisms. And if N is small then so are all of its subsets, so Set (and thus Cat) has to have cardinality at least 2^|N|.
There is no universe of all universes, but for each universe there is a larger one containing it. I would say grothendieck universes do have the same problem as ZFC, in that we can't collect all universes into a universe simultaneously, the problem just occurs "higher up the chain". This isn't a contradiction, it's simply that there is no such universe (like how there's no largest set). What we can do is bound any set of universes by another universe (eg any countably family of them) and this is good enough most of the time
Alright. It’ll take me a while to digest that. But I think I’ll undertake a study of finite categories to see some details clearer.
Evan Washington (Mar 30 2024 at 01:00):re: (1). as stated on the nLab, a Grothendieck universe is a transitive model of ZFC - Infinity (that's essentially all the conditions are saying). what's happening here is that ZFC proves there is a model of ZFC - Infinity (i.e. that ZFC - Infinity is consistent). this means ZFC can prove that there is a Grothendieck universe (in the nLab's sense). this is different from (ZFC - Infinity) + ¬Infinity, but ZFC can also prove that a model of those axioms exist (the HF sets, as Brendan points out). so I think a confusion here might be just noticing that difference: ZFC - Infinity is different from ZFC - Infinity plus the negation of Infinity (like how ZF is different from ZF + ¬Choice).
ZFC cannot prove there is a Grothendieck universe satisfying Infinity, because that's equivalent to proving that ZFC is consistent, which cannot be by Gödel's incompleteness theorem. but we can prove that if a Grothendieck universe satisfying Infinity exists, it's a model of ZFC; that's straightforward and does not require the axiom of universes.
the idea about "super-containers" is connected to the notion of indefinite extensibility and there's no escape from it here. remember that universes are sets. the axiom of universes says that every set (including universes) is contained in some universe, but that's not to say that some universe contains every set. (and there's no universe of all universes, because universes are transitive sets, so a universe of all universes would also be a set of all sets.)
Julius Hamilton (Mar 30 2024 at 01:10):Awesome thank you so much that article is perfect. I’ll strive to understand more of your post soon.
Mike Shulman (Mar 30 2024 at 03:11):Evan Washington said:
re: (1). as stated on the nLab, a Grothendieck universe is a transitive model of ZFC - Infinity (that's essentially all the conditions are saying).... ZFC cannot prove there is a Grothendieck universe satisfying Infinity, because that's equivalent to proving that ZFC is consistent
This is a very common misconception that turns on some technical details of set theory. In fact, having a Grothendieck universe is much stronger than having a transitive model of ZFC or knowing that ZFC is consistent. A Grothendieck universe satifies the "second-order replacement axiom" that every function , with , has an image in , whereas a model of ZFC only needs to satisfy the "first-order replacement axiom schema" which asserts this only when is definable by a logical formula. In fact one can prove that if there is a Grothendieck universe of cardinality , then there are -many transitive models of ZFC contained in !
Brendan Murphy (Mar 30 2024 at 04:17):Just to elaborate on the difference between first and second order replacement: if we assume ZFC has a countable transitive model M (this is implied by ZFC having any transitive model whatsoever by downward LS) then ω^M is the external ω while the powerset P(ω)^M cannot be the external powerset P(ω), because P(ω)^M is externally countable (as a subset of the countable set M). But we do have that P(ω)^M is a subset of P(ω). So there must be a set of natural numbers X (in fact, continuum many) which is undefinable in the model. Note X is not finite and so externally there exists a bijection ω -> X. Composing with the inclusion we get a function ω -> M which is necessarily not definable, because if it was then its image X would be an element of M. This kind of thing is ruled out by a grothendieck universe. It's extremely important if we want to pass back and forth between grothendieck universes that "the small powerset of a small set is its actual powerset", and this is not captured by just a transitive model of ZFC
Mike Shulman (Mar 30 2024 at 04:22):However, I believe that a Grothendieck universe of cardinality (i.e. an inaccessible cardinal ) even contains -many "natural models", i.e. transitive models that are a level of the von Neumann hierarchy, hence in which powersets do coincide with "real" powersets.
Brendan Murphy (Mar 30 2024 at 04:27):Huh, that's very interesting. I had no idea
Brendan Murphy (Mar 30 2024 at 04:28):I thought you could conclude 2nd order replacement from this but clearly not
Mike Shulman (Mar 30 2024 at 04:33):I learned this from the paper "Natural models of set theories" by Montague and Vaught. But I'm not an expert on ZFC and the paper is rather old, so it's conceivable I misinterpreted it.