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 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?
6 comments:
I don't know what that means!!
No, seriously, I don't know what that means. I hate my life.
Could you please write about kittens or balloons so I can read your blog?
Sincerely,
Grover
You should start an architecture blog, and then I'll leave the exact same comment. :-)
Anyway, here's my attempt:
"In any interesting kitten, there are balloons which are true but not kittens. The same goes for balloon animals. By the Three Stooges correspondence, there are pretty, pretty flowers for which neither the kittens themselves nor their owners are rhyming in the typed balloon-animal calculus …"
Got it, thanks!
Post a Comment