Revision #4805 → #4806 · back to history
modifiedCurry–Howard correspondence (overview)a7680aed9697
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"(Lead)","snippet":"a direct relationship between computer programs and mathematical proofs"},"resolution":"not_attempted"}}] |
modifiedCurry's 1934 observation (combinator types as axiom-schemes)6d2d1779e0e9
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Origin, scope, and consequences","snippet":"the types of the combinators could be seen as axiom-schemes for intuitionistic implicational logic"},"resolution":"not_attempted"}}] |
modifiedCurry's 1958 observation (Hilbert-style deduction ~ combinatory logic)ec638bfec454
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Origin, scope, and consequences","snippet":"coincides on some fragment with the typed fragment of a standard model of computation known as combinatory logic"},"resolution":"not_attempted"}}] |
modifiedHoward's 1969 observation (natural deduction ~ lambda calculus)9fd230a78524
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Origin, scope, and consequences","snippet":"can be directly interpreted in its intuitionistic version as a typed variant of the model of computation known as lambda calculus"},"resolution":"not_attempted"}}] |
modifiedCurry–Howard slogan: proofs as programs, formulas as types3d0c781c6cc4
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Origin, scope, and consequences","snippet":"a proof is a program, and the formula it proves is the type for the program"},"resolution":"not_attempted"}}] |
modifiedFormulas-as-types correspondence tablecce1eed9a25a
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"General formulation","snippet":"implication behaves the same as a function type"},"resolution":"not_attempted"}}] |
modifiedCurry's correspondence for axioms K and Sa0a8dba43135
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intuitionistic Hilbert-style deduction systems and typed combinatory logic","snippet":"the simplest types for the basic combinators K and S of combinatory logic surprisingly corresponded to the respective axiom schemes"},"resolution":"not_attempted"}}] |
modifiedHilbert-style derivability (Γ ⊢ δ)e267e38a22ff
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intuitionistic Hilbert-style deduction systems and typed combinatory logic","snippet":"Let Γ be a finite collection of formulas, considered as hypotheses"},"resolution":"not_attempted"}}] |
modifiedTyped combinatory logic typing judgment2df37befb95f
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intuitionistic Hilbert-style deduction systems and typed combinatory logic","snippet":"let Γ be a finite collection of variables, annotated with their types"},"resolution":"not_attempted"}}] |
modifiedPeirce's law excluded from intuitionistic correspondencec562463017be
| Field | From #4805 | To #4806 |
|---|
| links | — | [{"id":"c562463017be:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intuitionistic Hilbert-style deduction systems and typed combinatory logic","snippet":"some classical tautologies , such as Peirce's law"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"peirce","module":"Mathlib.Logic.Basic"}}]}}] |
| unlinked | — | [] |
modifiedNo combinator typable with Peirce's law typede25b2faa5aa
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intuitionistic Hilbert-style deduction systems and typed combinatory logic","snippet":"there is no typed term of combinatory logic that is typable with type"},"resolution":"not_attempted"}}] |
modifiedCombinator X as one-point basis43b5a4bff911
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intuitionistic Hilbert-style deduction systems and typed combinatory logic","snippet":"the fact that the combinator X constitutes a one-point basis of (extensional) combinatory logic"},"resolution":"not_attempted"}}] |
modifiedHoward's correspondence (natural deduction ~ simply typed lambda calculus)cea2d76897c8
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intuitionistic natural deduction and typed lambda calculus","snippet":"a syntactic analogy between the programs of simply typed lambda calculus and the proofs of natural deduction"},"resolution":"not_attempted"}}] |
modifiedNormal forms correspond to normal deductionsd57cd14d63cd
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Intuitionistic natural deduction and typed lambda calculus","snippet":"the notion of normal forms in lambda calculus matches Prawitz 's notion of normal deduction in natural deduction"},"resolution":"not_attempted"}}] |
modifiedGriffin's extension of Curry–Howard to classical logic1ad09bc95582
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Classical logic and control operators","snippet":"The extension of the correspondence to Peirce's law and hence to classical logic became clear from the work of Griffin"},"resolution":"not_attempted"}}] |
modifiedFiner classical correspondence (multiple conclusions)bb0e9111ed34
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Classical logic and control operators","snippet":"A finer Curry–Howard correspondence exists for classical logic if one defines classical logic not by adding an axiom such as Peirce's law"},"resolution":"not_attempted"}}] |
modifiedProofs-as-programs correspondence for sequent calculus9277650fd4fc
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Sequent calculus","snippet":"A proofs-as-programs correspondence can be settled for the formalism known as Gentzen 's sequent calculus"},"resolution":"not_attempted"}}] |
modifiedPrawitz's homomorphism (natural deduction to construction terms)400e7e836584
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Prawitz's 1968 homomorphism","snippet":"Dag Prawitz defined a homomorphism between natural deduction derivations for minimal and intuitionistic first-order logic and construction terms"},"resolution":"not_attempted"}}] |
modifiedde Bruijn's independent proofs-as-lambda-terms correspondencebb49e02045d0
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"The role of de Bruijn","snippet":"used the lambda notation for representing proofs of the theorem checker Automath"},"resolution":"not_attempted"}}] |
modifiedBHK interpretation173b4cc47e40
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"BHK interpretation","snippet":"The BHK interpretation interprets intuitionistic proofs as functions"},"resolution":"not_attempted"}}] |
modifiedKleene's recursive realizability446d5c82b460
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Realizability","snippet":"splits proofs of intuitionistic arithmetic into the pair of a recursive function and of a proof of a formula"},"resolution":"not_attempted"}}] |
modifiedKreisel's modified realizability8fcbe0f99bf3
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Realizability","snippet":"applies to intuitionistic higher-order predicate logic and shows that the simply typed lambda term inductively extracted from the proof realizes the initial formula"},"resolution":"not_attempted"}}] |
modifiedGödel's dialectica interpretation10a868aea2b4
| Field | From #4805 | To #4806 |
|---|
| links | — | [{"id":"10a868aea2b4:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Realizability","snippet":"dialectica interpretation realizes (an extension of) intuitionistic arithmetic with computable functions"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.Dial","module":"Mathlib.CategoryTheory.Dialectica.Basic"}}]}}] |
| unlinked | — | [] |
modifiedLambek's theorem (CCC equational theory)dee7a59ffb01
| Field | From #4805 | To #4806 |
|---|
| links | — | [{"id":"dee7a59ffb01:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Curry–Howard–Lambek correspondence","snippet":"the proofs of intuitionistic propositional logic and the combinators of typed combinatory logic share a common equational theory"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.MonoidalClosed","module":"Mathlib.CategoryTheory.Monoidal.Closed.Basic"}}]}}] |
| unlinked | — | [] |
modifiedCartesian closed category objects (propositions/types)89fbc520c345
| Field | From #4805 | To #4806 |
|---|
| links | — | [{"id":"89fbc520c345:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Curry–Howard–Lambek correspondence","snippet":"Objects (propositions/types) include"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.CartesianMonoidalCategory","module":"Mathlib.CategoryTheory.Monoidal.Cartesian.Basic"}}]}}] |
| match_kind | — | exact |
| unlinked | — | [] |
modifiedCartesian closed category morphisms (deductions/terms)5bf60e21e742
| Field | From #4805 | To #4806 |
|---|
| links | — | [{"id":"5bf60e21e742:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Curry–Howard–Lambek correspondence","snippet":"Morphisms (deductions/terms) include"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.MonoidalClosed.curry","module":"Mathlib.CategoryTheory.Monoidal.Closed.Basic"}}]}}] |
| match_kind | — | generalization |
| unlinked | — | [] |
modifiedCurry–Howard–Lambek iff (term exists iff provable)ceb8f7c012f1
| Field | From #4805 | To #4806 |
|---|
| links | — | [{"id":"ceb8f7c012f1:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Curry–Howard–Lambek correspondence","snippet":"Now, there exists t such that"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.MonoidalClosed.curry","module":"Mathlib.CategoryTheory.Monoidal.Closed.Basic"}}]}}] |
| unlinked | — | [] |
modifiedIdentity combinator as proof of α → α6ceebe8e47fd
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"The identity combinator seen as a proof of α → α in Hilbert-style logic","snippet":"As an example, consider a proof of the theorem"},"resolution":"not_attempted"}}] |
modifiedComposition combinator (B) as proof of (β→α)→(γ→β)→γ→α2fa120f585e0
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"The composition combinator seen as a proof of ( β → α ) → ( γ → β ) → γ → α in Hilbert-style logic","snippet":"let's look at the theorem that corresponds to the B function"},"resolution":"not_attempted"}}] |
modifiedNatural deduction proof of (β→α)→(γ→β)→γ→α as a λ-termff9c9fa4436c
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"The normal proof of ( β → α ) → ( γ → β ) → γ → α in natural deduction seen as a λ -term","snippet":"The diagram below gives proof of"},"resolution":"not_attempted"}}] |
modifiedCCCs generalized by closed monoidal categories501a3abc5d26
| Field | From #4805 | To #4806 |
|---|
| links | — | [{"id":"501a3abc5d26:link:0","annotation":{"subject":[{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Generalizations","snippet":"cartesian closed categories are generalized by closed monoidal categories"},"resolution":"not_attempted"}}],"object":[{"type":"lean","uri":"https://github.com/leanprover-community/mathlib4","location":{"declaration":"CategoryTheory.MonoidalClosed","module":"Mathlib.CategoryTheory.Monoidal.Closed.Basic"}}]}}] |
| match_kind | — | generalization |
| unlinked | — | [] |
modifiedCorrespondence to cobordisms4637862bf7fe
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Generalizations","snippet":"these can be shown to correspond to cobordisms"},"resolution":"not_attempted"}}] |
modifiedUnivalence axiome9fa084765dc
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Generalizations","snippet":"type theory is extended by the univalence axiom"},"resolution":"not_attempted"}}] |
modifiedHomotopy type theory generalization (proofs as paths)016dbbb0f517
| Field | From #4805 | To #4806 |
|---|
| links | — | [] |
| unlinked | — | [{"type":"html","uri":"https://en.wikipedia.org/w/index.php?title=Curry%E2%80%93Howard_correspondence&oldid=1373154084","location":{"profile":"urn:wikilean:anchor:v3","anchor":{"section":"Generalizations","snippet":"the Curry–Howard correspondence that proofs are elements of inhabited types is generalized to the notion of homotopic equivalence of proofs"},"resolution":"not_attempted"}}] |