# Independence and Category Theory

I'm not very experienced with respect to Category Theory. So if this question makes no sense I'm sorry. At any rate here is my question: If the existence or non-existence of specific sets can be independent of set theory, then how can it be that the category Set is complete under small limits?

For example, suppose you have a small category A, with objects that are linearly ordered spaces X such that: X is without smallest or largest element, X has CCC, X is complete, and X is dense in itself. And as morphisms for A, you take order preserving bijections. Now, let F be the forgetful functor from A to the underlying set.

How exactly can you define the limit over F inside of Set?

Another example, would be considering some set sized collection of Whitehead groups, call it X. Now, consider X as a category equipped with homomorphisms as morphisms. And let G be the forgetful functor from X into Set.

How exactly can one define the limit over G inside Set?

Or even better, suppose that G is the identity functor from X into Grps. Then, what happens?

Am I correct in saying that the answer depends drastically on the set theoretic universe you pick? If so, how is this not a problem with category theory?

-

Like all fields of mathematics, Category Theory is not immune to foundational questions. Although different foundations have been presented, the most common foundation for Category Theory is within Set Theory: Category Theory starts with a given universe of sets and then develops its theory. The computation of limits, colimits, and whatnot will be affected by the overlying structure of sets. However, this overlying structure of sets is not variable. When a computation depends on certain principles of Set Theory, it must be labeled as such. For example, Grothendieck Universes and Vopenka's Principle are large cardinal axioms which have direct applications in Category Theory.

That said, Category Theory is in a unique position to deal with independence results that arise from Set Theory. Indeed, every forcing construction in Set Theory has an analogue in Category Theory via sheaves over an appropriate site. More precisely, forcing poset can be viewed as a small category and when endowed with the double-negation topology, the Grothendieck topos of sheaves over this site is equivalent to the Boolean-valued model that one obtains in via forcing. Thus independence results from Set Theory are directly visible to Category Theory by doing the computations inside a Boolean Grothendieck topos instead of the topos of sets.

-
I totally fail to see how this answer (although a very informative one) actually answers your worries. – Andrej Bauer Oct 18 '10 at 22:45
Well my worry was that in some sense CT needed for things to be settled, or decided "in order to function." (at least this the sense I was always left with after speaking with "category theorist" like Harry for example or reading about category theory). This made me curious about: 1) How "things" which are independent with respect to ZFC transfer into, and play with the inner workings of CT. And 2) If you could even show, using categorical language and tools that these "things" were indeed independent in the first place. He answered both of these. You did not. – Michael Blackmon Oct 19 '10 at 4:23
My only problem was that my question was a poor attempt to convey this, I was under the impression that things of this nature (which are considered more of an issue in set theory) where handled in a similar way. I now see, this was a very incorrect assumption – Michael Blackmon Oct 19 '10 at 4:25

A beginner's question is ok I think, especially since it may confuse non-beginners. Let me try to answer as concretely as possible, for the benefit of beginners who usually prefer to see concrete answers to general ones.

We first consider a simple case. We adopt as our meta-theory ZFC. Consider the small category $\mathcal{C}$ whose objects are $$\mathrm{ob}(\mathcal{C}) = \lbrace \emptyset \mid 2^{\aleph_0} = \aleph_1 \rbrace,$$ and there are no morphisms other than the identity morphisms. Thus, $S$ has a single object $\emptyset$ if the continuum hypothesis holds, and is empty if the continuum hypothesis does not hold. We define a functor $F : \mathcal{C} \to \mathsf{Set}$ by $F(X) = X$ and $F(\mathrm{id}_X) = \mathrm{id}_X$. Now of course the limit of $F$ exists, but the answer as to what the limit is depends on the status of the continuum hypothesis:

• first note that by the law of excluded middle either $2^{\aleph_0} = \aleph_1$ or not,
• if $2^{\aleph_0} = \aleph_1$ then the limit of $F$ is the set $\emptyset$,
• if $2^{\aleph_0} \neq \aleph_1$ then the limit of $F$ is a singleton, e.g., $\lbrace \emptyset \rbrace$.

Ok, this was just an exercise in which we get used to the fact that a thing may exist, but what the thing is may depend on the status of an undecidable sentence. Nevertheless, it exists, it is just that the question "Is the limit $\emptyset$ or $\lbrace \emptyset \rbrace$?" is undecidable.

There is a trickier question we can ask, and which you are asking I think, namely, can we conjure up a functor $F$ such that its limit is a set whose very existence itself is independent of ZFC. For example, one might try to come up with an $F$ whose limit is a Suslin line. The answer is that you will fail in such attempts. Why? Because ZFC proves that all small diagrams have limits. If the power of proof does not convince you, then perhaps we should look at one specific example that you listed.

You suggested the category $\mathcal{S}$ of "Suslin objects" (by which I mean dense totally ordered sets without endpoints satisfying CCC) with order-isomorphisms as morphisms. First of all, as stated $\mathcal{S}$ is not small, but we can make it small by limiting the rank of its objects to something like $\omega + 1$ (correct me if my ordinal is too small, I just need an $\alpha$ such that $V_\alpha$ includes isomorphic copies of all possible Suslin objects). The functor $F : \mathcal{S} \to \mathsf{Set}$ is just the underlying-set functor. The trouble here of course is that the question "Does $\mathcal{S}$ contain a Suslin line?" is undecidable, so we might worry that the existence of the limit of $F$ itself is undecidable. But it isn't! The limit exists, and up to isomorphism it is simply the cartesian product of (the underlying sets of) all Suslin objects whose rank does not exceed $\omega + 1$, whatever they are. Of course, the question "what does the limit look like?" depends on existence of Suslin lines.

The other examples you listed are of the same nature.

Look, this has nothing to do with category theory. Consider the triangle in the plane whose vertices have coordinates $A = (0,0)$, $B = (0,1)$ and $C = (x,1)$ where $x = 1/2$ if Suslin line exists and $x = 42$ otherwise. The triangle exists, but telling whether it is isosceles is a bit difficult. Your worry is of exactly the same kind, I think.

-
Now I fill dizzy for having used the law of excluded middle in such a horrible way. – Andrej Bauer Oct 18 '10 at 13:33
Yes, I know I just rewrote Todd's anwser and your comments. But I think in this case the answer should be as specific and down-to-earth as possible, so I thought it was worth doing. – Andrej Bauer Oct 18 '10 at 14:39
You two don't seem to understand what I'm looking for: Namely whether category theory can correctly handle independence results. That is to say, without actually trying to compute or define objects that depend on them. That being said the examples you have given me are fine, and your answer is a nice attempt. The only problem is they rely on the assumption that you can make a choice about the existence of such objects. That is to say they only make sense when you have asserted the existence or non-existence. – Michael Blackmon Oct 18 '10 at 17:17
This discussion should probably be brought to a close (if you want you can write me at topological dot musings at gmail dot com), but in which statement of mine does it seem to you that I am missing the well-known fact that independence phenomena are embedded in theories? The question as to "how these issues are dealt with in category theory" has been partially addressed by Francois, but you seem to be advancing the idea that "category theory" gets it wrong somehow. I guess there are inexperienced category theorists who get it wrong sometimes, but I don't see that's happened here. Bye! – Todd Trimble Oct 18 '10 at 19:34
@burned: Excuse me, but you asked explicitly "How can you define the limit of $F$ inside $\mathrm{Set}$?" This means you explicitly worried that somehow independence phenomena prevent us from constructing limits of small diagrams. They do not. All I can say is that you are confused in some trivial issue, but unfortunately I cannot see what the issue is (and certainly it is unrelated to Category theory). I thought I answered your problem. Anyhow, I am not going to prolong this discussion anymore. Talk to me privately if you will. – Andrej Bauer Oct 18 '10 at 22:51

First, may I ask that we please not get into name-calling or ad hominem attacks. You should think of this as a site at a professional level, and the behavior should be more or less that expected at a professional seminar.

The question is, I think, quite reasonable. A limit or colimit as seen from within a countable model of set theory may not be the limit or colimit as seen from an external point of view. But note that the "external" judgment itself involves a background model $V$!

None of this should be a worry. The point is that, for any reasonable theory of sets, limits and colimits exist and are unique up to isomorphism for any small diagram which is definable in the theory. Each model of the theory will interpret the terms as they will, and each model is complete and cocomplete according to that interpretation.

Other categories such as $Grp$, and forgetful functors and so on, are definable by class formulas we can write down in the theory, and these too will be interpreted as they will for each individual model. We understand that the "meanings" of these terms are model-dependent, but in any event it's enough to recognize that the theory itself is expressive enough to accommodate limits and colimits, etc.

-
@Todd: The question that the OP is asking is how can we define the colimit over a category when the content of the category is independent of ZFC. I'll strip down his objection to a very barebones case: Let $X$ denote a set consisting of one representative per isomorphism class of whitehead groups of cardinality less than $\gamma$, and consider this as a discrete subcategory (not full, obviously) of the category of sets (denote the inclusion also by $X$). Consider the proposition: colim X is empty. Then this proposition is independent of ZFC. – Harry Gindi Oct 18 '10 at 13:07
So far, that's all well and good. However, for some reason, the OP seems to think that this is a problem with category theory. We can't pin down the exact set $colim X$ without further axioms of ZFC. Category theory says that this set exists in the ordinary category of ZFC sets and further that we can characterize it up to unique isomorphism by a universal property. – Harry Gindi Oct 18 '10 at 13:12
The point that the OP seems to be missing is that given any small category $X$ and any functor $X\to Set$, we can give a formula for the colimit (i.e. a set satisfying the universal property), which exists as a ZFC-set (by inspection). – Harry Gindi Oct 18 '10 at 13:16
Well, I was focusing on OP's question about existence of limits and colimits, and the question of whether any model is complete. As Andrej said, "Because ZFC proves that all small diagrams have limits", and this was my answer too. I think we are all in agreement here. – Todd Trimble Oct 18 '10 at 14:06
@Todd: Yes, I was clarifying what the OP meant to ask (since I was arguing with him on IRC, and his question here was somewhat unclear). Everything you've said is virtuous, fair, and true. – Harry Gindi Oct 18 '10 at 14:14

This is where you make an easily made error (emphasis mine)

how can it be that the category Set is complete under small limits?

Set depends on your background choice of set theory (if that is how you are doing things). Your question has been answered, but I hope this will clear up a few loose ends. Given two models $M_1$, $M_2$ of ZF(C), you get two categories $Set_1$ and $Set_2$. Now both of these are cartesian closed, so that the hom-objects of $Set_i$ are objects of $Set_i$.

• Point 1: nothing tells us that the hom-objects of one are objects of the other.

Now both of these have limits, with respect to diagrams $D_i \to Set_i$ where $D_i$ (the shape of the diagram) is a category internal to $Set_i$.

• Point 2: nothing tells us that $D_1$ is a category internal to $Set_2$ and vice versa.

But I gather from your question that you are interested in diagrams of shape $D$ such that $D$ is a category in both $Set_1$ and $Set_2$. (This poses somewhat of a restriction, especially if $M_1$ (say) is a countable model, as then $D_1$ has a countable set of arrows, whereas $Set_2$ may have many more limits) Now suppose we have such a $D$. Then all diagrams $D\to Set_i$ have a limit. This argument is rubbery, as it supposes that $D$ is contained in two categories at once, so see below.

However, your question is, what happens if these limits are different? Well, this is not really a question one can ask, as $Set_1$ and $Set_2$ are different categories. There is no a priori way to compare objects of two different categories. If one has a functor between categories, then it is possible to see what relation objects of one category have to another category (at this point, someone might ask 'what about comparing the objects of the two categories in some meta-theory, but taking a category theoretic approach, one does not refer to the meta-theory - everything happens inside the categories). But to have such a functor one needs $Set_1$ and $Set_2$ to belong to the same category $Cat$ of categories. But $Cat$ again depends on one's choice of background theory. This is not a problem, because it makes less sense to ask for a morphism between two objects of a different category than to ask to compare objects of different categories. So in a sense, $Set_1$ and $Set_2$ don't know about each others' limits.

So really where things 'went wrong' is that we assumed that $D$ was contained in both categories $Set_1$ and $Set_2$. To even know this works we need a functor between $Set_1$ and $Set_2$. But what $D$ is in $Set_1$ could be somewhat different to what it is in $Set_2$. We could take $D = \mathcal{C}$ from Andrej's answer, which is not a single category but really two, $D_1$, $D_2$ one in each of $Set_i$. The functor between the two categories of sets can quite happily map one of these categories to the other, and the limit will be preserved by this functor, it's just they won't be "the same".

The above is very much off-the-cuff, and I am not a logician, but I hope it helps a little.

-
David, the question of whether there is a functor of a certain kind from one category to another can also be seen as a purely set-theoretic question (is there a function from the objects and morphisms from the first category to the other with certain properties) rather than as a category theoretic question that only makes sense in some bigger meta-category. And I see this as the key issue involved in your other recent question mathoverflow.net/questions/42710/… – Joel David Hamkins Oct 19 '10 at 1:43

A category is small if its objects and morphisms form a set rather then some other kind of class. Smallness is therefore relative to the model of set theory we are working in and the whole notion was invented just to express this dependence on set theory. The limits you are talking about are unstable: they change when the model of sets in the background changes. Most mathematicians that work with categories simply avoid such pathological cases.

-
If I'm looking for more material on the subject of unstable limits and category theory where might I look? – Michael Blackmon Oct 18 '10 at 9:20
@burned: If a limit exists in ZFC, it exists in any extension of ZFC. – Harry Gindi Oct 18 '10 at 9:45
@burned: I'm not going to get into a namecalling match with you. This is over. – Harry Gindi Oct 18 '10 at 9:53
@burned I flagged that last comment as offensive. Wherever you learned (or failed to learn) how to behave, you will have to play by different rules on this site. – Alex B. Oct 18 '10 at 11:50
@Michael Blackmon: "Sheaves in Geometry and Logic" by Saunders MacLane and Ieke Moerdijk is a good starting point. – Wouter Stekelenburg Oct 19 '10 at 8:11

The actual category $A$ does not matter. The only thing that matters is the "shape" of $A$. We define the limit to be the hom-set $Hom_{Set^A}(*,F)$ from the terminal functor into $F$. It does depend on the set-theoretic universe, and I've glossed over those details, but you can be reasonably certain that it really doesn't matter once we pick $Set$ to be large enough.

If you mean by "set-theoretic universe" that we pick different axioms for our sets, then it obviously depends a lot on this. $A$ is defined in terms of the category of sets.

There is no problem with category theory. The problem is that you don't understand what kinds of questions we ask and answer using it. You are asking questions akin to "Let X be a set. What is the cardinality of X?" We can define the cardinality just fine. We cannot determine it without more information. In fact, since we know that $X$ is a set, we know that its cardinality is a cardinal denoted by $|X|$, but pending more information, we cannot say anything more.

-
But you cannot quarantine this to just sets, this dependence on the axioms of set theory will spread to any category you can "map" Set into, Top, Grp, etc.. The independence of the very existence of a suslin line and whitehead group will guarantee that as soon as you pick a "value" for any of these limits, you have just changed the axioms of set theory you are currently working with. That is the problem, and I don't understand why this isn't handled with more care. Thus, you do not answer my question. – Michael Blackmon Oct 18 '10 at 8:34
You have a fundamental misunderstanding of category theory, as you demonstrated in our IRC exchange. I feel like the only way that you will be satisfied is if a logician explains to you why you're wrong. – Harry Gindi Oct 18 '10 at 8:37
Yes, when a logician, and properly trained mathematician--that understands the care you need to take with these issues--gives me an answer I will be satisfied. – Michael Blackmon Oct 18 '10 at 8:40