Re:Type Systems (2004) [pdf]
by adamnemecek on Thursday August 31, 2017 @02:05PM
(#15142373)
Constructive mathematics is based on intuitionistic logic (i.e. classical logic without law of the excluded middle, meaning you don't have proof by contradiction, to demonstrate the existence of something you have to "construct" it).
Intuitionistic logic is very close to type theory.
[ Parent
| on HN ]
Re:Type Systems (2004) [pdf]
by AnimalMuppet on Thursday August 31, 2017 @03:05PM
(#15142874)
OK, ELI10: Why or how is intuitionistic logic very close to type theory? Is it based on type theory? Or is it just similar? In either case, how and why?
See https://codewords.recurse.com/issues/one/type-systems-and-lo... for a pretty elaborate response to this question.
tl;dr: types are propositions and values are proofs of those propositions. Constructive logic is not concerned with (true xor false), but rather "I can prove A" or "I can prove not-A". There's also the middle ground of "I don't know how to prove anything about A".
Re:Type Systems (2004) [pdf]
by adamnemecek on Thursday August 31, 2017 @03:31PM
(#15143153)
Good ol' Curry-Howard isomorphism.
https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
But the connections don't really end there.