4
$\begingroup$

I have seen many examples of working with categories inside a proof assistant, even some proof assistants like rzk created in part with this as a motivating purpose. Given trinitarianism, it seems at least plausible to me that one might create a proof assistant whose core is based on category theory instead of type theory.

Has this been tried previously in any experimental proof assistants? Are there any immediately apparent reasons that this would or would not be useful?

$\endgroup$
4
  • 1
    $\begingroup$ What do you mean by a core which uses category theory? Like first order logic with ETCS (or ETCC) instead of ZFC? If not, then one could argue that type theory is just formal category theory. (Although I guess one could take a category-theoretic-first approach to designing the type system making sure it is exactly the semantics of a particular family of categories, like a topos. Maybe homotopy type theory fits that bill.) $\endgroup$
    – Jason Rute
    Commented May 7 at 20:36
  • $\begingroup$ Or is the point that “category” should be the fundamental notion instead of say “set”, “type”, or “function”? I think this is what ETCC does, but I don’t think it is in any proof assistant. I guess I have also heard of people trying to come up with a type theory where the types represent (higher?) categories (instead of sets, groupoids, etc). I don’t know if there has been progress. $\endgroup$
    – Jason Rute
    Commented May 7 at 20:43
  • $\begingroup$ I mean your second comment, that "category" (maybe along with functors, natural transformations, etc.) is the fundamental notion. I ran across this paper A Formal Logic for Formal Category Theory that seems to be somewhat in that direction, embedded in Agda. I have not seen any standalone proof assistants. $\endgroup$ Commented May 8 at 0:05
  • $\begingroup$ Does something like Metamath + first-order theory of an abstract category count? $\endgroup$
    – siegment
    Commented May 8 at 4:24

1 Answer 1

6
$\begingroup$

It only makes sense to embed a certain aspect of mathematics into the core of a proof assistant if that has a significant advantage over defining the same aspect on top of the core. For example, it makes sense to embed dependent types into the core, because implementing dependencies on top of a non-dependent foundation (first-order logic or simple type theory) is a royal pain.

We may therefore rule out approaches such as "first order logic + everything is a category", as that can also be achieved by having just first-order logic in the core, and some general support for defining structures (which we will want anyway).

There is a taunting possibility though. Homotopy type theory is like type theory with built-in higher category theory in which all morphisms are equivalences. This is so because every identification $p : \mathsf{Id}(x,y)$ has an inverse $p^{-1} : \mathsf{Id}(y,x)$ and these two compose to give reflexivity. So, if we could just get rid of the inverses, we would obtain a type theory in which the identity types correspond to category-theoretic $\mathsf{Hom}$-sets. Such a thing is called directed homotopy type theory and is currently being developed by several people. Every year it seems to be a little different, so it's kind of hard to implement it. One could certainly play around with prototypes, and that may inform the theoretical development, but it's a non-trivial amount of work.

$\endgroup$
4
  • $\begingroup$ The "FOL + categories" example is helpful, thank you. It makes intuitive sense to not add something to the core that could easily be supported outside it. $\endgroup$ Commented May 8 at 10:42
  • $\begingroup$ I don’t understand your first two paragraphs. If you replace “category” with “set”, wouldn’t you be saying that Isabelle/ZFC, Metamath/set.mm, and Mizar are just a core of FOL? I’m not sure what “core” means in this case? They are all “FOL + sets”. Maybe it comes down to if OP is looking for a system to do category theory or a system to do all of mathematics but use category theory as the foundation. I assume it is the second. I’m not sure the second one is a “good” approach, but I think it is feasible, no? And “FOL + categories” is one way to do it. Is see no reason to rule it out. $\endgroup$
    – Jason Rute
    Commented May 8 at 10:51
  • 2
    $\begingroup$ If you have bare FOL in the core, then you'll be able to express a first-order theory. If you have FOL + set theory in the core, then you'll be able to express much more, because FOL + set theory is a poorly engineered replacement for simple type theory. If you attempt to have just a core FOL, and then build set theory on top of that, and then use that set theory as the foundation to develop the rest of math, things might get ugly, depending on what else is in the core. In cases where this works, there is good meta-level support in the core. $\endgroup$ Commented May 8 at 11:07
  • $\begingroup$ Regarding "FOL + categories", I suppose that would be some sort of Lawvere-style (such as discussed by McLarty here. Yeah, that could work, alhtough I am personally a fan of dependently typed formalisms, I think they fit more closely the reality of practice. $\endgroup$ Commented May 8 at 11:10

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