Showing posts with label Heyting algebra. Show all posts
Showing posts with label Heyting algebra. Show all posts

Friday, November 9, 2007

Lectures on the Curry-Howard Isomorphism saves the day

Morten Heine B. Sørensen and Pawel Urzyczyn's Lectures on the Curry-Howard Isomorphism (mirror 1, mirror 2, errata) provides answers to two questions I asked here before:

I speculated about a complexity problem and its relation to types. On page 104 of LotCHI (92, in print), the authors note that, in the simply-typed lambda calculus, a reduction of the type inhabitation problem to the type checking problem would show that P = PSPACE.

I also wondered if there was a Heyting algebra for higher-order polymorphic typed lambda calculi that we can use to show that some type is uninhabited. LotCHI section 12.2 gets part of the way there (The authors cover F2, I would need F3, I think.), with the answer that yes, there is such an algebra, but no, it doesn't make things so easy.

Wednesday, August 22, 2007

Leibniz Equality, Decomposition, and Definability

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.

In Emir Pasalic's PhD thesis, (end of section 4.2.2, page 80 in the PDF, 70 in print), he mentions that it is unknown whether the following type is inhabited:

∀ a, b, c, d . Equal (a,b) (c,d) -> Equal a c
where 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?