In any interesting logic, there are propositions which are true but not provable. The same goes for intuitionistic logic. By the Curry-Howard correspondence, there are types for which neither the types themselves nor their negations are inhabited in the typed lambda calculus. An example of this is Peirce's law:
∀ p, q . ((p -> q) -> p) -> p. We can use Heyting algebra to show that Peirce's law is not provable in intuitionistic logic. According to John C. Mitchell's Foundations for Programming Languages, problem 4.3.16, we could also show that this is not provable because:
. . . if there us a closed lambda term M:((a -> b) -> a) -> a then there is a closed normal form (the normal form of M) of this type. Show that this implicational formula is not provable by showing there is no closed normal form term of this type.
∀ a, b, c, d . Equal (a,b) (c,d) -> Equal a cwhere type equality is defined by Leibniz equality
data Equal a b = Equal (∀ f . f a -> f b)To avoid dealing with datatypes or pairs, this can be expanded to
∀ a, b, c, d . (∀ f . f (∀ r . (a -> b -> r) -> r) -> f (∀ s . (c -> d -> s) -> s)) -> (∀ g . g a -> g c)In GADTless Programming in Haskell 98 (Section 6, top of page 13) Martin Sulzmann and Meng Wang call this the decomposition law.
Is there some Heyting algebra for higher-order polymorphic typed lambda calculi that we can use to show that this type is uninhabited?