Girard's paradox

Hi folks, this might be of interest to anyone who is designing a language with dependent types. I stumbled upon this question from a couple years ago about Girard's paradox. If you haven't heard of Girard's paradox, it's the reason you don't want Type : Type if you want your language to be consistent for writing proofs. Note that Type : Type doesn't break soundness (i.e., type safety), which means it's fine if you don't care about proofs. It just means you can construct a non-normalizing term (i.e., an infinite loop), which most languages will happily let you do anyway regardless of the type system.

The comments in that thread seem to reveal some misconceptions about the nature of the paradox, which made me want to get my hands dirty and play around with it. So I read through the literature, deciphered the menagerie of inscrutable symbols, and managed to construct the paradox in Coq (a language with dependent types). Of course, since Coq is intended to be consistent, it rejects the paradox unless you collapse the universe hierarchy into Type : Type, which I've done on the first line by disabling universe consistency checking. Anyway, here it is in all its glory:

#[local] Unset Universe Checking.

Definition exfalso := forall (p : Type), p.
Definition negate := fun (phi : Type) => phi -> exfalso.
Definition power := fun (S : Type) => S -> Type.
Definition universe :=
  forall (X : Type),
    ((power (power X) -> X) -> power (power X)).
Definition tau :=
  fun (t : power (power universe)) =>
    fun (X : Type) =>
      fun (f : power (power X) -> X) =>
        fun (p : power X) =>
          t (fun (x : universe) => p (f (x X f))).
Definition sigma :=
  fun (s : universe) =>
    s universe (fun (t : power (power universe)) => tau t).
Definition delta :=
  fun (y : universe) =>
    negate (forall (p : power universe), sigma y p -> p (tau (sigma y))).
Definition omega :=
  tau (fun (p : power universe) => forall (x : universe), sigma x p -> p x).

Definition bad := (
  fun (
    zero :
      forall (p : power universe),
        (forall (x : universe), sigma x p -> p x) -> p omega
  ) => (
    zero delta (
      fun (x : universe) =>
        fun (two : sigma x delta) =>
          fun (
            three :
              forall (p : power universe), sigma x p -> p (tau (sigma x))
          ) => three delta two (
            fun (p : power universe) =>
              three (fun (y : universe) => p (tau (sigma y)))
          )
    )
  ) (
    fun (p : power universe) => zero (fun (y : universe) => p (tau (sigma y)))
  )
) (
  fun (p : power universe) =>
    fun (one : forall (x : universe), sigma x p -> p x) =>
      one omega (fun (x : universe) => one (tau (sigma x)))
).

Check bad. (* exfalso *)

This is very difficult to understand, so don't worry if it looks like gibberish to you. You can read the paper if you really want to grok it. The good news is that all the hard work is done for you—you don't have to figure out how it works. You just have to know that it exists and decide what your language is going to do about it.

If you're building a dependently typed language, try translating this into your language and seeing what happens. It's a good stress test for your type checker and interpreter/compiler.

Edit: Fixed a typo.

Posted Mar 19, 2022, 4:55 AM UTC · edited

2413
Loading comments…