We characterize Weihrauch reducibility in $ \operatorname {\mathrm {E-PA^{\omega }}} + \operatorname {\mathrm {QF-AC^{0,0}}}$ and all systems containing it by the provability in a linear variant of the same calculus using modifications of Gödel’s Dialectica interpretation that incorporate ideas from linear logic, nonstandard arithmetic, higher-order computability, and phase semantics.

We prove that the Weihrauch lattice can be transformed into a Brouwer algebra by the consecutive application of two closure operators in the appropriate order: first completion and then parallelization. The closure operator of completion is a new closure operator that we introduce. It transforms any problem into a total problem on the completion of the respective types, where we allow any value outside of the original domain of the problem. This closure operator is of interest by itself, as (...) it generates a total version of Weihrauch reducibility that is defined like the usual version of Weihrauch reducibility, but in terms of total realizers. From a logical perspective completion can be seen as a way to make problems independent of their premises. Alongside with the completion operator and total Weihrauch reducibility we need to study precomplete representations that are required to describe these concepts. In order to show that the parallelized total Weihrauch lattice forms a Brouwer algebra, we introduce a new multiplicative version of an implication. While the parallelized total Weihrauch lattice forms a Brouwer algebra with this implication, the total Weihrauch lattice fails to be a model of intuitionistic linear logic in two different ways. In order to pinpoint the algebraic reasons for this failure, we introduce the concept of a Weihrauch algebra that allows us to formulate the failure in precise and neat terms. Finally, we show that the Medvedev Brouwer algebra can be embedded into our Brouwer algebra, which also implies that the theory of our Brouwer algebra is Jankov logic. (shrink)

In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees (...) can be embedded. The importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. As crucial corner points of this classification scheme the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations are studied. It is proved that parallelized LLPO is equivalent to Weak Kőnig's Lemma and hence to the Hahn—Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof, based on a computational version of Kleene's ternary logic, that the class of weakly computable operations is closed under composition. Moreover, weakly computable operations on computable metric spaces are characterized as operations that admit upper semi-computable compact-valued selectors and it is proved that any single-valued weakly computable operation is already computable in the ordinary sense. (shrink)

We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to $\mathrm {ATR_0}$ from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions (...) turns out to be strictly stronger than any previously studied multivalued functions arising from statements around $\mathrm {ATR}_0$. (shrink)

Continuous reducibilities are a proven tool in Computable Analysis, and have applications in other fields such as Constructive Mathematics or Reverse Mathematics. We study the order-theoretic properties of several variants of the two most important definitions, and especially introduce suprema for them. The suprema are shown to commutate with several characteristic numbers.

The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single-valued as well as for multi-valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and corresponding complete (...) functions. We use this classification and an effective version of a Selection Theorem of Bhattacharya-Srivastava in order to prove a generalization of the Representation Theorem of Kreitz-Weihrauch for Borel measurable functions on computable metric spaces: such functions are Borel measurable on a certain finite level, if and only if they admit a realizer on Baire space of the same quality. This Representation Theorem enables us to introduce a realizer reducibility for functions on metric spaces and we can extend the completeness result to this reducibility. Besides being very useful by itself, this reducibility leads to a new and effective proof of the Banach-Hausdorff-Lebesgue Theorem which connects Borel measurable functions with the Baire functions. Hence, for certain metric spaces the class of Borel computable functions on a certain level is exactly the class of functions which can be expressed as a limit of a pointwise convergent and computable sequence of functions of the next lower level. (shrink)

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between [math] principles over [math]-models of [math]. They also introduced a version of this game that similarly captures provability over [math]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [math] between two (...) principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H. Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between [math] principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of [math], uncovering new differences between their logical strengths. (shrink)

We systematically study the completion of choice problems in the Weihrauch lattice. Choice problems play a pivotal rôle in Weihrauch complexity. For one, they can be used as landmarks that characterize important equivalences classes in the Weihrauch lattice. On the other hand, choice problems also characterize several natural classes of computable problems, such as finite mind change computable problems, non-deterministically computable problems, Las Vegas computable problems and effectively Borel measurable functions. The closure operator of completion generates the (...) concept of total Weihrauch reducibility, which is a variant of Weihrauch reducibility with total realizers. Logically speaking, the completion of a problem is a version of the problem that is independent of its premise. Hence, studying the completion of choice problems allows us to study simultaneously choice problems in the total Weihrauch lattice, as well as the question which choice problems can be made independent of their premises in the usual Weihrauch lattice. The outcome shows that many important choice problems that are related to compact spaces are complete, whereas choice problems for unbounded spaces or closed sets of positive measure are typically not complete. (shrink)

The Lovász local lemma (LLL) is a technique from combinatorics for proving existential results. There are many different versions of the LLL. One of them, the lefthanded local lemma, is particularly well suited for applications to two player games. There are also constructive and computable versions of the LLL. The chief object of this thesis is to prove an effective version of the lefthanded local lemma and to apply it to effectivise constructions of non-repetitive sequences.The second goal of this thesis (...) is to categorize some classes of cohesive powers. We completely describe both the isomorphism types of cohesive powers of equivalence structures and injection structures, as well as clarify the relationship between these cohesive powers and their original structures. We also describe the finite condensation of cohesive powers of computable copies of the integers as a linear order by cohesive sets whose complement are computably enumerable.Finally, we investigate the possibility of decomposing problems in the Weihrauch degrees into a product of first order part and second order part. We give a preliminary result in this direction.Abstract prepared by Daniel Mourad.E-mail: [email protected]: https://daniel-mourad.scholar.uconn.edu/wp-content/uploads/sites/2530/2023/06/ThesisFinalWithRevisio ns-2.pdf. (shrink)

We show that \\) cannot be proved with one typical application of \\) in an intuitionistic extension of \ to higher types, but that this does not remain true when the law of the excluded middle is added. The argument uses Kohlenbach’s axiomatization of higher order reverse mathematics, results related to modified reducibility, and a formalization of Weihrauch reducibility.

We study the computational content of various theorems with reverse mathematical strength around Arithmetical Transfinite Recursion (ATR_0) from the point of view of computability-theoretic reducibilities, in particular Weihrauch reducibility. Our main result states that it is equally hard to construct an embedding between two given well-orderings, as it is to construct a Turing jump hierarchy on a given well-ordering. This answers a question of Marcone. We obtain a similar result for Fraïssé's conjecture restricted to well-orderings.

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)

This thesis is devoted to the exploration of the complexity of some mathematical problems using the framework of computable analysis and descriptive set theory. We will especially focus on Weihrauch reducibility as a means to compare the uniform computational strength of problems. After a short introduction of the relevant background notions, we investigate the uniform computational content of problems arising from theorems that lie at the higher levels of the reverse mathematics hierarchy.We first analyze the strength of the (...) open and clopen Ramsey theorems. Since there is not a canonical way to phrase these theorems as multi-valued functions, we identify eight different multi-valued functions and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility.We then discuss some new operators on multi-valued functions and study their algebraic properties and the relations with other previously studied operators on problems. In particular, we study the first-order part and the deterministic part of a problem f, capturing the Weihrauch degree of the strongest multi-valued problem that is reducible to f and that, respectively, has codomain $\mathbb {N}$ or is single-valued.These notions proved to be extremely useful when exploring the Weihrauch degree of the problem $\mathsf {DS}$ of computing descending sequences in ill-founded linear orders. They allow us to show that $\mathsf {DS}$, and the Weihrauch equivalent problem $\mathsf {BS}$ of finding bad sequences through non-well quasi-orders, while being very “hard” to solve, are rather weak in terms of uniform computational strength. We then generalize $\mathsf {DS}$ and $\mathsf {BS}$ by considering $\boldsymbol {\Gamma }$ -presented orders, where $\boldsymbol {\Gamma }$ is a Borel pointclass or $\boldsymbol {\Delta }^1_1$, $\boldsymbol {\Sigma }^1_1$, $\boldsymbol {\Pi }^1_1$. We study the obtained $\mathsf {DS}$ -hierarchy and $\mathsf {BS}$ -hierarchy of problems in comparison with the Baire hierarchy and show that they do not collapse at any finite level.Finally, we work in the context of geometric measure theory and we focus on the characterization, from the point of view of descriptive set theory, of some conditions involving the notions of Hausdorff/Fourier dimension and Salem sets. We first work in the hyperspace $\mathbf {K}$ of compact subsets of $[0,1]$ and show that the closed Salem sets form a $\boldsymbol {\Pi }^0_3$ -complete family. This is done by characterizing the complexity of the family of sets having sufficiently large Hausdorff or Fourier dimension. We also show that the complexity does not change if we increase the dimension of the ambient space and work in $\mathbf {K}$. We also generalize the results by relaxing the compactness of the ambient space and show that the closed Salem sets are still $\boldsymbol {\Pi }^0_3$ -complete when we endow $\mathbf {F}$ with the Fell topology. A similar result holds also for the Vietoris topology.We conclude by analyzing the same notions from the point of view of effective descriptive set theory and Type-2 Theory of Effectivity, and show that the complexities remain the same also in the lightface case. In particular, we show that the family of all the closed Salem sets is $\Pi ^0_3$ -complete. We furthermore characterize the Weihrauch degree of the functions computing Hausdorff and Fourier dimension of closed sets.prepared by Manlio Valenti.E-mail:[email protected]. (shrink)

Matthias Schröder has asked the question whether there is a weakest discontinuous problem in the topological version of the Weihrauch lattice. Such a problem can be considered as the weakest unsolvable problem. We introduce the discontinuity problem, and we show that it is reducible exactly to the effectively discontinuous problems, defined in a suitable way. However, in which sense this answers Schröder’s question sensitively depends on the axiomatic framework that is chosen, and it is a positive answer if we (...) work in Zermelo–Fraenkel set theory with dependent choice and the axiom of determinacy $\mathsf {AD}$. On the other hand, using the full axiom of choice, one can construct problems which are discontinuous, but not effectively so. Hence, the exact situation at the bottom of the Weihrauch lattice sensitively depends on the axiomatic setting that we choose. We prove our result using a variant of Wadge games for mathematical problems. While the existence of a winning strategy for Player II characterizes continuity of the problem (as already shown by Nobrega and Pauly), the existence of a winning strategy for Player I characterizes effective discontinuity of the problem. By Weihrauch determinacy we understand the condition that every problem is either continuous or effectively discontinuous. This notion of determinacy is a fairly strong notion, as it is not only implied by the axiom of determinacy $\mathsf {AD}$, but it also implies Wadge determinacy. We close with a brief discussion of generalized notions of productivity. (shrink)

We study computability of the abstract linear Cauchy problem equation image)where A is a linear operator, possibly unbounded, on a Banach space X. We give necessary and sufficient conditions for A such that the solution operator K: x ↦ u of the problem is computable. For studying computability we use the representation approach to computable analysis developed by Weihrauch and others. This approach is consistent with the model used by Pour-El/Richards.

The placebo drug reactions from controlled trials were studied for the first time systematically for efficacy and the safety in drug data pooled from randomized, placebo-controlled, multicentre studies. Results: The efficacy of placebo on clinical symptoms and outcome varied between the therapeutic indications. However, no placebo effects on laboratory values, as e.g. blood glucose or Hb1c in diabetics, were noted. The frequency and type of placebo-induced adverse reactions also varied between indication groups. The placebo side effect profile was largely similar (...) to the side effect profile of the active treatment. The mechanisms of placebo effects are manyfold and varied (e.g. endorphin release, conditioning), much lacks explanation. Conclusion: Since the prescription of non-evidence based medicines (= pseudoplacebos) may clearly also result in serious adverse effects, such practice may not only be non-beneficial but may even be harmful. In clinical research, the judicious use of placebo remains essential to establish the efficacy and safety, safeguarding that patients receiving placebo will not be subject to harm and are fully informed. (shrink)

The placebo drug reactions from controlled trials were studied for the first time systematically for efficacy and the safety in drug data pooled from randomized, placebo-controlled, multicentre studies. Results: The efficacy of placebo on clinical symptoms and outcome varied between the therapeutic indications. However, no placebo effects on laboratory values, as e.g. blood glucose or Hb1c in diabetics, were noted. The frequency and type of placebo-induced adverse reactions also varied between indication groups. The placebo side effect profile was largely similar (...) to the side effect profile of the active treatment. The mechanisms of placebo effects are manyfold and varied (e.g. endorphin release, conditioning), much lacks explanation. Conclusion: Since the prescription of non-evidence based medicines (= pseudoplacebos) may clearly also result in serious adverse effects, such practice may not only be non-beneficial but may even be harmful. In clinical research, the judicious use of placebo remains essential to establish the efficacy and safety, safeguarding that patients receiving placebo will not be subject to harm and are fully informed. (shrink)

Every second-countable regular topological space X is metrizable. For a given “computable” topological space satisfying an axiom of computable regularity M. Schröder [10] has constructed a computable metric. In this article we study whether this metric space can be considered computationally as a subspace of some computable metric space [15]. While Schröder's construction is “pointless”, i. e., only sets of a countable base but no concrete points are known, for a computable metric space a concrete dense set of computable points (...) is needed. But there may be no computable points in X. By converging sequences of basis sets instead of Cauchy sequences of points we construct a metric completion of a space together with a canonical representation equation image, equation image. We show that there is a computable embedding of in with computable inverse. Finally, we construct a notation of a dense set of points in with computable mutual distances and prove that the Cauchy representation of the resulting computable metric space is equivalent to equation image. Therefore, every computably regular space has a computable homeomorphic embedding in a computable metric space, which topologically is its completion. By the way we prove a computable Urysohn lemma. (shrink)

For semi-continuous real functions we study different computability concepts defined via computability of epigraphs and hypographs. We call a real function f lower semi-computable of type one, if its open hypograph hypo is recursively enumerably open in dom × ℝ; we call f lower semi-computable of type two, if its closed epigraph Epi is recursively enumerably closed in dom × ℝ; we call f lower semi-computable of type three, if Epi is recursively closed in dom × ℝ. We show that (...) type one and type two semi-computability are independent and that type three semi-computability plus effectively uniform continuity implies computability, which is false for type one and type two instead of type three. We show also that the integral of a type three semi-computable real function on a computable interval is not necessarily computable. (shrink)

A real number x is computable iff it is the limit of an effectively converging computable sequence of rational numbers, and x is left computable iff it is the supremum of a computable sequence of rational numbers. By applying the operations “sup” and “inf” alternately n times to computable sequences of rational numbers we introduce a non-collapsing hierarchy {Σn, Πn, Δn : n ∈ ℕ} of real numbers. We characterize the classes Σ2, Π2 and Δ2 in various ways and give (...) several interesting examples. (shrink)

By the Riesz representation theorem for the dual of C [0; 1], if F: C [0; 1] → ℝ is a continuous linear operator, then there is a function g: [0;1] → ℝ of bounded variation such that F = ∫ f dg . The function g can be normalized such that V = ‖F ‖. In this paper we prove a computable version of this theorem. We use the framework of TTE, the representation approach to computable analysis, which allows (...) to define natural computability for a variety of operators. We show that there are a computable operator S mapping g and an upper bound of its variation to F and a computable operator S ′ mapping F and its norm to some appropriate g. (shrink)

This paper initiates the study of sets in Euclidean spaces ℝn that are defined in terms of the dimensions of their elements. Specifically, given an interval I ⊆ [0, n ], we are interested in the connectivity properties of the set DIMI, consisting of all points in ℝn whose dimensions lie in I, and of its dual DIMIstr, consisting of all points whose strong dimensions lie in I. If I is [0, 1) or.

We show that if M is an r‐maximal set, A is a major subset of M, B is an arbitrary set and, then. We prove that the c.e. ‐degrees are not dense. We also show that there exist infinite collections of ‐degrees and such that the following hold: (i) for every i, j,, and,(ii) each consists entirely of r‐maximal sets, and(iii) each consists entirely of non‐r‐maximal hyperhypersimple sets.

We discuss several axiomatizations of set theory in first order predicate calculus with epsilon and a constant symbol W, starting with the simple system K(W) which has a strong equivalence with ZF without Foundation. The other systems correspond to various extensions of ZF by certain large cardinal hypotheses. These axiomatizations are unusually simple and uncluttered, and are highly suggestive of underlying philosophical principles that generate higher set theory.

We study a refined framework of parameterized complexity theory where the parameter dependence of fixed-parameter tractable algorithms is not arbitrary, but restricted by a function in some family . For every family of functions, this yields a notion of -fixed-parameter tractability. If is the class of all polynomially bounded functions, then -fixed-parameter tractability coincides with polynomial time decidability and if is the class of all computable functions, -fixed-parameter tractability coincides with the standard notion of fixed-parameter tractability. There are interesting choices (...) of between these two extremes, for example the class of all singly exponential functions. In this article, we study the general theory of -fixed-parameter tractability. We introduce a generic notion of reduction and two classes -W[P] and -XP, which may be viewed as analogues of NP and EXPTIME, respectively, in the world of -fixed-parameter tractability. (shrink)

This article is devoted to the conceptual analysis of two texts of leading scholars in cognitive neuroscience and its philosophy, Patricia Churchland and Eric Kandel. After a short introduction about the notion of reduction, I give a detailed account of the way both scientists view the relationship between theories about brain functioning on the one hand and consciousness and psychopathology, respectively, on the other hand. The analysis not only reveals underlying philosophical mind/brain conceptions and their inner tensions, but also the (...) conceptual relevance of distinctions that are fundamental in the work of Dooyeweerd, such as the distinction between modes and entities, between law and subject and between subject function and object function. After a brief clarification of the way these distinctions function in Dooyeweerd’s theory of the body as an ‘enkaptic structural whole’, I try to explain how the conceptual framework, developed here, could be applied to brain functioning and leads to greater clarity in neuroscientific theorizing. (shrink)

*Weitere Angaben Inhalt: Mit der Frage nach der Zuständigkeit der eigenen Nase in Religionsangelegenheiten beginnt diese ungewöhnliche Reise in Erfahrungsbereiche, die von Theologen bislang eher gemieden wurden. Nicht der Inhalt von Glaubensbekenntnissen ist Gegenstand des Interesses, sondern der Tonfall, in dem sie vorgetragen werden. Von bestimmten Kirchengerüchen geht die Rede, von Körperhaltungen beim Gottesdienst, von Kindheitserinnerungen und vom Läuten der Glocken. Dabei stellt sich heraus, dass mit dem abgenützten Etikett des Religiösen die Sinnenfälligkeit des Erlebten nur sehr oberflächlich bezeichnet wird.