Realizability

Realizability is a part of proof theory which can be used to handle information about formulas instead of about the proofs of formulas. [Oosten, pp. 3-5] 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.

Origins

Kleene introduced the concept of realizability in 1945 in the hopes of it being a faithful mirror of intuitionistic reasoning, [Kleene (1945)] but this conjecture was first disproved by Rose with his example of realizable propositional formulas that are unprovable in intuitionist calculus. [Rose] 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. [Oosten, p. 20]

Later developments

The modified realizability [Kreisel] 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: $(\; eg\; A\; ightarrow\; exists\; x;P(x))\; ightarrow\; exists\; x;(\; eg\; A\; ightarrow\; P(x))$.

Relative realizability [Birkedal] 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 science

Modified realizability justifies the process of "program extraction" implemented in some proof assistants such as Coq.

References

*

* Kreisel G. (1959). "Interpretation of Analysis by Means of Constructive Functionals of Finite Types", in: Constructivity in Mathematics, edited by A. Heyting, North-Holland, pp. 101--128.

*

* Kleene, S. C. (1973). "Realizability: a retrospective survey" from cite book | last = Mathias | first = A. R. D. | coauthors = Hartley Rogers | title = Cambridge Summer School in Mathematical Logic : held in Cambridge/England, August 1-21, 1971 | year = 1973 | location = Berlin | publisher = Springer | id = ISBN 354005569X, pp. 95-112.

*

*

Notes