15
$\begingroup$

In chapter 1 and Appendix A of the Hott book, several primitive type families are presented (universe types, dependent function types, dependent pair types, Coproduct types, Empty Type, Unit type, natural number type, and identity types) to form the foundation for Homotopy Type Theory.

However it seems that given universe types, and dependent function types you can construct all these other "primitive" types. For instance the Empty type could instead be defined as

ΠT:U.T

I assume the other types could also be constructed similar to how they are in pure CC, (ie just derive the type from the inductive part of the definition).

Many of these types are explicitly made redundant by the Inductive/W types that are introduced in chapters 5 and 6. But Inductive/W types appear to be an optional part of the theory since there are open questions on how they interact with HoTT (at least at the time the book came out).

So I am very confused about why these additional types are presented as primitive. My intuition is that a foundational theory should be as minimal as possible, and redefining a redundant Empty type as a primitive into the theory seems very arbitrary.

Was this choice made

  • for some some metatheoretic reasons that I am unaware of?
  • for historical reasons, to make the type theory look like past type theories (which were not necessarily trying to be foundational)?
  • for "usability" of computer interfaces?
  • for some advantage in proof search that I am unaware of?

Similar to: Minimal specification of Martin-Löf type theory , https://cs.stackexchange.com/questions/82810/reducing-products-in-hott-to-church-scott-encodings/82891#82891

$\endgroup$
  • $\begingroup$ They are redundant, but not in the way you're suggesting. You should ask yourself what purpose does "minimality of foundation" serve? And do we care about the purpose? $\endgroup$ – Andrej Bauer Dec 16 '17 at 18:09
  • 1
    $\begingroup$ I assume technical work is minimal by convention, where things don't need to be minimal if it is obviously convenient or explicitly noted otherwise. The book even adheres to this in other places, like when it defines truncation types (defined by rules, but explicitly not minimal). For example if I saw the nats defined in terms of 0,1,10, the successor and the power operation, I would be confused, but I could at least see why it is notationally convenient. Hott is a much more complex area of study and I want to know if I am missing anything obvious. $\endgroup$ – user833970 Dec 16 '17 at 19:43
  • 1
    $\begingroup$ I would be very interested in hearing about how they can be harmful. Should I make a new question about that? $\endgroup$ – user833970 Dec 17 '17 at 18:39
  • 1
    $\begingroup$ @AndrejBauer I'd like to know why they would be harmful, too. My reasoning to believe the foundational language should be minimal is the reasoning behind occam's razor, it is unjustified added complexity. Why stop there? Why not add also lists, strings, pairs, triples, vectors? Those seems arbitrary choices, what justifies them? Edit: I just noticed this question has answers; but I'll leave this comment here just for the sake of noting why I'd be interested in that too. $\endgroup$ – MaiaVictor Dec 21 '17 at 6:05
  • 1
    $\begingroup$ I'll write a blog post. $\endgroup$ – Andrej Bauer Dec 21 '17 at 20:41
14
$\begingroup$

Let me explain why the suggested encoding of the empty type does not work. We need to be explicit about universe levels and not sweep them under the rug.

When people say "the empty type", they might mean one of two things:

  1. A single type $E$ which is empty with respect to all types. Such a type has the elimination rule: for every $n$ and type family $A : E \to U_n$, there is a map $e_{n,A} : E \to A$.

  2. A family of types $E_k$, one for each universe level $k$, such that $E_k$ is "the empty type of $U_k$". Such a type has to satisfy $E_k : U_k$, obviously, and also: for every type family $A : E_{k} \to U_k$, there is a map $e_{k,A} : E_{k} \to A$.

Without any provisos, when people say "empty type" they expect the first meaning above.

How can we get $E$? A first try could be something like $$E = \Pi (T : U) \,.\, T$$ but this is precisely the sort of sweeping under the rug that creates confusion. We must write down explicit universe levels. If we write something like $$E_k = \Pi (T : U_k) \,.\, T$$ then we get a sequence of types $E_0, E_1, E_2, \ldots$, one for each level $k$. We might hope that this sequence is the empty type in the sense above, but it is not, because $E_k$ is in $U_{k+1}$ but it is supposed to be in $U_k$.

Another try is $$E = \Pi n \,.\,\Pi (T : U_{n}) \,.\, T$$ but now you have to explain what "$\Pi n$" is supposed to be. You might be tempted to say that there is a type $L$ of universe levels, and so $$E = \Pi (n : L) \,.\,\Pi (T : U_{n}) \,.\, T$$ You have now fallen into a trap, because I will ask: in which universe does $E$ live? And in which universe does $L$ live? This is not going to work.

There is a solution, known as impredicative universe. This is a magical universe $U$ which has the property that, given $B : U \to U$, the type $\Pi (X : U) B(X)$ lives in $U$ (and not one level up from $U$). Then at least $\Pi (X : U) X$ is again in $U$, and will have the expected eliminator. But we are still not done, as now we have to worry about equations for the eliminator, as was pointed out by Neel.

Impredicative universes can be arranged. However, a famous theorem of Thierry Coquand (if I am not mistaken), shows that having two impredicative universes, one contained in the other, leads to a contradiction.

The moral of the story is: just axiomatize the empty type directly and stop encoding things.

$\endgroup$
  • $\begingroup$ That is a convincing reasoning to axiomatize the empty type, but I'm still curious about the reasoning to axiomatize all those heavier things. $\endgroup$ – MaiaVictor Dec 21 '17 at 6:10
  • $\begingroup$ @MaiaVictor: as opposed to what? $\endgroup$ – Andrej Bauer Dec 21 '17 at 20:40
  • $\begingroup$ Sorry? I just mean you convincingly justified why it is a good idea to axiomatize the empty type in particular. But OP also asked about other things: "universe types, dependent function types, dependent pair types, Coproduct types, Empty Type, Unit type, natural number type, and identity types" (which I assume are also primitives on the system proposed on the HoTT book). (I'm obviously not asking you to justify those all, just manifesting my interest.) $\endgroup$ – MaiaVictor Dec 21 '17 at 22:22
  • $\begingroup$ @MaiaVictor: The story with the other types is very similar. For instance, the unit type looks a bit like it could be encoded as $\mathbb{1} = \prod_{X : U} (X \to X)$; however problems arise as soon as one tries to be more precise with that definition. $\endgroup$ – Ingo Blechschmidt Sep 24 '18 at 18:53
  • $\begingroup$ @IngoBlechschmidt curious to learn what kinds of problems! It looks good to me... $\endgroup$ – MaiaVictor Sep 24 '18 at 20:44
15
$\begingroup$

You are asking several questions which are similar but distinct.

  1. Why doesn't the HoTT book use Church encodings for data types?

    Church encodings do not work in Martin-Löf type theory, for two reasons.

    First, MLTT is predicative. There is a universe hierarchy, and each type lives at a particular universe level, and a type at level $n$ can only quantify over types at smaller universe levels $k < n$. Church encodings like in System F or the CoC require impredicative quantification, where you can instantiate quantifiers with types which are the same size, or even bigger.

    Second, even if you defined datatypes like the natural numbers with Church encodings, to do proofs with these types, you need induction principles to prove things about them. To derive induction principles for Church encodings, you need to use an argument based on Reynolds' parametricity, and the question of how to internalize parametricity principles into type theory is still not fully settled. (The state of the art is Nuyts, Vezzosi, and Devriese's ICFP 2017 paper Parametric Quantifiers for Dependent Type Theory -- note that this is well after the HoTT book was written!)

  2. Next, you are asking why the foundation is not minimal. This is actually one of the distinctive sociological features of type-theoretic foundations -- type theorists regard having a small set of rules as a technical convenience, without much foundational significance. It's far, far more important to have the right set of rules, rather than the smallest set of rules.

    We develop type theories to be used by mathematicians and programmers, and it's very, very important that the proofs done within type theory are the ones that mathematicians and programmers regard as being done in the right way. This is because the arguments mathematicians typically regard as having good style typically are structured using the key algebraic and geometrical principles of the domain of study. If you have to use complicated encodings then much structure is lost or obscured.

    This is why even type-theoretic presentations of propositional classical logic invariably give all the logical connectives, even though it is formally equivalent to a logic with just NAND. Sure, all the boolean connectives can be encoded with NAND, but that encoding obscures the structure of the logic.

$\endgroup$
  • $\begingroup$ Thanks for this answer! I'll need to read that paper (and yours) and it might make more sense. But, I thought the universe hierarchy was designed to make it look like you can do predicative things: for instance (λA:U.λa:A.a)(ΠA:U.A→A) would desugar to (λA:Un+1.λa:A.a)(ΠA:Un.A→A). I do think that it is a strange editorial choice not to explain this, every logic book I know points out several more minimal encoding like CNF, DNF, NAND and so on. And anyone who is used to set theory expects a "natural" encoding of the Nats, to demonstrate the theory. But that may just be my classical biases. $\endgroup$ – user833970 Dec 15 '17 at 13:09
  • $\begingroup$ that should be "impredicative" in my last comment $\endgroup$ – user833970 Dec 15 '17 at 13:28
  • $\begingroup$ CNF, DNF, NAND and so on are irrelevant in this context, as they are about a tiny subset of logic, namely the Boolean part. They are useless in type theory (which isn't logic). As for your encodings, they won't work because they land in a universe one higher than we want it, and also they don't have the correct elimnation properties. The type $\prod (T : U_n) . T$ is "empty" only as far as $U_n$ is concerned (what do other universes think about it?), and it lands in $U_{n+1}$ instead of $U_n$. $\endgroup$ – Andrej Bauer Dec 16 '17 at 18:06
  • $\begingroup$ Perhaps I am misunderstanding something about universe hierarchies. I thought that we never care which specific Universe a type is in, only that the universe numbers can be assigned when we want to verify a proof. So technically ΠT:U.T is a family of types indexed over universes. Just like the polymorphic identity is a family of types indexed over universes. But don't we have the same problem with the polymorphic identity? I'd really appreciate it if you could expand on the last 2 sentences, I don't think I understand. $\endgroup$ – user833970 Dec 16 '17 at 21:28
  • $\begingroup$ When you say that it doesn't have the right elimination properties do you mean that once the universe is fixed there are types in higher universes that cannot be directly synthesized by a term of ΠT:Un.T? $\endgroup$ – user833970 Dec 16 '17 at 21:32

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.