realizability

Realizability is a concept in mathematical logic and theoretical computer science that connects formal proofs with computational objects. Introduced by Stephen Kleene in the 1940s, the notion originally linked intuitionistic arithmetic to recursive functions, showing that a proof of an existential statement can be interpreted as an algorithm producing a witness. In this framework, a formula is said to be realizable if there exists a natural number (or more generally, a term of a formal language) that serves as a concrete witness to its truth according to a prescribed decoding procedure.

Various forms of realizability have been developed. Kleene’s original realizability interprets each formula of intuitionistic arithmetic in terms of partial recursive functions. Modified realizability, due to Kreisel, adapts the interpretation to classical logic by allowing the use of double negation. Later extensions include functional realizability, where witnesses are higher‑type functionals, and realizability in typed lambda calculi, which underlies the Curry‑Howard correspondence between proofs and programs.

In constructive mathematics, realizability provides a semantics that validates intuitionistic principles and often yields models where classical theorems fail. It has been employed to analyze the strength of axioms, to extract algorithms from proofs, and to study the computational content of mathematical statements. In type theory and proof assistants, realizability informs the design of extraction mechanisms that turn certified proofs into executable code.

Realizability also appears in topos theory, where realizability toposes are categories of sheaves built from a partial combinatory algebra, offering models of intuitionistic set theory. Overall, realizability bridges logic, computation, and mathematics by interpreting proofs as constructive procedures.