×

Effective bounds from ineffective proofs in analysis: An application of functional interpretation and majorization. (English) Zbl 0781.03051

The paper contains quite a number of interesting results, which in their simplest form read as follows. Suppose we are given a proof in WE- \(\text{PA}^ \omega+\)AC-qf of \(\forall x^ 1 \forall\widetilde x\leq_ \rho sx \exists y^ \tau A_ 0\) with \(A_ 0\) quantifier-free, \(s\) a closed term of Gödel’s \(T\) and \(\tau\leq 2\). Then one can extract a closed term \(\Phi\in T\) such that WE-\(\text{HA}^ \omega\lvdash\forall x^ 1 \forall\widetilde x\leq_ \rho sx \exists y\leq_ \tau \Phi x A_ 0\). This result is obtained by a combination of functional interpretation and a pointwise version of hereditary majorization of functionals from \(T\). One of the generalizations dealt with in the paper allows additional assumptions of the form \(\forall x^ \delta \exists y\leq_ \rho sx \forall z^ \eta A_ 0\). The author shows (by an adaptation of a well- known counterexample due to Kreisel) that a straightforward generalization of his method to proofs of weak König’s Lemma WKL fails. However, it turns out that one can construct an equivalent WKL\('\) of WKL (in \(\widehat{\text{WE-}\text{HA}}^ \omega \upharpoonright\)) which has the right logical form for an admissible premise: \(\forall f^ 1\), \(g^ 1 \exists b\leq_ 1 \lambda k 1 \forall x^ 0(\widehat{(\hat f)_ g}(\bar b x)=_ 0 0)\). Therefore the previous results generalize to proofs using WKL. As a corollary, some new conservation results for WKL are derived, e.g. with respect to sentences of the form \(\forall u^ 1\forall v\leq tu \exists w^ \eta B_ 0\). The particular logical form of the sentences considered is motivated by intended applications to uniqueness theorems in approximation theory, which the author plans to elaborate in subsequent papers. – The paper is an extended version of parts of the author’s dissertation (thesis adviser: H. Luckhardt).

MSC:

03F60 Constructive and recursive analysis
03F10 Functionals in proof theory
03F50 Metamathematics of constructive systems
Full Text: DOI

References:

[1] DOI: 10.1016/0021-9045(80)90012-X · Zbl 0458.41021 · doi:10.1016/0021-9045(80)90012-X
[2] DOI: 10.1090/S0002-9939-1982-0660604-7 · doi:10.1090/S0002-9939-1982-0660604-7
[3] Strongly majorizable functionals of finite type: a model for bar recursion containing discontinuous functionals 50 pp 652– (1985)
[4] DOI: 10.1007/BF01621477 · Zbl 0722.03040 · doi:10.1007/BF01621477
[5] Rendiconti del Seminario Matematico, Università e Politecnico di Torino, Special issue: Conference on logic and computer science: new trends and issues pp 75– (1987)
[6] DOI: 10.1007/BF01794980 · Zbl 0729.03031 · doi:10.1007/BF01794980
[7] The foundations of intuitionistic mathematics, especially in relation to recursive functions (1965) · Zbl 0133.24601
[8] Transactions of the American Mathematical Society 91 pp 1– (1959)
[9] Introduction to metamathematics (1952)
[10] DOI: 10.1007/BFb0067653 · doi:10.1007/BFb0067653
[11] DOI: 10.1007/BF01206605 · JFM 51.0044.02 · doi:10.1007/BF01206605
[12] DOI: 10.1111/j.1746-8361.1958.tb01464.x · Zbl 0090.01003 · doi:10.1111/j.1746-8361.1958.tb01464.x
[13] Ergebnisse eines Mathematischen Kolloquiums 4 pp 34– (1933)
[14] Konig’s lemma and fragments of arithmetic 52 pp 342– (1987)
[15] DOI: 10.1016/0168-0072(85)90030-2 · Zbl 0558.03029 · doi:10.1016/0168-0072(85)90030-2
[16] A relative consistency proof 19 pp 21– (1954) · Zbl 0055.00404
[17] DOI: 10.1090/pspum/005/0141595 · doi:10.1090/pspum/005/0141595
[18] Konstruktive Funktionentheorie (1949) · Zbl 0041.18602
[19] Extensional Gödei functional interpretation: a consistency proof of classical analysis 306 (1973)
[20] DOI: 10.1007/BFb0064871 · doi:10.1007/BFb0064871
[21] Metamathematical investigation of intuitionistic arithmetic and analysis 344 (1973)
[22] Seminar on the foundations of analysis. Reports, Vol. II (1963)
[23] DOI: 10.1007/BF01627504 · Zbl 0742.03021 · doi:10.1007/BF01627504
[24] Systems of second order arithmetic with restricted induction 41 pp 558– (1976)
[25] Proceedings of the international congress of mathematicians (Vancouver, 1974) 1 pp 235– (1975)
[26] Hubert’s program relativized: proof-theoretical and foundational reductions 53 pp 364– (1988)
[27] Handbook of mathematical logic pp 913– (1977)
[28] Leçons sur l’approximation des fonctions d’une variable réelle (1919)
[29] Some models for intuitionistic finite type arithmetic with fan functional 42 pp 194– (1977) · Zbl 0385.03048
[30] DOI: 10.1007/BF01792983 · Zbl 0689.03027 · doi:10.1007/BF01792983
[31] Note on the fan theorem 39 pp 584– (1974)
[32] Formal systems and recursive functions pp 176– (1965)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.