Curry–Howard correspondence

As Curry - Howard isomorphism (also: Curry - Howard correspondence ) refers to the interpretation of types as logical statements and terms of a particular type of evidence as to the type belonging statement; and vice versa.

Semi - formal description

The concept of truth is replaced with the notion of provability. So you go on intuitionistisches area. A statement is provable if there is a term which has the right to testify type.

Simple connectives

A proof of a conjunction is a pair of evidence for both.

A proof of a disjunction is a term from the disjoint union of and.

Evidence of implications are total functions of the type.

The logical negation is usually an abbreviation for, said under the Curry - Howard isomorphism corresponds to the empty type.

Quantifiers

A universally quantified statement is to a function where the type of the function value from the value of the function argument depends. So here you will encounter dependent types.

The evidence from an existentially quantified statement must provide two things: one element, and a proof for.

Proof example

The law of excluded middle in constructive logic calculi usually does not ( he would apply every statement would be decidable, which entails either express weakness or inconsistency by itself ). A version with double negation below the Allquantisierung about statements, however, can prove by giving a proof term. Is sought for any statements, evidence of

What is meant by Curry Howard and with resolution of negation abbreviation term of the type

Will. The lambda expression

Represents an expression of the desired type, and the injections are in the two-digit sum type.

Practical Applications

Available and usable proof assistants / programming languages ​​such as Coq, Epigram and Agda make the Curry Howard isomorphism use by allowing it to provide evidence as programs, and statements as types. The type checker takes over the task to verify the evidence given.

Swell

• Simon Thompson: Type Theory and Functional Programming ( PDF, 1.3 MB)
• Bengt Nordström, Kent Petersson, Jan M. Smith, Programming in Martin- Löf 's Type Theory (PDF, 709 kB)

• Type theory