Showing 1–40 of 40 results for author: Pauly, A

More on the indivisibility of $\mathbb{Q}$

Authors: Arno Pauly

Abstract: We study the complexity of the computational task ``Given a colouring $c : \mathbb{Q} \to \mathbf{k}$, find a monochromatic $S \subseteq \mathbb{Q}$ such that $(S,<) \cong (\mathbb{Q},<)$''. The framework is Weihrauch reducibility. Our results answer some open questions recently raised by Gill, and by Dzhafarov, Solomon and Valenti. We study the complexity of the computational task ``Given a colouring $c : \mathbb{Q} \to \mathbf{k}$, find a monochromatic $S \subseteq \mathbb{Q}$ such that $(S,<) \cong (\mathbb{Q},<)$''. The framework is Weihrauch reducibility. Our results answer some open questions recently raised by Gill, and by Dzhafarov, Solomon and Valenti. △ Less

Submitted 4 July, 2024; originally announced July 2024.

MSC Class: 03D30; 05C55

The equational theory of the Weihrauch lattice with multiplication

Authors: Eike Neumann, Arno Pauly, Cécilia Pradic

Abstract: We study the equational theory of the Weihrauch lattice with multiplication, meaning the collection of equations between terms built from variables, the lattice operations $\sqcup$, $\sqcap$, the product $\times$, and the finite parallelization $(-)^*$ which are true however we substitute Weihrauch degrees for the variables. We provide a combinatorial description of these in terms of a reducibilit… ▽ More We study the equational theory of the Weihrauch lattice with multiplication, meaning the collection of equations between terms built from variables, the lattice operations $\sqcup$, $\sqcap$, the product $\times$, and the finite parallelization $(-)^*$ which are true however we substitute Weihrauch degrees for the variables. We provide a combinatorial description of these in terms of a reducibility between finite graphs, and moreover, show that deciding which equations are true in this sense is complete for the third level of the polynomial hierarchy. △ Less

Submitted 20 March, 2024; originally announced March 2024.

MSC Class: 03D30; 08A50; 68Q17

Sequential discontinuity and first-order problems

Authors: Arno Pauly, Giovanni Soldà

Abstract: We explore the low levels of the structure of the continuous Weihrauch degrees of first-order problems. In particular, we show that there exists a minimal discontinuous first-order degree, namely that of $\accn$, without any determinacy assumptions. The same degree is also revealed as the least sequentially discontinuous one, i.e. the least degree with a representative whose restriction to some se… ▽ More We explore the low levels of the structure of the continuous Weihrauch degrees of first-order problems. In particular, we show that there exists a minimal discontinuous first-order degree, namely that of $\accn$, without any determinacy assumptions. The same degree is also revealed as the least sequentially discontinuous one, i.e. the least degree with a representative whose restriction to some sequence converging to a limit point is still discontinuous. The study of games related to continuous Weihrauch reducibility constitutes an important ingredient in the proof of the main theorem. We present some initial additional results about the degrees of first-order problems that can be obtained using this approach. △ Less

Submitted 23 January, 2024; originally announced January 2024.

MSC Class: 03D78; 03D30; 54H05

The weakness of finding descending sequences in ill-founded linear orders

Authors: Jun Le Goh, Arno Pauly, Manlio Valenti

Abstract: We prove that the Weihrauch degree of the problem of finding a bad sequence in a non-well quasi order ($\mathsf{BS}$) is strictly above that of finding a descending sequence in an ill-founded linear order ($\mathsf{DS}$). This corrects our mistaken claim in arXiv:2010.03840, which stated that they are Weihrauch equivalent. We prove that König's lemma $\mathsf{KL}$ and the problem… ▽ More We prove that the Weihrauch degree of the problem of finding a bad sequence in a non-well quasi order ($\mathsf{BS}$) is strictly above that of finding a descending sequence in an ill-founded linear order ($\mathsf{DS}$). This corrects our mistaken claim in arXiv:2010.03840, which stated that they are Weihrauch equivalent. We prove that König's lemma $\mathsf{KL}$ and the problem $\mathsf{wList}_{2^{\mathbb{N}},\leqω}$ of enumerating a given non-empty countable closed subset of $2^\mathbb{N}$ are not Weihrauch reducible to $\mathsf{DS}$ either, resolving two main open questions raised in arXiv:2010.03840. △ Less

Submitted 2 July, 2024; v1 submitted 22 January, 2024; originally announced January 2024.

MSC Class: 03D30 03D78 06A75

Minimal covers in the Weihrauch degrees

Authors: Steffen Lempp, Joseph S. Miller, Arno Pauly, Mariya I. Soskova, Manlio Valenti

Abstract: In this paper, we study the existence of minimal covers and strong minimal covers in the Weihrauch degrees. We characterize when a problem $f$ is a minimal cover or strong minimal cover of a problem $h$. We show that strong minimal covers only exist in the cone below $\mathsf{id}$ and that the Weihrauch lattice above $\mathsf{id}$ is dense. From this, we conclude that the degree of $\mathsf{id}$ i… ▽ More In this paper, we study the existence of minimal covers and strong minimal covers in the Weihrauch degrees. We characterize when a problem $f$ is a minimal cover or strong minimal cover of a problem $h$. We show that strong minimal covers only exist in the cone below $\mathsf{id}$ and that the Weihrauch lattice above $\mathsf{id}$ is dense. From this, we conclude that the degree of $\mathsf{id}$ is first-order definable in the Weihrauch degrees and that the first-order theory of the Weihrauch degrees is computably isomorphic to third-order arithmetic. △ Less

Submitted 21 November, 2023; originally announced November 2023.

MSC Class: 03D30 03D78

Embeddability of graphs and Weihrauch degrees

Authors: Vittorio Cipriani, Arno Pauly

Abstract: We study the complexity of the following related computational tasks concerning a fixed countable graph G: 1. Does a countable graph H provided as input have a(n induced) subgraph isomorphic to G? 2. Given a countable graph H that has a(n induced) subgraph isomorphic to G, find such a subgraph. The framework for our investigations is given by effective Wadge reducibility and by Weihrauch reducibil… ▽ More We study the complexity of the following related computational tasks concerning a fixed countable graph G: 1. Does a countable graph H provided as input have a(n induced) subgraph isomorphic to G? 2. Given a countable graph H that has a(n induced) subgraph isomorphic to G, find such a subgraph. The framework for our investigations is given by effective Wadge reducibility and by Weihrauch reducibility. Our work follows on "Reverse mathematics and Weihrauch analysis motivated by finite complexity theory" (Computability, 2021) by BeMent, Hirst and Wallace, and we answer several of their open questions. △ Less

Submitted 16 January, 2024; v1 submitted 1 May, 2023; originally announced May 2023.

MSC Class: 05C60; 54H05; 03D30

On the Weihrauch degree of the additive Ramsey theorem

Authors: Arno Pauly, Cécilia Pradic, Giovanni Solda

Abstract: We characterize the strength, in terms of Weihrauch degrees, of certain problems related to Ramsey-like theorems concerning colourings of the rationals and of the natural numbers. The theorems we are chiefly interested in assert the existence of almost-homogeneous sets for colourings of pairs of rationals respectively natural numbers satisfying properties determined by some additional algebraic st… ▽ More We characterize the strength, in terms of Weihrauch degrees, of certain problems related to Ramsey-like theorems concerning colourings of the rationals and of the natural numbers. The theorems we are chiefly interested in assert the existence of almost-homogeneous sets for colourings of pairs of rationals respectively natural numbers satisfying properties determined by some additional algebraic structure on the set of colours. In the context of reverse mathematics, most of the principles we study are equivalent to $Σ^0_2$-induction over $\mathrm{RCA}_0$. The associated problems in the Weihrauch lattice are related to $\mathrm{TC}_\mathbb{N}^*$, $(\mathrm{LPO}')^*$ or their product, depending on their precise formalizations. △ Less

Submitted 4 December, 2023; v1 submitted 7 January, 2023; originally announced January 2023.

MSC Class: 03B30; 03D78; 03D30

Finding descending sequences through ill-founded linear orders

Authors: Jun Le Goh, Arno Pauly, Manlio Valenti

Abstract: In this work we investigate the Weihrauch degree of the problem $\mathsf{DS}$ of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem $\mathsf{BS}$ of finding a bad sequence through a given non-well quasi-order. We show that $\mathsf{DS}$, despite being hard to solve (it has computable inputs with no hyperarithmetic solution), is rather w… ▽ More In this work we investigate the Weihrauch degree of the problem $\mathsf{DS}$ of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem $\mathsf{BS}$ of finding a bad sequence through a given non-well quasi-order. We show that $\mathsf{DS}$, despite being hard to solve (it has computable inputs with no hyperarithmetic solution), is rather weak in terms of uniform computational strength. To make the latter precise, we introduce the notion of the deterministic part of a Weihrauch degree. We then generalize $\mathsf{DS}$ and $\mathsf{BS}$ by considering $\boldsymbolΓ$-presented orders, where $\boldsymbolΓ$ is a Borel pointclass or $\boldsymbolΔ^1_1$, $\boldsymbolΣ^1_1$, $\boldsymbolΠ^1_1$. We study the obtained $\mathsf{DS}$-hierarchy and $\mathsf{BS}$-hierarchy of problems in comparison with the (effective) Baire hierarchy and show that they do not collapse at any finite level. △ Less

Submitted 24 January, 2024; v1 submitted 8 October, 2020; originally announced October 2020.

Comments: Added errata. The problems $\mathsf{DS}$ and $\mathsf{BS}$ are not Weihrauch-equivalent, and the separation has been proved in arXiv:2401.11807. Please check the errata for the full list of changes

MSC Class: 03D30 03D78 06A75

Journal ref: J. symb. log. 86 (2021) 817-854

An update on Weihrauch complexity, and some open questions

Authors: Arno Pauly

Abstract: This is an informal survey of progress in Weihrauch complexity (cf arXiv:1707.03202) in the period 2018-2020. Open questions are emphasised. This is an informal survey of progress in Weihrauch complexity (cf arXiv:1707.03202) in the period 2018-2020. Open questions are emphasised. △ Less

Submitted 25 August, 2020; originally announced August 2020.

Comments: Extended abstract for invited talk at CCA 2020 (http://cca-net.de/cca2020/)

MSC Class: 03D78; 03D28

Luzin's (N) and randomness reflection

Authors: Arno Pauly, Linda Westrick, Liang Yu

Abstract: We show that a computable function $f:\mathbb R\rightarrow\mathbb R$ has Luzin's property (N) if and only if it reflects $Π^1_1$-randomnes, if and only if it reflects $Δ^1_1(\mathcal O)$-randomness, and if and only if it reflects $\mathcal O$-Kurtz randomness, but reflecting Martin-Löf randomness or weak-2-randomness does not suffice. Here a function $f$ is said to reflect a randomness notion $R$… ▽ More We show that a computable function $f:\mathbb R\rightarrow\mathbb R$ has Luzin's property (N) if and only if it reflects $Π^1_1$-randomnes, if and only if it reflects $Δ^1_1(\mathcal O)$-randomness, and if and only if it reflects $\mathcal O$-Kurtz randomness, but reflecting Martin-Löf randomness or weak-2-randomness does not suffice. Here a function $f$ is said to reflect a randomness notion $R$ if whenever $f(x)$ is $R$-random, then $x$ is $R$-random as well. If additionally $f$ is known to have bounded variation, then we show $f$ has Luzin's (N) if and only if it reflects weak-2-randomness, and if and only if it reflects $\emptyset'$-Kurtz randomness. This links classical real analysis with algorithmic randomness. △ Less

Submitted 25 September, 2020; v1 submitted 12 June, 2020; originally announced June 2020.

Comments: 25 pages

MSC Class: 03D32; 26A30

Convex choice, finite choice and sorting

Authors: Takayuki Kihara, Arno Pauly

Abstract: We study the Weihrauch degrees of closed choice for finite sets, closed choice for convex sets and sorting infinite sequences over finite alphabets. Our main results are: One, that choice for finite sets of cardinality $i + 1$ is reducible to choice for convex sets in dimension $j$, which in turn is reducible to sorting infinite sequences over an alphabet of size $k + 1$, iff $i \leq j \leq k$. Tw… ▽ More We study the Weihrauch degrees of closed choice for finite sets, closed choice for convex sets and sorting infinite sequences over finite alphabets. Our main results are: One, that choice for finite sets of cardinality $i + 1$ is reducible to choice for convex sets in dimension $j$, which in turn is reducible to sorting infinite sequences over an alphabet of size $k + 1$, iff $i \leq j \leq k$. Two, that convex choice in dimension two is not reducible to the product of convex choice in dimension one with itself. Three, that sequential composition of one-dimensional convex choice is not reducible to convex choice in any dimension. The latter solves an open question raised at a Dagstuhl seminar on Weihrauch reducibility in 2015. Our proofs invoke Kleene's recursion theorem, and we describe in some detail how Kleene's recursion theorem gives rise to a technique for proving separations of Weihrauch degrees. △ Less

Submitted 1 May, 2019; originally announced May 2019.

MSC Class: 03F60; 03D30

Enumeration degrees and non-metrizable topology

Authors: Takayuki Kihara, Keng Meng Ng, Arno Pauly

Abstract: The enumeration degrees of sets of natural numbers can be identified with the degrees of difficulty of enumerating neighborhood bases of points in a universal second-countable $T_0$-space (e.g. the $ω$-power of the Sierpiński space). Hence, every represented second-countable $T_0$-space determines a collection of enumeration degrees. For instance, Cantor space captures the total degrees, and the H… ▽ More The enumeration degrees of sets of natural numbers can be identified with the degrees of difficulty of enumerating neighborhood bases of points in a universal second-countable $T_0$-space (e.g. the $ω$-power of the Sierpiński space). Hence, every represented second-countable $T_0$-space determines a collection of enumeration degrees. For instance, Cantor space captures the total degrees, and the Hilbert cube captures the continuous degrees by definition. Based on these observations, we utilize general topology (particularly non-metrizable topology) to establish a classification theory of enumeration degrees of sets of natural numbers. △ Less

Submitted 17 September, 2020; v1 submitted 8 April, 2019; originally announced April 2019.

MSC Class: 03D28; 54G20; 54A05; 54D10; 54H05

Effective local compactness and the hyperspace of located sets

Authors: Arno Pauly

Abstract: We revisit the definition of effective local compactness, and propose an approach that works for arbitrary countably-based spaces extending the previous work on computable metric spaces. We use this to show that effective local compactness suffices to ensure that the hyperspace of closed-and-overt sets (aka located sets, aka closed sets with full information) is computably compact and computably m… ▽ More We revisit the definition of effective local compactness, and propose an approach that works for arbitrary countably-based spaces extending the previous work on computable metric spaces. We use this to show that effective local compactness suffices to ensure that the hyperspace of closed-and-overt sets (aka located sets, aka closed sets with full information) is computably compact and computably metrizable. △ Less

Submitted 13 March, 2019; originally announced March 2019.

Comments: Working paper

MSC Class: 03F60

Computability Aspects of Differential Games in Euclidian Spaces

Authors: Gafurjan Ibragimov, Bakh Khoussainov, Arno Pauly

Abstract: We study computability-theoretic aspects of differential games. Our focus is on pursuit and evasion games played in Euclidean spaces in the tradition of Rado's "Lion versus Man" game. In some ways, these games can be viewed as continuous versions of reachability games. We prove basic undecidability of differential games, and study natural classes of pursuit-evasion games in Euclidean spaces where… ▽ More We study computability-theoretic aspects of differential games. Our focus is on pursuit and evasion games played in Euclidean spaces in the tradition of Rado's "Lion versus Man" game. In some ways, these games can be viewed as continuous versions of reachability games. We prove basic undecidability of differential games, and study natural classes of pursuit-evasion games in Euclidean spaces where the winners can win via computable strategies. The winning strategy for Man found by Besicovitch for the traditional "Lion versus Man" is not computable. We show how to modify it to yield a computable non-deterministic winning strategy, and raise the question whether Man can win in a computable and deterministic way. △ Less

Submitted 2 March, 2019; originally announced March 2019.

MSC Class: 49N70; 03D78

Overt choice

Authors: Matthew de Brecht, Arno Pauly, Matthias Schröder

Abstract: 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'… ▽ More 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 Frechet-Urysohn. △ Less

Submitted 14 February, 2019; originally announced February 2019.

MSC Class: 54H99; 54D55; 03D80

Combinatorial principles equivalent to weak induction

Authors: Caleb Davis, Denis R. Hirschfeldt, Jeffry L. Hirst, Jake Pardo, Arno Pauly, Keita Yokoyama

Abstract: We consider two combinatorial principles, ${\sf{ERT}}$ and ${\sf{ECT}}$. Both are easily proved in ${\sf{RCA}}_0$ plus ${Σ^0_2}$ induction. We give two proofs of ${\sf{ERT}}$ in ${\sf{RCA}}_0$, using different methods to eliminate the use of ${Σ^0_2}$ induction. Working in the weakened base system ${\sf{RCA}}_0^*$, we prove that ${\sf{ERT}}$ is equivalent to ${Σ^0_1}$ induction and ${\sf{ECT}}$ is… ▽ More We consider two combinatorial principles, ${\sf{ERT}}$ and ${\sf{ECT}}$. Both are easily proved in ${\sf{RCA}}_0$ plus ${Σ^0_2}$ induction. We give two proofs of ${\sf{ERT}}$ in ${\sf{RCA}}_0$, using different methods to eliminate the use of ${Σ^0_2}$ induction. Working in the weakened base system ${\sf{RCA}}_0^*$, we prove that ${\sf{ERT}}$ is equivalent to ${Σ^0_1}$ induction and ${\sf{ECT}}$ is equivalent to ${Σ^0_2}$ induction. We conclude with a Weihrauch analysis of the principles, showing ${\sf{ERT}} {\equiv_{\rm W}} {\sf{LPO}}^* {<_{\rm W}}{\sf{TC}_{\mathbb N}}^* {\equiv_{\rm W}} {\sf{ECT}}$. △ Less

Submitted 24 December, 2018; originally announced December 2018.

MSC Class: 03B30; 03F35; 03D30

Searching for an analogue of ATR in the Weihrauch lattice

Authors: Takayuki Kihara, Alberto Marcone, Arno Pauly

Abstract: 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 ATR_0 has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candid… ▽ More 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 ATR_0 has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated. △ Less

Submitted 13 January, 2020; v1 submitted 4 December, 2018; originally announced December 2018.

MSC Class: 03D30; 03F50; 03F60

Journal ref: The Journal of Symbolic Logic 85 (2020), 1006-1043

Projection operators in the Weihrauch lattice

Authors: Guido Gherardi, Alberto Marcone, Arno Pauly

Abstract: In this paper we study the Weihrauch complexity of projection operators onto closed subsets of the Euclidean space. We show that some fundamental degrees of the Weihrauch lattice can be characterized in terms of such operators. In this paper we study the Weihrauch complexity of projection operators onto closed subsets of the Euclidean space. We show that some fundamental degrees of the Weihrauch lattice can be characterized in terms of such operators. △ Less

Submitted 7 November, 2018; v1 submitted 30 May, 2018; originally announced May 2018.

Comments: A few changes following the referee report

Journal ref: Computability, vol. 8, no. 3-4, pp. 281-304, 2019

Ramsey's theorem and products in the Weihrauch degrees

Authors: Damir D. Dzhafarov, Jun Le Goh, Denis R. Hirschfeldt, Ludovic Patey, Arno Pauly

Abstract: We study the positions in the Weihrauch lattice of parallel products of various combinatorial principles related to Ramsey's theorem. Among other results, we obtain an answer to a question of Brattka, by showing that Ramsey's theorem for pairs ($\mathsf{RT}^2_2$) is strictly Weihrauch below the parallel product of the stable Ramsey's theorem for pairs and the cohesive principle (… ▽ More We study the positions in the Weihrauch lattice of parallel products of various combinatorial principles related to Ramsey's theorem. Among other results, we obtain an answer to a question of Brattka, by showing that Ramsey's theorem for pairs ($\mathsf{RT}^2_2$) is strictly Weihrauch below the parallel product of the stable Ramsey's theorem for pairs and the cohesive principle ($\mathsf{SRT}^2_2 \times \mathsf{COH}$). △ Less

Submitted 20 October, 2019; v1 submitted 29 April, 2018; originally announced April 2018.

Comments: 30 pages

Weihrauch Complexity in Computable Analysis

Authors: Vasco Brattka, Guido Gherardi, Arno Pauly

Abstract: We provide a self-contained introduction into Weihrauch complexity and its applications to computable analysis. This includes a survey on some classification results and a discussion of the relation to other approaches. We provide a self-contained introduction into Weihrauch complexity and its applications to computable analysis. This includes a survey on some classification results and a discussion of the relation to other approaches. △ Less

Submitted 7 December, 2018; v1 submitted 11 July, 2017; originally announced July 2017.

Comments: 50 pages plus 11 pages appendix

Journal ref: in: Brattka, V. and Hertling, P. (eds.), Handbook of Computability and Complexity in Analysis, Theory and Applications of Computability, Springer, Cham, 2021, pages 367-417

Noetherian Quasi-Polish Spaces

Authors: Matthew de Brecht, Arno Pauly

Abstract: In the presence of suitable power spaces, compactness of $\mathbf{X}$ can be characterized as the singleton $\{X\}$ being open in the space $\mathcal{O}(\mathbf{X})$ of open subsets of $\mathbf{X}$. Equivalently, this means that universal quantification over a compact space preserves open predicates. Using the language of represented spaces, one can make sense of notions such as a $Σ^0_2$-subset… ▽ More In the presence of suitable power spaces, compactness of $\mathbf{X}$ can be characterized as the singleton $\{X\}$ being open in the space $\mathcal{O}(\mathbf{X})$ of open subsets of $\mathbf{X}$. Equivalently, this means that universal quantification over a compact space preserves open predicates. Using the language of represented spaces, one can make sense of notions such as a $Σ^0_2$-subset of the space of $Σ^0_2$-subsets of a given space. This suggests higher-order analogues to compactness: We can, e.g.~, investigate the spaces $\mathbf{X}$ where $\{X\}$ is a $Δ^0_2$-subset of the space of $Δ^0_2$-subsets of $\mathbf{X}$. Call this notion $\nabla$-compactness. As $Δ^0_2$ is self-dual, we find that both universal and existential quantifier over $\nabla$-compact spaces preserve $Δ^0_2$ predicates. Recall that a space is called Noetherian iff every subset is compact. Within the setting of Quasi-Polish spaces, we can fully characterize the $\nabla$-compact spaces: A Quasi-Polish space is Noetherian iff it is $\nabla$-compact. Note that the restriction to Quasi-Polish spaces is sufficiently general to include plenty of examples. △ Less

Submitted 18 January, 2017; v1 submitted 25 July, 2016; originally announced July 2016.

MSC Class: 54B30; 03F60; 03G30

The Vitali Covering Theorem in the Weihrauch Lattice

Authors: Vasco Brattka, Guido Gherardi, Rupert Hölzl, Arno Pauly

Abstract: We study the uniform computational content of the Vitali Covering Theorem for intervals using the tool of Weihrauch reducibility. We show that a more detailed picture emerges than what a related study by Giusto, Brown, and Simpson has revealed in the setting of reverse mathematics. In particular, different formulations of the Vitali Covering Theorem turn out to have different uniform computational… ▽ More We study the uniform computational content of the Vitali Covering Theorem for intervals using the tool of Weihrauch reducibility. We show that a more detailed picture emerges than what a related study by Giusto, Brown, and Simpson has revealed in the setting of reverse mathematics. In particular, different formulations of the Vitali Covering Theorem turn out to have different uniform computational content. These versions are either computable or closely related to uniform variants of Weak Weak Kőnig's Lemma. △ Less

Submitted 26 July, 2016; v1 submitted 11 May, 2016; originally announced May 2016.

Comments: 13 pages

Journal ref: in: A. Day et al. (Eds.) Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, Springer, 2017, LNCS vol. 10010, pp. 188-200

On the algebraic structure of Weihrauch degrees

Authors: Vasco Brattka, Arno Pauly

Abstract: We introduce two new operations (compositional products and implication) on Weihrauch degrees, and investigate the overall algebraic structure. The validity of the various distributivity laws is studied and forms the basis for a comparison with similar structures such as residuated lattices and concurrent Kleene algebras. Introducing the notion of an ideal with respect to the compositional product… ▽ More We introduce two new operations (compositional products and implication) on Weihrauch degrees, and investigate the overall algebraic structure. The validity of the various distributivity laws is studied and forms the basis for a comparison with similar structures such as residuated lattices and concurrent Kleene algebras. Introducing the notion of an ideal with respect to the compositional product, we can consider suitable quotients of the Weihrauch degrees. We also prove some specific characterizations using the implication. In order to introduce and study compositional products and implications, we introduce and study a function space of multi-valued continuous functions. This space turns out to be particularly well-behaved for effectively traceable spaces that are closely related to admissibly represented spaces. △ Less

Submitted 24 October, 2018; v1 submitted 28 April, 2016; originally announced April 2016.

Journal ref: Logical Methods in Computer Science, Volume 14, Issue 4, Computability and logic (October 25, 2018) lmcs:3854

Game characterizations and lower cones in the Weihrauch degrees

Authors: Hugo Nobrega, Arno Pauly

Abstract: We introduce a parametrized version of the Wadge game for functions and show that each lower cone in the Weihrauch degrees is characterized by such a game. These parametrized Wadge games subsume the original Wadge game, the eraser and backtrack games as well as Semmes's tree games. In particular, we propose that the lower cones in the Weihrauch degrees are the answer to Andretta's question on whic… ▽ More We introduce a parametrized version of the Wadge game for functions and show that each lower cone in the Weihrauch degrees is characterized by such a game. These parametrized Wadge games subsume the original Wadge game, the eraser and backtrack games as well as Semmes's tree games. In particular, we propose that the lower cones in the Weihrauch degrees are the answer to Andretta's question on which classes of functions admit game characterizations. We then discuss some applications of such parametrized Wadge games. Using machinery from Weihrauch reducibility theory, we introduce games characterizing every (transfinite) level of the Baire hierarchy via an iteration of a pruning derivative on countably branching trees. △ Less

Submitted 5 August, 2019; v1 submitted 11 November, 2015; originally announced November 2015.

MSC Class: 03E15; 54H05; 03D60; 03F15

Journal ref: Logical Methods in Computer Science, Volume 15, Issue 3 (August 6, 2019) lmcs:4284

Computability on the space of countable ordinals

Authors: Arno Pauly

Abstract: While there is a well-established notion of what a computable ordinal is, the question which functions on the countable ordinals ought to be computable has received less attention so far. We propose a notion of computability on the space of countable ordinals via a representation in the sense of computable analysis. The computability structure is characterized by the computability of four specific… ▽ More While there is a well-established notion of what a computable ordinal is, the question which functions on the countable ordinals ought to be computable has received less attention so far. We propose a notion of computability on the space of countable ordinals via a representation in the sense of computable analysis. The computability structure is characterized by the computability of four specific operations, and we prove further relevant operations to be computable. Some alternative approaches are discussed, too. As an application in effective descriptive set theory, we can then state and prove computable uniform versions of the Lusin separation theorem and the Hausdorff-Kuratowski theorem. Furthermore, we introduce an operator on the Weihrauch lattice corresponding to iteration of some principle over a countable ordinal. △ Less

Submitted 9 April, 2017; v1 submitted 2 January, 2015; originally announced January 2015.

Comments: corrected Theorem 21 from v2

MSC Class: 03E15; 54H05; 03D60; 03F15

How constructive is constructing measures?

Authors: Arno Pauly, Willem L. Fouché

Abstract: Given some set, how hard is it to construct a measure supported by it? We classify some variations of this task in the Weihrauch lattice. Particular attention is paid to Frostman measures on sets with positive Hausdorff dimension. As a side result, the Weihrauch degree of Hausdorff dimension itself is determined. Given some set, how hard is it to construct a measure supported by it? We classify some variations of this task in the Weihrauch lattice. Particular attention is paid to Frostman measures on sets with positive Hausdorff dimension. As a side result, the Weihrauch degree of Hausdorff dimension itself is determined. △ Less

Submitted 11 September, 2014; originally announced September 2014.

MSC Class: 03D78; 03B30; 28A33 ACM Class: F.1.0

The descriptive theory of represented spaces

Authors: Arno Pauly

Abstract: This is a survey on the ongoing development of a descriptive theory of represented spaces, which is intended as an extension of both classical and effective descriptive set theory to deal with both sets and functions between represented spaces. Most material is from work-in-progress, and thus there may be a stronger focus on projects involving the author than an objective survey would merit. This is a survey on the ongoing development of a descriptive theory of represented spaces, which is intended as an extension of both classical and effective descriptive set theory to deal with both sets and functions between represented spaces. Most material is from work-in-progress, and thus there may be a stronger focus on projects involving the author than an objective survey would merit. △ Less

Submitted 22 August, 2014; originally announced August 2014.

Comments: survey of work-in-progress

MSC Class: 03E15; 26A21; 54H05; 18B25 ACM Class: F.4.1

Point degree spectra of represented spaces

Authors: Takayuki Kihara, Arno Pauly

Abstract: We introduce the point degree spectrum of a represented space as a substructure of the Medvedev degrees, which integrates the notion of Turing degrees, enumeration degrees, continuous degrees, and so on. The notion of point degree spectrum creates a connection among various areas of mathematics including computability theory, descriptive set theory, infinite dimensional topology and Banach space t… ▽ More We introduce the point degree spectrum of a represented space as a substructure of the Medvedev degrees, which integrates the notion of Turing degrees, enumeration degrees, continuous degrees, and so on. The notion of point degree spectrum creates a connection among various areas of mathematics including computability theory, descriptive set theory, infinite dimensional topology and Banach space theory. Through this new connection, for instance, we construct a family of continuum many infinite dimensional Cantor manifolds with property $C$ whose Borel structures at an arbitrary finite rank are mutually non-isomorphic. This provides new examples of Banach algebras of real valued Baire class two functions on metrizable compacta, and strengthen various theorems in infinite dimensional topology such as Pol's solution to Alexandrov's old problem. △ Less

Submitted 4 August, 2017; v1 submitted 27 May, 2014; originally announced May 2014.

MSC Class: 03D78; 03D30; 54F45; 54H05; 46J10 ACM Class: F.4.1

Non-deterministic computation and the Jayne-Rogers Theorem

Authors: Arno Pauly, Matthew de Brecht

Abstract: We provide a simple proof of a computable analogue to the Jayne Rogers Theorem from descriptive set theory. The difficulty of the proof is delegated to a simulation result pertaining to non-deterministic type-2 machines. Thus, we demonstrate that developments in computational models can have applications in fields thought to be far removed from it. We provide a simple proof of a computable analogue to the Jayne Rogers Theorem from descriptive set theory. The difficulty of the proof is delegated to a simulation result pertaining to non-deterministic type-2 machines. Thus, we demonstrate that developments in computational models can have applications in fields thought to be far removed from it. △ Less

Submitted 31 March, 2014; originally announced April 2014.

Comments: In Proceedings DCM 2012, arXiv:1403.7579

ACM Class: F.1.1

Journal ref: EPTCS 143, 2014, pp. 87-96

A comparison of concepts from computable analysis and effective descriptive set theory

Authors: Vassilios Gregoriades, Tamás Kispéter, Arno Pauly

Abstract: Computable analysis and effective descriptive set theory are both concerned with complete metric spaces, functions between them and subsets thereof in an effective setting. The precise relationship of the various definitions used in the two disciplines has so far been neglected, a situation this paper is meant to remedy. As the role of the Cauchy completion is relevant for both effective approac… ▽ More Computable analysis and effective descriptive set theory are both concerned with complete metric spaces, functions between them and subsets thereof in an effective setting. The precise relationship of the various definitions used in the two disciplines has so far been neglected, a situation this paper is meant to remedy. As the role of the Cauchy completion is relevant for both effective approaches to Polish spaces, we consider the interplay of effectivity and completion in some more detail. △ Less

Submitted 13 August, 2015; v1 submitted 31 March, 2014; originally announced March 2014.

Comments: accepted for publication in the special issue of "Mathematical Structures in Computer Science" dedicated to CCC 2013

MSC Class: 03E15; 03D78 ACM Class: F.2

Equilibria in multi-player multi-outcome infinite sequential games

Authors: Stéphane Le Roux, Arno Pauly

Abstract: We investigate the existence of certain types of equilibria (Nash, $\varepsilon$-Nash, subgame perfect, $\varepsilon$-subgame perfect, Pareto-optimal) in multi-player multi-outcome infinite sequential games. We use two fundamental approaches: one requires strong topological restrictions on the games, but produces very strong existence results. The other merely requires some very basic determinacy… ▽ More We investigate the existence of certain types of equilibria (Nash, $\varepsilon$-Nash, subgame perfect, $\varepsilon$-subgame perfect, Pareto-optimal) in multi-player multi-outcome infinite sequential games. We use two fundamental approaches: one requires strong topological restrictions on the games, but produces very strong existence results. The other merely requires some very basic determinacy properties to still obtain some existence results. Both results are transfer results: starting with the existence of some equilibria for a small class of games, they allow us to conclude the existence of some type of equilibria for a larger class. To make the abstract results more concrete, we investigate as a special case infinite sequential games with real-valued payoff functions. Depending on the class of payoff functions (continuous, upper semi-continuous, Borel) and whether the game is zero-sum, we obtain various existence results for equilibria. Our results hold for games with two or up to countably many players. △ Less

Submitted 16 March, 2016; v1 submitted 14 January, 2014; originally announced January 2014.

Comments: Section 8 of Version 1 is no longer part of the article, and will in time be made available elsewhere; Section 7 of Version 2 has been expanded into http://arxiv.org/abs/1602.08912

MSC Class: 91A13; 91A18; 03E15 ACM Class: F.4

Function spaces for second-order polynomial time

Authors: Akitoshi Kawamura, Arno Pauly

Abstract: In the context of second-order polynomial-time computability, we prove that there is no general function space construction. We proceed to identify restrictions on the domain or the codomain that do provide a function space with polynomial-time function evaluation containing all polynomial-time computable functions of that type. As side results we show that a polynomial-time counterpart to admis… ▽ More In the context of second-order polynomial-time computability, we prove that there is no general function space construction. We proceed to identify restrictions on the domain or the codomain that do provide a function space with polynomial-time function evaluation containing all polynomial-time computable functions of that type. As side results we show that a polynomial-time counterpart to admissibility of a representation is not a suitable criterion for natural representations, and that the Weihrauch degrees embed into the polynomial-time Weihrauch degrees. △ Less

Submitted 27 October, 2015; v1 submitted 13 January, 2014; originally announced January 2014.

MSC Class: 68Q15; 03D30; 03D65 ACM Class: F.1.3; I.1.1

Towards Synthetic Descriptive Set Theory: An instantiation with represented spaces

Authors: Arno Pauly, Matthew de Brecht

Abstract: Using ideas from synthetic topology, a new approach to descriptive set theory is suggested. Synthetic descriptive set theory promises elegant explanations for various phenomena in both classic and effective descriptive set theory. Presently, we mainly focus on developing the ideas in the category of represented spaces. Using ideas from synthetic topology, a new approach to descriptive set theory is suggested. Synthetic descriptive set theory promises elegant explanations for various phenomena in both classic and effective descriptive set theory. Presently, we mainly focus on developing the ideas in the category of represented spaces. △ Less

Submitted 2 June, 2014; v1 submitted 7 July, 2013; originally announced July 2013.

MSC Class: 03E15; 54H05; 03D78; 18A99 ACM Class: F.4.1

Finite choice, convex choice and finding roots

Authors: Stéphane Le Roux, Arno Pauly

Abstract: We investigate choice principles in the Weihrauch lattice for finite sets on the one hand, and convex sets on the other hand. Increasing cardinality and increasing dimension both correspond to increasing Weihrauch degrees. Moreover, we demonstrate that the dimension of convex sets can be characterized by the cardinality of finite sets encodable into them. Precisely, choice from an n+1 point set is… ▽ More We investigate choice principles in the Weihrauch lattice for finite sets on the one hand, and convex sets on the other hand. Increasing cardinality and increasing dimension both correspond to increasing Weihrauch degrees. Moreover, we demonstrate that the dimension of convex sets can be characterized by the cardinality of finite sets encodable into them. Precisely, choice from an n+1 point set is reducible to choice from a convex set of dimension n, but not reducible to choice from a convex set of dimension n-1. Furthermore we consider searching for zeros of continuous functions. We provide an algorithm producing 3n real numbers containing all zeros of a continuous function with up to n local minima. This demonstrates that having finitely many zeros is a strictly weaker condition than having finitely many local extrema. We can prove 3n to be optimal. △ Less

Submitted 1 December, 2015; v1 submitted 2 February, 2013; originally announced February 2013.

Comments: An earlier version was titled "Closed choice: Cardinality vs convex dimension"

Journal ref: Logical Methods in Computer Science, Volume 11, Issue 4 (December 2, 2015) lmcs:1607

Theta divisors of stable vector bundles may be nonreduced

Authors: George H. Hitching, With an appendix by Christian Pauly

Abstract: A generic strictly semistable bundle of degree zero over a curve X has a reducible theta divisor, given by the sum of the theta divisors of the stable summands of the associated graded bundle. The converse is not true: Beauville and Raynaud have each constructed stable bundles with reducible theta divisors. For X of genus at least 5, we construct stable vector bundles over X of rank $r$ for all… ▽ More A generic strictly semistable bundle of degree zero over a curve X has a reducible theta divisor, given by the sum of the theta divisors of the stable summands of the associated graded bundle. The converse is not true: Beauville and Raynaud have each constructed stable bundles with reducible theta divisors. For X of genus at least 5, we construct stable vector bundles over X of rank $r$ for all $r \geq 5$, with reducible and nonreduced theta divisors. We also adapt the construction to symplectic bundles. In the appendix, Raynaud's original example of a stable rank 2 vector bundle with reducible theta divisor over a bi-elliptic curve of genus 3 is generalized to bi-elliptic curves of genus $g \geq 3$. △ Less

Submitted 8 June, 2013; v1 submitted 5 November, 2012; originally announced November 2012.

Comments: 18 pages. Some statements improved. Appendix by Christian Pauly added

MSC Class: 14H60

Connected Choice and the Brouwer Fixed Point Theorem

Authors: Vasco Brattka, Stéphane Le Roux, Joseph S. Miller, Arno Pauly

Abstract: We study the computational content of the Brouwer Fixed Point Theorem in the Weihrauch lattice. Connected choice is the operation that finds a point in a non-empty connected closed set given by negative information. One of our main results is that for any fixed dimension the Brouwer Fixed Point Theorem of that dimension is computably equivalent to connected choice of the Euclidean unit cube of the… ▽ More We study the computational content of the Brouwer Fixed Point Theorem in the Weihrauch lattice. Connected choice is the operation that finds a point in a non-empty connected closed set given by negative information. One of our main results is that for any fixed dimension the Brouwer Fixed Point Theorem of that dimension is computably equivalent to connected choice of the Euclidean unit cube of the same dimension. Another main result is that connected choice is complete for dimension greater than or equal to two in the sense that it is computably equivalent to Weak Kőnig's Lemma. While we can present two independent proofs for dimension three and upwards that are either based on a simple geometric construction or a combinatorial argument, the proof for dimension two is based on a more involved inverse limit construction. The connected choice operation in dimension one is known to be equivalent to the Intermediate Value Theorem; we prove that this problem is not idempotent in contrast to the case of dimension two and upwards. We also prove that Lipschitz continuity with Lipschitz constants strictly larger than one does not simplify finding fixed points. Finally, we prove that finding a connectedness component of a closed subset of the Euclidean unit cube of any dimension greater or equal to one is equivalent to Weak Kőnig's Lemma. In order to describe these results, we introduce a representation of closed subsets of the unit cube by trees of rational complexes. △ Less

Submitted 9 November, 2018; v1 submitted 21 June, 2012; originally announced June 2012.

Comments: 36 pages

MSC Class: 03D30; 03D78; 03F60; 37C25

Journal ref: Journal of Mathematical Logic 19:1 (2019) 1-46

On the topological aspects of the theory of represented spaces

Authors: Arno Pauly

Abstract: Represented spaces form the general setting for the study of computability derived from Turing machines. As such, they are the basic entities for endeavors such as computable analysis or computable measure theory. The theory of represented spaces is well-known to exhibit a strong topological flavour. We present an abstract and very succinct introduction to the field; drawing heavily on prior work… ▽ More Represented spaces form the general setting for the study of computability derived from Turing machines. As such, they are the basic entities for endeavors such as computable analysis or computable measure theory. The theory of represented spaces is well-known to exhibit a strong topological flavour. We present an abstract and very succinct introduction to the field; drawing heavily on prior work by Escardó, Schröder, and others. Central aspects of the theory are function spaces and various spaces of subsets derived from other represented spaces, and -- closely linked to these -- properties of represented spaces such as compactness, overtness and separation principles. Both the derived spaces and the properties are introduced by demanding the computability of certain mappings, and it is demonstrated that typically various interesting mappings induce the same property. △ Less

Submitted 2 March, 2015; v1 submitted 17 April, 2012; originally announced April 2012.

Comments: Earlier versions were titled "Compactness and separation for represented spaces" and "A new introduction to the theory of represented spaces"

MSC Class: 54D99; 03F60 ACM Class: F.3

Relative Computability and Uniform Continuity of Relations

Authors: Arno Pauly, Martin Ziegler

Abstract: A type-2 computable real function is necessarily continuous; and this remains true for relative, i.e. oracle-based computations. Conversely, by the Weierstrass Approximation Theorem, every continuous f:[0,1]->R is computable relative to some oracle. In their search for a similar topological characterization of relatively computable multivalued functions f:[0,1]=>R (aka relations), Brattka and He… ▽ More A type-2 computable real function is necessarily continuous; and this remains true for relative, i.e. oracle-based computations. Conversely, by the Weierstrass Approximation Theorem, every continuous f:[0,1]->R is computable relative to some oracle. In their search for a similar topological characterization of relatively computable multivalued functions f:[0,1]=>R (aka relations), Brattka and Hertling (1994) have considered two notions: weak continuity (which is weaker than relative computability) and strong continuity (which is stronger than relative computability). Observing that uniform continuity plays a crucial role in the Weierstrass Theorem, we propose and compare several notions of uniform continuity for relations. Here, due to the additional quantification over values y in f(x), new ways of (linearly) ordering quantifiers arise, yet none of them turn out as satisfactory. We are thus led to a notion of uniform continuity based on the Henkin Quantifier; and prove it necessary for relative computability. In fact iterating this condition yields a strict hierarchy of notions each necessary, and the omega-th level also sufficient, for relative computability. △ Less

Submitted 8 September, 2011; v1 submitted 16 May, 2011; originally announced May 2011.

Comments: 23 pages, 5 figures

MSC Class: 03F60; 03D78; 54C08

Many-one reductions and the category of multivalued functions

Authors: Arno Pauly

Abstract: Multi-valued functions are common in computable analysis (built upon the Type 2 Theory of Effectivity), and have made an appearance in complexity theory under the moniker search problems leading to complexity classes such as PPAD and PLS being studied. However, a systematic investigation of the resulting degree structures has only been initiated in the former situation so far (the Weihrauch-degree… ▽ More Multi-valued functions are common in computable analysis (built upon the Type 2 Theory of Effectivity), and have made an appearance in complexity theory under the moniker search problems leading to complexity classes such as PPAD and PLS being studied. However, a systematic investigation of the resulting degree structures has only been initiated in the former situation so far (the Weihrauch-degrees). A more general understanding is possible, if the category-theoretic properties of multi-valued functions are taken into account. In the present paper, the category-theoretic framework is established, and it is demonstrated that many-one degrees of multi-valued functions form a distributive lattice under very general conditions, regardless of the actual reducibility notions used (e.g. Cook, Karp, Weihrauch). Beyond this, an abundance of open questions arises. Some classic results for reductions between functions carry over to multi-valued functions, but others do not. The basic theme here again depends on category-theoretic differences between functions and multi-valued functions. △ Less

Submitted 30 December, 2015; v1 submitted 15 February, 2011; originally announced February 2011.

Comments: an earlier version was titled "Many-one reductions between search problems". in Mathematical Structures in Computer Science, 2015

MSC Class: 03D30; 03D65; 68Q15; 18D99 ACM Class: F.1.3; F.1.1

Closed Choice and a Uniform Low Basis Theorem

Authors: Vasco Brattka, Matthew de Brecht, Arno Pauly

Abstract: We study closed choice principles for different spaces. Given information about what does not constitute a solution, closed choice determines a solution. We show that with closed choice one can characterize several models of hypercomputation in a uniform framework using Weihrauch reducibility. The classes of functions which are reducible to closed choice of the singleton space, of the natural numb… ▽ More We study closed choice principles for different spaces. Given information about what does not constitute a solution, closed choice determines a solution. We show that with closed choice one can characterize several models of hypercomputation in a uniform framework using Weihrauch reducibility. The classes of functions which are reducible to closed choice of the singleton space, of the natural numbers, of Cantor space and of Baire space correspond to the class of computable functions, of functions computable with finitely many mind changes, of weakly computable functions and of effectively Borel measurable functions, respectively. We also prove that all these classes correspond to classes of non-deterministically computable functions with the respective spaces as advice spaces. Moreover, we prove that closed choice on Euclidean space can be considered as "locally compact choice" and it is obtained as product of closed choice on the natural numbers and on Cantor space. We also prove a Quotient Theorem for compact choice which shows that single-valued functions can be "divided" by compact choice in a certain sense. Another result is the Independent Choice Theorem, which provides a uniform proof that many choice principles are closed under composition. Finally, we also study the related class of low computable functions, which contains the class of weakly computable functions as well as the class of functions computable with finitely many mind changes. As one main result we prove a uniform version of the Low Basis Theorem that states that closed choice on Cantor space (and the Euclidean space) is low computable. We close with some related observations on the Turing jump operation and its initial topology. △ Less

Submitted 28 September, 2010; v1 submitted 14 February, 2010; originally announced February 2010.

Journal ref: Annals of Pure and Applied Logic 163:8 (2012) 986--1008