Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
I started reworking a quasi-periodic study of mine on propositions as types that introduces the factors of "proof hints" and "untyped terms" into the analogy.
Update . This material is now at propositions as types in combinatory algebra.
By popular request, I've changed the name to propositions as types done right.
I have followed Toby's suggestion and put my excursus (foiled again) at propositions as types in combinatory algebra. I put Toby's intro at propositions as types in type theory as the software kept sending propositions as types to the original article even after I deleted the redirects. I don't know how folks here like to handle disambiguation pages. I sort of liked Toby's use of "in {your sub*subject here}" instead of parenthetical subcategorizers, so long as it works grammatically.
I left the redirect from propositions as types done right in order to preserve several links from the cafe and forum.
By the way, how do you put invisible comments in an article here?
I just noticed that propositions as types goes to Toby's edition of the article while propositions as types done right still goes to my old version.
Is this a glitch? — or just something that feathers through after a few propagation cycles?
If the links don't update correctly, that could indicate that a cached page needs clearing. If you list which pages have incorrect links, we can delete the cached copies of those and see if that fixes things.
You can't put invisible comments in an article on the n-lab - or at least you shouldn't be able to. That's a wide-open door for spammers.
So far I've noticed only the above two links.
It's the redirect cache bug again. I cleared the caches.
added to propositions as types the following (check, needs syntax polishing, but have to run now)
Moreover, in homotopy type theory where types may be thought of as ∞-groupoids (or rather ∞-stacks, more generally), we may think for $A$ any type of
the objects of $A$ are proofs of some proposition;
the morphisms of $A$ are equivalences between these proofs;
the 2-morphisms of $A$ are equivalences between these equivalences, and so on.
So in terms of the notion of n-connected and n-truncated objects in an (∞,1)-category we have
if $A$ is (-1)-connected then the corresponding proposition has a proof and hence is true;
if $A$ is (-2)-truncated then the corresponding proposition is true by a unique proof which is uniquely equivalent to itself, etc.;
if $A$ is 0-truncated then there may be more than one proof, but none equivalent to itself in an interesting way;
if $A$ is 1-truncated then there may be proofs of the corresponding proposition that are equivalent to themselves in interesting ways.
Homotopy type theory doesn’t really have propositions as types; the $(-1)$-truncated types may be distinguished as the propositions per se (much as the subsingletons in set theory or the subterminal objects in topos theory). In contrast, no such distinction is made in Martin–Löf type theory (which has less structure than HoTT), which is why Martin–Löf has PaT.
However, this page is our page on the Curry–Howard correspondence, so your remarks are not out of place. I’ve just rearranged things a bit.
Okay, thanks.
It’s a shame that the phrase “propositions as types” is generally taken to include the converse “types as propositions”. The naive English interpretation of “propositions as types” for me would be that propositions are types, but not necessarily that all types are propositions. I added some remarks about “propositions as some types” – it would be good to add a reference to Awodey-Bauer “Propositions as [types]”.
That’s a good point, Mike. Maybe that’s how the phrase should really be read. I take it to mean the identification of propositions with generic examples of the more general concept (types, sets, spaces, whatever), since I see it as obvious that propositions can be identified with specific examples (subsingletons), at least where equality is available. But in logic (rather than in mathematics), this is not obvious, and not even true if one has more logical operators than type constructors.
Have added some historical info at propositions as types – References – History that was thrown around on the HoTT mailing list
Edited and polished a tad more at propositions as types. Added a pointer to section 1.11 in the HoTT book. But the entry could still be improved a good bit, I suppose.
added a couple of textbook pointers:
Simon Thompson, Type Theory and Functional Programming, Addison-Wesley (1991) [ISBN:0-201-41667-0, webpage, pdf, ISBN:9780444520777]
Morten Heine Sørensen, Pawel Urzyczyn, Lectures on the Curry-Howard isomorphism, Studies in Logic 149 (2006) [ISBN:9780444520777, pdf]
added pointer to:
added pointer to:
added pointer to:
added pointer to:
1 to 19 of 19