Trouble type checking Girard's paradox?

Hi folks, I'm working on a small dependently-typed programming language with Type : Type. Of course this system is inconsistent as a logic, but it's sound as a type system for programming, and the goal of this language is not theorem proving.

As a stress test of the type checker, I am trying to type check Girard's paradox. I'm using the version of the paradox given in section 3 of the paper A Simplification of Girard's Paradox. The goal is to construct a well-typed program that loops forever without any fixpoint operators or recursive types (e.g., no Y combinator). This is my attempt at translating that rather insidious term into code (warning: nasty lambda calculus ahead!):

false = (p : type) -> p;
negate = (phi : type) => phi -> false;
power = (S : type) => S -> type;
U = (X : type) -> ((power (power X) -> X) -> power (power X));
tau = (t : power (power U)) => (X : type) => (f : power (power X) -> X) =>
      (p : power X) => t ((x : U) => p (f (x X f)));
sigma = (s : U) => s U ((t : power (power U)) => tau t);
Delta = (y : U) => negate ((p : power U) -> sigma y p -> p (tau (sigma y)));
Omega = tau ((p : power U) => (x : U) -> sigma x p -> p x);

# Ok, here we go!
(zero : (p : power U) -> ((x : U) -> sigma x p -> p x) -> p Omega) =>
((zero Delta ((x : U) => (two : sigma x Delta) => (three : (p : power U) -> sigma x p -> p (tau (sigma x))) => (three Delta two) ((p : power U) => three ((y : U) => p (tau (sigma y)))))) ((p : power U) => zero ((y : U) => p (tau (sigma y)))))
((p : power U) => (one : (x : U) -> sigma x p -> p x) => one Omega ((x : U) => one (tau (sigma x))))

Unfortunately, I am having trouble type checking this term. My implementation gives the following:

Error in `examples/girard.g`: This has type `((p : (power U)) -> ((one : (x : U) -> ((sigma x) p) -> (p x)) -> (p (Omega))))` when `type` was expected.

19 | ((p : power U) => (one : (x : U) -> sigma x p -> p x) => one Omega ((x : U) => one (tau (sigma x))))

Yikes...the term is so nasty that I have no idea what to make of this. It must be a bug in my type checker, right? Or perhaps there is an error in the paper? Seems unlikely. But have any of you ever attempted to type check this? Does anyone have experience with this paradox?

The syntax of the language I'm working on is pretty spartan right now (very little syntactic sugar). It looks a lot like Agda or Idris. (x : A) -> B is a pi type, and (x : A) => e is a lambda. The only syntactic sugar is that A -> B is an abbreviation of that pi type, provided x does not occur in B. Happy to clarify anything about the syntax as needed.

Posted Feb 17, 2020, 2:10 AM UTC · edited

264
stepstepOP•

Update: The type checker is fine. The problem is that I had misread the proof term from the paper. The correct term is:

false = (p : type) -> p;
negate = (phi : type) => phi -> false;
power = (S : type) => S -> type;
U = (X : type) -> ((power (power X) -> X) -> power (power X));
tau =
  (t : power (power U)) =>
    (X : type) =>
      (f : power (power X) -> X) =>
        (p : power X) =>
          t ((x : U) => p (f (x X f)));
sigma = (s : U) => s U ((t : power (power U)) => tau t);
Delta = (y : U) => negate ((p : power U) -> sigma y p -> p (tau (sigma y)));
Omega = tau ((p : power U) => (x : U) -> sigma x p -> p x);

(
  (zero : (p : power U) -> ((x : U) -> sigma x p -> p x) -> p Omega) =>
    (
      zero
      Delta
      (
        (x : U) =>
          (two : sigma x Delta) =>
            (three : (p : power U) -> sigma x p -> p (tau (sigma x))) =>
              three Delta two ((p : power U) => three ((y : U) => p (tau (sigma y))))
      )
    )
    ((p : power U) => zero ((y : U) => p (tau (sigma y))))
)
(
  (p : power U) =>
    (one : (x : U) -> sigma x p -> p x) =>
      one Omega ((x : U) => one (tau (sigma x)))
)

I can't tell you how happy I am that this actually works!

8
faiface•

Cool! Can you recommend any resources/tips for actually understanding this paradox? I've been searching for a long while, but nothing's been clicking yet.

4
stepstepOP•

Unfortunately I don't yet have an intuition for the paradox other than my understanding of Russell's paradox from naïve set theory. The paper [1] seems to be well-written, but I've only read through section 3 to get the proof term. The explanation appears to follow in the subsequent sections.

[1] A Simplification of Girard's Paradox

4
faiface•

Ah, thanks anyway! I’ve already tried reading through that paper a couple times, but perhaps I should just give it a few more attempts.

3