Constructive semantics

From Encyclopedia of Mathematics
Revision as of 16:59, 7 February 2011 by (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

The collection of methods for understanding statements in constructive mathematics. The need for a special semantics is caused by the difference in the general principles underlying traditional (classical) and constructive mathematics (in what follows the latter term refers mainly to the approach developed in the Soviet school of constructive mathematics). The main attention of constructive semantics is given to statements concerning constructive objects (cf. Constructive object) in first-order languages; i.e., essentially arithmetic statements (see Arithmetic, formal). The principal difference from traditional semantics in the understanding of the disjunction (and of statements concerning the existence ) were stated by L.E.J. Brouwer. The constructive justification of such statements requires a solution of the problem: Find a number such that is true (or: Find a number such that ). The general principles of description of problems corresponding to more complex formulas were outlined by A. Heyting and A.N. Kolmogorov. A precise formulation (which became possible after the appearance of the mathematical definition of an algorithm) was given by S.C. Kleene in the form of the notion of realization of a closed arithmetic formula (see Recursive realizability). A realization of a true equality is a fixed constant; for example, the number , while a false equation has no realization. A realization of a conjunction is a pair where is a realization of and is a realization of . A realization of a disjunction is a pair , where and is a realization of . A realization of the statement is a pair , where is a number and is a realization of . A realization of is a general method that gives for each natural number a realization of . A realization of is a general method that, for each realization of , gives a realization of (and which need not be defined for arguments that are not realizations of ). Here, a general method is understood to be an algorithm (a partial recursive function). By using an encoding of algorithms by numbers, one can write the condition "the number e is a realization of the formula A" in the form of an arithmetic formula that does not contain the disjunction and contains the existence quantifier only in a natural way, in front of equalities. Such formulas are called almost normal or almost negative. The statement (read "A is realizable" ) may serve as a constructive interpretation of . Under this interpretation the law of the excluded middle, , is refuted, for example, for , where means that the (encoded) algorithm completes its processing on the argument after steps. The law of double negation, , is also refuted, for example, for . The above definition associates to each statement a constructive interpretation (to find a realization), even if does not contain . The algorithm giving this constructive interpretation, put forward by N.A. Shanin, does not change formulas without (normal formulas) and is equivalent to realizability in formal intuitionistic arithmetic with quantifier-free induction. Arbitrary formulas can be reduced to almost-normal ones, since a justification of consists in producing a number and a justification of . Constructive semantics for almost-normal formulas is defined in different ways by different authors; however, in no case does one obtain such a significant departure from the classical concept as for formulas containing and a non-trivial .

A.A. Markov defines truth for almost-normal formulas by means of derivability according to the usual laws for the logical connectives plus the effective -rule: If there is a general method enabling one to establish for any the derivability of from a statement , then is derivable from . Truth is defined step by step. The language consisting of all almost-normal formulas is divided into layers ; the language consists of formulas without ; the language , , includes and the formulas that can be obtained from by a single application of implication and any number of applications of . Truth for formulas in is defined as derivability according to the usual rules for , , . Truth for formulas in is defined in terms of admissibility of the appropriate rule. For example, the truth of means the existence of an algorithm such that for any number . For formulas in for , truth of conjunctions and -formulas is defined in the ordinary way in terms of truth of their components, while truth of an implication means derivability of from according to certain rules about which it has already been proved that they preserve the truth of formulas in . The systems contain the -rule and, as axioms, all true formulas in . The notion of derivability in is introduced by a generalized inductive definition, and a corresponding induction principle is applied for the proof of meta-theorems. The admissibility of the rule is proved by induction over -derivation. It is included in and gives Markov's principle . The systems , , consist of the ordinary rules for the connectives, including the -rule. It turns out that an almost-normal formula is true in the sense of Markov if and only if the primitive recursive cut-free proof search tree for (with the -rule and the Markov principle) is a derivation in the sense of the inductive definition. This is equivalent (in the framework of classical mathematics) to the classical truth of .

In the majorizing semantics of Shanin a transfinite hierarchy of formulas of simple structure is defined for every almost-normal formula , such that is provable in a suitable formal system. The formula is called a majorant for , and is called a true formula of rank , if is true. The accuracy of the approximation increases with increasing : . Up to technical details, a formula is constructed by -fold moving quantifiers forward according to the equivalence

and by fusing the string of quantifiers according to the algorithm for constructive interpretation. This gives the equivalence

which is provable in an arithmetic with transfinite induction up to , containing a quantifier-free formula , so that

turns out to be a majorant for . The statement turns out to be equivalent, up to some technical details, to the assertion of the existence of a derivation of height less that for the original formula using the -rule. In this sense, the majorizing semantics is equivalent to the stepwise semantics of Markov. After fixing some class of general recursive functions (for example, the class of all functions defined by recursion up to ), majorants of even simpler structure are defined:

If is a quantifier-free calculus for the class , then -truth of the formula is defined as derivability of with variable and a constant term . If is the standard equation calculus for functions defined by recursion up to , then the -true formulas turns out to be those that are derivable in formal intuitionistic arithmetic supplemented by Markov's principle, the equivalences defining the algorithm for constructive interpretation, and the rule of induction up to ordinal numbers for which , where is the first -number greater than . In particular, for , that is, for ordinary induction.

The justification at the quantifier-free level (-truth) relates to the desire to remain as far as possible within the realms of finitism, that is, quantifier-free language and the corresponding logical means. Related to this is the aim of restricting the value of . For the greater part of constructive analysis "in practice" finite 's suffice (including in the theorem on the continuity of effective operators).


[1] A.A. Markov, "An attempt to construct the logic of constructive mathematics" , Investigations on the theory of algorithms and mathematical logic , 2 , Moscow (1976) pp. 3–31 (In Russian)
[2] N.A. Shanin, "A hierarchy of ways of understanding judgements in constructive mathematics" Trudy Mat. Inst. Steklov. , 129 (1973) pp. 203–266 (In Russian)
[3] S.C. Kleene, "Introduction to metamathematics" , North-Holland (1951)


Realizability is just one of the many semantics for constructive or intuitionistic logic and mathematics. An introductory account is given in [a1]; more on realizability can found in [a2]. Other semantics include those using sheaf theory and topos theory (cf. Topos, [a3]).


[a1] M.A.E. Dummett, "Elements of intuitionism" , Oxford Univ. Press (1977)
[a2] A.S. Troelstra (ed.) , Mathematical investigations of intuitionistic arithmetic and analysis , Lect. notes in math. , 344 , Springer (1973)
[a3] P.T. Johnstone, "Topos theory" , Acad. Press (1977)
How to Cite This Entry:
Constructive semantics. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by G.E. Mints (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article