19
$\begingroup$

Normally in a type theory, you can not have a type of all types, due to Girad's paradox. This is somewhat similar to how in set theory, you cannot have a set of all sets.

Therefore, usually you just have a type of types that have types, which itself has no type (Calculus of Construction as defined here), or you just define an infinite tower of types, such that every type is of the type of something in that tower (a.k.a. a tower of universes).

These two solutions are analogous to the set-theoretic notions of a class of all sets and the Von Neumann hierarchy.

In set theory, there is actually a third solution: the New Foundations (and its relatives). In it, there is in fact a set of all sets.

My question is, can you similarly have a type theory in which there is a type of all types, possibly using similar techniques as those of New Foundations. You obviously can not just "transfer over" the axioms of New Foundations, since set theory and type theory are quite different, but maybe you can use similar axioms.

One direction I was thinking about it somehow extending universe polymorphism. For example, in Coq "Type : Type" is valid. But that doesn't mean Type is of type Type. Rather, there is actually a type Type$_n$ for each $n$, and Coq automatically tries to assign a $n$ to each occurrence of "Type" in the code. If you tried to formalize Girard's paradox in Coq, this assignment would fail. This is rather similar to the idea of stratified formulas in NF. Perhaps we could say that Type is a member of Type, but in any formula involving Type, there must be a way to "stratify" the formula, or something like that.

Another possibility would be to establish to have a hierarchy of universes, but declare them all to be isomorphic (although this would make the theory incompatible with the univalence axiom).

$\endgroup$
18
$\begingroup$

Of course you can have $\mathsf{Type} : \mathsf{Type}$, the consequence of that is that all types are inhabited (by Girard's paradox). Some people call this an inconsistency, but that only makes sense if you view terms as proofs and types as logical statements.

In other contexts, for instance when we think of terms as programs, there is nothing wrong with all types being inhabited. After all, in a general-purpose programming language all types are inhabited, thanks to recursion. In fact, if we lean towards programming, $\mathsf{Type} : \mathsf{Type}$ will be desirable because it will say that there is a datatype of all datatypes. There will be no end to Haskell-style hackage after that.

There are very nice domain-theoretic models of $\mathsf{Type} : \mathsf{Type}$. For example, we can take countably-based algebraic lattices and continuous maps. Then every such lattice embeds as a retract into $\mathcal{P}(\omega)$, which means that $\mathcal{P}(\omega)$ is a universal lattice. It plays the role of $\mathsf{Type}$. But what is even cooler is that the (algebraic) retracts of $\mathcal{P}(\omega)$ themselves form a countably based algebraic lattice, and this gives us $\mathsf{Type} : \mathsf{Type}$.

$\endgroup$
  • 1
    $\begingroup$ I would love to hear from the person that -1 this answer. I am curious to see if some sort of ideology about type theory was at work, or was it something else? $\endgroup$ – Andrej Bauer Sep 6 '17 at 21:00
  • 4
    $\begingroup$ It was me. As for all of your answers I think it was interesting and well-written, but in this case I think it side-steps the intent of the question entirely: I believe that the true content of the question was: "are there type theories that have comparable logical strength, and are similar in feel, to New Foundations?" In particular, this would require them to be consistent (unless New Foundations is inconsistent!) and have some notion of "stratified comprehension" like in NF. For other set theoretical foundations one can argue that there are type theories that are similar in feel and... $\endgroup$ – cody Sep 7 '17 at 14:23
  • 2
    $\begingroup$ ... strength, like Martin--Löf type theory for (certain versions of) K-P set theory, and CoC for Zermelo set theory. While I think that domain models for $\mathrm{Type}:\mathrm{Type}$ are very interesting, I don't think they capture the spirit of these examples. In particular, that type theory is essentially useless for foundational considerations, whereas NF seems to be somewhat interesting from that point of view. $\endgroup$ – cody Sep 7 '17 at 14:29
  • 1
    $\begingroup$ Thank you for clarifying, point taken. I was afraid it came from one of those "propositions-as-types-or-die" fanatics that roam around Europe. $\endgroup$ – Andrej Bauer Sep 7 '17 at 20:57
  • 4
    $\begingroup$ New Foundations is inspired by a type theory, the simple theory of types $\mathsf{TST}$. Randall's many drafts of his claimed proof have some motivation and references for this theory, and discuss some of its history (together with the appropriate variants his proof requires). See for instance here. $\endgroup$ – Andrés E. Caicedo Sep 16 '17 at 22:11

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.