Equivalence classes of proper classes

[disregardthat]

Suppose we have a class equivalence relation ~ on a proper class C. Can we form the class of equivalence classes C/~? What axioms do we need, assuming we base ourself on NBG?

I can't seem to prove that this class exists with the axioms stated. I.e., the proposition that there exists a class D, and a surjective class function F : C -> D such that x ~ y if and only if F(x) = F(y).

Axiom of global choice doesn't work here either. A single equivalence class may be a proper class, and since this axiom only applies to the class of sets (and not a "collection" of classes), we may not pick out a single representative this way.

Formally the equivalence relation is a subclass of the cartesian product CxC satisfying the necessary conditions. The cartesian product exists by the axiom of pairing, and the axiom of unrestricted comprehension.Take a look at the wikipedia entry for quotient categories. The way it is worded, it seems to imply that the quotient category may always be constructed given a categorical equivalence relation on a category.

Consider the category consisting of a single object X, with morphisms being simply the class of sets. Composition is defined as union (clearly associative). The identity morphism is the empty-set. Define an equivalence relation on hom(X,X) by x ~ y if x and y are in bijection. This clearly defines a congruence relation as described in the link. However, the quotient category would be the category of a single object, with morphisms corresponding to cardinal numbers. As a category, the morphisms should form a class. However, assuming that quotient categories always exists, this seems to imply that we have constructed the class of cardinal numbers.

So how is this this construction defined?

Clearly, if the category is locally small this may be done using the global choice function. The trouble appears when dealing with not locally small categories.

 

[micromass]

This does not directly answer your question, but NBG or ZFC are really uncomfortable system for doing category theory. The free book "The Joy of Cats" outlines in his introductory Foundations chapter a set theory more suitable for category theory: http://katmat.math.uni-bremen.de/acc/acc.pdf Be sure also to check out the references in that chapter.

Now, if you ask how you should extend ZFC or NBG to give a suitable set theory for category theory, then the answer is that you should have an axiom which gives you the existence of an inaccessible cardinal $\kappa$.

So let us take a ZFC-universe which contains an inaccessible cardinal. We will call the elements of this universe a conglomerate (instead of a set).

By transfinite induction, we can then build the Von Neumann universe:
$$V_0 = \emptyset,~V_{\alpha+1} = \mathcal{P}(V_\alpha),~V_\alpha= \bigcup_{\beta<\alpha}V_\beta~\text{if}~\alpha~\text{is a limitordinal}$$

Then all elements $V_\kappa$ should be called sets. All subsets of $V_\kappa$ should then be called classes. All other things are just conglomerates. It is now perfectly possible to take an equivalence relation on a class $C$ and to find the quotient $C/\sim$. This will however be only a conglomerate. The axiom of choice which holds for all conglomerates is now perfectly applicable to $C/\sim$.

 

[disregardthat]

I've seen this kind of approach, but it doesn't sit all very well with me. But it might be I don't understand it very well. Is the idea here, that when dealing with categories, we say that the category of sets is not really the proper class of all sets, but rather all elements of this set V_k? Thus we are working in the axiomatic system of ZFC+the existence of an inaccesible cardinal, in which categories as defined are not proper classes (which doesn't make sense here, as everything is sets) but actually sets?

Or is the idea that V_k provides us with a model for ZFC, so while our axioms are the axioms of ZFC, we are actually working at two levels: in a predefined universe V_k defined in a larger axiomatic system, with the axioms of ZFC? This last part is what I don't really get. In a way we are using set theory to provide us with a model for set theory.

I can get on with the first part, it does make sense. I've just started reading "categories for the working mathematician", and the author does not really explain how 1) we know that the universe set exists, and 2) we can still talk about proper classes and categories being larger than the universe set, such as the category of ALL sets. In your view, does the category of ALL sets really have any meaning at all(that is, assuming ZFC+inaccessible cardinal)? If not, will we not be missing something here?

I will take a look at your link, to see if it is explained perhaps better there than in the book I'm currently reading.

 

[Erland]

Suppose we have a class equivalence relation ~ on a proper class C. Can we form the class of equivalence classes C/~? What axioms do we need, assuming we base ourself on NBG?

I can't seem to prove that this class exists with the axioms stated. I.e., the proposition that there exists a class D, and a surjective class function F : C -> D such that x ~ y if and only if F(x) = F(y).

It is clear that in general, such classes of equivalence classes do not exist in NBG, unless all the equivalence classes themselves are sets, because if such an equivalence class is a proper class, it cannot be an element of any class.

For example, if M is the class of all sets, and if the equivalence relation ~ on M is the total relation M x M (so that x ~ y hold for all x,y ε M), then there is only one equivalence class, M itself. If there was such a class S of eqivalence classes, we would have M ε S, which is impossible, since M is a proper class.

 

[micromass]

I've seen this kind of approach, but it doesn't sit all very well with me. But it might be I don't understand it very well. Is the idea here, that when dealing with categories, we say that the category of sets is not really the proper class of all sets, but rather all elements of this set V_k? Thus we are working in the axiomatic system of ZFC+the existence of an inaccesible cardinal, in which categories as defined are not proper classes (which doesn't make sense here, as everything is sets) but actually sets?

Or is the idea that V_k provides us with a model for ZFC, so while our axioms are the axioms of ZFC, we are actually working at two levels: in a predefined universe V_k defined in a larger axiomatic system, with the axioms of ZFC? This last part is what I don't really get. In a way we are using set theory to provide us with a model for set theory.

I don't know how much model theory and set theory you know. But you should see the ZFC axioms not as axioms describing one single universe (unlike the field axioms). You should see them more as the group theory axioms, they describe many different groups. But groups are things we can write down explicitely in most cases: we can write down what elements it has and we can write down the multiplication table. The issue with set theory is that we cannot do the same. We can never write down all the different elements in the universe. So we just accept that there is some universe that agrees with the ZFC axioms. But if there is one such universe, then there are many universes. Indeed, we can find many subuniverses that also satisfy the ZFC axiom (just like there are many subgroups of a group).

In our case, if we have a universe that satisfies ZFC + the existence of a inaccessible cardinal $\kappa$, then we can show that $V_\kappa$ again satisfies all the ZFC axioms. So from mathematical point of view, there is little difference between taking the entire universe, or just $V_\kappa$, they are both valid.

So yes, we are working with two universes, the $V_\kappa$ and the entire universe (whose elements I call conglomerates). The category theory should be done on $V_\kappa$, it should provide us with a category of sets which is completely acceptable rigorously.

Also note that if I work in ZFC+inaccessible cardinal, then my terminology is a bit different. The entities here are called conglomerates (not sets). The elements of $V_\kappa$ are called sets and the subsets of $V_\kappa$ are called classes. This is different from the usual terminology. However, if we work in the universe $V_\kappa$, then the notion of sets and classes coincide with the usual terminology.

Of course, we can work in NBG too and there we also have a notion of sets and classes. But then there are many categorical constructions that we just cannot do. For example, quotienting. It would be very awkward to do category theory in NBG. In my point of view, accepting the existence of an inaccessible cardinal makes life way simpler, since it resolves all issues very neatly.

I can get on with the first part, it does make sense. I've just started reading "categories for the working mathematician", and the author does not really explain how 1) we know that the universe set exists and 2) we can still talk about proper classes and categories being larger than the universe set, such as the category of ALL sets. In your view, does the category of ALL sets really have any meaning at all(that is, assuming ZFC+inaccessible cardinal)? If not, will we not be missing something here?

Yes, category theory books tend to ignore the set theoretical issues. Some even state that they will totally ignore such issues.

Note that in the ZFC+inaccessible cardinal universe, all category theory is done on $V_\kappa$. So all categories are subsets of $V_\kappa$. In particular, the category of sets has as objects all elements of $V_\kappa$. If we want to talk about the category of all categories, then this is possible too, but then we don't call it a category but a quasicategory, since it will be just a conglomerate, not a class. If we want to talk about the category of all the conglomerates, then we will again run in the same issues, luckily we rarely ever want to do this.

 

[rubi]

The cleanest way to provide a basis for category theory is (in my opinion) the adding the axiom of universes to ZFC. It is equivalent to the existence of a proper class of inaccessibles, so that you don't run into any size issues anymore unless you want to break things deliberately. Inaccessible cardinals are actually a very weak addition to ZFC, compared to what set theorists study all day, so there is no need to worry. However, almost all the things that seem to require large cardinals at first, can already be proven from ZFC alone or ZFC + one inaccessible.

 

[disregardthat]

As far as I remember from an introductory course in mathematical logic, a model for a formal axiomatic system, like the peano axioms, (I have forgotten the exact terminology) were defined as a set, for which each axiom were given sense in the model. E.g. take the set of natural numbers N as a model for the peano axioms. The successor function is just addition with 1, and the 0 element is just 0 in N.

So how does one reconcile that set theory itself may provide a model for set theory? This very notion seems odd and self-referential to me. But also contradictory to the definition of a model as a set (if we use ZFC here). We take ZFC+inaccessible cardinal to prove the existence of a set which then in turn gives a model for ZFC. Am I just missing something? How does one formally define the notion of a model?

 

[disregardthat]

So let us assume that we take ZFC+inaccessible cardinals as our axiomatic system, and restrict the object and morphism classes of categories to elements and subsets of V_k. This still does not allow us to speak of the category of all sets. But as I understand it, the category with object class V_k does the job for most of our purposes in various settings. I will reiterate my question of whether we are not really missing something then. Why do we rarely want bigger categories than this, are there not common categorical constructions which may not fit into this picture? I have in mind for example the category of functors between two large categories, e.g. the category of functors V_k --> V_k. This is needed to view the natural transformations of functors V_k --> V_k as morphisms in a category.

 

[rubi]

So how does one reconcile that set theory itself may provide a model for set theory? This very notion seems odd and self-referential to me. But also contradictory to the definition of a model as a set (if we use ZFC here). We take ZFC+inaccessible cardinal to prove the existence of a set which then in turn gives a model for ZFC. Am I just missing something? How does one formally define the notion of a model?

What you do is the following: You start with a purely syntactic theory consisting of first order logic + ZFC + inaccessibles. Once you have that, you can develop formal logic and model theory within this theory by defining what a language is, what a well-formed formula is, what a theory is, and so on. You can then prove (on the level of syntax) that $(V_\kappa,\in)$ is a model of ZFC (viewed as a theory that is given by a language together with some first order axioms, just like any other theory like groups for example). So it really isn't circular at all.

So let us assume that we take ZFC+inaccessible cardinals as our axiomatic system, and restrict the object and morphism classes of categories to elements and subsets of V_k. This still does not allow us to speak of the category of all sets.

Right. However, $V_\kappa$ serves as the "indended model" of ZFC, because it is really how we think about sets. You can do all of ordinary mathematics within it, so it is really what we meant the category $Set$ to be. Of course, you are still free to talk about the category $SET$ of all sets, but then you have to deal with the size issues again and can't form functor categories as freely as you'd like to.

But as I understand it, the category with object class V_k does the job for most of our purposes in various settings. I will reiterate my question of whether we are not really missing something then. Why do we rarely want bigger categories than this, are there not common categorical constructions which may not fit into this picture? I have in mind for example the category of functors between two large categories, e.g. the category of functors V_k --> V_k. This is needed to view the natural transformations of functors V_k --> V_k as morphisms in a category.

If you have the axiom of universes, then all interesting categories are small with respect to some universe and functor categories don't pose any problems. The problems reappear if you want to talk about categories like $SET$ or $GRP$ instead of $Set$ and $Grp$. That's what we just have to live with if we want to deal with such pathological objects, I guess. Maybe you can climb up the ladder of large cardinals after you have exhausted all the inaccessibles, but that would just shift the problem. There is always only one "layer of proper classes" that you can meaningfully speak of, because if you have a class, given by some predicate $P(x)$, then $a \in \{x : P(x)\}=:A$ is just an informal way to write $P(a)$ (NBG is just a way to make this formal), but writing $P(a)$ is perfectly okay in first-order logic, so you can talk about one layer of classes by writing $P(a)$ instead of $a\in A$ everywhere. You can't have a "class of classes", however, because there is no way to formalize this in first-order logic, since a class itself isn't an element of the universe of discourse and thus you can't recycle the trick to write $P(A)$.

 

[disregardthat]

So, with our universe V_k, we distinguish between small and large categories. Small categories are categories in which the objects and the morphisms form sets. Large categories are categories in which the objects and the morphisms form subsets of V_k. But I still don't see how the exact same difficulties doesn't crop up with this, as opposed to dealing with small and large categories in NBG. With the V_k-model, you still can't generally form quotient categories, functor categories and such:

For example, the quotient category C/~: this would be a category in which the hom-classes hom(X,Y) are the "set of equivalence classes" in hom-classes hom_C(X,Y) of a category C. C may be large, and if not locally small, the sets hom_C(X,Y) may themselves be large, (i.e. not elements of V_k, but subsets). So now you form a category in which the hom-sets themselves are sets of subsets of V_k. Thus we depart from our notion of small and large categories, and form even larger types of categories. This is exactly the same issue we have in NBG.

In the link you provided he does not really talk about V_k at all. He does however introduce conglomerates as a way of formalizing these even larger categories. It doesn't really explain what axioms we impose on conglomerates, but as I understand it we allow quantification over classes, and basically do the same for classes as NBG does for sets.

Interpreting this in terms of models for ZFC, I believe this can be fixed by looking at the power set P(V_k). If we now say that conglomerates are elements of P(V_k), we are in the position to formally define the quotient category.

The category of all large categories would again form a proper class, the object class being P(V_k). To deal with the new issues here (such as taking quotient categories here), we could do a similar extension as ZFC --> ZFC+inaccessible and introduce classes for ZFC+inaccessible, just like NBG does for ZFC. But, the alternative here, just as before, is to extend ZFC+inaccessible by yet another inaccessible cardinal. And so on, of course. I now see rubi's point, that what we really need in order to do category theory freely without any worries (unless we deliberately want to ruin things) is the axiom of universes. As I understand it, we take ZFC and impose the axiom that for every set x, there is a universe containing x. Formally, by universe I suppose we are talking about Grothendieck universes.

In conclusion, we start off with a universe U containing the set of natural numbers. This already leaves ZFC. Then, assuming the axiom of universes, all the common categorical constructions such as functor categories, quotient categories and such can always be done on ANY category.

This was mostly me just wrapping up my thoughts on this issue.

 

[disregardthat]

I've been reading Set theory for category theory and I found it extremely informative.

One problem he pointed out with the approach of assuming ZFC+"Axiom of Universes", or equivalently ZFC+"a proper class of inaccessible cardinals" has to do with universal properties. We start out with an initial universe $V_{\kappa}$ for the least inaccessible cardinal $\kappa$. Suppose now we have a formula on the form $\phi(G,H)$ creating a statement on the form of that there exists a unique small G such that a certain property holds for all small H. For example, in the category of small groups Grp, let $F : J \to Grp$ be a diagram. The limit of this functor is determined by a universal property, namely that in the (small) category of nodes to this diagram, there is a unique object G satisfying a certain property $\phi(G,H)$ for all nodes H.

Now suppose we work with this object, and later decide to move up a step in the hierarchy, e.g. by considering the functor $F_* : Funct(CAT,J) \to Funct(CAT,Grp)$ by composition with F: $T : CAT \to J \mapsto F \circ T : CAT \to Grp$. Here CAT is the category of all large categories, contained in $V_{\lambda}$ for some inaccessible $\lambda > \kappa$. Now, having advanced a step, we now (crucially) consider Grp as a category contained in $V_{\lambda}$. Due to the different interpretations of "small", we can't a priori know that the small G satisfying $\phi(G,H)$ is the same as before. So we can't conclude that there exists $\phi(G,H)$ for all H (not just small H). Intuitively, G may now belong to $V_{\lambda}$ but not to $V_{\kappa}$, since we are in a different universe in which Grp and the category of nodes to F is interpreted differently. Even F must be redefined, going from J to the category of $\kappa$-small groups and then included into the category of $\lambda$-small groups.

The issue lies in the fact that we are changing all the definitions when advancing a step up the hierarchy. In $V_{\lambda}$, we are not at all interested in the category of $\kappa$-small groups, but rather $\lambda$-small groups. But simply considering a new object such as the functor $F_*$ shouldn't force us to redefine our previously defined sets, it is cumbersome to deal with both $Grp_{\kappa}$ and $Grp_{\lambda}$.