Propositional equality, identity types, and direct computational paths

Details Propositional equality, identity types, and direct computational paths Propositional equality, identity types, and direct computational paths

2011-07-10

arxiv.org/abs/1107.1901v2

Computer Science

Logic in Computer Science

37 pages, submitted to TCS

Scientific paper

In proof theory the notion of canonical proof is rather basic, and it is usually taken for granted that a canonical proof of a sentence must be unique up to certain minor syntactical details (such as, e.g., change of bound variables). When setting up a proof theory for equality one is faced with a rather unexpected situation where there may not be a unique canonical proof of an equality statement. Indeed, in a (1994--5) proposal for the formalisation of proofs of propositional equality in the Curry--Howard style, we have already uncovered such a peculiarity. Totally independently, and in a different setting, Hofmann & Streicher (1994) have shown how to build a model of Martin-L\"of's Type Theory in which uniqueness of canonical proofs of identity types does not hold. The intention here is to show that, by considering as sequences of rewrites and substitution, it comes a rather natural fact that two (or more) distinct proofs may be yet canonical and are none to be preferred over one another. By looking at proofs of equality as rewriting (or computational) paths this approach will be in line with the recently proposed connections between type theory and homotopy theory via identity types, since elements of identity types will be, concretely, paths (or homotopies).

Affiliated with

Also associated with

No associations

Rating

Propositional equality, identity types, and direct computational paths does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Propositional equality, identity types, and direct computational paths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Propositional equality, identity types, and direct computational paths will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-137023