Realizability

In <a href="/facts/Mathematical_logic/SaI7Y3wN">mathematical logic</a>, realizability is a collection of methods in <a href="/facts/Proof_theory/kopBdQn9">proof theory</a> used to study <a href="/facts/Constructive_proof/0QhhRjhW">constructive proofs</a> and extract additional information from them. <a href="/facts/Well-formed_formula/YpTVlzuj">Formulas</a> from a formal theory are "realized" by objects, known as "realizers", in a way that knowledge of the realizer gives knowledge about the truth of the formula. There are many variations of realizability; exactly which class of formulas is studied and which objects are realizers differ from one variation to another.
Realizability can be seen as a formalization of the <a href="/facts/Brouwer%25E2%2580%2593Heyting%25E2%2580%2593Kolmogorov_interpretation/Tm5t5LaF">Brouwer–Heyting–Kolmogorov (BHK) interpretation</a> of <a href="/facts/Intuitionistic_logic/zI7ulCnM">intuitionistic logic</a>. In realizability the notion of "proof" (which is left undefined in the BHK interpretation) is replaced with a formal notion of "realizer". Most variants of realizability begin with a theorem that any statement that is provable in the formal system being studied is realizable. The realizer, however, usually gives more information about the formula than a formal proof would directly provide.
Beyond giving insight into intuitionistic provability, realizability can be applied to prove the <a href="/facts/Disjunction_and_existence_properties/18s8ll0e">disjunction and existence properties</a> for intuitionistic theories and to extract programs from proofs, as in <a href="/facts/Proof_mining/5PkmkIHm">proof mining</a>. It is also related to <a href="/facts/Topos_theory/zzttCIwC">topos theory</a> via <a href="/facts/Effective_topos/IHVugWtH">realizability topoi</a>.

Realizability open-in-new

Realizability