# Can everything in category theory be restated in a sufficiently expressive type theory?

I've been reading the homotopy type theory (HoTT) book as well as some articles on ncat lab, particularly this article < https://ncatlab.org/nlab/show/relation+between+type+theory+and+category+theory >

It seems that HoTT can be interpreted as the syntax for an $\infty$-groupoid or more generally an $(\infty,1)$-category. That article and related articles on ncatlab seem to suggest that within an arbitrary category $C$ the objects can be translated as types (as in HoTT types) and morphisms can be translated as dependent types. Thus a category can be interpreted as an "abstract data structure" and functors between categories are just ordinary (type theoretic) functions between data types/structures in type theory.

Is that translation correct, and if so, does that suggest that any categorical notion has a simple reformulation (without much work) to a homotopy type theoretic form? Coming from a computational background, for some reason, just replacing the word "category" with "abstract data structure" and a few other terms in category theory with type theoretic terminology seems to make category theory much more intuitive than it appears.

There are multiple issues here.

First, internal language is the term for when the structure on a class of categories can be captured by a type theory. Different type theories correspond to different classes of categories. For example, the simply typed lambda calculus (STLC) corresponds to Cartesian closed categories. This implies that any operation that would work within any Cartesian closed category corresponds to an operation in the STLC, and vice versa. It doesn't mean the STLC structure tells you everything about a particular Cartesian closed category. And if you have an arbitrary category which is not Cartesian closed, then this doesn't help you at all.

This leads to the next issue. Homotopy Type Theory (HoTT) is conjectured to be the internal language of $(\infty,1)$-toposes. These have a lot of structure (as does HoTT). Most categories are not $(\infty,1)$-toposes. Just like the STLC being the internal language for Cartesian closed categories doesn't help you when you have a category that isn't Cartesian closed, HoTT doesn't help you when your category isn't an $(\infty,1)$-topos. Types in HoTT don't correspond to arbitrary categories.

As the final issue, the categorical semantics of dependent type theories is complicated (because dependent type theories are complicated). Very roughly speaking, to translate a type theory into a category with the additional structure needed to support the operations in that type theory, types will be interpreted as objects and terms (in context) as morphisms. For dependent type theories with universes, types are also terms and there is extra structure on the category to handle that. With or without universes, though, there is a whole bunch of extra structure beyond a plain category that you need to interpret even the basic structure of a dependent type theory. We don't map categories into type theories, instead we recognize that some categories are models of some type theories. In the internal language of left exact categories, we can axiomatize the notion of a category. Models of this give rise to internal categories. In much richer type theories, we can construct things that look like categories to the type theory. This is what the HoTT book does in Chapter 9, for example.

While a category can be treated as an algebraic object like a group or a ring, this is not what most categorists are doing most of the time. Instead categorists are usually focused on larger categories like $\mathbf{Set}$ or $\mathbf{Grp}$ or $R\operatorname -\mathbf{Mod}$ and/or classes (or typically categories) of categories like Abelian categories, toposes, or symmetric monoidally closed categories. Rather than "abstract data structures", these classes of categories are more like languages (this is what the notion of internal languages is about) and then specific categories in those classes are like models/semantics for the corresponding internal languages. That said, most categorists don't think that much about internal languages either (at least not as explicit, formal things). This is typical. Most group theorists don't study the proof-theoretic, metalogical properties of the theory of groups but instead study (classes of) the (set-theoretic) models of the the theory of groups, namely the groups themselves.

If you did want to see what the internal language of an arbitrary category looked like, that's effectively what I'm illustrating in this blog post. If you wanted something where the "types" were arbitrary categories, then you'd want to look at what internal languages $\mathbf{Cat}$ was a model for, or put another way, what categorical structure $\mathbf{Cat}$ supports. Something that's not presented as an internal language but you may find interesting is A Higher-Order Calculus for Categories by Cáccamo and Winskel.

• Thanks for this thorough reply, very helpful. Another question I have: Is it necessary to "invoke" category theory for functional programming (e.g. in Haskell)? Can't the useful parts of category theory be stated more clearly in type theory? There's such a clamor for category theory in functional programming these days. – Brandon Brown Dec 22 '17 at 1:33
• There is a particular theory in SLTC that corresponds to a particular cartesian closed category, which is also sometimes called the "internal language" of that category: its types are, by definition, the objects of the category, and its morphisms are the terms. That STLC theory does tell you "everything" about the category, in a suitable sense. – Mike Shulman Dec 22 '17 at 4:58
• @MikeShulman Yeah, I was trying to tread a fine line there hence the phrasing "the STLC structure". In an earlier form I had something like "it doesn't 'usefully' describe the category" followed by some sentences stating what you said but pointing out that this comes in the form of a bunch of (likely a proper class of) "primitive" terms and equations. I intentionally avoided talking about the "internal language" of a particular category, though I was tempted to, e.g., at the end say "the internal language of Cat". – Derek Elkins Dec 22 '17 at 6:22