Independence and Category Theory - MathOverflow

Independence and Category Theory

2010-10-18T07:14:19Z

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?

Answer by Harry Gindi for Independence and Category Theory

2010-10-18T07:32:48Z

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.

Answer by Wouter Stekelenburg for Independence and Category Theory

2010-10-18T09:11:42Z

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.

Answer by Todd Trimble for Independence and Category Theory

2010-10-18T12:25:15Z

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.

Answer by François G. Dorais for Independence and Category Theory

2010-10-18T13:13:19Z

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.

Answer by Andrej Bauer for Independence and Category Theory

2010-10-18T13:24:27Z

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.

Answer by David Roberts for Independence and Category Theory

2010-10-18T22:59:37Z

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.