58
$\begingroup$

Earlier today, I stumbled upon this article written by V. Voevodsky about the "philosophy" behind the Univalent Foundations program. I had read it before around the time of his passing, and one passage that I remember vividly is this, for which I have little in the way of rigorous justification:

The greatest roadblock for me was the idea that categories are “sets in the next dimension.” I clearly recall the feeling of a breakthrough that I experienced when I understood that this idea is wrong. Categories are not “sets in the next dimension.” They are “partially ordered sets in the next dimension” and “sets in the next dimension” are groupoids.

Voevodsky, The Origins and Motivations of Univalent Foundations

If I had to guess, I'd say that the noninvertibility of morphisms in categories corresponds to some form of partial ordering, whereas a groupoid carries no such information since all morphisms are in fact isomorphisms, but surely there's something deeper at play that caused someone like Voevodsky to consider this realisation a "breakthrough" that accompanied a significant "roadblock".

$\endgroup$
  • $\begingroup$ I had no idea what to tag this with; appropriate retagging would be appreciated. I'm not sure if this is a valid soft-question. $\endgroup$ – Soham Chowdhury Aug 31 '18 at 13:19
  • $\begingroup$ I have a very low-brow answer. A poset that's a groupoid is a set with a reflexive relation on it. Conversely, you can canonically turn any set into a poset by taking its reflexive relation as the partial order. $\endgroup$ – arsmath Aug 31 '18 at 15:51
  • 1
    $\begingroup$ If I take 0-categories as categories enriched in -1-categories i.e. truth values {0,1}, then a 0-category is equivalent to a preorder. A 0-groupoid is a 0-category in which every morphism is invertible i.e a symmetric preorder otherwise known as an equivalence relation. This means 0-groupoids are sets with equivalence relations (sometimes called setoids) which can be thought of as a set which retains evidence for equality (I believe this is the view of Bishop). The skeleton of a setoid is then the quotient (i.e. equivalence classes) which is a set. $\endgroup$ – Callan McGill Aug 31 '18 at 18:47
  • 1
    $\begingroup$ In the same way an infinity groupoid might be thought of as a model for types with higher order identity relations. $\endgroup$ – Callan McGill Aug 31 '18 at 18:48
62
$\begingroup$

First, there is indeed nothing mathematically very deep in this observation, and I agree that the word "breakthrough" might be exaggerated. But on the other hand lots of very deep ideas look trivial once spelled out explicitly. Moreover being younger than Voevosky I have never been really exposed to the idea that categories were sets of higher dimension (but this indeed appears in the early work on higher categories, typically in Baez & Dolan's work), so I can't comment on how important it was to understand that this is not a good point of view. But I can give some context on what Voevodsky probably meant here.

One thing to understand is that, like many mathematicians and most category theorists, Voevodsky is very attached to the "principle of equivalence" saying that when talking about categories you should only use concepts that are invariant under equivalence of categories. For example, in his work on contextual categories, he renamed them "C-systems" because he didn't want to call them categories as their definition is not invariant under equivalence of categories.

Now, if you follow this principle of equivalence very strictly, talking about "the set of objects of a category" is not meaningful (i.e. break the principle of equivalence): equivalent categories can have non-isomorphic sets of objects. So saying that a category is "a set of objects together with a set of arrows having a certain structure" is incorrect from this perspective.

It is true that if you have a set of objects and a set of arrows with the appropriate structure you get a category, and it is also true that any category can be obtained this way, but you cannot recover the set of objects and the set of arrows from the category without breaking the principle of equivalence. To some extent the set of objects and of arrows with the appropriate structure is a "presentation" of your category.

What is meaningful though (i.e. respects the principle of equivalence) is that a category has a "groupoid of objects" $X$, with a bifunctor $Hom : X \times X \rightarrow Set$

From the point of view of the principle of equivalence, a category is really a groupoid with structure. Moreover this structure is a very natural categorification of the notion of poset:

  • A poset is a set X with a function $X \times X \rightarrow Prop$ satisfying reflexivity, anti-symmetry and transitivity.

  • A category is a groupoid $X$ with a functor $X \times X \rightarrow Sets$, satisfying some conditions. Reflexivity corresponds to the existence of an identity, transitivity corresponds to the composition operation, and anti-symmetry corresponds to the fact that in the end one wants $X$ to be the core groupoid of the category.

But if you really take the principle of equivalence seriously, you cannot define what a "groupoid" is, you have to take it as a primitive notion that you axiomatize. But this is not really different from the fact that you cannot define what a "Set" is, you can only axiomatize what you can do with sets.

It is in this sense that groupoids are "higher dimensional sets" and categories are groupoids with a structure. This has been made even more clear with the theory of $(\infty,1)$-categories, where it is completely clear that $\infty$-groupoids play the role that sets played for ordinary categories. (The $(\infty,1)$-categorical Yoneda lemma is in terms of functors to the category of $\infty$-groupoids etc...)

Another way to say this is that in the $n$-categorical hierarchy "0-groupoid"s are just sets while $0$-categories are posets (if you consider them as $(n,1)$-categories for varying $n$...)

| cite | improve this answer | |
$\endgroup$
  • 5
    $\begingroup$ This is a great answer! $\endgroup$ – user45878 Aug 31 '18 at 14:27
  • 8
    $\begingroup$ Seconded. I'd never thought of categories as "groupoids with structure" before, and "To some extent the set of object and of arrows with the appropriate structure is a "presentation" of your category." was a bit of an aha-moment (a breakthrough, if you will!) for me. :) $\endgroup$ – Soham Chowdhury Aug 31 '18 at 14:55
  • 3
    $\begingroup$ Right, this is exactly my impression. (And I definitely understand Voevodsky there as using breakthrough in the sense of a personal aha moment, not in the sense of a difficult technical triumph — he had much higher standards of what the latter would mean…) $\endgroup$ – Peter LeFanu Lumsdaine Aug 31 '18 at 17:04
  • 4
    $\begingroup$ Maybe worth adding that once you do take that step of regarding groupoids, or more generally $\infty$-groupoids, as a primitive notion to be axiomatized, then it is no longer true that every category can be presented by a set of objects equipped with a set of arrows (unless you assume as an axiom that every groupoid can be so presented, which rules out many naturally-occurring higher topos models). $\endgroup$ – Mike Shulman Aug 31 '18 at 18:53
  • 8
    $\begingroup$ By the way, the idea of categories as "groupoids with structure" is very explicit in Chapter 9 of the HoTT Book homotopytypetheory.org/book, which in turn owes a lot to Charles Rezk's "complete Segal spaces" as a model for $(\infty,1)$-categories by regarding them as "$\infty$-groupoids with structure". $\endgroup$ – Mike Shulman Aug 31 '18 at 18:54
38
$\begingroup$

The other answers are quite good and nothing is wrong with them, but lest a wrong impression be given (e.g. by the implicit suggestion that the idea of "categories as sets in the next dimension" in early work on higher categories was "wrong"), I want to add that while Voevodsky is of course correct from a certain point of view, there is another valid point of view according to which categories are, indeed, "sets in the next dimension".

The point is that you have to have two orthogonal axes of "dimension". David Corfield mentioned this briefly in a comment: instead of just $n$-categories, consider $(n,r)$-categories: categories with (potentially) nontrivial $k$-morphisms for $0\le k\le n$, but where all $k$-morphisms are invertible for $k>r$. Here "0-morphisms" are objects, and it doesn't make sense to ask for them to be invertible, so $r\ge 0$. Thus for instance:

  • A (1,1)-category is a 1-category in the usual sense: objects (0-morphisms) and arrows (1-morphisms), not required to be invertible.
  • A (1,0)-category is a groupoid: objects and arrows, but the arrows are required to be invertible.
  • A (2,2)-category is a 2-category in the usual sense: objects, arrows, and 2-cells, none required to be invertible.
  • A (2,1)-category is a 2-category all of whose 2-cells are invertible, but whose 1-morphisms may not be, i.e. a category (perhaps weakly) enriched over groupoids.
  • A (2,0)-category is a 2-groupoid: a 2-category all of whose 1-morphisms and 2-morphisms are (perhaps weakly) invertible.
  • An $(\infty,0)$-category is an $\infty$-groupoid: it has cells of all dimension, all invertible.
  • An $(\infty,1)$-category is what Lurie's school calls an "$\infty$-category": it has morphisms of all dimension, all invertible except the 1-morphisms.
  • A (0,0)-category is a set: only objects, no invertibility requirements.

Now you might think from the definition of $(n,r)$-category that you would have to have $r\le n$. But in fact there is a natural way to extend it to the case $r=n+1$. For when $r\le n$, we can identify $(n,r)$-categories (up to equivalence) as $(n+1,r)$-categories in which any two parallel $(n+1)$-morphisms are equal. Then we can take the latter when $r=n+1$ as a definition of $(n,n+1)$-category. This gives:

  • A (0,1)-category is a 1-category in which any two parallel 1-morphisms are equal, i.e. (up to equivalence) a poset.
  • A (1,2)-category is a category enriched over posets, or equivalently a 2-category in which all hom-categories are posets.

Now we can see how the "raising dimension" step that Voevodsky was thinking of takes sets to groupoids and posets to categories: just add one to $n$ in $(n,r)$.

  • $(0,0) \mapsto (1,0)$
  • $(0,1) \mapsto (1,1)$

But there's another natural "raising dimension" step that does indeed take sets to categories: add one to both $n$ and $r$.

  • $(0,0) \mapsto (1,1)$

Since in common usage "$n$-category" for $n\ge 1$ refers to an $(n,n)$-category, it is therefore very natural to say that it is sets, i.e. (0,0)-categories, deserve the name "0-categories", whereas posets should be called (0,1)-categories.

So I think Voevodsky's phrasing of his breakthrough may have been a bit too dogmatic. The point isn't that it's "wrong" to regard categories as sets in the next dimension (or at least a next dimension). The point is that it's also valid to regard groupoids as sets in the next dimension, and that this latter point of view is extremely fruitful, leading in particular to univalent foundations but also (somewhat independently) to the recent boom in $(\infty,1)$-category and $(\infty,n)$-category theory.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ +1, very enlightening. It looks like the world where the $(n,r) \mapsto (n+1,r+1)$ step were the one "chosen" would have $(2,1)$-categories as its notion of "poset, one dimension up", and this makes sense once I think about it being enriched in groupoids. $\endgroup$ – Soham Chowdhury Sep 1 '18 at 2:37
  • $\begingroup$ Do you have a source for the discussion where Corfield made that remark? $\endgroup$ – Soham Chowdhury Sep 1 '18 at 2:37
  • 1
    $\begingroup$ @SohamChowdhury I just mean this comment right here: mathoverflow.net/questions/309515/… $\endgroup$ – Mike Shulman Sep 1 '18 at 3:21
  • 3
    $\begingroup$ This idea goes back to Baez and Dolan. You can read about it around pp. 34-36 of Baez's Lectures on n-Categories and Cohomology (for which Mike took the notes), arxiv.org/abs/math/0608420. $\endgroup$ – David Corfield Sep 1 '18 at 11:33
11
$\begingroup$

Even if this answer can be seen as an expansion of the last two lines of Simon's answer, it does not really come in the same spirit.

From the point of view of enriched category theory, posets are categories enriched over the boolean algebra $2=\{\bot < \top\}$. Very often this enriched category theory is called $0$-category theory.

$$\text{Pos} = 0-\text{Cat}. $$

The concept of groupoid is not enrichment dependent, but the actual incarnation of such is. When one looks at groupoids in this context, sets arise. It would be better to say discrete posets.

$$ \text{Sets} = 0-\text{Grpd}. $$

Obviously, changing site of enrichment from $2$ to Set one gets that Cats are Set-Categories and Grpds are Set-Groupoids.

$$\text{Cat} = \text{Set}-\text{Cat}, $$ $$\text{Grpd} = \text{Set}-\text{Grpd}. $$

Very often, especially in the context of homotopy theory, Set-category theory is called $1$-category theory.

To come closer to Simon's answer, one should observe that technically $0$-groupoids correspond to setoids and not sets. For several reasons, especially in these days of homotopy type theorists, setoids might be a more convinient category of sets.

Talking about posets, they correspond to skeletal $0$-categories, while $0$-categories are preorders.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Is a setoid the same thing as what Vistoli (arxiv.org/abs/math/0412512) calls a "rigid groupoid" (i.e. a groupoid such that there no morphism or exactly one morphism between any objects (in a given order) i.e. $Hom(x,y)\subseteq \{*\}$ )? Then how can an object have nontrivial automorphisms? $\endgroup$ – Qfwfq Aug 31 '18 at 16:24
  • 1
    $\begingroup$ I am not familiar with the notion of rigid groupoid, but I was pretty clear with my definitions, a setoid is precisely a groupoid in $0$-category theory. Equivalently it is a symmetric preordered set. $\endgroup$ – Ivan Di Liberti Aug 31 '18 at 16:30
  • $\begingroup$ I'm pretty sure that the terminal Boolean algebra has only one element. (-: $\endgroup$ – Mike Shulman Aug 31 '18 at 20:33
  • $\begingroup$ And @Qfwfq is right, an object of a setoid cannot have a nontrivial automorphism group. $\endgroup$ – Mike Shulman Aug 31 '18 at 20:34
  • $\begingroup$ I briefly edited my answer, but feel free to improve it. $\endgroup$ – Ivan Di Liberti Aug 31 '18 at 20:53
7
$\begingroup$

I cannot say what exactly Voevodsky meant but here is a wild guess.

Disclaimer in what follows I use heavily type theoretic notation, so you have trouble understanding feel free to ask in the comments.

In constructive, specifically type theoretic, settings one usually define sets as pairs of the form $(X,=)$ where $(=)$ is an equivalence relation, which in the context of type theory is basically a dependent type of the form $X \to X \to Type$ ($X \times X \to Type$ if you do not feel confortable with currying) such that

  • for each $x,y \colon X$ the type $x = y$ is either a singleton or the empty type
  • the relation is reflexive, that is for every $x$ we have that $x = x$ is a singleton, which means that we have a function that sends every $x \in X$ in the inly element of $x = x$ that is an element of the type $\prod_{x \colon X} (x = x)$
  • transitive, i.e. for each $x,y,z \colon X$ if $x = y$ and $y = z$ are both inhabitated, hence they are singleton types, then also $x = z$ is inhabitated, which in type theory is equivalent to require that there is an element of type $\prod_{x,y,z \colon X} (y=z) \times (x=y) \to (x=z)$
  • symmetric, which means that if $x = y$ is the singleton type(i.e. is inhabitated) $y = x$ is a singleton type as well, which again type theoretically means that there is an inhabitant of the type $\prod_{x,y} (x = y) \to (y=x)$.

In this framework a poset (to be honest a preordered set) can be defined pretty much the same way just dropping the symmetric-requirement above: so a poset is given by a type $X$ with a dependent type $\leq \colon X \to X \to Types$ whose values are only singletons or the empty type with a dependent function in $r \colon \prod_{x \colon X} x \leq x$ (withnessing the reflexivity of $\leq$) and a dependent function in $t \colon \prod_{x,y,z \colon X}(y \leq z) \times (x \leq y) \to (x \leq z)$ (withnessing transitivity).

If you drop the singletons-or-empty type requirement in the definitons above and replace it with the condition

  • for every $x,y \colon X$ the type $x \leq y$ is a set, i.e. a type with an equality as above

and add as requirement the existance of elements for the types

  1. $\prod_{x,y,z,w \colon X}\prod_{f \colon x \leq y}\prod_{g \colon y \leq z}\prod_{h \colon z \leq w}(t(h,t(g,f)))=t(t(h,g),f))$
  2. $\prod_{x,y \colon X}\prod_{f \colon x \leq y} (t(f,r(x))=f)$
  3. $\prod_{x,y \colon X}\prod_{f \colon x \leq y} (t(r(x),f)=f)$

you get the definition of a category.

If you replace $\leq$ with $=$ add the element to the type $\prod_{x,y} (x=y)\to (y=x)$ and few other things you get the definition of a groupoid.

So summarizing I think that the motto categories are poset in the next dimension means that they are transitive systems, i.e. types with a transitive and reflexive dependent type $\leq$, in which $\leq$ is a set which is a $1$-dimensional object (a type with equality relations between its elements) instead of just a $0$-dimensional object (a type with at most one inhabitant).

In similar way groupoids are next level sets because they are sets, i.e. types with a dependent reflexive, symmetric and transitive type $=$, in which $x=y$ are sets $1$-dimensional objects instead of just singletons or empty types.

I hope this helps.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ +1, this is a great answer from the "other side" and made the similarities a little clearer! $\endgroup$ – Soham Chowdhury Aug 31 '18 at 17:05
  • 1
    $\begingroup$ Incidentally, regarding the disclaimer: I was (quite informally) familiar with type theory (from occasionally dabbling in Agda and implementing type systems in Haskell) before I ever started learning maths, and your answer was quite readable. :) $\endgroup$ – Soham Chowdhury Aug 31 '18 at 17:06
  • $\begingroup$ @SohamChowdhury if you give me some hints on where improve it I can expand a little more on some part. I'm all for improving answers whenever it's possible. $\endgroup$ – Giorgio Mossa Aug 31 '18 at 21:33
  • $\begingroup$ Besides what did you mean by "the other side"? I am curious. :-) $\endgroup$ – Giorgio Mossa Aug 31 '18 at 21:54
  • $\begingroup$ I just meant something more from the type theory POV, rather than the category theory one. $\endgroup$ – Soham Chowdhury Sep 1 '18 at 2:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.