Search

In this paper, we study Hausdorff and Fourier dimension from the point of view of effective descriptive set theory and Type-2 Theory of Effectivity. Working in the hyperspace K (X) of compact subsets of X, with X = [ 0 , 1 ] d or X = R d , we characterize the complexity of the family of sets having sufficiently large Hausdorff or Fourier dimension. This, in turn, allows us to show that family of all the closed Salem sets is Π 3 0 -complete. One of our main tools is a careful analysis of the effectiveness of a classical theorem of Kaufman. We furthermore compute the Weihrauch degree of the functions computing Hausdorff and Fourier dimension of closed sets. [ABSTRACT FROM AUTHOR]

We define an on-line (incremental) algorithm that, given a (possibly infinite) pseudo-transitive oriented graph, produces a transitive reorientation. This implies that a theorem of Ghouila-Houri is provable in RCA 0 and hence is computably true. [ABSTRACT FROM AUTHOR]

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 (five corresponding to the open Ramsey theorem and three corresponding to the clopen Ramsey theorem) 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$. [ABSTRACT FROM AUTHOR]

There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far ATR0 has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated. [ABSTRACT FROM AUTHOR]

We introduce notions of continuous strong Weihrauch reducibility and of continuous Weihrauch reducibility for functions with range in a preordered set. Then we associate with such functions certain labeled forests and trees and show that Wadge reducibility, continuous strong Weihrauch reducibility and continuous Weihrauch reducibility between such functions can be characterized by suitable reducibility relations between the associated forests when they are defined. This leads to a combinatorial description of the initial segments of these three hierarchies for those functions defined on the Baire space that have countable range in a bqo set and that are Σ 2 0 -measurable with respect to the reverse Alexandroff topology on the bqo set. Furthermore, we show that the characterization of the topological reducibility relations for bqo-valued functions can be used in order to obtain a similar characterization for the usual Wadge reducibility relation, the continuous strong Weihrauch reducibility relation, and the continuous Weihrauch reducibility relation for multi-valued functions with finite range. [ABSTRACT FROM AUTHOR]

We introduce and study the notion of overt choice for countably-based spaces and for CoPolish spaces. Overt choice is the task of producing a point in a closed set specified by what open sets intersect it. We show that the question of whether overt choice is continuous for a given space is related to topological completeness notions such as the Choquet-property; and to whether variants of Michael's selection theorem hold for that space. For spaces where overt choice is discontinuous it is interesting to explore the resulting Weihrauch degrees, which in turn are related to whether or not the space is Fréchet–Urysohn. [ABSTRACT FROM AUTHOR]

The SRT 2 2 vs. COH problem is a central problem in computable combinatorics and reverse mathematics, asking whether every Turing ideal that satisfies the principle SRT 2 2 also satisfies the principle COH. This paper is a contribution towards further developing some of the main techniques involved in attacking this problem. We study several principles related to each of SRT 2 2 and COH , and prove results that highlight the limits of our current understanding, but also point to new directions ripe for further exploration. [ABSTRACT FROM AUTHOR]

In this paper, we show that the dense existence of nowhere-differentiable continuous functions in C [ 0 , 1 ] is provable, using a version of the Baire category theorem, in an intuitionistic subsystem of elementary analysis whose induction is restricted to Σ 1 0 formulae. [ABSTRACT FROM AUTHOR]

A natural extension of the Wadge hierarchy is obtained if we consider k-partitions (or even Q-partitions for a countable better quasiorder Q) of the Baire space instead of sets (i.e., 2-partitions). Natural initial segments of the Q-Wadge hierarchy were recently characterised in terms of the so called h-quasiorder on suitably iterated Q-labeled countable well founded forests. Though these characterisations are natural and constructive, their definitions are rather long and technical. In this paper, we find clear shorter characterizations as (reducts of) a kind of free structures satisfying some natural axioms. Informally, we provide short and clear axiomatisations of the initial segments. [ABSTRACT FROM AUTHOR]

We consider two combinatorial principles, ERT and ECT. Both are easily proved in RCA 0 plus Σ 2 0 induction. We give two proofs of ERT in RCA 0 , using different methods to eliminate the use of Σ 2 0 induction. Working in the weakened base system RCA 0 ∗ , we prove that ERT is equivalent to Σ 1 0 induction and ECT is equivalent to Σ 2 0 induction. We conclude with a Weihrauch analysis of the principles, showing ERT ≡ W LPO ∗ < W TC N ∗ ≡ W ECT. [ABSTRACT FROM AUTHOR]

Finding the set of leaves for an unbounded tree is a nontrivial process in both the Weihrauch and reverse mathematics settings. Despite this, many combinatorial principles for trees are equivalent to their restrictions to trees with leaf sets. For example, let WF ˆ denote the problem of choosing which trees in a sequence are well-founded, and let PK denote the problem of finding the perfect kernel of a tree. Let WF ˆ L and PK L denote the restrictions of these principles to trees with leaf sets. Then WF ˆ , WF ˆ L , PK , and PK L are all equivalent to Π 1 1 – CA 0 over RCA 0 , and all strongly Weihrauch equivalent. [ABSTRACT FROM AUTHOR]

In reverse mathematics, one sometimes encounters proofs which invoke some theorem multiple times in series, or invoke different theorems in series. One example is the standard proof that Ramsey's theorem for 2 colors implies Ramsey's theorem for 3 colors. A natural question is whether such repeated applications are necessary. Questions like this can be studied under the framework of Weihrauch reducibility. For example, one can attempt to capture the notion of one multivalued function being uniformly reducible to multiple instances of another multivalued function in series. There are three known ways to formalize this notion: the compositional product, the reduction game, and the step product. We clarify the relationships between them by giving sufficient conditions for them to be equivalent. We also show that they are not equivalent in general. [ABSTRACT FROM AUTHOR]

In this paper we study, for n ⩾ 1 , the projection operators over R n , that is the multi-valued functions that associate to x ∈ R n and A ⊆ R n closed, the points of A which are closest to x. We also deal with approximate projections, where we content ourselves with points of A which are almost the closest to x. We use the tools of Weihrauch reducibility to classify these operators depending on the representation of A and the dimension n. It turns out that, depending on the representation of the closed sets and the dimension of the space, the projection and approximate projection operators characterize some of the most fundamental computational classes in the Weihrauch lattice. [ABSTRACT FROM AUTHOR]

When a linear order has an order preserving surjection onto each of its suborders, we say that it is strongly surjective. We prove that the set of countable strongly surjective linear orders is a D ̌ 2 ( Π 1 1) -complete set. Using hypotheses beyond ZFC, we prove the existence of uncountable strongly surjective orders. [ABSTRACT FROM AUTHOR]

Building on previous work by Mummert et al. (2015, The modal logic of Reverse Mathematics. Archive for Mathematical 54 (3-4) 425-437), we study the logic underlying the web of implications and non-implications which constitute the so called reverse mathematics zoo. We introduce a tableaux system for this logic and natural deduction systems for important fragments of the language. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we study the reverse mathematics of two theorems by Bonnet about partial orders. These results concern the structure and cardinality of the collection of initial intervals. The first theorem states that a partial order has no infinite antichains if and only if its initial intervals are finite unions of ideals. The second one asserts that a countable partial order is scattered and does not contain infinite antichains if and only if it has countably many initial intervals. We show that the left to right directions of these theorems are equivalent to and , respectively. On the other hand, the opposite directions are both provable in , but not in . We also prove the equivalence with of the following result of Erdös and Tarski: a partial order with no infinite strong antichains has no arbitrarily large finite strong antichains. [Copyright &y& Elsevier]

We introduce the notion of τ-like partial order, where τ is one of the linear order types ω, ω*, ω + ω*, and ζ. For example, being ω-like means that every element has finitely many predecessors, while being ζ-like means that every interval is finite. We consider statements of the form 'any τ-like partial order has a τ-like linear extension' and 'any τ-like partial order is embeddable into τ' (when τ is ζ this result appears to be new). Working in the framework of reverse mathematics, we show that these statements are equivalent either to \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {B}{\Sigma }^{0}_{2}$\end{document} or to \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {ACA}_0$\end{document} over the usual base system \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\mathsf {RCA}_0$\end{document}. [ABSTRACT FROM AUTHOR]