Introduction. Il est bien connu que la correspondance de Curry-Howard permet d'associer un programme, sous la forme d'un λ-terme, à toute preuve intuitionniste, formalisée dans le calcul des prédicats du second ordre. Cette correspondance a été étendue, assez récemment, à la logique classique moyennant une extension convenable du λ-calcul. Chaque théorème formalisé en logique du second ordre correspond donc à une spécification de programme.Il se pose alors le problème, en général tout à fait non trivial, de trouver la spécification associée (...) à un théorème donné; autrement dit, de déterminer le comportement opérationnel commun aux λ-termes associés aux diverses démonstrations formelles du théorème considéré.Cette question est résolue ici pour le théorème de complétude de la logique classique.La première étape consiste à formaliser convenablement ce théorème en logique du second ordre. Ce travail est fait complètement dans la section 1. Il a comme sous-produit, peut-être inattendu, de montrer que ce théorème est prouvable en logique intuitionniste du second ordre. Ceci, toutefois, à condition d'introduire une légère variante de la notion de modèle, en admettant un modèle supplémentaire trivial, où toute formule est satisfaite.On notera, à ce sujet, que des preuves intuitionnistes du théorème de complétude de la logique intuitionniste, utilisant des variantes de la notion de modele de Kripke, ont été données par H. Friedman [7] et W. Veldman [8]. On remarquera également qu'un argument de G. Kreisel [2] montre que le théorème de complétude habituel de la logique intuitionniste n'a pas de preuve intuitionniste. (shrink)

The paper presents a refined method of extracting reasonable and sometimes unexpected programs from classical proofs of formulas of the form ∀x∃yB . We also generalize previously known results, since B no longer needs to be quantifier-free, but only has to belong to a strictly larger class of so-called “goal formulas”. Furthermore we allow unproven lemmas D in the proof of ∀x∃yB , where D is a so-called “definite” formula.

We give a direct, purely arithmetical and elementary proof of the strong normalization of the cut-elimination procedure for full (i.e., in presence of all the usual connectives) classical natural deduction.

In this paper, we extend the system AF2 in order to have the subject reduction for the $betaeta$-reduction. We prove that the types with positive quantifiers are complete for models that are stable by weak-head expansion.

Storage operators are λ-terms which simulate call-by-value in call-by-name for a given set of terms. Krivine's storage operator theorem shows that any term of type ¬D → ¬D*, where D* is the Gödel translation of D, is a storage operator for the terms of type D when D is a data-type or a formula with only positive second order quantifiers. We prove that a new semantical version of Krivine's theorem is valid for every types. This also gives a simpler proof (...) of Krivine's theorem using the properties of data-types. (shrink)

We present an extension of Heyting arithmetic in finite types called Uniform Heyting Arithmetic that allows for the extraction of optimized programs from constructive and classical proofs. The system has two sorts of first-order quantifiers: ordinary quantifiers governed by the usual rules, and uniform quantifiers subject to stronger variable conditions expressing roughly that the quantified object is not computationally used in the proof. We combine a Kripke-style Friedman/Dragalin translation which is inspired by work of Coquand and Hofmann and a variant (...) of the refined A-translation due to Buchholz, Schwichtenberg and the author to extract programs from a rather large class of classical first-order proofs while keeping explicit control over the levels of recursion and the decision procedures for predicates used in the extracted program. (shrink)