Hacker News Reader

Comment by i_k_k | Hacker News Reader

I never understood this either...

Category theory works with collections, which can be modeled as sets -- or if you want to deal with categories of sets and other "large" categories -- as proper classes. And you can use a set theory that incorporates classes, like Morse-Kelley, to model this. IOW, it seems like category theory can be modeled in set theory.

On the other hand, I've not seen a rigorous set of axioms for category theory that didn't presuppose a notion of set or category or "collection".

Set theory also sheds a lot of light on what feel like foundational issues: sizes of sets, independence of axioms, etc.; I haven't seen something similar out of category theory.

Love for a category theory partisan to chime in with more here -- I'm definitely not an expert.

View on HN

> On the other hand, I've not seen a rigorous set of axioms for category theory that didn't presuppose a notion of set or category or "collection".

I'm no expert, but I do want to point out that you'll never see a set of axioms for set theory that doesn't also presuppose some realm from which sets themselves are drawn. The question is not whether sets exist; it's whether the collection of them can be represented within the theory. It is well-known (in certain circles...) that the realm of all sets cannot itself be described by a set.

In the same way, category theory may assume the existence of collections of objects and arrows, but these collections are not themselves represented within category theory. The category of all categories encounters exactly the same size issues as does the set of all sets.

There are different ways around these size issues. I think a lot of people go with something like Russell's stratified hierarchy of universes -- but this is also done in set theory, like with the alternative to ZFC based on sets and classes. (But what is the class of all classes!? You just keep building bigger universes.)

> I'm no expert, but I do want to point out that you'll never see a set of axioms for set theory that doesn't also presuppose some realm from which sets themselves are drawn.

Huh? Of course you do; ZFC itself is such a set of axioms. There's no particular requirement on objects that can be members of sets (at least, nothing really goes wrong if they're not all sets), so the theory doesn't depend on anything else, in a very intuitive sense.

To get a little bit technical, the axioms of ZFC, as a "first-order theory", make use of universal and existential quantifiers. These quantifiers have to quantify over some universe, whose constituents we call "sets". Take the axiom of the empty set as an example:

    exists x. forall y. y not in x

The meaning of the "exists" quantifier is that it runs over the universe of entities; the formula it quantifies over must be true when instantiated on at least one such entity. The meaning of the "forall" quantifier is similar, except it must be true for every such instantiation. Notably, since the universe of all sets is not a set on pain of paradox, the universe itself cannot be a set. It is a primitive "sort", part of the logical signature of the theory.

These quantifiers only "work" when there's a universe of entities to run over. This universe is not internal to set theory as an axiomatic system; the whole point of "non-standard models" is that we're looking for universes where the axioms of set theory hold, and yet are not what we normally think of when we reason using those axioms (e.g. "large cardinal" models).

Category theory can also be framed as a first-order theory. In its most common incarnation, it's a two-sorted first-order theory, with separate universes for objects and for arrows. This isn't essential; we can actually dispense with objects and work only with arrows. (Objects are then encoded as their identity arrows.) But it's a first-order theory either way; all the axioms of a category can be given with quantified formulas.

Group theory is also a first-order theory. When you specify a particular group, you give the universe over which its axioms quantify, and then prove(!) that those axioms hold on that universe. If you interpret group theory internal to set theory, then your universe will be a set; but the axioms don't care as long as quantification can be interpreted appropriately.

The idea that you can do category theory over any kind of thing as an arrow may be true as a matter of formal mathematical logic, but it's very much not intuitive in the way that it is for sets. If we wanted to work with tables, chairs, and beer mugs, it's very natural and easy to think about forming sets of beer mugs - a beer mug might either be a member of a set, or not, and this doesn't seem to require anything of it. For a group you need a binary operation and inverses, so this feels a bit more complex and abstract than a set (indeed the way I was taught, a group is a set plus some additional structure), but it's still fairly direct and understandable what kind of things satisfy the group axioms (if I had some rule for merging two beer mugs, and some kind of inverse - obviously this is unphysical, but it's at least imagineable). Whereas for a category it's just impossible to get started - should my beer mugs be objects or arrows? Presumably objects (since beer mugs are objects in the conventional sense), but then what are the arrows?

What kind of relationships between beer mugs are you interested in? "can contain more beer than"? "is both at least as deep and at least as wide"?

What about beer mugs are you trying to model?

I'm not trying to model anything about beer mugs. I'm trying to construct some nontrivial, intuitively understandable categories to play around with.

I like to take example categories from order theory, like with lattices and preorders and such. All such orders are also categories; the objects are the elements of the order, and the arrows are the relationships. However, if x <= y in the order, then there's only one arrow x -> y -- the order doesn't distinguish the different ways two objects can be related, only the mere fact that they are. (This is the difference between an order and a category: categories do allow us to distinguish the multiple ways two things can be related.)

Lots of category theory has direct analogues in order theory. Functors are monotone functions, for instance; monads are closure operators; and presheafs are lower sets. But since there's at most one arrow between any two objects, you don't have to worry about all the coherence conditions you end up seeing in category theory. Their whole purpose is to make sure that you pick "the right" arrow in various circumstances; but when there's only one arrow, it is trivially the right one.

I think this is an interesting topic worth discussing, but also I don't think it's related to your post I replied to, which claimed that ZFC doesn't presuppose any more primitive kind of collection.

> sets of beer mugs

Set theory doesn't admit anything other than sets. Based on the way you're describing things, you'll need to encode each mug as a set, just as we encode numbers themselves as sets. But that's rather unnatural, and mathematicians generally go about their business without worrying about such encodings. They work with the axioms of their setting instead, comforted merely that they could find a model of their constructions in set theory if they really cared to carry out the encodings required.

Confusingly, the "group" and "set" in "group theory" and "set theory" are referring to different parts of the theory. Group theory posits a universe with entities called elements, which when used in certain ways do nice things. Set theory posits a universe with entities called sets, which when used in certain ways do nice things. In one, a "group" is the universe; in the other, a "set" is a constituent of the universe.

If you wanted your mugs to be a model of set theory, the same way we say that something is a group (is a model of group theory), you'd need to somehow prove that your collection of mugs satisfies the ZFC axioms. I don't think "is this mug an element of that mug" is the kind of question you're hoping to model, so your mugs are probably not a model of set theory.

Your mugs might be a model of the theory of preorders, if you deign to order them by their fluid capacity.

> Whereas for a category it's just impossible to get started - should my beer mugs be objects or arrows?

It sounds like what you want is some kind of "mug theory", and the sibling comment has it right in asking what you want to model about mugs. The common thread with all of these theories is that you state first-order axioms, and then work with those axioms freely ignorant of whatever choice of model somebody might come along with that satisfies those axioms.

This is really no different than what we do in something like Java. We define interfaces (theories) capturing the things we want to be able to do with objects, and worry later about what implementations (models) actually meet the requirements. If you want to work with mugs in Java, what are you going to do but define a new type with the operations you need?

There's no reason to expect that some other interface is going to just happen to meet your needs. Not even set theory; not even category theory.

Well, I guess what I'm technically doing is building a non-standard model of set theory in which my beer mugs are some kind of inaccessible sets that are not members of each other. And yes, that doesn't let me study the mugs themselves in any useful way, since I'm not interested in which mugs are members of which other mugs - but it does let me play around with sets of beer mugs and get comfortable with set theory. And it makes it feel like a simple theory if the entities it studies are just opaque "things".

> Presumably objects (since beer mugs are objects in the conventional sense), but then what are the arrows?

This is definitely one of the most unintuitive parts of early category theory. The "objects" are not automatically the things you're studying; often they're best modeled as the arrows. It took me a really long time to internalize that.

Put it this way: the arrows are the actually interesting things, from a categorical perspective. The objects literally only exist to tell you which arrows you can fit together. The objects don't contain any other information. We often say that sets are objects, or topological spaces are objects, but that's only because we're studying functions or homeomorphisms, and if we want to chain those together, we need to make sure that one ends where the other begins or else the composition isn't well-defined.

No, we don't expect everything to be modeled directly as a category. That's not how the abstraction pays for itself.

> The meaning of the "exists" quantifier is that it runs over the universe of entities; the formula it quantifies over must be true when instantiated on at least one such entity.

This much is true when we start assigning semantics to formulas - which is what leads to model theory, where you assume that a mathematical universe already exists and you're trying to figure out which sets of formulas describe which parts of it (to oversimplify).

If you look at the ZFC axioms purely syntactically, there aren't many presuppositions. Essentially we only posit that we should be able to coherently reason about finite sequences of strings - because a first-order proof is nothing more than that. That seems easy enough to believe. And it's what allows us to write proofs with computers.

> On the other hand, I've not seen a rigorous set of axioms for category theory that didn't presuppose a notion of set or category or "collection".

I never worked through the details, and I'm not a category theory partisan, but I think that's what this is: https://ncatlab.org/nlab/show/fully%20formal%20ETCS

Yes, this is essentially what I'm getting at in my cousin comment -- although the nlab is typically rather impenetrable to non-specialists.

Reply on news.ycombinator.com