Proof uses forcing on perfect trees for 2-quantifier sentences in the language of arithmetic. The result extends to exact pairs for the hyperarithmetic degrees.

Let I be a countable jump ideal in $\mathscr{D} = \langle \text{The Turing degrees}, \leq\rangle$ . The central theorem of this paper is: a is a uniform upper bound on I iff a computes the join of an I-exact pair whose double jump a (1) computes. We may replace "the join of an I-exact pair" in the above theorem by "a weak uniform upper bound on I". We also answer two minimality questions: the (...) class of uniform upper bounds on I never has a minimal member; if ∪ I = L α [ A] ∩ ω ω for α admissible or a limit of admissibles, the same holds for nice uniform upper bounds. The central technique used in proving these theorems consists in this: by trial and error construct a generic sequence approximating the desired object; simultaneously settle definitely on finite pieces of that object; make sure that the guessing settles down to the object determined by the limit of these finite pieces. (shrink)

A uniform upper bound on a class of Turing degrees is the Turing degree of a function which parametrizes the collection of all functions whose degree is in the given class. I prove that if a is a uniform upper bound on an ideal of degrees then a is the jump of a degree c with this additional property: there is a uniform bound b<a so that b V c < a.

We show that there is a low T-upper bound for the class of K-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in $\Delta _2^0 $ T-degrees for which there is a low T-upper bound.

We settle a question in the literature about degrees of models of true arithmetic and upper bounds for the arithmetic sets. We prove that there is a model of true arithmetic whose degree is not a uniform upper bound for the arithmetic sets. The proof involves two forcing constructions.

An Exact Pair for the Arithmetic Degrees whose join is not a Weak Uniform Upper Bound, in the Recursive Function Theory-Newsletters, No. 28, August-September 1982.

Pudlák shows that bounded arithmetic proves an upper bound on the Ramsey number Rr . We will strengthen this result by improving the bound. We also investigate lower bounds, obtaining a non-constructive lower bound for the special case of 2 colors , by formalizing a use of the probabilistic method. A constructive lower bound is worked out for the case when the monochromatic set size is fixed to 3 . The constructive lower bound is (...) used to prove two “reversals”. To explain this idea we note that the Ramsey upper bound proof for k=3 uses the weak pigeonhole principle in a significant way. The Ramsey upper bound proof for the case in which the upper bound is not explicitly mentioned, uses the totality of the exponentiation function in a significant way. It turns out that the Ramsey upper bounds actually imply the respective principles used to prove them, indicating that these principles were in some sense necessary. (shrink)

In this paper we study a new approach to classify mathematical theorems according to their computational content. Basically, we are asking the question which theorems can be continuously or computably transferred into each other? For this purpose theorems are considered via their realizers which are operations with certain input and output data. The technical tool to express continuous or computable relations between such operations is Weihrauch reducibility and the partially ordered degree structure induced by it. We have identified certain choice (...) principles such as co-finite choice, discrete choice, interval choice, compact choice and closed choice, which are cornerstones among Weihrauch degrees and it turns out that certain core theorems in analysis can be classified naturally in this structure. In particular, we study theorems such as the Intermediate Value Theorem, the Baire Category Theorem, the Banach Inverse Mapping Theorem, the Closed Graph Theorem and the Uniform Boundedness Theorem. We also explore how existing classifications of the Hahn—Banach Theorem and Weak Kőnig's Lemma fit into this picture. Well-known omniscience principles from constructive mathematics such as LPO and LLPO can also naturally be considered as Weihrauch degrees and they play an important role in our classification. Based on this we compare the results of our classification with existing classifications in constructive and reverse mathematics and we claim that in a certain sense our classification is finer and sheds some new light on the computational content of the respective theorems. Our classification scheme does not require any particular logical framework or axiomatic setting, but it can be carried out in the framework of classical mathematics using tools of topology, computability theory and computable analysis. We develop a number of separation techniques based on a new parallelization principle, on certain invariance properties of Weihrauch reducibility, on the Low Basis Theorem of Jockusch and Soare and based on the Baire Category Theorem. Finally, we present a number of metatheorems that allow to derive upper bounds for the classification of the Weihrauch degree of many theorems and we discuss the Brouwer Fixed Point Theorem as an example. (shrink)

In this paper we study with proof-theoretic methods the function(al) s provably recursive relative to Ramsey's theorem for pairs and the cohesive principle (COH). Our main result on COH is that the type 2 functional provably recursive from $RCA_0 + COH + \Pi _1^0 - CP$ are primitive recursive. This also provides a uniform method to extract bounds from proofs that use these principles. As a consequence we obtain a new proof of the fact that $WKL_0 + \Pi _1^0 (...) - CP + COH$ is $\Pi _1^0 $ -conservative over PRA. Recent work of the first author showed that $\Pi _1^0 + CP + COH$ is equivalent to a weak variant of the Bolzano-Weierstraß principle. This makes it possible to use our results to analyze not only combinatorial but also analytical proofs. For Ramsey's theorem for pairs and two colors $\left( {RT_2^2 } \right)$ we obtain the upper bounded that the type 2 functionals provable recursive relative to $RCA_0 + \sum\nolimits_2^0 {IA + RT_2^2 } $ are in T₁. This is the fragment of Gödel's system T containing only type 1 recursion—roughly speaking it consists of functions of Ackermann type. With this we also obtain a uniform method for the extraction of T₁-bounds from proofs that use RT2..... Moreover, this yields a new proof of the fact that $WKL_0 + \sum\nolimits_2^0 {IA} + RT_2^2 $ is $\Pi _1^0 $ -conservative over $RCA_0 + \sum\nolimits_2^0 { - IA} $ . The results are obtained in two steps: in the first step a term including Skolem functions for the above principles is extracted from a given proof. This is done using Gödel's functional interpretation. After this the term is normalized, such that only specific instances of the Skolem functions are used. In the second step this term is interpreted using $\Pi _1^0 $ -comprehension. The comprehension is then eliminated in favor of induction using either elimination of monotone Skolem functions (for COH) or Howard's ordinal analysis of bar recursion (for $RT_2^2 $. (shrink)

We introduce and investigate the notion of uniform Lyndon interpolation property which is a strengthening of both uniform interpolation property and Lyndon interpolation property. We prove several propositional modal logics including \, \, \ and \ enjoy ULIP. Our proofs are modifications of Visser’s proofs of uniform interpolation property using layered bisimulations Gödel’96, logical foundations of mathematics, computer science and physics—Kurt Gödel’s legacy, Springer, Berlin, 1996). Also we give a new upper bound on the complexity (...) of uniform interpolants for \ and \. (shrink)

The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We prove that the first-order theory of a string automatic structure of bounded degree is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). This result is shown to be optimal since we also present a string automatic structure of bounded degree whose first-order theory is hard for 2EXPSPACE. We prove similar (...) results also for tree automatic structures. These findings close the gaps left open in [28] by improving both the lower and the upper bounds. (shrink)

In recent years, proof theoretic transformations that are based on extensions of monotone forms of Gödel’s famous functional interpretation have been used systematically to extract new content from proofs in abstract nonlinear analysis. This content consists both in effective quantitative bounds as well as in qualitative uniformity results. One of the main ineffective tools in abstract functional analysis is the use of sequential forms of weak compactness. As we recently verified, the sequential form of weak compactness for bounded (...) closed and convex subsets of an abstract Hilbert space can be carried out in suitable formal systems that are covered by existing metatheorems developed in the course of the proof mining program. In particular, it follows that the monotone functional interpretation of this weak compactness principle can be realized by a functional Ω∗ definable from bar recursion of lowest type. While a case study on the analysis of strong convergence results that are based on weak compactness indicates that the use of the latter seems to be eliminable, things apparently are different for weak convergence theorems such as the famous Baillon nonlinear ergodic theorem. For this theorem we recently extracted an explicit bound on a metastable version of this theorem that is primitive recursive relative to Ω∗.In the current paper we for the first time give the construction of Ω∗ . As a corollary to the fine analysis of the use of bar recursion in this construction we obtain that Ω∗ elevates arguments in Tn at most to resulting functionals in Tn+2 . In particular, one can conclude from this that our bound on Baillon’s theorem is at least definable in T4. (shrink)

Mostowski [11] shows that if a structure has a decidable theory, then its weak direct power has one as well; his proof however never produces decision procedures which are elementary recursive. Some very general results are obtained here about the nature of the weak direct power of a structure, which in most cases lead to elementary recursive decision procedures for weak direct powers of structures which themselves have elementary recursive procedures. In particular, it is shown that $\langle (...) N^\ast, +\rangle$ , the weak direct power of $\langle N, +\rangle$ , can be decided in space 2 2 2 cn for some constant c. As corollaries, the same upper bound is obtained for the theory of the structure $\langle N^+, \cdot\rangle$ of positive integers under multiplication, and for the theory of finite abelian groups. Fischer and Rabin [7] have shown that the theory of $\langle N^\ast, +\rangle$ requires time 2 2 2 dn even on nondeterministic Turing machines. (shrink)

Cimpian et al. observed that we accept generic statements of the form ‘Gs are f’ on relatively weak evidence, but that if we are unfamiliar with group G and we learn a generic statement about it, we still treat it inferentially in a much stronger way: all Gs are f. This paper makes use of notions like ‘representativeness’, ‘contingency’ and ‘relative difference’ from psychology to provide a uniform semantics of generics that explains why people accept generics based on (...) weak evidence. The spirit of the approach has much in common with Leslie’s cognition-based ideas about generics, but the semantics will be grounded on a strengthening of Cohen’s relative readings of generic sentences. In contrast to Leslie and Cohen, we propose a uniform semantic analysis of generics. The basic intuition is that a generic of the form ‘Gs are f’ is true because f is typical for G, which means that f is valuably associated with G. We will make use of Kahneman and Tversky’s Heuristics and Biases approach, according to which people tend to confuse questions about probability with questions about representativeness, to explain pragmatically why people treat many generic statements inferentially in a much stronger way. (shrink)

We study ideals in the computably enumerable Turing degrees, and their upper bounds. Every proper ideal in the c.e. Turing degrees has an incomplete upper bound. It follows that there is no prime ideal in the c.e. Turing degrees. This answers a question of Calhoun [2]. Every proper ideal in the c.e. Turing degrees has a low2 upper bound. Furthermore, the partial order of ideals under inclusion is dense.

We study the classes of hypersimple and semicomputable sets as well as their intersection in the weak truth table degrees. We construct degrees that are not bounded by hypersimple degrees outside any non-trivial upper cone of Turing degrees and show that the hypersimple-free c.e. wtt degrees are downwards dense in the c.e. wtt degrees. We also show that there is no maximal (w.r.t. ≤wtt) hypersimple wtt degree. Moreover, we consider the sets that are both hypersimple and semicomputable, characterize (...) them as the (bi-infinite) c.e. cuts of computable orderings of ℕ of order type ω+ω* and study their wtt degrees. We show that there are hypersimple degrees that are not bounded by any hypersimple semicomputable degree, investigate relationships with the join and look for maximal and minimal elements of related classes. (shrink)

We estimate the derivation lengths of functionals in Gödel's system \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document} of primitive recursive functionals of finite type by a purely recursion-theoretic analysis of Schütte's 1977 exposition of Howard's weak normalization proof for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}. By using collapsing techniques from Pohlers' local predicativity approach to proof theory and based on the Buchholz-Cichon and Weiermann 1994 approach to subrecursive hierarchies we define (...) a collapsing f unction\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} ${\cal D}:T\to \omega$\end{document} so that for (closed) terms \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $a,b$\end{document} of Gödel's \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document} we have: If \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $a$\end{document} reduces to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $b$\end{document} then \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\omega>{\cal D}(a)>{\cal D}(b).$\end{document} By one uniform proof we obtain as corollaries: A derivation lengths classification for functionals in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}, hence new proof of strongly uniform termination of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}. A new proof of the Kreisel's classific ation of the number-theoretic functions which can be defined in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}, hence a classification of the provably total functions of Peano Arithmetic. A new proof of Tait's results on weak normalization for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}. A new proof of Troelstra's result on strong normalization for \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document}. Additionally, a slow growing analysis of Gödel's \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $T$\end{document} is obtained via Girard's hierarchy comparison theorem. This analyis yields a contribution to two open pro blems posed by Girard in part two of his book on proof theory. For the sake of completeness we also mention the Howard Schütte bound on derivation lengths for the simple typed \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $\lambda$\end{document}-calculus. (shrink)

We give modest upper bounds for consistency strengths for two well-studied combinatorial principles. These bounds range at the level of subcompact cardinals, which is significantly below a κ+-supercompact cardinal. All previously known upper bounds on these principles ranged at the level of some degree of supercompactness. We show that by using any of the standard modified Prikry forcings it is possible to turn a measurable subcompact cardinal into ℵω and make the principle □ℵω,<ω fail in the generic extension. (...) We also show that by using Lévy collapse followed by standard iterated club shooting it is possible to turn a subcompact cardinal into ℵ2 and arrange in the generic extension that simultaneous reflection holds at ℵ2, and at the same time, every stationary subset of ℵ3 concentrating on points of cofinality ω has a reflection point of cofinality ω1. (shrink)

In this article we introduce systems for metapredicative Mahlo in explicit mathematics and admissible set theory. The exact upper proof-theoretic bounds of these systems are established.

The existence of exact upper bounds for increasing sequences of ordinal functions modulo an ideal is discussed. The main theorem gives a necessary and sufficient condition for the existence of an exact upper bound ƒ for a ¦A¦+ is regular: an eub ƒ with lim infI cf ƒ = μ exists if and only if for every regular κ ε the set of flat points in tf of cofinality κ is stationary. Two applications of the main Theorem (...) to set theory are presented. A theorem of Magidor's on covering between models of ZFC is proved using the main theorem : If V-W are transitive models of set theory with ω-covering and GCH holds in V, then κ-covering holds between V and W for all cardinals κ. A new proof of a Theorem by Cummings on collapsing successors of singulars is also given . The appendix to the paper contains a short proof of Shelah's trichotomy theorem, for the reader's convenience. (shrink)

Where AR is the set of arithmetic Turing degrees, 0 (ω ) is the least member of { $\mathbf{\alpha}^{(2)}|\mathbf{a}$ is an upper bound on AR}. This situation is quite different if we examine HYP, the set of hyperarithmetic degrees. We shall prove (Corollary 1) that there is an a, an upper bound on HYP, whose hyperjump is the degree of Kleene's O. This paper generalizes this example, using an iteration of the jump operation into the transfinite (...) which is based on results of Jensen and is detailed in [3] and [4]. In $\S1$ we review the basic definitions from [3] which are needed to state the general results. (shrink)

By obtaining several new results on Cook-style two-sorted bounded arithmetic, this paper measures the strengths of the axiom of extensionality and of other weak fundamental set-theoretic axioms in the absence of the axiom of infinity, following the author’s previous work [K. Sato, The strength of extensionality I — weak weak set theories with infinity, Annals of Pure and Applied Logic 157 234–268] which measures them in the presence. These investigations provide a uniform framework in which three (...) different kinds of reverse mathematics–Friedman–Simpson’s “orthodox” reverse mathematics, Cook’s bounded reverse mathematics and large cardinal theory–can be reformulated within one language so that we can compare them more directly. (shrink)

In this article we introduce systems for metapredicative Mahlo in explicit mathematics and admissible set theory. The exact upper proof-theoretic bounds of these systems are established.

The discipline of parallelization in the manifold of all possible measurement results is shown to be responsible for the existence of all quantum correlations, with the upper bound on their strength stemming from the maximum of possible torsion within all norm-composing parallelizable manifolds. A profound interplay is thus uncovered between the existence and strength of quantum correlations and the parallelizability of the spheres S^0, S^1, S^3, and S^7 necessitated by the four real division algebras. In particular, parallelization within (...) a unit 3-sphere is shown to be responsible for the existence of EPR and Hardy type correlations, whereas that within a unit 7-sphere is shown to be responsible for the existence of all GHZ type correlations. Moreover, parallelizability in general is shown to be equivalent to the completeness criterion of EPR, in addition to necessitating the locality condition of Bell. It is therefore shown to predetermine both the local outcomes as well as the quantum correlations among the remote outcomes, dictated by the infinite factorizability of points within the spheres S^3 and S^7. The twin illusions of quantum entanglement and non-locality are thus shown to stem from the topologically incomplete accountings of the measurement results. (shrink)

The paper considers a commonly used axiomatization of the classical propositional logic and studies how different axiom schemata in this system contribute to proof complexity of the logic. The existence of a polynomial bound on proof complexity of every statement provable in this logic is a well-known open question.The axiomatization consists of three schemata. We show that any statement provable using unrestricted number of axioms from the first of the three schemata and polynomially-bounded in size set of axioms from (...) the other schemata, has a polynomially-bounded proof complexity. In addition, it is also established, that any statement, provable using unrestricted number of axioms from the remaining two schemata and polynomially-bounded in size set of axioms from the first scheme, also has a polynomially-bounded proof complexity. (shrink)

The paper concerns the expression of non-strict comparison, focusing in particular on constructions of the form [no(t) . . .-er than] in modified numerals. The main empirical finding is the observation that negated comparatives contrast with regular comparatives in that the former but not the latter can give rise to (scalar) implicatures. It is shown that such a contrast falls out of theories of exhaustive interpretation that claim alternatives to form dense scales. An important result is that the paper sharpens (...) the desiderata for theories of exhaustification. (shrink)

In this paper, we show that certain choiceless models of ZF originally constructed using an almost huge cardinal can be constructed using cardinals strictly weaker in consistency strength.

Syllogisms (e.g. “All A are B; All B are C; What is true about A and C?”) are a long‐studied area of human reasoning. Riesterer, Brand, and Ragni compare a variety of models to human performance and show that not only do current models have a lot of room for improvement, but more importantly a large part of this improvement must come from examining individual differences in performance.

In a previous paper we constructed a full and faithful functor ℳ from the category of locally compact metric spaces to the category of formal topologies . Here we show that for a real-valued continuous function f, ℳ factors through the localic positive reals if, and only if, f has a uniform positive lower bound on each ball in the locally compact space. We work within the framework of Bishop constructive mathematics, where the latter notion is strictly stronger (...) than point-wise positivity. (shrink)

In an influential recent paper, Hawthorne, Rothschild, and Spectre (“HRS”) argue that belief is weak. More precisely: they argue that the referent of believe in ordinary language is much weaker than epistemologists usually suppose; that one needs very little evidence to be entitled to believe a proposition in this sense; and that the referent of believe in ordinary language just is the ordinary concept of belief. I argue here to the contrary. HRS identify two alleged tests of weakness – (...) the neg-raising and weak upper bounds tests, as I call them – which they claim believe and think pass. But I identify several other expressions in ordinary English for attributing belief, all of which fail both tests. Therefore, even if HRS are correct that believe and think refer to a weak attitude, it does not follow that the ordinary concept of belief is weak. I conclude by raising some problems for the accounts of belief as guessing, building on HRS's arguments, due to Kevin Dorst, Matt Mandelkern, and Ben Holguín. (shrink)

We define a new NP search problem, the “local improvement” principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in , it characterizes the consequences of and that natural restrictions of it characterize the consequences of and of the bounded arithmetic hierarchy. We also show that over V0 it characterizes the consequences of V1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the consequences of . Throughout our search (...) problems are “type-2” NP search problems, which take second-order objects as parameters. (shrink)

We show that length initial submodels of S12 can be extended to a model of weak second order arithmetic. As a corollary we show that the theory of length induction for polynomially bounded second order existential formulae cannot define the function division.