RealizabilityRealizability is a part of proof theory which can be used to handle information about formulas instead of about the proofs of formulas.[1] A natural number n is said to realize a statement in the language of arithmetic of natural numbers. Other logical and mathematical statements are also realizable, providing a method for interpreting well formed formulas without resorting to proofs for arriving at those formulas.
[] OriginsKleene introduced the concept of realizability in 1945 in the hopes of it being a faithful mirror of intuitionistic reasoning,[2] but this conjecture was first disproved by Rose with his example of realizable propositional formulas that are unprovable in intuitionist calculus.[3] Realizability appears to defy axiomatization due to its complexity, but it may be approachable through a higher-order Heyting arithmetic (HA). For HA3, a completeness property for the category of modest sets may be proved from the axioms which characterize the realizability of HA3.[4] [] Later developmentsThe modified realizability[5] uses typed lambda calculus as the language of realizers. Modified realizability is one way to show that Markov's principle is not derivable in intuitionistic logic. On the contrary, it allows to constructively justify the principle of independence of premisses: Relative realizability[6] is an intuitionist analysis of recursive or recursively enumerable elements of data structures that are not necessarily computable, such as computable operations on all real numbers when reals can be only approximated on digital computer systems. [] Applications in computer scienceModified realizability justifies the process of program extraction implemented in some proof assistants such as Coq. [] References
[] NotesRealizability is a part of proof theory which can be used to handle information about formulas instead of about the proofs of formulas.[1] A natural number n is said to realize a statement in the language of arithmetic of natural numbers. Other logical and mathematical statements are also realizable, providing a method for interpreting well formed formulas without resorting to proofs for arriving at those formulas.
[] OriginsKleene introduced the concept of realizability in 1945 in the hopes of it being a faithful mirror of intuitionistic reasoning,[2] but this conjecture was first disproved by Rose with his example of realizable propositional formulas that are unprovable in intuitionist calculus.[3] Realizability appears to defy axiomatization due to its complexity, but it may be approachable through a higher-order Heyting arithmetic (HA). For HA3, a completeness property for the category of modest sets may be proved from the axioms which characterize the realizability of HA3.[4] [] Later developmentsThe modified realizability[5] uses typed lambda calculus as the language of realizers. Modified realizability is one way to show that Markov's principle is not derivable in intuitionistic logic. On the contrary, it allows to constructively justify the principle of independence of premisses: Relative realizability[6] is an intuitionist analysis of recursive or recursively enumerable elements of data structures that are not necessarily computable, such as computable operations on all real numbers when reals can be only approximated on digital computer systems. [] Applications in computer scienceModified realizability justifies the process of program extraction implemented in some proof assistants such as Coq. [] References
[] Notes |
.