Order:
  1.  7
    Searching for an Analogue of Atr0 in the Weihrauch Lattice.Takayuki Kihara, Alberto Marcone & Arno Pauly - 2020 - Journal of Symbolic Logic 85 (3):1006-1043.
    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 $\mathrm {ATR}_0$ has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  2.  15
    Closed Choice and a Uniform Low Basis Theorem.Vasco Brattka, Matthew de Brecht & Arno Pauly - 2012 - Annals of Pure and Applied Logic 163 (8):986-1008.
  3.  15
    On the (Semi)Lattices Induced by Continuous Reducibilities.Arno Pauly - 2010 - Mathematical Logic Quarterly 56 (5):488-502.
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  4.  10
    Connected Choice and the Brouwer Fixed Point Theorem.Vasco Brattka, Stéphane Le Roux, Joseph S. Miller & Arno Pauly - 2019 - Journal of Mathematical Logic 19 (1):1950004.
    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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  3
    Luzin’s (N) and Randomness Reflection.Arno Pauly, Linda Westrick & Liang Yu - 2020 - Journal of Symbolic Logic:1-27.
    We show that a computable function $f:\mathbb R\rightarrow \mathbb R$ has Luzin’s property if and only if it reflects $\Pi ^1_1$ -randomness, if and only if it reflects $\Delta ^1_1$ -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$ is R-random, then x is R-random as well. If additionally f is known to have (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  5
    Multi-Valued Functions in Computability Theory.Arno Pauly - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 571--580.
  7.  1
    Luzin’s (N) and Randomness Reflection.Arno Pauly, Linda Westrick & Liang Yu - 2022 - Journal of Symbolic Logic 87 (2):802-828.
    We show that a computable function $f:\mathbb R\rightarrow \mathbb R$ has Luzin’s property if and only if it reflects $\Pi ^1_1$ -randomness, if and only if it reflects $\Delta ^1_1$ -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$ is R-random, then x is R-random as well. If additionally f is known to have (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8.  3
    Finding Descending Sequences Through Ill-Founded Linear Orders.Jun le Goh, Arno Pauly & Manlio Valenti - 2021 - Journal of Symbolic Logic 86 (2):817-854.
    In this work we investigate the Weihrauch degree of the problem Decreasing Sequence of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem Bad Sequence of finding a bad sequence through a given non-well quasi-order. We show that $\mathsf {DS}$, despite being hard to solve, 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 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark