Constructive set theoryAxiomatic constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with "" and "" of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories. In addition to rejecting the principle of excluded middle (), constructive set theories often require some logical quantifiers in their axioms to be set bounded, motivated by results tied to impredicativity.
Disjunction and existence propertiesIn mathematical logic, the disjunction and existence properties are the "hallmarks" of constructive theories such as Heyting arithmetic and constructive set theories (Rathjen 2005). The disjunction property is satisfied by a theory if, whenever a sentence A ∨ B is a theorem, then either A is a theorem, or B is a theorem. The existence property or witness property is satisfied by a theory if, whenever a sentence (∃x)A(x) is a theorem, where A(x) has no other free variables, then there is some term t such that the theory proves A(t).
Principe de Markovvignette|250x250px|Une représentation artistique d'une machine de Turing. Le principe de Markov dit que s'il est impossible qu'une machine de Turing ne s'arrête pas, alors elle doit s'arrêter. Le principe de Markov, nommé d'après Andreï Markov Jr, est une déclaration d'existence conditionnelle pour laquelle il existe de nombreuses formulations, ainsi qu'il est discuté ci-dessous. Ce principe est utilisé dans la validité logique classique, mais pas dans les mathématiques intuitionniste constructives.
RéalisabilitéLa réalisabilité est une branche de la logique mathématique, et plus précisément de la théorie de la démonstration, qui définit une relation logique entre les formules d'un système logique et les programmes d'un modèle de calcul. Elle a été introduite dans les années 40 par Kleene comme une interprétation des formules de l' par des ensembles (d'indices) de fonctions récursives. Elle a depuis été étendue à toute sorte d'autres systèmes logiques, et aujourd'hui est vue comme une généralisation de la correspondance de Curry-Howard.
Luitzen Egbertus Jan BrouwerLuitzen Egbertus Jan Brouwer (né le à Overschie et mort le à Blaricum) est un mathématicien néerlandais. Aîné de trois enfants, ce fils du maître d'école Egbertus Luitzens Brouwer et de Henderika Poutsma, témoigne dès son plus jeune âge d'une intelligence exceptionnelle. À 16 ans seulement, le jeune prodige s'inscrit à l'université d'Amsterdam pour y étudier les mathématiques, sans pour autant négliger ses lectures de chevet, celles des philosophes Emmanuel Kant et Arthur Schopenhauer.
Analyse constructiveL'analyse constructive est une branche des mathématiques constructives. Elle critique l'analyse mathématique classique et vise à fonder l'analyse sur des principes constructifs. Elle s'inscrit dans le courant de pensée constructiviste ou intuitionniste, dont les principaux membres ont été Kronecker, Brouwer ou Weyl. La critique porte sur la façon dont est utilisée la notion d'existence, de disjonction et sur l'utilisation du raisonnement par l'absurde.
Church's thesis (constructive mathematics)In constructive mathematics, Church's thesis is an axiom stating that all total functions are computable functions. The similarly named Church–Turing thesis states that every effectively calculable function is a computable function, thus collapsing the former notion into the latter. is stronger in the sense that with it every function is computable. The constructivist principle is fully formalizable, using formalizations of "function" and "computable" that depend on the theory considered.
Double-negation translationIn proof theory, a discipline within mathematical logic, double-negation translation, sometimes called negative translation, is a general approach for embedding classical logic into intuitionistic logic. Typically it is done by translating formulas to formulas which are classically equivalent but intuitionistically inequivalent. Particular instances of double-negation translations include Glivenko's translation for propositional logic, and the Gödel–Gentzen translation and Kuroda's translation for first-order logic.
Dialectica interpretationIn proof theory, the Dialectica interpretation is a proof interpretation of intuitionistic logic (Heyting arithmetic) into a finite type extension of primitive recursive arithmetic, the so-called System T. It was developed by Kurt Gödel to provide a consistency proof of arithmetic. The name of the interpretation comes from the journal Dialectica, where Gödel's paper was published in a 1958 special issue dedicated to Paul Bernays on his 70th birthday.
Effective toposIn mathematics, the effective topos introduced by captures the mathematical idea of effectivity within the framework. The topos is based on the partial combinatory algebra given by Kleene's first algebra . In Kleene's notion of recursive realizability, any predicate is assigned realizing numbers, i.e. a subset of . The extremal propositions are and , realized by and . However in general, this process assigns more data to a proposition than just a binary truth value.