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
Update: The type checker is fine. The problem is that I had misread the proof term from the paper. The correct term is:
I can't tell you how happy I am that this actually works!